迭代最近点算法综述

《迭代最近点算法综述》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、图像、主曲率方法、遗传算法、随机采样一致性算法等等，这些算法各有特色，在许多特定的情况下能够解决配准的问题。但是应用最广泛的，影响最大的还是由Besl和Mckay在1992年提出的迭代最近点算法[2]（IterativeClosestPoint，ICP），它是基于纯粹几何模型的三维物体对准算法，由于它的强大功能以及高的精确度，很快就成为了曲面配准中的主流算法。随着ICP算法的广泛应用，许多研究者对ICP算法做了详细的研究，分析了该算法的缺陷和特点，提出了许多有价值的改进，推动了这一重要算法的发展。本文着眼于ICP算法的

3、发展历程，详细介绍了ICP算法的基本原理，总结其发展和改进的过程，对于该算法的各个阶段的发展和变化做了简单的论述。2ICP算法原理2.1ICP算法原理ICP算法主要用于三维物体的配准问题，可以理解为：给定两个来至不同坐标系的三维数据点集，找出两个点集的空间变换，以便它们能进行空间匹配。假定用{Pi,i=1,2,…,N}表示空间第一个点集，第二个点集的对齐匹配变换为使下式的目标函数最小[3]。fR,t=i=1N

4、

5、Qi-(RPi+T)

6、

7、2=min(1)ICP算法的实质是基于最小二乘法的最优匹配算法，它重复进行“确定对应

8、关系点集—计算最优刚体变换”的过程，直到某个表示正确匹配的收敛准则得到满足。ICP算法的母的是找到目标点集与参考点之间的旋转R和平移T变换，使得两匹配数据中间满足某种程度度量准则下的最优匹配。假设目标点集P的坐标为{Pi,i=1,2,…,NP}及参考点集Q的坐标为{Qi,i=1,2,…,Nq}，在第k次迭代中计算与点集P的坐标相对应的对应点坐标为{Qik,i=1,2,…,NP}，计算P与Qk之间的变换矩阵并对原变换进行更新，直到数据间平均距离小于给定值τ9，即满足式（1）最小。具体步骤[4]：（1）在目标点集P中取点集

9、Pik∈P；（2）计算参考点集Q中对应点Qik∈Qk，使Qik-Pik=min；（3）计算旋转矩阵Rk与平移向量Tk，使得i=1nRkPik+Tk-Qik2=min；（4）计算Pk+1={Pik+1=RkPik+Tk，Pik∈P}；（5）计算dk+1=1ni=1nPik+1-Qik2；（6）如果dk+1不小于给定的τ返回到（2），直到dk+1<τ或迭代次数大于预设的最大的迭代次数为止。对于ICP的每次迭代，最小化对应点的均方差使得点集Pik更接近Qik，而Qik是Pik在Qi的最近点。这样，每一次迭代就使得Pi更接近于

10、Qi。基于这样的思想，Besl等人证明了ICP算法的收敛性。1.1ICP算法特性分析在三维点集配准的各种应用中，ICP算法的使用非常广泛，这是由于ICP算法有以下优点：l可以获得非常精确的配准效果；l可以处理三维点集、参数曲面等多种形式表达的曲面，也就是说该算法对曲面表示方法独立[5]；l不必对待处理的点集进行分割和特征提取；l在较好的初值情况下，可以得到很好的算法收敛性[6]。虽然其得到了广泛的应用，但是对于最初的ICP算法，存在很多的不足之处，主要表现在：l算法假设其中一个点集是另一个点集的子集，也就是说，一个点集

11、必须含在另一个点集中，这一要求在很多时候难以满足；l该算法在搜索对应点的过程中，计算代价非常的大；l在基本的ICP算法中，在寻找对应点的时候，认为欧氏距离最近的点就是对应点，这种假设是比较武断的，它会产生一定数量的错误对应点[7]。针对上面的一些问题，许多研究者提出了ICP算法的各种改进版本。为了说明ICP算法的不同改进版本，有必要将ICP算法分成几个阶段来讨论，在各个阶段的划分，国内外的研究学者也提出了自己的看法。主要的划分方法有，在Rusinkiewicz[8]的文章中，将ICP算法的进行分成了六个阶段，分别为：点

12、集的选择、对应点对的配准、点对的权重确定、特定点对的剔除、误差矩阵的建立、误差矩阵最小化的求解；伍毅[9]则将其分为四个阶段：重采样、空间查找及距离度量、目标度量函数最小化和算法的迭代；Nishino[10]认为，不同的改进方法的差异不过体现在三个方面：配准策略、配准元素和误差度量。通过比较国内外学者提出的各种ICP算法的改进算法