On the performance of the ICP algorithm

DOI10.1016/J.COMGEO.2007.10.007MaRDI QIDQ934025zbMATH OpenOpenAlexFDO

Authors Esther Ezra, Micha Sharir, Alon Efrat

Publication date 29 July 2008

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2007.10.007

zbMATH Keywords

Hausdorff distanceiterative closest point (ICP) algorithm proposednearest neighborspattern matchingVoronoi diagrams

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Review text

A rigorous analysis is given for the iterative closest point (ICP) algorithm proposed by \textit{P. J. Besl} and {N. D. McKay} [A method for registration of 3-d shapes, IEEE Trans. Pattern Anal. Mach. Intell. 14, No. 2, 239--256 (1992)] as a successful heuristic for matching of point sets in \(d\)-space under translation. They consider two measures: The RMS (root mean squared distance) and the (one-sided) Hausdorff distance. They showed that in both cases the number of iterations performed by the algorithm is polynomial in the number of input points.

Recommendations

• Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method
• Iterative closest geometric objects registration
• scientific article; zbMATH DE number 2043656
• Reliable updates of the transformation in the iterative closest point algorithm
• Geometry and convergence analysis of algorithms for registration of 3D shapes

Cites work

• An Optimal-Time Algorithm for Slope Selection
• How fast is the \(k\)-means method?
• scientific article; zbMATH DE number 5506231 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• scientific article; zbMATH DE number 1424291 (Why is no real title available?)

Cited in

(8)

• Iterative closest geometric objects registration
• Nonrigid registration using Gaussian processes and local likelihood estimation
• FPTAS for minimizing the earth mover's distance under rigid transformations and related problems
• Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method
• scientific article; zbMATH DE number 1945212 (Why is no real title available?)
• scientific article; zbMATH DE number 2043656 (Why is no real title available?)
• Reliable updates of the transformation in the iterative closest point algorithm
• Surface estimation for multiple misaligned point sets

This page was built for publication: On the performance of the ICP algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q934025)