羅方燕，羅杰紅，熊建斌

（1.廣東職業(yè)技術學院，廣東佛山528041; 2.廣東石油化工學院，廣東茂名525000）

旋轉和平移雙推測的ICP配準加速算法

羅方燕1，羅杰紅1，熊建斌2

（1.廣東職業(yè)技術學院，廣東佛山528041; 2.廣東石油化工學院，廣東茂名525000）

為了提高迭代最近點(Iterative Closest Point,ICP)的運算速度，在原始ICP及其加速算法(Accelerated ICP,AccICP)的基礎上，提出旋轉和平移配準參數雙推測的加速算法。該算法通過對配準參數進行統(tǒng)一推測的AccICP進行分析，針對配準參數迭代求取過程中旋轉和平移參數存在變化不同步的情況，提出了對該倆參數進行獨立推測，只要任一參數迭代變化符合要求即可進行推測。實驗結果表明，該算法比原始ICP具有較好的加速效果；與AccICP算法相比，做到了精準推測，減少了不必要的統(tǒng)一推測。

旋轉和平移雙推測;迭代最近點算法;點云配準;加速算法

一、引言

三維點云數據拼接技術是計算機三維測量領域的研究熱點和難點，其中一個關鍵步驟是點云配準，需要將不同視角下采集的三維點云數據拼接在一起。點云拼接技術可以分為粗拼接和精確拼接兩個步驟[1-3]，粗拼接技術主要包括轉臺法、標簽法和曲面特征法等。精確拼接技術主要包括迭代最近點算法(Iterative Closest Point ICP)[4]，有向距離場方法(Signed Distance Fields)[5]，和遺傳算法(Genetic Algorithms)[6]等,其中最典型的是Besl提出的ICP算法，自提出以來，有大量的學者專家對該算法進行改進和應用研究[2,3,7-17]。

Granger等[15]提出EM-ICP改進算法，將最大期望算法(Expectation Maximization Algorithm)應用于ICP算法中，可以精確地配準大規(guī)模點云數據。在該算法中使用馬氏距離(Mahalanobis distance)代替標準ICP算法中的配準誤差公式，然后使用最大期望算法進行求解。Chetverikovd等[17]提出了一種基于LTS(Least Trimmed Squares)的Tri-ICP算法，該算法可以配準部分重疊的點云數據。Mohammadzade等[16]提出一種基于點的法向量的ICNP算法，并很好地應用于人臉識別方面。Bouaziz等[13]提出一種Sparse-ICP算法用于適應在出現(xiàn)噪聲和缺乏配準數據的情況，提高了ICP算法的魯棒性，并且不需要預先設定初始位置。在該算法中，提出了與標準ICP算法不同的配準誤差公式，在標準ICP中采用L2范數的平方，而在該稀疏ICP算法中采用L2范數的p次方，其中p∈[0,1]。

ICP算法的運行效率是研究的重點方面[18-22]，比如對實時要求比較高的深度視覺機器人中，要求對三維數據進行快速的配準，以便獲得全局環(huán)境數據。Besl[4]對ICP提出了一種基于配準參數推測的加速算法(Accelerated ICP algorithm,AccICP)，在該算法中對參數的7個變量進行統(tǒng)一推測，

本文提出將旋轉參數的推測和水平位移參數的推測分別單獨進行，參數推測是否進行，主要取決于各自最新參數的變化情況。如果最新所求取的參數狀態(tài)符合要求，則進行相應的參數推測。通過實驗驗證，該算法不僅能對ICP進行加速，而且與AccICP相比較，有很明顯的加速效果。

二、迭代最近點算法簡述

迭代最近點算法（ICP）[4]主要步驟如下：

給定兩個從不同視角下掃描測量得到的數據集X和B，其中X為點集{x}i=1Nx，點的數量為Nx；數據集B的數據形式可以為點、線或三角面等不同方式。

ICP算法的核心是循環(huán)執(zhí)行下面的計算，首先設定初始化：設循環(huán)次數k=0，待配準點云初始狀態(tài)為Ak=X，配準參數向量，點云數據集X和B之間的距離均方差dk=0。

1）求取數據集B中到最新待配準數據集Ak中每一個點的最近點，并將這些最近點集合為點云，并記為Yk=C(Ak,B)；

