基于加权距离投票的点云匹配算法设计

韩德川

（中国电子科技集团公司第二十研究所，西安 710068）

0 引言

在计算机应用领域，点云匹配是一个非常重要的中间步骤，它在表面重建、三维物体识别、相机定位等问题中有着极其重要的应用。对于点云匹配问题，研究者提出了很多解决方案，如点标记法、自旋图像、主曲率方法、遗传算法、随机采样一致性算法等，这些算法各有特色，在许多特定的情况下能够解决点云匹配的问题。但是应用最广泛、影响最大的还是由Besl于1992 年提出的迭代最近点算法（Itera⁃tiveClosest Point，ICP），该算法重复进行选择对应关系点对，计算最优刚体变换，直到满足正确配准的收敛精度要求，其本质是基于最小二乘法的最优配准方法。ICP算法虽然因为简单而被广泛应用，但是它易于陷入局部最大值，同时其严重依赖初始配准位置，它要求两个点云的初始位置必须足够近，并且当存在噪声点、外点时可能导致配准失败。除ICP 算法之外，Tsin和Kanade应用核密度估计，将点云表示成概率密度，提出了核心相关算法（Kernel Correla⁃tion，KC）。这种计算最优配准的方法通过设置两个点云间的相似度测量来减小它们的距离。对全局目标函数执行最优化算法，使目标函数值减小到收敛域。因为一个点云中的点必须和另一个点云中的所有点进行比较，所以这种方法的算法复杂度很高。

在生产制造中，很多时候需要对部件位姿调整过程中的点云进行匹配，例如航天器的自动对接过程，然而上述较为熟知的算法，无法很好地适用于部件位姿调整过程中的点云匹配任务，进而无法完成姿态追踪等问题，对此，本文提出一种基于加权距离投票的点云匹配算法，完成位姿调整过程中的部件表面点云匹配。

1 算法原理

本文所提出的点云匹配算法是建立在点云的距离不变性之上的。随着部件位姿调整，部件外形在线测量系统可获得不同视角下的部件表面标志点点云数据，但标志点与其周围的标志点的空间距离是不随测量视角改变而发生变化，本文利用部件表面点云的距离不变性来进行点云匹配。

图1 距离不变性示意图

假设不同视角下测得移动部件表面局部点云数据1 和点云数据2 包含部分共有的标志点测量数据，其中移动部件表面局部点云数据1中的测量标志点为：={s|s∈,= 1,2…} ，移动部件表面局部点云数据2 中的测量标志点为：={t|t∈,= 1,2…} 。部件表面测量点云的匹配过程，即找到、中同一测量标志点，确定部件表面局部点云间同一测量标志点点对集，完成无序点云匹配的过程。设和中同一部件表面测量标志点构成的有序子集分 别 为：={p| p∈,= 1,2…} 和={q|q∈,= 1,2…} ，其中(p,q)为匹配测量标志点点对，即(p,q)分别为不同视角下同一测量标志点的三维空间坐标，则点云匹配过程如图2所示。

图2 部件表面测量点云匹配

根据标志点的空间距离不变性，若(p,q)、(p,q)为两组匹配测量标志点点对时，必满足如下约束。

其中，为距离误差阈值，由双目测量精度确定。

因此，由于测量标志点空间分布的随机性，当(p,q)为匹配测量标志点点对时，p到部件表面局部点云中每个点的距离依次与q到部件表面局部点云中每个点的距离相比较，满足以下不等式的总个数最多。

图3 距离投票示意图

遍历过点p的所有边，并按以上规则对中顶点进行投票，当所有的边投票结束时，得票最多的点T即为点p的匹配点。重复以上步骤，直至找到部件表面局部点云和部件表面局部点云中所有的匹配点对。

2 算法实现

（5）遍历部件表面局部点云中所有顶点的得票数，得分最多的点T即为待匹配点S的匹配点；

（6）循环执行步骤（3）直至找到所有匹配点对；

3 算法分析

3.1 算法时效性分析

通过不同规模的点云仿真实验对点云匹配算法的时效性展开分析，部分点云匹配结果如图4所示。其中，圆点云为原始点云，菱形点为目标点云，五角星点为由距离投票法计算转换矩阵对原始点云的转换结果。

图4 点云匹配时效性分析

点云匹配实验中点云匹配时间如表1所示。

表1 点云匹配时间统计

通过表1的结果，作出基于加权距离投票的点云匹配算法的时间-点数曲线拟合，结果如图5所示。

图5 点云匹配时间-点数曲线图

由图5所示的实验数据所拟合的点云匹配算法的时间-点数曲线为：

式中，为匹配时间，为点云数目。拟合结果见表2。

表2 拟合结果准确性分析

由图5 可知，当点数在30 以内时，时间随点的个数增加速度平缓，且由式（3）可知，此时匹配算法耗时在0.011 s 以内，满足算法的实时性要求。

3.2 算法匹配准确性分析

匹配算法的时效性实验中，实验结果充分证明了匹配算法在点云数据理想时是有效的。但在实际部件位姿调整过程中，由于双目相机的视角变化、测量环境的变化及标志点测量算法发生退化时，会造成部件表面标志点点云测量数据的测量误差，所以有必要验证在点云数据质量差时，本文点云匹配算法的有效性。

如图6 所示，由于标志点空间位置测量时，必然存在一定的测量误差，故实验验证时，首先给定一组柱面模拟点云数据1，给数据1 中每一点叠加测量误差，得到柱面模拟点云数据2，对点云数据1 进行刚体变换后同样叠加测量误差，得到点云数据3；其中点云数据1 为标志点的理论空间位置，点云数据2、点云数据3 为理论标志点云在不同视角下的观测值。此时以点云数据2及点云数据3进行点云匹配模拟实验。

图6 测量误差示意图

如图7所示，部件对接工况下，在部件位姿调整过程中，由于双目相机的视角变化、标志点的遮挡及标志点检测算法发生退化会造成部件表面点云数据的不完整，此时待匹配局部点云只有部分重叠。故在实验时，通过将不同视角下的测量点云中各自独立删除部分空间点进行模拟实验。

图7 部分重叠示意图

由时效性分析实验可知，当匹配点云中待匹配点数在30 以内时，距离投票算法耗时在0.011 s 内，可满足追踪算法的实时性要求，故实验考虑在30 点以内的点云匹配问题，部分实验如图8所示。

图8 非完整点云匹配结果

由表3可知，本文提出的基于加权距离投票的点云匹配算法，在仿真点云存在测量误差及点云数据不完整的情况下是可靠的。

表3 非完整点云匹配结果

续表3

4 结语

本文给出了基于加权距离投票的点云匹配算法，从时效性和匹配准确性两方面对算法进行分析，分析结果显示算法满足实时性要求，在仿真点云存在测量误差及点云数据不完整的情况下，点云匹配算法是可靠的。该算法可以解决点云匹配过程中的一些相关问题，具有一定的实际意义。