鄰域多維度特征點結合相關熵的點云配準

黃淞宣,李新春,劉玉珍

(1.遼寧工程技術大學研究生院,遼寧 葫蘆島 125105; 2.遼寧工程技術大學電子與信息工程學院,遼寧 葫蘆島 125105)

1 引 言

點云配準技術作為激光雷達掃描成像的關鍵技術之一,被廣泛用于三維重建、醫療成像、自動駕駛、目標識別與定位等領域[1]。點云配準的目的是將不同視角下采集到的點云數據整合到同一坐標系下,為后續工作打下基礎。

在點云配準中經典的迭代最近點(ICP)算法[2]對點云的初始位置和重疊率要求較高,且存在易受噪聲點和離群點影響、配準耗時較長的問題[3]。Segal等[4]提出一種GICP算法,將點到點的ICP算法和點到面的ICP算法結合到一個概率框架上,然后基于此框架進行局部平面建模與配準,提高了抗噪性能,但配準效率較低。Yang[5]等提出一個可以解耦尺度估計、旋轉和平移的算法框架,結合截斷最小二乘法求解最優變換,提高了配準精度。陸軍[6]等根據不同尺度空間的法向量投影值提取特征點,用特征點估計初始位置再用ICP配準,提高了配準精度。張彬[7]等對原始點云體素下采樣后,利用法向量夾角特性提取特征點,對特征點特征匹配后用ICP精配準,提高了配準的效率和精度。徐思雨[8]等設計一種加權的最小二乘目標函數,通過迭代最近點求解最佳參數,提高了配準精度。

但上述的ICP改進算法采用單一特征提取特征點,會因特征信息不夠完整而出現誤匹配;采用最小二乘形式的目標誤差函數,易受噪聲點、離群點等誤匹配的干擾,會降低配準精度,而相關熵形式的誤差函數可以更好的處理非高斯分布數據,能夠提高配準的精度和魯棒性[9]。為此,本文提出一種多維度特征點結合最大相關熵模型的點云配準方法。所提取的多維度特征點含有加權投影信息、表面曲率、法向量夾角三種特征信息,在特征匹配時能夠減少誤匹配。在精配準階段采用特征點代替源點云以提高配準效率,用法向量夾角與剛性距離約束剔除誤匹配點對,并結合相關熵模型的目標函數雙向配準,進一步減小了誤匹配的影響,提高了配準的精度。

2 基本原理

2.1 多維度特征點提取

特征點作為粗配準的輸入點集,用于快速估計兩個點云間的初始位姿。特征點提取的效果及數量很大程度上影響著粗配準的精度和效率,用單一特征提取的特征點存在特征信息不夠完整的問題,容易在特征匹配時出現誤匹配,導致配準效果不佳[10]。因此,本文結合鄰域點的投影信息、表面曲率和法向量夾角三個維度的特征,提出一種多維度特征點(MFP)。

鄰域點在采樣點法向量上的投影可以反映表面的彎曲程度,如圖1所示,在半徑為r的鄰域內,若采樣點pi位于表面彎曲度較大的區域,則鄰域點pj在采樣點pi法向量上的投影距離dij較大。當采樣點位于表面彎曲度較小的區域,則該投影距離較小。

圖1 不同區域點的投影

設鄰域半徑為r,建立點pi的加權協方差矩陣,其形式為:

(1)

(2)

求得式(1)矩陣的特征值為λi1≥λi2≥λi3,最小特征值λi3所對應的特征向量即為點pi的法向量ni。用法向量內積來計算鄰域點在采樣點pi法向量上的投影距離值dij,為:

(3)

(4)

ωd=edij

(5)

采樣點與鄰域點的法向量夾角可以很好的表示該區域的起伏程度。如圖2所示,在平坦區域采樣點與領域點的法向量夾角接近于0°,在彎曲區域采樣點與鄰域點的法向量夾角較大。用鄰域法向量內積均值代替鄰域法向量夾角均值來計算,可以更簡便的評判一點是否處于表面起伏較大的特征區,其形式為:

圖2 不同區域的法向量

(6)

式中,nj為鄰域點pj的法向量。當pi點位于表面彎曲度越大的位置時,它與鄰域點的法向量夾角就越大,法向量內積就越小,X(pi)的值就越小。

表面曲率可以評估一點鄰域的表面彎曲程度[12]。根據式(1)求得的特征值為λi1≥λi2≥λi3,則點pi的表面曲率σ(pi)為:

(7)

當點pi位于彎曲度較大的區域時,σ(pi)的值就比較大。

由于法向量夾角與表面曲率都可以評估點鄰域的彎曲程度,本文提出一種彎曲度函數S,其形式為:

(8)

取彎曲度閾值為δ,當S(pi)大于δ時,則pi點處于彎曲度較大的區域,即認為pi點為特征點。

用彎曲度函數對初始特征點進行篩選,若初始特征點滿足S(pi)>δ,則該點為本文的MFP特征點。最終提取的MFP特征點含有豐富的特征信息,包含了鄰域點的投影、表面曲率與法向量夾角特征。

2.2 粗配準

