基于轮廓点的三维点云配准*

于微波，钱柏竹，杨宏韬，何科毅

(长春工业大学电气与电子工程学院，长春 130012)

0 引言

三维点云数据是离散点组成的集合，构成物体的几何特征，同时还具有较高的精简性和灵活性，因此逐渐成为三维重建中常见的处理对象，与之相关的点云配准逐渐成为热门的研究方向。

点云配准是三维重建研究中的关键技术之一，在点云数据完整且重叠率相对较高的情况下，传统的点云配准方法会获得较好的配准结果，但往往由于设备以及环境等因素，获得的点云数据常常有所缺失且重叠率较低，这时用传统的点云配准方法导致配准的结果误差很大，配准时间较长等问题，严重影响接下来的三维重建的结果。

在点云配准中，如果直接把每个点都纳入计算中，就会使算法的计算时限很长。所以在近年来，已经有不少学者都在点云的提取方向中作了不少研究，这样就会使计算的时限大大地缩短，而且都可以取得不错的配准成果。李仁忠等[1]提出采用ISS算法对源点云进行提取特征点操作，采用点特征直方图(FPFH)对提取的特征点进行特征描述，结合改进的迭代最近点(ICP)[2]算法进行点云配准处理，该算法提高了该点云数据之间的配准速度，但在点云配准精度方面与ICP算法相差不大；鲁铁定等[3]提出一种改进的超四点快速鲁棒匹配算法(super four point fast robust matching algorithm，Super 4PCS)，将3D-SIFT算法用于提取点云数据中的关键点，减少总体的点云数据，但该算法处理低重叠率的点云数据得不到良好的配准结果。陆军等[4]提出一种多尺度加权法向投影均值差的特征点提取方法，该方法的主要目的是提取点云数据中具有明显特征的关键点，同时对关键点计算方向直方图签名描述子(SHOT)，用随机采样一致性(RANSAC)算法结合ICP算法完成点云配准，该算法基本解决对于低重叠率时点云配准结果较差的问题，但常面临噪声影响较大、时间复杂度较高等问题。胡加涛等[5]提出一种基于几何特征的由粗到细的点云配准算法，利用投影变换提取轮廓点，根据曲率特征对所获得的轮廓点进行特征描述，从而实现粗配准。但该算法在具有低重叠程度的点云数据得不到较好的配准结果。荆路等[6]提出一种基于尺度不变特征变换(SIFT)特征点结合ICP的点云配准方法，利用SIFT算法提取特征点，对提取的特征点计算点特征直方图(FPFH)的值，将该特征值带入采样一致性初始配准算法(SAC-IA)实现点云粗配准，然后利用ICP计算实现点云的精配准。但该算法在提取点云数据的特征点需要一定的时间。梁振斌等[7]提出一种利用深度学习进行点云配准的方法，首先通过训练生成3D描述子，然后利用生成的3D描述子对关键点进行特征描述，获取对应点对的集合，实现点云配准。但该算法中特征点的描述子需要经过从大量的数据集训练中得出，配准时间较长。

本文针对目前的三维点云配准算法中，配准时间长，配准结果产生错位、局部最小值等问题。采用两步配准方式，先对三维点云数据进行初始配准，然后针对初始配准的结果，进行精确配准，防止产生局部最小值的问题，同时提出一种基于轮廓点作为特征点的提取算法，以减少配准所需的时间。

1 三维点云配准流程

在初始配准阶段，提出一种基于轮廓点的配准方法，利用聚类算法对点云数据进行分割，引入角度阈值进行轮廓点提取，以提取出的轮廓点作为特征点，计算3DSC描述值，获得对应关系，根据对应关系，再采用改进的随机采样一致性(RANSAC)算法计算变换矩阵，完成初始配准。点云初始配准之后，源点云已经与目标点云基本重合，但是仍然存在偏差，因此需要在初始配准的基础上，进行精配准。采用广义迭代最近点(generalized iterative closest point，GICP)算法进行轴承盖点云数据的精配准。算法流程图如图1所示。

图1 改进的点云配准算法流程图

2 三维点云初始配准算法

2.1 三维点云特征点提取

2.1.1 三维点云分割处理

