Design and analysis of optimization methods for subdivision surface fitting.
We present a complete framework for computing a subdivision surface to approximate unorganized point sample data, which is a separable nonlinear least squares problem. We study the convergence and stability of three geometrically-motivated optimization schemes and reveal their intrinsic relations with standard methods for constrained nonlinear optimization. A commonly-used method in graphics, called point distance minimization, is shown to use a variant of the gradient descent step and thus has only linear convergence. The second method, called tangent distance minimization, which is well-known in computer vision, is shown to use the Gauss-Newton step, and thus demonstrates near quadratic convergence for zero residual problems but may not converge otherwise. Finally, we show that an optimization scheme called squared distance minimization, recently proposed by Pottmann et al., can be derived from the Newton method. Hence, with proper regularization, tangent distance minimization and squared distance minimization are more efficient than point distance minimization. We also investigate the effects of two step size control methods -- Levenberg-Marquardt regularization and the Armijo rule -- on the convergence stability and efficiency of the above optimization schemes.
Cheng
Kin-Shing
KS
Department of Computer Science, The University of Hong Kong, Hong Kong. ksdcheng@cs.hku.hk
Wang
Wenping
W
Qin
Hong
H
Wong
Kwan-Yee
KY
Yang
Huaiping
H
Liu
Yang
Y
D000465:Algorithms; D001185:Artificial Intelligence; D003198:Computer Simulation; D007089:Image Enhancement / Q000379:methods; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D021621:Imaging, Three-Dimensional / Q000379:methods*; D016247:Information Storage and Retrieval / Q000379:methods; D008962:Models, Theoretical; D010363:Pattern Recognition, Automated / Q000379:methods*; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D012984:Software; D012985:Software Design; D013382:Subtraction Technique