Maximum Spanning Tree for 3D Point Cloud Registration | SpringerLink
Skip to main content
Springer Nature Link
Log in

Maximum Spanning Tree for 3D Point Cloud Registration

  • Conference paper
  • First Online:
Pattern Recognition and Computer Vision (PRCV 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 15036))

Included in the following conference series:

  • 74 Accesses

Abstract

3D point cloud registration, as a fundamental and challenging problem in computational vision, aims to seek the best pose to align a point cloud between two 3D objects or scenes and transform them into the same coordinate system to achieve the best alignment of point clouds. The key to point cloud registration is accurately finding the corresponding relationship between point clouds. In this paper, we propose a pure geometric 3D point cloud registration method based on the maximum spanning tree (MST): 1) We extract the local features of the point clouds for initial alignment and construct the initial compatibility graph of two 3D objects or scenes. 2) We sparse the initial compatibility graph and find the maximum spanning tree in the sparse graph. 3) We select the maximum spanning tree with the most nodes and use the DFS algorithm to find all the node sets(each node set contains three nodes) in the selected maximum spanning tree. 4) We generate and evaluate the hypothesis of the node sets, and the hypothesis with the highest evaluation score is the transform matrix solved. We extensively tested our method on the 3DMatch, 3DLoMatch datasets. The experimental results show that the proposed MST method performs the same or better than the existing 3D point cloud registration methods.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 9380
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 11725
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Aoki, Y., Goforth, H., Srivatsan, R.A., Lucey, S.: Pointnetlk: robust & efficient point cloud registration using pointnet. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 7163–7172 (2019)

    Google Scholar 

  2. Bai, X., et al.: Pointdsc: robust point cloud registration using deep spatial consistency. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 15859–15869 (2021)

    Google Scholar 

  3. Bai, X., Luo, Z., Zhou, L., Fu, H., Quan, L., Tai, C.L.: D3feat: joint learning of dense detection and description of 3d local features. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 6359–6367 (2020)

    Google Scholar 

  4. Barath, D., Matas, J.: Graph-cut ransac. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 6733–6741 (2018)

    Google Scholar 

  5. Besl, P.J., McKay, N.D.: Method for registration of 3-d shapes. In: Sensor Fusion IV: Control Paradigms and Data Structures. vol. 1611, pp. 586–606. SPIE (1992)

    Google Scholar 

  6. Biber, P., Straßer, W.: The normal distributions transform: a new approach to laser scan matching. In: Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003) (Cat. No. 03CH37453), vol. 3, pp. 2743–2748. IEEE (2003)

    Google Scholar 

  7. Borrmann, A., König, M., Koch, C., Beetz, J.: Building Information Modeling: Why? What? How? Springer (2018)

    Google Scholar 

  8. Chen, H., Bhanu, B.: 3d free-form object recognition in range images using local surface patches. Pattern Recogn. Lett. 28(10), 1252–1262 (2007)

    Article  Google Scholar 

  9. Chen, H.H.: Weighted-svd: matrix factorization with weights on the latent factors (2017). arXiv:1710.00482

  10. Chen, X., Ma, H., Wan, J., Li, B., Xia, T.: Multi-view 3d object detection network for autonomous driving. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1907–1915 (2017)

    Google Scholar 

  11. Chen, Z., Sun, K., Yang, F., Tao, W.: Sc2-pcr: A second order spatial compatibility for efficient and robust point cloud registration. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 13221–13231 (2022)

    Google Scholar 

  12. Choy, C., Dong, W., Koltun, V.: Deep global registration. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2514–2523 (2020)

    Google Scholar 

  13. Choy, C., Park, J., Koltun, V.: Fully convolutional geometric features. In: Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 8958–8966 (2019)

    Google Scholar 

  14. Deng, H., Birdal, T., Ilic, S.: Ppfnet: global context aware local features for robust 3d point matching. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 195–205 (2018)

    Google Scholar 

  15. Fischler, M.A., Bolles, R.C.: Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 24(6), 381–395 (1981)

    Article  MathSciNet  Google Scholar 

  16. Geiger, A., Lenz, P., Urtasun, R.: Are we ready for autonomous driving? The kitti vision benchmark suite. In: 2012 IEEE Conference on Computer Vision and Pattern Recognition, pp. 3354–3361. IEEE (2012)

    Google Scholar 

  17. Geiger, A., Ziegler, J., Stiller, C.: Stereoscan: dense 3d reconstruction in real-time. In: 2011 IEEE Intelligent Vehicles Symposium (IV), pp. 963–968. IEEE (2011)

    Google Scholar 

  18. Greenberg, H.J.: Greedy Algorithms for Minimum Spanning Tree. University of Colorado at Denver (1998)

    Google Scholar 

  19. Guo, Y., Sohel, F., Bennamoun, M., Lu, M., Wan, J.: Rotational projection statistics for 3d local surface description and object recognition. Int. J. Comput. Vision 105, 63–86 (2013)

    Article  MathSciNet  Google Scholar 

  20. Holz, D., Ichim, A.E., Tombari, F., Rusu, R.B., Behnke, S.: Registration with the point cloud library: a modular framework for aligning in 3-d. IEEE Robot. Autom. Mag. 22(4), 110–124 (2015)

    Article  Google Scholar 

  21. Huang, S., Gojcic, Z., Usvyatsov, M., Wieser, A., Schindler, K.: Predator: Registration of 3d point clouds with low overlap. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 4267–4276 (2021)

    Google Scholar 

  22. Huang, X., Mei, G., Zhang, J., Abbas, R.: A comprehensive survey on point cloud registration (2021). arXiv:2103.02690

  23. Jiang, H., Dang, Z., Wei, Z., Xie, J., Yang, J., Salzmann, M.: Robust outlier rejection for 3d registration with variational bayes. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1148–1157 (2023)

    Google Scholar 

  24. Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7(1), 48–50 (1956)

    Article  MathSciNet  Google Scholar 

  25. Lee, J., Kim, S., Cho, M., Park, J.: Deep hough voting for robust global registration. In: Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 15994–16003 (2021)

    Google Scholar 

  26. Leordeanu, M., Hebert, M.: A spectral technique for correspondence problems using pairwise constraints. In: Tenth IEEE International Conference on Computer Vision (ICCV’05) Volume 1, vol. 2, pp. 1482–1489. IEEE (2005)

    Google Scholar 

  27. Maeder, U., Morari, M.: Attitude estimation for vehicles with partial inertial measurement. IEEE Trans. Veh. Technol. 60(4), 1496–1504 (2011)

    Article  Google Scholar 

  28. Pais, G.D., Ramalingam, S., Govindu, V.M., Nascimento, J.C., Chellappa, R., Miraldo, P.: 3dregnet: a deep neural network for 3d point registration. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 7193–7203 (2020)

    Google Scholar 

  29. Pomerleau, F., Liu, M., Colas, F., Siegwart, R.: Challenging data sets for point cloud registration algorithms. Int. J. Robot. Res. 31(14), 1705–1711 (2012)

    Article  Google Scholar 

  30. Qin, Z., Yu, H., Wang, C., Guo, Y., Peng, Y., Xu, K.: Geometric transformer for fast and robust point cloud registration. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11143–11152 (2022)

    Google Scholar 

  31. Quan, S., Yang, J.: Compatibility-guided sampling consensus for 3-d point cloud registration. IEEE Trans. Geosci. Remote Sens. 58(10), 7380–7392 (2020)

    Article  Google Scholar 

  32. Rusinkiewicz, S., Levoy, M.: Efficient variants of the icp algorithm. In: Proceedings Third International Conference on 3-D Digital Imaging and Modeling, pp. 145–152. IEEE (2001)

    Google Scholar 

  33. Rusu, R.B., Blodow, N., Beetz, M.: Fast point feature histograms (fpfh) for 3d registration. In: 2009 IEEE International Conference on Robotics and Automation, pp. 3212–3217. IEEE (2009)

    Google Scholar 

  34. Salti, S., Tombari, F., Di Stefano, L.: Shot: unique signatures of histograms for surface and texture description. Comput. Vis. Image Underst. 125, 251–264 (2014)

    Article  Google Scholar 

  35. Schnabel, R., Wahl, R., Klein, R.: Efficient ransac for point-cloud shape detection. In: Computer Graphics Forum, vol. 26, pp. 214–226. Wiley Online Library (2007)

    Google Scholar 

  36. Yang, H., Shi, J., Carlone, L.: Teaser: fast and certifiable point cloud registration. IEEE Trans. Rob. 37(2), 314–333 (2020)

    Article  Google Scholar 

  37. Yang, J., Huang, Z., Quan, S., Qi, Z., Zhang, Y.: Sac-cot: sample consensus by sampling compatibility triangles in graphs for 3-d point cloud registration. IEEE Trans. Geosci. Remote Sens. 60, 1–15 (2021)

    Google Scholar 

  38. Yurtsever, E., Lambert, J., Carballo, A., Takeda, K.: A survey of autonomous driving: common practices and emerging technologies. IEEE Access 8, 58443–58469 (2020)

    Article  Google Scholar 

  39. Zeng, A., Song, S., Nießner, M., Fisher, M., Xiao, J., Funkhouser, T.: 3dmatch: Learning local geometric descriptors from rgb-d reconstructions. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1802–1811 (2017)

    Google Scholar 

  40. Zhang, X., Yang, J., Zhang, S., Zhang, Y.: 3d registration with maximal cliques. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 17745–17754 (2023)

    Google Scholar 

  41. Zhou, Q.Y., Park, J., Koltun, V.: Fast global registration. In: Computer Vision–ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, 11–14 Oct 2016, Proceedings, Part II 14, pp. 766–782. Springer (2016)

    Google Scholar 

