迭代最近点算法综述

迭代最近点算法综述摘要：三维点集配准问题是计算机技术中的一个极其重要的问题，作为解决三维点集配准问题的一个应用较为广泛的算法，ICP算法得到了研究者的关注，本文以一种全新的思路从配准元素的选择、配准策略的确定和误差函数的求解等3个方面对三维点集配准的ICP算法的各种改进和优化进行了分类和总结。关键词：三维点集；迭代最近点；配准1引言在计算机应用领域，三维点集配准是一个非常重要的中间步骤，它在表面重建、三维物体识别、相机定位等问题中有着极其重要的应用［1］。对于三维点集配准问题，研究者提出了很多解决方案，如点标记法、自旋图像、主曲率方法、遗传算法、随机采样一致性算法等等，这些算法各有特色，在许多特定的情况下能够解决配准的问题。但是应用最广泛的，影响最大的还是由Besl和Mckay在1992年提出的迭代最近点算法［2］(IterativeClosestPoint，ICP)，它是基于纯粹几何模型的三维物体对准算法，由于它的强大功能以及高的精确度，很快就成为了曲面配准中的主流算法。随着ICP算法的广泛应用，许多研究者对ICP算法做了详细的研究，分析了该算法的缺陷和特点，提出了许多有价值的改进，推动了这一重要算法的发展。本文着眼于ICP算法的发展历程，详细介绍了ICP算法的基本原理，总结其发展和改进的过程，对于该算法的各个阶段的发展和变化做了简单的论述。2ICP算法原理2.1ICP算法原理ICP算法主要用于三维物体的配准问题，可以理解为：给定两个来至不同坐标系的三维数据点集，找出两个点集的空间变换，以便它们能进行空间匹配。假定用二一％表示空间第一个点集，第二个点集的对齐匹配变换为使下式的目标函数最小［3］N®)-£|||QL(RPi+T)|H-min (1)TlICP算法的实质是基于最小二乘法的最优匹配算法，它重复进行“确定对应关系点集一计算最优刚体变换”的过程，直到某个表示正确匹配的收敛准则得到满足。ICP算法的母的是找到目标点集与参考点之间的旋转R和平移T变换，使得两匹配数据中间满足某种程度度量准则下的最优匹配。假设目标点集P的坐标为"」二--*｝及参考点集Q的坐标为

