Skip to main content
SpringerLink
Log in

An improved iterative closest point algorithm based on the particle filter and K-means clustering for fine model matching

  • Original article
  • Published:
The Visual Computer Aims and scope Submit manuscript

Abstract

The rigid matching of two geometric clouds is vital in the computer vision and its intelligent applications, such as computational geometry, robotics, shape modelling, surface reconstruction and mapping, and many other fields. The variants of the iterative closest point algorithm were employed as the most noticeable matching algorithm. In traditional ICP algorithms applications for symmetrical geometry matching, the initial uncertainty and the multiple local minima of the distance function adversely affect the alignment process, which leads to weak performance, such as incorrect correspondence, narrow convergence region, and instability. In this study, the novel algorithm fused the ICP algorithm, particle filter and K-means clustering to correctly estimate the transformation ICP parameters. Further guide to initial values of parameters and their covariance obtained by k-means clustering. Then, a particle filter was implemented to estimate accurate values and perform global optimization. In the introduced PF-ICP algorithm, the alignment parameters: rotation angles, scale factor, and translation, were defined as particles elements optimized using a sequential importance resampling (SIR) particle filter. The proposed algorithm was implemented on a medical robot FPGA board and applied to “three symmetrical models” and “noisy and poor datasets.” The calculated variances and estimated parameters were compared with four modified ICP methods. The results show a significantly increasing accuracy and convergence region with an acceptable speed for the practical conditions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Algorithm 1:
Algorithm 2:
Fig. 3
Algorithm 3:
Algorithm 4:
Algorithm 5:
Fig. 4
Fig. 5
Algorithm 6:
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19

Similar content being viewed by others

Data availability

The data that support the findings of this study are available from the corresponding author upon request. Mail to: research552@gmail.com, momeni_h@modares.ac.ir, ahmadreza_saleh@modres.ac.ir.

