一种针对大规模场景的点云匹配算法

刘芊伟 张朝霞 谢怡婷 张成龙

收稿日期：2023-11-10

基金项目：广东省自然科学基金（2014A030313739）

DOI：10.19850/j.cnki.2096-4706.2024.07.030

摘  要：针对大规模点云匹配时传统算法速度慢和匹配结果不一致的问题，提出一种新的点云匹配方法。该方法首先利用KD树找到点云中深度最小的点并以该点作为种子点，然后通过在深度信息和曲率两个方面做以改进的区域生长分割算法提取出点云上表面区域，并在该区域提取点云边界。最后使用改进的点对特征完成点云匹配算法验证。实验结果表明，相比传统算法，该方法在匹配速度以及匹配结果的一致性方面得到了显著的提升，在处理大规模点云匹配上具有实际应用价值。

关键词：大规模点云；
KD树；
改进的区域生长分割算法；
点对特征

中图分类号：TP312；
TP301.6 文献标识码：A 文章编号：2096-4706（2024）07-0146-05

A Point Cloud Matching Algorithm for Large-scale Scenarios

LIU Qianwei， ZHANG Chaoxia， XIE Yiting， ZHANG Chenglong

（School of Mechatronic Engineering and Automation， Foshan University， Foshan  528225， China）

Abstract：
A new point cloud matching method is proposed to address the issues of slow speed and inconsistent matching results in traditional algorithms in large-scale point cloud matching. This method first uses the KD tree to find the point with the minimum depth in point cloud and uses it as a seed point. Then， an improved region growth segmentation algorithm improving in depth information and curvature is used to extract the upper surface area of point cloud， and the point cloud boundary is extracted in this area. Finally， the point cloud matching algorithm is validated using improved point pair features. The experimental results show that compared with traditional algorithms， the proposed method has significantly improved matching speed and consistency of matching results， and has practical application value in handling large-scale point cloud matching.

Keywords：
large-scale point cloud; KD tree; improved region growth segmentation algorithm; point pair feature

0  引  言

点云匹配[1]是计算机视觉和机器人领域中的一个重要问题，其目的是将两个或多个点云对齐，从而实现对点云的精确比较、配准或合并等操作。点云匹配广泛应用于无序抓取[2]和三维重建[3]等方面。常用的点云匹配算法有基于模板的点云匹配算法和基于特征的点云匹配算法。

基于模板的点云匹配算法[4-7]大致思路是采用物体的三维模型在多视角下进行投影，经过点云处理后提取特征形成姿态库，并将姿态库中的图像逐一与RGB-D图像进行比对选出最合适的模板作为物体的位姿。Peng等人[4]在LineMOD [5]算法的基础上提出一种多尺度模板训练方法，该方法在进行模板匹配时，首先将测试图像划分为几个区域，然后根据每个测试图像的区域深度选择深度相似的训练模板。该算法相比于LineMOD算法，增强了对模板深度的敏感度，提高了模板匹配的速度。Ye [6]等人通过金字塔的在线分层搜索，收集所有相似度量标准的候选模板。所有候选模板及其相邻模板都被追踪到金字塔的下一个较低级别。重复相同操作，直至所有候选模板都被追踪到金字塔的最低级别。

基于特征的方法有基于局部特征的方法[8，9]和基于全局特征的方法[10，11]。Liu [8]等人在原有基于快速点特征直方图匹配算法的基础上，以豪斯多夫距离搜索对应的点对，并利用随机采样一致性算法剔除不正确的点对，从而提高对应关系的准确性。Yue [9]等人提出的LPPF特征描述符是对经典点对特征局部应用的改进描述符，是通过计算局部点云邻域的特征信息而形成的直方图描述符，配准精度更高，配准时间更短。Guo [10]等人提出一种基于PPF改进的识别框架，特别是提出一种新的基于目标中心和点对特征之间几何关系的中心投票策略。该算法对相似外观的干扰物、传感器噪声和简单几何形状具有鉴别性和鲁棒性。Liu [11]等人提出一种使用多个模型描述目标物体的方法——多边缘外观模型，以提高识别率并减少计算时间。

