Jump to content

Iterative closest point

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by BG19bot (talk | contribs) at 23:18, 14 October 2015 (WP:CHECKWIKI error fix for #61. Punctuation goes before References. Do general fixes if a problem exists. - using AWB (11700)). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Iterative Closest Point (ICP) [1][2][3] is an algorithm employed to minimize the difference between two clouds of points. ICP is often used to reconstruct 2D or 3D surfaces from different scans, to localize robots and achieve optimal path planning (especially when wheel odometry is unreliable due to slippery terrain), to co-register bone models, etc.

In the algorithm, one point cloud, the reference, or target, is kept fixed, while the other one, the source, is transformed to best match the reference. The algorithm iteratively revises the transformation (combination of translation and rotation) needed to minimize the distance from the source to the reference point cloud.

Inputs: reference and source point clouds, initial estimation of the transformation to align the source to the reference (optional), criteria for stopping the iterations.

Output: refined transformation.

Essentially, the algorithm steps are:

  1. For each point in the source point cloud, find the closest point in the reference point cloud.
  2. Estimate the combination of rotation and translation using a mean squared error cost function that will best align each source point to its match found in the previous step.
  3. Transform the source points using the obtained transformation.
  4. Iterate (re-associate the points, and so on).

Zhang [3] proposes a modified K-D tree algorithm for efficient closest point computation. In this work a statistical method based on the distance distribution is used to deal with outliers, occlusion, appearance, and disappearance, which enables subset-subset matching.

There exist many ICP variants,[4] from which point-to-point and point-to-plane are the most popular. The latter usually performs better in structured environments.[5][6]

Implementations

  • Sparse ICP Robust implementation of the ICP algorithm using sparse norms (both point to plane and point to point). Header only C++ (Mozilla Public License v. 2.0)
  • libpointmatcher is an implementation of both point-to-point and point-to-plane ICP. It is released under a permissive BSD license.
  • LIBICP: C++ Library for Iterative Closest Point Matching, released under the GNU General Public License.
  • ICP implements many variants of ICP in Matlab. It is release under the BSD license.
  • MeshLab an open source mesh processing tool that includes a GNU General Public License implementation of the ICP algorithm.
  • CloudCompare an open source point and model processing tool that includes an implementation of the ICP algorithm. Released under the GNU General Public License.
  • PCL (Point Cloud Library) is an open-source framework for n-dimensional point clouds and 3D geometry processing. It includes several variants of the ICP algorithm.
  • Open source C++ implementations of the ICP algorithm are available in VTK and ITK libraries.

References

  1. ^ Besl, Paul J.; N.D. McKay (1992). "A Method for Registration of 3-D Shapes". IEEE Trans. on Pattern Analysis and Machine Intelligence. 14 (2). Los Alamitos, CA, USA: IEEE Computer Society: 239–256. doi:10.1109/34.121791.
  2. ^ Chen, Yang; Gerard Medioni (1991). "Object modelling by registration of multiple range images". Image Vision Comput. Newton, MA, USA: Butterworth-Heinemann: 145–155. doi:10.1016/0262-8856(92)90066-C.
  3. ^ a b Zhang, Zhengyou (1994). "Iterative point matching for registration of free-form curves and surfaces". International Journal of Computer Vision. 13 (12). Springer: 119–152. doi:10.1007/BF01427149.
  4. ^ Pomerleau, François; Colas, Francis; Siegwart, Roland (2015). "A Review of Point Cloud Registration Algorithms for Mobile Robotics". Foundations and Trends in Robotics. 4 (1): 1–104. doi:10.1561/2300000035.
  5. ^ http://www.comp.nus.edu.sg/~lowkl/publications/lowk_point-to-plane_icp_techrep.pdf
  6. ^ François Pomerleau, Francis Colas, Roland Siegwart, and Stéphane Magnenat. Comparing ICP Variants on Real-World Data Sets. In Autonomous Robots, 34(3), pages 133–148, DOI: 10.1007/s10514-013-9327-2, April 2013.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Iterative_closest_point&oldid=685780359"