基于区域划分的点云全局配准研究

周建钊，杜文超，颜雨吉，何晓辉，代菊英

(陆军工程大学 野战工程学院，江苏 南京 210007)

0 引言

由于激光以及结构光的物理性质以及被扫描物体自身相互遮挡的原因，扫描仪测量范围无法全方位覆盖完整的物体表面，需要从不同角度多次对目标物体进行扫描，从而获取的是多片相互重叠的点云。不同角度获取的点云具有不同的参考坐标系，必须把从不同角度获取的点云统一到同一坐标系中，才能获取被测物体完整的点云，这个过程即为点云配准[1]。

全局配准一般分为两类：一类是基于几何特征，常用的几何特征描述算法如Curvedness、Shape Index、FPFH[2]、3DSC[3]、Spin image[4-5]、VFH[6]等；另一类是基于穷举思想，比如随机采样一致性(Random Sample Consensus,RANSAC)算法[7]、四点全等集(4-Points Congruent Sets,4PCS)算法[8]以及Super4PCS算法[9]等。基于几何特征的方法过于依赖物体的几何特征，因设备精度以及人为原因产生的噪声、外点，将会严重影响配准的效果。因此，本文采用了对噪声、点云鲁棒性较强的基于穷举思想配准的方法对点云全局配准进行研究。

1 常用基于穷举思想的配准算法

1.1 随机采样一致性算法

随机采样一致性(RANSAC)算法是采用迭代的方式从一组包含离散值的样本数据中估算出数学模型参数，得到有效样本数据的一种算法，其基本步骤是：

(1)从样本P中随机抽取n个样本点构成样本子集D，用于初始化模型M，其中n为初始化模型参数所需的最小样本个数，P的样本数大于n。

(2)样本余集(从样本P中除去样本子集D后的集合)PC与模型M误差小于设定阈值δ的样本集与样本子集D构成有效样本集D*，构成D的一致集(Consensus Set)。

(3)若有效样本集D*不小于N，则认为得到了正确的模型参数，并利用有效样本集D*重新计算新的模型M*；重新随机抽取新的样本子集D，迭代重复以上过程。

(4)在完成一定的抽样次数后，选取抽样后得到的最大一致集的模型进行参数估计，算法结束；若未找到D的一致集则算法失败。

1.2 四点全等集算法

四点全等集(4PC))算法是在RANSAC算法的基础上在对应点选取策略上的改进。将RANSAC算法选取三点的策略改进为选取非共线的共面四点的策略，运用仿射变换理论，在目标点云中寻找全等集，运用于RANSAC框架下，实现点云全局配准。该算法在继承了RANSAC算法对噪声以及异常点鲁棒性较强优点的基础上，改进了算法的稳定性，减少了时间复杂度。

算法主要思想描述如下：

(1)基底选择。在点集P中选择一个由四个共面点组成的基底B≡{p1,p2,p3,p4}。

(2)全等集查找。通过上一步骤中确定的基底B，从点集Q中寻找出在一定范围与基底B配对的全部点对构成点集U≡{U1，U2，…，Us}。对于任意一个Ui，通过基底B与Ui都可以计算出相应的刚体变换矩阵Ti，使得B与Ui相互配准。

(3)剔除错误点对，计算最优刚体变换矩阵T。应用RANSAC思想，计算Ti(P)，并统计与点集Q之间距离小于δ的点的个数，评估不同的Ti，剔除掉错误的对应点对，从而得出最优刚体变换矩阵T。

(4)对于P中不同的基底Bj，循环上述过程均可计算出相应的最优变换矩阵Tj，根据重叠度f测试L组不同的基底Tj，最终得到最优刚体变换矩阵Topt。

1.3 超级四点全等集算法

随着三维扫描技术不断提升，对算法的高效性、稳定性提出了更高的要求。4PCS算法在处理效率上显然难以满足目前的要求，这就要求对其进行改进优化。该算法受限制于两个瓶颈：(1)在全等集查找中，查找出给定距离的所有点。对于P中给定的基底B，从Q中查找出所有的距离为d1、d2的两点对。(2)在剔除错误点对中，由于考虑仿射不变量而产生的大量的冗余候选四点对。产生的四点对是所有全等四点对的超集，包含大量冗余。

针对第一个查找两点对的瓶颈问题，超级四点全等集(Super4PC))算法提出采用栅格化[10]的方法，如图1的点云栅格化二维示意图所示，大大地缩短了在从Q中查找出所有距离为d1、d2的两点对的时间，提高了算法的效率。