由于三维点云数据的空间关系较为复杂，因此通过对固定的距离阈值对点云进行聚类，将产生过分割以及欠分割等问题，因此，采用基于密度的DBSCAN聚类算法[8]进行点云数据的分割处理。给定源点云数据集P={p1,p2,…,pn}和目标点云数据集Q={q1,q2,…,qm}，为了提高搜索效率，将k-d tree数据结构引入到DBSCAN算法中形成改进的DBSCAN算法，其算法流程是：

步骤1：对于需要进行处理的点云数据P和Q，给定参数Eps和参数MinPts。

步骤2：建立点云数据的k-d tree数据结构。

步骤3：随机在源点云数据集P和目标点云数据集Q中各找一点pi和点qi，通过参数Eps和参数MinPts，判断点pi和点qi是否为核心点。

步骤4：若点pi和点qi为核心点，根据密度可达要求可以找到该核心点的可达点集合分别为P1和Q1。

步骤5：重复步骤3、步骤4，直到给定的数据集中的所有点都被访问过。于是得到聚类完成的点集P1,P2,…,Pn和Q1,Q2,…,Qm。

将采集的三维点云数据，使用改进后的DBSCAN算法进行聚类分割，分割结果如图2和图3所示。

(a) 分割得到上表面 (b) 分割后得到正表面

(a) 分割得到上表面 (b) 分割后得到侧表面

2.1.2 基于角度阈值的特征点提取

三维点云数据中的点可以分为内点和边界轮廓点，如图4和图5所示。根据2.1.1节可以得到分割后的点云数据，需要对分割后的点云数据进行边界轮廓提取。因此需要判别该点是否为边界轮廓点。根据图4和图5可以直观发现，如果点P在点云数据的内部时，点P与周围点的连线夹角在每个角度均会存在，但点P在点云数据的边界时，点P与周围点的连线夹角超过一定的角度之后，这种连线夹角就不存在，则这样的点P为边界点。

将点P与其K邻域点投影到其构造的最小二乘平面，设K邻域点为Mi(i∈[0,k-1])，Mj为P的K邻域最近点，以PMj为基准向量，取K邻域点中其他任意一点Mi，作向量PMi。

首先，计算PMj与PMi向量间的夹角β(β∈[0,π])以及叉积向量ni=PMj×PMi，并以此为基准向量。

当nj·ni>0时，βi保持不变；当nj·ni<0时，βi=βi+π。

然后，对向量夹角序列s=(β1,β2,…,βk-1)进行升序排列并加入两个极值角度，得到新的向量夹角序列s=(0,β1,β2,…,βk-1,2π)，则每个相邻线段之间的夹角θi=βi+1-βi(i∈[0,k])。根据θi是否超过设定阈值来判断P点是否为边界轮廓点。

图4 点P为边界轮廓点 图5 点P在点云内部

针对分割后的三维点云数据，进行基于角度阈值的特征点提取可以得到图6和图8的实验结果，将得到的分割后的目标点云特征点和分割后的源点云特征点分别进行取并处理，得到图7和图9的整体轮廓特征点的结果。

图6 分割后目标点云的特征点 图7 整体目标点云的特征点

图8 分割后源点云的特征点 图9 整体源点云的特征点

2.2 三维点云特征点描述

由2.1节获得目标点云P和源点云Q的特征点后，需要对提取的特征点计算3DSC[9]描述值。3DSC描述值的基本思想是计算特征点中的每个点的上下文信息，然后比较每个点是否相似，得到最近似的排列次序，最后找到两个点云之间对应的点。具体计算步骤如下：

步骤1：估计特征点的法向量，对于任意特征点pi和点qi构建点邻域的协方差矩阵。

(1)

(2)

式中，k分别为点pi和点qi为中心的最近点数目；p0、q0为质心。接下来对式(1)和式(2)进行特征值分解，得到特征向量和特征值。

M·vj=λj·vj，j∈{1,2,3}

(3)

记特征值λ1<λ2<λ3，则最小特征值λ1所对应的特征向量v1是点pi或点qi的法向量。

步骤2：构建以特征值的法向量方向为北极方向，分别以点pi和点qi为球心，Rj为半径的球区域。

(4)

式中，rmin、rmax为设置的最小半径和最大半径。

步骤3：计算每个区域的权重。

(5)

(6)

式中，V(j,k,l)为第j个半径，第k个方位角，第l个仰角方向的区域体积；ρi为对应局部点的密度。