2）使用四元數法，求取Yk和B之間的旋轉矩陣和平移矩陣對應的配準參數向量

5）如果｜dk-dk-1｜＜τ，計算結果誤差變化小于一定小的τ，則結束計算；否則繼續(xù)迭代，返回步驟1。

三、AccICP算法分析

在ICP迭代計算過程中，前面階段主要進行比較大幅度的調整，而在后面階段主要進行微細的調整，與前面階段相比，調整的方向和幅度是有規(guī)律可循的。在AccIPC算法[4]中，當相鄰3個配準參數的夾角小于一定閥值時，可以根據最新3次的配準參數推測產生新的配準參數，若能帶來更好的收斂效果，則采用，否則棄之。該加速算法對ICP具有較好的加速效果，但同時也存在一個問題，因為配準參數由7個變量組成，其中前4個為旋轉參數，后3個為平移參數，進行參數推測時，同時作用于旋轉和平移參數。但在實際的配準過程中，可能出現(xiàn)平移參數已經到位，旋轉參數未到位，或旋轉參數已經到位，但平移參數未到位的情況。

四、最近點迭代雙推測加速算法

ICP在迭代過程中，求取的配準參數中包含旋轉參數和平移參數，不但這兩個參數求取的過程不相同，而且作用的范圍也不一樣，本算法中提出將這兩個參數進行分別獨立的推測，具體改進如下。

在原始ICP算法的基礎上，當執(zhí)行完步驟4時，執(zhí)行以下操作：

4.3）同理確定平移參數的預測尺度和方向。

4.4）將所預測的配準參數作用于數據X，如果配準誤差小于原來的誤差，則采納該配準參數的預測。

然后執(zhí)行原始ICP算法的步驟5。

五、驗證結果及分析

為了驗證該加速算法，采用斯坦福計算機圖形學實驗室的3D掃描數據庫[23]三個不同數量級別的模型，如圖1所示，其中Bunny模型有1889個點，Dragon模型有5205個點，Happy模型有7108個點。首先對原模型給予一定角度和位置的偏移產生新的模型，然后通過原始ICP、AccICP和本文所提出的加速ICP算法對新-原模型對進行配準。根據配準實驗結果，主要從配準誤差、迭代次數和執(zhí)行時間等方面進行分析。

圖1 斯坦福計算機圖形學實驗室3D數據模型

圖2和表1-3為數據模型Bunny、Dragon和Happy實驗的驗證結果。Bunny是屬于驗證數據量比較少的代表，由圖2(a)和表1可以發(fā)現(xiàn)，在該模型中，原始ICP算法進行了26次迭代，AccICP算法和本文的算法同樣迭代了17次。在圖2(a)的子圖收斂趨勢圖中，可以比較清楚的看到，從第8次的迭代開始AccICP算法開始起加快作用了收斂速度，而本文所提出的算法從4次開始就起加速作用了，比旋轉和平移參數同時預測的AccICP算法提前了4次迭代。

從表1和圖2(a)中，算法的配準精度達到了原始ICP和AccICP算法的精度，同時執(zhí)行時間比原始ICP算法稍少。在Bunny模型驗證中，AccICP算法進行了8次預測，而本文算法進行了旋轉預測7次，平移預測9次，包括旋轉和平移同時預測的有5次，總共預測了12次，比AccICP算法多了4次。通過本文算法進行了2次單獨的旋轉預測和4次單獨的平移預測，即在另一個方面不符合條件時，仍可以進行預測，加速迭代算法的收斂性。

圖2 不同ICP算法的收斂性比較

圖2(b)和表2是Dragon模型的驗證結果，三個算法中的計算誤差都符合計算要求。在原始ICP算法中總共進行了43次迭代，耗時為2.581秒，由于數據量比較大，比Bunny模型耗費時間多。AccICP和本文的算法都起到加速的作用，在該模型中，本文的算法比AccICP算法起到更好的加速作用。在AccICP算法中，從第18次開始加速，累計進行了9次有效預測加速，總共比原始ICP算法少了10次迭代。而在本文算法中，從第7次就開始加速，通過進一步的預測，加速的速度比AccICP快，分別進行了10次旋轉和平移加速，其中9次是同時進行的，最后迭代23次后達到收斂的效果。執(zhí)行效率方面也略比AccICP快，達到了加速的效果。

