基于K-means++的多视图点云配准技术

计算机与现代化 ›› 2022, Vol. 0 ›› Issue (02): 97-101.

基于K-means++的多视图点云配准技术

(1.广西大学计算机与电子信息学院，广西南宁530004；2.广西多媒体通信与网络技术重点实验室，广西南宁530004)

出版日期:2022-03-31 发布日期:2022-03-31
作者简介:梁正友(1968—),男,广西天等人,教授,博士,研究方向:计算机视觉,无线传感器网络,并行分布式计算,人工智能，E-mail： zhyliang@gxu.edu.cn; 王璐(1996—),女,福建福州人,硕士研究生,研究方向:计算机视觉,图像处理,机器学习,E-mail： 709243264@qq.com；李轩昂(1993—),男,广西玉林人,硕士研究生,研究方向:计算机视觉,图像处理,机器学习,E-mail： 931476138@qq.com；杨锋(1979—),男,广西玉林人,副教授,博士,研究方向:人工智能,网络信息安全,大数据与高性能计算,精准医学,E-mail： yf@gxu.edu.cn。
基金资助:
国家自然科学基金资助项目（61861004）

Multi-view Point Cloud Registration Technology Based on K-means++

(1. School of Computer and Electronic Information, Guangxi University, Nanning 530004, China;
2. Guangxi Key Laboratory of Multimedia Communications and Network Technology, Nanning 530004, China)

Online:2022-03-31 Published:2022-03-31

摘要/Abstract

摘要： 针对大规模点集可能存在噪声、离群点及遮挡等情况，提出一种基于K-means+〖KG-*3〗+的多视图点云配准方法。首先，利用K-means+〖KG-*3〗+算法的随机播种技术对下采样后的多视图点集选取初始化的质心，并根据算法的基本原理完成聚类；其次，将点云数据存入K-D树结构，并利用最近邻搜索算法建立点集间的对应关系，从而提升对应点集的搜索效率；最后，通过迭代最近点算法依照扫描顺序计算各视图聚类得到的点云数据与所有视图间的刚性变换参数，将成对配准造成的误差均匀扩散到每个视图中，直至获得最终配准结果。在Stanford三维点云数据集上进行实验的结果表明，本文提出的方法比近年的部分多视图配准算法具有更高的配准精度及鲁棒性。

关键词: 点云配准, 多视图配准, K-means++算法, 迭代最近点算法, 刚性配准

Abstract: A multi-view point cloud registration method based on K-means+〖KG-*3〗+ is proposed for the possibility of noise, outliers and occlusion in large scale point sets. Firstly, the random seeding technique of K-means+〖KG-*3〗+ algorithm is used to select the initialized center of mass from the subsampled multi-view point sets, and the clustering is completed according to the basic principle of the algorithm. Secondly, the point cloud data are stored in the K-D tree structure, and the nearest neighbor search algorithm is used to establish the corresponding relationship between the point sets, so as to improve the search efficiency of the corresponding point sets. Finally, the rigid transformation parameters between the point cloud data obtained by the clustering of each view and all views are calculated according to the scanning sequence by the iterative closest point algorithm, and the errors caused by pairwise registration are evenly spread to each view until the final registration result is obtained. Experiments on Stanford 3D point cloud datasets show that the proposed method has higher registration accuracy and robustness than partial multi-view registration algorithms in recent years.

Key words: point cloud registration, multi-view registration, K-means+〖KG-*3〗+ algorithm, iterative closest point algorithm, rigid registration

梁正友, 王璐, 李轩昂, 杨锋, . 基于K-means++的多视图点云配准技术[J]. 计算机与现代化, 2022, 0(02): 97-101.

参考文献

