基于特征點匹配的點云配準方法研究

歐 鑫, 高 飛, 崔 浩, 葉周潤, 湯 毅

(合肥工業大學 土木與水利工程學院,安徽 合肥 230009)

三維激光掃描技術是一種在不接觸被測物體的情況下就可以得到物體表面的三維坐標信息以及反射信息的技術,而獲得的數據統稱為點云數據。該技術被廣泛應用于機器人識別、自動導航、文物保護等領域[1]。

在點云數據的采集中,由于物體的大小以及表面問題,而不能一次性獲取被測物體的全部點云數據,需要進行多個測站數據的采集。為了得到完整的點云數據模型,必須對各測站點云進行拼接,即將不同坐標系下的點云數據通過旋轉平移到同一坐標系中。

最為經典的配準方法是迭代最近點(iterative closest point,ICP)算法[2],有不少學者對傳統ICP算法進行了改進[3],但該算法在沒有良好的初始位置時,容易陷入局部最優,因此現在的算法大多數先通過粗配準獲得良好的初始位置,再使用ICP算法進行精配準[4-5]。常用的粗配準算法一般為基于特征描述的配準算法。常見的特征描述算子有快速點特征直方圖(fast point feature histogram,FPFH)[6]、歸一化對齊特征(normal aligned rodial features,NARF)[7]、局部特征直方圖(local signature feature histagram,LSFH)[8]等。基于特征描述的配準算法不太適用于稠密的點云,這是由于計算每個點的特征描述會極大影響點云配準的效率[9]。本文進一步提出了特征點與特征描述相結合的特征匹配算法,只需計算特征點的特征描述,再對其進行點對配對,最后計算初始矩陣。

1 點云粗配準

為了給ICP算法求得一個良好的變換矩陣,本文使用了基于特征點配對的粗配準方法,具體流程如下:首先采用尺度不變特征變換(scale-invariant feature transform,SIFT)算法[10]以及3DHarris算法[11]對點云進行特征點提取,計算FPFH特征,再基于FPFH特征找尋點對關系,使用隨機采樣一致性(random sample consensus,RANSAC)算法進行錯誤點對的剔除,最后使用奇異值分解法(singular value decomposition,SVD)求得變換矩陣,完成粗配準。

1.1 3DSift算法原理

(1) 建立點云的尺度空間。在點云的三維空間中,通過體素網格的方式進行點云體素化,設置體素網格的大小,計算體素網格包含點云的重心,再用各個重心替代每個體素網格內所包括的點云,構成新點集,該步驟用公式表述為:

(1)

其中:Ii(x,y,z,θ)為第i個體素網格內包含點云的重心坐標;pq為第i個體素網格內包含點云中第q個點的三維坐標;n為第i個體素網格中點的數目。由Ii(x,y,z,θ)構成的點集則是在體素網格大小為?下進行降采樣后的原點云。

(2) 建立點云高斯差分金字塔[12]。設金字塔共有n組,每組有S層,則組內第s層的尺度為:

θs=θ02s/S,s∈{0,…,S+2}

(2)

其中:θ0為點云的基準尺度;θs為點云金字塔組內第s層的尺度。

通過計算相鄰尺度下采樣點的高斯響應值R,可以進一步計算其高斯差分值RDOG。對采樣點及距離采樣點3σ范圍內的點進行高斯曲率加權,高斯響應值R和高斯差分值RDOG的計算公式表示為:

(3)

(4)

RDOG=R-R1

(5)

其中:ρi為采樣點第i個近鄰點的曲率;ωi為加權數;μ為采樣點到相鄰點的間距;σ為采樣點所在尺度空間的大小;R1為上一尺度的高斯響應值。

(3) 檢測特征點。若該點在RDOG尺度空間本層內的RDOG值為最值,以及與相鄰上下2個尺度層內的RDOG對比仍是最值時,則認為該點為特征點。

1.2 3DHarris提取特征點

