多分辨率配準點的ICP算法

王 勇，鄒 輝，何養(yǎng)明，黎 春

(重慶理工大學 計算機科學與工程學院，重慶 400054)

1 引 言

隨著計算機技術的發(fā)展，各行各業(yè)都趨于自動化和智能化方向發(fā)展，機器視覺、逆向工程、文化遺產保護等領域對自動化獲取物體的三維信息，并對其自動化分析、建模、控制等處理的需求越來越大[1].因此，激光掃描儀、結構光掃描儀等各類掃描儀應運而生.由于受到視角或技術的限制，需要對同一物體進行不同角度的測量才能獲取精確完整的物體三維信息.從不同角度測量獲取的點云數(shù)據(jù)不在同一坐標系下，因此，需對不同視角獲取的點云進行配準，配準的過程實質就是求解不同坐標系下點云間的剛性轉換關系.

目前，應用較多、精度也較高的配準算法為Besl提出的迭代最近鄰算法[2]，即ICP((Iterative Closest Point)算法.該算法通過每次迭代都在目標點集中選擇最近的點作為匹配點來估算變換矩陣參數(shù)，直到目標函數(shù)值不變或小于條件閾值為止.但該算法計算量大，速度較慢，且對點云間位姿要求較高，同時容易陷入局部最優(yōu).針對上述傳統(tǒng)ICP算法的缺陷，國內外學者相繼提出了眾多改進的ICP算法.Blais等人[3]提出將待配準點云中的點沿著目標點云視點方向穿過，與目標點云中的點相交的點作為匹配點，即點到投影的ICP算法，該算法應用范圍不廣且配準精度不高；Chen等人[4]提出將待配準點云中的點在其法線與目標點云相交的點的切平面上投影的點作為匹配點，即點到面的ICP算法，該算法的缺陷是需要計算點的投影，算法效率慢，優(yōu)點是精度較高.文獻[5]對ICP相關算法進行歸納并指出ICP算法可分為上述三類，分別為點到點、點到投影、點到面的ICP算法.Yang等人[6]首次提出一種全局最優(yōu)算法用以解決傳統(tǒng)ICP算法易陷入局部最優(yōu)的問題.文獻[7]使用點-面距離來獲取匹配點對，然后提出單應性假設，根據(jù)單應性假設對不合要求的點對進行剔除，從而達到提升配準速度的目的.楊小青[8]等人利用點云法向量夾角初步提取關鍵點，并使用主曲率約束選取初始點集，然后使用點間距離和高斯曲率來確認精確匹配點，但該方法閾值較多，較難確定，且適合特征突出的點云匹配，一旦匹配點選取錯誤，容易造成配準失敗.秦緒佳[9]等人結合法向量和直方圖，提出法向量直方圖概念，并將點的法向量直方圖特征量作為點云的特征描述子來確定匹配點對，該算法避免了直接使用法向量進行匹配帶來的歧義性問題.文獻[10]利用提出的法矢夾角度分級精簡點云，然后利用匹配度篩選匹配點，然而該方法提出的法矢夾角度不能很好的代表點的特征，精簡算法不能保證以特征點保留為主，匹配度計算復雜.

本文提出一種多分辨率配準點的ICP算法，首先利用鄰域點法向量夾角平均值信息對點云中的點進行分級，然后設置點云的分辨率，根據(jù)提出的方法對每級的點在不同分辨率下進行采樣，最后分別對不同分辨率下提取的配準點結合所提出的匹配度確定匹配點對進行迭代配準.從而解決點云配準慢，精度低的問題.

2 點云處理

2.1 點云KD-tree的構建

散亂點云中各點間并不具備任何拓撲關系，因此若尋找某點的鄰域點，需遍歷整片點云，計算量十分龐大，使得計算速度緩慢.傳統(tǒng)ICP算法速度較慢的主要原因就在于尋找點間關系，計算量較大.KD-tree是Bentley[11]提出的一種K維數(shù)據(jù)點在空間進行層次劃分的數(shù)據(jù)結構，即對K維數(shù)據(jù)點構建索引結構樹.KD-tree在K維數(shù)據(jù)的范圍和近鄰點的搜索具有速度快的特點，因此，本文對點云構建KD-tree用 以加速點間關系的查找.構建KD-tree的步驟如下：

1)分別求點云中所有點在x，y，z維度上的方差；

