迭代最近点算法综述

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

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

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

4、参考点集Q的坐标为Qi,i=1,2,Nq，在第k次迭代中计算与点集P的坐标相对应的对应点坐标为Qik,i=1,2,NP，计算P与Qk之间的变换矩阵并对原变换进行更新，直到数据间平均距离小于给定值，即满足式（1）最小。具体步骤4：（1） 在目标点集P中取点集PikP；（2） 计算参考点集Q中对应点QikQk，使Qik-Pik=min；（3） 计算旋转矩阵Rk与平移向量Tk，使得i=1nRkPik+Tk-Qik2=min；（4） 计算Pk+1=Pik+1= RkPik+Tk，PikP；（5） 计算dk+1= 1ni=1nPik+1-Qik2；（6） 如果dk+1不小于给定的返回到（2），直到dk+

5、10,则有这个单位四元数产生的旋转矩阵为33： R=q02+q12-q22-q322*(q1q2-q0q3)2*(q1q3+q0q2)2*(q1q2+q0q3)q02-q12+q22-q322*(q2q3-q0q1)2*(q1q3-q0q2)2*(q2q3+q0q1)q02-q12-q22+q32 （5）定义平移向量为qT=q4,q5,q6T，并由qR和qT组成一个配准状态向量q=qR|qTT。点集的重心分别为p和p，则两点集的协方差如下： pp，=1Ni=1N(Pi-p)(Qi-p,) （6）根据pp，得出一个反对称矩阵A，其元素为Aij=（pp，-pp，T）ij，由A的三个循环元素又组成了

6、一个列向量=A23,A31,A12T。最后，由以上矩阵和向量组成对称矩阵Q（pp，） Q（pp，）=tr（pp，）Tpp，+pp，T-tr（pp，）I3 （7）其中I3为3X3单位矩阵。求解对称矩阵Q（pp，）的特征值和特征向量，所得最大特征值所对应的特征向量即为旋转四元数qR=q0,q1,q2,q3T。计算平移向量qR=p，-R*p，最终生成一个配准向量q。6 总结本文从配准元素的选择、配准策略的确定和误差函数的求解等三个方面对ICP算法的各种改进和优化进行了分类和总结。通过文中的分析可以发现，ICP在这些年的发展过程中，将各种技术吸收进来，这一方面说明了ICP算法以其本身的优势获得了研究者

7、的关注，另一方面也说明研究者在对ICP算法改进上付出了不懈的努力但是ICP算法的研究还没有停止，因为这种算法还不能解决所有的配准问题，也将还会有人继续对这种算法展开研究，让其变得更加完美。参考文献 1 罗纲，罗斌. 图象特征点集配准的加权相关迭代算法J. 中国图象图形学报. 2000(09): 47-50. 2 Besl P J, Mckay H D. A method for registration of 3-D shapesJ. Pattern Analysis and Machine Intelligence, IEEE Transactions on. 1992, 14(2): 23

8、9-256. 3 蒋成成，胡同森，周维. 一种改进的迭代最近点算法J. 计算机系统应用. 2009(08): 84-87. 4 张波. 基于ICP和SVD的眼底图像配准研究D. 吉林大学, 2009. 5 李必卿，蔡勇. 一种改进的ICP算法在多视配准中的应用J. 机械工程师. 2009(02): 73-75. 6 任治新，罗诗途，吴美平，等. 基于改进ICP算法的地磁图匹配技术J. 计算机应用. 2008(S1): 351-354. 7 刘承香，阮双琛，刘繁明，等. 基于迭代最近点算法的地形匹配算法可靠性分析J. 深圳大学学报. 2005(01): 22-26. 8 Rusinkiewicz

9、 S, Levoy M. Efficient variants of the ICP algorithmC. 2001. 9 伍毅. 三维扫描信息获取的深度图像配准算法设计及开发D. 浙江大学, 2005.10 Nishino K,Ikeuehi K.Robust simultaneous registration of multiple range images comprising a large number of pointsJ. Electronics and Communications in Japan(Part II:Electronics). 2004,87(8):61-74

10、.11 G. Turk,M. LevoyZippered Polygon Meshes from Range ImagesC. Proceedings of SIGGRAPH 1994:311-318.12 Masuda T, Sakaue K, Yokoya N. Registration and integration of multiple range images for 3-D model constructionC. 1996.13 Weik S. Registration of 3-D partial surface models using luminance and dept

11、h informationC. 1997.14 Sappa A,Restrepo-specht A,Uevy M.Range image registration by using an edge-based representationC.P roceedings of the 9th International Symposium on Intelligent Rohotic.Toulouse;France:2001.15 张同刚，岑敏仪，冯义从. 用于无控制DEM匹配的LZD和ICP算法的比较J. 中国图象图形学报. 2006(05): 714-719.16 Chen Y, Medion

12、i G. Object modeling by registration of multiple range imagesC. 1991.17 Pulli K. Multiview registration for large data setsC. 1999.18 张鸿宾，谢丰. 基于表面间距离度量的多视点距离图像的对准算法J. 中国科学E辑:信息科学. 2005(02): 150-160.19 杨清夙，游志胜，张先玉. 基于豪斯多夫距离的快速多人脸检测算法J. 电子科技大学学报. 2004(04): 407-409.20 Ezra E,Sharir M,Efrat A.On the per

13、formance of the ICP algorithmJ. Computational Geometry.2008,41(1-2):77-93.21 Bemardini F,Mittleman J,Rnshmeier H,et al.The ball-pivoting algorithm for surface reconstructionJ. Visualization and Computer Graphics,IEEE Transactions on.1999,5(4):349-359.22 Godin P,Boulanger G.Range image registration t

14、hrough viewpoint invariant computation of curvatureC.Proceedings of ISPRS,1995:170175.23 Zhang Z. Iterative point matching for registration of free-form curves and surfacesJ. International Journal of Computer Vision.1994,13(2):119-152.24 Greenspan M, Yurick M. Approximate k-d tree search for efficie

15、nt ICPC. 2003.25 Okuda H.HM-ICP:Fast 3-D Registration Algorithm with Hierarchical and Region Selection Approach of M-ICPC. Journal of Robotics and Mechatronics.2006.18(2):765-771.26 Neugebauer P J. Geometrical cloning of 3D objects via simultaneous registration of multiple range imagesC. 1997.27 Ben

16、jemaa R, Schmitt F. Fast global registration of 3D sampled surfaces using a multi-z-buffer techniqueC. 1997.28 陈楚. 基于激光扫描的深度影像配准方法的研究D. 武汉大学, 2005.29 Walker M W, Shao L, Volz R A. Estimating 3-D location parameters using dual number quaternionsJ. CVGIP: Image Understanding. 1991, 54(3): 358-367.30 E

17、ggert D W,Lorusso A,Fisher R B.Estimating 3-D rigid body transformations:a comparison of four major algorithmsJ. Machine Vision and Applications. 1997,9(5):272-290.31 Arun K S, Huang T S, Blostein S D. Least-Squares Fitting of Two 3-D Point SetsJ. Pattern Analysis and Machine Intelligence, IEEE Transac