Download references

Acknowledgements

We would like to thank the anonymous reviewers for their helpful suggestions. This work was supported by the National Natural Science Foundation of China (Grant No. 62106227), the China Postdoctoral Science Foundation (Grant No. 2023M743132), and the “Teacher Professional Development Project” for Domestic Visiting Scholars in 2023 (Project No. FX2023007).

Author information

Authors and Affiliations

  1. School of Computer Science and Technology, Zhejiang Normal University, 688 Yingbin Road, Jinhua, 321004, Zhejiang Province, China

    Xin Zhao, Chengzhuan Yang & Zhonglong Zheng

Authors
  1. Xin Zhao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chengzhuan Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zhonglong Zheng
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Chengzhuan Yang .

Editor information

Editors and Affiliations

  1. Peking University, Beijing, China

    Zhouchen Lin

  2. Nankai University, Tianjin, China

    Ming-Ming Cheng

  3. Chinese Academy of Sciences, Beijing, China

    Ran He

  4. Xinjiang University, Ürümqi, Xinjiang, China

    Kurban Ubul

  5. Xinjiang University, Ürümqi, China

    Wushouer Silamu

  6. Peking University, Beijing, China

    Hongbin Zha

  7. Tsinghua University, Beijing, China

    Jie Zhou

  8. Chinese Academy of Sciences, Beijing, China

    Cheng-Lin Liu

1 Electronic supplementary material

Below is the link to the electronic supplementary material.

Supplementary material 1 (pdf 1399 KB)

Rights and permissions

Reprints and permissions

Copyright information

© 2025 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Zhao, X., Yang, C., Zheng, Z. (2025). Maximum Spanning Tree for 3D Point Cloud Registration. In: Lin, Z., et al. Pattern Recognition and Computer Vision. PRCV 2024. Lecture Notes in Computer Science, vol 15036. Springer, Singapore. https://doi.org/10.1007/978-981-97-8508-7_18

Download citation

  • DOI: https://doi.org/10.1007/978-981-97-8508-7_18

  • Published:

  • Publisher Name: Springer, Singapore

  • Print ISBN: 978-981-97-8507-0

  • Online ISBN: 978-981-97-8508-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation