基于图像特征和奇异值分解的点云配准算法 下载: 1585次
1 引言
三维激光扫描技术是近些年兴起的一种新型技术,能够快速采集物体表面的三维坐标信息,并建立物体的三维影像模型,即点云模型。由于受到视野、自遮挡及测量环境等因素的影响,三维激光扫描仪需对物体进行多次不同视角的扫描,并将多个视角下获取的点云数据整合到同一个坐标系下,通过点云配准来得到物体的完整数据信息[1]。
根据采用的配准基元,点云配准算法分为基于特征的点云配准算法和基于无特征的点云配准算法两类。基于特征的点云配准算法利用物体表面的角点、轮廓线或特征区域等几何特征来计算变换参数,无需知道变换参数的初值即可实现点云配准。Persad等[2]提出一种基于二维高度图的点云配准算法,利用多尺度小波关键点检测技术实现点云特征配准;张哲等[3]提出一种基于特征点的快速点云配准算法,实现了散乱点云的鲁棒配准;Quan等[4]提出一种基于局部特征的点云配准算法,可解决计算机视觉领域的配准问题;黄源等[5]提出一种关键点特征的点云配准算法,实现了低重叠率点云的精确配准。基于特征的点云配准算法在特征提取和组织上的耗时较长,并且难以实现表面特征缺失点云的精确配准。
基于无特征的点云配准算法无需提取点云特征,直接利用原始数据即可实现配准,其中最经典的代表算法是由Besl等[6]提出的迭代最近点(ICP)算法,该算法基于最小二乘法重复寻找对应点和最优刚体变换来实现点云配准。虽然ICP算法可取得较高的配准精度,但其对两个点云的初始位置要求较高,而且要求两个待配准点云间存在包含关系。鉴于此,国内外研究人员提出了多种改进的ICP算法。唐志荣等[7]提出一种基于正交因子模型的ICP算法,提高了点云配准的精度和稳定性;Yu等[8]提出一种基于最大可行子系统框架的点云配准算法,提高了点云配准的精度和鲁棒性;唐志荣等[9]提出一种基于典型相关分析的ICP算法,对存在遮挡、缺损、缩放和噪声的无序点云具有良好的配准效果。
为了提高点云配准的精度和速度,本文综合利用基于特征的点云配准算法和基于无特征的点云配准算法的优点,提出一种基于二维方位角(BA)图像特征和奇异值分解(SVD)的点云配准算法。该算法粗配准采用基于特征的点云配准算法实现,先将三维点云转换成二维BA图像,再利用基于内部距离的形状上下文(IDSC)算法提取BA图像的局部特征,并利用该局部特征实现点云的粗配准;精配准采用基于SVD的ICP算法实现,该算法通过矩阵分解可降低特征空间维数,得到唯一且稳定的特征描述,同时提高算法的抗噪性。
2 基于BA图像的点云粗配准
基于二维图像特征和SVD的点云配准算法的整体框架如
2.1 点云到BA图像的转换
对于一个三维点云P,假设pij是P中任意一点,定义pij对应BA图像的像素灰度水平[10]:从点pij到其一个连续点pi-1,j-1的激光束矢量间的夹角为θBAij,如
假设点o为点云的源点,则θBAij为
式中:ρi,j为第i个扫描层的第j个扫描点的测量值;ρi-1,j-1为第i-1个扫描层的第j-1个扫描点的测量值;dφ为相应的角度增量。
由BA图像的定义可知,其不同于深度图像,不是通过简单投影变换得到二维图像。BA图像的像素点与原始点云的数据点是一一对应关系,不存在像素点的缺失。同时,BA图像还可突出由角度形成的边缘,有效表示三维点云中的点及其邻域点间的关系,其比深度图像提取的信息更多。因此,将三维点云降维成二维BA图像,利用BA图像的配准实现三维点云的配准,在不影响配准精度的情况下,可有效提高点云配准速度。
2.2 基于IDSC的BA图像配准
对于2.1节获取的BA图像,采用基于IDSC算法对其进行配准[11]。IDSC算法是基于形状上下文(SC)算法,也是基于形状轮廓的局部特征描述算法,将BA图像轮廓边界采样点中的任意一点相对于其他特征点的角度和距离的统计直方图作为该点的形状上下文信息。不同的是,IDSC算法利用采样点间的内部距离代替欧氏距离,定义内部距离为两点间的最短距离,若两点的连接线段位于图像特征形状的内部,该内部距离就等于欧氏距离;否则两点间的内部距离就是各采样点间欧氏距离的代数和,这里采用Bellman-Ford算法计算两点间的最短距离。
对于一幅BA图像轮廓边界上的任意一个采样点,计算该点到其余所有轮廓边界点的内部距离和角度,从而得到一个基于距离和角度分割的二维统计直方图,该统计直方图即为每个采样点的IDSC局部特征描述子。对于BA图像轮廓边界上不同的采样点,其IDSC特征直方图也不相同,如
图 3. 不同采样点的IDSC特征直方图。(a)头部轮廓的三个采样点;(b)三个采样点的IDSC直方图
Fig. 3. Histogram of IDSC features at different sampling points. (a) Three sampling points for head contour; (b) IDSC histogram at three sampling points
采用卡方检验C(pik,qjl)作为两幅BA图像IDSC局部特征描述子的相似性判断准则,定义式为
式中:p、q为两幅待配准图像对应的原始点云模型中的点;S为特征直方图分割的区间数量;Hp,ik(s)为模板BA图像中点pik对应的IDSC直方图,pik为第一个点云中的第i个扫描层的第k个扫描点;Hq,jl(s)为目标BA图像中点qjl对应的IDSC直方图,qjl为第二个点云中的第j个扫描层的第l个扫描点。C(pik,qjl)值越小,表示点pik和qjl在形状或结构上的特征越相似;C(pik,qjl)小于一定阈值时,认为点pik和qjl是BA图像中的可匹配点。通过判断C(pik,qjl)值即可找到两幅BA图像的匹配像素点。
BA图像中,任意一个像素点的θBAij对应初始三维点云的第i个扫描层的第j个扫描点。由于三维点云中的点和BA图像的二维像素点是一对一的映像关系,因此BA图像像素θBAij对应初始三维点云的点就是pij。
假设两个待配准的初始三维点云为P={pi}和Q={qj},满足简单的刚体变换。若P和Q可正确配准,至少有三对相关点,因此求解P和Q的旋转矩阵R的问题就是一个正交Procrustes问题。
假设从P的质心平移到Q的质心,在不考虑平移变换的情况下,P和Q可写为
式中:pic和qjc分别为点pi和qj平移后得到的点;
式中:m和n分别为点云P和Q中点的数目。
令新的相关点云分别为Pc和Qc,那么R定义为
式中:‖·‖F为Frobenius范数,定义为
式中:A为某一待求解范数的矩阵;aij为矩阵A中的元素。求解(7)式即可得到点云的刚体变换,由此实现基于BA图像的点云粗配准。
3 基于SVD的点云精配准
SVD是重要的矩阵分解算法,可降低特征空间维数,得到唯一且稳定的特征描述,同时提高算法的抗噪性,在点云配准、信号处理及统计学等领域具有重要的应用价值[12]。基于第2节点云的粗配准结果,采用基于SVD的改进ICP算法对点云数据进行进一步的精配准。
假设粗配准后的两个三维点云分别为P'={p'i,i=1,2,…,NP}和Q'={q'j,j=1,2,…,NQ},其中NP和NQ分别为P'和Q'中所包含的点数。点p'i和q'j的相关性可表示为
式中:t为平移矢量。刚体变换(R,t)的求解式为
式中:集合SE(3)是一个Euclid训练组;E为单位矩阵;P'a和Q'b分别为P'和Q'经过刚体变换后的点云集合。
对于平移矢量t,可通过P'和Q'的质心移动来求解。因此可将(10)式转换成仅依赖于R的形式,即
式中:R∈so(3)是一个三维旋转组。P'a和Q'b分别定义为
式中:IaNP和IbNQ均为单元矩阵。
对于目标函数(11)式,采用SVD法进行分解,于是有
式中:U为左奇异矩阵;V为右奇异矩阵;Σ为包含奇异值的对角矩阵。
定义一个避免噪声点云中微小图像匹配矩阵S,并求解R,S和R分别为
基于上述刚体变换求解过程,点云精配准算法(即基于SVD的ICP配准算法)的具体实现步骤如下。
1) 采用2.2节的基于BA图像的粗配准算法对点云进行初步对齐,假设粗配准后的两个点云分别为P'={p'i,i=1,2,…,NP}和Q'={q'j,j=1,2,…,NQ}。
2) 构建测量模式矩阵P'a=[p'a1,…,p'aNP]。
3) 通过平移操作对齐P'和Q'的质心。
4) SVD算法应用于P'a,即P'a=UPaΣPa
5) 利用(12)式和(13)式构建旋转模式
6) 计算配准误差ε(j)=‖
4 实验结果与分析
算法在Visual Studio 2010环境下,Intel Core i7 3.33 GHz的CPU、16 GB内存的Windows 7 64位PC上进行实验。实验对4组不同类型的点云数据模型进行配准,分别为斯坦福大学在网络上公开的Bunny点云和Dragon点云的数据模型,以及采用三维扫描仪实地采集的原始颅骨点云和文物点云的数据模型,4组点云如
图 4. 4组待配准点云。(a) Bunny;(b) Dragon;(c)颅骨;(d)文物
Fig. 4. Four groups of point clouds to be registered. (a) Bunny; (b) Dragon; (c) skull; (d) cultural relic
采用基于二维图像特征和奇异值分解的点云配准算法对4组点云分别进行配准,先将三维点云转换成二维BA图像,利用IDSC算法对BA图像进行配准;再根据三维点和二维像素的一对一映像关系计算三维点云的刚体变换,从而实现两个点云的粗配准;最后采用基于SVD的ICP算法对点云进行进一步精配准。
实验中选取的算法参数:特征直方图分割的区间数量S为10~50,ε(j)的阈值为0.1 mm,特征直方图分割的区间数量根据具体实验数据情况而定。4组点云的粗配准结果如
表 1. 4种算法的配准结果比较
Table 1. Comparison of registration results of four algorithms
|
图 5. 4组点云的粗配准结果。(a) Bunny;(b) Dragon;(c)颅骨;(d)文物
Fig. 5. Rough registration results of four groups of point clouds. (a) Bunny; (b) Dragon; (c) skull; (d) cultural relic
图 6. 4组点云的精配准结果。(a) Bunny;(b) Dragon;(c)颅骨;(d)文物
Fig. 6. Fine registration results of four groups of point clouds. (a) Bunny; (b) Dragon;(c) skull; (d) cultural relic
为了进一步验证基于二维图像特征和奇异值分解的点云配准算法的配准性能,对
由
由于ICP算法是一种基于无特征的点云配准算法,其要求两个待配准点云的初始位置相对比较接近,且存在包含关系,因此对旋转和平移较大的低覆盖率点云的配准效果不佳。ICP算法在配准过程中需不断迭代得以实现,因此算法运行时仅需存储两个待配准点云,耗时与待配准点云的点数目NP和NQ及迭代次数K有关,其空间复杂度为O(NP+NQ),时间复杂度为O[K max (NP,NQ)]。文献[ 13]算法是一种基于特征点的点云配准算法,利用点云模型上的内部形态描述子(ISS)实现迭代配准,但所选特征相对简单,对复杂模型的配准精度还有待提高。由于特征点数量较少,假设为N'P和N'Q,迭代次数为K',文献[ 13]算法的空间复杂度和时间复杂度比ICP算法相对要小,空间复杂度为O(N'P+N'Q),时间复杂度为O[K' max (N'P,N'Q)]。文献[ 14]算法是一种基于距离误差评价的ICP算法,可实现高密度点云的有效配准,但对于采样均匀的公共点云数据模型的配准并无明显优势。由于文献[ 14]算法是基于ICP算法引入距离误差评价函数来实现的,因此其迭代次数远低于ICP算法,其空间复杂度为O(NP+NQ),时间复杂度为O[max (NP,NQ)log2K max (NP,NQ)]。所提算法通过降维的方式实现特征点的无迭代精确配准,配准精度和速度明显优于已有配准算法,其空间复杂度为O(N'P+N'Q),时间复杂度为O[max (N'P,N'Q)]。
由此可见,基于二维图像特征和奇异值分解的点云配准算法可对不同类型的点云模型实现精确配准,算法空间复杂度和时间复杂度都较小,是一种精度高、速度快和鲁棒性好的点云配准算法。
5 结论
点云配准是三维重建的关键技术之一,目前已在各个领域得到了广泛关注。随着应用需求的不断提高,对点云配准算法的精度、抗噪性、速度和普适性的要求也越来越高。为了提高点云配准的性能,提出一种基于BA图像和SVD的点云配准算法。先将三维点云转换成二维BA图像,实现了三维点和二维像素的一对一映像关系,并利用IDSC算法对BA图像的轮廓进行配准,从而实现点云的粗配准;再采用基于SVD的ICP算法,通过矩阵分解降低特征空间维数,实现了点云的精配准。所提算法充分考虑了局部特征和噪声对配准结果的影响,可实现点云的快速精确配准。今后的研究中,要进一步研究重叠率在50%以下的低覆盖率点云的配准问题,并将其应用于非薄壁缺损文物断裂面的匹配中,进一步扩大点云配准算法的应用范围。
[1] 刘鸣, 舒勤, 杨赟秀, 等. 基于独立成分分析的三维点云配准算法[J]. 激光与光电子学进展, 2019, 56(1): 011203.
[2] Persad R A, Armenakis C. Automatic co-registration of 3D multi-sensor point clouds[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2017, 130: 162-186.
[3] 张哲, 许宏丽, 尹辉. 一种基于关键点选择的快速点云配准算法[J]. 激光与光电子学进展, 2017, 54(12): 121002.
[4] Quan S W, Ma J, Hu F Y, et al. Local voxelized structure for 3D binary feature representation and robust registration of point clouds from low-cost sensors[J]. Information Sciences, 2018, 444: 153-171.
[5] 黄源, 达飞鹏, 陶海跻. 一种基于特征提取的点云自动配准算法[J]. 中国激光, 2015, 42(3): 0308002.
[6] Besl P J. McKay N D. A method for registration of 3-D shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(2): 239-256.
[7] 唐志荣, 蒋悦, 苗长伟, 等. 基于因子分析法的三维点云配准算法[J]. 激光与光电子学进展, 2019, 56(19): 191503.
[8] Yu C, Ju D. A maximum feasible subsystem for globally optimal 3D point cloud registration[J]. Sensors, 2018, 18(2): 544-553.
[9] 唐志荣, 刘明哲, 蒋悦, 等. 基于典型相关分析的点云配准算法[J]. 中国激光, 2019, 46(4): 0404006.
[10] Lin C C, Tai Y C, Lee J J, et al. A novel point cloud registration using 2D image features[J]. EURASIP Journal on Advances in Signal Processing, 2017, 2017: 5.
[11] Carstensen A, Zhang J, Heyman G D, et al. Context shapes early diversity in abstract thought[J]. Proceedings of the National Academy of Sciences of the United States of America, 2019, 116(28): 13891-13896.
[12] Guillemot V, Beaton D, Gloaguen A, et al. A constrained singular value decomposition method that integrates sparsity and orthogonality[J]. PLoS One, 2019, 14(3): e0211463.
[13] 赵夫群, 耿国华. 基于特征点的秦俑断裂面匹配方法[J]. 激光与光电子学进展, 2018, 55(4): 041005.
[14] Wu M M, Wang J F. Registration of point cloud data for matching crushed sand particles[J]. Powder Technology, 2019, 347: 227-242.
赵夫群, 耿国华. 基于图像特征和奇异值分解的点云配准算法[J]. 激光与光电子学进展, 2020, 57(10): 101101. Fuqun Zhao, Guohua Geng. Point Cloud Registration Algorithm Based on Image Feature and Singular Value Decomposition[J]. Laser & Optoelectronics Progress, 2020, 57(10): 101101.