在三維點云空間中,選取點O作為中心,再以k為半徑來建立空間區域,將區域p內所有的點進行主成分分析(principal component analysis,PCA),根據最小二乘法原理生成一個二次曲面f(x,y),其展開式為:

(6)

計算f(x,y)的x和y的偏導,近似點云點強度I,進而解出矩陣M中各個元素的值如下:

(7)

(8)

(9)

fx(x,y)fy(x,y)dxdy

(10)

w(x,y)是5×5窗口權函數(根據實際設置),(8)～(10)式積分后可得A、B、C值,即

(11)

(12)

C=O4O5+2O1O2+2O2O3

(13)

最后再計算Harris響應值R:

R=detM-k(traceM)2

(14)

將計算的R與設定的檢測值Rq對比,當R>Rq時,則該點為特征點。

1.3 RANSAC算法

RANSAC算法常被用于提取正確匹配點對和剔除錯誤匹配點對,該算法具有良好的抗噪性[13]。利用對應關系估計對錯誤匹配的剔除進行預處理,RANSAC算法效率更高。具體流程如下。

首先使用合適的轉換模型使點對之間進行擬合。點對關系需要滿足:

(15)

其中:Ri{i=1,2,3…,9}為旋轉參數;X0、Y0、Z0為平移參數;(X2,Y2,Z2)為源點云;(X1,Y1,Z1)為目標點云。

