1、 敬请登录网站在线投稿(t o u g a o.m e s n e t.c o m.c n)2 0 2 3年第4期 6 1 一种基于S A C N D T和I C P的高精度点云配准方法*单彦虎,张潇丹,储成群(中北大学 仪器与电子学院,太原 0 3 0 0 5 1)*基金项目:国家自然科学基金面上项目(6 2 0 7 5 1 9 9)。摘要:传统的正态分布变换算法精度低,而精度较高的迭代最近点算法极易陷入局部最优解。为了解决以上问题,将采样一致性算法与N D T算法结合作为点云初始配准方法,再利用K D t r e e加速的I C P精配准方法完成点云匹配。实验结果表明,本文所提出的方法大大
2、提高了配准精度。关键词:点云配准;快速点特征直方图;正态分布变换;迭代最近点中图分类号:T P 3 9 1 文献标识码:AH i g h-p r e c i s i o n P o i n t C l o u d R e g i s t r a t i o n M e t h o d B a s e d o n S A C-N D T a n d I C PS h a n Y a n h u,Z h a n g X i a o d a n,C h u C h e n g q u n(S c h o o l o f I n s t r u m e n t a n d E l e c t r o
3、n i c s,N o r t h U n i v e r s i t y o f C h i n a,T a i y u a n 0 3 0 0 5 1,C h i n a)A b s t r a c t:T h e t r a d i t i o n a l n o r m a l d i s t r i b u t i o n s t r a n s f o r m(N D T)a l g o r i t h m h a s l o w a c c u r a c y,w h i l e t h e i t e r a t i v e c l o s e s t p o i n t(I
4、C P)a l g o-r i t h m w i t h h i g h a c c u r a c y i s e a s y t o f a l l i n t o t h e l o c a l o p t i m a l s o l u t i o n.I n o r d e r t o s o l v e t h e a b o v e p r o b l e m s,t h e s a m p l e c o n s e n s u s i n i t i a l a l i g n m e n t(S C A)a l g o r i t h m a n d N D T a l
5、g o r i t h m a r e c o m b i n e d a s t h e p o i n t c l o u d i n i t i a l r e g i s t r a t i o n m e t h o d,a n d t h e n t h e I C P f i n e r e g i s-t r a t i o n m e t h o d a c c e l e r a t e d b y K D-t r e e(K-D i m e n s i o n a l t r e e)i s u s e d t o c o m p l e t e t h e p o i
6、n t c l o u d m a t c h i n g.T h e e x p e r i m e n t r e s u l t s s h o w t h a t t h e m e t h o d i n t h i s p a p e r g r e a t l y i m p r o v e s t h e a c c u r a c y o f r e g i s t r a t i o n.K e y w o r d s:p o i n t c l o u d r e g i s t r a t i o n;f a s t p o i n t f e a t u r e h
7、i s t o g r a m;n o r m a l d i s t r i b u t i o n t r a n s f o r m a t i o n;i t e r a t i v e c l o s e s t p o i n t0 引 言随着三维数据采集设备的成熟和普及,3 D点云数据的获取更加方便快捷。越来越多的学者基于点云数据研究相关算法处理方法。其中,点云配准技术1的应用领域极其广泛,包括三维重建、逆向工程、工业检测、计算机视觉、机器视觉等以及近几年来的一些新兴领域,包括移动机器人的同步定位和制图、自动驾驶中使用的高精度地图构建和环境感知、自动城市建模、增强现实、医学检测的
8、图像合成等。这些应用场景和领域往往需要极高的配准精度,有些对配准时间和速度也有要求。但是由于点云是一种非结构化的数据形式,且一般原始的点云数据量都很庞大,还伴随着较多的噪声和遮挡,因此点云的配准工作是点云数据处理技术中一个极具挑战性的研究方向。点云配准2的结果就是求得一个旋转矩阵和平移矩阵,使得源点云通过这两个矩阵变换到目标点云相同坐标下。迭代最近点(I C P)算法3是目前比较经典的方法,配准精度比较高,但是算法要求待配准数据具有较好的初值,若两点云位姿相差太大,则很容易掉入局部收敛。为了解决局部收敛问题,李慧慧4等提出在I C P配准之前增加主成分分析方法对点云进行粗配准,对初始位置相差较
9、大的点云进行位姿调整,该方法运行效率较高、鲁棒性好,但是配准结果可能会出现孔洞,尤其是在初始点云分布不均匀的情况下。陈学伟5等提出了一种基于特征点的采样一致性初始配准算法(S a m p l e C o n s e n s u s I n i t i a l A l i g n-m e n t,S A C I A),用来做点云的初始粗配准,并利用方向向量阈值去除错误点对,为精配准提供了较好的初始位置姿态,但是从配准效果来看,仍存在一些孔洞和噪声点。李庆玲6等提出一种基于N D T I C P的点云配准方法,使用N D T算法作为粗配准方法,实验过程分别基于实验室数据和K I T T I数据集完
10、成,该方法提升了配准效率,同时提高了3 D点云地图的建图精度,但是配准时间较长,仍需要继续改进。张泽鹏7等提出一种基于快速点特征直方图(F a s t P o i n t F e a t u r e H i s t o g r a m,F P F H)初始匹配与I C P的点云配准方法,首先使用随机抽样一致(R a n d o m S a m p l e C o n s e n s u s,R AN S A C)算法对点云数据进行预处理,接着基于F P F H算法提取点云特征后再初始匹配,最后使用I C P算法求得最终变换矩阵,该方法在配准精度上有所提高,但是配准均方根误差还处于毫米级别。6
11、2 M i c r o c o n t r o l l e r s&E m b e d d e d S y s t e m s 2 0 2 3年第4期w w w.m e s n e t.c o m.c n 为了进一步提高点云配准的精度,本文结合S A C与N D T算法作为点云的初始配准方法,得到精度较高的初始匹配效果后,再利用经典的I C P精配准方法实现点云的高精度配准。1 点云配准方法1.1 本文提出的算法为了提高点云配准的精度,本文将S A C算法和N D T算法相结合实现粗配准,I C P精配准过程使用K D t r e e加速来搜寻最近点,大大提高了配准精度和配准效果。首先将源点云
12、P和目标点云Q分别进行降采样处理,以精简点云数量,并去除一些噪声点,提高后续点云配准的效率,将降采样后的源点云和目标点云模型分别记为P 和Q;对P 和Q 分别基于F P F H特征描述子进行点云特征提取后,使用S A C算法进行初始粗匹配,由于S A C算法配准精度有限,本文提出添加配准更精确的N D T算法作为粗配准的第二步,得到最终的粗配准变换,即旋转矩阵RN以及平移矩阵TN,经过以上S A CN D T粗配准,源点云P经过式(1)变换为PN;PN与目标点云Q 作为I C P精配准方法的输入源点云和目标点云,最后使用K D t r e e加速的I C P精配准算法完成点云的配准工作。pN=
13、RNps+TN(1)式中,ps表示源点云中的点,pN表示经过S A C N D T变换后,与源点云中ps一一对应的点。本文算法流程图如图1所示。图1 本文算法流程图1.2 点云体素降采样原始点云数量一般都很庞大,后续计算F P F H特征和运行S A C N D T算法时效率会变低,此时,需要先对点云进行下采样处理8,以减少点的数量,体素化网格方法满足精简点云数量的同时,还能够不破坏原始点云数据的表面形状 和 特 征,有 效 提 高 后 续 点 云 配 准 算 法 的 运 行效率。该方法具体过程如下:首先,创建一个能够完全包含所有点云的最小长方体盒子,假设点云数据在三维坐标轴x、y、z方向上的
14、范围分别为mx、my、mz,那么创建的最小长方体盒子的体积为V=mxmymz。长方体盒子内部需要继续栅格体素划分成若干个小长方体,这些小长方体即为体素,根据滤波需求可以设置体素的长lx、宽ly和高lz。每个体素中都包含着若干个点云数据,体素滤波方法就是计算每个体素内所有点云数据的重心,直接用该重心点代替体素中所有点,从而实现把体素中若干个点精简为一个点来减少点云个数。假设每个体素内 的 点 云 集 合 为Pxi,yi,zi(i=1,2,k),则重心坐标的计算公式为:x=1kki=1xi,y=1kki=1yi,z=1kki=1zi(2)为了实现点云密度的均匀性,本文在进行点云体素网格降采样时,取
15、lx=ly=lz=l=0.0 1 2 m,即体素都是均匀的小立方体。1.3 F P F H提取点云特征点云数据中包含了大量的特征信息,包括三维坐标信息、法向量、曲率和密度等。基于某一种几何特征进行分析和统计9,就能得到相应特定的点云特征描述子,为后续点云相关算法处理提供了方法,提高了效率。F P F H特征描述子1 0-1 1是将点云中所有点的法向量和每个点邻域的表面曲率特征统计量化成直观的参数,从而构建特征直方图。F P F H特征描述子进行点云特征提取时的工作原理如图2所示。图2 F P F H特征提取原理图特征提取步骤如下:关键点集P 中的一点记为p i,ni为p i的法向量,以p i为
16、圆心,设定邻域半径r1,在该圆内查询p i的邻近点集,记为pi j,建立pi与其邻近点pi j之间的(U,V,W)坐标系,坐标系表达公式如下:敬请登录网站在线投稿(t o u g a o.m e s n e t.c o m.c n)2 0 2 3年第4期 6 3 U=niV=Up i-pi j()p i-pi jW=UV|(3)计算p i与其邻近点pi j之间的S P F H特征关系,即(,)角度关系,计算方式见式(4)。再选pi j点集中任意一点为中心点,重新计算与其r1邻近点之间的(,)角度关系,直到遍历完所有邻近点为止。=Vni=Up i-pi j()p i-pi j=a r c t a n Wni,Uni()|(4)按照上述步骤能得到所有邻近点的S P F H特征,根据式(5)继续求得该点的F P F H特征描述子:F P F H p i()=S P F H p i()+1kkj=11wjS P F H(pi j)(5)式中,wj表示p i与邻近点pi j之间的欧氏距离,k为邻近点的数量。可以选择合适的邻近点,以提高计算速度。1.4 S A C粗配准算法计算完特征描述子之后,通