表1 Bunny模型的驗證結果

表2 Dragon模型的驗證結果

表3 Happy模型的驗證結果

圖2(c)和表3是數據模型Happy的驗證結果，該模型的數據量比前面2個驗證稍大，在原始ICP算法中的迭代次數和運行時間都會比較大。首先在該模型驗證中，本文的算法與其他算法同樣都到了收斂效果，在運行效率方面，比原始ICP算法快。從圖2(c)中可以發(fā)現(xiàn)，AccICP算法從第6次迭代開始加速，而文中算法從第5次就開始了加速，雖然加速的效果與AccICP相當，但與原始ICP算法48次的迭代相比較，加速后才執(zhí)行了22次的迭代，加快了算法的運算速度。同時從表3可以看到，AccICP算法進行了14次的推測，而文中算法進行了旋轉推測12次，平移推測9次，其中同時執(zhí)行的推測有8次。

從上述三維數據的驗證結果，文中算法達到了預期效果，與AccICP相比，起到了再次加速效果。在AccICP算法中，判斷的依據是當相鄰3個七元配置參數的變化情況比較穩(wěn)定時，進行線性或二次拋物線的推測，在這過程中需要這7個配置參數同時符合要求，并且同時預測。該算法不單推測的條件苛刻，而且推測后的效果也不一定符合收斂要求。

將七元配置參數分為兩種情況進行分析推測，一是四元旋轉參數符合要求時，另一種情況是三元平移參數。如果旋轉參數符合推測的條件，則進行旋轉推測，同理平移參數符合推測條件時，進行旋轉推測。兩種推測互不沖突，可以同時進行。

六、結論

本文就對經典的迭代最近點算法(ICP)及其改進的加速算法(AccICP)進行分析，在研究AccICP算法的基礎上，提出了基于旋轉參數和平移參數獨立推測新的加速迭代最近算法。該算法以ICP為基礎，在完成每次迭代后，對旋轉參數和平移參數進行單獨的推測判斷和應用，如果推測結果能達到更好的收斂效果，則采用推測結果。

文中使用斯坦福大學3D數據庫作為載體進行驗證，通過對結果進行，新的算法起到了有效的加速效果，其主要特點如下：

1)算法保證了原ICP算法的單調收斂性，確保迭代步驟之后，兩三維數據的距離越來越近。

2)與AccICP算法相比較，新的算法起到進一步加速的作用，加快了算法的收斂。

3)由于新算法是基于原ICP算法的一種加速改進，仍然是一種局部最優(yōu)化算法，在配準前需要較好地初次配置，否則不能達到配準效果。

4)該加速算法可以應用于其他ICP改進算法中，提高運行速度。

[1]Salvi J,Matabosch C,Fofi D,et al.A review of recent range image registration methods with accuracy evaluation[J].Image and Vision Computing,2007,25(5):578-596.

[2]Tam G,Cheng Z-Q,Lai Y-K,et al.Registration of 3d point clouds and meshes:A survey from rigid to non-rigid [J].Visualization and Computer Graphics,IEEE Transactions on,2013,19(7):1199-1217.

[3]Santamaría J,Cordón O,Damas S.A comparative study of state-of-the-art evolutionary image registration methods for 3d modeling[J].Computer Vision and Image Understanding, 2011,115(9):1340-1354.

[4]Besl PJ,McKay ND.A method for registration of 3-d shapes[J].Pattern Analysis and Machine Intelligence,IEEE Transactions on,1992:586-606.

[5]Masuda T.Generation of geometric model by registration and integration of multiple range images[C].in 3-D Digital Imaging and Modeling,2001.Proceedings.Third International Conference on.2001.IEEE.

[6]Chow CK,Tsui HT,Lee T.Surface registration using a dynamic genetic algorithm[J].Pattern Recognition,2004,37(1): 105-117.

[7]嚴劍鋒,鄧喀中.基于特征點提前和匹配的點云配準算法[J].測繪通報,2013,（9）:62-65.

[8]戴玉成,章愛武.三維激光掃描數據快速配準算法研究[J].測繪通報,2010,（6）:8-11.

[9]Korn M,Holzkothen M,Pauli J.Color supported generalized-icp[C].in International Confer-ence on Computer Vision Theory and Applications.2014.