迭代過程中,需要計算(15)式中的旋轉平移參數,為此需要選擇至少4組點對進行求解。為了有效選取點對,將對應關系估計用做點對篩選,從而提升RANSAC剔除點對的效率。記源點云P={p1,p2,…,pn}和目標點云Q={q1,q2,…,qm}的特征分別為{pf1,pf2,…,pfn}和{qf1,qf2,…,qfm}。對于源點云的任一特征pfi(i

(16)

則判定pi和qj是一對正確的點對(pi,qj)。其中,sn為特征維數,可取值為33或125,C為所設常數。獲得的點對可以用來估算轉換參數R和T。將剩余點對(pi,qj),計算其距離d=‖Rpi+T-qj‖,根據距離d與所設閾值的比對,判定該點對(pi,qj)是內點或者外點。每次迭代,統計使用該組參數獲得的內點數目n,直至達到所設迭代次數。當該組轉換參數所得內點數數目n最大時,則其為最優參數,所獲得的n對內點可以通過1.4節介紹的SVD算法計算旋轉平移矩陣完成粗配準。

1.4 SVD算法

SVD算法的基本思想是將一個復雜的矩陣可以拆分為幾個簡單矩陣來表示。正是基于這種思想算法具有良好的抗噪性和穩定性[14]。該思想用公式表示為:

U=XZYT

(17)

其中:U為M×N的矩陣;X為M×M的矩陣,稱X矩陣內的向量為左奇異向量,且向量相互正交;Z為M×N的矩陣,其構成為對角線上元素為奇異值,其余數值為0;YT為N×N的矩陣,稱矩陣YT內的向量為右奇異向量,其內部向量也相互正交。

假設2個點云分別為P={pi,i=1,2,3,…,np}和Q={qj,j=1,2,3,…,nq},其中np、nq分別代表2個點云的總點數。點pi和qj的關系可以表示為:

qj=Rpi+T

(18)

其中:R為旋轉矩陣;T為平移矩陣。相應的目標函數可表示為:

(19)

然后對R進行SVD分解可得:

R=XZYT

(20)

(20)式可以更有效率地求取旋轉矩陣,再通過(18)式求得平移矩陣。

2 點云精配準

粗配準后可以獲得一個初始矩陣,使得2個點云擬合到一個比較良好的位置,但一般還不完全重合,此時就需要對點云進行精配準。

ICP算法基本原理為分別在源點云P={pi,i=1,2,3,…,n}和目標點云Q={qi,i=1,2,3,…,n}中,對于任意點對(pi,qi),設誤差函數為:

(21)

其中,n為鄰近點個數。

通過迭代計算,直到θ小于設定的閾值min,也就是通過不斷求解2個點云間的變換關系,更新2個點云位置,直到收斂于設定閾值,即找出最優轉換矩陣R和T。具體步驟為:

(1) 在目標點云P中取點pi∈P;

(2) 源點云Q中取點qi∈Q,其兩點關系滿足‖qi-pi‖2=min;

(3) 使用該點計算相應的轉換矩陣R和T;

(6) 如果誤差函數θ小于所設閾值min或者迭代次數大于預設的迭代次數,那么終止運算,輸出最終矩陣,否則返回步驟(2),直到滿足給定條件為止。

這樣經過多次迭代,點云P就會越來越接近Q,最終實現重合,這是迭代最近點ICP算法的基本思想。

3 實例分析

實驗采用斯坦福大學提供Dragon以及Armadillo-scans點云數據進行仿真實驗。Dragon選取了dragonStandRight-0和dragonUpRight-0,點數目分別為41 841、42 641個;Armadillo-scans選取了ArmadilloSide-105和ArmadilloOnHeadMultiple-0,點數目分別為29 715、32 385個。

實驗在VS 2017、Win 10系統、內存16 GiB下進行。兩點云位置如圖1所示,圖1中:綠色為源點云;紅色為目標點云。實驗過程為通過粗配準獲得初始矩陣后,使用ICP算法不斷迭代計算變換矩陣,使得綠色點云向紅色點云逐漸靠近,最終實現重合。

圖1 點云初始位置

3.1 Armadillo點云配準結果

特征點匹配如圖2所示(連線為對應點對)。

圖2 Armadillo點云特征點點對匹配

經過粗配準以及精配準后所得配準結果如圖3所示。

圖3 Armadillo點云配準結果

3.2 Dragon點云配準結果

特征點匹配如圖4所示(連線為對應點對)。

圖4 Dragon點云特征點點對匹配

經過粗配準以及精配準后所得配準結果如圖5所示。

圖5 Dragon點云配準結果

3.3 FPFH與ICP結合算法配準結果

兩點云直接使用FPFH與ICP結合算法的配準結果如圖6所示。

圖6 FPFH與ICP結合算法配準結果

從圖6可以看出,2個模型中的2幅點云都不能很好地重合在一起,這是粗配準效果不好,所得初始矩陣并不能滿足ICP算法要求,從而導致ICP算法進行求解時陷入局部最優[15]。配準數據對比見表1所列。

表1 不同算法配準結果比較

從圖2～圖6以及表1可以看出,基于特征點提取的配準算法比只基于特征描述的配準算法效果要好,因此本文提出的算法具有一定的可靠性。

再對比本文中使用的2種特征點提取方法,在Armadillo點云模型中,基于SIFT算法在配準誤差以及配準時間上都優于基于Harris算法,圖3中配準效果也比較好;在Dragon點云模型中,兩者的配準誤差差距不大,圖5中兩者配準效果基本相同,但在時間效率上,仍是基于SIFT的算法比較好。

4 結 論

本文針對在點云配準中使用FPFH與ICP結合的算法達不到配準精度的問題,提出了一種基于特征點匹配的點云配準算法,使用SIFT和3DHarris算子提取特征點,特征點集根據FPFH特征描述進行點對匹配,再使用RANSAC算法進行錯誤點對去除,使用SVD算法對剩余點對進行解算,完成粗配準,得到初始矩陣,最后使用傳統ICP精配準,得到最終結果。實驗表明,該算法在配準效果上優于FPFH與ICP結合算法,在基于SIFT算法和基于Harris算法兩者的比較中,進一步得出使用SIFT算法進行特征點提取匹配,可以得到更好的初始矩陣,且在時間效率上要遠優于Harris的結論。在真實場景中,面臨數目更加龐大的點云,對算法效率的提升以及閾值的設置是今后研究的重要方向。