迭代最近点算法综述

《迭代最近点算法综述》由会员分享，可在线阅读，更多相关《迭代最近点算法综述（9页珍藏版）》请在金锄头文库上搜索。

1、迭代最近点算法综述摘要：三维点集配准问题是计算机技术中的一个极其重要的问题，作为解决三维点集配准问题的一个应用 较为广泛的算法，ICP算法得到了研究者的关注，本文以一种全新的思路从配准元素的选择、配准策 略的确定和误差函数的求解等3个方面对三维点集配准的ICP算法的各种改进和优化进行了分类和总 结。关键词：三维点集；迭代最近点：隗准1 引言在计算机应用领域，三维点集配准是一个非常重要的中间步骤，它在表面重建、三维物 体识别、相机定位等问题中有着极其重要的应用七对于三维点集配准问题，研究者提出了 很多解决方案，如点标记法、自旋图像、主曲率方法、遗传算法、随机采样一致性算法等等， 这些算法各有特色

2、，在许多特定的情况卜.能够解决配准的问题。但是应用最广泛的，影响最 大的还是由Besl和Mckay在1992年提出的迭代最近点算法p(Iterative ClosestPouit,ICP), 它是基于纯粹几何模型的三维物体对准算法，由于它的强大功能以及高的精确度，很快就成 为了曲面配准中的主流算法。随着ICP算法的广泛应用，许多研究者对ICP算法做了详细的研究，分析了该算法的 缺陷和特点，提出了许多有价值的改进，推动了这一重要算法的发展。本文着眼于ICP算 法的发展历程，详细介绍了 ICP算法的基本原理，总结其发展和改进的过程，对于该算法 的各个阶段的发展和变化做了简单的论述。2 ICP算法原

3、理2.1 ICP算法原理ICP算法主要用于三维物体的配准问题，可以理解为：给定两个来至不同坐标系的三维 数据点集，找出两个点集的空间变换，以便它们能进行空间匹配。假定用品i=l,2，,N 表示空间第一个点集，第二个点集的对齐匹配变换为使下式的目标函数最小。Nf(Rt)= |Qj (明+T)|2 = min(1)i=lICP算法的实质是基于最小二乘法的最优匹配算法，它重复进行“确定对应关系点集一 计算最优刚体变换”的过程，直到某个表示正确匹配的收敛准则得到满足oICP算法的母的 是找到目标点集与参考点之间的旋转R和平移T变换，使得两匹配数据中间满足某种程度 度量准则下的最优匹配。假设目标点集P的

4、坐标为Pifi= 1,2，,Np及参考点集Q的坐标为 Qi，i=L2，,Nq,在第k次迭代中计算与点集P的坐标相对应的对应点坐标为 Qjk,i=l,2，,Np,计算P与Qk之间的变换矩阵并对原变换进行更新，直到数据间平均距 离小于给定值T ,即满足式（1）最小。具体步骤田：（1）在目标点集P中取点集昨e P：（2）计算参考点集Q中对应点Qi e Qk,使|Qjk - Rk| = min；（3）计算旋转矩阵史与平移向量T、使得*LRkRk + TkQ|2 = min：（4）计算Pk+l = 砂+1 = RkRk + 丁七 Rk e p.（5）计算 dk+l=曲 |Pjk+l_Qjk|2；（6）如

5、果罪+1不小于给定的T返回到（2）,直到dk+1 T或迭代次数大于预设的最 大的迭代次数为止。对于ICP的每次迭代，最小化对应点的均方差使得点集耳14更接近Qi、而Qk是Rk在Q的 最近点。这样，每一次迭代就使得R更接近于Qi。基于这样的思想，Besl等人证明了 ICP算 法的收敛性。2.2 ICP算法特性分析在三维点集配准的各种应用中，ICP算法的使用非常广泛，这是由于ICP算法有以下优 点： 可以获得非常精确的配准效果； 可以处理三维点集、参数曲面等多种形式表达的曲面，也就是说该算法对曲面表示 方法独立性 不必对待处理的点集进行分割和特征提取； 在较好的初值情况下，可以得到很好的算法收敛性

