改进的多分辨率点云自动配准算法

王 勇,黎 春,何养明,陈荟西

(重庆理工大学 计算机科学与工程学院,重庆 400054)E-mail:2351583604@qq.com

1 引 言

点云自动配准方法一般分为粗配准和精配准两步.粗配准方法包括标志点法、重心重合法、特征提取法等方法[1,2].标志点法需要人为贴上标志点,但人为因素会导致误差等问题,影响后续配准精度;重心重合法要将点云的两个中心重合在一起,适用于点云重叠度较高的情况;特征提取法一般不适用于物体特征不明显的点云配准.由于粗配准算法存在的上述缺陷以及点云的拓扑结构、稀疏程度、噪声等的存在[1],导致粗配准的精度很难满足人们的要求,因此,需要对粗配准结果进行精配准.

目前国内外最常用的精配准算法是由 Besl[3]等人和 Chen[4]等人分别提出的迭代最近点算法(Iterative Close Point,ICP),但该算法存在以下缺陷:当两片点云没有较好的初始位置时,易陷入局部最优;算法是对点云中的所有点进行处理,因此搜寻匹配点时间很长,且点云规模越大其效率越低.因此,众多国内外专家学者提出了一系列的优化算法.LI[5]引入动态调整因子进行ICP 配准,在不影响配准精度的前提下,提高了算法的配准效率.文献[6]提出利用局部深度信息、法线偏角和点云密度信息建立局部特征描述子,再根据该局部特征描述子的相关性完成配准,解决了点云覆盖率较低时的配准问题.文献[9]在经典ICP算法的基础上引入带边界的尺度因素和动态迭代因子,既解决了配准中尺度变换的问题,也提高了算法速度,但没有考虑到旋转角度、噪声等因素.文献[10]提出一种使用深度神经网络自动编码器进行3D点云配准;该算法首先对点云分为超点集,并将超点集投影成深度图;然后采用深度神经网络进行特征压缩,获取特征描述子并进行粗配准,最后采用ICP进行精配准;该算法在数据缺失的情况下,其配准精度也很高.文献[11]提出一种NV关键点和快速点特征直方图结合的快速点云配准算法,该算法提取点云关键点比较简单,能实现点云快速配准;文献[12]使用曲率特征指导点云配准,该算法对于表面平缓的点云数据,其配准效果优于结合法向量变换的ICP算法.上述方法相较于传统ICP算法在精度、速度或尺度因素方面有所改进,但没有考虑到噪声因素存在下算法配准的稳定性和鲁棒性.

本文提出一种改进的多分辨率点云自动配准算法.为避免因点云初始位置而陷入局部最优的问题,首先采用文献[8]中的算法进行粗配准.为了进一步改善该算法的速度,分别对源点云和目标点云建立KD-tree;同时提出利用法向量夹角平均值的均值设置特征提取的阈值,能有效提取特征点,且不会损失大量特征不明显的点云信息,进一步保证了配准的精度.为了解决粗配准精度不够的问题,提出了一种改进的多分辨率迭代最近点算法进行精配准.该方法利用法向量夹角平均值对点云中的点进行分级,并根据特征点的稠密度计算点云分辨率,然后利用改进的采样比例进行下采样,并采用文献[7]中的匹配度提取关键点对,避免了大量出现错误匹配点对的情况,最后迭代完成配准.

2 粗配准算法

本文粗配准采用精度较高的文献[8]中的算法,并对特征点提取部分进行了改进.同时,为了解决该算法速度较慢的问题,本文对两片点云建立KD-tree,对比穷尽搜索的方法其搜索速度得到了很大的提高,且随着点云规模的递增,其效果更明显.然后分别对源点云和目标点云中的点计算特征度,并根据特征度提取特征点集.然后分别对源点云和目标点云中的特征点集建立直方图特征描述子,并根据特征直方图获取初始匹配点对.对于含有误匹配点对的初始匹配点对采用欧式距离约束和随机抽样一致性(Random Sample Consensus,RANSAC)算法剔除误配点对,最后利用四元素法完成粗配准.算法的整个流程如图1所示.

图1 粗配准算法流程图Fig.1 Rough registration algorithm flow diagram

·改进的特征点提取算法

本文根据公式(1)计算点云的特征度,即法向量夹角平均值,其中法向量采用文献[7]所述的主成分分析法(PCA)求取.

(1)

式中,npi为源点云中某点pi的法向量,npj为pi的k近邻点pj的法向量,pni为源点云中某一点与其k近邻点法向量夹角的平均值.用pni描述点云的区域特性,若pni较小,则说明此区域几何特征变化较平缓;若pni较大,说明此区域存在突出的几何特征;本文根据pni值提取源点云中的特征点.在提取特征点时,去掉源点云中特征不明显的部分,保留pni>ε1的点,然后对于保留的点中的每一点px,提取满足公式(3)的点作为特征点.

