迭代最近點算法綜述

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

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

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

4、參考點集Q的坐標為Qi,i=1,2,Nq，在第k次迭代中計算與點集P的坐標相對應的對應點坐標為Qik,i=1,2,NP，計算P與Qk之間的變換矩陣并對原變換進行更新，直到數(shù)據(jù)間平均距離小于給定值，即滿足式（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、1<或迭代次數(shù)大于預設的最大的迭代次數(shù)為止。對于ICP的每次迭代，最小化對應點的均方差使得點集Pik更接近Qik，而Qik是Pik在Qi的最近點。這樣，每一次迭代就使得Pi更接近于Qi?；谶@樣的思想，Besl等人證明了ICP算法的收斂性。2.2 ICP算法特性分析在三維點集配準的各種應用中，ICP算法的使用非常廣泛，這是由于ICP算法有以下優(yōu)點：l 可以獲得非常精確的配準效果；l 可以處理三維點集、參數(shù)曲面等多種形式表達的曲面，也就是說該算法對曲面表示方法獨立5；l 不必對待處理的點集進行分割和特征提??；l 在較好的初值情況下，可以得到很好的算法收斂性6。雖然其得到了廣泛的應用，但是對

6、于最初的ICP算法，存在很多的不足之處，主要表現(xiàn)在：l 算法假設其中一個點集是另一個點集的子集，也就是說，一個點集必須含在另一個點集中，這一要求在很多時候難以滿足；l 該算法在搜索對應點的過程中，計算代價非常的大；l 在基本的ICP算法中，在尋找對應點的時候，認為歐氏距離最近的點就是對應點，這種假設是比較武斷的，它會產(chǎn)生一定數(shù)量的錯誤對應點7。針對上面的一些問題，許多研究者提出了ICP算法的各種改進版本。為了說明ICP算法的不同改進版本，有必要將ICP算法分成幾個階段來討論，在各個階段的劃分，國內(nèi)外的研究學者也提出了自己的看法。主要的劃分方法有，在Rusinkiewicz8的文章中，將ICP算

7、法的進行分成了六個階段，分別為：點集的選擇、對應點對的配準、點對的權重確定、特定點對的剔除、誤差矩陣的建立、誤差矩陣最小化的求解；伍毅9則將其分為四個階段：重采樣、空間查找及距離度量、目標度量函數(shù)最小化和算法的迭代；Nishino10認為，不同的改進方法的差異不過體現(xiàn)在三個方面：配準策略、配準元素和誤差度量。通過比較國內(nèi)外學者提出的各種ICP算法的改進算法，可以知道，Nishino的劃分方法可以很好的反應算法所做改變的各個階段。所以，在本文中將圍繞ICP算法配準元素的選擇、配準策略的確定和誤差函數(shù)的求解等三個方面做的改進來展開。3 配準元素的選擇在標準ICP算法中，選用點集中的所有點來計算對應

8、的點，但是通常用于配準的點集元素數(shù)量都是非常巨大的，通過這些點集來計算，所消耗的時間也是很長的。所以在后來的研究當中，提出了各種各樣的方法來選擇配準元素，這些算法的主要目的無一例外的是為了減小點集元素的數(shù)目，即對匹配點集進行采樣。既然涉及到采樣，就有多種采樣方法被嘗試使用。Turk使用了一致采樣方法11，Masuda12使用的式隨機采樣方法，而且在每一的迭代過程中都要進行隨機采樣獲取不同的采樣點進行計算。也有一些學者提出了一些新的采樣方法，這些方法主要特點是會利用點集的特征信息來減少點的數(shù)目，運用一些具有明顯特征的點集來進行配準。比如，Weik13在文獻中提到的，利用圖像的梯度信息來選擇符合要

9、求的點，再用這些點來完成配準。Sappa14則是采用了另外一種策略，直接選取邊緣點作為配準的選擇點，這樣就可以大大的減小配準點的數(shù)目。通過上面的分析可以發(fā)現(xiàn)，配準元素的選擇的改進，主要集中在如何減小配準點的數(shù)目方面，即如何用最少的點來表征原始點集的全部特征信息。4 配準策略的確定上面介紹了ICP算法在配準元素選擇方面做得一些改進，而更多的改進集中在配準策略方面。具體的配準策略包括特征度量的選取和搜索策略的選取方面。4.1 特征度量的選取要尋找對應點對，就必須尋找場景數(shù)據(jù)點和模型數(shù)據(jù)點的特征差異，這就需要對特征進行度量。在利用特征度量獲得對應點以后，還需要利用特征度量建立迭代優(yōu)化的目標函數(shù)，為誤

