朱桂林，張棟良，陳輝

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

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

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

　　中圖分類號：TP391文獻標識碼：ADOI： 10.19358/j.issn.1674-7720.2017.01.022

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

0引言

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

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

　　本文在三維點云配準過程中分以下兩步：

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

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

1算法過程

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

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

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

　?。?）錯誤點對剔除

　　點集采集過程中不可避免地引入噪聲點，因此在對應(yīng)點的計算過程中可能會產(chǎn)生錯誤對應(yīng)點對，本文采用鄰域點集比值法來檢驗對應(yīng)點對是否符合標準，并剔除錯誤點對。由對應(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ù)法求配準矩陣R和T

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

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

　?。?）求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改進ICP算法的配準過程

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

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

　　配準過程具體如下：

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

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

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

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

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

2實驗論證

　　本實驗采用的實驗數(shù)據(jù)來自斯坦福兔子（Stanford Bunny），分別選取不同視角下的兩組點云數(shù)據(jù)作為原始點云和目標點云，兩片點云的數(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ù)下兩種方法配準效果原始數(shù)據(jù)點云圖ICP配準效果圖本文配準方法效果圖迭代次數(shù)5次10次15次從表1可得出，在使用相同的初始點云數(shù)據(jù)情況下：（1）迭代次數(shù)相同時，本文所采用的改進ICP算法所得出的配準效果明顯優(yōu)于傳統(tǒng)ICP算法；（2）隨著迭代次數(shù)增加，傳統(tǒng)ICP算法配準效果逐級優(yōu)化，但是采用改進算法所得到的配準圖像逐級優(yōu)化效果更加明顯。

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

　　從表2可以看出，在同一迭代次數(shù)下改進算法與傳統(tǒng)ICP算法相比在配準誤差以及配準時間上都得到了明顯優(yōu)化，這種優(yōu)化隨著迭代次數(shù)的增加變得更加明顯，例如迭代次數(shù)為5時，傳統(tǒng)ICP算法配準時間為240.37 s，配準誤差為0.122 4，而改進的ICP算法配準時間為22.70 s，配準誤差為0.066 0；當?shù)螖?shù)為15時，傳統(tǒng)ICP算法配準時間為610.45 s，配準誤差為0.037 6，此時改進ICP算法配準時間僅為40.89 s，配準誤差為0.002 4。綜上，無論是在同一迭代次數(shù)的橫向?qū)Ρ冗€是在不同迭代次數(shù)的縱向?qū)Ρ戎?，本文采用的配準方法在配準效果、配準時間以及配準誤差上都要明顯優(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方法相比在配準時間和配準誤差上均有進步，但差別并不明顯，如在點云數(shù)為400點時二者配準時間相差為0.05 s，在小數(shù)點后精確5位的情況下配準誤差同為0.089 79。但是隨著點云數(shù)量的增加，改進的ICP算法與傳統(tǒng)ICP算法相比具有明顯優(yōu)勢，例如當初始點云數(shù)量為6 400時，傳統(tǒng)ICP算法配準時間為16.00 s，配準誤差為0.046 38，而改進ICP算法配準時間僅為2.40 s，配準誤差為0.037 35；當初始點云數(shù)量為32 400時，改進算法優(yōu)勢更為突出。由表3數(shù)據(jù)分析可知，在不同點云數(shù)量下改進的ICP方法與傳統(tǒng)ICP算法相比，無論是在配準時間還是在配準誤差上都具有明顯改進，并且隨著初始點云數(shù)量的增加，本文改進方法的優(yōu)勢彰顯得更為明顯。

3結(jié)論

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

參考文獻

　?。?］ 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云配準算法［J］.計算機輔助設(shè)計與圖形學學報, 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.

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

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

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

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

　?。?］ 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.