ICP Algorithm: Theory, Practice and Its SLAM-oriented Taxonomy

Hao Bai

doi:10.54254/2755-2721/2/20220512

Research Article

Open access

Published on 22 March 2023

Download pdf

Bai,H. (2023). ICP Algorithm: Theory, Practice and Its SLAM-oriented Taxonomy. Applied and Computational Engineering,2,451-462.

Export citation

ICP Algorithm: Theory, Practice and Its SLAM-oriented Taxonomy

Hao Bai ¹

¹ University of Illinois Urbana-Champaign, UIUC Champaign, Illinois, USA

* Author to whom correspondence should be addressed.

https://doi.org/10.54254/2755-2721/2/20220512

Abstract

The Iterative Closest Point (ICP) algorithm is one of the most important algorithms for ge-ometric alignment of three-dimensional surface registration, which is frequently used in computer vision tasks, including the Simultaneous Localization And Mapping (SLAM) tasks. In this paper, we illustrate the theoretical principles of the ICP algorithm, how it can be used in surface registration tasks, and the traditional taxonomy of the variants of the ICP algorithm. As SLAM is becoming a popular topic, we also introduce a SLAM-oriented taxonomy of the ICP algorithm, based on the characteristics of each type of SLAM task, including whether the SLAM task is online or not and whether the landmarks are present as features in the SLAM task. We make a synthesis of each type of SLAM task by compar-ing several up-to-date research papers and analyzing their implementation details.

Keywords

Iterative Closest Point Algorithm, Simultaneous Localization and Mapping, Surface Registration, Algorithm Taxonomy

View pdf

References

[1]. Schenker, Paul S. "Sensor fusion IV: Control paradigms and data structures; Proceedings of the Meeting, Boston, MA, Nov. 12-15, 1991." (1992).

[2]. Censi, Andrea. "An ICP variant using a point-to-line metric." 2008 IEEE International Confer-ence on Robotics and Automation. Ieee, 2008.

[3]. Low, Kok-Lim. "Linear least-squares optimization for point-to-plane icp surface registra-tion." Chapel Hill, University of North Carolina 4.10 (2004): 1-3.

[4]. Jost, Timothée, and Heinz Hugli. "A multi-resolution scheme ICP algorithm for fast shape regis-tration." Proceedings. First International Symposium on 3D Data Processing Visualization and Transmission. IEEE, 2002.

[5]. Men, Hao, Biruk Gebre, and Kishore Pochiraju. "Color point cloud registration with 4D ICP al-gorithm." 2011 IEEE International Conference on Robotics and Automation. IEEE, 2011.

[6]. Rusinkiewicz, Szymon, and Marc Levoy. "Efficient variants of the ICP algorithm." Proceedings third international conference on 3-D digital imaging and modeling. IEEE, 2001.

[7]. Pomerleau, François, et al. "Comparing ICP variants on real-world data sets." Autonomous Ro-bots 34.3 (2013): 133-148.

[8]. Ezra, Esther, Micha Sharir, and Alon Efrat. "On the performance of the ICP algo-rithm." Computational Geometry 41.1-2 (2008): 77-93.

[9]. Durrant-Whyte, Hugh, and Tim Bailey. "Simultaneous localization and mapping: part I." IEEE robotics & automation magazine 13.2 (2006): 99-110.

[10]. Bailey, Tim, and Hugh Durrant-Whyte. "Simultaneous localization and mapping (SLAM): Part II." IEEE robotics & automation magazine 13.3 (2006): 108-117.

[11]. Dissanayake, MWM Gamini, et al. "A solution to the simultaneous localization and map building (SLAM) problem." IEEE Transactions on robotics and automation 17.3 (2001): 229-241.

[12]. Pritsker, A. Alan B. "Applications of SLAM." IIE Transactions 14.1 (1982): 70-77.

[13]. Singandhupe, Ashutosh, and Hung Manh La. "A review of slam techniques and security in au-tonomous driving." 2019 third IEEE international conference on robotic computing (IRC). IEEE, 2019.

[14]. Grisetti, Giorgio, et al. "A tutorial on graph-based SLAM." IEEE Intelligent Transportation Systems Magazine 2.4 (2010): 31-43.

[15]. Mur-Artal, Raul, Jose Maria Martinez Montiel, and Juan D. Tardos. "ORB-SLAM: a versatile and accurate monocular SLAM system." IEEE transactions on robotics 31.5 (2015): 1147-1163.

[16]. Davison, Andrew J., et al. "MonoSLAM: Real-time single camera SLAM." IEEE transactions on pattern analysis and machine intelligence 29.6 (2007): 1052-1067.

