Fast Nonlinear Least Squares Optimization of Large‐Scale Semi‐Sparse Problems
Fast Nonlinear Least Squares Optimization of Large‐Scale Semi‐Sparse Problems
复制标题
大规模半稀疏问题的快速非线性最小二乘优化
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
T. Beeler
中科院分区：
文献类型：
--
作者：
M. Fratarcangeli;D. Bradley;Aurel Gruber;Gaspard Zoss;T. Beeler
计算机图形和视觉中的许多问题都可以表述为非线性最小二乘优化问题，对此有许多现成的求解器可供使用。然而，根据问题的结构，现有的求解器可能或多或少合适，并且在某些情况下，解决方案的代价是收敛时间过长。其中一种情况是半稀疏优化问题，例如在局部面部性能重建中出现的问题，其中非线性最小二乘问题可以由数十万个成本函数组成，每个成本函数都涉及许多优化参数。虽然这些问题可以用现有的求解器来解决，但计算时间会严重阻碍这些方法的适用性。我们引入了一种新颖的迭代求解器，用于大规模半稀疏问题的非线性最小二乘优化。我们使用非线性 Levenberg-Marquardt 方法基于其一阶近似来并行局部线性化问题。然后，我们使用局部 Schur 补集将线性问题分解为小块，从而形成更紧凑的线性系统，而不会丢失信息。由此产生的系统是密集的，但其尺寸足够小，可以在短时间内使用并行直接方法进行求解。使用这种方法的主要好处是整个优化过程完全并行且可扩展，使其适合映射到图形硬件（GPU）上。通过使用我们的最小化器，获得结果的速度比其他现有求解器快一个数量级，而不会牺牲模型的通用性和准确性。我们对我们的方法进行了详细分析，并使用最近提出的解剖局部面部变形模型应用基于性能的面部捕捉来验证我们的结果。
Many problems in computer graphics and vision can be formulated as a nonlinear least squares optimization problem, for which numerous off‐the‐shelf solvers are readily available. Depending on the structure of the problem, however, existing solvers may be more or less suitable, and in some cases the solution comes at the cost of lengthy convergence times. One such case is semi‐sparse optimization problems, emerging for example in localized facial performance reconstruction, where the nonlinear least squares problem can be composed of hundreds of thousands of cost functions, each one involving many of the optimization parameters. While such problems can be solved with existing solvers, the computation time can severely hinder the applicability of these methods. We introduce a novel iterative solver for nonlinear least squares optimization of large‐scale semi‐sparse problems. We use the nonlinear Levenberg‐Marquardt method to locally linearize the problem in parallel, based on its first‐order approximation. Then, we decompose the linear problem in small blocks, using the local Schur complement, leading to a more compact linear system without loss of information. The resulting system is dense but its size is small enough to be solved using a parallel direct method in a short amount of time. The main benefit we get by using such an approach is that the overall optimization process is entirely parallel and scalable, making it suitable to be mapped onto graphics hardware (GPU). By using our minimizer, results are obtained up to one order of magnitude faster than other existing solvers, without sacrificing the generality and the accuracy of the model. We provide a detailed analysis of our approach and validate our results with the application of performance‐based facial capture using a recently‐proposed anatomical local face deformation model.
DOI：
10.1145/3197517.3201354
发表时间：
2018-07
期刊：
ACM Transactions on Graphics (TOG)
影响因子：
--
作者：
Xianzhong Fang;H. Bao;Y. Tong;M. Desbrun;Jin Huang
通讯作者：
Xianzhong Fang;H. Bao;Y. Tong;M. Desbrun;Jin Huang
影响因子：
6.2
作者：
Zollhoefer, Michael;Niessner, Matthias;Stamminger, Marc
通讯作者：
Stamminger, Marc