基于特征点匹配的点云配准方法研究

欧 鑫, 高 飞, 崔 浩, 叶周润, 汤 毅

(合肥工业大学 土木与水利工程学院,安徽 合肥 230009)

三维激光扫描技术是一种在不接触被测物体的情况下就可以得到物体表面的三维坐标信息以及反射信息的技术,而获得的数据统称为点云数据。该技术被广泛应用于机器人识别、自动导航、文物保护等领域[1]。

在点云数据的采集中,由于物体的大小以及表面问题,而不能一次性获取被测物体的全部点云数据,需要进行多个测站数据的采集。为了得到完整的点云数据模型,必须对各测站点云进行拼接,即将不同坐标系下的点云数据通过旋转平移到同一坐标系中。

最为经典的配准方法是迭代最近点(iterative closest point,ICP)算法[2],有不少学者对传统ICP算法进行了改进[3],但该算法在没有良好的初始位置时,容易陷入局部最优,因此现在的算法大多数先通过粗配准获得良好的初始位置,再使用ICP算法进行精配准[4-5]。常用的粗配准算法一般为基于特征描述的配准算法。常见的特征描述算子有快速点特征直方图(fast point feature histogram,FPFH)[6]、归一化对齐特征(normal aligned rodial features,NARF)[7]、局部特征直方图(local signature feature histagram,LSFH)[8]等。基于特征描述的配准算法不太适用于稠密的点云,这是由于计算每个点的特征描述会极大影响点云配准的效率[9]。本文进一步提出了特征点与特征描述相结合的特征匹配算法,只需计算特征点的特征描述,再对其进行点对配对,最后计算初始矩阵。

1 点云粗配准

为了给ICP算法求得一个良好的变换矩阵,本文使用了基于特征点配对的粗配准方法,具体流程如下:首先采用尺度不变特征变换(scale-invariant feature transform,SIFT)算法[10]以及3DHarris算法[11]对点云进行特征点提取,计算FPFH特征,再基于FPFH特征找寻点对关系,使用随机采样一致性(random sample consensus,RANSAC)算法进行错误点对的剔除,最后使用奇异值分解法(singular value decomposition,SVD)求得变换矩阵,完成粗配准。

1.1 3DSift算法原理

(1) 建立点云的尺度空间。在点云的三维空间中,通过体素网格的方式进行点云体素化,设置体素网格的大小,计算体素网格包含点云的重心,再用各个重心替代每个体素网格内所包括的点云,构成新点集,该步骤用公式表述为:

(1)

其中:Ii(x,y,z,θ)为第i个体素网格内包含点云的重心坐标;pq为第i个体素网格内包含点云中第q个点的三维坐标;n为第i个体素网格中点的数目。由Ii(x,y,z,θ)构成的点集则是在体素网格大小为∂下进行降采样后的原点云。

(2) 建立点云高斯差分金字塔[12]。设金字塔共有n组,每组有S层,则组内第s层的尺度为:

θs=θ02s/S,s∈{0,…,S+2}

(2)

其中:θ0为点云的基准尺度;θs为点云金字塔组内第s层的尺度。

通过计算相邻尺度下采样点的高斯响应值R,可以进一步计算其高斯差分值RDOG。对采样点及距离采样点3σ范围内的点进行高斯曲率加权,高斯响应值R和高斯差分值RDOG的计算公式表示为:

(3)

(4)

RDOG=R-R1

(5)

其中:ρi为采样点第i个近邻点的曲率;ωi为加权数;μ为采样点到相邻点的间距;σ为采样点所在尺度空间的大小;R1为上一尺度的高斯响应值。

(3) 检测特征点。若该点在RDOG尺度空间本层内的RDOG值为最值,以及与相邻上下2个尺度层内的RDOG对比仍是最值时,则认为该点为特征点。

1.2 3DHarris提取特征点

在三维点云空间中,选取点O作为中心,再以k为半径来建立空间区域,将区域p内所有的点进行主成分分析(principal component analysis,PCA),根据最小二乘法原理生成一个二次曲面f(x,y),其展开式为:

(6)

计算f(x,y)的x和y的偏导,近似点云点强度I,进而解出矩阵M中各个元素的值如下:

(7)

(8)

(9)

fx(x,y)fy(x,y)dxdy

(10)

w(x,y)是5×5窗口权函数(根据实际设置),(8)～(10)式积分后可得A、B、C值,即

(11)

(12)

C=O4O5+2O1O2+2O2O3

(13)

最后再计算Harris响应值R:

R=detM-k(traceM)2

(14)

将计算的R与设定的检测值Rq对比,当R>Rq时,则该点为特征点。

1.3 RANSAC算法

RANSAC算法常被用于提取正确匹配点对和剔除错误匹配点对,该算法具有良好的抗噪性[13]。利用对应关系估计对错误匹配的剔除进行预处理,RANSAC算法效率更高。具体流程如下。

首先使用合适的转换模型使点对之间进行拟合。点对关系需要满足:

(15)

其中:Ri{i=1,2,3…,9}为旋转参数;X0、Y0、Z0为平移参数;(X2,Y2,Z2)为源点云;(X1,Y1,Z1)为目标点云。

