朱桂林,，張棟良，陳輝

　?。ㄉ虾ｋ娏W(xué)院 自動化工程學(xué)院,，上海市電站自動化技術(shù)重點實驗室， 上海 200090）

       摘要：針對同一物體不同視角下獲得的三維點云數(shù)據(jù),，提出一種基于改進(jìn)特征點對選取的三維點云配準(zhǔn)方法,。在歐氏距離的基礎(chǔ)上選取與目標(biāo)點最近的三點均值為對應(yīng)點，并應(yīng)用鄰域比值法來剔除錯誤點,，結(jié)合Kd tree提高搜索速度,，實現(xiàn)最終點云配準(zhǔn)。實驗結(jié)果表明,，該方法具有可行性,，相比傳統(tǒng)ICP算法，其匹配精度和效率明顯提升,。

　　關(guān)鍵詞：點云配準(zhǔn),；ICP算法；最近點選取,；錯誤點剔除

　　中圖分類號：TP391文獻(xiàn)標(biāo)識碼：ADOI： 10.19358/j.issn.1674-7720.2017.01.022

　　引用格式：朱桂林,，張棟良，陳輝. 基于改進(jìn)特征點對選取的三維點云配準(zhǔn)［J］.微型機與應(yīng)用,，2017,36（1）：73-75.

0引言

　　利用激光掃描儀對建筑物進(jìn)行掃描,，得到其點云信息，從而建立物體的三維模型,，成為當(dāng)下研究的熱點［1］,。但在實際操作中往往受到各種限制，無法一次性精準(zhǔn)地獲得待測物體的全部點云信息,。為了在后期重建過程中得到較為完整的三維模型,，實際測量中需要對待測物體進(jìn)行多角度、多次數(shù)的測量并且通過點云配準(zhǔn)將獲得的點云數(shù)據(jù)變換到同一坐標(biāo)中［2］,。

　　針對點云配準(zhǔn)過程,，迭代最近點算法（Iterative Closest Point，ICP）［3］是目前比較經(jīng)典的配準(zhǔn)方法,。其優(yōu)點是對初始點云形狀要求低,，配準(zhǔn)過程簡單，結(jié)果相對收斂,。但是該算法也存在著一些不足,，如：要求待配準(zhǔn)兩片點云的數(shù)據(jù)為包含關(guān)系，兩片點云中的數(shù)據(jù)點滿足一一對應(yīng)關(guān)系,；其次隨著點云數(shù)量的增加計算代價也相應(yīng)增加,；最后在對應(yīng)點尋找過程中,，僅僅假設(shè)兩片點云中歐氏距離最近的點為所求的對應(yīng)點，由于這種假設(shè)過于理想化,，在實際操作過程中可能會出現(xiàn)錯誤的對應(yīng)點,，使配準(zhǔn)陷入局部最小值導(dǎo)致配準(zhǔn)失敗。針對傳統(tǒng)ICP算法的不足,，國內(nèi)外學(xué)者在配準(zhǔn)策略,、配準(zhǔn)元素、錯誤點剔除以及誤差度量等方面對算法進(jìn)行了改進(jìn)與優(yōu)化,，使傳統(tǒng)ICP算法在性能方面得到提高［47］,。

　　本文在三維點云配準(zhǔn)過程中分以下兩步：

　　（1）提出了一種改進(jìn)的特征點對選取方法,，過程采用Kd tree查找最近點以提高搜索效率,。對于原始點云中的一點，尋找其在目標(biāo)點云中歐氏距離最近的三點并計算三點的平均值,，以此作為對應(yīng)點，然后利用鄰域比值的方法來剔除誤匹配點,，提高匹配精度,，最后結(jié)合四元法［89］求取旋轉(zhuǎn)矩陣R及平移向量T。

　?。?）根據(jù)計算得到的初始矩陣R及平移向量T,，利用ICP算法對兩片點云進(jìn)行配準(zhǔn)。

1算法過程

　　1.1對應(yīng)點對選取和剔除錯誤點對

　?。?）對應(yīng)點對求取

　　利用Kd tree計算點集P中任一點pi(i=1,2,，...)在目標(biāo)點集Q中與其歐氏距離最近的三個點q1、q2,、q3,，分別計算三點x、y,、z的均值構(gòu)成新的坐標(biāo)(=()),，pi與構(gòu)成對應(yīng)點對(pi)。

　?。?）錯誤點對剔除

　　點集采集過程中不可避免地引入噪聲點,，因此在對應(yīng)點的計算過程中可能會產(chǎn)生錯誤對應(yīng)點對，本文采用鄰域點集比值法來檢驗對應(yīng)點對是否符合標(biāo)準(zhǔn),，并剔除錯誤點對,。由對應(yīng)關(guān)系可知，如果兩個點是對應(yīng)點則其在各自δ鄰域內(nèi)所包含的點數(shù)應(yīng)該近似相等,。實驗過程中在點云P和點云Q內(nèi)分別計算pi與以δ為半徑所構(gòu)成鄰域內(nèi)點的個數(shù)m和n,。若mn=γ(0.9≤γ≤1.1),，保留對應(yīng)點對，否則剔除,。如下圖1,。

