迭代最近点算法研究

摘要：三维点云数据的配准一直是计算机视觉、模式识别、摄影测量等领域的研究热点，它对于解决曲线曲面匹配、图像拼接、三维重建、计算机辅助文物复等问题至关重要。目前最常用的点云数据配准方法是迭代最近点（Iterative　Closest　Point，ICP）算法，伴随着三维扫描技术的进步，许多研究者对该算法做了细致的研究并提出了各种改进算法。该文首先总结了ICP算法的基本原理，然后从数据采样、特征点选取与点对权重、非重叠区域检测、兼容性约束四个方面对改进算法进行了系统而详细的分析与研究。

关键词：三维点云；配准；迭代最近点

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2012）31-7568-03

在计算机应用领域，三维点云数据的配准对解决曲线曲面匹配、图像拼接、三维重建、计算机辅助文物复原等问题至关重要。以计算机辅助文物碎片拼接为例，在过去十年间有很多研究项目需要获取文物详细的三维表示，但是通过三维扫描设备获取的多个扫描需要采取一定的技术恢复每个扫描的相对视点，然后将多个扫描融合到一个最终的模型。这一过程就是三维点云数据的配准，它是获取文物准确的三维表示的关键步骤。1992年，Besl和Mckay提出了一种基于几何模型的三维物体配准算法——迭代最近点算法[1]。近年来，伴随着三维扫描技术的不断进步，该算法得到了广泛应用，也吸引了众多研究者的目光。许多研究者对该算法进行了系统的研究，分析了该算法的特点与不足，提出了各种改进算法。国外学者Michael　Wild[2]回顾了2002年到2007年ICP算法的发展；介绍了ICP算法的流程并对几种改进算法做了详细的分析和比较；最后介绍了该算法在放射疗法中的应用。近几年，ICP算法的研究改进以及应用仍然是国内外众多学者热衷的一个研究方向，这从发表在IEEE上的论文数量即可看出。本文详细总结了ICP算法的基本原理，然后从数据采样、特征点选取与点对权重、非重叠区域检测、兼容性约束四个方面对几种改进算法进行了系统而详细的分析与研究。总结了这些算法的基本思想和特点，这些工作对后期的研究将会起到重要的作用。

1　ICP算法的基本原理

1.1　基本原理

ICP算法是大多数点云配准算法的心，它是一个点对刚性算法。基本思想是：假设两个点集P和X近似对齐，对P上的每个点，假设X上的最近点与之对齐。采用最近点搜索，在X上找出P上各个点对应的最近点，构成集合Y，然后计算一个新的P到Y的刚体变换。重复上述过程直到配准收敛。