References:

  1. Besl, P.J., McKay, N.D.: Method for registration of 3-D shapes. In: Sensor fusion IV: control paradigms and data structures, vol. 1611. Spie (1992)

  2. Kamgar-Parsi, B., Kamgar-Parsi, B.: Vehicle localization on gravity maps. In: Unmanned Ground Vehicle Technology. International Society for Optics and Photonics, vol. 3693 (1999)

  3. Turk, G., Levoy, M.: Zippered polygon meshes from range images. In: Proceedings of the SIGGRAPH (1994)

  4. Masuda, T., Sakaue, K., Yokoya, N.: Registration and Integration of Multiple Range Images for 3-D Model Construction. In: Proceedings of 13th international conference on pattern recognition (CVPR) (1996)

  5. Xiao, J., Duan, X., Qi, X.: An adaptive △M-ICCP geomagnetic matching algorithm. J. Navig. 71, 649–663 (2018). https://doi.org/10.1017/S0373463317000844

    Article  Google Scholar 

  6. Zhao, J., Sun, X., Li, M., Zhang, Y.: Random error modeling and compensation of geomagnetic map data. In: 2021 IEEE International Conference on Power Electronics, Computer Applications (ICPECA), pp. 70–73 (2021). https://doi.org/10.1109/ICPECA51329.2021.9362557.

  7. Meng, Y., Zhang, H.: Registration of point clouds using sample-sphere and adaptive distance restriction. Vis. Comput. 27, 543–553 (2011). https://doi.org/10.1007/s00371-011-0580-0

    Article  Google Scholar 

  8. Nuchter, A., Lingemann, K., Hertzberg, J.:Cached kd tree search for ICP algorithms. In: Sixth International Conference on 3-D Digital Imaging and Modeling (3DIM 2007). IEEE (2007)

  9. Bouaziz, S., Tagliasacchi, A., Pauly, M.: Sparse iterative closest point. In: Proceedings of the Eleventh Eurographics/ACMSIGGRAPH Symposium on Geometry Processing (SGP'13). Eurographics Association, Goslar, DEU, pp. 113–123 (2013). https://doi.org/10.1111/cgf.12178

  10. Guo, Y., Zhao, L., Shi, Y., Zhang, X., Du, S., Wang, F.: Adaptive weighted robust iterative closest point. Neurocomputing 508, 225–241 (2022). https://doi.org/10.1016/j.neucom.2022.08.047

    Article  Google Scholar 

  11. Ketty, F., Muriel, P., Eric, M., Luce, M.: Plane-based Accurate Registration of Real-world Point Clouds. In: 2021 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pp. 2018–2023 (2021).

  12. Dong, J., Peng, Y., Ying, S., Hu, Z.: LieTrICP: an improvement of trimmed iterative closest point algorithm. Neurocomputing 140, 67–76 (2014)

    Article  Google Scholar 

  13. Wang, X., Li, Y., Peng, Y., Ying, S.: A coarse-to-fine generalized-ICP algorithm with trimmed strategy. IEEE Access 8, 40692–40703 (2020). https://doi.org/10.1109/ACCESS.2020.2976132

    Article  Google Scholar 

  14. Li, J., Hu, Q., Zhang, Y., Ai, M.: Robust symmetric iterative closest point. ISPRS J. Photogramm. Remote Sens. 185, 219–231 (2022). https://doi.org/10.1016/j.isprsjprs.2022.01.019

    Article  Google Scholar 

  15. Ireta Muñoz, F.I., Comport, A.I.: Point-to-hyperplane ICP: fusing different metric measurements for pose estimation. Adv. Robot. 32(4), 161–175 (2018)

    Article  Google Scholar 

  16. Combès, B., Prima, S.: An efficient EM-ICP algorithm for non-linear registration of large 3D point sets. Comput. Vis. Image Underst. 191, 102854 (2020). https://doi.org/10.1016/j.cviu.2019.102854

    Article  Google Scholar 

  17. Walker, H.F., Ni, P.: Anderson acceleration for fixed-point iterations. SIAM J. Numer. Anal. 49, 1715–1735 (2011). https://doi.org/10.1137/10078356X

    Article  MathSciNet  Google Scholar 

  18. Zhang, J., Yao, Y., Deng, B.: Fast and robust iterative closest point. IEEE Trans. Pattern Anal. Mach. Intell. 44, 3450–3466 (2022). https://doi.org/10.1109/TPAMI.2021.3054619

    Article  Google Scholar 

  19. Yue, X., et al.: Coarse-fine point cloud registration based on local point-pair features and the iterative closest point algorithm. Appl. Intell. 52(11), 12569–12583 (2022)

    Article  MathSciNet  Google Scholar 

  20. Li, M., Zhang, M., Niu, D., et al.: Point set registration based on feature point constraints. Vis. Comput. 36, 1725–1738 (2020). https://doi.org/10.1007/s00371-019-01771

    Article  Google Scholar 

  21. Basdogan, C., Oztireli, A.: A new feature-based method for robust and efficient rigid-body registration of overlapping point clouds. Vis. Comput. 24, 679–688 (2008). https://doi.org/10.1007/s00371-008-0248-6

    Article  Google Scholar 

  22. André, M., Lionel, L.: On-manifold probabilistic Iterative Closest Point: application to underwater karst exploration. Int. J. Robot. Res. 41, 875–902 (2022). https://doi.org/10.1177/02783649221101418

    Article  Google Scholar 

  23. Xiao, J., Duan, X., Qi, X., Liu, Y.: An improved ICCP matching algorithm for use in an interference environment during geomagnetic navigation. J. Navig. 73, 56–74 (2020). https://doi.org/10.1017/S0373463319000535

    Article  Google Scholar 

  24. R¨owek¨amper, J., Sprunk, C., Tipaldi, G.D., Stachniss, C., Pfaff, P., Burgard, W.: On the position accuracy of mobile robot localization based on particle filters combined with scan matching. In: International Conference on Intelligent Robots and Systems, pp. 3158–3164 (2012). https://doi.org/10.1109/IROS.2012.6385988

  25. Censi, A.: An accurate closed-form estimate of ICP’s covariance. In: Proceedings 2007 IEEE International Conference on Robotics and Automation (ICRA), pp. 3167–3172 (2007). https://doi.org/10.1109/ROBOT.2007.363961

  26. Maken, F., Ramos, F., Ott, L.: Stein ICP for uncertainty estimation in point cloud matching. IEEE Robot. Autom. 7, 1063–1070 (2021). https://doi.org/10.1109/LRA.2021.3137503

    Article  Google Scholar 

  27. Hu, L., Xiao, J., Wang, Y.: An automatic 3D registration method for rock mass point clouds based on plane detection and polygon matching. Vis. Comput. 36, 669–681 (2020). https://doi.org/10.1007/s00371-019-01648-z

    Article  MathSciNet  Google Scholar 

  28. Ameer, M., Abbas, M., Miura, K.T., Majeed, A., Nazir, T.: Curve and surface geometric modeling via generalized Bézier-like model. Mathematics 10(7), 1045 (2022). https://doi.org/10.3390/math10071045

    Article  Google Scholar 

  29. Song, Y., Shen, W., Peng, K.: A novel partial point cloud registration method based on graph attention network. Vis. Comput. 39, 1109–1120 (2023). https://doi.org/10.1007/s00371-021-02391-0

    Article  Google Scholar 

  30. Majeed, A., Abbas, M., Miura, K.T., Kamran, M., Nazir, T.: Surface modeling from 2D contours with an application to craniofacial fracture construction. Mathematics 8(8), 1246 (2020). https://doi.org/10.3390/math8081246

    Article  Google Scholar 

  31. Nguyen, M., Yuan, X., Chen, B.: Geometry completion and detail generation by texture synthesis. Vis. Comput. 21, 669–678 (2005). https://doi.org/10.1007/s00371-005-0315-1

    Article  Google Scholar 

  32. Eggert, D., Lorusso, A., Fisher, R.: Estimating 3-D rigid body transformations: a comparison of four major algorithms. Mach. Vis. Appl. 9, 272–290 (1997). https://doi.org/10.1007/s001380050048

    Article  Google Scholar 

  33. Oomori, S., Nishida, T., Kurogi, S.: Point cloud matching using singular value decomposition. Artif. Life Robot. 21, 149–154 (2016). https://doi.org/10.1007/s10015-016-0265-x

    Article  Google Scholar 

  34. Saleem, W., Schall, O., Patanè, G., et al.: On stochastic methods for surface reconstruction. Vis. Comput. 23, 381–395 (2007). https://doi.org/10.1007/s00371-006-0094-3

    Article  Google Scholar 

  35. Prakhya, S.M., Bingbing, L., Rui, Y., Lin, W.: A closed-form estimate of 3D ICP covariance. In: 14th IAPR International Conference on Machine Vision Applications (MVA), pp. 526–529 (2015). https://doi.org/10.1109/MVA.2015.7153246

  36. Maken, F.A., Ramos, F. and Ott, L.: Estimating motion uncertainty with bayesian icp. In 2020 IEEE International Conference on Robotics and Automation (ICRA), 8602–8608 (2020).

  37. Barrie Wetherill, G., Duncombe, P., Kenward, M., Köllerström, J., Paul, S.R., Vowden, B.J.: Regression Analysis with Applications. Chapman & Hall, London (1986)

    Book  Google Scholar 

  38. Segal, A., Haehnel, D., Thrun, S.: Generalized-icp. In: Robotics: science and systems, vol. 2, no. 4, p. 435 (2009)

  39. Gustafsson, F.: Particle filter theory and practice with positioning applications. IEEE Aerosp. Electron. Syst. Mag. 25, 53–82 (2010). https://doi.org/10.1109/MAES.2010.5546308

    Article  Google Scholar 

  40. Ying, W., Sun, Sh.: An improved Monte Carlo localization using optimized iterative closest point for mobile robots. Cognitive Comput. Syst. 4(1), 20–30 (2022)

    Article  Google Scholar 

  41. Speekenbrink, M.: A tutorial on particle filters. J. Math. Psychol. 73, 140–152 (2016). https://doi.org/10.1016/j.jmp.2016.05.006

    Article  MathSciNet  Google Scholar 

  42. Liu, J.S., Chen, R., Logvinenko, T.: A theoretical framework for sequential importance sampling with resampling. In: Sequential Monte Carlo methods in practice, pp. 225–246. Springer, New York (2001).

  43. Bengtsson, O., Baerveldt, A.J.: Robot localization based on scan matching - estimating the covariance matrix for the IDC algorithm. Robot. Auton. Syst. 44, 29–40 (2003). https://doi.org/10.1016/S0921-8890(03)00008-3

    Article  Google Scholar 

  44. Bergström, P., Edlund, O.: Robust registration of surfaces using a refined iterative closest point algorithm with a trust region approach. Numer. Algor. 74, 755–779 (2017). https://doi.org/10.1007/s11075-016-0170-3

    Article  MathSciNet  Google Scholar 

  45. Bergström, P.: Reliable updates of the transformation in the iterative closest point algorithm. Comput. Optim. Appl. 63, 543–557 (2016). https://doi.org/10.1007/s10589-015-9771-3

    Article  MathSciNet  Google Scholar 

  46. Fox, D., Burgard, W., Dellaert, F., Thrun, S.: Monte Carlo localization: efficient position estimation for mobile robots. In: Proceedings of the National Conference on Artificial Intelligence, pp. 343–349 (1999)

Download references

Funding

The authors did not receive support from any organization for the submitted work. The authors declare that no funds, grants, or other support were received during the preparation of this manuscript.

Author information

Authors and Affiliations

  1. Faculty of Electrical and Computer Engineering, Tarbiat Modares University, Jalal Ale Ahmad, P. O. Box: 14115-111, Tehran, Iran

    Ahmad Reza Saleh & Hamid Reza Momeni

Authors
  1. Ahmad Reza Saleh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hamid Reza Momeni
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

All authors contributed to the study conception and design. Material preparation, data collection, and analysis were performed by ARS and HRM. The first draft of the manuscript was written by ARS, and all authors commented on previous versions of the manuscript. All authors read and approved the final manuscript.

Corresponding author

Correspondence to Hamid Reza Momeni.

Ethics declarations

Conflict of interest

The authors whose names are listed immediately below of the title of manuscript certify that they have no relevant financial or non-financial interests to disclose. They have no affiliations with or involvement in any organization or entity with any financial interest (such as honoraria; educational grants; participation in speakers’ bureaus; membership, employment, consultancies, stock ownership, or other equity interest; and expert testimony or patent-licensing arrangements) or non-financial interest (such as personal or professional relationships, affiliations, knowledge, or beliefs) in the subject matter or materials discussed in this manuscript.

Ethics approval

The authors affirm that this manuscript does not involve human or animal research subject.

Consent to participate

Informed consent was obtained from all individual participants included in the study.

Consent to publish

The authors affirm that this manuscript has not human research participants to provide informed consent for publication.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Saleh, A.R., Momeni, H.R. An improved iterative closest point algorithm based on the particle filter and K-means clustering for fine model matching. Vis Comput (2024). https://doi.org/10.1007/s00371-023-03195-0

Download citation

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00371-023-03195-0

Keywords

Search

Navigation