[10]Dong J,Peng Y,Ying S,et al.Lietricp:An improvement of trimmed iterative closest point algorithm[J].Neuro computing, 2014.

[11]Yang J,Li H,Jia Y.Go-icp:Solving 3d registration efficiently and globally optimally[C].in International Conference on Computer Vision.2013.

[12]Ma J,Zhao J,Tian J,et al.Robust estimation of nonrigid transformation for point set registration[C].in Proceedings of IEEE conference on Computer Vision and Pattern Recognition.2013.

[13]Bouaziz S,Tagliasacchi A,Pauly M.Sparse iterative closest point[C].in Computer Graphics Forum.2013.Wiley Online Library.

[14]Maier-Hein L,M.Franz A,Santos TRd,et al.Convergent iterative closest-point algorithm to accomodate anisotropic and inhomogenous localization error[C].in IEEE Transactions on Pattern Analysis and Machine Interlligence.2012.

[15]Granger S,Pennec X.Multi-scale em-icp:A fast and robust approach for surface registration,in Computer vision—eccv 20022002,Springer Berlin Heidelberg.p.418-432.

[16]Mohammadzade H,Hatzinakos D.Iterative closest normal point for 3d face recognition[J].Pattern Analysis and Machine Intelligence,IEEE Transactions on,2013,35(2):381-397.

[17]Chetverikov D,Svirko D,Stepanov D,et al.The trimmed iterative closest point algorithm[C].in Pattern Recognition, 2002.Proceedings.16th International Conference on.2002.

[18]Chin T-J,Bustos AP,Brown MS,et al.Fast rotation search for real-time interactive point cloud registration[C].in Proceedings of the 18th meeting of the ACM SIGGRAPH Symposium on Interactive3D Graphics and Games.2014.ACM.

[19]Yu W.Fast and robust image registration for 3d face modeling[C].in Information Processing,2009.APCIP 2009.Asia-Pacific Conference on.2009.IEEE.

[20]Parra Bustos AJ,Chin T-J,Suter D.Fast rotation search with stereographic projections for 3d registration[C].in Computer Vision and Pattern Recognition(CVPR),2014 IEEE Conference on.2014.IEEE.

[21]Wu F,Wang F,Jiang P,et al.A nearest neighbor searches(nns)algorithm for fast registration of 3d point clouds based on gpgpu[C].in 2015 International Conference on Intelligent Systems Research and Mechatronics Engineering.2015.Atlantis Press.

[22]Eckart B,Kim K,Troccoli A,et al.Mlmd:Maximum likelihood mixture decoupling for fast and accurate point cloud registration[C].in 3D Vision(3DV),2015 International Conference on.2015.IEEE.

[23]Turk G,Levoy M.Zippered polygon meshes from range images[C].in Proceedings of the 21st annual conference on Computer graphics and interactive techniques.1994.ACM.

（責任編輯：魏樹峰）

Accelerated ICP Registration Algorithm Based on Expectation of Both Rotation and Translation

LUO Fang-yan1,LUO Jie-hong1,XIONG Jian-bin2
(1.Department of Information Engineering,Guangdong Polytechnic,Foshan 528041,China 2.School of Computer and Electronic Information,Guangdong University of Petrochemical Technology,Maoming 525000,China)

To increase the calculation speed of Iterative Closest Point(ICP)Algorithm,a new accelerated ICP is proposed based on the original ICP and its accelerated ICP(AccICP).Both rotation and translation registration parameters are expected in the algorithm.The whole registration parameters are expected in the AccICP,and the changes of both rotation and translation registration parameters may not be synchronized during the process of iterative calculation.Both parameters are expected respectively in the new proposed method,and it can do expectation independently if one parameter's change meets the requirement.The experimental results show that the proposed algorithm can accelerate calculation,compared with the original ICP.Compared with AccICP,it does accurate expectation,and avoids unnecessary unified expectation.

expectation of both rotation and translation;Iterative Closest Point;point cloud registration; accelerated algorithm

TP391

A

2016－08－20

羅方燕（1981-），女，廣東梅州人，實驗師，研究方向：三維數據處理。E-mail：532443807@qq.com.

國家自然科學基金項目(No.61271380)；廣東省自然科學基金項目(No.2014A030307049)

1671－802X(2016)05－0006－06