{'"」「’，「},在第k次迭代中计算与点集P的坐标相对应的对应点坐标为：jlj-1■' ,计算P与。'之间的变换矩阵并对原变换进行更新，直到数据间平均距离小于给定值T,即满足式（1）最小。具体步骤［4］：(1)(2)(1)(2)(3)(4)(5)(6)计算参考点集Q中对应点疽"/，使*伊_|lil；计算旋转矩阵*与平移向量I'，使得、一疽11"；计算-il' I',I'S■；计算*'"."；jb1 jb+1如果• 不小于给定的T返回到（2）,直到• ■ 或迭代次数大于预设的最大的迭代次数为止。对于ICP的每次迭代，最小化对应点的均方差使得点集’更接近L「，而疽是、•在"的最近点。这样，每一次迭代就使得'更接近于"。基于这样的思想，Besl等人证明了ICP算法的收敛性。2.2ICP算法特性分析在三维点集配准的各种应用中，ICP算法的使用非常广泛，这是由于ICP算法有以下优点：：可以获得非常精确的配准效果；可以处理三维点集、参数曲面等多种形式表达的曲面，也就是说该算法对曲面表示方法独立［5］；不必对待处理的点集进行分割和特征提取；在较好的初值情况下，可以得到很好的算法收敛性［6］。虽然其得到了广泛的应用，但是对于最初的ICP算法，存在很多的不足之处，主要表现在：算法假设其中一个点集是另一个点集的子集，也就是说，一个点集必须含在另一个点集中，这一要求在很多时候难以满足；该算法在搜索对应点的过程中，计算代价非常的大；在基本的ICP算法中，在寻找对应点的时候，认为欧氏距离最近的点就是对应点，这种假设是比较武断的，它会产生一定数量的错误对应点［7］。针对上面的一些问题，许多研究者提出了ICP算法的各种改进版本。为了说明ICP算法的不同改进版本，有必要将ICP算法分成几个阶段来讨论，在各个阶段的划分，国内外的研究学者也提出了自己的看法。主要的划分方法有，在Rusinkiewicz［8］的文章中，将ICP算法的进行分成了六个阶段，分别为：点集的选择、对应点对的配准、点对的权重确定、特定点对的剔除、误差矩阵的建立、误差矩阵最小化的求解；伍毅9］则将其分为四个阶段：重采样、空间查找及距离度量、目标度量函数最小化和算法的迭代；Nishino［i0］认为，不同的改进方法的差异不过体现在三个方面：配准策略、配准元素和误差度量。通过比较国内外学者提出的各种ICP算法的改进算法，可以知道，Nishino的划分方法可以很好的反应算法所做改变的各个阶段。所以，在本文中将围绕ICP算法配准元素的选择、配准策略的确定和误差函数的求解等三个方面做的改进来展开。3配准元素的选择在标准ICP算法中，选用点集中的所有点来计算对应的点，但是通常用于配准的点集元素数量都是非常巨大的，通过这些点集来计算，所消耗的时间也是很长的。所以在后来的研究当中，提出了各种各样的方法来选择配准元素，这些算法的主要目的无一例外的是为了减小点集元素的数目，即对匹配点集进行采样。既然涉及到采样，就有多种采样方法被尝试使用。Turk使用了一致采样方法［ii］，Masuda［i2］使用的式随机采样方法，而且在每一的迭代过程中都要进行随机采样获取不同的采样点进行计算。也有一些学者提出了一些新的采样方法，这些方法主要特点是会利用点集的特征信息来减少点的数目，运用一些具有明显特征的点集来进行配准。比如，Weik［13］在文献中提到的，利用图像的梯度信息来选择符合要求的点，再用这些点来完成配准。Sappa［14］则是采用了另外一种策略，直接选取边缘点作为配准的选择点，这样就可以大大的减小配准点的数目。通过上面的分析可以发现，配准元素的选择的改进，主要集中在如何减小配准点的数目方面，即如何用最少的点来表征原始点集的全部特征信息。4配准策略的确定上面介绍了ICP算法在配准元素选择方面做得一些改进，而更多的改进集中在配准策略方面。具体的配准策略包括特征度量的选取和搜索策略的选取方面。特征度量的选取要寻找对应点对，就必须寻找场景数据点和模型数据点的特征差异，这就需要对特征进行度量。在利用特征度量获得对应点以后，还需要利用特征度量建立迭代优化的目标函数，为误差函数的求解奠定基础［15］。ICP算法被提出来时，采用的是欧氏距离作为特征度量，所以在这一阶段的改进方面，主要是围绕距离展开，很多研究者在这方面提出了自己的改进想法，当然有一些也并没有采用距离作为特征度量，在下面会做详细的介绍。点到点的距离在标准ICP算法中，Besl和McKay直接采用的是点到点的欧氏距离。首先利用点到点的最小欧氏距离得到点到集合的距离，从而寻找到对应点，再对这些对应点到集合的距离进行求和得到求解刚体变换的目标函数，如(1)式所示。简而言之，标准ICP算法使用的是点到点(point-to-point)的距离。点到平面的距离Chen［16］利用的是场景点集中的点的法线与模型点集合的交点来确定对应点，得到对应点后，目标函数则采用的是点到面(point-to-plane)的距离，点到面的距离是指，场景数据集中的点到模型数据集合中的经过对应点的切平面的距离，如图l所示。场景点P中的点I，它的法线与模型点集X的交点：就被选择为I■■的对应点。在建立目标函数时，使用的并不是11到的距离，而是I’到模型点集X过的切平面的距离。图1点到平面的距离点到平面的距离减少了迭代次数，能够以更快的速度收敛到给定的阈值。Pulli对点到点的方法和点到面的方法进行了对比讨论［17］，他们指出与点到点的ICP算法相比，运用点到平面的距离的方法大大减少了计算量以及迭代次数，但是该方法的鲁棒性并不是太好。与上面的度量标准相类似的还有点到三角形的距离，它运用点与点之间的邻接信息，将三维点集三角化，以点到三角形表面的距离作为特征度量，与点到面的距离有一些相似，主要由张鸿宾和谢丰在文献中提出［18］。豪斯多夫（Hausdorff）距离Hausdorff距离［19］作为一种距离测度，常用于衡量两个点集之间的相似程度。由于使用Hausdorff距离作为距离测度时无需考虑两个点集中的点与点之间的对应关系，因此可以有效解决当图像中存在噪声和目标被部分遮挡时的识别问题。Ezras］研究了使用Hausdorff距离在ICP中的一些理论结果，还没有进行配准的实际应用。几何特征严格的说，距离也是一种几何特征，这里指的几何特征是指除距离以外的几何特征。主要有法相量［21］、曲率等特征。加入几何特征更多的是为了在确定点对时加入限制条件，尽量减小误差点的数目。Pulli在文献中就加入了给定点对的限制条件，其中一个是每个点对对应的法向矢量差不能超过45度，而Godina则是通过曲率来构造候选兼容点集。图2就是通过原始ICP算法和加入法相限制条件后获取的点对情况，其中空心箭头表示法相矢量方向，黑色箭头表示找到的对应点对。（a） （b）图2对应点对（a）通过传统ICP方法获得（b）中加入了法矢限制条件通过加入几何特征的限制条件，可以进一步的降低找到错误点对的概率，同时加入几何特征后，可以非常迅速的确定候选点集，可以大大的提高搜索速度。4.2搜索策略在对应点的选取，也就是构造各对应点的过程中，需要进行大量的搜索过程，这是传统ICP算法的瓶颈，为了提高ICP算法的效率，提高搜索速度是很有必要的，所以如何改进搜索策略也是ICP算法研究的热点。Zhang在其论文中采用了多维二元搜索树［23］（K-DTree），该算法可以自动的踢出异常值，可以处理非完全对应的点集合。Greenspan分析了该树的特性，提出了近似多维二元搜索树［24］（AK-DTree），达到了近似的效果，并提高了效率。另一种方法是依靠金字塔原理提出来的分级收缩算法［25］，大大加快了搜索速度。该方法通过评估目标区域距离值的方差和均匀拓扑映射来选择区域，在点集中进行逐级的收缩，先进行粗略定位，最后获取准确地对应点，对于搜索效率有很大的提高。投影的方法也被应用到ICP算法中来，Blais和Neugbeuaer采用反向定标［26］（ReverseCalibration）技术，就是使用的投影搜索算法。Benjemaa［27］则采用了具有多个投影平面的Z-buffer方法进行投影搜索。5误差函数求解误差函数的求解，也就是目标函数的最小化，是ICP算法的最后一个阶段。在求得目标函数后应该采用什么样的方法来求解目标函数，使其值能最快最准的的收敛到最小，也是一个比较重要的问题。传统的ICP算法的目标函数是通过点对点的距离建立的，其求解方法有基于奇异值分解的方法、四元数方法、正交矩阵法［28］和双四元数方法［29］。Eggerts］评估了上述四种方法的精确性和稳定性，并且说明了这些方法存在的差异。由于基于奇异值分解的方法和四元数方法应用的更加广泛，所以，在下面将对这两种方法的实现方式做具体的介绍。5.1 基于奇异值分解的方法用奇异值分解法（SVD方法）来求解ICP算法过程中的几何参数最初是由ARUN［31等提出来的，其并没有建立目标函数等式，而是通过矩阵变换的相关性质，直接求解出最优的参数解。该方法实现起来比较简单，而且计算结果也比较准确，下面就对相关原理进行论述。在运用SVD方法之前，我们默认已经通过了点对的搜索环节，而且已经准确的找了各个对应点对。我们认为有两组点，模型点和采集到的点，模型点定义为'一顷''••••',n为点的数目。假设要求的旋转矩阵是R，平移矩阵是T，理想情况下通过'变换得到的对应点位『*，有下面的等式：P；=RPj+T+凹R变换的旋转角度值；T变换的平移值；Ni噪声。对于这N个点，现在我们已经找到每个点对，对于每个点在变换前后的值都可以非常清楚地知道，根据式（1）,可以得到下面的欧氏距离和。由ICP算法的原理可知，欧氏距离最小的点就是采集点在模型中的对应的点，所以基本ICP算法就是求解上面的代数式，使代数式的值最小的R和T就是要求的旋转角度和平移值。而对上面的欧氏距离和，我们可以进行化简。先计算模板点和数据点的重心P岳p'=耘显然有p=R*p+I ⑶令I：二一「，土——,」，代入式（2），则有Z2=IIqi-RqiII对于（3）式右边进行分解，可以得到下式。=Jqi-Rqi）'（qi-RqJ=E：+q&|-2qi'Rqi)通过上面的等式，我们可以发现，要使^'的值达到最大，等价于使下式最大。_Tr函已1明沌')=Trace(RH)其中，什么样的情况下Trace（RH）才能最大呢？这是接下来要讨论的问题。假设-、"「是一个正定矩阵，B为正交矩阵，是A中的第i列，则有Tracc（BAA9=Tracc（A'BA）=由施瓦茨不等式可以得到，讯时）三瑚矗原日网）=a%所以有，

Trace(BAA1Trace(BAA1)<£*比=Trace(AA^)在求取F的最大值时，我们可以效仿上面的定理，先对H进行SVD分解，可以得到。H=UAV［其中U和V为正交矩阵，•"•为非负的对角矩阵。我们可以令""，当然，X也为正交矩阵，则有XH-VUtUAVt-VAVh (4)XH是一个对称正定矩阵，而由上面的证明，我们可以知道，对于任意的正交矩阵B，有Trace(XFI)>Traci?(时XH)通过上式，我们可以发现，当R取XH时，F将达到最大值。所以可以求出R。则SVD方法进行的步骤可以归纳如下。1、 通过!「一；,「；L计算］■，以及".和E：。P= 〕P」 P=如qi=P.-p qi-Pi-p2、 计算矩阵H，通过式NH=i=i3、 对H进行SVD分解。HUA寸4、 求解旋转矩阵。R-VU15、 计算平移矩阵T。T=p_R#p该算法不适合运用于线性的和有奇异点的数据集。5.2 四元数方法Horn等［32］提出了基于单位四元数的计算运动参数的方法。旋转矩阵R用一个单位四元数q来表示：R=R(q),其中设单位四元数-:,其中，一一+q：-I,而且■'■-",则有这个单位四元数产生的旋转矩阵为［33］：+ - 2*gw+qoq；j)'R=2*(Qi92+qoQs) q希-q¥+q*-q52*Sq，-qoqi)虹—"Eg疏项-艮刷 (5)定义平移向量为’山，• ，并由"和：组成一个配准状态向量,=I。点集的重心分别为p和，则两点集的协方差如下:跖=跖=畚二1[(PlP)(QlP)1(6)根据三卜得出一个反对称矩阵A，其元素为' %', -|p ■，由A的三个循环元素又组成了一个列向量'一■■元素又组成了一个列向量'一■■-1最后，由以上矩阵和向量组成对称矩阵Q冲Q冲其中为3X3单位矩阵。求解对称矩阵」,'ri•的特征值和特征向量，所得最大特征值所对应的特征向量即为旋转四元数q.-M--：。计算平移向量・[•-「—K匚最终生成一个配准向量q。6总结本文从配准元素的选择、配准策略的确定和误差函数的求解等三个方面对ICP算法的各种改进和优化进行了分类和总结。通过文中的分析可以发现，icp在这些年的发展过程中，将各种技术吸收进来，这一方面说明了ICP算法以其本身的优势获得了研究者的关注，另一方面也说明研究者在对ICP算法改进上付出了不懈的努力但是ICP算法的研究还没有停止，因为这种算法还不能解决所有的配准问题，也将还会有人继续对这种算法展开研究，让其变得更加完美。参考文献罗纲，罗斌.图象特征点集配准的加权相关迭代算法[J].中国图象图形学报.2000(09):47-50.BeslPJ,MckayHD.Amethodforregistrationof3-Dshapes[J].PatternAnalysisandMachineIntelligence,IEEETransactionson.1992,14(2):239-256.蒋成成，胡同森，周维.一种改进的迭代最近点算法[J].计算机系统应用.2009(08):84-87.张波.基于ICP和SVD的眼底图像配准研究[D].吉林大学,2009.李必卿，蔡勇.一种改进的ICP算法在多视配准中的应用[J].机械工程师.2009(02):73-75.任治新，罗诗途，吴美平，等.基于改进ICP算法的地磁图匹配技术[J].计算机应用.2008(S1):351-354.刘承香，阮双琛，刘繁明，等.基于迭代最近点算法的地形匹配算法可靠性分析[J].深圳大学学报.2005(01):22-26.RusinkiewiczS,LevoyM.EfficientvariantsoftheICPalgorithm[C].2001.伍毅.三维扫描信息获取的深度图像配准算法设计及开发[D].浙江大学,2005.NishinoK,IkeuehiK.Robustsimultaneousregistrationofmultiplerangeimagescomprisingalargenumberofpoints[J].ElectronicsandCommunicationsinJapan(PartII:Electronics).2004,87(8):61-74.G.Turk,M.LevoyZipperedPolygonMeshesfromRangeImages[C].ProceedingsofSIGGRAPH1994:311-318.MasudaT,SakaueK,YokoyaN.Registrationandintegrationofmultiplerangeimagesfor3-Dmodelconstruction[C].1996.WeikS.Registrationof3-Dpartialsurfacemodelsusingluminanceanddepthinformation[C].1997.SappaA,Restrepo-spechtA,UevyM.Rangeimageregistrationbyusinganedge-basedrepresentation[C].Proceedingsofthe9thInternationalSymposiumonIntelligentRohotic.Toulouse;France:2001.张同刚，岑敏仪，冯义从.用于无控制DEM匹配的LZD和ICP算法的比较[J].中国图象图形学报.2006(05):714-719.ChenY,MedioniG.Objectmodelingbyregistrationofmultiplerangeimages[C].1991.PulliK.Multiviewregistrationforlargedatasets[C].1999.张鸿宾，谢丰.基于表面间距离度量的多视点距离图像的对准算法 [J].中国科学E辑:信息科学.2005(02):150-160.杨清夙，游志胜，张先玉.基于豪斯多夫距离的快速多人脸检测算法[J].电子科技大学学报.2004(04):407-409.EzraE,SharirM,EfratA.OntheperformanceoftheICPalgorithm[J].ComputationalGeometry.2008,41(1-2):77-93.BemardiniF,MittlemanJ,RnshmeierH,etal.Theball-pivotingalgorithmforsurfacereconstruction[J].VisualizationandComputerGraphics,IEEETransactionson.1999,5(4):349-359.GodinP,BoulangerG.Rangeimageregistrationthroughviewpointinvariantcomputationofcurvature[C].ProceedingsofISPRS,1995:170—175.ZhangZ.Iterativepointmatchingforregistrationoffree-formcurvesandsurfaces[J].InternationalJournalofComputerVision.1994,13(2):119-152.GreenspanM,YurickM.Approximatek-dtreesearchforefficientICP[C].2003.OkudaH.HM-ICP:Fast3-DRegistrationAlgorithmwithHierarchicalandRegionSelectionApproachofM-ICP[C].JournalofRoboticsandMechatronics