基于特征匹配的三維點云粗配準方法

郭克凡,王威娜,林 楷

(1.吉林化工學院 信息與控制工程學院，吉林 吉林 132022；2.吉林化工學院 理學院，吉林 吉林 132022；3.蘇州邁為科技股份有限公司,江蘇 蘇州 215200)

隨著激光雷達和掃描設備的不斷升級，所需要的三維信息以更低的成本和更短的時間獲取[1]，三維重構技術的應用也隨之越來越廣泛.三維點云配準是三維重構技術中的關鍵一環，一個良好的配準結果對三維重構的效果起著決定性的作用.從最經典的點云配準算法—迭代最近點(Iterative Closest Point，ICP)[2]到后來的ICP改進算法[3]，可以發現，為了保證此類算法的精確性，通常需要對點云進行粗配準，以獲得良好的初值.

在粗配準算法中，較為主流的是基于主成分分析(Principal Component Analysis,PCA)[4]及其改進方法對點云信息進行變換估計.Chung等[5]估計激光雷達采集信息點主軸方向，利用PCA算法計算出多站點云的協方差矩陣，進而求出旋轉矩陣與平移向量.Rusu等[6]提出著名的點特征描述子(Point Feature Histogram,PFH)計算不同視角點云的特征相似度，再求解剛性變換參數，此算法魯棒性較低，易受噪聲與離群點影響.Sun等[7]利用區域曲率圖(Regional Curvature Maps，RCM)對三維點云的局部特征進行描述，將RCM子區域作為待配準點云的對應特征依據，利用幾何一致性實現粗配準，該方法在一定程度上提升了配準精度.Fischler等[8]提出基于隨機抽樣一致算法(Random Samle Consensus,RANSAC)框架的方法，利用點云數據的重疊區域尋找特征點，進而計算剛性變換參數，該算法利用重復選擇的方式尋找最優解，但由于其簡單的利用概率作為約束條件，造成算法穩定性較低的缺陷，在含有噪聲的環境中易產生誤匹配.陶海躋等[9]利用RANSAC與特征直方圖融合的方式，根據局部法向量選取點云數據的信息點，建立幾何特征直方圖后篩選對應配準點，再通過RANSAC算法對不同視角點云進行約束，求解旋轉矩陣與平移向量.此算法大幅提升了配準的有效性，但當點云信息不明顯或點云密度降低時，算法性能易受到影響.

根據以上的研究，提出一種基于特征匹配的三維點云粗配準算法.該算法根據源點云與目標點云的法向量變化程度選取特征點集并對特征點集中的點建立特征直方圖，然后利用特征直方圖獲取相匹配的點對，根據剛性不變原則和RANSAC算法消除誤配準的點對，求解出剛性變換參數.為了提升算法效率，加入了特征保留權值δ，通過對特征保留權值δ的設定，提高了算法的配準效率.算法流程如圖1所示.

圖1 算法流程圖

1 基于特征匹配的三維點云粗配準

1.1 特征點集的選取

在基于特征匹配的點云配準中，為達到快速有效配準的目的，首先要選取特征點集.對于點集的特征描述采用法向量的方法，通過對點云法向量的求解可以發現：在點云的不同區域內，法向量有著不同程度的變化，如圖2所示.圖2(a)所示區域點的法向量變化程度不大，相對平緩；圖2(b)所示區域點的法向量變化程度相對較大.

(a) 平坦曲面法向量

(b) 凹凸曲面法向量圖2 不同區域的法向量

選取區域內法向量變化較大的點為特征點，可以更好地表現點云的面特征，具有較高的區分度，便于找到相匹配的點.特征度用該點的法向量與其鄰域內其他信息點的法向量夾角的均值表示，即：

(1)

其中h為點pi的近鄰點個數；αij表示點pi的法向量與其近鄰點pj的法向量的夾角.為了提高算法的效率，加入特征保留權值δ來進行調整特征度，定義為：

(2)

根據上面對特征度的定義可以看出：特征度的大小與區域內起伏變化的程度成正比關系，因此點云中的特征點選取可根據定義的特征度來完成.為了減少后續的計算量，引入閾值o1將點云中起伏變化不明顯的部分去除掉，即保留下來的初始特征點均滿足fj>o1，對于保留下來的初始特征點中任意點pm，如果滿足：

f(pm)=max[f(pm1),f(pm2),…,f(pm)] ，

(3)

則將初始特征點pm視為特征點，其中f(pm)為特征點pm在鄰域內其他近鄰點的特征度.將需要配準的點云中的源點云設為點云P，目標點云設為點云Q，根據提出的方法，分別對目標點云P和源點云Q的特征點進行提取，得到的特征點集分別為Pt={pt1,pt2,pt3,…,ptm′}、Qt={qt1,qt2,qt3,…,qtn′}，其中m′為源點云P的特征點個數，n′為目標點云Q的特征點個數.

1.2 建立特征直方圖