在特征点提取过程中,阈值的选取相当重要.若阈值取值过大,提取的特征点就会相对较少,可能会损失部分点云的关键特征信息和大量细节信息;若阈值选取过小,可以保留大量细节信息,但是会导致点云配准的速度变慢.在文献[8]中,阈值ε1为根据实验选取的经验值,针对不同的点云数据需要多次实验选择合适的阈值,在实际应用中不方便.本文提出根据点云中每个点的法向量与其近邻点法向量的乘积的均值来计算,该方法可根据法向量变化自适应的计算阈值,从而自适应的提取特征点,可以很好的保留点云的关键特征信息,同时剔除了大量影响较小的细节信息,加快了配准速度.其计算公式见公式(2):

(2)

pn(px)=max[pn(px1),pn(px2),…,pn(pxk)]

(3)

式中,Np为点云中的点数,px是点云中的某一特征点,pn(pxi)(i=1,2,…,k)为点px的k近邻点的法向量夹角平均值,根据此特征点提取方法对源点云和目标点云中的所有点进行特征点提取,分别得到P的特征点集pf和Q的特征点集Qf.

3 精配准算法

3.1 改进的多分辨率关键点采样

多分辨率配准的精髓在于可以根据级数和分辨率来调整所提取的关键点.级数控制每一级提取的点数,级数越大,采样比例越大;分辨率控制整体提取的点数,分辨率越大,整体采样的点越多,精度越高,速度相对较慢.为了使点云快速收敛,利用低分辨率匹配点对进行快速配准,然后利用高分辨率匹配点对提高配准精度,以此来解决点云配准精度低、速度慢的问题.

分辨率可以用点云的稠密程度来反映,稠密程度[13]为点云中各点与其k近邻点欧式距离的均值.但计算一片点云中的所有点的稠密程度其计算量很大,因此,本文提出利用特征点与其k近邻点欧式距离的均值来计算,并根据调整因子动态调整分辨率的大小.该方法根据点云特征点的稠密度计算点云分辨率,比起凭经验设置更加合理.为了不重复提取特征点从而减少时间复杂度,在粗配准提取特征点时就计算并输出点云的分辨率.其分辨率由公式(4)计算:

(4)

本文根据公式(1)计算的法向量夹角平均值对点云中的点分为m级,法向量夹角平均值越大,其特征越明显,反之,法向量夹角平均值越小,特征越不明显.但通常获取的大多数点云数据,特征明显的点相对较少,特征不明显的点相对较多,因此,在配准时,若仅依靠特征明显的关键点进行配准其精度较低,且有可能会导致配准失败.本文提出改进的采样方式不仅充分利用了特征明显的关键点,同时充分利用了特征不明显的点.

在文献[7]中,当分辨率为j(1≤j≤n),级数为i(1≤i≤m)时,其提取关键点的采样比例Ri,j由公式(5)计算:

(5)

式中,countm表示第m级的点数,counti表示第i级的点数,fix为向下取整函数.该采样比例在级数较低时,提取的关键点太少,丢失了大量特征不明显的关键点信息,导致配准精度相对较低.

本文改进的采样比例Ri,j由公式(6)计算,每一分辨率下各级提取的关键点keypointi,j由公式(7)计算:

(6)

keypointi,j=round(Ri,j·counti)

(7)

该采样方式提高了级数较低时的采样比例,充分利用了特征不明显的点.由于采样的关键点数增多其速度稍慢,但极大的提高了配准的精度.

3.2 改进的多分辨率迭代配准点算法

点云配准就是求解旋转矩阵R和平移矩阵T,使公式(8)最小化:

(8)

式中,qi为目标点集中的点,pi为源点集中的点,Np为源点集中的点数.

为解决传统ICP算法计算效率、精度及易受噪声干扰的问题,本文算法首先通过初始配准获取较好的初始位姿,并改进文献[7]中多分辨率配准点ICP算法.在文献[7]中,分辨率是凭经验设置的,对于不同规模的点云数据需要多次实验确定其值,在应用上不是很方便.本文在初始配准阶段通过计算点云中各特征点与其近邻点距离的均值来确定点云分辨率.其次,采用匹配度提取关键点对,减少了错误匹配率,提高了算法的精度和鲁棒性.改进ICP算法流程如算法1所示.

算法1.改进的多分辨率迭代配准点算法

输入:通过初始配准转换后的源点云P1,目标点云Q,迭代次数,级数m,初始配准中输出的分辨率n;

输出:旋转矩阵R,平移矩阵T,均方根误差ER;

Step 1.初始化:R,T,ER;

Step 2.对源点云P1、目标点云Q建立KD-tree,并计算P1和Q的法向量;

Step 4.

fori=1:n

forj=1:m

计算提取关键点的采样比例Ri,j;

计算各级提取的关键点keypointi,j;

end for

end for

Step 5.

while(目标函数不是最优‖迭代次数没有达到最大)

根据文献[7]中的方式求采样点的匹配度,并提取关键点对;

使用四元素法对获得的匹配点对计算旋转矩阵R和平移矩阵T;

end while

4 实验与分析

