Geometry and convergence analysis of algorithms for registration of 3D shapes

Helmut Pottmann*, Qi Xing Huang, Yong Liang Yang, Shi Min Hu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

152 Scopus citations

Abstract

The computation of a rigid body transformation which optimally aligns a set of measurement points with a surface and related registration problems are studied from the viewpoint of geometry and optimization. We provide a convergence analysis for widely used registration algorithms such as ICP, using either closest points (Besl and McKay, 1992) or tangent planes at closest points (Chen and Medioni, 1991) and for a recently developed approach based on quadratic approximants of the squared distance function (Pottmann et al., 2004). ICP based on closest points exhibits local linear convergence only. Its counterpart which minimizes squared distances to the tangent planes at closest points is a Gauss-Newton iteration; it achieves local quadratic convergence for a zero residual problem and - if enhanced by regularization and step size control-comes close to quadratic convergence in many realistic scenarios. Quadratically convergent algorithms are based on the approach in (Pottmann et al., 2004). The theoretical results are supported by a number of experiments; there, we also compare the algorithms with respect to global convergence behavior, stability and running time.

Original languageEnglish (US)
Pages (from-to)277-296
Number of pages20
JournalInternational Journal of Computer Vision
Volume67
Issue number3
DOIs
StatePublished - May 1 2006

Keywords

  • Convergence analysis
  • Distance function
  • ICP algorithm
  • Kinematics
  • Optimization
  • Registration
  • Rigid registration

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Geometry and convergence analysis of algorithms for registration of 3D shapes'. Together they form a unique fingerprint.

Cite this