基于3DSIFT和BSHOT特征的点云配准方法

刘 雷,柏艳红,王 银,孙志毅

(太原科技大学电子信息工程学院,山西 太原 030024)

1 引 言

随着移动机器人技术快速发展,机器人被应用到各种复杂的环境,比如抢灾救险、配送物流、无人测绘等任务[1-2]。通常在这些环境下都没有预先建立好地图环境信息。而随着SLAM(simultaneous ocalization and mapping)技术的发展,为移动机器人在未知环境中的定位与构图提供了较好的解决方案[3-6]。依靠高精度激光雷达及多传感器融合的技术也越来越成熟,激光点云的配准技术在SLAM技术框架中起着十分重要的作用[7]。研究具有快速性、鲁棒性的配准方法也有着重要的意义。

目前应用最广且最经典的点云配准算法是迭代最近点(ICP)方法,但在两个点云的初始位置差别较大、相邻重复率较低的情况下达不到很好的配准效果[8]。于是后人开始大量研究如何利用初配准提供较好的点云初始位置。以特征描述为代表的点特征直方图(PFH)方法、以及改进的快速点特征直方图(FPFH)方法。文献[9]提出基于法线特征约束的点云精确配准方法,采用局部表面拟合方法进行法线估计,并计算其快速点特征直方图。文献[10]、[11]提出了一种基于内部形态描述子(ISS)及方向直方图描述子(SHOT)特征的点云配准算法,采用ISS算法提取特征点,并用SHOT对特征点进行描述。文献[12]提出了一种基于二维图像特征的点云配准方法,再采用SURF算法提取点云深度图的特征,并求解其匹配像素点对。

基于特征描述的点云配准算法思想是构建点云局部邻域描述子,然后通过建立基于描述子的匹配对,最后通过匹配对估计变换矩阵。针对当前基于特征描述的配准算法存在的问题,本文提出了一种结合三维尺度不变特征变换关键点和二进制方向直方图描述子匹配的配准方法。该方法首先利用差分高斯模型检测尺度空间的SIFT关键点,其次在关键点的邻域构建局部坐标系,将查询点处法线和邻域点法线夹角特征统计入直方图,本文将特征向量转化为二进制的描述符。然后利用随机采样一致性算法(RANSAC)去除误匹配的点对,初步估计点云配准的初始变换矩阵,最后在精配准上利用ICP算法估计最优的变换矩阵。

2 关键点提取算法

局部特征描述SIFT(Scale Invariant Feature Transform)被广泛应用于二维图像的物体辨识上,该局部特征对旋转、尺度缩放、亮度变化保持不变性,对视角变化、仿射变换、噪声也保持一定程度的稳定性。将2D SIFT算法扩展到三维空间形成三维尺度不变特征描述符。首先将三维高斯核函数与点云模型进行卷积,得到该模型的尺度空间,计算公式如下。

(1)

L(x,y,z,kσ)=G(x,y,z,kσ)⊗P(x,y,z)

(2)

式中,尺度空间为L(x,y,z,kσ);高斯核函数为G(x,y,z,kσ);点云中模型表示为P(x,y,z);σ为空间尺度参数;k为尺度大小调整参数。其次计算相邻尺度层的高斯差分模型,以保证原始点云具有与之相关的尺度不变性。定义DoG算子计算公式如下:

DoGi=Li(x,y,z,kσ)-Li-1(x,y,z,kσ)

(3)

式中,i∈(0,S+2),S为高斯金字塔每组的层数。最后在DoG函数空间上寻找极值点,该极值点是所有高斯差分模型中的极大值点或极小值点。如图1所示,中间检测点与同尺度的26个近邻点比较,然后同上下相邻尺度对应的27×2个点比较,只有该检测点大于或者小于80个近邻点时,该点被检测为SIFT关键点。

(a)σ/k (b)σ (c)kυ

3 关键点描述算法

为了使描述符具有旋转不变性,加上SIFT原有的局部特征描述方法计算过于复杂,为了降低特征描述符匹配的计算能力和时间。本文采用二进制方向直方图描述子BSHOT对关键点邻域特征进行描述。首先利用邻域点云建立局部坐标系,计算邻域的协方差矩阵M,计算公式如下。

(4)

图2 BSHOT特征空间划分

本文二进制描述符将高维直方图特征向量转化为352位的二进制数表示,减少了描述子的存储空间,同时计算复杂度下降。考虑到一个SHOT描述符Si,其中i={0,1,2,…,351},并且每个Si由4个字节组成。我们假设BSHOT描述符Bi,其中i={0,1,2,…,351},Bi为一个二进制数。将连续的4个Si,{S0,S1,S2,S3}编码为4位二进制数,对应BSHOT描述符{B0,B1,B2,B3}。

设S=S0+S1+S2+S3,我们先检查一个值Si,Si∈{S0,S1,S2,S3}是否大于S的90 %。如果S1的值大于S的90 %,则编码{B0,B1,B2,B3}为{0,1,0,0}。然后在检查两个值的和是否大于S的90 %,如果S0+S1大于S的90 %,则编码{B0,B1,B2,B3}为{1,1,0,0}。以此类推,通过迭代将352维的SHOT描述符编码为BSHOT描述符。BSHOT描述符并不具有唯一性,但用来估计粗略的对应关系速度更快,同时方便修改比值,在有噪声的环境下鲁棒性更高。

