基于SIFT特征点结合ICP的点云配准方法

荆 路,武 斌,方锡禄

(天津城建大学计算机与信息工程学院,天津 300384)

1 引 言

近年来随着激光技术的快速发展,激光雷达正不断应用到各种领域,例如智能驾驶、电力巡线、三维重建以及隧道变形监测等[1-4]。然而,当进行实际测量时,由于受到测量环境和仪器设备等因素的影响,采集到的每帧点云数据仅仅包含所测物体的部分点云信息。因此,为了获取所测物体完整的点云数据,往往需要对物体进行多站点多视角测量,并通过配准把不同视角测得的点云数据变换到同一坐标系下。

点云配准通常分为两步:初始配准和精配准。初始配准中基于特征的配准算法是目前主要的研究方向,如纹理[5]和角点[6]等。在精配准阶段,Besl等[7]提出的ICP(iterative closest point)算法是目前最经典的算法,但是此算法对点云初始位置要求高,否则容易陷入局部最优,而且存在迭代速度慢、耗时长的问题[8]。为了解决ICP算法存在的问题,许多学者对该算法作了改进和创新,而且也提出了一些新的算法。Yang等[9]提出Scale-ICP算法,与ICP算法相比,此算法虽然在配准精度和迭代速度方面都有一定的改进,但对迭代过程依赖性较强,导致算法收敛缓慢。文献[10]提出一种利用K-D树对ICP配准算法进行优化的方法,但是当配准海量点云数据时,此方法的配准效率无法完全满足应用要求,还需不断改善搜索策略。赵明富[11]融合了采样一致性算法与ICP算法,虽然在一定程度上解决了ICP算法依赖初值的问题,但当点云数据量较大时,配准效率较低。文献[12]提出一种依据高斯混合模型来拟合点云模型的方法,虽然保证了配准精度,但同时牺牲了配准效率。王畅等[13]提出一种依据点云结构特征进行配准的方法,虽然该算法使配准速度有一定的提高,但是当点云数据点不完整或者交叉数据点不够时,可能会造成配准结果失效。

基于以上研究现状,针对ICP算法对点云初始位置依赖性强且迭代速度慢的问题,本文提出一种基于SIFT(scale invariant feature transform)特征点结合ICP的点云配准方法。该方法依据SIFT特征检测算法以实现初始配准时特征点对的匹配,然后在初始配准的基础上再使用ICP算法进行精配准。

2 配准流程

本文配准方法的流程如图1所示。首先利用SIFT算法提取待配准和目标点云的特征点；接着计算特征点的FPFH(fast point feature histogram)特征；然后依据特征点的FPFH特征利用SAC-IA(sample consensus intial alignment)算法求出变换矩阵,从而完成初始配准；最后在初始配准的基础上利用ICP算法对初始配准的结果进一步优化,完成精配准。

图1 点云配准流程

3 相关算法原理

3.1 初始配准

3.1.1 SIFT特征检测算法

SIFT算法是Lowe D G在1999年提出的一种局部特征描述算法,并在2004年对其进行了完善[14],该特征对亮度变化、噪声、旋转和平移等因素保持较好的不变性。SIFT算法步骤简介如下:

(1)生成尺度空间。图像的尺度空间定义为:

L(x,y,σ)=G(x,y,σ)⊗I(x,y)

(1)

其中,G(x,y,σ)是尺度可变高斯函数：

(2)

式中,σ表示尺度空间因子,反应了图像的模糊程度;(x,y)表示像素的坐标。

(2)在尺度空间上检测极值点。构造高斯差分(DoG,Difference of Guassian)函数,即：

D(x,y,σ)=[G(x,y,kσ)-G(x,y,σ)]⊗I(x,y)

=L(x,y,kσ)-L(x,y,σ)

(3)

其中,k表示两个相邻高斯尺度空间的比例因子,通过该函数可以有效检测尺度空间中的特征点。当检测极值点时,把尺度空间中的每个像素点与26个像素点作比较,这26个像素点分别为上下相邻尺度的18个和同尺度相邻的8个,然后判断该像素点的DoG算子在这26个领域中是否取得极小值或者极大值,若取得极小值或者极大值那么该点即为特征点。

(3)对极值点进行筛选。通过曲线拟合DoG函数以剔除不符合要求的点,从而获得稳定的极值点,即特征点。

(4)求取特征点的主方向。计算特征点邻域内各个像素点的梯度,并把10°作为一个单位,采用直方图统计梯度方向,定义特征点的主方向为直方图中最大值对应的方向。

(5)建立一个包函尺度、位置和方向信息的描述符,通过该描述符对特征点进行描述。

3.1.2 点云FPFH特征描述

FPFH算法是一种基于局部特征描述的算法,它是通过对点特征直方图(Point Feature Histograms,PFH)[15]改进得到的,关于PFH的详细介绍可参考文献[15]。相比较PFH而言,FPFH由于没有计算全互联Mq的所有邻近点,因而使得算法的计算量降低,把复杂度由Ο(k2)降低到Ο(k),FPFH的计算原理如图2所示。

图2 FPFH计算原理

计算FPFH特征的步骤如下:

(1)计算出每个待计算点Mq与其所有领域点之间的相对关系,从而建立简化的点特征直方图(Simplified Point Feature Histogram,SPFH),并记为S(Mq)。

(2)根据上述(1)步计算得到的k个领域点的SPFH特征计算FPFH特征,记为F(Mq),表示为:

(4)

3.1.3 SAC-IA算法

SAC-IA算法步骤如下:

(1)对采样点进行选取:依据预先设置的距离阈值d从待配准点云M中选取采样点,要使得d小于采样点两两间距,从而保证各采样点的FPFH特征均不相同。

(2)对采样点的对应点进行查找:依据采样点的FPFH特征,从目标点云N中查找与该特征相似的点,从而将其作为目标点云N中与待配准点云M中的采样点相对应的点。

(5)

其中,ml表示预先设定的值;li表示第i组对应点经过变换之后的距离差。最后为了使误差函数取得最小值,则需要从所有的变换中找出一组最优的变换,从而进行初始配准。

3.2 精配准

3.2.1 ICP算法

经过初始配准之后,缩小了点云之间的旋转和平移误差,使得源点云和目标点云具有了较好的初始位置,然后在初始配准的基础上采用ICP配准算法进行精配准,从而避免ICP算法对点云初始位置依赖的问题,进一步提高配准精度,使精配准后的结果达到预设的收敛条件。ICP算法步骤如下:

(1)从目标点云Q中搜索与源点云P中的点pi相应的最近点pi′,从而构成对应点对。

(2)根据对应点对,求出点云Q和P之间的变换关系R和T。

(3)更新源点云P,求出P′=Rpi+T。

(4)求出均方误差:

(5)当dm-dm+1小于预设的域值或者达到预设的迭代次数时,则迭代结束；反之重新迭代。

4 实 验

本文实验的硬件环境为Inter(R)Core(TM)i7-8750H CPU @2.20Hz处理器,8.00GB内存；系统环境为64位win10操作系统；软件环境为Visual Studio2013、开源点云库PCL1.8.0。首先采用的点云模型为斯坦福大学点云库的bunny点云模型。为了验证本文方法的有效性,分别与ICP算法和文献[11]方法进行对比分析,对bunny点云模型进行配准实验。同时,以欧式适合度评分作为配准误差评判指标,欧式适合度评分表示输出点云到最近目标点云对应点对的距离平方和,距离平方和越小说明说明重合度越好、配准精度越高,并把配准所用时间进行比较,以衡量配准的效率。

如图3所示为bunny初始点云,图4为利用SIFT算法提取bunny点云特征点的结果。

图3 bunny初始点云

图4 bunny点云SIFT特征点

如图5所示为bunny使用ICP算法迭代5次、10次、15次、20次时的配准结果。如图6所示为bunny使用文献[11]方法迭代5次、7次、10次时的配准结果。

图5 ICP算法配准bunny结果

图6 文献[11]方法配准bunny结果

如下图7所示为bunny使用本文方法迭代5次、7次、10次时的配准结果。

图7 本文方法配准bunny结果

如表1所示,为bunny配准误差和用时统计结果。

通过上述结果可以看出,在使用ICP算法配准情况下,当迭代次数较少时,点云模型的头部、尾部、脚掌及耳朵等多处部位出现了明显配准偏差,随着迭代次数的增加,虽然配准效果不断改善,但配准用时更长,配准效率明显下降。对比直接使用ICP算法,随着迭代次数的增加,本文方法的配准精度更高、配准用时更少。同时,与文献[11]方法相比,虽然本文方法的配准效率有所降低,但配准精度得到了提高。

表1 bunny配准统计结果

为了进一步分析本文方法的普适性,以采集的椅子点云数据进行上述实验。如图8所示为椅子初始点云,图9为利用SIFT算法提取椅子点云特征点的结果。

图8 椅子初始点云

图9 椅子点云SIFT特征点

如图10所示为椅子点云使用ICP算法迭代5次、10次、15次、20次时的配准结果。

图10 ICP算法配准椅子结果

如图11所示为椅子点云使用文献[11]方法迭代5次、7次、10次时的配准结果。

图11 文献[11]方法配准椅子结果

如图12所示为椅子点云使用本文方法迭代5次、7次、10次时的配准结果。

图12 本文方法配准椅子结果

如表2所示,为椅子点云配准误差和时间统计结果。

通过对椅子点云配准的结果可以得出,与ICP算法相比,本文方法在迭代次数较少时便取得了较高的配准精度,并且随着迭代次数的增加,配准效率相对更高、误差收敛得更快。同时与文献[11]方法相比,虽然降低了效率,但配准精度更高。

表2 椅子点云配准统计结果

5 结 语

由于ICP算法存在对点云初始位置依赖性强且迭代速度慢的问题,本文提出了一种基于SIFT特征点结合ICP的点云配准方法。对点云模型使用SIFT算法提取特征点,并计算出特征点的FPFH特征,依据该特征并利用SAC-IA算法完成初始配准,从而使两片点云具有一个较好的初始位置,最后再利用ICP算法对两片点云进行精配准以进一步优化配准结果。实验表明,该方法能够有效避免ICP算法依赖初始位置的问题,加快了迭代速度,提高了配准精度与效率。由于在三维重建过程中点云数据配准是十分关键的一步,配准的成功与否会对后续的重建结果造成直接影响,因此,本文的配准方法为后期点云模型重建提供了一定程度的参考。但是,需要注意的是,提取点云SIFT特征点时仍需消耗一定的时间,这是该方法日后需要优化的地方,同时,该方法中某些参数的阈值设置问题还需进一步优化,这些问题将在未来科研中继续改进。