步骤4：计算特征点的3DSC描述值。

fpi={ω1,ω2,…,ωk}

(7)

fqi={ω1,ω2,…,ωk}

(8)

则fpi、fqi为特征点的3DSC描述值。

2.3 错误匹配点对剔除

由式(7)、式(8)得到特征点的描述值去确定初始对应点对时，仍会造成一些误匹配的点对，因此需要剔除误匹配的点对，使得点云数据之间的变换关系更加精确。

根据2.2节可以找到初始的匹配点对的集合，将其记为L。

L={(pi,qi)|pi∈P1,qi∈Q1,i=1,2,…,n}

(9)

式中，P1、Q1分别为P、Q的特征点集；N为L中的点对数目。在L中随机取n个点对，分别为(p1,q1),(p2,q2),…,(pn,qn)，如果满足式(10)，则(pi,qi)属于正确的匹配点对的集合L1。

(10)

式中，dpn,qn为点pn、点qn的欧式距离；ω为设置大于0的阈值。上述几何一致性可以去除一些误匹配的点对，得到对应点对集合L1。接下来使用随机采样一致性(RANSAC)算法[10]进一步精确点对。具体算法流程如下：

步骤1：从提取的匹配点对中随机选取3个点对作为一个样本点集。

步骤2：将随机选取的3个点对作为正确的匹配点对，计算旋转矩阵和平移向量。

步骤3：使用步骤2计算出的旋转矩阵和平移向量，判断其余的匹配点对是否为正确的匹配：如果通过旋转平移其余匹配点之间的距离小于给定的阈值，则认为这一组点是正确的匹配点对，记作内点；否则记作外点。所有内点组成一组正确的对应点对。

步骤4：继续重复步骤1～步骤3的步骤，直到到达给定的循环最大次数，将内点最多的点集L2作为提取的正确匹配点对。

2.4 三维点云初始配准

根据点集L2中源点云P和目标点云Q的对应关系，计算式(11)和式(12)得到对应的质心pc、qc。

(11)

(12)

式中，n为邻域点的数量；pi和qi为对应点。

接下来根据式(13)计算协方差矩阵E。

(13)

对矩阵E进行SVD奇异分解：

E=UΛVT

(14)

式中，U、V为3×3的正交矩阵；Λ为协方差矩阵E的特征值组成的对角矩阵，根据U、VT得到旋转矩阵R和平移矩阵T。

R=VUT

(15)

T=qc-Rpc

(16)

根据求出的旋转矩阵R和平移矩阵T，得到初始配准后的源点云P′。

P′=RP+T

(17)

三维点云初始配准结果，如图10所示。可以看出初始配准后，源点云与目标点云的位置仍存在偏差。

(a) 初始位置 (b) 初始配准结果

3 三维点云精配准算法

3.1 GICP算法

GICP算法是ICP算法的改进，主要目的在于找到经过初始配准后的源点云P′与目标点云Q之间的旋转矩阵和平移向量，使得目标函数最小。为了提高点云配准中鲁棒性，该算法在构造误差函数时引入一个高斯概率模型，利用点云邻域集合的协方差矩阵构造误差函数，其他部分保持不变，以降低算法的复杂度和保持速度。

(18)

(19)

(20)

(21)

所以，GICP算法的误差函数为：

(22)

3.2 三维点云精配准

步骤1：将初始配准后的源点云数据P′和目标点云数据Q进行配准。

步骤3：利用SVD奇异分解求取旋转矩阵R和平移向量T，更新源点云数据P′′=RP′+T，然后计算目标函数式(22)使其最小，即对应点之间的均方误差最小。

步骤4：如果计算的误差函数最小值大于给定的阈值，将返回步骤2；如果低于给定的阈值或者迭代次数大于给定的最大迭代次数，则停止计算。

经过精配准后的三维点云配准结果，如图11所示。可以看出经过精配准后，源点云与目标点云已经完全重合。

(a) 初始配准结果 (b) 精配准结果

4 三维点云配准实验结果分析

首先，利用光栅扫描仪获取工业上轴承盖的点云数据原图，对不同角度的轴承盖点云数据，进行配准实验。采用配准精度(RMSE)评判点云的配准精度，RMSE表示两片点云在空间中距离的接近程度，其定义为：

(23)