待配準的兩片點云通常不具有相同的空間結構關系，其稀疏程度也不相同，而且點云當中可能還會存在噪聲，所以將夾角作為特征量的方法[10-11]在實際應用的場景當中描述的特征信息相對較少，不容易區分特征點使得無法達到理想的效果.為解決不容易區分特征點的問題，采用特征直方圖的方法，利用特征直方圖將特征點及其鄰域內其他特性進行統計，并將特征點及其鄰域內的幾何特征采用特征向量的方式進行描述.

在以往的算法中，描述點云特征多為單一的特征值，并且這些特征值往往都較為接近，因此使點云當中一些特征變化不明顯的點無法被有效地區分.基于上述分析，在描述點云方面使用特征直方圖的方法，可描述更多的特征信息，便于區分不同特征的點云.提出的特征直方圖方法如下：

1.在源點云P中任取一點pti，將pti視為球心，以r為半徑構建球域，把球內的所有區域看作是pti的近鄰域，因此，球內的所有點都是pti的近鄰點記作N(pti)，如圖3所示.

圖3 N(pti)示意圖

2.根據點Pti和N(Pti)的關系，選取以下3個空間特征：

f1=acos ，

(4)

f2= ，

(5)

f3=‖sh-pti‖ ，

(6)

在上述公式中，ni代表點pti的法向量；vk代表點pti某一近鄰點的法向量；sk代表點pti某個近鄰點的三維空間坐標.f1表示pti的法向量與它某一近鄰點法向量之間的夾角，并且夾角通常在[0-π/2]區間內，所以將f1描述為4個區間，分別是0-π/6、π/6-π/3、π/3-π/2、π/2-π.f2代表pti的法向量與其鄰域內某一點的點間向量的點積，根據點積值的正負，將f2分成兩個部分.f3代表pti和其某一近鄰點之間的歐式距離，選擇r/4、r/2、3r/4這3個閾值，將f3分成4個部分.根據f1、f2、f3的劃分，可構建一個4×2×4=32維的三維點云特征描述直方圖.

3.確定特征點及其鄰域內其他信息點在特征直方圖中的位置.根據“2.”中得到的結果，f1的值在0-π/6、π/6-π/3、π/3-π/2、π/2-π內分別記作1、2、3、4；根據f2的正負，將f2記作0和1，如果f2為負數，將f2記作1，否則記作0；r/4、r/2、3r/4將f3劃分為0-r/4、r/4-r/2、r/2-3r/4和3r/4-r4個區間，f3的值在這3個區間內分別記作1、2、3、4.

fidex=k1+k2×4+k3×2 ，

(7)

從式(7)可以看出，fidex的結果可以得到點pti在特征直方圖的具體位置，按照此過程遍歷pti鄰域內所有點，得到落入直方圖不同位置的數量，然后除以鄰域內點的總數，便可獲得點pti的特征向量.按照此方法分別對源點云P和目標點云Q中的所有特征點建立特征向量.

1.3 初始匹配點對數組的獲取

根據1.2節中建立的特征向量，在Pt和Qt中尋找特征相同或者相近的點，把它們看作匹配點對.在相似特征點的區分上，將特征向量之間的歐式距離作為衡量標準.因為點云存在不重疊的部分，所以在Pt和Qt中存在無法匹配的點，因此要設置一個閾值o2，去除掉歐式距離大于o2的誤匹配點對，將篩選后的點對視為初始匹配點對，記作

(8)

其中num(SMatchdots)是匹配點對的數量.

1.4 精確匹配點對數組的獲取

點云數據集中通常存在很多相似的點對，所以單純的依靠歐式距離篩選出的匹配點對往往存在較大的誤差，因此需采用其他方法在得到初始匹配點集的基礎上篩選出正確的匹配點對.

將剛性不變約束條件與自適應的RANSAC算法相結合，從初始匹配點集中篩選出正確的匹配點對.在初始匹配點對中的任意兩個點對(si1,si2)和(sj1,sj2)，如果他們的匹配關系都是正確的，根據剛性不變性可以得到dist(si1,si2) =dist(sj1,sj2)，因為在兩個點云當中很難找出對應關系百分百正確的點對，所以正確匹配點對只需滿足dist(si1,si2)≈dist(sj1,sj2).因為是近似關系，所以要設置合適的非負閾值o3，確保篩選出的點對可以滿足配準要求.則SMatchdots中一個點對(sj1,sj2)滿足下式：

(9)

則將點對(sj1,sj2)記為相對于點對(si1,si2)的符合距離約束的點對.

1.5 計算配準參數

根據1.4節中獲得的正確匹配點集，運用四元素法[12]計算獲得初始配準參數，旋轉矩陣R和平移向量t.根據

(10)

綜上所述，基于特征匹配的三維點云粗配準的算法描述為：

步驟1：計算點云的特征度.

將輸入的源點云P和目標點云Q根據公式(2)計算其點云數據的特征度.

步驟2：篩選特征信息點.