6、回。虽然其得到了广泛的应用，但是对于最初的ICP算法，存在很多的不足之处，主要表 现在： 算法假设其中一个点集是另一个点集的子集，也就是说，一个点集必须含在另一个 点集中，这一要求在很多时候难以满足； 该算法在搜索对应点的过程中，计算代价非常的大： 在基本的ICP算法中，在寻找对应点的时候，认为欧氏距离最近的点就是对应点， 这种假设是比较武断的，它会产生一定数量的错误对应点针对上面的一些问题，许多研究者提出了 ICP算法的各种改进版本。为了说明ICP算 法的不同改进版本，有必要将ICP算法分成几个阶段来讨论，在务个阶段的划分，国内外 的研究学者也提出了自己的看法。主要的划分方法有，在Rusin

7、kiewicz冏的文章中，将ICP 算法的进行分成了六个阶段，分别为：点集的选择、对应点对的配准、点对的权重确定、特 定点对的剔除、误差矩阵的建立、误差矩阵最小化的求解；伍毅啊则将其分为四个阶段：重 采样、空间查找及距离度量、目标度量函数最小化和算法的迭代；Nishino认为，不同的 改进方法的差异不过体现在三个方面：配准策略、配准元素和误差度量。通过比较国内外学者提出的各种ICP算法的改进算法，可以知道，Nishin。的划分方法 可以很好的反应算法所做改变的各个阶段。所以，在本文中将围绕ICP算法配准元素的选 择、配准策略的确定和误差函数的求解等三个方面做的改进来展开。3配准元素的选择在标准

8、ICP算法中，选用点集中的所有点来计算对应的点，但是通常用于配准的点集 元素数量都是非常巨大的，通过这些点集来计算，所消耗的时间也是很长的。所以在后来的 研究当中，提出了各种各样的方法来选择配准元素，这些算法的主要目的无一例外的是为了 减小点集元素的数目，即对匹配点集进行采样。既然涉及到采样，就有多种采样方法被尝试使用。Turk使用了一致采样方法凹， Masuda1121使用的式随机采样方法，而且在每一的迭代过程中都要进行随机采样获取不同的 采样点进行计算。也有一些学者提出了一些新的采样方法，这些方法主要特点是会利用点集的特征信息来 减少点的数目，运用一些具有明显特征的点集来进行配准。比如，W

9、eik131在文献中提到的， 利用图像的梯度信息来选择符合要求的点，再用这些点来完成配准。Sappa则是采用了另 外一种策略，直接选取边缘点作为配准的选择点，这样就可以大大的减小配准点的数目。通过上面的分析可以发现，配准元素的选择的改进，主要集中在如何减小配准点的数目 方面，即如何用最少的点来表征原始点集的全部特征信息。4配准策略的确定上面介绍了 ICP算法在配准元素选择方面做得一些改进，而更多的改进集中在配准策 略方面。具体的配准策略包括特征度量的选取和搜索策略的选取方面。4.1 特征度的选取要寻找对应点对，就必须寻找场景数据点和模型数据点的特征差异，这就需要对特征进 行度量。在利用特征度量

10、获得对应点以后，还需要利用特征度量建立迭代优化的目标函数, 为误差函数的求解奠定基础凹。ICP算法被提出来时，采用的是欧氏距离作为特征度量，所以在这一阶段的改进方面, 主要是困绕距离展开，很多研究者在这方面提出了自己的改进想法，当然有一些也并没有采 用距离作为特征度量，在下面会做详细的介绍。4.1.1 点到点的距离在标准ICP算法中，Besl和McKay直接采用的是点到点的欧氏距离。首先利用点到点 的最小欧氏距离得到点到集合的距离，从而寻找到对应点，再对这些对应点到集合的距离进 行求和得到求解刚体变换的目标函数，如(1)式所示。简而言之，标准ICP算法使用的是点 到点(point-to-poi

11、nt)的距离。4.1.2 点到平面的距离Chen四利用的是场景点集中的点的法线与模型点集合的交点来确定对应点，得到对应 点后，目标函数则采用的是点到面(point-to-plane)的距离，点到面的距离是指，场景数据集 中的点到模型数据集合中的经过对应点的切平面的距离，如图1所示。场景点P中的点p” 它的法线与模型点集X的交点就被选择为小的对应点。在建立目标函数时，使用的并不是 Pi到疆的距离，而是小到模型点集X过的切平面的距离。图1点到平面的距离点到平面的距离减少了迭代次数，能够以更快的速度收敛到给定的阈值。Pulll对点到 点的方法和点到面的方法进行了对比讨论阿，他们指出与点到点的ICP算