本文介绍一种针对大规模场景的点云匹配算法，相较于现有的点云匹配算法，该算法在以下三个方面得到了显著提升：

1）所提取的特征点是点云的轮廓点，能够保留更多的点云基本信息，适用于大规模的点云匹配。

2）对场景点云进行区域化设置，并仅对上表面点云进行匹配，解决了点云匹配结果不一致的情况，同时提高了点云匹配的速度。

3）改进的点对特征提高了匹配算法的准确性。

1  提出的方法

1.1  点云区域化

在堆叠大场景中有较多相似特征的点云时，采用传统点对特征匹配算法进行多次匹配会出现匹配结果不一致的情况，同时匹配速度也比较缓慢。图1、图2为在相同场景下多次使用传统点对特征匹配的结果（图中带有箭头的灰色区域为匹配后模板点云区域），从图中可以看到匹配结果并不一致，且图2中的点云是底部点云不利于做无序抓取。

为解决传统点对匹配算法存在的匹配速度缓慢和匹配结果不一致的问题，选择采用点云区域化的方法。该方法融合了深度信息和曲率，通过对表面点云进行提取和匹配，有效解决了传统点云匹配算法存在的问题。图3为提取出来的上表面区域（图中灰色区域）。具体步骤为：通过KD树找到深度最小的点并将该点作为种子点，根据一定的判断条件确定是否将邻域内的点加到当前种子点所属的区域。判断条件如下：

1）距离条件：邻域内的点与种子点之间的距离在一定的阈值范围内。

2）曲率条件：邻域内点的曲率ki与种子点的曲率差异在一定的阈值范围内。Mi为点mi的协方差矩阵，计算式如式（1）所示，通过式（2）计算出特征向量和特征值，最小特征值对应的特征向量可以表示一个区域中法向量的大致趋势，可以作为法向量。而最大特征值可以作为曲率ki表示整个区域的弯曲程度。

从初始种子点开始，逐步扩展邻域，根据上述条件将符合条件的点添加到当前区域中。可以使用深度优先搜索等算法来遍历点云并进行区域生长。

在算法运算的过程中，可能会出现不同种子点生长到同一区域的情况，此时可以进行区域合并，将重叠的区域合并成一个。

遍历所有的子区域，用KD树判断深度最小的点位于哪个子区域的领域内，这时可以得到包含深度最小点的匹配区域。

（1）

（2）

其中， 为特征向量；

为特征值，设 ；

为最小特征值；

为mi的法向量；

为最大特征值且为mi的曲率kj。

（3）

1.2  点云关键点提取

点云关键点是指能够反映点云几何形状的点集。通过点云特征点确定的特征描述符具有平移旋转不变性。选用点云的边界点作为点云的关键点，能够在保证点云基本信息不变的情况下得到较好的匹配结果。

本文通过点云法向量提取点云边界，该算法通过计算每个点的法向量与其相邻点法向量之间的夹角来识别边界点。具体来说，该算法的步骤为：首先计算每个点的法向量，通过pi与其最近邻点集合Ni中所有点的均值pa计算pi的协方差矩阵Mi：

（4）

其中，n为pi领域点的个数。对Mi进行特征值分解得到特征向量和特征值：

（5）

其中， 为特征向量；

为特征值，设 ，则最小特征值  是点pi的法向量。首先采用KD树数据结构找到每个点的相邻点；
然后计算每个点的法向量与其相邻点的法向量之间的夹角，将夹角超过预设阈值的点标记为边界点；
最后对边界点进行聚类以识别多个不同的边界。该算法运用了点云中每个点的法向量信息，具有简单、高效、适用于大规模点云数据集等优点。如图4所示为提取轮廓前后的模板点云图。

1.3  改进的点对特征