通常維度越高的特征描述子具有更好的特征描述能力,但是由于特征描述子向量是浮點數形式,在計算歐氏距離進行特征匹配時會產生巨大的計算開銷,導致效率低下,而二值化的特征描述子可以很好的解決這個問題[13]。為了提高粗配準的效率及精度,本文采用352維度的二進制描述子B-SHOT[14],分別對源點云和目標點云的特征點進行特征描述,再用漢明距離代替歐式距離進行特征匹配以提高計算效率,由此得到初始匹配點對集記為:

H={(pi,qi)|pi∈P0,qi∈Q0,i=1,2,3,…,N}

(9)

式中,P0和Q0分別為源點云和目標點云的特征點集;pi和qi為匹配點對;N為匹配點對的個數。

由于存在特征相似的情況,初始匹配點對集中存在大量誤匹配點對。對點對集H中的任意兩組對應點對(pi,qi)和(pj,qj)進行歐式距離約束,若不滿足式(10),則視為誤匹配點對并剔除。

(10)

式中,ε為閾值,取ε為0.02[15]。

遍歷點對集H,得到更為正確的匹配點對集H′,表示為:

H′={(pk,qk)|pk∈P0,qk∈Q0,k=1,2,3,…,M}

(11)

式中,pk和qk為匹配點對;M為匹配點對的個數。

最后,用隨機采樣一致性算法(RANSAC)算法對匹配點對集H′進行處理[6],得到點云的初始變換矩陣R0和T0。

2.3 精配準

2.3.1 相關熵模型的目標函數

相關熵是利用非線性的方法度量兩個變量之間的相似性,通過核函數對殘差進行約束,可以有效的抵抗粗差的干擾,對于點云類非高斯分布數據的處理,相關熵比均方誤差函數更加準確[16]。

(12)

如圖3(a)所示,均方誤差函數在x=y的谷底取得最小值,但隨著x和y差值的增大,均方誤差函數對殘差呈二次放大作用。離群點或噪聲點容易產生誤匹配,且點對間的距離差值一般較大,而均方誤差函數對該差值具有放大作用,因此離群點或噪聲點對均方誤差函數具有較大的干擾。由圖3(b)可知,相關熵沿x=y線時取得最大,隨著x和y差值的增大,相關熵的值迅速減小到接近于0,這說明相關熵能很好的抵抗粗差的干擾,能有效的降低噪聲點或離群點誤匹配的影響。

圖3 均方誤差函數與相關熵

點到面的距離比點到點的距離更能體現點云的空間結構,具有一定的抗噪性。點到對應點曲面的距離越小,相關熵的值就越大,因此目標函數是最大化點到面的相關熵模型,其形式為:

(13)

2.3.2 MFP特征點結合相關熵的精配準流程

設點到對應點曲面的距離閾值為dm,法向量夾角閾值為θm。為了提高精配準效率,本文算法采用MFP特征點代替含大量冗余點的源點云進行精配準,具體流程為:

1)對源點云P的特征點集P′和目標點云Q構建k維樹;

2)對P′中一點pi,在目標點云Q中用KD-tree搜索pi的最近點qi;在P′中用KD-tree搜索點qi的最近點為pi′;

3)若pi與pi′不為同一點,則返回2)重新選擇下一個點pi+1;若pi與pi′是同一個點,則計算點pi到點qi所在曲面的距離di和兩點間的法向量夾角θi;如果di

4)計算對應點對的旋轉矩陣R和平移向量T,使相關熵模型的目標函數Ec(R,T)最大,將點集P′通過R和T變換;

5)重復步驟2)到4),若滿足相鄰兩次迭代誤差的差值小于閾值或迭代次數達到設定值,則停止迭代,將P用最終的R和T變換變即完成了精配準;若不滿足,則繼續迭代。

3 實驗與分析

本文的實驗平臺是Intel Core i5-8300H CPU @ 2.30GHz處理器、四核八線程、8G內存的PC機。本文實驗是在Windows10 64 位操作系統下,基于PCL1.8.1庫和Visual Studio2017編譯環境,用C++語言實現。用均方誤差評價配準精度和用時間評價配準效率,均方誤差表達式為:

(14)

式中,pi和qi為源點云變換后與目標點云重疊部分間的點對;N為點對的個數。均方誤差EMS的值越小,代表配準精度越高。

3.1 閾值選取實驗

彎曲度閾值的選取對配準的精度和效率有著重要的影響,該實驗采用斯坦福數據庫下的Bunny模型和Dragon模型。如圖4(a)所示,當彎曲度閾值δ為0.03時,配準誤差最小。如圖4(b)所示,隨著彎曲度閾值δ的增大,配準時間逐漸減小。彎曲度閾值δ越小,特征相似的點較多,會產生較多的誤匹配與較大的時間消耗。彎曲度閾值δ越大,提取的特征點越少,配準耗時越少,但較少的特征點不能產生足夠的匹配點對,會導致配準誤差增大。因此在兼顧配準精度和效率的前提下,Bunny和Dragon模型選取的彎曲度閾值δ為0.03。

圖4 閾值對配準的影響