10、差函數(shù)的求解奠定基礎15。ICP算法被提出來時，采用的是歐氏距離作為特征度量，所以在這一階段的改進方面，主要是圍繞距離展開，很多研究者在這方面提出了自己的改進想法，當然有一些也并沒有采用距離作為特征度量，在下面會做詳細的介紹。4.1.1點到點的距離在標準ICP算法中，Besl和McKay直接采用的是點到點的歐氏距離。首先利用點到點的最小歐氏距離得到點到集合的距離，從而尋找到對應點，再對這些對應點到集合的距離進行求和得到求解剛體變換的目標函數(shù)，如(1)式所示。簡而言之，標準ICP算法使用的是點到點（point-to-point）的距離。4.1.2點到平面的距離Chen16利用的是場景點集中的點的

11、法線與模型點集合的交點來確定對應點，得到對應點后，目標函數(shù)則采用的是點到面(point-to-plane)的距離，點到面的距離是指，場景數(shù)據(jù)集中的點到模型數(shù)據(jù)集合中的經(jīng)過對應點的切平面的距離，如圖l所示。場景點P中的點pi，它的法線與模型點集X的交點qi就被選擇為pi的對應點。在建立目標函數(shù)時，使用的并不是pi到qi的距離，而是pi到模型點集X過qi的切平面的距離。圖1 點到平面的距離點到平面的距離減少了迭代次數(shù)，能夠以更快的速度收斂到給定的閾值。Pulli對點到點的方法和點到面的方法進行了對比討論17，他們指出與點到點的ICP算法相比，運用點到平面的距離的方法大大減少了計算量以及迭代次數(shù)，但

12、是該方法的魯棒性并不是太好。與上面的度量標準相類似的還有點到三角形的距離，它運用點與點之間的鄰接信息，將三維點集三角化，以點到三角形表面的距離作為特征度量，與點到面的距離有一些相似，主要由張鴻賓和謝豐在文獻中提出18。4.1.3豪斯多夫(Hausdorff)距離Hausdorff距離19作為一種距離測度，常用于衡量兩個點集之間的相似程度。由于使用Hausdorff距離作為距離測度時無需考慮兩個點集中的點與點之間的對應關系，因此可以有效解決當圖像中存在噪聲和目標被部分遮擋時的識別問題。Ezra20研究了使用Hausdorff距離在ICP中的一些理論結果，還沒有進行配準的實際應用。4.1.4幾何特

13、征嚴格的說，距離也是一種幾何特征，這里指的幾何特征是指除距離以外的幾何特征。主要有法相量21、曲率等特征。加入幾何特征更多的是為了在確定點對時加入限制條件，盡量減小誤差點的數(shù)目。Pulli在文獻中就加入了給定點對的限制條件，其中一個是每個點對對應的法向矢量差不能超過45度，而Godin22則是通過曲率來構造候選兼容點集。圖2就是通過原始ICP算法和加入法相限制條件后獲取的點對情況，其中空心箭頭表示法相矢量方向，黑色箭頭表示找到的對應點對。（a） （b）圖2 對應點對（a）通過傳統(tǒng)ICP方法獲得（b）中加入了法矢限制條件通過加入幾何特征的限制條件，可以進一步的降低找到錯誤點對的概率，同時加入幾何

14、特征后，可以非常迅速的確定候選點集，可以大大的提高搜索速度。4.2 搜索策略在對應點的選取，也就是構造各對應點的過程中，需要進行大量的搜索過程，這是傳統(tǒng)ICP算法的瓶頸，為了提高ICP算法的效率，提高搜索速度是很有必要的，所以如何改進搜索策略也是ICP算法研究的熱點。Zhang在其論文中采用了多維二元搜索樹23（K-D Tree），該算法可以自動的踢出異常值，可以處理非完全對應的點集合。Greenspan分析了該樹的特性，提出了近似多維二元搜索樹24（AK-D Tree），達到了近似的效果，并提高了效率。另一種方法是依靠金字塔原理提出來的分級收縮算法25，大大加快了搜索速度。該方法通過評估目標