　　1.2四元數(shù)法求配準(zhǔn)矩陣R和T

　　對于原始點云數(shù)據(jù),在求取旋轉(zhuǎn)矩陣R和平移向量T時，采用四元數(shù)法,，其計算過程如下：

　?。?） 分別計算點集{pi}和點集{qi}的質(zhì)心：

　　（5）求K的特征值并且求解最大特征值所對應(yīng)的單位特征向量d,d=［d1d2d3d4］T

　?。?）求解旋轉(zhuǎn)矩陣R

　?。?）根據(jù)R與T的對應(yīng)關(guān)系求取平移向量T

　　T=μq－Rμp（7）

　　1.3改進(jìn)ICP算法的配準(zhǔn)過程

　　ICP算法在本質(zhì)上是使用最小二乘的方法對待配準(zhǔn)的點云數(shù)據(jù)進(jìn)行最優(yōu)匹配。計算過程中重復(fù)進(jìn)行選擇對應(yīng)關(guān)系點對,，計算最優(yōu)旋轉(zhuǎn)矩陣R和平移矢量T,直到滿足正確的收斂精度函數(shù)E并使E達(dá)到最小值,。

　　式中,Pi為原數(shù)據(jù)的初始點集；Qi為Pi對應(yīng)目標(biāo)數(shù)據(jù)點集的最近點,；R為3×3旋轉(zhuǎn)矩陣,；T為3×1平移矢量。

　　配準(zhǔn)過程具體如下：

　?。?） 讀取初始點云并在初始點云中選取點集pi,；

　　（2） 利用Kd tree對點集p中任一點pi計算其在點集q內(nèi)歐氏距離最近的三個點q1,、q2,、q3，并計算,，過程對應(yīng)點對(pi),；

　　（3）采用鄰域點集比值法剔除不符合條件的對應(yīng)點,；

　?。?）采用四元數(shù)法計算旋轉(zhuǎn)矩陣R和平移矢量T；

　?。?）迭代終止判斷：若ek－ek+1<ε,，則終止迭代，否則重復(fù)（2）~（5）直至結(jié)果滿足收斂條件,。其中ε表示大于零的閾值,。

2實驗論證

　　本實驗采用的實驗數(shù)據(jù)來自斯坦福兔子（Stanford Bunny），分別選取不同視角下的兩組點云數(shù)據(jù)作為原始點云和目標(biāo)點云,，兩片點云的數(shù)量分別為35 947和30 379,。實驗平臺為：CPU 2.70 GHz，內(nèi)存4 GB，Windows7 32位操作系統(tǒng),；算法在MATLAB 2011b環(huán)境中實現(xiàn),，實驗選取的ε=0.005。

　　實驗過程中為了進(jìn)一步驗證本文方法的可行性,，減少中間誤差,，在與傳統(tǒng)ICP算法比較過程中，本文分別從迭代次數(shù)和迭代點云數(shù)量兩方面（即更改迭代次數(shù)以及更改點云數(shù)量）進(jìn)行驗證,。

　　2.1迭代次數(shù)

　　為消除實驗過程中次數(shù)對結(jié)果的影響,，對于Stanford Bunny操作過程中分別選取迭代次數(shù)為5次、10次以及15次作為一組參照進(jìn)行對比驗證,，實驗結(jié)果如表1,。表1不同迭代次數(shù)下兩種方法配準(zhǔn)效果原始數(shù)據(jù)點云圖ICP配準(zhǔn)效果圖本文配準(zhǔn)方法效果圖迭代次數(shù)5次10次15次從表1可得出，在使用相同的初始點云數(shù)據(jù)情況下：（1）迭代次數(shù)相同時,，本文所采用的改進(jìn)ICP算法所得出的配準(zhǔn)效果明顯優(yōu)于傳統(tǒng)ICP算法,；（2）隨著迭代次數(shù)增加，傳統(tǒng)ICP算法配準(zhǔn)效果逐級優(yōu)化,，但是采用改進(jìn)算法所得到的配準(zhǔn)圖像逐級優(yōu)化效果更加明顯,。

　　為了進(jìn)一步比較改進(jìn)算法相對于傳統(tǒng)ICP算法的優(yōu)勢，在基于不同迭代次數(shù)情況下分別從配準(zhǔn)時間以及配準(zhǔn)誤差兩個方面進(jìn)行列表對比,，本文采用均方根誤差［10］（Root Mean Square,，RMS）來表示配準(zhǔn)誤差，對比情況如表2,。

