一種基于K-D樹優化的ICP三維點云配準方法

劉　江,張　旭,朱繼文

(1.黑龍江工程學院 測繪工程學院，黑龍江 哈爾濱 150050；2.北京建筑大學 測繪與城市空間信息學院,北京 100044)

?

一種基于K-D樹優化的ICP三維點云配準方法

劉江1,張旭2,朱繼文1

(1.黑龍江工程學院 測繪工程學院，黑龍江 哈爾濱 150050；2.北京建筑大學 測繪與城市空間信息學院,北京 100044)

摘要：為提高三維點云數據配準精度和速度，提出一種基于K-D樹優化的ICP三維點云配準方法，首先采用中心重合法實現點云數據的粗配準，然后利用K-D tree快速搜索最近點對改進傳統ICP方法，完成三維點云數據精配準，該方法克服傳統ICP算法中由于利用歐式距離來判斷最近點所引起的工作量大、耗費時間多的缺陷，提高點云的配準速度。在此基礎上利用斯坦福不同密度Bunny點云數據進行實驗驗證，結果表明在采用中心重合法實現三維點云粗配準的基礎上，利用K-D tree優化ICP算法，能夠提高點云配準的精度、速度和穩定性。

關鍵詞：點云配準；k-d tree；中心重合；精度；穩定性

隨著數字城市不斷向前發展，大規模三維數據采集技術迅速提升，由激光原理、攝影測量原理等方式產生多種點云數據。這些三維點云數據不僅可以記錄物體的空間信息，同時還可以得到物體表面的幾何信息。在實際獲取點云數據時考慮到測量設備、測量范圍的限制以及被測物體外形的復雜性等，每次掃描只能獲取當前視點下的點云，其坐標是相對于當前的儀器坐標系而言的，要得到被測物體完整的三維模型，需要從不同的視點對被測物體進行掃描，并將不同視點獲取的點云數據進行配準。

H.Alt等提出基于Hausdorff距離和Frechetl距離幾何結構形狀的配準[1]。其中，在解決噪聲點和局部遮擋等問題上Hausdorff距離體現出明顯的優勢，同時Hausdorff距離解決在計算變形時歐式距離所產生的扭曲與失真[2]。Frechetl距離是基于收斂性提出的，因此配準后的點云數據具有很強的收斂特性。Barequet等提出以有向腳標對部分表面進行配準，用這種方法進行配準既簡單而又快速，但是不足之處是配準結果的精確度不高[3]。這些算法彼此之間存在著一定的共性，都是根據點云或曲面尋找特征相似的區域，尋求最佳的目標函數，利用目標函數值最小化來提高配準的精度。ICP算法最初由Besl和Mckey提出，是一種點配準方法，但配準的效率不高、耗費時間長，需要對算法進行一定的改進。在本文應用k-d tree的方法對ICP算法進行改進，進一步提高點云的配準效率。

1改進的三維點云配準算法

點云配準大致分成兩個過程粗配準和精配準，粗配準是對點云數據的重疊部分進行大致擬合，為精配準提供平移和旋轉參數的初始值，精配準是在粗配準的基礎上進行再次配準，使用這種配準方式可以提高配準的準確度。目前，粗配準的方法主要有標簽法、主方向貼合法、中心重合法等，在本文利用中心重合法進行點云粗配準。

1.1中心重合法

中心重合法在點云粗配準中利用點云A與待配準點云B的中心重合，從而降低兩組點云數據之間的平移差值。

1)計算點云A與點云B對應點集的質心

(1)

(2)

(3)

(4)

對兩組點云數據進行中心重合，可縮小點云之間的平移錯位，為下一步的精配準提供初始位置，提高點云的配準精度。

1.2精配準

在三維點云數據配準過程中，計算旋轉變換矩陣和平移矩陣，這是任何一種算法都不可避免的。在利用粗配準得到的初始位置，本文選用ICP算法進行點云精配準，并在算法中用單位四元數算法求解迭代過程中的旋轉矩陣。

1.2.1單位四元數算法

