鄰域多維度特征點(diǎn)結(jié)合相關(guān)熵的點(diǎn)云配準(zhǔn)

黃淞宣,李新春,劉玉珍

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

1 引 言

點(diǎn)云配準(zhǔn)技術(shù)作為激光雷達(dá)掃描成像的關(guān)鍵技術(shù)之一,被廣泛用于三維重建、醫(yī)療成像、自動(dòng)駕駛、目標(biāo)識(shí)別與定位等領(lǐng)域[1]。點(diǎn)云配準(zhǔn)的目的是將不同視角下采集到的點(diǎn)云數(shù)據(jù)整合到同一坐標(biāo)系下,為后續(xù)工作打下基礎(chǔ)。

在點(diǎn)云配準(zhǔn)中經(jīng)典的迭代最近點(diǎn)(ICP)算法[2]對(duì)點(diǎn)云的初始位置和重疊率要求較高,且存在易受噪聲點(diǎn)和離群點(diǎn)影響、配準(zhǔn)耗時(shí)較長(zhǎng)的問題[3]。Segal等[4]提出一種GICP算法,將點(diǎn)到點(diǎn)的ICP算法和點(diǎn)到面的ICP算法結(jié)合到一個(gè)概率框架上,然后基于此框架進(jìn)行局部平面建模與配準(zhǔn),提高了抗噪性能,但配準(zhǔn)效率較低。Yang[5]等提出一個(gè)可以解耦尺度估計(jì)、旋轉(zhuǎn)和平移的算法框架,結(jié)合截?cái)嘧钚《朔ㄇ蠼庾顑?yōu)變換,提高了配準(zhǔn)精度。陸軍[6]等根據(jù)不同尺度空間的法向量投影值提取特征點(diǎn),用特征點(diǎn)估計(jì)初始位置再用ICP配準(zhǔn),提高了配準(zhǔn)精度。張彬[7]等對(duì)原始點(diǎn)云體素下采樣后,利用法向量夾角特性提取特征點(diǎn),對(duì)特征點(diǎn)特征匹配后用ICP精配準(zhǔn),提高了配準(zhǔn)的效率和精度。徐思雨[8]等設(shè)計(jì)一種加權(quán)的最小二乘目標(biāo)函數(shù),通過迭代最近點(diǎn)求解最佳參數(shù),提高了配準(zhǔn)精度。

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

2 基本原理

2.1 多維度特征點(diǎn)提取

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

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

圖1 不同區(qū)域點(diǎn)的投影

設(shè)鄰域半徑為r,建立點(diǎn)pi的加權(quán)協(xié)方差矩陣,其形式為:

(1)

(2)

求得式(1)矩陣的特征值為λi1≥λi2≥λi3,最小特征值λi3所對(duì)應(yīng)的特征向量即為點(diǎn)pi的法向量ni。用法向量?jī)?nèi)積來計(jì)算鄰域點(diǎn)在采樣點(diǎn)pi法向量上的投影距離值dij,為:

(3)

(4)

ωd=edij

(5)

采樣點(diǎn)與鄰域點(diǎn)的法向量夾角可以很好的表示該區(qū)域的起伏程度。如圖2所示,在平坦區(qū)域采樣點(diǎn)與領(lǐng)域點(diǎn)的法向量夾角接近于0°,在彎曲區(qū)域采樣點(diǎn)與鄰域點(diǎn)的法向量夾角較大。用鄰域法向量?jī)?nèi)積均值代替鄰域法向量夾角均值來計(jì)算,可以更簡(jiǎn)便的評(píng)判一點(diǎn)是否處于表面起伏較大的特征區(qū),其形式為:

圖2 不同區(qū)域的法向量

(6)

式中,nj為鄰域點(diǎn)pj的法向量。當(dāng)pi點(diǎn)位于表面彎曲度越大的位置時(shí),它與鄰域點(diǎn)的法向量夾角就越大,法向量?jī)?nèi)積就越小,X(pi)的值就越小。

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

(7)

當(dāng)點(diǎn)pi位于彎曲度較大的區(qū)域時(shí),σ(pi)的值就比較大。

由于法向量夾角與表面曲率都可以評(píng)估點(diǎn)鄰域的彎曲程度,本文提出一種彎曲度函數(shù)S,其形式為:

(8)

取彎曲度閾值為δ,當(dāng)S(pi)大于δ時(shí),則pi點(diǎn)處于彎曲度較大的區(qū)域,即認(rèn)為pi點(diǎn)為特征點(diǎn)。

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

2.2 粗配準(zhǔn)

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

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

(9)

式中,P0和Q0分別為源點(diǎn)云和目標(biāo)點(diǎn)云的特征點(diǎn)集;pi和qi為匹配點(diǎn)對(duì);N為匹配點(diǎn)對(duì)的個(gè)數(shù)。

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

