基于光学照相式测量的多视角三维点云拼接算法

1、摘要： 提出一种面向自由视角扫描点云的两步法三维拼接算法。首先在重叠区域采样出两片大致相似的点云，根据空间坐标组合变换原理，使用N边形法进行预拼接，获取预拼接的转换矩阵参数，尽量缩小两片点云间的位置关系；然后，基于初始位姿对采样点云使用改进的ICP算法微调精拼，融合传统的迭代最近点距离度量函数的优点，通过分层次设定迭代终止条件和多次重采样获取对应点对，达到减少迭代次数，同时保证全局最小收敛。试验结果表明，该三维拼接两步法具有较高的拼接精度和好的操作性，适用于不能进行粘贴标记点和转轴固定的特殊三维视觉测量领域。关键词：三维扫描，配准，自由视角，迭代最近点法 中图分类号：TG386 文献标识码：A

2、前言1 相关算法研究与分析目前的拼接技术大致可分为基于机械转轴的拼接，基于标志点粘贴识别的拼接及基于最近点迭代收敛算法的拼接三大类，这三类方法各有自身的优点和适用条件。1.1 基于转轴和标志点的拼接技术文献3对基于机械转轴的拼接算法原理及实现做了详细的描述。其原理是利用一个步进电机驱动旋转工作台，旋转拍摄多视角下的场景影像，记录相应角度值，通过标定出的基准坐标系和旋转台坐标系的空间位置关系，对不同视场的数据点云进行缝合，完成测量数据的采集和拼合。该算法精度依赖于机械精度，灵活性差，而且对测量有严格的位置限制，被测物体必须放置在旋转工作台上，因此很大程度的限制了其应用性。基于粘贴标志点拼接的方法

3、目前得到广为应用，该方法属于有约束的拼接方法。首先人工在被测物体表面粘贴方便识别的标志点，采集若干标志点在不同视角下的三维坐标，依据标志点的空间几何不变性，得到不同标志点在不同视角下的匹配关系，然后运用SVD奇异值矩阵分解算法4或四元组算法5分解求出转换参数R和T。另外有延伸的全局标志点识别拼接算法6。该类方法拼接对标志点依赖过高，在编码圆的识别方面有精度和可靠性限制，而且对于现场测量环境应用不方便，另外不适用于不能进行标志点粘贴的测量情况。1.2 迭代最近点拼接算法迭代最近点拼接算法（ICP）是由Besl和McKay7提出，它是一种以几何结构为主的拼接、配准算法，该算法实现首先找出需拼接点云

4、之间的对应关系，利用反复迭代的方法缩小两组点云的距离，逐步减小误差，找出一组具有距离最小平方差的几何转换矩阵，使两片点云经过几何转换精确拼接对齐一起8。该类方法不需要额外的特征就能实现两个物体的拼接，然而ICP算法仍然有自身的缺陷：（A）为了避免陷入局部最小化的错误配准，该算法需要有个好的转换参数的初始估计值；（B）当要配准的两个曲面数据量较大时，在每次迭代过程中最近点的搜索计算量很大，导致算法实现很耗时；（C）即使对无噪音的数据，也不能一定保证获取正确的结果，不能保证收敛到全局（甚至局部）最小值,鲁棒性较差。2 算法描述本文提出了一种高效，高质量的拼接算法，算法实现大致需要两步。首先对采样点

5、云进行N边形法预拼接，将两片点云位姿大致重合在一起，实现拼接的粗拼，然后对预拼接的模型使用改进的ICP融合算法-ICPP(iterative closest plane and point algorithm)保证全局收敛，减少迭代次数，实现准确的精拼，使两片点云完全重合在一起，最后，将获取的两次拼接转换参数用于整体数据，实现数据高精度的无缝拼接。2.2 改进ICP算法用于精拼传统的ICP（iterative closest point）算法7限制经研究发现，ICP算法正确快速的收敛及达到目标函数优化全局最小很大程度的依赖于对应点的选择和目标距离度量函数的设定，因此我们提出了融合点到点距离(p

6、oint-to-point distance metrics)和点到面距离(point-to-plane)两种模型的综合度量函数（point-to-plane and point），通过分层次的迭代终止条件设定，减少了迭代终止的次数，使用基于k-d tree的搜索算法15多次重采样对应点集，减少了对应点的搜索时间，保证了对应点选择的正确性，最终实现了正确全局最小收敛的获取。(1) 初层次收敛 对于N变形采样的局部点云数据P1，Q1使用基于几何曲率的采样获取适量的点集对P2,Q2作为对应点集对，首先设定相对较大的终止阈值0.1mm，以减少迭代次数，同时进一步缩小点云间的距离。 设pi,qi(i=

7、1,N)分别是点云P2和Q2中的点，理论上，两个曲面拼接完成即认为对应点对(pi,qi)之间存在如下式的刚体变换：i-qj=0但是，实际测量获得的数据因为标定误差，系统精度，噪音数据等影响等式不会成立，因此首先设定一个精度可以接受的无穷小值使得等式成立，设定极限值e, 通过最小化下面的值能容易的实现转换矩阵空间的获取：Ne=i-qi)i=1但是，对应点对的查找非常困难而且耗时，特别对非规则性的曲面。本文首先固定曲面P2，利用k-d tree搜索算法15查找Q2中到P2最小距离的最近点qi:qi=q|minqQi-q设TR0是经过初始N边法获取的位姿，随着迭代次数k的增加，将上次迭代获取的数据T

