用于多视点云拼接的改进ICP算法①

陈金广,郭秋梦,马丽丽,徐步高

(西安工程大学 计算机科学学院,西安 710048)

1 引言

点云拼接在三维物体重建中有着广泛的应用,如逆向工程、移动机器人、航天航空、指纹识别、计算机视觉等众多领域.在对三维物体进行测量的过程中,扫描设备可能会受到视野上的限制,或是受到噪声、光照等的影响,使得扫描设备在同一视角下无法获取待测物体的全部点云信息.因此,需要从多视角对待测物体进行测量,从而重建出完整的三维物体模型.

目前使用最为广泛的点云拼接算法是1992年Besl等[1]提出的迭代最近点算法(Iterative Closest Points,ICP),其目的是在两片点云之间寻找距离最近的点,计算最优刚体变换矩阵,直到满足某种度量准则下的最优匹配.Chen等在传统的ICP算法的基础上提出了一种新的点云拼接算法[2],该方法能够提高算法的收敛速度,减少迭代耗时及迭代次数,两者的不同之处在于前者提出的是将点与点之间的距离作为邻近点,而后者则利用点与面之间的距离作为邻近点.文献[3]提出与图像信息相结合的快速点云拼接方法,对平移和旋转两种变换分别求解.通过改进的ICP算法得到平移变换,而旋转矩阵则是由拍摄图像与几何知识相结合而得到的.此方法大大降低了计算复杂度,但利用相机拍摄得到的图像必须存在较大部分的重叠,否则需要通过人工操作提供匹配点,操作过程繁琐.文献[4]提出的动态分层匹配标识点算法,将带标识点的点云分别建立最小包围盒,通过4个方向进行分层搜索,以最后搜索到的标识点为顶点,建立动态矩阵,并记录相应的标识点对,但此方法不仅费时而且增加了算法的复杂性.文献[5]提出一种将三维激光扫描技术与测量技术相结合的研究思路,通过对点云数据进行处理、配准、拼接、去噪等步骤实现三维物体重建.

目前点云拼接技术按照拼接过程可以分为粗拼接和精确拼接,粗拼接是将不同坐标系下的点云数据统一到同一坐标系下,随后进行配准,为精确拼接提供初始值;精确拼接则是通过ICP算法对坐标变换参数进行迭代优化,使拼接误差最小,满足所需的收敛精度.粗拼接一般可分为两类,一类是借助辅助设备的拼接方法,包括转台法[6-8]、标识点法[9,10]、定标球法[11].转台法是使回转台倾斜一定的角度,通过旋转待测物体来获取测量数据,但此方法对测量设备的精度要求较高,且定位精度难以保证;标识点法是在不同的视图中建立三个基准点,通过这三个基准点对齐三维测量数据,此方法的计算较为简单,但是在寻找基准点时较为繁琐,并且会影响其定位精度及测量的真实度.文献[10]提出利用标识点对多视图进行约束的高精度粗拼接算法,此方法是在扫描过程中构建标识点多视图网格,并两两拼接,然后利用光束法平差技术优化此网格,得到全局控制点,并保存坐标系下的三维点云数据,最后将全局控制点与坐标系下的三维点云数据进行拼接,得到完整的三维模型.另一类是基于曲面特征的拼接方法,包括三点法、双切曲线法等.三点法是Zhang等[12]通过两片点云中的三个点所形成的平面来确定坐标变换参数,此方法的不足之处在于点云数量过多时计算效率下降,分辨率不高.双切曲线法是由Wyngaerd等[13]人提取待测物体曲线的表面特征,通过匹配双曲线之间对应点的关系来确立点云之间的关系,此方法操作简单,但对于表面特征不明显的待测物体效果欠佳.目前国内外关于点云的拼接算法力求改善拼接精度,许多学者针对对应点之间的搜索问题提出了不同的搜索策略,但一定程度上仍存在问题,比如点云表面曲率变化较大时,会导致平面投影点与真正的对应点之间存在较大的偏差,此偏差会直接影响两片点云的拼接精度,另外在处理此偏差的过程中无疑增加了计算机的计算量等诸如此类的问题.也正是因为存在这样的问题,故而需要对点云拼接算法进行改进.国内外的相关工作为本文的点云拼接算法研究提供了方向,本文算法致力于提高拼接精度,减少迭代次数及迭代耗时,因而提出了一种改进的ICP算法对多视点云进行拼接,通过多次实验验证了其正确性及有效性.

