基于区间分割和兼容加权的点云配准算法

Point cloud registration algorithm based on interval segmentation and compatibility weighting

摘要

针对重叠区域小、共享的特征点较少的点云存在配准精度不高的问题，提出一种基于区间分割和兼容加权的点云配准算法。该算法利用距离分割将点云划分为多个子区间，并通过构建子区间的特征描述符求取其直方图相似度，从而确定子区间的对应关系。引入可信性和一致性约束，求解刚体变换组合系数，从局部配准得到全局配准，从而实现点云粗配准。最后基于尺度不变相容约束进行双点采样，并计算对应点对的兼容性权重矩阵，对其进行投票后排序，求得共识最大化的刚体变换，完成点云精配准。实验采用斯坦福点云数据模型、3DMatch室内场景数据模型以及农田点云数据模型进行验证，结果表明，对比6种配准算法，所提算法具有最高的配准精度和最低的配准耗时。在斯坦福点云数据的配准中，所提算法在平均精度上均提高了10%以上，平均耗时均降低了14%以上；在室内场景的点云配准中，所提算法在平均精度上均提高了20%以上，平均耗时均降低了14%以上；在农田点云数据配准中，所提算法在平均精度上均提高了21%以上，平均耗时均降低了16%以上，因此可以说该基于区间分割和兼容加权的点云配准算法是一种高效的点云配准算法。

Abstract

Aiming at the problem of low registration accuracy of point clouds with small overlapping areas and few shared feature points, a point cloud registration algorithm based on interval segmentation and compatible weighting is proposed. In this algorithm, the point cloud is divided into several sub-intervals by distance segmentation, and the histogram similarity is obtained by constructing the feature descriptors of the sub-intervals, so as to determine the corresponding relationship of the sub-intervals. By introducing credibility and consistency constraints, the combination coefficients of rigid body transformation are solved, and the global registration is obtained from local registration, thereby achieving the coarse registration of point cloud. Finally, two-point sampling is carried out based on the scale invariant compatibility constraint, the compatibility weight matrix of corresponding point pairs is calculated, the rigid body transformation with maximum consensus is obtained after voting, and the fine registration of point cloud is completed. Stanford point cloud data model, 3DMatch indoor scene data model and the farmland point cloud data model are used to verify the experiment. The results show that compared with the six registration algorithms, the proposed algorithm has the highest registration accuracy and the lowest registration time consumption. In the registration of Stanford point cloud data, the average accuracy of the proposed algorithm is improved by more than 10%, and the average time consumption is reduced by more than 14%. In the point cloud registration of indoor scenes, the average accuracy of the proposed algorithm is improved by more than 20%, and the average time consumption is reduced by more than 14%. In the registration of farmland point cloud data, the proposed algorithm has increased the average accuracy by more than 21% and reduced the average time consumption by more than 16%. Therefore, it can be said that the point cloud registration algorithm based on interval segmentation and compatible weighting is an efficient point cloud registration algorithm.

关键词

点云配准 / 区间分割 / 组合系数 / 兼容性权重矩阵 / 共识最大化

Key words

point cloud registration / interval segmentation / combination coefficient / compatibility weight matrix / consensus maximization

参考文献