提取完上表面点云的特征点后，后续就是对模板点云进行离线建模，对上表面场景点云进行特征计算。然后通过哈希表查找上表面点云和模板点云相似的特征对。

传统点对特征匹配算法的特征是通过两个点之间法向量的关系得到的，它可以表示两个点之间的位置关系，具体的描述如图5所示。已知法线n1、n2、点m1和m2，可以通过式（6）得到点对特征。其中，F1为两个点之间的距离，而F2、F3、F4为法向量n1、n2和向量m1m2的夹角。特征描述如图5所示。

当涉及点云的特征匹配时，传统方法通常仅关注点对之间的关系，而忽略了整体的点云结构和曲率特性。为了克服这一弊端，本文提出一种改进的特征匹配方法，它综合考虑了邻域信息和曲率特征，以下是详细描述：

首先，引入点的邻域概念，对每个点定义邻域N1和N2。这样的设计能够更全面地把握每个点的特征，不再局限于分析点对之间的关系。

随后，计算邻域N1和N2内点的协方差矩阵，分别标记为M1和M2。协方差矩阵是一个有力的工具，可以描述点在不同坐标轴上的分布情况和协同变化。此外，充分考虑了点云的曲率特性，用于更好地描述点的曲率情况。曲率是描述曲线或曲面弯曲程度的重要概念。传统的点对特征很难准确捕捉点云的曲率特征。因此，在本方法中，通过计算点云的曲率信息，能够更加准确地呈现点云表面的局部特点。综上，这种方法能够更全面地描述每个点的特征。通过结合点的邻域结构和曲率信息，提高了特征匹配的准确性和鲁棒性。改进的点对特征计算式如式（11）所示。F1、F2、F3、F4为传统的点对特征，而F5、F6为m1和m2的曲率。特征描述如图6所示。

（11）

（12）

（13）

2  实验部分

本节描述了本文算法在点云数据上的性能测试，并将测试结果与现有最先进描述符的结果进行了比较。场景点云和模板点云通过三维相机拍摄获得。其中模板点云的大小为11 980，场景点云的大小为几十万的数量级，满足大规模点云匹配的要求。为了验证本文算法的有效性，在四个场景下对PPF、FPFH和本文算法进行了比较。

2.1  算法评价指标

为了对比不同算法的实验效果，使用了均方根误差（RMSE）和运行时间（TIME）。通过RMSE来确定算法匹配的精度，采用TIME来表示算法的时间复杂度。

RMSE用于评估预测值与真实值之间的误差。在点云匹配中，模板点云经过刚体变换后得到一组点云，对这组点云和场景点云进行计算即可得到均方根误差。RMSE计算式如式（14）所示：

（14）

其中，pi为刚体变换后模板点云中的点；
qi为场景点云中距离pi最近的点。

2.2  匹配实验

针对三组场景点云进行了三种算法的实验，包括本文算法、FPFH和PPF，记录了实验数据。实验结果如图7、图8和图9所示（图中带有箭头的灰色区域为匹配后模板点云区域），实验数据如表1所示。在图7中，（a）和（b）展示了PPF对场景a进行匹配时的两次不同结果，（c）（d）展示了PPF算法对场景b、c进行匹配后的结果。图8展示了FPFH算法对场景a、d、c匹配后的结果。图9展示了本文算法对场景a、b、c匹配后的结果。

在三个不同的场景中，分别使用PPF、FPFH和本文算法进行了实验，并记录了这些算法在每个场景中的性能指标，包括处理的点云数量、均方根误差（RMSE）和运行时间（TIME）。相关数据整理在表1中。通过对这些数据的分析，能够得出以下几个结论。

首先，从数据来看，FPFH算法的运行速度优于PPF算法，但前者在匹配精度上稍有下降。与之相反，本文算法在匹配速度方面不仅超越了FPFH算法，在匹配精度方面亦表现出色，优于PPF算法。因此，本文算法在处理大规模点云匹配任务方面表现出色。