8、(k-1)值代入迭代公式找到qkj：Nek=kpki-qj)，i=1式中，qkk-1j=q|minpqQi-q，通过分析上式发现，最小化获得的点集qkj是一个数字化的曲面模型，如果近似用一个点来代替该曲面，那么问题就会得到大大简化，在初次迭代循环，基于点云距离未知或相对较远时，使用点到平面的距离度量函数12，因为该方法对于点云距离位姿距离较远的情况能实现较优的线性收敛，如下图4通过小角度的近似旋转来实现转换。点qi处的切平面用si来表示，那么距离度量函数表示为：Ne='i-q'j)其中qj=q|minqSTpi-qi=1J点到平面的距离可表示为一个线性函数：Nek=d2kks(

9、Tpi,Sj)，i=1Skk'k'kk-1j=s|nqj(qj-s)=0，qj=(Tli)Q式中dks是点到平面的距离，nqj是曲面Q2在点qkj处的曲面法向量，l=a|(pi-a)npi=0表示在pi点的线性切向量，npi是曲面P在点pi的法向量，(Tli)Q2表示线l在曲面Q2的插入点。qi图4 度量函数收敛逼近模拟图该算法不考虑特殊的对应点问题，因此消除了收敛速度慢的问题，另外本系统将收敛终止条件设置较为宽松设定为0.1mm，大大减少了迭代的次数，经过逐步迭代逼近，获取最后转换矩阵参数。为了验证算法的效率，我们对比了本系统算法和基于点到平面距离度量函数算法，及传统的ICP

10、算法，具体见图5。从图5也看出，虽然迭代次数大大减少，但是收敛误差一直没有减少，因此，需进行进一步高精度逼近。图5 各算法收敛迭代次数对比图（2）第二层次收敛对应点查找和对应转换参数确立之间相互对应，如果对应关系参数c1,ck已知,那么利用参数很容易找到每个点的对应最近点。相反，如果两片点云数据处于最佳转换拼接状态，那么两片点云间的转换关系即是要找到拼接转换参数。因此，本系统基于建立的拼接转换关系TR1重采样对应点集为P3和Q3，然后搜索这些采样点在参考采样点集中的对应点邻近局部区域查找最近点，通过这些步骤可以将搜索时间代价减少到小于使用k-d tree进行全局查找的O(LogNx)，具体实现

11、如下：点pi=(x1,y1,z1)，qj=(x2,y2,z2), (i=1,Nq)分别是基于近似转换关系重采样的两个对应点集对,两点之间的欧式距离表示为d(pi,qi),d(pi,qi)=pi-qi=(x-x2(y2221)+2-y1)+(z2-z1)。迭代初始设定T0=1,0,0,0,0,0,0T,迭代次数k=0,定义迭代拼接过程中获得的拼接向量为序列：t1,t2,t3,tk。那么具体实现步骤可表示为： 1）得到目标点云P3(pi<P,(i=1Np)和参考点云 Q3(qi<Q,(i=1,Nq)； 2) 基于初始的转换参数TR1,对P3中Np个点在Q3中重采样标识出对应点集Q4；3

12、) 初始化数据：X0=P3, TT0=1,0,0,0,0,0,0,k=0； 4) 在对应点集Q4的邻近局部区域使用k-d tree搜索P3中各点在Q4中的最近点Y,定义第k次迭代为：Yk=T(Xk,Q4)；5) 计算拼接向量：(tk,dk)=T(X0,Yk)；6) 应用k次拼接向量到初始点集X0：Xk+1=tk(X0)； 7) 点到点的二次方距离函数简化为基于线性搜索的多元无约束最小化问题,迭代向量间的夹角在拼接空间定义了收敛的方向。t1k=cos-(qkqk-1q)kqk-1式中，qk=qk-qk-18）判断误差是否收敛，如果dk-dk+1<,则收敛，否则循环到步骤4。本次迭代终止获取

13、拼接转换参数TR2，终止条件设定为0.02mm。虽然传统的基于点到点距离函数的ICP算法效率不高，在最坏的情况耗时能达到O(NpNq),本身不本文的拼接算法以初始预拼接和微调精拼两步来完成，预拼接的目的使两片点云数据能尽量缩小彼此间的位置关系，让两片数据都能有相同的精确配准拼接条件；微调精拼的目的是让两片需拼接的点云采样数据的距离或角度误差达到最小。通过预拼接保证了两视的大致转换参数已知，通过ICPP的步骤最近点搜索，达到近似转换参数矩阵空间的获取，为以后的点对面ICP搜索提供了前提，简化了复杂非线性问题求解的难度，保证了全局最小距离d(P,Q)的查找。本文算法不仅具有良好的拼接精度，而且具有