2)將方差最大的維度設為split域；

3)將所有點按split域的值進行排序，取中值點作為根節(jié)點；

4)將split域的值小于中值點split域的值的點分配到左子空間，反之分配到右子空間；

5)對左子空間和右子空間重復步驟1)到4)，直到只剩一個數(shù)據(jù)點.

2.2 點云法向量的估計

本文使用主成分分析法(PCA)來求取法向量，估計點云中p點的法向量的問題近似于估計該點相切面法線的問題，即可轉化為估計p點k鄰域最小二乘擬合平面的問題.

(1)

則?滿足使得下式最?。?/p>

(2)

令：

(3)

(4)

則可求得：

(5)

(6)

即：

(7)

(8)

(9)

求p點的法向量步驟如下：

3)根據(jù)式(7)求得協(xié)方差矩陣C，并求取C的特征值和特征向量；

2.3 點云曲率的估計

曲率不僅能夠描述曲面的幾何特征，而且具備縮放、旋轉以及平移不變性，是分析曲面局部特征的重要依據(jù).本文使用曲率來描述點云各點的局部特征，依據(jù)曲率信息來引導點云進行配準.

由于二次曲面具有普遍性，對各類點云適應性強，且計算簡單，因此本文采用擬合二次曲面來估計曲率.

對于點pi，利用構建的KD-tree求取其k近鄰點，記pi和其k近鄰點為Nbhd(pi)，設擬合的二次曲面η方程為：

z=f(x，y)=ax2+by2+cx+dy+e

(10)

則在Nbhd(pi)中，η滿足使得下式取值最?。?/p>

(11)

分別對式(11)中各系數(shù)求導，并使其值為0，然后聯(lián)立式(11)即可求解各系數(shù)，從而得到擬合二次曲面方程z=f(x，y).曲面的參數(shù)方程為：

P(x，y)=(xyz，(x，y，f(x，y)))

(12)

(13)

由曲面第一和第二基本形式可得：

(14)

從而可得高斯曲率K、平均曲率H、主曲率k1和主曲率k2為：

(15)

(16)

(17)

(18)

3 多分辨率配準點的ICP算法

3.1 多分辨率關鍵點的采樣

點云的局部法向量變化可以表征該局部曲面的彎曲程度，法向量變化越大，曲面起伏越大，向量變化越小，曲面越平坦.因此，本文提出使用法向量夾角平均值來度量點的特征，以此為依據(jù)提取點云的關鍵點.對于任意一點pi，使用構建的KD-tree求取其k近鄰點，則該點法向量夾角平均值Mi定義如下：

(19)