　　從表2可以看出，在同一迭代次數(shù)下改進(jìn)算法與傳統(tǒng)ICP算法相比在配準(zhǔn)誤差以及配準(zhǔn)時間上都得到了明顯優(yōu)化,，這種優(yōu)化隨著迭代次數(shù)的增加變得更加明顯,，例如迭代次數(shù)為5時，傳統(tǒng)ICP算法配準(zhǔn)時間為240.37 s,，配準(zhǔn)誤差為0.122 4,，而改進(jìn)的ICP算法配準(zhǔn)時間為22.70 s，配準(zhǔn)誤差為0.066 0,；當(dāng)?shù)螖?shù)為15時,，傳統(tǒng)ICP算法配準(zhǔn)時間為610.45 s，配準(zhǔn)誤差為0.037 6,，此時改進(jìn)ICP算法配準(zhǔn)時間僅為40.89 s,，配準(zhǔn)誤差為0.002 4。綜上,，無論是在同一迭代次數(shù)的橫向?qū)Ρ冗€是在不同迭代次數(shù)的縱向?qū)Ρ戎?，本文采用的配?zhǔn)方法在配準(zhǔn)效果、配準(zhǔn)時間以及配準(zhǔn)誤差上都要明顯優(yōu)于傳統(tǒng)ICP算法。

　　2.2迭代點云數(shù)量

　　為了消除點云數(shù)量對兩種方法產(chǎn)生的誤差,，本文在基于Bunny數(shù)據(jù)基礎(chǔ)上,，選取初始點云數(shù)量分別為400點、3 600點,、6 400點以及32 400點,，并在迭代次數(shù)同為15次的基礎(chǔ)上進(jìn)行對比驗證，結(jié)果如表3,。

　　根據(jù)表3,，在初始點云數(shù)較少的情況下，改進(jìn)方法與傳統(tǒng)ICP方法相比在配準(zhǔn)時間和配準(zhǔn)誤差上均有進(jìn)步,，但差別并不明顯,，如在點云數(shù)為400點時二者配準(zhǔn)時間相差為0.05 s，在小數(shù)點后精確5位的情況下配準(zhǔn)誤差同為0.089 79,。但是隨著點云數(shù)量的增加,，改進(jìn)的ICP算法與傳統(tǒng)ICP算法相比具有明顯優(yōu)勢，例如當(dāng)初始點云數(shù)量為6 400時,，傳統(tǒng)ICP算法配準(zhǔn)時間為16.00 s,，配準(zhǔn)誤差為0.046 38，而改進(jìn)ICP算法配準(zhǔn)時間僅為2.40 s,，配準(zhǔn)誤差為0.037 35,；當(dāng)初始點云數(shù)量為32 400時，改進(jìn)算法優(yōu)勢更為突出,。由表3數(shù)據(jù)分析可知,，在不同點云數(shù)量下改進(jìn)的ICP方法與傳統(tǒng)ICP算法相比，無論是在配準(zhǔn)時間還是在配準(zhǔn)誤差上都具有明顯改進(jìn),，并且隨著初始點云數(shù)量的增加,，本文改進(jìn)方法的優(yōu)勢彰顯得更為明顯。

3結(jié)論

　　本文針對三維點云數(shù)據(jù)配準(zhǔn)耗時長,、精度低兩方面的不足進(jìn)行了相應(yīng)改進(jìn),，提出了一種改進(jìn)特征點對選取方法，通過在經(jīng)典點云Standford Bunny數(shù)據(jù)集上與采用傳統(tǒng)ICP算法的配準(zhǔn)結(jié)果相比,，在配準(zhǔn)時間和配準(zhǔn)精度上都有明顯提高,。本文對點云數(shù)據(jù)配準(zhǔn)的優(yōu)化，對后續(xù)點云網(wǎng)格化以及場景重建提供了算法基礎(chǔ),。

參考文獻(xiàn)

　?。?］ TANG P B,HUBER D， AKINCI B,， et al.Automatic reconstruction of asbuilt building information models from laserscanned point clouds:a review of related techniques［J］.Automation in Construction,2010,19(7):829-843.

　?。?］ 韓寶昌，曹俊杰，蘇志勛.一種區(qū)域?qū)哟紊系淖詣狱c云配準(zhǔn)算法［J］.計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2015,，27(2):313-

319.

　?。?］ BESL P J, MCKAY N D. Method for registration of 3D shapes［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence,1992，14(2):239-256.

　?。?］ Guo Yu, BENNAMOUN M, SHOEL F, et al.3D object recognition in cluttered scenes with local surface features: a survey［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014,36(11):2270-2287.

　?。?］ 楊小青, 楊秋翔，楊劍.基于法向量改進(jìn)的ICP算法［J］.計算機工程與設(shè)計, 2016,， 37(1):169-173.

　?。?］ 許斌, 李忠科，呂培軍,，等.基于特征的點云精確配準(zhǔn)算法［J］.計算機應(yīng)用與軟件, 2013,30(11):112-115.

　?。?］ 張曉娟,李忠科，王先澤,等.基于特征點和改進(jìn)ICP的三維點云數(shù)據(jù)配準(zhǔn)算法［J］.傳感器與微系統(tǒng), 2012,，31(9):116118.

　?。?］ KUIPERS J B. Quaternions and rotation sequences［M］.Sofia: Coral Press,2000:127-143.

　　［9］ HORN B K P.Closed-form solution of absolute orientation using unit quaternions［J］.Optical Society of America, 1987,4(4):629-642.

　?。?0］ EGGERT D W, LORUSSO A.Estimating 3D rigid body transformations a comparison of four major algorithms［J］.Machine Vision and Applications, 1997,9(5):272-290.