2 迭代最近点算法

针对点云的拼接问题,国内外的研究学者对此提出了很多解决方案,其中就有Besl提出的ICP算法,此算法是对目标点集P寻找与之存在一一对应关系的参考点集Q中距离最近的点构成的集合,建立点与点之间的映射关系,根据这种映射关系计算两点集之间的变换参数,最终求出相应的平移向量和旋转矩阵,直到满足所需的收敛精度并达到点云拼接的目的为止.

ICP算法的实现[1]一般分为以下5个步骤:

(1)假设给定点云P为目标点云,用表示,点云数量为NP,给定点云Q为参考点云,用表示,点云数量为NQ,并满足NP≤NQ.确定点云P、Q之间存在映射关系的对应点对,并构成集合,搜索方法主要包括点到点、点到切平面、K-D树搜索、八叉树搜索等.

(2)根据搜索到的对应点对集合求出初始旋转矩阵T1和平移参数R1:

其中P1和Q0分别表示目标点集P和参考点云Q中的点.求取平移和旋转参数最典型的方法有四元数法[14]和奇异值分解法[15]等.

(3)利用上述求得的平移和旋转参数对Q1进行坐标转换,得到新的变换点集Q2:

(4)重复步骤(2)和(3),进行迭代计算,其中m表示对应点对的个数:

(5)步骤(4)中得到的新的变换点集与参考点云,这两个点集在配准转换过程中能使目标函数最小:

i表示点云中的任意一点.当目标函数最小时停止迭代计算,得到均方误差

假设给定迭代收敛阈值τ,且τ＞0,相邻两次迭代间的均方误差时,停止迭代.若不满足式(5),则重复步骤(4)重新迭代计算新的点集,直到满足目标函数的要求为止.

3 改进的ICP算法

ICP算法是一种迭代计算的算法,具有较高的拼接匹配精度,但是ICP算法强调两片待拼接的点云之间的数据点必须是一一对应的包含关系,ICP算法为目标点云中的每个点寻找在参考点云中对应的点,一一进行匹配,无疑增加了计算量.如果初始位姿较好,则能获取较好的拼接精度和收敛速度,若点云的初始姿态较差将直接影响计算机的计算速度.若初始位置较差会影响目标点云寻找与之存在对应关系的参考点云中的点,在寻找对应点时会出现错误匹配,无形中增加了难度,因而也就难以保证算法精度及效率,对此部分做出改进后对应Step2,确定目标点云中的点的三维坐标并进行排序,将邻域搜索转化为局部搜索,从而提高计算机的计算速度.从上述过程可知,由于需要计算目标点云中每个点的对应点因而计算量较大,可能使整个迭代过程陷入局部最优而不是全局最优.另外此方法是对点云直接处理,无需进行特征点提取、分割等操作.

由于传统的ICP算法是采用遍历的方式来寻找两片点云之间的对应关系,增大了计算机的计算量,降低了计算效率,针对传统ICP算法的缺陷,本文提出的坐标轴法用以计算目标点云中的点及前后各n个点在坐标轴上的距离,加以阈值限制,取距离最近的k个点构成最近点集,减少了不必要的计算量,提高了计算效率.基本思想是确定一个点k的三维坐标Pk,创建三个索引表,以坐标递增的顺序存储输入点的三维坐标,从而将某个点的邻域搜索转化为局部搜索.另外点云模型中的点是均匀密集分布的,因而选择坐标与Pk坐标相近的点组成搜索子集,其中在搜索最近点集时,设定约束搜索范围的阈值,减少不必要的计算量,然后计算子集中的每个点到Pk的距离,并以递增的顺序排列,进而得到最近点集.以Pk为中心点进行最近点集搜索时,设置阈值以约束Pk点前后的搜索范围,其中阈值的大小与扫描的点云距离有关.当阈值取值过小时,不能获取全部有效的最近点,若阈值过大,则计算量仍然较大.经多次实验,设置阈值为0.01.