點云的特征信息是由所包含的所有點共同來決定的，主要表現(xiàn)為特征明顯的關鍵點的特征信息，關鍵點的特征信息并不能完全代表點云的特征信息.因此本文以特征明顯的關鍵點為主，特征不明顯的點為輔來配準點云.首先，根據(jù)式(19)計算出的向量夾角平均值對點云中的點分為m級，則第i(1≤i

minM+(i-1)*G≤Mi

(20)

(21)

其中minM為點云所有點法向量夾角平均值最小值，maxM為最大值.

對于各種傳統(tǒng)ICP的改進算法，實質為權衡速度和精度的問題.關鍵特征點選取越少，計算量越少，收斂速度越快，相應精度也會降低；選取越多，計算量越大，收斂速度越慢.本文提出使用多分辨率配準點來指導點云配準.首先利用低分辨率匹配點對進行配準，使要配準的點云迅速收斂，此時配準精度較低；然后使用高分辨率匹配點對進行配準，提高配準精度，由于在已收斂的配準點云基礎上進行迭代配準，收斂速度會大大提升.

設最大分辨率為n，則分辨率為j(1≤j≤n)時，第i(1≤i≤m)級提取點的采樣比例為：

(22)

其中，countm為第m級總點數(shù)，counti為第i級總點數(shù)，fix為向零取整.

由上式可看出，級別越大，采樣比例越大，且各級之間采樣呈指數(shù)關系.同時，本文引入Logistic模型，其曲線為S型曲線，具備開始增長迅速，后來增長緩慢的特點，符合點云多分辨率配準思想；先采樣少數(shù)點進行迅速配準，然后大幅增加采樣點，提升配準精度，最后小幅增加采樣，使點云整體收斂.各分辨率間采樣呈S型增長.

3.2 改進的ICP算法

配準的過程即是求解待配準源點云到目標點云的剛性旋轉R和平移T的過程，如公式(23)所示.

(23)

在實際測量中，點云的采集不可避免帶入噪聲，往往點云間的數(shù)據(jù)并沒有絕對的一一對應關系，因此ICP算法實質是基于最小二乘原則保證計算得到的旋轉矩陣R和平移向量T使得目標函數(shù)最小，即求解目標函數(shù)的最優(yōu)解.目標函數(shù)形式多樣，本文使用點到點距離平方和作為目標函數(shù)，如式(24)所示：

(24)

上式中Qi為目標點集，Pi為待配準點集(源點集)，N為匹配點對總數(shù).

對于選取最近點匹配策略，通?？赡軐е鲁霈F(xiàn)大量錯誤匹配點，本文提出使用匹配度來選擇匹配點，以提高匹配點對的匹配準確性.對于任意一點pi，使用構建的KD-tree求取其在目標點集Q中的k近鄰點，則該點與其各近鄰點qj的匹配度定義如下：

(25)

其中pi1、pi2、pi3、pi4分別為點pi的主曲率k1、k2，高斯曲率K，平均曲率H，同理，qj1、qj2、qj3、qj4分別為點qj的主曲率k1、k2，高斯曲率K，平均曲率H.在微分幾何中，兩個主曲率衡量了曲面在某點處指定方向的彎曲程度和彎曲方向，高斯曲率反映了曲面在某點處總的彎曲程度，平均曲率描述了曲面在某點處平均彎曲程度.因此，由式(25)可知，兩點越相似，則其匹配度越小.

分別計算pi和其k近鄰點的匹配度W(pi，qj)，選取W(pi，qj)值最小的點作為pi的匹配點.

為進一步降低配準計算過程的時間復雜度，只有需要使用點pi和點qi的曲率時才計算其曲率并存儲，若其曲率存在，則不進行計算.

四元數(shù)法[12]不僅易于實現(xiàn)，且在匹配點對較多的情形下計算量小，本文使用四元數(shù)法來對上述方法獲取的匹配點對求取旋轉矩陣R和平移向量T.

改進的多分辨率配準點的ICP算法步驟如下：

1)計算點云集P中所有點pi的法向量夾角平均值Mi；

2)根據(jù)式(20)將P中的點分為m級并設置最大分辨率n；

3)根據(jù)式(22)計算分辨率為j(1≤j≤n)，第i(1≤i≤m)級點的采樣比例Ri，j；

4)計算分辨率為j(1≤j≤n)，第i(1≤i≤m)級采樣點數(shù)Ci，j=counti·Ri，j，若分辨率j=1，對第i級隨機采樣Ci，j個點，否則，在已采樣點的基礎上再隨機采樣Ci，j-Ci，j-1個點；

5)由式(25)求取采樣點的匹配點，若某點沒曲率信息，則計算其曲率信息并存儲；

6)對步驟5)獲得的匹配點對使用四元數(shù)法計算，獲取旋轉矩陣R和平移向量T；

7)使用步驟6)獲得的R和T對P利用式(23)進行變換，得到新的點云集P；

8)重復步驟5)到7)直到使得式(24)最?。?/p>

9)若分辨率不為n，則進入下一分辨率，返回步驟3).

4 實驗結果

本文實驗在Intel(R) Core(TM)i3-2120 CPU、4GB內存、Windows 7操作系統(tǒng)、Matlab 2012b環(huán)境下進行.為驗證本文所提出算法的有效性，分別和傳統(tǒng)ICP算法、文獻[10]改進的ICP算法實驗結果進行對比，實驗數(shù)據(jù)來源于斯坦福大學開放點云數(shù)據(jù)庫的Bunny和Dragon模型.由于點云數(shù)據(jù)不具備完全的一一對應關系，業(yè)內還沒有被普遍被認可的評價配準誤差的方法[13]，本文使用文獻[13]中所提方法來評價配準誤差.