14、很好的收敛效率。与原来的基于点到点距离的ICP算法和基于点到面距离的ICP算法，本文的多次采样点改进算法使用k-d tree搜索局限在局部区域减少了迭代次数，提高了收敛效率保证了拼接精度。下表1是各种算法的对比数据：表1 算法收敛效率及精度对比表的牙齿和头像为例，使用三种算法对比验证了收敛迭代次数及拼接精度，具体显示如表1，可以看出本位的算法在迭代收敛速度和拼接精度整体优于另外两种算法，值得注意的是点到点算法对头像例子拼接时易出现局部收敛，出现拼接错误。3算法实例验证及拼接度评估3.1 试验结果为实现基于自由视角扫描的多片点云无约束三维拼接，本文基于VC+.NET20003开发出一套三维点云采

15、集和拼接系统，该测量系统是我们自行研制的基于结构光的视角测量系统D3DScanner，本文以口腔修复中的牙齿为测量对象进行多视角点云扫描，使用本文算法对多片点云进行了拼接并显示。图6是使用本系统进行预拼接的软件界面，图6a是对需拼接的两片点云多边形采样预拼接，图6b是预拼接结果图，从拼接间隙的局部放大图6c看出需进行精确拼接。在预拼接的基础上经过本文的第二步ICPP精拼如图6d，获取高精度拼接结果如图6e，从图6f的渲染图看出拼接精度能满足系统需求，图6g是使用本文算法对多片测量点云拼接的结果。(a) N边形预拼接 (b) 预拼接结果 (c) 预拼接误差放大(d) ICPP算法精拼 (e) 精

16、拼结果 (f) 精拼结果渲染图(g) 多片牙齿点云拼接渲染图图6 系统拼接流程软件界面3.2 拼接度评估对拼接的结果，我们虽然可以从点云的显示直观判断其拼接效果，但不能准确定量的看出其拼接精度，因此我们采用文献16提到的相似度评估函数S来量化其拼接精确程度。相似程度的数学函数S表示为：-SSDD,MS=(e(L1/2D+LM)100%,式中，SSD=xT(x2b-a)，Xp=(xp,yp,zp),Xq=(xq,yq,zq)分别是点集P和Q上对应点坐标，SSDD,M是两片点云模型之间的最小差值平方和，LD是点云P模型顶点值原点的距离平方和，LM是点云Q模型顶点值原点的距离平方和，下表是利用本文算

17、法对任取的多个对应点云点对的相似度评判结果。表2 点云拼接相似度4 结论本文介绍了一种面向特殊需求扫描点云拼接方法，解决了那些特性不明显、不能使用基于转轴测量和粘贴标记点进行全周测量的问题。由于拼接是一个局部匹配的问题，因此本文借助匹配的思想实现局部拼接，首先大致采样出两片点云的重叠部分，使用提出的N边形法尽量缩小彼此间的位置关系，也为精拼微调提出必备的初始位姿，通过分层次的迭代终止条件设定，使用改进的迭代最近点融合算法，减少了迭代次数，保证了全局最小收敛的获取。实例证明该方法具有较好的拼接精度和收敛效率，而且操作简单，人性化等优点，最后将该三维拼接技术和自行研制的三维测量系统结合完成了复杂物

18、体形面的全方位信息精确获取，具有较高的实际应用价值。参考文献：1 张小锋 徐鸿钧 吴琦, 基于双目视觉技术的磨粒高度检测J,中国机械工程，2007，18（7）：812-815.2 吴凤和 张晓峰 施法中. 基于单幅图像数据的三维重构方法研究J,中国机械工程，2007,18(17):2071-2075.3 龙玺，钟约先，李仁举.等. 结构光三维扫描测量的三维拼接技术J. 清华大学学报（自然科学版），2002，42（4）：477-480.4Eggert D W, Lorusso A, Fisher R B. Estimating 3-D Rigid Body Transformations: a

19、Comparision of Four Major AlgorithmsJ. Machine Vision and Application,1997,9:272-290.5B K P Horn. Closed-form Solution of Absolute Orientaion Using Quite QuaternionJ. Journal Optical of Society American A, 1987, 4(4);629-642.6 任同群，邾继贵，李艳军，叶声华. 形貌测量中立体图像拼接的关键技术J. 机械工程学报，2008, 44(5): 137-141.7Besl P J, Mckay N D. A Method for Registration of 3-D ShapesJ. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992,14(2): 239-256.8 Rusinkiewicz S, Levoy M, Efficient Variants of The ICP AlgorithmA, Proceedings of the 3rd International Conference on 3D Digital Imaging and Modeling, Qu