15、區(qū)域距離值的方差和均勻拓撲映射來選擇區(qū)域，在點集中進行逐級的收縮，先進行粗略定位，最后獲取準確地對應點，對于搜索效率有很大的提高。投影的方法也被應用到ICP算法中來，Blais和Neugbeuaer采用反向定標26（Reverse Calibration）技術，就是使用的投影搜索算法。Benjemaa27則采用了具有多個投影平面的Z-buffer方法進行投影搜索。5 誤差函數(shù)求解誤差函數(shù)的求解，也就是目標函數(shù)的最小化，是ICP算法的最后一個階段。在求得目標函數(shù)后應該采用什么樣的方法來求解目標函數(shù)，使其值能最快最準的的收斂到最小，也是一個比較重要的問題。傳統(tǒng)的ICP算法的目標函數(shù)是通過點對點的距

16、離建立的，其求解方法有基于奇異值分解的方法、四元數(shù)方法、正交矩陣法28和雙四元數(shù)方法29。Eggert30評估了上述四種方法的精確性和穩(wěn)定性，并且說明了這些方法存在的差異。由于基于奇異值分解的方法和四元數(shù)方法應用的更加廣泛，所以，在下面將對這兩種方法的實現(xiàn)方式做具體的介紹。5.1 基于奇異值分解的方法用奇異值分解法（SVD方法）來求解ICP算法過程中的幾何參數(shù)最初是由ARUN31等提出來的，其并沒有建立目標函數(shù)等式，而是通過矩陣變換的相關性質，直接求解出最優(yōu)的參數(shù)解。該方法實現(xiàn)起來比較簡單，而且計算結果也比較準確，下面就對相關原理進行論述。 在運用SVD方法之前，我們默認已經(jīng)通過了點對的搜索環(huán)

17、節(jié)，而且已經(jīng)準確的找了各個對應點對。我們認為有兩組點，模型點和采集到的點，模型點定義為Pi,i=1,2,3,N,N為點的數(shù)目。假設要求的旋轉矩陣是R，平移矩陣是T，理想情況下通過Pi變換得到的對應點位Pi'，有下面的等式： Pi'=RPi+T+Ni R變換的旋轉角度值；T變換的平移值；Ni 噪聲。對于這N個點，現(xiàn)在我們已經(jīng)找到每個點對，對于每個點在變換前后的值都可以非常清楚地知道，根據(jù)式（1），可以得到下面的歐氏距離和。 2=i=1NQi-（RPi+T）2 (2) 由ICP算法的原理可知，歐氏距離最小的點就是采集點在模型中的對應的點，所以基本ICP算法就是求解上面的代數(shù)式，使代

18、數(shù)式的值最小的R和T就是要求的旋轉角度和平移值。而對上面的歐氏距離和，我們可以進行化簡。先計算模板點和數(shù)據(jù)點的重心p=1Ni=1NPip'=1NQi顯然有p'=R*p+T (3)令qi=Pi-p，qi'=Qi-p'，代入式（2），則有 2=qi'-Rqi2 對于（3）式右邊進行分解，可以得到下式。 2=i=1N(qi'-Rqi)tqi'-Rqi =i=1N(qi'tqi'+qitRtRqi-qi'tRqi-qitRtqit) =i=1N(qi'tqi'+qitqi-2qi'tRqi)通過上面

19、的等式，我們可以發(fā)現(xiàn)，要使2的值達到最大，等價于使下式最大。F = i=1Nqi'tRqi=Trace(i=1NRqiqi't)=Trace(RH)其中， H=i=1Nqiqi't 什么樣的情況下Trace（RH）才能最大呢？這是接下來要討論的問題。假設AAt是一個正定矩陣，B為正交矩陣，ai是A中的第i列，則有TraceBAAt=TraceAtBA=iait(Bai)由施瓦茨不等式可以得到，aitBaiaitaiaitBtBai = aitai所以有，TraceBAAt iaitai = Trace(AAt)在求取F的最大值時，我們可以效仿上面的定理，先對H進行SVD

20、分解，可以得到。 H=UVt 其中U和V為正交矩陣，為非負的對角矩陣。我們可以令X=VUt，當然，X也為正交矩陣，則有XH=VUtUVt = VVt (4)XH是一個對稱正定矩陣，而由上面的證明，我們可以知道，對于任意的正交矩陣B，有Trace(XH)Trace(BXH)通過上式，我們可以發(fā)現(xiàn)，當R取XH時，F(xiàn)將達到最大值。所以可以求出R。則SVD方法進行的步驟可以歸納如下。1、 通過Pi,Qi計算p，p'以及qi和qi'。 p=1Ni=1NPi p'=1NQi qi=pi-p qi'=pi'-p'2、 計算矩陣H，通過式H= i=1Nqiqi&