圖1為對Bunny進行配準實驗.本文算法中估計點云法向量、曲率以及選取目標點集配準點的k值均設為8，m=3，n=6.圖1(a)為Bunny兩視角(0度和45度)配準前點云圖，兩片點云點數(shù)分別為40256和40097；圖1(b)為傳統(tǒng)ICP配準效果圖，可以看出兔子耳朵、尾巴部分有一定偏差；圖1(c)為文獻[10]改進的ICP算法配準結果，較傳統(tǒng)ICP算法有一定的改進，但尾巴部分仍有偏差；圖1(d)為本文所提出的算法配準結果，可以看出配準效果強于上面兩種算法.

圖1 Bunny配準實驗Fig.1 Bunny registration experiment

表1為三種算法配準速度和配準誤差結果.從表中可以看出傳統(tǒng)ICP算法比較耗時，主要是由于查詢匹配點和迭代過程較慢；文獻[10]算法根據(jù)點云特征精簡了配準點，在查詢鄰域點上使用KD-tree加速，并且根據(jù)所提出的方法篩選匹配點對，一定程度上降低了迭代次數(shù)并提高了匹配點對的匹配精度，在精度和速度上都有一定提升；而本文提出的多分辨率匹配點ICP算法，根據(jù)點云特征，選取少數(shù)匹配點對快速配準，然后增加匹配點對，提高配準精度，在查詢鄰域點上使用KD-tree加速，在選擇匹配點對上，使用所提出的匹配度選擇匹配點，增加匹配點對的匹配精度，無論在精度還是速度上，較文獻[10]算法都有進一步的提升.

表1 不同算法配準結果Table 1 Registration results of different algorithms

為進一步驗證本文算法的有效性，使用曲面更為復雜的Dragon點云數(shù)據(jù)集進行實驗.本文算法中估計點云法向量、曲率以及選取目標點集配準點的k值均設為8，m=5，n=8.圖2(a)為Dragon兩視角(24度和48度)配準前點云圖，兩片點云點數(shù)分別為34836和22092；圖2(b)為傳統(tǒng)ICP配準效果圖，可以看出配準效果較差，頭部和尾部偏差較大；圖2(c)為文獻[10]算法配準效果，可以看出，總體效果較傳統(tǒng)ICP算法有所改進，頭部杈角處和尾巴比傳統(tǒng)ICP好，但嘴巴和尾巴拐角處比傳統(tǒng)ICP差.圖2(d)為本文所提出的算法配準效果，可以明顯看出配準較為準確，能較好的體現(xiàn)Dragon模型頭部、身體、足部、尾部輪廓特征.

圖2 Dragon配準實驗Fig.2 Dragon registration experiment

如表2所示，隨著點云數(shù)據(jù)的減少，三種方法配準耗時都有所縮短，其中傳統(tǒng)ICP算法縮短幅度最大，本文算法縮短幅度最小，但本文算法效率仍遠遠高于其他兩種算法；由于Dragon表面較為復雜，三種配準算法誤差都有所提升，傳統(tǒng)ICP不能完成兩片點云的配準，誤差較大，文獻[10]算法勉強完成了配準，但精度還達不到要求，本文算法配準效果較好，誤差較小，精度遠遠高于其他兩種算法.

表2 不同算法配準結果Table 2 Registration results of different algorithms

表3 不同規(guī)模點云耗時Table 3 Time consuming of different size of point clouds

為驗證本文算法的執(zhí)行效率，分別對不同規(guī)模的點云進行配準，其耗時如表3所示，根據(jù)表3，分別計算本文算法相對傳統(tǒng)ICP算法和文獻[10]算法所提高的百分比并繪制折線圖，所繪折線圖如圖3所示，可以看出，本文算法相比傳統(tǒng)ICP算法，速度提升了77%以上，相比文獻[10]算法，速度提升了62%以上，且隨著點云規(guī)模的增大，有遞增的趨勢.

圖3 提升百分比折線圖Fig.3 Line chart of percentage increase

5 結 論