改进后的ICP算法步骤如下:

Step1.寻找待拼接点云的特征点,并进行初始化,确立待测点云之间的对应关系;

Step2.

1)确定一个点Pk的三维坐标,然后创建三个索引表;

2)将输入的三维坐标以坐标递增的顺序排列,并存入数组Px、Py、Pz中,从而将某个点的邻域搜索转化为局部搜索;

3)将Pk点作为候选点,计算数组 Px、Py、Pz中Pk点及前后各n个点在三维坐标轴上的欧式距离;

4)判断欧式距离与给定阈值的关系,若欧式距离大于等于阈值则停止计算,将全部点存入到新数组Tx、Ty、Tz中,若小于阈值则返回到数组Px、Py、Pz中重新选取候选点;

Step3.求新数组Tx、Ty、Tz中三维坐标的交集,计算出最近点集及坐标变换矩阵,若误差收敛则配准到参考点云,否则返回重新计算最近点.

改进的ICP算法流程图如图1.

4 实验结果及分析

本文共进行了三组实验,分别采用斯坦福点云数据库中的Bunny模型、Dragon模型及一组由Kinect采集的三维人体点云数据,通过三组实验验证本文算法的有效性和正确性.

实验1采用的是不同视角下的Bunny点云模型,分别为点云数量是40 256的bunny_000.pcd模型和点云数量是40 097的bunny_045.pcd模型,如图2(a)、(b)所示.实验先后采用传统的ICP算法和改进的ICP算法进行点云拼接,得到拼接效果如图2(c)、(d).由图2(c)可知,采用传统的ICP算法在拼接过程中出现较大程度上的错位,尤其在Bunny的耳朵、后背以及整个躯体上,从图中可以看出未能得出良好的拼接效果.经改进的ICP算法拼接后效果良好,从图2(d)中可以看出Bunny的耳朵、脚部以及头部较传统ICP算法实现了完全的拼接,姿态良好,并且在尾部和后背部分较传统ICP算法也有明显的改进.

图1 改进的ICP算法流程图

图2 Bunny点云拼接

实验2选取的是点云数量较小的Dragon点云模型,图3(a)、(b)的初始点云数量分别为19 318、30 492.图3(c)是经传统ICP算法拼接后的效果图,可知Dragon点云在躯干和头部的拼接较模糊,姿态差,拼接错位.从图3(d)中可以看出Dragon的躯干部分拼接良好,尤其是在脚部和头部实现完全拼接,效果优良,另外在迭代时间上较传统的ICP算法提高了19.11%.由此可以看出,经改进后的ICP算法在初始点云具有良好姿态的情况下,将拼接误差大幅度降低,并且花费的迭代时间减少,可见改进后的算法减少了计算量,提高了拼接精度.

图3 Dragon点云拼接

为进一步验证本文算法的普适性,实验3采用一组由Kinect采集的三维人体点云数据进行实验.图4(a)、(b)表示两片未拼接的初始点云,点云数量分别为12 675、14 742.从图4(c)看出未经改进的传统ICP算法在拼接时头部出现偏移,并且手臂部位与身体部位也出现重叠,姿态较差,拼接精度较低.经改进的ICP算法拼接后,头部和手臂部分的拼接有了明显的改善如图4(d),在迭代耗时上也由原先的0.821 s降低至0.567 s,提高了44.8%.