［1］ PAN Y Q, ZHENG R, LIU F B, et al. The use of CT scan and stereo lithography apparatus technologies in a canine individualized rib prosthesis［J］. International Journal of Surgery, 2014,12(1):71-75.
［2］赵夫群,周明全. 文物点云模型的优化配准算法［J］. 计算机应用研究, 2017,34(12):3885-3888.
［3］ YAN L, TAN J X, LIU H, et al. Automatic registration of TLS-TLS and TLS-MLS point clouds using a genetic algorithm［J］. Sensors, 2017,17(9):1979. DOI:10.3390/s17091979.
［4］侯彬,金尚忠,王赟,等. 点云配准方法在粗配准中的比较［J］. 激光与光电子学进展, 2020,57(8):286-293.
［5］ PULLI K. Multiview registration for large data sets［C］// Proceedings of the 2nd International Conference on 3-D Digital Imaging and Modeling. 1999:160-168.
［6］ BESL P J, MCKAY N D. Method for registration of 3-D shapes［C］// Sensor Fusion IV: Control Paradigms and Data Structures. 1992,1611:586-606.
［7］艾达,倪国斌,王苗,等. 基于Kinect的三维重建技术综述［J］. 传感器与微系统, 2017,36(8):1-6.
［8］ CHETVERIKOV D, STEPANOV D, KRSEK P. Robust Euclidean alignment of 3D point sets: The trimmed iterative closest point algorithm［J］. Image and Vision Computing, 2005,23(3):299-309.
［9］ LI S H, WANG J X, LIANG Z Q, et al. Tree point clouds registration using an improved ICP algorithm based on kd-tree［C］// 2016 IEEE International Geoscience and Remote Sensing Symposium (IGARSS). 2016:4545-4548.
［10］CASTELLANI U, BARTOLI A. 3D shape registration［M］// 3D Imaging, Analysis and Applications. Springer, Cham, 2020:221-264.
［11］CASTELLANI U, FUSIELLO A, MURINO V. Registration of multiple acoustic range views for underwater scene reconstruction［J］. Computer Vision and Image Understanding, 2002,87(1-3):78-89.
［12］BROWN L G. A survey of image registration techniques［J］. ACM Computing Surveys, 1992,24(4):325-376.
［13］CHANG W C, PHAM V T. 3-D point cloud registration using convolutional neural networks［J］. Applied Sciences, 2019,9(16):3273.
［14］KUROBE A, SEKIKAWA Y, ISHIKAWA K, et al. CorsNet: 3D point cloud registration by deep neural network［J］. IEEE Robotics and Automation Letters, 2020,5(3):3960-3966.
［15］TEKLEHAYMANOT F K, MUMA M, ZOUBIR A M. Bayesian cluster enumeration criterion for unsupervised learning［J］. IEEE Transactions on Signal Processing, 2018,66(20):5392-5406.
［16］ZHOU H, LIU Y H. Accurate integration of multi-view range images using k-means clustering［J］. Pattern Recognition, 2008,41(1):152-175.
［17］EVANGELIDIS G D, HORAUD R. Joint alignment of multiple point sets with batch and incremental expectation-maximization［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2017,40(6):1397-1410.
［18］JI S, XU D C, GUO L K, et al. The seeding algorithm for spherical k-means clustering with penalties［J］. Journal of Combinatorial Optimization, 2020(2):1-18.
［19］ZHU J H, LI Z Y, DU S Y, et al. Surface reconstruction via efficient and accurate registration of multiview range scans［J］. Optical Engineering, 2014,53(10):102104.
［20］GUPTA A, TRIPATHY B K. Implementing GloVe for context based k-means+〖KG-*3〗+ clustering［C］// 2017 International Conference on Intelligent Sustainable Systems (ICISS). 2017:1041-1046.
［21］ARTHUR D, VASSILVITSKII S. K-Means+〖KG-*3〗+: The advantages of careful seeding［C］// Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. 2007:1027-1035.
［22］LEE J M. Fast k-nearest neighbor searching in static objects［J］. Wireless Personal Communications, 2017,93(1):147-160.
［23］ZIGIC M, GRAHOVAC N. Numerical algorithm for rigid body position estimation using the quaternion approach［J］. Acta Mechanica Sinica, 2018,4(2):400-408.
［24］ZHU J H, JIANG Z T, EVANGELIDIS G D, et al. Efficient registration of multi-view point sets by K-means clustering［J］. Information Sciences, 2019,488:205-218.
［25］ZHU J H, ZHU L, LI Z Y, et al. Automatic multi-view registration of unordered range scans without feature extraction［J］. Neurocomputing, 2016,171:1444-1453.

[1]	李家乐1, 李哲润1, 赵勇2, 张杨1. 基于3D-SIFT与4PCS融合的大数据量点云快速配准方法[J]. 计算机与现代化, 2024, 0(02): 1-6.
[2]	张亚文, 林文忠, 韩晓东. 基于组合特征点和主成分分析的点云配准算法[J]. 计算机与现代化, 2023, 0(09): 59-63.
[3]	梁正友, 王璐, 李轩昂, 杨锋, . 基于改进PSO-TrICP算法的点云配准[J]. 计算机与现代化, 2022, 0(05): 90-95.
[4]	李运川, 王晓红, 陈思吉, 葛义攀, 李闯. 基于多核并行和动态阈值的点云配准算法[J]. 计算机与现代化, 2020, 0(09): 77-82.
[5]	李宇萌，段欣伯，马蓬勃. 基于点云的转子表面缺陷检测方法[J]. 计算机与现代化, 2019, 0(10): 101-.
[6]	赵夫群,方荣. 迭代最近点算法的改进策略[J]. 计算机与现代化, 2019, 0(01): 17-.
[7]	王伟. 非刚性三维点云配准方法[J]. 计算机与现代化, 2018, 0(12): 116-.
[8]	马大贺，刘国柱. 改进的基于FPFH特征配准点云的方法[J]. 计算机与现代化, 2017, 0(11): 46-50.