本文提出了一種多分辨率配準點的ICP算法.該算法使用法向量夾角平均值來度量點云各點的特征；引入分級和多分辨率概念，以特征關鍵點為主，非特征關鍵點為輔來選取配準點，利用低分辨率下選取的少數(shù)匹配點對迅速完成配準，利用高分辨率下選取的大量匹配點對提升配準精度；在選取匹配點對方面，利用點的曲率信息計算所提出的匹配度，根據(jù)匹配度在目標點集局部區(qū)域確定匹配點對；在估計點云法向量、曲率，計算法向量夾角平均值、匹配點中的查詢鄰域點方面，使用KD-tree加速，并且在確定匹配點對時，根據(jù)計算需要來計算相應點的曲率信息，從而簡化配準過程中的時間復雜度.上述實驗表明，本文算法較傳統(tǒng)ICP算法和文獻[10]算法，在精度和速度方面都有明顯提升，且速度提升幅度隨點云規(guī)模增加有遞增趨勢.

[1] Zhang Yu-wei.Research on three-dimensional topography measurement using structured light [D].Harbin：Harbin Engineering University，2012.

[2] Besl P J，McKay N D.A method for registration of 3-D shapes[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1992，14(2)：239-256.

[3] Blais G，Levine M D.Registering multiview range data to create 3D computer objects[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1995，17(8)：820-824.

[4] Chen Y，Medioni G.Object modelling by registration of multiple range images[J].Image and Vision Computing，1992，10(3)：145-155.

[5] Jie Ze-xiao，Xu Shang.A survey on the ICP algorithm and its variants in registration of 3D point clouds [J].Periodical of Ocean University of China，2010，40(1)：99-103.

[6] Yang J，Li H，Campbell D，et al.Go-ICP：a globally optimal solution to 3D ICP point-set registration[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2016，38(11)：2241-2255.

[7] Wei Sheng-bin，Wang Shao-qing，Zhou Chang-he，et al.An iterative closest point algorithm based on biunique correspondence of point clouds for 3D reconstruction [J].Acta Optica Sinica，2015，35(5)：252-258.

[8] Yang Xiao-qing，Yang Qiu-xiang，Yang Jian.Improved ICP algorithm based on normal vector [J].Computer Engineering and Design，2016，37(1)：169-173.

[9] Qin Xu-jia，Xu Fei，Wang Jian-qi，et al.Point clouds ICP registration based on normal histogram feature description [J].Journal of Chinese Computer Systems，2016，37(3)：593-597.

[10] Yang Qiu-xiang，Wang Cheng-yuan，Yang Jian.Improved ICP algorithm based on included angle of normal vector [J].Computer Engineering and Design，2016，37(8)：2082-2086.

[11] Bentley J L.Multidimensional binary search trees used for associative searching[J].Communications of the Acm，1975，18(9)：509-517.

[12] An Yan-yan.Research on three-dimensional image mosaic algorithm [D].Taiyuan：North University of China，2015.

[13] Wang Xin，Zhang Ming-ming，Yu Xiao，et al.Point cloud registration based on improved iterative closest point method [J].Optics and Precision Engineering，2012，20(9)：2068-2077.

附中文參考文獻：

[1] 張雨薇.基于結構光的物體三維形貌測量[D].哈爾濱：哈爾濱工程大學，2012.

[5] 解則曉，徐 尚.三維點云數(shù)據(jù)拼接中ICP及其改進算法綜述[J].中國海洋大學學報，2010，40(1)：99-103.

[7] 韋盛斌，王少卿，周常河，等.用于三維重建的點云單應性迭代最近點配準算法[J].光學學報，2015，35(5)：252-258.

[8] 楊小青，楊秋翔，楊 劍.基于法向量改進的ICP算法[J].計算機工程與設計，2016，37(1)：169-173.

[9] 秦緒佳，徐 菲，王建奇，等.基于法向量直方圖特征描述的點云ICP拼接[J].小型微型計算機系統(tǒng)，2016，37(3)：593-597.

[10] 楊秋翔，王程遠，楊 劍，等.基于法矢夾角的改進ICP算法[J].計算機工程與設計，2016，37(8)：2082-2086.

[12] 安雁艷.三維圖像拼接算法的研究[D].太原：中北大學，2015.

[13] 王 欣，張明明，于 曉，等.應用改進迭代最近點方法的點云數(shù)據(jù)配準[J].光學精密工程，2012，20(9)：2068-2077.