選擇適當的保留參數，對特征度大于保留參數的信息點作為源點云與目標點云中信息變化程度較好的特征點云.

步驟3：建立特征直方圖并且構建初始對應關系.

依次將點云P、Q中的信息點p作為球心做一個半徑為r的球形點云包圍盒，根據公式(3)的描述將信息點與包圍盒內的特征關系構建特征直方圖.對比直方圖的相同程度篩選出點云的對應關系.

步驟4：利用剛性不變約束以及RANSAC算法求解粗配準特征點對.

由于相同模型的源點云與目標點云的變換是剛性變換，所以可以使用剛性不變性約束步驟3中匹配點的對應關系，并利用RANSAC方法驗證其準確性，得到滿足要求的信息點之間的對應關系.

步驟5：求解對應點之間的配準參數.

利用四元素法根據公式(10)求解目標點云與源點云之間剛性變換的旋轉矩陣R和平移向量t.

2 實驗結果分析

2.1 實驗設置及評價指標

為了驗證提出算法的有效性，采用Standford 3d Scanning Repository[13]的Bunny、Dragon、Happy以及Armadillo模型進行配準效果測試.實驗在Matlab軟件2020a環境下運行于Intel(R) Core(TM) i5-8250U CPU，4G內存，Windows10的計算機上.實驗中的參數設置為：h=15，o1=5，o2=0.05，o3=0.02.

實驗采用旋轉誤差eR、平移誤差et以及配準所需時間T這3種常用指標作為評價標準.這3種評價指標分別從配準的有效性和配準的效率兩方面進行評價，并且都是數值越小所表示的性能越好.旋轉誤差eR和平移誤差et的計算公式為：

(11)

et=‖tm-tg‖2，

(12)

其中，Rg和tg分別代表配準所需的旋轉矩陣R和平移向量t的真值；Rm和tm則分別代表所求得的旋轉矩陣R和平移向量t.

2.2 特征保留權值的確定

采用Bunny和Dragon兩個模型進行實驗，確定δ的取值.通過選用不同的特征保留權值δ，經過篩選后的特征保留點和配準結果如圖4所示.

(a) Bunny保留點與配準結果

(b) Dragon保留點與配準結果圖4 不同權值下配準結果對比

從實驗結果可以看出，當特征保留權值δ分別取值1、0.99、0.98、0.97時，保留下來的特征點有較大差距，但是仍然有著較高的配準精度.δ取值越小保留下的特征點越少，減少數據量可以有效地縮短點云配準時間，提高配準的效率.為了更明顯地體現實驗結果，表1展示了不同權值下點云配準所需要的時間.

表1 不同權值下配準所需時間

從表1可以看出隨著特征保留權值的減少，配準的效率也隨之提高.Bunny模型配準時間從0.597降至0.350 s，Dragon模型配準時間從0.509降至0.297 s.所以配準效率隨之特征保留權值的減小而提高，但是考慮精度的要求，因此特征保留權值不可以設置過低，特征保留權值取0.97，這樣在保證了配準結果精度的同時，也提高了配準的效率.

2.3 配準實驗結果分析

為了驗證提出算法的有效性，采用Standford 3d Scanning Repository的Bunny、Dragon、Happy以及Armadillo模型進行配準效果測試，如圖5所示.圖5表明提出的算法可以有效地對這4個模型進行粗配準，并獲得最優的配準結果.為了更加直觀地表現該方法的有效性，實驗結果的具體數值如表2～4所示.

圖5 不同模型配準前后對比

表2 粗配準算法的eR對比

表3 粗配準算法的et對比

表4 配準所需時間T對比

從表2～4可看出，提出的算法配準精度高于其他算法，尤其是在Bunny、Dragon以及Happy這3個模型當中，提出算法的精度遠遠高于其他4種算法.在配準效率方面，由于加入了特征保留權值，減少了運算時間，所以配準所消耗的時間均低于其他4種算法.在Armadillo模型當中，雖然旋轉矩陣誤差eR表現不是很突出，但是平移矩陣誤差et和配準時間都大大低于其他算法.因此，提出算法可以有效地完成三維點云的粗配準任務，而且在保證配準精度的同時也提高了配準的效率.

3 結 論

針對無初值情況下點云粗配準精度和效率低的問題，提出一種基于特征匹配的三維點云粗配準算法.首先對帶配準的點云進行特征提取，然后根據特征信息建立特征直方圖，將剛性不變約束和RANSAC相結合得到匹配點對，最后進行剛性變換估計得到旋轉矩陣和平移向量.根據局部變化信息提取特征點，提出了一種新的特征直方圖建立方法，加入特征保留權值提高了算法的配準效率.通過多組的實驗數據表明，提出的方法可以很好地完成點云配準任務，并且具有較高的配準效率，可以為后續的精確配準工作提供良好的初值，但提出的粗配準算法存在魯棒性不高的情況，因此下一步的工作是在保證配準的有效性和效率的前提下，進一步提高算法的魯棒性.