图1 点云栅格化二维示意图

图2 错误对应点对示意图

Super4PCS算法针对上述问题提出在提取四点对的同时去除错误点对，即可得到与基底B对应的集合，从而在去除冗余点对的同时，大大提高了算法效率。由图2所示可知，若给定基底B的{p1,p2,p3,p4,θ}五个参数，在目标点云P中就可以搜索出唯一对应的四点对。

2 基于区域划分改进的点云全局配准

经过1.2节分析可知，Super4PCS算法在算法效率上有了巨大的改进，但对重叠率较低的两片点云执行全局配准时，往往容易收敛于局部最优，难以达到预想的效果。为提高配准效果，本文提出了基于区域划分改进的Super4PCS算法。首先根据重叠率的大小对两点云进行适当的区域划分，然后分别对每个区域内的两片点云执行Super4PCS算法，计算刚体变换矩阵并选择出配准效果最好的两片对应区域，对整体源点云执行上述刚体变换，从而实现点云的全局配准[11]。下面重点对区域划分以及区域配准两个环节展开讨论。

2.1 区域划分

空间栅格法[12]和Voronoi图法[13]等都是常用于区域划分的方法。空间栅格法是将包围点云的最小长方体包围盒均匀地划分成边长为L的小立方体单元栅格的方法。Voronoi图法是通过求取区域内相邻两点的垂直平分线将区域划分为多个连续多边形的方法。综合对比上述两个划分方法后，本文采用Voronoi图法进行划分，如图3所示。

图3 二维Voronoi图法划分过程示意图

本文中区域划分首先分别对源点云和目标点云进行均匀采样构成采样点集合为{pi,i=1,2,…,M}和{qj,j=1,2,…,N}；然后，应用Voronoi图法对两点云进行区域的划分。M、N分别表示对源点云与目标点云划分区域的数目。区域数目由两点云的重叠比例决定，一般取值为1～20。当重叠比例越小，区域数目取值越大；相反，当重叠比例越大，区域数目取值越小，当区域数目为1时，点云的区域配准即为全局配准。

2.2 区域配准

区域配准实际上是对点云中的一部分点云与另点云中的一部分点云进行配准，本质上没有发生任何变化。现有的诸多配准方法均适用于点云内区域间的配准。

Super4PCS算法不依赖于曲率、法线等几何特征，不会受到噪声和异常值等因素的严重影响，鲁棒性较好；该算法是对4PCS算法的改进，大大提高了算法的效率，具有较低的时间复杂度；同时，Super4PCS算法能够自动估计点云的配准效果，对于每一次区域配准都能够给出一个最大化公共点集(LCP)度量，遍历所有的M×N个配准区域对，比较其LCP度量值即可得到重叠率最高的两片区域。因此，本文选择采用Super4PCS算法进行点云的区域间配准。

2.3 算法步骤

针对目前常用算法对于重叠率较低的两片点云，难以实现理想的全局配准效果的问题，本文提出了基于区域划分改进的点云全局配准。图4所示为算法的流程图。

图4 基于区域划分改进的点云全局配准算法流程图

算法具体步骤为：

(1)输入源点云P={pi|pi∈R}与目标点云Q={qj|qj∈R}；初始化P中M个区域迭代次数m=0，Q中N个区域迭代次数n=0，Pm中基底迭代次数i，其中m∈[0，M],n∈[0，N],i∈[0，imax]。

(2)对P和Q进行区域划分，分别划分为M、N个区域。

(3)在源点云P中的Pm区域中，选择基底Bmi={p1,p2,p3,p4,θ}。

(4)运用Super4PCS算法，在目标点云Q中的Qn区域中查找四点全等集{q1,q2,q3,q4,θ}。

(5)判断是否i

(6)比较LCPmni度量值，计算出最大的重叠比例，将其对应的旋转矩阵Rmni和平移向量tmni应用于全局配准中，计算出刚体变换后的点云P′=RmniP+tmni；

(7)输出变换后的P′以及目标点云Q，实现全局配准。

3 实验结果与分析

为了验证本文全局配准算法的实际效果，对斯坦福大学点云模型数据库和PCL官网中的大量点云模型进行了实验，选取了各具代表性的bunny、dragon和Armadillo点云模型。通过与4PCS算法进行比较，证明本算法的有效性。分别对比验证了不同类型模型的配准效果，以及不同采样点数目和在不同重叠比例下的配准效率。