4 对应点匹配

待配准的两片点云经过下采样、SIFT关键点提取及SHOT描述子计算后得到每个特征点的特征向量。一般来说,不同点云中同一个点的特征描述子应该近似相同,传统的算法通常利用两个特征向量间的欧氏距离作为衡量标准。本文将SHOT描述符转化为二进制描述符BSHOT,利用汉明距离进行匹配。汉明距离近似则为同一个点,但是由于点云拓扑结构、稀疏性、噪声的影响,难免会产生错误的匹配对,直接影响配准的结果。本文采用随机采样一致性(RANSAC)去除点云中错误的匹配对。首先RANSAC假设一个含有3个“内点”以上的模型作为初始状态。假设“内点”在n个数据中的占比为t:

(5)

其中,ninliners为“内点”,noutliners为“外点”,在k次迭代的情况下,(1-t)k计算k次迭代计算模型都至少采样到一个外点的概率,那么能正确采样到内点的概率为P=1-(1-t)k。P接近1时表示此时模型已经具有较多的内点,迭代完成后估计出最优的模型参数。RANSAC是通过反复选择数据集去估计出模型,一直迭代到估计出认为比较好的模型。

5 点云的配准过程

点云配准的一般过程分为粗配准、精配准两个阶段。粗配准是在点云相对位姿完全未知的情况下对点云进行配准,可以为精配准提供良好的初始值。精配准的目的是在粗配准的基础上让点云之间的空间位置差别最小化。

本文采样特征描述子匹配的点云配准方法,首先对输入点云进行下采样,得到较为稀疏的点云,然后利用k近邻搜索查询点附近的邻域空间来提取SIFT关键点,其次在每个关键点处构建BSHOT描述子,最后通过汉明距离建立点云匹配对,RANSAC利用点云匹配对估计出初始的变换矩阵。为了进一步提高配准的精度,利用粗配准提供的初始位置,本文采用ICP估计两个点云的最优的变换关系。本文配准过程如图3所示。

图3 本文的配准算法

6 实验结果与分析

本文的实验数据采用的是斯坦福大学不同视角下的bunny数据和dragon数据,作为点云配准的源与目标点云。实验平台为Intel(R)Core(TM)i7-7500U CPU @2.7GHz处理器,8G运行内存,操作系统为Windows10 64位操作系统,编译环境为cmake-gui和Visual Studio 2017,结合第三方点云处理库PCL1.81。

由于bunny原始数据和dragon原始数据均为高密度点云数据,数据点数高达4万。本文采用体素滤波器进行下采样,体素采样半径设置为0.001 m。在采样后数据中分别提取SIFT关键点,然后在每个关键点处计算BSHOT描述子。将BSHOT描述子存储为一个352位二进制的数。两个相同描述子的汉明距离应该近似相同,在源和目标点云上提取出对应的点,结果如图4所示。

图4 对应点匹配结果

对bunny00、bunny45数据和dragon00、dragon24数据进行粗配准,RANSAC通过对应点的关系估计出较为准确的变换矩阵,并与文献[11]的粗配准结果对比,不同算法粗配准结果如图5所示,其中图5(a)、(d)为配准前原始点云,图5(b)、(e)为文献[11]粗配准结果，图5(c)、(f)为本文粗配准结果,本文配准效果通过计算MSE(均方误差)来衡量,该结果反映两个点云的接近程度。由图5和表1分析可知,文献[11]的粗配准方法最小均方误差达到11.91 μm,本文粗配准最小均方误差达到8.08 μm。本文方法在粗配准效率和配准精度上有所提高。

完成粗配准后,利用图5的粗配准结果进行精配准。为了确保粗配准算法的可比性,文献[11]和本文方法精配准均采用ICP方法,ICP方法迭代次数均为20。最终精配准结果误差和运行时间如表1所示,精配准效果如图6所示,其中图6(a)、(d)为ICP配准结果,图6(b)、(e)为文献[11]精配准结果,图6(c)、(f)为本文精配准结果。由图6和表1分析可知,本文配准方法为3种方法里面用时最少,和文献[11]的方法对比,时间效率平均提升了67.2 %。配准精度上略低于文献[11]方法,但较传统ICP方法,配准精度有所提高。

图5 不同方法粗配准结果

图6 不同方法精配准结果

表1 不同算法配准效果评估

7 结 语

本文受二维图像中检测尺度不变特征关键点SIFT思路的启发,提出了结合三维空间的尺度不变特征关键点和二进制方向直方图描述子特征匹配的配准方法。该方法对空间中两个重叠率较低的点云完成快速精确配准。在实际应用中,有较高的使用价值。在如今多传感器数据融合SLAM的大趋势下,可以利用其他传感器为点云配准算法提供初始参数,以进一步提高配准效率。