(10)

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

遍歷點(diǎn)對(duì)集H,得到更為正確的匹配點(diǎn)對(duì)集H′,表示為:

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

(11)

式中,pk和qk為匹配點(diǎn)對(duì);M為匹配點(diǎn)對(duì)的個(gè)數(shù)。

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

2.3 精配準(zhǔn)

2.3.1 相關(guān)熵模型的目標(biāo)函數(shù)

相關(guān)熵是利用非線性的方法度量?jī)蓚€(gè)變量之間的相似性,通過核函數(shù)對(duì)殘差進(jìn)行約束,可以有效的抵抗粗差的干擾,對(duì)于點(diǎn)云類非高斯分布數(shù)據(jù)的處理,相關(guān)熵比均方誤差函數(shù)更加準(zhǔn)確[16]。

(12)

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

圖3 均方誤差函數(shù)與相關(guān)熵

點(diǎn)到面的距離比點(diǎn)到點(diǎn)的距離更能體現(xiàn)點(diǎn)云的空間結(jié)構(gòu),具有一定的抗噪性。點(diǎn)到對(duì)應(yīng)點(diǎn)曲面的距離越小,相關(guān)熵的值就越大,因此目標(biāo)函數(shù)是最大化點(diǎn)到面的相關(guān)熵模型,其形式為:

(13)

2.3.2 MFP特征點(diǎn)結(jié)合相關(guān)熵的精配準(zhǔn)流程

設(shè)點(diǎn)到對(duì)應(yīng)點(diǎn)曲面的距離閾值為dm,法向量夾角閾值為θm。為了提高精配準(zhǔn)效率,本文算法采用MFP特征點(diǎn)代替含大量冗余點(diǎn)的源點(diǎn)云進(jìn)行精配準(zhǔn),具體流程為:

1)對(duì)源點(diǎn)云P的特征點(diǎn)集P′和目標(biāo)點(diǎn)云Q構(gòu)建k維樹;

2)對(duì)P′中一點(diǎn)pi,在目標(biāo)點(diǎn)云Q中用KD-tree搜索pi的最近點(diǎn)qi;在P′中用KD-tree搜索點(diǎn)qi的最近點(diǎn)為pi′;

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

4)計(jì)算對(duì)應(yīng)點(diǎn)對(duì)的旋轉(zhuǎn)矩陣R和平移向量T,使相關(guān)熵模型的目標(biāo)函數(shù)Ec(R,T)最大,將點(diǎn)集P′通過R和T變換;

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

3 實(shí)驗(yàn)與分析

本文的實(shí)驗(yàn)平臺(tái)是Intel Core i5-8300H CPU @ 2.30GHz處理器、四核八線程、8G內(nèi)存的PC機(jī)。本文實(shí)驗(yàn)是在Windows10 64 位操作系統(tǒng)下,基于PCL1.8.1庫和Visual Studio2017編譯環(huán)境,用C++語言實(shí)現(xiàn)。用均方誤差評(píng)價(jià)配準(zhǔn)精度和用時(shí)間評(píng)價(jià)配準(zhǔn)效率,均方誤差表達(dá)式為:

(14)

式中,pi和qi為源點(diǎn)云變換后與目標(biāo)點(diǎn)云重疊部分間的點(diǎn)對(duì);N為點(diǎn)對(duì)的個(gè)數(shù)。均方誤差EMS的值越小,代表配準(zhǔn)精度越高。

3.1 閾值選取實(shí)驗(yàn)

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

圖4 閾值對(duì)配準(zhǔn)的影響

3.2 低重疊率點(diǎn)云的配準(zhǔn)實(shí)驗(yàn)

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

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

表1 點(diǎn)云模型配準(zhǔn)結(jié)果對(duì)比

圖5 點(diǎn)云模型配準(zhǔn)結(jié)果

3.3 加噪點(diǎn)云模型的配準(zhǔn)實(shí)驗(yàn)

為驗(yàn)證本文算法抗噪性能的優(yōu)越性,本試驗(yàn)選取斯坦福Bunny(35947)模型,并對(duì)目標(biāo)點(diǎn)云添加標(biāo)準(zhǔn)差σ分別為1.5 mm、2.0 mm,2.5 mm、3.0 mm的高斯噪聲。

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

表2 加噪模型配準(zhǔn)結(jié)果對(duì)比

圖6 加噪模型配準(zhǔn)結(jié)果

3.4 實(shí)際物體的配準(zhǔn)實(shí)驗(yàn)

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

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

表3 實(shí)際物體的點(diǎn)云配準(zhǔn)對(duì)比

圖7 實(shí)際物體的點(diǎn)云配準(zhǔn)

4 結(jié) 論

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