本文实验在Intel(R)Core(TM)i5-6300 CPU、8GB内存、Windows 10操作系统、Matlab R2015a环境下进行.为了验证本文算法的有效性,采用了Standford 3D Scanning Repository(1)https://graphics.stanford.edu/data/3Dscanrep/的Bunny和Buddha点云进行粗配准与精配准.并分别与经典ICP、文献[7]、文献[8]中的算法进行了比较.本文粗配准算法中的参数设置:ε1通过计算得到,ε2=0.05,ε3=0.02,k=16;本文精配准算法中的参数设置:分辨率n通过计算得到,m=3,k=8.

4.1 实验1

实验1选取0度和24度的Bunny点云数据进行配准.图2为不加入噪声时各种算法对Bunny点云进行配准的效果图,图3为加入1000个高斯白噪声点后各种算法对Bunny点云进行配准的效果图.其中图2(a)和图3(a)为两视角的原始数据图，图2(b)和图3(b)为经典ICP算法的配准效果图，图2(c)和图3(c)为文献[7]算法的配准效果图，图2(d)和图3(d)为文献[8]算法的粗配准效果图，图2(e)和图3(e)为本文粗配准算法的效果图，图2(f)和图3(f)为本文精配准算法的效果图.

图2 Bunny配准实验Fig.2 Bunny registration experiment

图3 带噪声的Bunny配准实验Fig.3 Bunny registration experiment with noise

从图2中可看出,经典ICP、文献[8]和本文算法配准效果很好,文献[7]算法在头部和前脚部分配准效果不是很好.从图3中可看出,在噪声存在的情况下经典ICP、文献[7]配准效果很差,文献[8]在耳朵部分、头部区域及前脚部分配准效果也不是很好,本文粗配准效果比文献[8]略差,但本文精配准效果在几种算法中最好.

表1 不同算法配准对比Table 1 Different algorithm registration comparison

表1为各种配准算法对原Bunny点云和带噪声的Bunny点云配准速度和配准误差的对比.可以看出经典ICP算法最耗时,同时容易受噪声干扰,在噪声点云配准中其精度很低;文献[7]算法配准速度得到了极大的提升,在原Bunny点云配准时其精度比经典ICP低,但同样易受噪声干扰;文献[8]粗配准算法精度比经典ICP和文献[7]高,同时受噪声干扰的程度比以上两种算法小,但其速度较慢;本文粗配准算法在原Bunny点云配准和带噪声点云配准时精度比文献[8]略低,但其速度比文献[8]快将近3倍;本文精配准算法在粗配准的基础上进一步提升了精度,尤其是对带噪声的点云配准其稳定性更好、精度更高.

4.2 实验2

实验2选取不同视角不同规模的Buddha点云数据进行实验,表2为各种算法对不同规模的Buddha点云进行配准的对比,表3为对Buddha(0度和24度)点云数据加入不同规模噪声进行配准的对比.

表2 不同规模Buddha点云配准Table 2 Buddha point cloud registration of different scales

从表2中可以看出,无论是哪种配准算法,点云规模越大,其配准所花时间越多;无论是哪种规模的点云数据,本文算法总体性能最佳.经典ICP虽然配准精度较好,但是其速度太慢;文献[7]和文献[8]精度差不多,但文献[7]速度更快,本文方法通过二次配准进一步提高了配准精度,其配准精度在几种对比算法中最高,总体速度比文献[8]更快.

从表3中可以看出,各种算法在加入噪声点后其精度和速度都受到了不同程度的影响.其中,经典ICP和文献[7]受噪声影响的程度最大,随着噪声的加入其精度变得较差.经典ICP在加入噪声点后,其运算效率变快、精度变低,但并不是随着加入的噪声越多其精度越差,这是由于噪声点的位置分布所导致.文献[7]在加入噪声点后,其速度变化不是很大,精度变低,但精度不是随着噪声点的规模呈现线性增长.文献[8]粗配准算法和本文粗配准、精配准算法鲁棒性都比较好,其精度基本不受噪声影响,文献[8]和本文粗配准算法中由于加入了RANSAC算法进一步剔除了误匹配点,增强了算法的鲁棒性,且本文粗配准算法速度比文献[8]快近3倍.本文精配准算法在粗配准的基础上进一步进行配准,同时改进了采样比例,使其配准精度在本文各种算法中更高、配准稳定性更好.

5 结 论

提出一种改进的多分辨率点云自动配准算法,该算法针对ICP算法对点云初始位姿的要求,结合文献[8]中的粗配准算法进行快速配准,然后对位姿较好的点云进行精确配准,进一步提高算法的精度.

为了尽可能的提高配准精度、增强算法的抗噪性,本文算法在粗配准部分采用欧式距离约束和RANSAC算法进行外点剔除,提高了粗配准的精度,确保其对于含噪声的和部分重叠度的点云都能为精配准提供较好的初始位姿.在精确配准部分,首先改进了分辨率的设置问题,分辨率可通过点云特征点的稠密度自适应的取值,避免了分辨率设置过大而导致的配准速度较慢的问题和分辨率设置过小而导致的精度不高的问题.其次改进了算法的采样比例,提高了其对于特征信息不明显的点云的配准精度,增强了算法的适用性.本文通过实验证明了算法的可行性和有效性,无论对哪种规模的点云进行配准,本文算法精度都比较高,同时速度较快.