1)求解兩組對應點集協方差

(5)

式中：∑ab兩點集協方差；N為點云數目；

2)計算出反對稱矩陣

(6)

式中：∑ba為∑ab的轉置據矩陣。

3)利用求得的反對稱矩陣A中A23,A31,A12位置上的元素定義一個新的列向量，Δ=[A23,A31A12]′.

4)用列向量Δ與上面的協方差∑ab組成一個新的4階矩陣

(7)

式中：E3為一個三階的單位矩陣；Δ′為Δ的轉置矩陣；tr(∑ab)為協方差∑ab的跡。

(8)

式中:q0,q1,q2,q3為四元向量的參數；

(9)

1.2.2ICP算法

ICP算法在點云配準中廣泛應用，特別是在精配準過程中，在點云配準中進行迭代運算，配準精度高、效果可靠。ICP算法步驟：

1)確定對應點對：由點云A中的點在待配準點云B中搜索出相應的最近的點，組成對應點對。

2)計算兩組新點集的質心，按照式(1)和式(2)計算新點集質心。

3)計算目標函數f(Rk,Tk)，以目標函數值最小為原則。

(10)

式中：Rk為最優旋轉矩陣；Tk為平移矩陣；f(Rk,Tk)為目標函數值。

4)用最優旋轉矩陣Rk和平移矩陣Tk，使配準點云B坐標變換到Bk+1。

(11)

5)計算點對的平均距離

(12)

(13)

1.3ICP算法改進

ICP算法雖然在配準中廣泛應用，但算法本身配準的效率低、花費時間長，特別在海量的點云數據中更為明顯。因此需要對ICP算法進行改進，以提高配準的效率。傳統的ICP算法以歐式距離為衡量標準來判斷最近點，這種方式工作量大、耗費時間多。而利用K-Dtree能快速搜索最近點對，提高點云的配準效率。

圖1為ICP算法配準流程，在尋找最近點對時，利用K-Dtree搜索最近點。其搜索步驟如下:

圖1　ICP算法配準流程

1)將待查詢的結點與所確定的分裂維的值進行比較，若小于等于分裂維的值進入左子樹分子；若大于分裂維的值就進入右子樹分支，這種方式循環到二叉樹的葉子結點，沿著搜索路徑找到處于和待查詢點同一子空間的最近鄰近似點；

2)對點進行“回溯”操作，若在搜索路徑上結點的其它子空間結點上有更近點，則跳到子空間結點上去搜索距離最近點；

3)反復進行步驟①和②到搜素路徑為空結束搜索。

2實驗驗證與分析

本文采用的是斯坦福Bunny點云數據，其中稀疏點云分辨率低，點云數目為112 782；密集點云分辨率高，點云數目為330 406。兩組點云數據都是在不同視點下且存在著一定平移旋轉平移。其中圖2為2組點云數據的示意圖。

圖2　原始點云數據

對圖2中的稀疏以及密集點云按照本文方法分別粗配準，得圖3所示的點云數據粗配準結果圖。

圖3　點云數據粗配準結果

在圖3粗配準的基礎上，采用ICP對其精確配準。得圖4所示的點云數據精配準結果圖。

圖4　點云數據ICP精配準結果

在圖3粗配準基礎上，采用改進ICP算法對其精配準，得圖5所示點云數據精配準結果圖。

圖5　改進的ICP配準結果

對實驗結果分析得到傳統ICP算法迭代次數與配準誤差關系圖，見圖6；K-D樹優化ICP算法迭代次數與配準誤差關系圖，見圖7。

圖6　迭代次數，誤差關系

圖7　改進后迭代次數，誤差關系

從實驗結果圖6和圖7上可以發現：

1)在配準誤差上：前5次的迭代中誤差雖然隨著迭代次數的增加而逐漸減少，而在圖7中前5次的迭代中誤差減小的幅度大而快。傳統的ICP算法誤差減小的幅度要比改進的ICP算法小的多，即在誤差上改進的ICP算法要優于傳統的ICP；