[1] GUO Y L, WANG H Y, HU Q Y, et al. Deep learning for 3D point clouds: A survey[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021, 43(12): 4338-4364.

[2] XU N L, QIN R J, SONG S. Point cloud registration for LiDAR and photogrammetric data: A critical synthesis and performance analysis on classic and deep learning algorithms[J]. ISPRS Open Journal of Photogrammetry and Remote Sensing, 2023, 8: 100032.

[3] MONJI—AZAD S, HESSER J, LÖW N. A review of non—rigid transformations and learning—based 3D point cloud registration methods[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2023, 196: 58-72.

[4] 缪永伟, 刘家宗, 孙瑜亮, 等. 基于类别—实例分割的室内点云场景修复补全[J]. 计算机学报, 2021, 44(11): 2189-2202.

[5] MIAO Y W, LIU J Z, SUN Y L, et al. Point cloud completion of indoor scenes based on category—instance segmentation[J]. Chinese Journal of Computers, 2021, 44(11): 2189-2202.

[6] 王奇, 钱伟中, 雷航, 等. 基于关键特征增强机制的3D人脸识别[J]. 电子科技大学学报, 2024, 53(2): 252-258.

[7] WANG Q, QIAN W Z, LEI H, et al. 3D face recognition based on key feature enhancement mechanism[J]. Chinese Journal of University of Electronic Science and Technology of China, 2024, 53(2): 252-258.

[8] YU H, HOU J, QIN Z, et al. RIGA: Rotation—invariant and globally—aware descriptors for point cloud registration[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024, 46(5): 3796-3812.

[9] LIU W B, SUN W, WANG S X, et al. Coarse registration of point clouds with low overlap rate on feature regions[J]. Signal Processing: Image Communication, 2021, 98: 116428.

[10] XU J B, HUANG Y K, WAN Z Y, et al. GLORN: Strong generalization fully convolutional network for low—overlap point cloud registration[J]. IEEE Transactions on Geoscience and Remote Sensing, 2022, 60: 5704814.

[11] WU Q Y, WANG J, ZHANG Y, et al. Accelerating point cloud registration with low overlap using graphs and sparse convolutions[J]. IEEE Transactions on Multimedia, 2023, 27: 744-753.

[12] YU J L, REN L W, ZHANG Y, et al. PEAL: Prior—embedded explicit attention learning for low—overlap point cloud registration[C]// Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. New York: IEEE, 2023: 17702-17711.

[13] WU S Q, TAO J L, WU C R, et al. Low—overlap point cloud registration algorithm based on coupled iteration[J]. The Visual Computer, 2024, 40(5): 3151-3162.

[14] WANG X C, YUAN Y. GCMTN: Low—overlap point cloud registration network combining dense graph convolution and multilevel interactive transformer[J]. Remote Sensing, 2023, 15(15): 3908.

[15] ZHANG W H, ZHANG Y, LI J L. A two—stage correspondence—free algorithm for partially overlapping point cloud registration[J]. Sensors, 2022, 22(13): 5023.

[16] GUO F, ZHENG W B, LIAN G F, et al. A point cloud registration method based on multiple—local—feature matching[J]. Optik, 2023, 295: 171511.

[17] CHE S Q, BAO C W, LU J F. A weighted local—spherical grid based lightweight descriptor for 3D point cloud registration[J]. The Journal of Engineering, 2023, 2023(9): e12304.

[18] ZHAO L D, XIANG Z F, CHEN M L, et al. Establishment and extension of a fast descriptor for point cloud registration[J]. Remote Sensing, 2022, 14(17): 4346.

[19] WANG W, ZHANG Y, GE G Y, et al. A new approach toward corner detection for use in point cloud registration[J]. Remote Sensing, 2023, 15(13): 3375.

[20] SUN R Y, ZHANG E Z, MU D Q, et al. Optimization of the 3D point cloud registration algorithm based on FPFH features[J]. Applied Sciences, 2023, 13(5): 3096.

[21] 赵宝, 王梓涵, 贾兆红, 等. 基于动态图卷积和PointNet的三维局部特征描述符[J]. 计算机辅助设计与图形学学报, 2025, 37(1): 89-99.

[22] ZHAO B, WANG Z H, JIA Z H, et al. Three—dimensional local feature descriptor based on dynamic graph convolution and PointNet[J]. Journal of Computer—Aided Design & Computer Graphics, 2025, 37(1): 89-99.

[23] WEN C W, HUANG S C. A LiDAR point cloud registration method combining linear feature extraction and TrICP algorithm[J]. Multimedia Systems, 2023, 29(6): 3209-3221.

[24] LIU L P, XIAO J, WANG Y B, et al. A novel rock—mass point cloud registration method based on feature line extraction and feature point matching[J]. IEEE Transactions on Geoscience and Remote Sensing, 2021, 60: 5701117.

[25] AIGER D, MITRA N J, COHEN—OR D. 4—points congruent sets for robust pairwise surface registration[C]// Proceedings of the ACM SIGGRAPH 2008. New York: ACM, 2008: 1-10.

[26] DA SILVA JUNIOR J P , BORGES D L , DE BARROS VIDAL F . A dynamic approach for approximate pairwise alignment based on 4—points congruence sets of 3D points[C]// Proceedings of the 18th IEEE International Conference on Image Processing. New York: IEEE, 2011: 889-892.

[27] LI S K, LU R D, LIU J Y, et al. Super edge 4—points congruent sets—based point cloud global registration[J]. Remote Sensing, 2021, 13(16): 3210.

[28] TAO W Y, LIU J B, XU D, et al. Automatic registration of point clouds by combining local shape descriptor and G4PCS algorithm[J]. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 2023, 16: 6339-6351.

[29] LIU H, WANG S L, ZHAO D H. Enhanced super4PCS algorithm by comparing transformed normals at corresponding points[J]. Computational Intelligence and Neuroscience, 2022(1): 6513776.

[30] XU Z W, WANG D. Research on point cloud registration algorithm based on boundary Harris—3D points and 4PCS[J]. Journal of Physics: Conference Series, 2022, 2258(1): 012002.

[31] JIANG S K, QI P, HAN L, et al. Navigation system for orchard spraying robot based on 3D LiDAR SLAM with NDT_ICP point cloud registration[J]. Computers and Electronics in Agriculture, 2024, 220: 108870.

[32] BESL P J, MCKAY N D. A method for registration of 3—D shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(2): 239-256.

[33] CHETVERIKOV D, SVIRKO D, STEPANOV D, et al. The trimmed iterative closest point algorithm[C]// Proceedings of the International Conference on Pattern Recognition. New York: IEEE, 2002: 545-548.

[34] BOUAZIZ S, TAGLIASACCHI A, PAULY M. Sparse iterative closest point[C]// Computer Graphics Forum. Oxford: Blackwell Publishing Ltd., 2013: 113-123.

[35] 杨稳, 周明全, 郭宝, 等. 基于曲率图的颅骨点云配准方法[J]. 光学学报, 2020, 40(16): 1-11.

[36] YANG W, ZHOU M Q, GUO B, et al. Skull point cloud registration method based on curvature diagram[J]. Chinese Journal of Acta Optica Sinica, 2020, 40(16): 1-11.

[37] WU P, LI W, YAN M. 3D scene reconstruction based on improved ICP algorithm[J]. Microprocessors and Microsystems, 2020, 75: 103064.

[38] ZHANG J Y, YAO Y X, DENG B L. Fast and robust iterative closest point[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022, 44(7): 3450-3466.

[39] LIU Y S, CHEN Y X, FANG S P. A compensation method for the eccentricity and inclination errors of spiral bevel gear based on improved ICP algorithm[J]. Advances in Mechanical Engineering, 2021, 13(3): 16878140211004400.

[40] YANG J L, LI H D, CAMPBELL D, et al. Go—ICP: A globally optimal solution to 3D ICP point—set registration[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2016, 38(11): 2241-2254.

[41] LV C L, LIN W S, ZHAO B Q. KSS—ICP: Point cloud registration based on Kendall shape space[J]. IEEE Transactions on Image Processing, 2023, 32: 1681-1693.

[42] DU S Y, LIU J, ZHANG C J, et al. Probability iterative closest point algorithm for m—D point set registration with noise[J]. Neurocomputing, 2015, 157: 187-198.

[43] MA J, WU J, YANG K. Measurement point cloud registration method for complex mechanical parts based on improved ICP[C]// International Conference on Optical and Photonic Engineering. [S.l.]: SPIE, 2023: 23-29.

[44] VIZZO I, GUADAGNINO T, MERSCH B, et al. KISS—ICP: In defense of point—to—point ICP—simple, accurate, and robust registration if done the right way[J]. IEEE Robotics and Automation Letters, 2023, 8(2): 1029-1036.

[45] CAO L, ZHUANG S B, TIAN S, et al. A global structure and adaptive weight aware ICP algorithm for image registration[J]. Remote Sensing, 2023, 15(12): 3185.

[46] HE L P, WANG S Q, HU Q J, et al. GFOICP: Geometric feature optimized iterative closest point for 3D point cloud registration[J]. IEEE Transactions on Geoscience and Remote Sensing, 2023, 61: 1-17.

[47] FISCHLER M A, BOLLES R C. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[J]. Communications of the ACM, 1981, 24(6): 381-395.

[48] LI J Y, HU Q W, AI M Y. Point cloud registration based on one—point RANSAC and scale—annealing biweight estimation[J]. IEEE Transactions on Geoscience and Remote Sensing, 2021, 59(11): 9716-9729.

[49] CHUNG K L, CHANG W T. Centralized RANSAC—based point cloud registration with fast convergence and high accuracy[J]. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 2024, 17: 5431-5442.

[50] YANG J Q, HUANG Z Q, QUAN S W, et al. SAC—COT: Sample consensus by sampling compatibility triangles in graphs for 3—D point cloud registration[J]. IEEE Transactions on Geoscience and Remote Sensing, 2021, 60: 5700115.

[51] YANG J Q, ZHANG X Y, FAN S C, et al. Mutual voting for ranking 3D correspondences[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024, 46(6): 4041-4057.

[52] CHENG Y X, HUANG Z Q, QUAN S W, et al. Sampling locally, hypothesis globally: Accurate 3D point cloud registration with a RANSAC variant[J]. Visual Intelligence, 2023(1): 20.

[53] GRILLI E, MENNA F, REMONDINO F. A review of point clouds segmentation and classification algorithms[J]. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2017, 42: 339-344.

[54] TAN P, LI X, XU J, et al. Catenary insulator defect detection based on contour features and gray similarity matching[J]. Journal of Zhejiang University—Science A, 2020, 21(1): 64-73.

[55] WALCZAK J, POREDA T, WOJCIECHOWSKI A. Effective planar cluster detection in point clouds using histogram—driven kd—like partition and shifted mahalanobis distance based regression[J]. Remote Sensing, 2019, 11(21): 2465-2488.

[56] PENG Y P, LIN S D, WU H K, et al. Point cloud registration based on fast point feature histogram descriptors for 3D reconstruction of trees[J]. Remote Sensing, 2023, 15(15): 3775.

[57] 韩宝昌, 曹俊杰, 苏志勋 . 一种区域层次上的自动点云配准算法[J]. 计算机辅助设计与图形学学报, 2015, 27(2): 313-319.

[58] HAN B C, CAO J J, SU Z X. Automatic point clouds registration based on regions[J]. Journal of Computer—Aided Design & Computer Graphics, 2015, 27(2): 313-319.

[59] YANG Y N, ZHANG J W. Perron—Frobenius type theorem for nonnegative tubal matrices in the sense of t—product[J]. Journal of Mathematical Analysis and Applications, 2023, 528(2): 127541.

[60] HUANG C, LI J, GAO G. Review of quaternion—based color image processing methods[J]. Mathematics, 2023, 11(9): 2056.

[61] DENAYER M, DE WINTER J, BERNARDES E, et al. Comparison of point cloud registration techniques on scanned physical objects[J]. Sensors, 2024, 24(7): 2142.

[62] SUN L. RANSIC: Fast and highly robust estimation for rotation search and point cloud registration using invariant compatibility[J]. IEEE Robotics and Automation Letters, 2022, 7(1): 143-150.

[63] HU E W, SUN L. VODRAC: Efficient and robust correspondence—based point cloud registration with extreme outlier ratios[J]. Journal of King Saud University — Computer and Information Sciences, 2023, 35(1): 38-55.

[64] CHEN K, LV Q, LU Y, et al. Robust regularized extreme learning machine for regression using iteratively reweighted least squares[J]. Neurocomputing, 2017, 230: 345-358.

[65] The Stanford 3D Scanning Repository[EB/OL]. [ 2024—04—20]. http://graphics.stanford.edu/data/3Dscanrep.

[66] DMatch: Learning Local Geometric Descriptors from RGB—D Reconstructions[EB/OL]. (2016—03—27) [2024—04—20]. https://3dmatch.cs.princeton.edu/.

[67] Sketchfab[EB/OL]. (2016—11—21) [2024—05—20]. https://sketchfab.com/3d—models/tuy—5c8c0b15a0d246e7a08c2deecc0c6c4e.

基金资助

国家自然科学基金(62271393)

陕西省教育厅科学研究计划项目(25JS049)