朱桂林，張棟良，陳輝

　　（上海電力學(xué)院 自動化工程學(xué)院，上海市電站自動化技術(shù)重點實驗室， 上海 200090）

       摘要：針對同一物體不同視角下獲得的三維點云數(shù)據(jù)，提出一種基于改進特征點對選取的三維點云配準(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文獻標(biāo)識碼：ADOI： 10.19358/j.issn.1674-7720.2017.01.022

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

0引言

　　利用激光掃描儀對建筑物進行掃描，得到其點云信息，從而建立物體的三維模型，成為當(dāng)下研究的熱點［1］。但在實際操作中往往受到各種限制，無法一次性精準(zhǔ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)元素、錯誤點剔除以及誤差度量等方面對算法進行了改進與優(yōu)化，使傳統(tǒng)ICP算法在性能方面得到提高［47］。

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

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

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

1算法過程

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

　　（1）對應(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)。

　　（2）錯誤點對剔除

　　點集采集過程中不可避免地引入噪聲點，因此在對應(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ù)法，其計算過程如下：

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

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

　　（6）求解旋轉(zhuǎn)矩陣R

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

　　T=μq－Rμp（7）

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

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

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

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

　　（1） 讀取初始點云并在初始點云中選取點集pi；

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

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

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

　　（5）迭代終止判斷：若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。

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

　　2.1迭代次數(shù)

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

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

　　從表2可以看出，在同一迭代次數(shù)下改進算法與傳統(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，而改進的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，此時改進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ǔ)上進行對比驗證，結(jié)果如表3。

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

3結(jié)論

　　本文針對三維點云數(shù)據(jù)配準(zhǔn)耗時長、精度低兩方面的不足進行了相應(yīng)改進，提出了一種改進特征點對選取方法，通過在經(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ǔ)。

參考文獻

　　［1］ 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.

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

319.

　　［3］ 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.

　　［4］ 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.

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

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

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

　　［8］ 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.

　　［10］ 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.