迭代过程中,需要计算(15)式中的旋转平移参数,为此需要选择至少4组点对进行求解。为了有效选取点对,将对应关系估计用做点对筛选,从而提升RANSAC剔除点对的效率。记源点云P={p1,p2,…,pn}和目标点云Q={q1,q2,…,qm}的特征分别为{pf1,pf2,…,pfn}和{qf1,qf2,…,qfm}。对于源点云的任一特征pfi(i

(16)

则判定pi和qj是一对正确的点对(pi,qj)。其中,sn为特征维数,可取值为33或125,C为所设常数。获得的点对可以用来估算转换参数R和T。将剩余点对(pi,qj),计算其距离d=‖Rpi+T-qj‖,根据距离d与所设阈值的比对,判定该点对(pi,qj)是内点或者外点。每次迭代,统计使用该组参数获得的内点数目n,直至达到所设迭代次数。当该组转换参数所得内点数数目n最大时,则其为最优参数,所获得的n对内点可以通过1.4节介绍的SVD算法计算旋转平移矩阵完成粗配准。

1.4 SVD算法

SVD算法的基本思想是将一个复杂的矩阵可以拆分为几个简单矩阵来表示。正是基于这种思想算法具有良好的抗噪性和稳定性[14]。该思想用公式表示为:

U=XZYT

(17)

其中:U为M×N的矩阵;X为M×M的矩阵,称X矩阵内的向量为左奇异向量,且向量相互正交;Z为M×N的矩阵,其构成为对角线上元素为奇异值,其余数值为0;YT为N×N的矩阵,称矩阵YT内的向量为右奇异向量,其内部向量也相互正交。

假设2个点云分别为P={pi,i=1,2,3,…,np}和Q={qj,j=1,2,3,…,nq},其中np、nq分别代表2个点云的总点数。点pi和qj的关系可以表示为:

qj=Rpi+T

(18)

其中:R为旋转矩阵;T为平移矩阵。相应的目标函数可表示为:

(19)

然后对R进行SVD分解可得:

R=XZYT

(20)

(20)式可以更有效率地求取旋转矩阵,再通过(18)式求得平移矩阵。

2 点云精配准

粗配准后可以获得一个初始矩阵,使得2个点云拟合到一个比较良好的位置,但一般还不完全重合,此时就需要对点云进行精配准。

ICP算法基本原理为分别在源点云P={pi,i=1,2,3,…,n}和目标点云Q={qi,i=1,2,3,…,n}中,对于任意点对(pi,qi),设误差函数为:

(21)

其中,n为邻近点个数。

通过迭代计算,直到θ小于设定的阈值min,也就是通过不断求解2个点云间的变换关系,更新2个点云位置,直到收敛于设定阈值,即找出最优转换矩阵R和T。具体步骤为:

(1) 在目标点云P中取点pi∈P;

(2) 源点云Q中取点qi∈Q,其两点关系满足‖qi-pi‖2=min;

(3) 使用该点计算相应的转换矩阵R和T;

(6) 如果误差函数θ小于所设阈值min或者迭代次数大于预设的迭代次数,那么终止运算,输出最终矩阵,否则返回步骤(2),直到满足给定条件为止。

这样经过多次迭代,点云P就会越来越接近Q,最终实现重合,这是迭代最近点ICP算法的基本思想。

3 实例分析

实验采用斯坦福大学提供Dragon以及Armadillo-scans点云数据进行仿真实验。Dragon选取了dragonStandRight-0和dragonUpRight-0,点数目分别为41 841、42 641个;Armadillo-scans选取了ArmadilloSide-105和ArmadilloOnHeadMultiple-0,点数目分别为29 715、32 385个。

实验在VS 2017、Win 10系统、内存16 GiB下进行。两点云位置如图1所示,图1中:绿色为源点云;红色为目标点云。实验过程为通过粗配准获得初始矩阵后,使用ICP算法不断迭代计算变换矩阵,使得绿色点云向红色点云逐渐靠近,最终实现重合。

图1 点云初始位置

3.1 Armadillo点云配准结果

特征点匹配如图2所示(连线为对应点对)。

图2 Armadillo点云特征点点对匹配

经过粗配准以及精配准后所得配准结果如图3所示。

图3 Armadillo点云配准结果

3.2 Dragon点云配准结果

特征点匹配如图4所示(连线为对应点对)。

图4 Dragon点云特征点点对匹配

经过粗配准以及精配准后所得配准结果如图5所示。

图5 Dragon点云配准结果

3.3 FPFH与ICP结合算法配准结果

两点云直接使用FPFH与ICP结合算法的配准结果如图6所示。

图6 FPFH与ICP结合算法配准结果

从图6可以看出,2个模型中的2幅点云都不能很好地重合在一起,这是粗配准效果不好,所得初始矩阵并不能满足ICP算法要求,从而导致ICP算法进行求解时陷入局部最优[15]。配准数据对比见表1所列。

表1 不同算法配准结果比较

从图2～图6以及表1可以看出,基于特征点提取的配准算法比只基于特征描述的配准算法效果要好,因此本文提出的算法具有一定的可靠性。

再对比本文中使用的2种特征点提取方法,在Armadillo点云模型中,基于SIFT算法在配准误差以及配准时间上都优于基于Harris算法,图3中配准效果也比较好;在Dragon点云模型中,两者的配准误差差距不大,图5中两者配准效果基本相同,但在时间效率上,仍是基于SIFT的算法比较好。

4 结 论

本文针对在点云配准中使用FPFH与ICP结合的算法达不到配准精度的问题,提出了一种基于特征点匹配的点云配准算法,使用SIFT和3DHarris算子提取特征点,特征点集根据FPFH特征描述进行点对匹配,再使用RANSAC算法进行错误点对去除,使用SVD算法对剩余点对进行解算,完成粗配准,得到初始矩阵,最后使用传统ICP精配准,得到最终结果。实验表明,该算法在配准效果上优于FPFH与ICP结合算法,在基于SIFT算法和基于Harris算法两者的比较中,进一步得出使用SIFT算法进行特征点提取匹配,可以得到更好的初始矩阵,且在时间效率上要远优于Harris的结论。在真实场景中,面临数目更加庞大的点云,对算法效率的提升以及阈值的设置是今后研究的重要方向。