迭代最近點(diǎn)算法綜述

1、迭代最近點(diǎn)算法綜述摘要：三維點(diǎn)集配準(zhǔn)問題是計(jì)算機(jī)技術(shù)中的一個(gè)極其重要的問題，作為解決三維點(diǎn)集配準(zhǔn)問題的一個(gè)應(yīng)用較為廣泛的算法，ICP算法得到了研究者的關(guān)注，本文以一種全新的思路從配準(zhǔn)元素的選擇、配準(zhǔn)策略的確定和誤差函數(shù)的求解等3個(gè)方面對(duì)三維點(diǎn)集配準(zhǔn)的ICP算法的各種改進(jìn)和優(yōu)化進(jìn)行了分類和總結(jié)。關(guān)鍵詞：三維點(diǎn)集；迭代最近點(diǎn)；配準(zhǔn)1 引言在計(jì)算機(jī)應(yīng)用領(lǐng)域，三維點(diǎn)集配準(zhǔn)是一個(gè)非常重要的中間步驟，它在表面重建、三維物體識(shí)別、相機(jī)定位等問題中有著極其重要的應(yīng)用1。對(duì)于三維點(diǎn)集配準(zhǔn)問題，研究者提出了很多解決方案，如點(diǎn)標(biāo)記法、自旋圖像、主曲率方法、遺傳算法、隨機(jī)采樣一致性算法等等，這些算法各有特色，在許多特

2、定的情況下能夠解決配準(zhǔn)的問題。但是應(yīng)用最廣泛的，影響最大的還是由Besl和Mckay在1992年提出的迭代最近點(diǎn)算法2（Iterative Closest Point，ICP），它是基于純粹幾何模型的三維物體對(duì)準(zhǔn)算法，由于它的強(qiáng)大功能以及高的精確度，很快就成為了曲面配準(zhǔn)中的主流算法。隨著ICP算法的廣泛應(yīng)用，許多研究者對(duì)ICP算法做了詳細(xì)的研究，分析了該算法的缺陷和特點(diǎn)，提出了許多有價(jià)值的改進(jìn)，推動(dòng)了這一重要算法的發(fā)展。本文著眼于ICP算法的發(fā)展歷程，詳細(xì)介紹了ICP算法的基本原理，總結(jié)其發(fā)展和改進(jìn)的過程，對(duì)于該算法的各個(gè)階段的發(fā)展和變化做了簡單的論述。2 ICP算法原理2.1 ICP算法原理

3、ICP算法主要用于三維物體的配準(zhǔn)問題，可以理解為：給定兩個(gè)來至不同坐標(biāo)系的三維數(shù)據(jù)點(diǎn)集，找出兩個(gè)點(diǎn)集的空間變換，以便它們能進(jìn)行空間匹配。假定用Pi,i=1,2,N表示空間第一個(gè)點(diǎn)集，第二個(gè)點(diǎn)集的對(duì)齊匹配變換為使下式的目標(biāo)函數(shù)最小3。fR,t= i=1N|Qi-(RPi+T)|2=min (1)ICP算法的實(shí)質(zhì)是基于最小二乘法的最優(yōu)匹配算法，它重復(fù)進(jìn)行“確定對(duì)應(yīng)關(guān)系點(diǎn)集計(jì)算最優(yōu)剛體變換”的過程，直到某個(gè)表示正確匹配的收斂準(zhǔn)則得到滿足。ICP 算法的母的是找到目標(biāo)點(diǎn)集與參考點(diǎn)之間的旋轉(zhuǎn)R和平移T變換，使得兩匹配數(shù)據(jù)中間滿足某種程度度量準(zhǔn)則下的最優(yōu)匹配。假設(shè)目標(biāo)點(diǎn)集P的坐標(biāo)為Pi,i=1,2,NP及

4、參考點(diǎn)集Q的坐標(biāo)為推薦精選Qi,i=1,2,Nq，在第k次迭代中計(jì)算與點(diǎn)集P的坐標(biāo)相對(duì)應(yīng)的對(duì)應(yīng)點(diǎn)坐標(biāo)為Qik,i=1,2,NP，計(jì)算P與Qk之間的變換矩陣并對(duì)原變換進(jìn)行更新，直到數(shù)據(jù)間平均距離小于給定值，即滿足式（1）最小。具體步驟4：（1） 在目標(biāo)點(diǎn)集P中取點(diǎn)集PikP；（2） 計(jì)算參考點(diǎn)集Q中對(duì)應(yīng)點(diǎn)QikQk，使Qik-Pik=min；（3） 計(jì)算旋轉(zhuǎn)矩陣Rk與平移向量Tk，使得i=1nRkPik+Tk-Qik2=min；（4） 計(jì)算Pk+1=Pik+1= RkPik+Tk，PikP；（5） 計(jì)算dk+1= 1ni=1nPik+1-Qik2；（6） 如果dk+1不小于給定的返回到（2），直