21、#39;t3、 對H進行SVD分解。H=UVt4、 求解旋轉矩陣。R = VUt5、 計算平移矩陣T。T= p'-R*p該算法不適合運用于線性的和有奇異點的數(shù)據(jù)集。5.2 四元數(shù)方法Horn等32提出了基于單位四元數(shù)的計算運動參數(shù)的方法。旋轉矩陣R用一個單位四元數(shù)q來表示：R=R(q),其中設單位四元數(shù)qR=q0,q1,q2,q3T,其中q02+q12+q22+q32=1,而且q0>0,則有這個單位四元數(shù)產(chǎn)生的旋轉矩陣為33： R=q02+q12-q22-q322*(q1q2-q0q3)2*(q1q3+q0q2)2*(q1q2+q0q3)q02-q12+q22-q322*(q2q

22、3-q0q1)2*(q1q3-q0q2)2*(q2q3+q0q1)q02-q12-q22+q32 （5）定義平移向量為qT=q4,q5,q6T，并由qR和qT組成一個配準狀態(tài)向量q=qR|qTT。點集的重心分別為p和p，則兩點集的協(xié)方差如下： pp，=1Ni=1N(Pi-p)(Qi-p,) （6）根據(jù)pp，得出一個反對稱矩陣A，其元素為Aij=（pp，-pp，T）ij，由A的三個循環(huán)元素又組成了一個列向量=A23,A31,A12T。最后，由以上矩陣和向量組成對稱矩陣Q（pp，） Q（pp，）=tr（pp，）Tpp，+pp，T-tr（pp，）I3 （7）其中I3為3X3單位矩陣。求解對稱矩陣Q（

23、pp，）的特征值和特征向量，所得最大特征值所對應的特征向量即為旋轉四元數(shù)qR=q0,q1,q2,q3T。計算平移向量qR=p，-R*p，最終生成一個配準向量q。6 總結本文從配準元素的選擇、配準策略的確定和誤差函數(shù)的求解等三個方面對ICP算法的各種改進和優(yōu)化進行了分類和總結。通過文中的分析可以發(fā)現(xiàn)，ICP在這些年的發(fā)展過程中，將各種技術吸收進來，這一方面說明了ICP算法以其本身的優(yōu)勢獲得了研究者的關注，另一方面也說明研究者在對ICP算法改進上付出了不懈的努力但是ICP算法的研究還沒有停止，因為這種算法還不能解決所有的配準問題，也將還會有人繼續(xù)對這種算法展開研究，讓其變得更加完美。參考文獻 1

24、羅綱，羅斌. 圖象特征點集配準的加權相關迭代算法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): 239-256. 3 蔣成成，胡同森，周維. 一種改進的迭代最近點算法J. 計算機系統(tǒng)應用. 2009(08): 84-87. 4 張波. 基于ICP和SVD的眼底圖像配準研究D. 吉林大學, 2009.

25、5 李必卿，蔡勇. 一種改進的ICP算法在多視配準中的應用J. 機械工程師. 2009(02): 73-75. 6 任治新，羅詩途，吳美平，等. 基于改進ICP算法的地磁圖匹配技術J. 計算機應用. 2008(S1): 351-354. 7 劉承香，阮雙琛，劉繁明，等. 基于迭代最近點算法的地形匹配算法可靠性分析J. 深圳大學學報. 2005(01): 22-26. 8 Rusinkiewicz S, Levoy M. Efficient variants of the ICP algorithmC. 2001. 9 伍毅. 三維掃描信息獲取的深度圖像配準算法設計及開發(fā)D. 浙江大學, 200

26、5.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.11 G. Turk,M. LevoyZippered Polygon Meshes from Range ImagesC. Proceedings of SIGGRAPH 1994:311-318.

27、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 depth informationC. 1997.14 Sappa A,Restrepo-specht A,Uevy M.Range image registration by using an edge-ba

28、sed 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, Medioni G. Object modeling by registration of multiple range imagesC. 1991.17 Pulli K. Multiview registrati

29、on 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 performance of the ICP algorithmJ. Computational Geometry.2008,41(1-2):77-93.21 Bemardini F,Mittleman J,

30、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 through viewpoint invariant computation of curvatureC.Proceedings of ISPRS,1995:170175.23 Zhang Z. Ite

31、rative 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 efficient ICPC. 2003.25 Okuda H.HM-ICP:Fast 3-D Registration Algorithm with Hierarchical and Region Selection Approach of M-ICPC. Journal of R