4.1 轮廓点提取实验结果分析

为验证本文所提出的提取轮廓点的方法在轴承盖点云配准方面的优越性，将从两个方面进行实验，分别为：

(1)设置不同的阈值提取轮廓点，进行初始配准实验，结果如图12和图13所示。

图12 不同阈值下轮廓特征点数目与配准时间比较 图13 不同阈值下配准精度比较

(2)选取合适的阈值后，将提取出的轮廓点与经典的特征点提取算法ISS、HARRIS、以及SIFT算法进行初始配准实验，将采用SAC-IA算法进行初始配准的结果进行对比分析，统计结果如图14所示。

图14 不同特征点提取算法初始配准结果精度比较/mm

根据图12和图13可以看出阈值的大小决定提取的轮廓点的数目，阈值越大，轮廓点越少，轮廓细节不明显。反之，则获得的轮廓点多，轮廓细节也就越多。但提取出的轮廓点太多，会使配准误差较大，配准时间很长。提取出的轮廓点少，即使配准时间短，但配准误差很大，因此，综合配准时间和配准精度因素，本文的配准实验中，提取的轮廓特征点阈值为0.79。轮廓特征点如图7和图9所示。

从图14可以看出，根据折线和数值可以发现利用ISS算法提取轴承盖的特征点进行初始配准的均方根误差最大。其次，是利用SIFT算法初始配准的均方根误差均值为1.172 mm，最后，利用HARRIS算法进行初始配准的均方根误差均值为0.92 mm。利用本文算法提出的将提取的轮廓作为特征点的方法，进行初始配准时，均方根误差均值为0.90 mm。因此，本文提出的提取特征点的方法是可行的，配准结果良好。

4.2 本文配准实验结果分析

为了验证本文算法的有效性，将本文算法与SAC-IA+ICP[11]算法、NDT+ICP[12]算法、SAC-IA+ NDT[7]算法进行对比分析。最终点云配准误差结果如图15所示，最终点云配准所需时间如图16所示，实验配准结果如图17所示。

图15 不同配准算法配准精度比较

图16 不同配准算法配准时间比较

图17 本文算法与不同算法配准结果

可以看出实验1、2、3的原始点云数据中，待配准的两片轴承盖点云数据的重叠程度均较低，针对实验1、2、3中提取出的轮廓点不同的情况时，观察图15和图16，SAC-IA+ICP算法进行配准实验时，配准误差较大，配准时间较长；NDT+ICP算法进行配准实验时，虽然配准时间较短，但仍没有改善配准误差；SAC-IA+NDT算法进行配准实验时，配准时间很长，同时配准误差大；本文算法的配准结果中看，两片点云完全匹配到一起，RMSE值达到毫米级，同时根据数值计算出配准误差与其他算法相比至少减少50%，配准时间与其他算法相比提升至少50%。针对实验4、5中提取出的轮廓点相同的情况时，观察图15和图16，SAC-IA+ICP算法进行配准实验时，配准误差与实验1、2、3相比有所减少，但误差仍较大，配准时间与实验1、2、3相比增加10 s左右；NDT+ICP算法进行配准实验时，配准误差与实验1、2、3相比有所减少，但配准时间与实验1、2、3相比增加5倍甚至需要更多的时间；SAC-IA+NDT算法进行配准实验时，配准误差与实验1、2、3相比有所减少，但配准所需要的时间是最多的；本文算法的配准结果中，两片待配准的点云已经完全匹配到一起，同时配准误差与其他三种算法相比是最小的，配准时间与其他三种算法相比至少提高2倍。

总体而言，相比于其他三种算法，本文算法在配准效果及配准时间上均有优势，对于重叠程度较低的点云数据也能得到很好的配准效果。

5 结论

对于三维重建中的点云配准问题，提出一种基于轮廓点作为特征点进行点云配准的方法，该方法可以减少点云表面变化不明显的点，且根据角度阈值提取出的轮廓点在多个点云数据中有较好的稳定性。设计了一种基于轮廓点的3DSC特征匹配的点云初始配准方法，并将初始配准的结果用GICP算法进行精确配准，实验结果表明本文方法的有效性，同时可以解决对较低重叠率点云数据的配准问题，配准精度与效率较好，能应用到点云配准中，因此，本文方法可以为接下来的三维重建提供较好的初值。