其次，在使用PPF算法进行场景a匹配时，出现了两次匹配结果不一致的情况。而使用本文算法可有效避免这种情况的发生。

最后，通过匹配结果的可视化，发现当使用PPF算法和FPFH算法进行匹配时，这些算法会出现匹配底层的点云。然而，本文算法将匹配点集中在了物体表面上的点云。这一特性有助于避免在无序取任务中错误地抓取底层物体。

3  结  论

为了解决传统点对特征匹配算法匹配速度慢和匹配不一致的问题，本文提出一种新的点云匹配算法，该算法通过引入改进的区域生长分割和点云的深度信息，加快了匹配速度并提高了匹配的一致性。同时，在传统点对特征的基础上加入了曲率特征，提高了点云匹配的精度。因此，在应对点云匹配问题时，本文算法提供一种有效且可行的解决方案。

参考文献：

[1] 李建微，占家旺.三维点云配准方法研究进展 [J].中国图像图形学报，2022，27（2）：349-367.

[2] 陶杰，吴尧才，朱熙豪，等.基于3D视觉的水泵生产线零部件无序抓取研究 [J].机电工程，2022，39（5）：604-611+640.

[3] ZHANG X，CHEN L，ZHANG F F，et al. Research on the Accuracy and Speed of Three-dimensional Reconstruction of Liver Surface Based on Binocular Structured Light [J].IEEE Access，2021，9：87592-87610.

[4] PENG J，SU Y. An Improved Algorithm for Detection and Pose Estimation of Texture-Less Objects [J].Journal of Advanced Computatioanl Intelligence and Intelligent Informatics，2021，25（2）：204-212.

[5] HINTERSTOISSER S，HOLZER S，CAGNIART C，et al. Multimodal Templates for Real-time Detection of Texture-less Objects in Heavily Cluttered Scenes [C]//Proceedings of the 2011 International Conference on Computer Vision. [S.I.]：IEEE Computer Society，2011：858-865.

[6] YE C Q，LI K，JIA L，et al. Fast Hierarchical Template Matching Strategy for Real-Time Pose Estimation of Texture-Less Objects [C]//International Conference on Intelligent Robotics and Applications. Tokyo：Springer，2016：225-236.

[7] HINTERSTOISSER S，CAGNIART C，ILIC S，et al. Gradient response maps for real-time detection of textureless objects [J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34（5）：876-888.

[8] LIU Y S，KONG D H，ZHAO D D，et al. A Point Cloud Registration Algorithm Based on Feature Extraction and Matching [J/OL].Mathematical Problems in Engineering，2018，2018[2023-10-02].https：//doi.org/10.1155/2018/7352691.

[9] YUE X F，LIU Z Y，ZHU J，et al. Coarse-fine Point Cloud Registration Based on Local Point-pair Features and the Iterative Closest Point Algorithm [J].Applied Intelligence，2022，52（11）：12569-12583.

[10] GUO J W，XING X J，QUAN W Z，et al. Efficient Center Voting for Object Detection and 6D Pose Estimation in 3D Point Cloud [J/OL].IEEE Transactions on Image Processing：
a Publication of the IEEE Signal Processing Society，2021，30：5072-5084.

[11] LIU D Y，ARAI S，MIAO J Q，et al. Point Pair Feature-Based Pose Estimation with Multiple Edge Appearance Models （PPF-MEAM） for Robotic Bin Picking [J/OL].Sensors，2018，18（8）：2719[2023-09-20]. https：//doi.org/10.3390/s18082719.

作者简介：刘芊伟（2000—），男，汉族，江西上饶人，硕士研究生在读，研究方向：三维视觉；
张朝霞（1976—），女，汉族，广东佛山人，副教授，博士，研究方向：三维视觉；
谢怡婷（2000—），女，汉族，广东梅州人，硕士研究生在读，研究方向：三维视觉；
张成龙（1997—），男，汉族，广东茂名人，硕士研究生在读，研究方向：三维视觉。