实验一：bunny模型的全局配准。图5(a)和图5(b)为bunny模型不同视角下获取的两片点云。目标点云为5 622个点，如图5(a)所示，源点云为5 401个点，如图5(b)所示，两点云的重叠比例为90%。bunny模型是经典的点云配准模型，其具有模型简单，特征明显，点云分布均匀等特点。

图5 bunny模型全局配准效果图

图5为bunny模拟采用两种不同全局配准算法的效果图，其中(a)为目标点云，(b)为源点云，(c)为采用4PCS算法对两点云配准后效果图，(d)为采用本文算法对两点云配准后效果图。

实验二：dragon模型的全局配准。图6(a)和图6(b)为dragon模型不同视角下获取的两片点云。目标点云为12 197个点，如图6(a)所示，源点云为8 917个点，如图6(b)所示。两点云的重叠比例为60%。dragon模型形状复杂，较多点的几何特征相似甚至相同，且选取的两片点云重叠比例较低。

图6 dragon模型全局配准效果图

图6为dragon模型采用两种不同全局配准算法的效果图，其中(a)为目标点云，(b)为源点云，(c)为采用4PCS算法对两点云配准后效果图，(d)为采用本文算法对两点云配准后效果图。

实验三：Armadillo模型的全局配准。图7(a)和图7(b)为Armadillo模型不同视角下获取的两片点云。目标点云为19 283个点，如图7(a)所示，源点云为22 410个点，，如图7(b)所示。两点云的重叠比例为30%。Armadillo模型形状十分复杂，特征较明显，且选取的两片点云分别来自于正面与背面两个视角，重叠比例十分低。

图7 Armadillo模型全局配准效果图

图7为Armadillo模拟采用两种不同全局配准算法的效果图，其中(a)为目标点云，(b)为源点云，(c)为采用4PCS算法对两点云配准后效果图，(d)为采用本文算法对两点云配准后效果图。

通过实验数据，综合对比以上三组实验，如表1所示。横向对比可发现，本文算法较4PCS算法在效率上有很大的改进，在较低重叠比例下仍能够得到较好的配准效果。纵向对比来看，随着点云数目总体上的增加，配准平均耗时增加，随着重叠比例的减少，配准平均耗时也显著增大。但对于多个变量同时作用的结果，难以得出理想结论。因此，本文采用控制变量的方法，分别研究在相同模型相同重叠比例下不同点云数目对两种算法配准效率的影响，以及在相同模型近似点云数目下不同重叠比例对两种算法配准效率的影响。

表1 三组实验数据对比

(1)重叠比例对配准效率影响

该实验采用经典的bunny模型，所有组的目标点云数目近似为40 256，源点云数目近似为40 097。改变两点云的重叠比例，每一重叠比例下多次实验取平均值，分别对比4PCS算法和本文算法，实验结果如图8所示。

图8 不同重叠比例对配准效率的影响

通过对比可发现两种算法随着重叠比例的降低，配准时间增加，且比例越低，耗时增加越显著。4PCS算法在40%重叠比例时，配准时间显著增加；而本文算法则低于20%重叠比例时才会显著变化。横向对比两种算法可得，本文算法在较低重叠比例时算法效率明显优于4PCS算法，且4PCS算法在较低重叠比例时易出现错误配准。因此，对于低重叠比例的情况，本文算法明显优于4PCS算法。

(2)采样点数目对配准效率的影响

该实验采用经典的bunny模型，所有组的重叠比例均为90%。改变采样点的数目，对于每一组进行多次实验取平均值，分别对比4PCS算法和本文算法，实验结果如图9所示。

图9 不同采样点数目对配准效率的影响

通过对比可以发现两种算法随着点云数目的增加，配准时间成比例增加。在点云数目较少时，两种算法配准时间相近且变化率较小，说明此时点云数目对配准时间影响较小。随着点云数目增多，配准时间成比例增加，这主要受点云数目的影响。横向对比两种算法可得，整体上本文算法在算法效率优于4PCS算法，点云数目越多，优势越明显。

4 结论

本文提出的基于区域划分的全局配准算法为点云局部配准提供了较好的初始位置，同时大大提高了配准效率，相比于目前常用全局配准算法，该算法对低重叠比例的两点云具有良好的效果。本文提出的基于区域划分的全局配准算法对于几何特征不明显且重叠比例较低的点云具有较好的配准效果，对提高点云全局配准的精度及效率具有重要的意义。