12、法相比，运用点 到平面的距离的方法大大减少了计算量以及迭代次数，但是该方法的鲁棒性并不是太好。与上面的度量标准相类似的还有点到三角形的距离，它运用点与点之间的邻接信息，将 三维点集三角化，以点到三角形表面的距离作为特征度量，与点到面的距离有一些相似，主 要由张鸿宾和谢丰在文献中提出。4.1.3 豪斯多夫(Hausdorff)距离Hausdorff距离作为一种距离测度，常用于衡量两个点集之间的相似程度。由于使用 Hausdorff距离作为距离测度时无需考虑两个点集中的点与点之间的对应关系，因此可以有 效解决当图像中存在噪声和目标被部分遮挡时的识别问题。Ezra研究了使用Hausdorff距 离在

13、ICP中的一些理论结果，还没有进行配准的实际应用。4.1.4 几何特征严格的说，距离也是一种几何特征，这里指的几何特征是指除距离以外的几何特征。主 要有法相量叫、曲率等特征。加入几何特征更多的是为了在确定点对时加入限制条件，尽量减小误差点的数目。Pulli 在文献中就加入了给定点对的限制条件，其中一个是每个点对对应的法向矢量差不能超过 45度，而Godina则是通过曲率来构造候选兼容点集。图2就是通过原始ICP算法和加入 法相限制条件后获取的点对情况，其中空心箭头表示法相矢量方向，黑色箭头表示找到的对 应点对。图2对应点对(a)通过传统ICP方法获得(b)中加入了法矢限制条件通过加入几何特征的

14、限制条件，可以进一步的降低找到错误点对的概率，同时加入几何 特征后，可以非常迅速的确定候选点集，可以大大的提高搜索速度。4.2 搜索策略在对应点的选取，也就是构造各对应点的过程中，需要进行大量的搜索过程，这是传统 ICP算法的瓶颈，为了提高ICP算法的效率，提高搜索速度是很有必要的，所以如何改进搜 索策略也是ICP算法研究的热点。Zhang在其论文中采用了多维二元搜索树四(K-D Tree),该算法可以自动的踢出异常 值，可以处理非完全对应的点集合。Greenspan分析了该树的特性，提出了近似多维二元搜 索树网(AK-DTree),达到了近似的效果，并提高了效率。另一种方法是依靠金字塔原理提

15、出来的分级收缩算法网，大大加快了搜索速度。该方法 通过评估目标区域距离值的方差和均匀拓扑映射来选择区域，在点集中进行逐级的收缩，先 进行粗略定位，最后获取准确地对应点，对于搜索效率有很大的提高。投影的方法也被应用到ICP算法中来，Blais和Neugbeuaer采用反向定标网(Reverse Calibration)技术，就是使用的投影搜索算法。Benjemaa则采用了具有多个投影平面的 Z-buffer方法进行投影搜索。5误差函数求解误差函数的求解，也就是目标函数的最小化，是ICP算法的最后一个阶段。在求得目 标函数后应该采用什么样的方法来求解目标函数，使其值能最快最准的的收敛到最小，也是

16、一个比较重要的问题。传统的ICP算法的目标函数是通过点对点的距离建立的，其求解方 法有基于奇异值分解的方法、四元数方法、正交矩阵法仍和双四元数方法29】。 Eggert啊评估了上述四种方法的精确性和稳定性，并且说明了这些方法存在的差 异。由于基于奇异值分解的方法和四元数方法应用的更加广泛，所以，在下面将 对这两种方法的实现方式做具体的介绍。5.1 基于奇异值分解的方法用奇异值分解法(SVD方法)来求解ICP算法过程中的几何参数最初是由ARUNpl等 提出来的，其并没有建立目标函数等式，而是通过矩阵变换的相关性质，直接求解出最优的 参数解。该方法实现起来比较简单，而且计算结果也比较准确，下面就对相关原理进行论述。