5、到dk+10,則有這個(gè)單位四元數(shù)產(chǎn)生的旋轉(zhuǎn)矩陣為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組成一個(gè)配準(zhǔn)狀態(tài)向量q=qR|qTT。點(diǎn)集的重心分別為p和p，則兩點(diǎn)集的協(xié)方差如下：推薦精選 pp，=1Ni=1N(Pi-p)(Qi-p,) （6）根據(jù)pp，得出一個(gè)反對(duì)稱矩陣A，其元素為Aij=（pp，-pp，T）ij，由A的三個(gè)

6、循環(huán)元素又組成了一個(gè)列向量=A23,A31,A12T。最后，由以上矩陣和向量組成對(duì)稱矩陣Q（pp，） Q（pp，）=tr（pp，）Tpp，+pp，T-tr（pp，）I3 （7）其中I3為3X3單位矩陣。求解對(duì)稱矩陣Q（pp，）的特征值和特征向量，所得最大特征值所對(duì)應(yīng)的特征向量即為旋轉(zhuǎn)四元數(shù)qR=q0,q1,q2,q3T。計(jì)算平移向量qR=p，-R*p，最終生成一個(gè)配準(zhǔn)向量q。6 總結(jié)本文從配準(zhǔn)元素的選擇、配準(zhǔn)策略的確定和誤差函數(shù)的求解等三個(gè)方面對(duì)ICP算法的各種改進(jìn)和優(yōu)化進(jìn)行了分類和總結(jié)。通過文中的分析可以發(fā)現(xiàn)，ICP在這些年的發(fā)展過程中，將各種技術(shù)吸收進(jìn)來，這一方面說明了ICP算法以其本身的

7、優(yōu)勢(shì)獲得了研究者的關(guān)注，另一方面也說明研究者在對(duì)ICP算法改進(jìn)上付出了不懈的努力但是ICP算法的研究還沒有停止，因?yàn)檫@種算法還不能解決所有的配準(zhǔn)問題，也將還會(huì)有人繼續(xù)對(duì)這種算法展開研究，讓其變得更加完美。參考文獻(xiàn) 1 羅綱，羅斌. 圖象特征點(diǎn)集配準(zhǔn)的加權(quán)相關(guān)迭代算法J. 中國圖象圖形學(xué)報(bào). 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, 1

8、4(2): 239-256. 3 蔣成成，胡同森，周維. 一種改進(jìn)的迭代最近點(diǎn)算法J. 計(jì)算機(jī)系統(tǒng)應(yīng)用. 2009(08): 84-87. 4 張波. 基于ICP和SVD的眼底圖像配準(zhǔn)研究D. 吉林大學(xué), 2009. 5 李必卿，蔡勇. 一種改進(jìn)的ICP算法在多視配準(zhǔn)中的應(yīng)用J. 機(jī)械工程師. 2009(02): 73-75. 6 任治新，羅詩途，吳美平，等. 基于改進(jìn)ICP算法的地磁圖匹配技術(shù)J. 計(jì)算機(jī)應(yīng)用. 2008(S1): 351-354. 7 劉承香，阮雙琛，劉繁明，等. 基于迭代最近點(diǎn)算法的地形匹配算法可靠性分析J. 深圳大學(xué)學(xué)報(bào). 2005(01): 22-26. 8 Rusi

9、nkiewicz S, Levoy M. Efficient variants of the ICP algorithmC. 2001. 9 伍毅. 三維掃描信息獲取的深度圖像配準(zhǔn)算法設(shè)計(jì)及開發(fā)D. 浙江大學(xué), 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(

10、8):61-74.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 lumina

11、nce and depth 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. 中國圖象圖形學(xué)報(bào). 2006(05): 714-719.16 Ch

12、en Y, Medioni G. Object modeling by registration of multiple range imagesC. 1991.17 Pulli K. Multiview registration for large data setsC. 1999.18 張鴻賓，謝豐. 基于表面間距離度量的多視點(diǎn)距離圖像的對(duì)準(zhǔn)算法J. 中國科學(xué)E輯:信息科學(xué). 2005(02): 150-160.19 楊清夙，游志勝，張先玉. 基于豪斯多夫距離的快速多人臉檢測(cè)算法J. 電子科技大學(xué)學(xué)報(bào). 2004(04): 407-409.20 Ezra E,Sharir M,Efrat

13、A.On the performance 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 re

14、gistration through 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

15、 for efficient 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.

16、 1997.27 Benjemaa R, Schmitt F. Fast global registration of 3D sampled surfaces using a multi-z-buffer techniqueC. 1997.28 陳楚. 基于激光掃描的深度影像配準(zhǔn)方法的研究D. 武漢大學(xué), 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):

17、358-367.30 Eggert 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 Transactions on. 1987, PAMI-9(5): 6