2)在迭代次數上：在相同的15次迭代中傳統的ICP算法要得到與改進后ICP算法相同的配準效果，要進行更多的迭代次數。即在迭代次數上改進的ICP算法要優于傳統的ICP算法；

3)對相同兩組點云數據進行配準，在配準的時間上，傳統的ICP算法迭代的次數要多，誤差減小的幅度要慢，改進的ICP在配準的過程中耗費的時間比傳統算法小的多。傳統ICP算法對點云數據進行配準耗費時間為36s，而改進后算法對點云數據進行配準耗費的時間僅為1.3s，花費的時間要比傳統的ICP算法低的多。

表1說明對不同數目點云利用k-dtree改進的ICP算法進行配準比用傳統的ICP算法配準耗費的時間少的多，并在點云數量較多時表現更為明顯，則可得在點云配準中利用k-dtree改進的ICP算法能提高配準效率。

表1　點云實驗配準時間統計

3結束語

本文采用中心重合法實現點云數據的粗配準，然后利用k-d tree快速搜索最近點對改進傳統ICP方法，完成三維點云數據精配準。該方法提高三維點云數據配準的精度和速度，特別在海量點云數據和不同密度三維點云數據應用中更為明顯，而且具有較好的穩定性。但是對于大型點云數據，該方法效率還是不能完全滿足應用需求，在搜索策略需進一步的改善。

參考文獻：

[1]張蕾,冀治航,普杰信.約束改進的ICP點云配準方法[J].計算機工程與應用,2012(18):197-200.

[2]馬婷.點云數據的顯示及配準[D].長春:吉林大學,2007.

[3]王蕊,李俊山,劉玲霞.基于幾何特征的點云配準算法[J].華東理工大學學報(自然科學版),2009,(05):768-773.

[4]朱寧寧.基于共面條件的點云配準旋轉角參數求解方法[J].測繪與空間地理信息，2015，38(5)：202-205.

[5]吳祿慎,孔維敬.基于特征點的改進ICP三維點云配準技術[J].南昌大學學報(工科版),2008(3):294-297.

[6]鄭德華.ICP算法及其在建筑物掃描點云數據配準中的應用[J].測繪科學,2007,32(2):31-32.

[7]吳靜,靳奉祥,王健.基于三維激光掃描數據的建筑物三維建模[J].測繪工程,2007,16(5):57-60.

[8]賀磊,余春平,李廣云.激光掃描數據的多站配準方法[J].測繪科學技術學報,2008,(06):410-413.

[責任編輯：李銘娜]

ICP three-dimensional point cloud registration based on K-D tree optimizationLIU Jiang1,ZHANG Xu2,ZHU Jiwen1

(1.School of Surveying and Mapping Engineering,Heilongjiang Institute of Technology,Harbin 150050，China；2.School of Mapping and City Space Information,Beijing University of Civil Engineering and Architecture,Beijing 100044,China)

Abstract：In order to improve the precision and speed of the three-dimensional point cloud registration,it presents a three dimensional point cloud registration based on ICP K-D tree optimization in this paper.First of all,the centre superposition method is adopted to realize the point cloud coarse registration,and then improve the traditional ICP where the K-D tree is used to quickly search the closest pair of points to enhance the speed of the point cloud registration.Finally the three dimensional point cloud coarse registration is completed precisely.The method overcomes the defects of the traditional ICP algorithm using Euclidean distance to determine the closest pair of points which is time-consuming and plains lots of work.On the basis of this method,the experiment can be verified through different density Bunny Stanford point cloud data.The result shows that using K-d tree optimization of ICP algorithm,the precision,speed and stability of the point cloud registration are improved when the centre superposition method is adopted to realize the three dimensional point cloud coarse registration.

Key words：point cloud registration；K-D tree；centre superposition；precision；stability

中圖分類號：P208

文獻標識碼：A

文章編號：1006-7949(2016)06-0015-04

作者簡介：劉江(1980-)，男，講師，碩士.

基金項目：黑龍江省自然科學基金資助項目(D201413)

收稿日期：2015-06-26,修回日期：2015-07-21