[17]. Engel, Jakob, Thomas Schöps, and Daniel Cremers. "LSD-SLAM: Large-scale direct monocular SLAM." European conference on computer vision. Springer, Cham, 2014.

[18]. Kok, Manon, and Arno Solin. "Scalable magnetic field SLAM in 3D using Gaussian process maps." 2018 21st international conference on information fusion (FUSION). IEEE, 2018.

[19]. Choi, Changhyun, Alexander JB Trevor, and Henrik I. Christensen. "RGB-D edge detection and edge-based registration." 2013 IEEE/RSJ International Conference on Intelligent Robots and Sys-tems. IEEE, 2013.

[20]. Weise, Thibaut, et al. "Online loop closure for real-time interactive 3D scanning." Computer Vi-sion and Image Understanding 115.5 (2011): 635-648.

[21]. Johnson, Andrew E., and Martial Hebert. "Surface registration by matching oriented points." Proceedings. International Conference on Recent Advances in 3-D Digital Imaging and Modeling (Cat. No. 97TB100134). IEEE, 1997.

[22]. Li, Hao, Robert W. Sumner, and Mark Pauly. "Global correspondence optimization for non‐rigid registration of depth scans." Computer graphics forum. Vol. 27. No. 5. Oxford, UK: Black-well Publishing Ltd, 2008.

[23]. Aiger, Dror, Niloy J. Mitra, and Daniel Cohen-Or. "4-points congruent sets for robust pairwise surface registration." ACM SIGGRAPH 2008 papers. 2008. 1-10.

[24]. Audette, Michel A., Frank P. Ferrie, and Terry M. Peters. "An algorithmic overview of surface registration techniques for medical imaging." Medical image analysis 4.3 (2000): 201-217.

[25]. Chua, Chin Seng, and Ray Jarvis. "3D free-form surface registration and object recogni-tion." International journal of computer vision 17.1 (1996): 77-99.

[26]. Bergevin, Robert, Denis Laurendeau, and Denis Poussart. "Registering range views of multipart objects." Computer vision and image understanding 61.1 (1995): 1-16.

[27]. Batlle, Elisabet, Carles Matabosch, and Joaquim Salvi. "Summarizing image/surface registration for 6dof robot/camera pose estimation." Iberian Conference on Pattern Recognition and Image Analysis. Springer, Berlin, Heidelberg, 2007.

[28]. Lenac, Kruno, et al. "Fast planar surface 3D SLAM using LIDAR." Robotics and Autonomous Systems 92 (2017): 197-220.

[29]. Whelan, Thomas, et al. "ElasticFusion: Dense SLAM without a pose graph." Robotics: Science and Systems, 2015.

[30]. Kim, Pileun, Jingdao Chen, and Yong K. Cho. "SLAM-driven robotic mapping and registration of 3D point clouds." Automation in Construction 89 (2018): 38-48.

[31]. Bar‐Shalom, Yaakov, Thomas E. Fortmann, and Peter G. Cable. "Tracking and data associa-tion." (1990): 918-919.

[32]. Tucker, Thomas M., and Thomas R. Kurfess. "Newton methods for parametric surface registra-tion. Part I. Theory." Computer-Aided Design 35.1 (2003): 107-114.

[33]. Chow, Chi Kin, Hung Tat Tsui, and Tong Lee. "Surface registration using a dynamic genetic al-gorithm." Pattern recognition 37.1 (2004): 105-117.

[34]. Amberg, Brian, Sami Romdhani, and Thomas Vetter. "Optimal step nonrigid ICP algorithms for surface registration." 2007 IEEE conference on computer vision and pattern recognition. IEEE, 2007.

[35]. Granger, Sébastien, and Xavier Pennec. "Multi-scale EM-ICP: A fast and robust approach for surface registration." European Conference on Computer Vision. Springer, Berlin, Heidelberg, 2002.

[36]. Kuramachi, Ryo, et al. "G-ICP SLAM: An odometry-free 3D mapping system with robust 6DoF pose estimation." 2015 IEEE International Conference on Robotics and Biomimetics (ROBIO). IEEE, 2015.

[37]. Simon, Dan. Optimal state estimation: Kalman, H infinity, and nonlinear approaches. John Wiley & Sons, 2006.

[38]. Mu, Xufu, et al. "Accurate Initial State Estimation in a Monocular Visual–Inertial SLAM Sys-tem." Sensors 18.2 (2018): 506.

[39]. Weiss, Stephan, and Roland Siegwart. "Real-time metric state estimation for modular vision-inertial systems." 2011 IEEE international conference on robotics and automation. IEEE, 2011.

