ICP迭代最近点算法综述.pdf

迭代最近点算法综述 摘要：三维点集配准问题是计算机技术中的一个极其重要的问题，作为解决三维点集配准问题的一个应用 较为广泛的算法，ICP 算法得到了研究者的关注，本文以一种全新的思路从配准元素的选择、配准策 略的确定和误差函数的求解等3 个方面对三维点集配准的ICP 算法的各种改进和优化进行了分类和总 结。 关键词：三维点集；迭代最近点；配准 1 引言 在计算机应用领域，三维点集配准是一个非常重要的中间步骤，它在表面重建、三维物 体识别、相机定位等问题中有着极其重要的应用[1] 。对于三维点集配准问题，研究者提出了 很多解决方案，如点标记法、自旋图像、主曲率方法、遗传算法、随机采样一致性算法等等， 这些算法各有特色，在许多特定的情况下能够解决配准的问题。但是应用最广泛的，影响最 大的还是由Besl 和Mckay 在1992 年提出的迭代最近点算法[2] （Iterative Closest Point，ICP ）， 它是基于纯粹几何模型的三维物体对准算法，由于它的强大功能以及高的精确度，很快就成 为了曲面配准中的主流算法。 随着ICP 算法的广泛应用，许多研究者对 ICP 算法做了详细的研究，分析了该算法的 缺陷和特点，提出了许多有价值的改进，推动了这一重要算法的发展。本文着眼于 ICP 算 法的发展历程，详细介绍了 ICP 算法的基本原理，总结其发展和改进的过程，对于该算法 的各个阶段的发展和变化做了简单的论述。 2 ICP算法原理 2.1 ICP算法原理 ICP 算法主要用于三维物体的配准问题，可以理解为：给定两个来至不同坐标系的三维 数据点集，找出两个点集的空间变换，以便它们能进行空间匹配。假定用{ } [3] 表示空间第一个点集，第二个点集的对齐匹配变换为使下式的目标函数最小 。 ICP 算法的实质是基于最小二乘法的最优匹配算法，它重复进行“确定对应关系点集— 计算最优刚体变换”的过程，直到某个表示正确匹配的收敛准则得到满足。ICP 算法的母的 是找到目标点集与参考点之间的旋转R 和平移T 变换，使得两匹配数据中间满足某种程度 度量准则下的最优匹配。假设目标点集P 的坐标为{ }及参考点集Q 的坐标为 { } ，在第 k 次迭代中计算与点集 P 的坐标相对应的对应点坐标为 ，计算P 与 之间的变换矩阵并对原变换进行更新，直到数据间平均距 [4] 离小于给定值τ，即满足式（1）最小。具体步骤 ： （1） 在目标点集P 中取点集 ； （2 ） 计算参考点集Q 中对应点 ，使 ； （3 ） 计算旋转矩阵 与平移向量 ，使得 ； （4 ） 计算 ； （5 ） 计算 ； （6 ） 如果 不小于给定的τ返回到（2 ），直到 或迭代次数大于预设的最 大的迭代次数为止。 对于ICP 的每次迭代，最小化对应点的均方差使得点集 更接近 ，而 是 在 的 最近点。这样，每一次迭代就使得 更接近于 。基于这样的思想，Besl 等人证明了ICP 算 法的收敛性。 2.2 ICP算法特性分析 在三维点集配准的各种应用中，ICP 算法的使用非常广泛，这是由于ICP 算法有以下优 点：  可以获得非常精确的配准效果；  可以处理三维点集、参数曲面等多种形式表达的曲面，也就是说该算法对曲面表示 方法独立[5] ；  不必对待处理的点集进行分割和特征提