迭代最近点算法综述

迭代最近点算法综述摘要：三维点集配准问题是计算机技术中的一个极其重要的问题，作为解决三维点集配准问题的一个应用较为广泛的算法，ICP算法得到了研究者的关注，本文以一种全新的思路从配准元素的选择、配准策略的确定和误差函数的求解等3个方面对三维点集配准的ICP算法的各种改进和优化进行了分类和总结。关键词：三维点集；迭代最近点；配准1引言在计算机应用领域，三维点集配准是一个非常重要的中间步骤，它在表面重建、三维物体识别、相机定位等问题中有着极其重要的应用[1]。对于三维点集配准问题，研究者提出了很多解决方案，如点标记法、自旋图像、主曲率方法、遗传算法、随机采样一致性算法等等，这些算法各有特色，在许多特定的情况下能够解决配准的问题。但是应用最广泛的，影响最大的还是由Besl和Mckay在1992年提出的迭代最近点算法[2]（IterativeClosestPoint，ICP），它是基于纯粹几何模型的三维物体对准算法，由于它的强大功能以及高的精确度，很快就成为了曲面配准中的主流算法。随着ICP算法的广泛应用，许多研究者对ICP算法做了详细的研究，分析了该算法的缺陷和特点，提出了许多有价值的改进，推动了这一重要算法的发展。本文着眼于ICP算法的发展历程，详细介绍了ICP算法的基本原理，总结其发展和改进的过程，对于该算法的各个阶段的发展和变化做了简单的论述。2ICP算法原理2.1ICP算法原理ICP算法主要用于三维物体的配准问题，可以理解为：给定两个来至不同坐标系的三维数据点集，找出两个点集的空间变换，以便它们能进行空间匹配。假定用{Pi,i=1,2,…,N}表示空间第一个点集，第二个点集的对齐匹配变换为使下式的目标函数最小[3]。f(R,t)=∑||Qi−(RPi+T)||2Ni=1=min(1)ICP算法的实质是基于最小二乘法的最优匹配算法，它重复进行“确定对应关系点集—计算最优刚体变换”的过程，直到某个表示正确匹配的收敛准则得到满足。ICP算法的母的是找到目标点集与参考点之间的旋转R和平移T变换，使得两匹配数据中间满足某种程度度量准则下的最优匹配。假设目标点集P的坐标为{Pi,i=1,2,…,NP}及参考点集Q的坐标为{Qi,i=1,2,…,Nq}，在第k次迭代中计算与点集P的坐标相对应的对应点坐标为{Qik,i=1,2,…,NP}，计算P与Qk之间的变换矩阵并对原变换进行更新，直到数据间平均距2离小于给定值τ，即满足式（1）最小。具体步骤[4]：（1）在目标点集P中取点集Pik∈P；（2）计算参考点集Q中对应点Qik∈Qk，使‖Qik−Pik‖=min；（3）计算旋转矩阵Rk与平移向量Tk，使得∑‖RkPik+Tk−Qik‖2ni=1=min；（4）计算Pk+1={Pik+1=RkPik+Tk，Pik∈P}；（5）计算dk+1=1n∑‖Pik+1−Qik‖2ni=1；（6）如果dk+1不小于给定的τ返回到（2），直到dk+1τ或迭代次数大于预设的最大的迭代次数为止。对于ICP的每次迭代，最小化对应点的均方差使得点集Pik更接近Qik，而Qik是Pik在Qi的最近点。这样，每一次迭代就使得Pi更接近于Qi。基于这样的思想，Besl等人证明了ICP算法的收敛性。2.2ICP算法特性分析在三维点集配准的各种应用中，ICP算法的使用非常广泛，这是由于ICP算法有以下优点：可以获得非常精确的配准效果；可以处理三维点集、参数曲面等多种形式表达的曲面，也就是说该算法对曲面表示方法独立[5]；不必对待处理的点集进行分割和特征提取；在较好的初值情况下，可以得到很好的算法收敛性[6]。虽然其得到了广泛的应用，但是对于最初的ICP算法，存在很多的不足之处，主要表现在：算法假设其中一个点集是另一个点集的子集，也就是说，一个点集必须含在另一个点集中，这一要求在很多时候难以满足；该算法在搜索对应点的过程中，计算代价非常的大；在基本的ICP算法中，在寻找对应点的时候，认为欧氏距离最近的点就是对应点，这种假设是比较武断的，它会产生一定数量的错误对应点[7]。针对上面的一些问题，许多研究者提出了ICP算法的各种改进版本。为了说明ICP算法的不同改进版本，有必要将ICP算法分成几个阶段来讨论，在各个阶段的划分，国内外的研究学者也提出了自己的看法。主要的划分方法有，在Rusinkiewicz[8]的文章中，将ICP算法的进行分成了六个阶段，分别为：点集的选择、对应点对的配准、点对的权重确定、特定点对的剔除、误差矩阵的建立、误差矩阵最小化的求解；伍毅[9]则将其分为四个阶段：重采样、空间查找及距离度量、目标度量函数最小化和算法的迭代；Nishino[10]认为，不同的改进方法的差异不过体现在三个方面：配准策略、配准元素和误差度量。通过比较国内外学者提出的各种ICP算法的改进算法，可以知道，Nishino的划分方法可以很好的反应算法所做改变的各个阶段。所以，在本文中将围绕ICP算法配准元素的选择、配准策略的确定和误差函数的求解等三个方面做的改进来展开。3配准元素的选择在标准ICP算法中，选用点集中的所有点来计算对应的点，但是通常用于配准的点集元素数量都是非常巨大的，通过这些点集来计算，所消耗的时间也是很长的。所以在后来的3研究当中，提出了各种各样的方法来选择配准元素，这些算法的主要目的无一例外的是为了减小点集元素的数目，即对匹配点集进行采样。既然涉及到采样，就有多种采样方法被尝试使用。Turk使用了一致采样方法[11]，Masuda[12]使用的式随机采样方法，而且在每一的迭代过程中都要进行随机采样获取不同的采样点进行计算。也有一些学者提出了一些新的采样方法，这些方法主要特点是会利用点集的特征信息来减少点的数目，运用一些具有明显特征的点集来进行配准。比如，Weik[13]在文献中提到的，利用图像的梯度信息来选择符合要求的点，再用这些点来完成配准。Sappa[14]则是采用了另外一种策略，直接选取边缘点作为配准的选择点，这样就可以大大的减小配准点的数目。通过上面的分析可以发现，配准元素的选择的改进，主要集中在如何减小配准点的数目方面，即如何用最少的点来表征原始点集的全部特征信息。4配准策略的确定上面介绍了ICP算法在配准元素选择方面做得一些改进，而更多的改进集中在配准策略方面。具体的配准策略包括特征度量的选取和搜索策略的选取方面。4.1特征度量的选取要寻找对应点对，就必须寻找场景数据点和模型数据点的特征差异，这就需要对特征进行度量。在利用特征度量获得对应点以后，还需要利用特征度量建立迭代优化的目标函数，为误差函数的求解奠定基础[15]。ICP算法被提出来时，采用的是欧氏距离作为特征度量，所以在这一阶段的改进方面，主要是围绕距离展开，很多研究者在这方面提出了自己的改进想法，当然有一些也并没有采用距离作为特征度量，在下面会做详细的介绍。4.1.1点到点的距离在标准ICP算法中，Besl和McKay直接采用的是点到点的欧氏距离。首先利用点到点的最小欧氏距离得到点到集合的距离，从而寻找到对应点，再对这些对应点到集合的距离进行求和得到求解刚体变换的目标函数，如(1)式所示。简而言之，标准ICP算法使用的是点到点（point-to-point）的距离。4.1.2点到平面的距离Chen[16]利用的是场景点集中的点的法线与模型点集合的交点来确定对应点，得到对应点后，目标函数则采用的是点到面(point-to-plane)的距离，点到面的距离是指，场景数据集中的点到模型数据集合中的经过对应点的切平面的距离，如图l所示。场景点P中的点pi，它的法线与模型点集X的交点qi就被选择为pi的对应点。在建立目标函数时，使用的并不是pi到qi的距离，而是pi到模型点集X过qi的切平面的距离。4图1点到平面的距离点到平面的距离减少了迭代次数，能够以更快的速度收敛到给定的阈值。Pulli对点到点的方法和点到面的方法进行了对比讨论[17]，他们指出与点到点的ICP算法相比，运用点到平面的距离的方法大大减少了计算量以及迭代次数，但是该方法的鲁棒性并不是太好。与上面的度量标准相类似的还有点到三角形的距离，它运用点与点之间的邻接信息，将三维点集三角化，以点到三角形表面的距离作为特征度量，与点到面的距离有一些相似，主要由张鸿宾和谢丰在文献中提出[18]。4.1.3豪斯多夫(Hausdorff)距离Hausdorff距离[19]作为一种距离测度，常用于衡量两个点集之间的相似程度。由于使用Hausdorff距离作为距离测度时无需考虑两个点集中的点与点之间的对应关系，因此可以有效解决当图像中存在噪声和目标被部分遮挡时的识别问题。Ezra[20]研究了使用Hausdorff距离在ICP中的一些理论结果，还没有进行配准的实际应用。4.1.4几何特征严格的说，距离也是一种几何特征，这里指的几何特征是指除距离以外的几何特征。主要有法相量[21]、曲率等特征。加入几何特征更多的是为了在确定点对时加入限制条件，尽量减小误差点的数目。Pulli在文献中就加入了给定点对的限制条件，其中一个是每个点对对应的法向矢量差不能超过45度，而Godin[22]则是通过曲率来构造候选兼容点集。图2就是通过原始ICP算法和加入法相限制条件后获取的点对情况，其中空心箭头表示法相矢量方向，黑色箭头表示找到的对应点对。（a）（b）图2对应点对（a）通过传统ICP方法获得（b）中加入了法矢限制条件通过加入几何特征的限制条件，可以进一步的降低找到错误点对的概率，同时加入几何特征后，可以非常迅速的确定候选点集，可以大大的提高搜索速度。54.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]。Eggert[30]评估了上述四种方法的精确性和稳定性，并且说明了这些方法存在的差异。由于基于奇异值分解的方法和四元数方法应用的更加广泛，所以，在下面将对这两种方法的实现方式做具体的介绍。5.1基于奇异值分解的方法用奇异值分解法（SVD方法）来求解ICP算法过程中的几何参数最初是由ARUN[31]等提出来的，其并没有建立目标函数等式，而是通过矩阵变换的相关性质，直接求解出最优的参数解。该方法实现起来比较简单，而且计算结果也比较准确，下面就对相关原理进行论述。在运用SVD方法之前，我们默认已经通过了点对的搜索环节，而且已经准确的找了各个对应点对。我们认为有两组点，模型点和采集到的点，模型点定义为{Pi,i=1,2,3…,N},N为点的数目。假设要求的旋转矩阵是R，平移矩阵是T，理想情况下通过Pi变换得到的对应点位Pi′，有下面的等式：Pi′=RPi+T+NiR变换的旋转角度值；