将迭代耗时和均方误差作为收敛效果的标准进行评价,均方误差记为error,迭代耗时记为time,改进的ICP算法在最近点集的搜索上,设置一个阈值约束搜索范围,避免了传统ICP算法为目标点云中的每个点寻找参考点云中与之对应的点这一计算量较大的过程,取而代之的是将阈值范围外的点剔除掉,从而减少了搜索的计算量.上述3组点云数据实验结果如表1所示.从表中可看出,在迭代时间上提高了19.1%～47.4%,在均方误差上也优于传统ICP算法,从而验证了本文算法的有效性.

图4 三维人体点云拼接

表1 两种算法拼接性能比较

5 结束语

点云拼接的拼接精度和拼接速度对三维重建有着至关重要的意义,因此对于传统ICP算法在点云拼接上存在的缺陷,提出一种改进的ICP算法.首先是在选取特征点时,将阈值与坐标轴结合,设定约束候选点搜索范围的阈值,获得欧氏距离最近的点集,然后利用ICP算法对点云进行拼接.实验结果表明在确保拼接精度的情况下迭代速度有明显的提升,解决了传统ICP算法在计算速度和迭代耗时上的问题,提高了算法的准确性和有效性,有较高的应用价值.虽然本文算法对于一般性点云数据的拼接取得了较传统ICP算法拼接的良好效果,但仍有不足之处,未来将对一般性点云数据的拼接精度做进一步研究.

1 Besl PJ,McKay ND.A method for registration of 3-D shapes.IEEE Transactions on Pattern Analysis and Machine Intelligence,1992,14(2):239–256.[doi:10.1109/34.121791]

2 Chen Y,Medioni G.Object modeling by registration of multiple range images.Proceedings of 1991 IEEE International Conference on Robotics and Automation.Sacramento,CA,USA.1991.2724–2729.

3 王瑞岩,姜光,高全学.结合图像信息的快速点云拼接算法.测绘学报,2016,45(1):96–102.

4 杨帆,白宝兴,张振普,等.基于多视点云拼接算法研究.长春理工大学学报(自然科学版),2014,37(3):124–127.

5 索俊锋,刘勇,蒋志勇,等.基于三维激光扫描点云数据的古建筑建模.测绘科学,2017,42(3):179–185.

6 周朗明,郑顺义,黄荣永.旋转平台点云数据的配准方法.测绘学报,2013,42(1):73–79.

7 马敏杰,杨洋,范爱平,等.复杂建筑物三维激光扫描与室内外精细建模.测绘与空间地理信息,2015,38(1):111–113.

8 Wang GH,Hu ZY,Wu FC,et al.Implementation and experimental study on fast object modeling based on multiple structured stripes.Optics and Lasers in Engineering,2004,42(6):627–638.[doi:10.1016/j.optlaseng.2004.05.008]

9 李学军,杨晟,李振举,等.标识点快速提取与高精度单点匹配式定位算法.吉林大学学报(工学版),2014,44(4):1197–1202.

10 袁建英,王琼,李柏林.利用标志点多视图约束实现结构光扫描高精度粗拼接.计算机辅助设计与图形学学报,2015,27(4):674–683.

11 李俊峰.大口径深焦比Hindle球面镜曲率半径精确测量.电子测量与仪器学报,2014,28(12):1401–1407.

12 Zhang Y,Tao T,Mei XS,et al.An online spindle rotation error measurement system based on improved three point method.Proceedings of the 9th International Conference on Electronic Measurement &Instruments.Beijing,China.2009.651–656.

13 Wyngaerd JV,van Gool L,Kock R,et al.Invariant-based registration of surface patches.The Proceedings of the 7th IEEE International Conference on Computer Vision.Kerkyra,Greece.1999.301–306.

14 徐晓苏,周峰,张涛,等.基于四元数自适应卡尔曼滤波的快速对准算法.中国惯性技术学报,2016,24(4):454–459.

15 张成,汪东,沈川,等.基于奇异值分解的可分离压缩成像方法.计算机研究与发展,2016,52(12):2816–2823.[doi:10.7544/issn1000-1239.2016.20150414]