[40]. Gordon, Neil J., David J. Salmond, and Adrian FM Smith. "Novel approach to nonlinear/non-Gaussian Bayesian state estimation." IEE Proceedings F-radar and signal processing. Vol. 140. No. 2. IET, 1993.

[41]. Huang, Shoudong, and Gamini Dissanayake. "Convergence and consistency analysis for extend-ed Kalman filter based SLAM." IEEE Transactions on robotics 23.5 (2007): 1036-1049.

[42]. Sim, Robert, et al. "Vision-based SLAM using the Rao-Blackwellised particle filter." IJCAI Workshop on Reasoning with Uncertainty in Robotics. Vol. 14. No. 1. 2005.

[43]. Huang, G. Q., A. B. Rad, and Y. K. Wong. "Online SLAM in dynamic environments." ICAR'05. Proceedings., 12th International Conference on Advanced Robotics, 2005.. IEEE, 2005.

[44]. Labbe, Mathieu, and François Michaud. "Online global loop closure detection for large-scale multi-session graph-based SLAM." 2014 IEEE/RSJ International Conference on Intelligent Ro-bots and Systems. IEEE, 2014.

[45]. Golfarelli, Matteo, Dario Maio, and Stefano Rizzi. "Elastic correction of dead-reckoning errors in map building." Proceedings. 1998 IEEE/RSJ International Conference on Intelligent Robots and Systems. Innovations in Theory, Practice and Applications (Cat. No. 98CH36190). Vol. 2. IEEE, 1998.

[46]. Konolige, Kurt. "Large-scale map-making." AAAI. 2004.

[47]. Thrun, Sebastian, and Michael Montemerlo. "The graph SLAM algorithm with applications to large-scale mapping of urban structures." The International Journal of Robotics Research 25.5-6 (2006): 403-429.

[48]. Pathak, Kaustubh, et al. "Online three‐dimensional SLAM by registration of large planar sur-face segments and closed‐form pose‐graph relaxation." Journal of Field Robotics 27.1 (2010): 52-84.

[49]. Sharf, Andrei, et al. "Snappaste: an interactive technique for easy mesh composition." The Visual Computer 22.9 (2006): 835-844.

[50]. Holz, Dirk, and Sven Behnke. "Sancta simplicitas-on the efficiency and achievable results of SLAM using ICP-based incremental registration." 2010 IEEE International Conference on Robot-ics and Automation. IEEE, 2010.

[51]. Geiger, Andreas, Julius Ziegler, and Christoph Stiller. "Stereoscan: Dense 3d reconstruction in real-time." 2011 IEEE intelligent vehicles symposium (IV). Ieee, 2011.

[52]. Dai, Jicheng, et al. "An Offline Coarse-To-Fine Precision Optimization Algorithm for 3D Laser SLAM Point Cloud." Remote Sensing 11.20 (2019): 2352.

[53]. Holder, Martin, Sven Hellwig, and Hermann Winner. "Real-time pose graph SLAM based on ra-dar." 2019 IEEE Intelligent Vehicles Symposium (IV). IEEE, 2019.

[54]. Cho, Hyunhak, Eun Kyeong Kim, and Sungshin Kim. "Indoor SLAM application using geometric and ICP matching methods based on line features." Robotics and Autonomous Systems 100 (2018): 206-224.

[55]. Mu, Beipeng, et al. "Slam with objects using a nonparametric pose graph." 2016 IEEE/RSJ Inter-national Conference on Intelligent Robots and Systems (IROS). IEEE, 2016.

[56]. Tomono, Masahiro. "Robust 3D SLAM with a stereo camera based on an edge-point ICP algo-rithm." 2009 IEEE International Conference on Robotics and Automation. IEEE, 2009.

Cite this article

Bai,H. (2023). ICP Algorithm: Theory, Practice and Its SLAM-oriented Taxonomy. Applied and Computational Engineering,2,451-462.

Data availability

The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.

Disclaimer/Publisher's Note

The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of EWA Publishing and/or the editor(s). EWA Publishing and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

About volume

Volume title: Proceedings of the 4th International Conference on Computing and Data Science (CONF-CDS 2022)

Conference website: https://www.confcds.org/

ISBN：978-1-915371-19-5(Print) / 978-1-915371-20-1(Online)

Conference date: 16 July 2022

Editor：Alan Wang

Series: Applied and Computational Engineering

Volume number: Vol.2

ISSN：2755-2721(Print) / 2755-273X(Online)

© 2024 by the author(s). Licensee EWA Publishing, Oxford, UK. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license. Authors who publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this series.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See Open access policy for details).