基于特征点的ICP点云配准算法

单丽杰,岳建平,钱 炜

(河海大学地球科学与工程学院,江苏 南京 211100)

点云配准在计算机视觉、三维重建、逆向工程等众多领域具有重要的研究意义。三维激光扫描设备在扫描时,由于扫描角度、物体遮挡等原因,在扫描过程中无法一次性得到需要的点云数据,所以,需要将多个视角的扫描数据进行配准,实质是将不同空间坐标基准下的待配准点云转换到一个空间坐标基准下。点云配准过程通常分为粗配准和精配准,粗配准将2个初始位置偏差较大的点云配准到大致正确的位置上,为精配准提供较好的初始位置姿态。

目前,点云配准算法中,Besl等[1]提出的最近点迭代算法(ICP,iterative closest point)应用最为广泛,但是该算法在初始位置相差太大时容易陷入局部收敛。为了提高点云配准的精度和效率,探索更优化的配准算法一直是许多学者研究的重点,如Fischler等[2]将随机抽样一致性算法用于初始配准,处理含有异常值和误差值的待配准点云,该方法具有较好的鲁棒性,但是算法的时间复杂度非常高;Chen等[3]在point-to-point的基础上提出了point-to-plane搜索最近点的配准方法,利用点的切平面逼近点云,通过点到切平面的距离寻找对应点对,但该方法在时间效率上没有很大的改进;刘剑等[4]提出了一种利用快速点特征直方图特征描述与Delaunay三角剖分相结合的三维点云配准方法,简化了特征提取的复杂度和特征点匹配的搜索范围;李慧慧等[5]提出了一种利用主成分分析法矫正主轴方向的改进ICP配准算法,通过两次搜索最近距离获取各点的概率值,嵌入到最小二乘函数中,达到对重叠点云配准的目的;陈学伟等[6]提出了一种基于特征点的采样一致性初始配准算法(SAC-IA),实现了两点云之间的初始变换,并利用方向向量阈值去除错误点对,为精配准提供了较好的初始位置姿态;勾会杰等[7]对点云进行格网化,根据平均模型和最邻近原则进行配准,提高了初始配准的精度;杨飚等[8]提出一种基于正态分布变换(NDT)和ICP的三步式点云快速配准方法,采用NDT算法进行粗配准,在此基础上利用ICP算法精配准,并与几种经典配准算法进行了对比,新方法减少了配准算法的计算量,提高了配准速度,同时降低了计算量与点云距离和数量的相关度,可以适用于远距离点云和大数据量点云的配准。

针对ICP算法在点云配准过程中出现的问题,提出一种基于特征点的ICP配准算法。在初始配准中,利用特征点匹配使2个待配准点云的位置大致重合,并使用K-D tree搜索最近点,提高算法配准效率。

1 经典ICP点云配准算法

点云配准可以分为粗配准和精配准,粗配准使2个点云的位置大致接近,为精配准提供较好的位置和变换矩阵初值,精配准在粗配准的基础上,进一步优化得到更精确的变换。

ICP配准算法的实质是在最小二乘的基础上求解矩阵的旋转平移参数R和T,计算对应点之间欧氏距离,通过不断迭代使其达到最小[9]:

(1)

经典ICP配准算法具体步骤如下:

(1) 在源点云P中选取子集p0,p0∈P;

(3) 计算旋转矩阵R和平移向量T,使式(1)最小;根据计算得到的变换矩阵,更新源点云的子集p′0;

2 基于特征点的ICP点云配准算法

2.1 初始配准

(2)

(3)

图1 以Pq为中心的FPFH邻域影响范围Fig.1 The influence range of FPFH neighborhoodcentered on point Pq

利用上述方法,将源点云和目标点云中提取的特征点集分别记为P′和Q′,通过矩阵变换得到初始变换矩阵,将两个点云调整到一个坐标系中,缩小配准点云之间的距离,实现初始配准。

2.2 精配准

通过初始配准后,两片点云处在大致重合的位置上,但是精度还达不到要求,因此,需要通过精配准提高配准精度。

在经典ICP配准步骤(2)中,使用K-D tree算法[11-12]搜索对应点子集,提高点云的搜索速度。搜索时按照坐标轴顺序依次搜索,先按X轴搜索,根据点与点之间的距离大小进行排序,以距离的平均值作为根节点将空间分为两部分,然后,用同样的方法再对Y轴和Z轴搜索,直至搜索完所有点云数据。根据刚性距离约束条件,运用四元数法或SVD分解法求解旋转矩阵R和平移向量T,直到满足迭代条件。

基于特征点的ICP配准算法,具体步骤为:

(1) 利用点云局部法向量,在源点云P中提取特征点集p′,p′∈P;

(3) 运用四元数法或SVD分解法,求解旋转矩阵R和平移向量T,使式(1)最小;根据计算得到的变换矩阵,更新特征点集p″;

(4) 根据刚性距离约束条件,判断迭代是否终止,当d小于设置的阈值或者达到了设置的迭代次数,则算法停止;否则,返回步骤(2)继续迭代。

3 实例分析

实验数据为斯坦福大学提供的2个视角(0°和24°)的Dragon点云,2个点云个数分别为41 841、34 836。基于特征点的ICP配准算法,选取的特征点集、特征点初始配准及最终配准结果如图2所示。

图2 Dragon点云配准效果Fig.2 Point cloud registration effect of Dragon

为了进一步验证基于特征点ICP配准算法的可行性,选取了斯坦福大学提供的Bunny 2个视角(0°和45°)数据,个数分别为40 256、40 097,选取Armadillo 2个视角(0°和30°)数据,个数分别为32 385、29 885,配准效果见图3。并对Dragon、Bunny和 Armadillo数据的配准结果,从算法耗时和误差上与经典ICP配准算法进行了对比,对比结果见表1。

图3 Bunny、Armadillo点云配准效果Fig.3 Point cloud registration effect of Bunny and Armadillo

表1 配准耗时、误差对比

由表1可见,利用特征点进行ICP配准可以明显减小配准误差,且缩短了配准时间。从图2可以看出,使用经典ICP算法进行配准后两片点云的位置大致接近,但误差较大;而通过特征点的ICP配准,解决了ICP配准算法因初始位置而陷入局部收敛的问题,具有更高的配准精度和时间效率。

4 结论

由于待配准点云初始位置差距较大,直接使用ICP算法进行配准容易陷入局部收敛,误差较大。通过提取点云局部邻域内的特征点,建立特征直方图进行初始匹配,可以使两片待配准点云的位置大致接近,为精配准提供良好的位置基准,提高了点云数据配准精度。同时,利用K-D tree搜索算法查找对应点对,减少了对应点对搜索的时间,提高了算法配准的效率。