3.2 低重疊率點云的配準實驗

為了驗證本文配準算法在低重疊率點云下配準的有效性,本實驗采用斯坦福大學數據庫的Armadillo模型、Dragon模型和Bunny模型。將本文的MFP征點結合相關熵模型的算法(MFP-CICP)與經典ICP算法、GICP[5]算法、內部形變描述子特征點(ISS)結合k維樹ICP的算法(ISS-KICP)[17]、鄰域特征點結合k維樹ICP的算法(NFP-KICP)[18]進行比較。

從圖5中可以看出,在三個模型下,本文算法與NFP-KICP均能完成配準,ICP算法、GICP算法與ISS-KICP算法在重疊度更低的Bunny模型下不能有效地完成配準。根據表1定量分析,本文算法的配準精度較ICP算法、GICP算法、ISS-KICP算法、NFP-KICP算法分別平均提高了約50.7 %、44.8 %、28.1 %、21.4 %。本文算法的配準效率比GICP算法平均提高了一個量級,與ICP算法、ISS-KICP算法、NFP-KICP算法相比平均提高了約86.7 %、19.1 %、33.6 %。本文算法所提取的多維度特征點含有多種特征信息,特征匹配時誤匹配點對較少,且相關熵模型的目標函數在迭代時能有效的限制非常重疊區域誤匹配點對的影響,進一步提高了配準精度。而ISS-KICP、NFP-KICP算法所提特征點的特征信息單一,容易產生誤匹配,在重疊度更低的Bunny模型下配準誤差較大。

表1 點云模型配準結果對比

圖5 點云模型配準結果

3.3 加噪點云模型的配準實驗

為驗證本文算法抗噪性能的優越性,本試驗選取斯坦福Bunny(35947)模型,并對目標點云添加標準差σ分別為1.5 mm、2.0 mm,2.5 mm、3.0 mm的高斯噪聲。

從圖6中可以看出,只有ICP算法在σ為3.0 mm時陷入局部最優,配準失敗,而其他算法都能有效的完成配準。根據表2定量分析,本文算法的配準精度較ICP算法、GICP算法分別提高了25.1 %～97.3 %、19.5 %～58.3 %。在σ為3.0 mm時,本文算法的配準精度較ISS-KICP算法、NFP-KICP算法分別提高了約25.4 %和20.0 %。本文算法的配準效率比ICP算法和GICP算法提高了1個量級,比ISS-KICP算法、NFP-KICP算法平均提高了約19.7 %、18.6 %。在迭代最近點時,本文算法通過雙向搜索、歐式距離約束和法向量夾角特征約束剔除了大量誤匹配點對,且相關熵模型的目標函數進一步降低了誤匹配點對的影響,提高了在噪聲環境下的配準精度。而其他算法采用均方誤差形式的目標函數,受噪聲影響較大,因此配準誤差較大。

表2 加噪模型配準結果對比

圖6 加噪模型配準結果

3.4 實際物體的配準實驗

為驗證本文算法在實際物體的點云配準中也具有較高的配準精度和配準效率,本實驗采用Creaform Handy SCAN 700激光掃描儀獲取的瓶子點云數據以及RIEGL VZ-400掃描儀獲取的石獅子雕像點云數據。

從圖7中可以看出,本文算法和ISS-KICP算法、NFP-KICP算法都能有效的完成配準,在石獅子的點云數據下,ICP算法和GICP算法配準效果不佳。從表3中定量分析可知,在瓶子的點云配準中,五種算法的配準精度相差不大。在石獅子的點云配準中,本文算法的配準精度比ICP算法、GICP算法、ISS-KICP算法、NFP-KICP算法分別提高了約67.4 %、63.1 %、48.1 %、24.5 %。本文算法的配準效率比ISS-KICP算法、NFP-KICP算法平均提高了約24.3 %、48.1 %。瓶子實物的點云數據量較小,且重疊度大,因此五種算法的配準效果相差不大。而石獅子的點云數據量大,重疊度低,非重疊區域的點會產生大量誤匹配,ICP算法和GICP算法配準效果較差;ISS-KICP算法、NFP-KICP算法在精配準階段沒有降低大量誤匹配點對的影響,因此配準誤差較大。本文算法通過多種約束剔除了大量誤匹配點對,并且相關熵模型的目標函數可進一步減少誤匹配的影響,提高了配準精度。

表3 實際物體的點云配準對比

圖7 實際物體的點云配準

4 結 論

為了提高點云配準的效率和精度,本文提出一種鄰域多維度特征點結合最大相關熵模型的點云配準方法。所提取的多維度特征點具有多種特征信息,不易產生誤匹配,將特征點代替含大量冗余點的源點云進行迭代提高了配準效率。通過多種約束與構建高斯核函數形式的相關熵模型,有效的限制了噪聲、離群點等誤匹配的干擾。實驗結果表明,在重疊度較低、噪聲干擾較大的點云配準中,相比于ICP算法、GICP算法、單一特征結合均方誤差目標函數的ISS-KICP算法和NFP-KICP算法,本文算法具有更高的配準精度和配準效率。