Iterative closest point

From HandWiki
Short description: Algorithm
Idea behind the iterative closest point algorithm

Iterative closest point (ICP)[1][2][3][4] 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.

Overview

The Iterative Closest Point algorithm keeps one point cloud, the reference or target, fixed, while transforming the other, the source, to best match the reference. The transformation (combination of translation and rotation) is iteratively estimated in order to minimize an error metric, typically the sum of squared differences between the coordinates of the matched pairs. ICP is one of the widely used algorithms in aligning three dimensional models given an initial guess of the rigid transformation required.[5] The ICP algorithm was first introduced by Chen and Medioni,[3] and Besl and McKay.[2]

The Iterative Closest Point algorithm contrasts with the Kabsch algorithm and other solutions to the orthogonal Procrustes problem in that the Kabsch algorithm requires correspondence between point sets as an input, whereas Iterative Closest Point treats correspondence as a variable to be estimated.

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:[5]

  1. For each point (from the whole set of vertices usually referred to as dense or a selection of pairs of vertices from each model) in the source point cloud, match the closest point in the reference point cloud (or a selected set).
  2. Estimate the combination of rotation and translation using a root mean square point to point distance metric minimization technique which will best align each source point to its match found in the previous step. This step may also involve weighting points and rejecting outliers prior to alignment.
  3. Transform the source points using the obtained transformation.
  4. Iterate (re-associate the points, and so on).

Zhang [4] 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,[6] from which point-to-point and point-to-plane are the most popular. The latter usually performs better in structured environments.[7][8]

Implementations

  • 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.[9]
  • Open source C++ implementations of the ICP algorithm are available in VTK, ITK and Open3D libraries.
  • libpointmatcher is an implementation of point-to-point and point-to-plane ICP released under a BSD license.
  • simpleICP is an implementation of a rather simple version of the ICP algorithm in various languages.

See also

References

  1. ↑ Arun, Somani; Thomas S. Huang; Steven D. Blostein (1987). "Least-square fitting of two 3-D point sets". IEEE Pattern Analysis and Machine Intelligence 9 (5): 698–700. doi:10.1109/TPAMI.1987.4767965. PMID 21869429. 
  2. ↑ 2.0 2.1 Besl, Paul J.; N.D. McKay (1992). "A Method for Registration of 3-D Shapes". IEEE Transactions on Pattern Analysis and Machine Intelligence 14 (2): 239–256. doi:10.1109/34.121791. 
  3. ↑ 3.0 3.1 Chen, Yang; Gerard Medioni (1991). "Object modelling by registration of multiple range images". Image Vision Comput. 10 (3): 145–155. doi:10.1016/0262-8856(92)90066-C. 
  4. ↑ 4.0 4.1 Zhang, Zhengyou (1994). "Iterative point matching for registration of free-form curves and surfaces". International Journal of Computer Vision 13 (12): 119–152. doi:10.1007/BF01427149. 
  5. ↑ 5.0 5.1 Rusinkiewicz, Szymon; Marc Levoy (2001). "Efficient Variants of the ICP Algorithm". Proceedings Third International Conference on 3-D Digital Imaging and Modeling. Quebec City, Quebec, Canada. pp. 145–152. doi:10.1109/IM.2001.924423. 
  6. ↑ 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. https://www.researchgate.net/publication/277558596. 
  7. ↑ Kok-Lim Low (February 2004). "Linear Least-Squares Optimization for Point-to-Plane ICP Surface Registration". Technical Report TR04-004, Department of Computer Science, University of North Carolina at Chapel Hill. http://www.comp.nus.edu.sg/~lowkl/publications/lowk_point-to-plane_icp_techrep.pdf. Retrieved 2017-02-27. 
  8. ↑ 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.
  9. ↑ Holz, Dirk; Ichim, Alexandru E.; Tombari, Federico; Rusu, Radu B.; Behnke, Sven (2015). "Registration with the Point Cloud Library: A Modular Framework for Aligning in 3-D". IEEE Robotics Automation Magazine 22 (4): 110–124. doi:10.1109/MRA.2015.2432331. https://www.researchgate.net/publication/283198426. 



Retrieved from "https://handwiki.org/wiki/index.php?title=Iterative_closest_point&oldid=3429550"