王正家,蘇超全,聶 磊

(1.湖北工業(yè)大學(xué)機(jī)械工程學(xué)院,湖北 武漢 430068;2.湖北工業(yè)大學(xué)現(xiàn)代制造質(zhì)量工程湖北省重點(diǎn)實(shí)驗(yàn)室,湖北 武漢 430068)

1 引 言

隨著3D成像技術(shù)的興起,激光掃描儀在機(jī)器人、智能制造、文物保護(hù)等領(lǐng)域得到了廣泛的應(yīng)用[1]。然而,在實(shí)際掃描過程中,由于測量環(huán)境和儀器設(shè)備等因素的影響,通常需要對物體多視角掃描,并通過配準(zhǔn)把不同視角的點(diǎn)云變換到同一坐標(biāo)系下[2]。點(diǎn)云配準(zhǔn)通常分為粗配準(zhǔn)和精細(xì)配準(zhǔn)[3]。粗配準(zhǔn)算法主要有人工設(shè)計(jì)的特征配準(zhǔn)、基于學(xué)習(xí)的特征配準(zhǔn)[4]、隨機(jī)樣本一致性(Random Sample Consensus,RANSAC)、概率分布配準(zhǔn)和基于投影的配準(zhǔn)[5]。精確配準(zhǔn)主要包括Besl[6]等提出的迭代最近點(diǎn)(iterative closest point,ICP)算法,ICP算法時(shí)間復(fù)雜度高,需要良好的初始位姿,不然容易陷入局部最優(yōu)。Chetverikov、Dong等人對ICP的改進(jìn)提高了算法的效率和準(zhǔn)確性[7-8],對于數(shù)據(jù)量大的情況下迭代耗時(shí)。Biber[9]提出了基于概率密度分布的NDT算法,算法精度高、計(jì)算速度快但對初始位姿有一定的要求。Rusu[10-11]提出了持久特征直方圖配準(zhǔn)(Persistent Feature Histograms)算法,計(jì)算復(fù)雜度高,速度慢,接著提出優(yōu)化后的快速點(diǎn)特征直方圖(Fast Point Feature Histograms,FPFH)描述符,基于樣本共識的方法(Sample Consensus Initial Align,SAC-IA)進(jìn)行特征配準(zhǔn),提高了配準(zhǔn)速度,克服了點(diǎn)云位置的局限性,配準(zhǔn)精度不高?？紤]到粗配準(zhǔn)和精確配準(zhǔn)優(yōu)缺點(diǎn),兩步配準(zhǔn)算法成為了主流。荊路等人[12]提出一種基于FPFH的SAC-IA和NDT(Normal Distributions Transform)融合的點(diǎn)云配準(zhǔn)方法,點(diǎn)云采樣的大小對配準(zhǔn)速度有很大的影響以及NDT的配準(zhǔn)精度相比ICP稍微降低。趙明富、宋濤等人[13]提出了基于FPFH融合采樣一致性和迭代最近點(diǎn)算法的點(diǎn)云配準(zhǔn)方法,解決了ICP算法陷入局部最優(yōu)的問題,在計(jì)算FPFH特征時(shí)耗時(shí)有待于進(jìn)一步改進(jìn)。劉今越等人[14]提出一種基于曲率精簡點(diǎn)云,融合NDT與ICP的點(diǎn)云配準(zhǔn)算法提高了點(diǎn)云配準(zhǔn)的速度,模型數(shù)據(jù)不具普適性。Sun T等人[15]提出結(jié)構(gòu)緊湊的加權(quán)高度圖像描述符(Weighted Height Image,WHI),并用于點(diǎn)云粗配準(zhǔn),配準(zhǔn)精度、效率高。

針對點(diǎn)云兩步配準(zhǔn)效率低、配準(zhǔn)精度差的問題,提出ISS算法(Intrinsic Shape Signatures,ISS)精簡點(diǎn)云,通過WHI描述符完成粗配準(zhǔn),利用安德森算法改進(jìn)ICP完成點(diǎn)云的精確配準(zhǔn)。實(shí)驗(yàn)表明所提算法的速度、精度都有一定程度的提高,在噪聲環(huán)境下配準(zhǔn)效果良好。

2 加權(quán)高度圖像描述符

加權(quán)高度圖像描述符(Weighted Height Image,WHI)是一種三維信息二維離散化的表達(dá),主要包括簡化LRF(local coordinate reference system,LRF)和基于良態(tài)空間優(yōu)化的加權(quán)編碼兩個(gè)部分。

2.1 局部坐標(biāo)參考系

一個(gè)獨(dú)特的、可重復(fù)的、魯棒的局部坐標(biāo)參考系對于特征描述是非常重要的[16]。LRF估計(jì)一般通過局部點(diǎn)云的協(xié)方差矩陣特征值分解得到:

(1)

式中,pf為特征點(diǎn);r是搜索半徑;pi為支持域內(nèi)的點(diǎn);μ鄰域控制因子,di=‖pi-pf‖2。

協(xié)方差矩陣中,對離特征點(diǎn)較遠(yuǎn)的鄰域點(diǎn)進(jìn)行了較小權(quán)值的加權(quán),這可以在遮擋存在的情況下增加LRF的可再現(xiàn)性。由于協(xié)方差矩陣C(pf)是實(shí)對稱矩陣,對其進(jìn)行特征值分解可以得到:

C(pf)=QΛQT

(2)

(3)

(4)

(5)

然后根據(jù)坐標(biāo)分量和定義坐標(biāo)軸的方向,如下:

(6)

(7)

signy=signx×signz

(8)

定義一個(gè)符號向量S=[signxsignysignz]T,則支撐區(qū)域內(nèi)各點(diǎn)的最終坐標(biāo)可表示為:

(9)

其中,RLRF=SRam,是符號重定向后的局部坐標(biāo)系。

2.2 WHI特征描述符生成

(10)

提出一種權(quán)函數(shù)對編碼函數(shù)進(jìn)行加權(quán),以使得特征空間更加逼近于良態(tài)空間,權(quán)函數(shù)定義為:

0<η≤1

(11)

其中,r是搜索半徑,di(x,y,z)是點(diǎn)pf與點(diǎn)pi的距離,η是權(quán)函數(shù)值域范圍的控制因子,它使得W(x,y,z)的值域?yàn)閇η,1]。則優(yōu)化后的編碼函數(shù)見下式:

F(x,y,z)=W(x,y,z)Fz(x,y)=

(12)

Fz(x,y)=z,為了生成描述符,編碼函數(shù)應(yīng)該重新編碼或直接離散成描述符。在pf建立LRF,點(diǎn)pf的切平面是由基點(diǎn)pf和它的法向量n唯一決定的。另外兩個(gè)正交分量nz,ny位于平面內(nèi)。落入支持區(qū)域的點(diǎn)沿法向量投影到平面上。圖像的像素值由所有加權(quán)高度的平均值決定,而不是由最小距離決定。WHI計(jì)算公式見下式:

(13)

(14)

其中,D是局部高度圖像對應(yīng)的正方形區(qū)域(D:-R≤x≤R,-R≤y≤R)。則x方向(用隨機(jī)變量X表示)對應(yīng)的邊緣概率密度函數(shù)為下式:

(15)

同理:

(16)

(17)

采用的卷積核尺寸為5×5。利用該濾波器對局部高度圖像進(jìn)行濾波并保持分辨率不變,最后將濾波后m×m的局部高度圖像按照一定順序展開成一維向量,即可得到該特征點(diǎn)的WHI描述子。

3 特征點(diǎn)提取及點(diǎn)云配準(zhǔn)

3.1 ISS算法

由于點(diǎn)云數(shù)量較大,一般提取點(diǎn)云中幾何特征明顯的點(diǎn)來代表整體點(diǎn)云。ISS算法具有豐富的幾何信息,可以完成高質(zhì)量的點(diǎn)云配準(zhǔn)。ISS特征點(diǎn)算法檢測原理如下:

Step1:利用kd_tree構(gòu)建三維點(diǎn)云k鄰域內(nèi)的拓?fù)浣Y(jié)構(gòu),從而利于三維點(diǎn)云的搜索;

Step2:假設(shè)三維點(diǎn)云中的查詢點(diǎn)為Pi,鄰域的點(diǎn)集N(pi)={pij,j∈{1,2,…,k}}pij表示鄰域內(nèi)的點(diǎn),對于鄰域內(nèi)的中心點(diǎn):

(18)

Step3:依據(jù)歐式距離計(jì)算點(diǎn)pij的權(quán)值,見下式:

(19)

Step4:構(gòu)建協(xié)方差矩陣:

(20)

Step5:求協(xié)方差矩陣從大到小排列的特征值λi1λi2λi3,以及對應(yīng)的特征向量ei1ei2ei3。

Step6:設(shè)置篩選特征點(diǎn)的閾值ε1和ε2,滿足以下條件的點(diǎn)設(shè)置為關(guān)鍵點(diǎn):

(21)

(22)

通過對三維點(diǎn)云的ISS特征點(diǎn)作為采樣點(diǎn)進(jìn)行點(diǎn)云的配準(zhǔn),精簡點(diǎn)云數(shù)量,降低點(diǎn)云特征描述的復(fù)雜度,有利于提高點(diǎn)云配準(zhǔn)的速度。

3.2 基于WHI的粗配準(zhǔn)

(1)對源點(diǎn)云、目標(biāo)點(diǎn)云提取ISS特征點(diǎn)計(jì)算點(diǎn)對的WHI特征;

(2)利用kdtree算法搜索相近特征的對應(yīng)點(diǎn)對,作為對應(yīng)點(diǎn)對;

(3)從對應(yīng)的點(diǎn)集中隨機(jī)選取四個(gè)對應(yīng)點(diǎn)對,采用SVD算法計(jì)算源點(diǎn)云與目標(biāo)點(diǎn)云之間的變換矩陣;

(4)對應(yīng)點(diǎn)對的源點(diǎn)云進(jìn)行變換,計(jì)算變換后的點(diǎn)云與原對應(yīng)點(diǎn)對的目標(biāo)點(diǎn)云的歐式距離,如果小于一定閾值作為內(nèi)點(diǎn)記錄,否則記為外點(diǎn);

(5)重復(fù)(2)～(4)步直到迭代次數(shù)達(dá)到設(shè)定閾值,選擇最多一個(gè)內(nèi)點(diǎn)的記錄,利用迭代矩陣對源點(diǎn)云進(jìn)行變換。

3.3 基于ICP改進(jìn)的精配準(zhǔn)

3.3.1 安德森加速算法

(23)

(24)

研究表明,Anderson加速法是求殘差函數(shù)的根的一種擬牛頓方法,對于線性收斂的不動點(diǎn)迭代,Anderson加速法可以提高收斂速度[18]。

3.3.2 安德森加速的ICP點(diǎn)云配準(zhǔn)算法

傳統(tǒng)ICP配準(zhǔn)算法寫成關(guān)于需要求解的關(guān)于R,t固定點(diǎn)迭代的形式:

(25)

(26)

ΠQ(·)表示在投影在點(diǎn)集Q的最近點(diǎn)。然而,我們不能直接將Anderson加速度應(yīng)用于映射GICP。這是因?yàn)榘驳律铀俣葘⒂?jì)算R的新值作為旋轉(zhuǎn)矩陣的仿射組合,這通常不是一個(gè)旋轉(zhuǎn)矩陣本身。為了解決這個(gè)問題,使用另一組變量X來參數(shù)化一個(gè)剛性變換,這樣X的任何值都對應(yīng)一個(gè)有效的剛性變換,并且ICP迭代可以重寫為式(27)的形式[19]:

(27)

然后我們可以通過在每次迭代中執(zhí)行以下步驟對變量X應(yīng)用安德森加速度:

(1)從x(k)計(jì)算旋轉(zhuǎn)矩陣R(k)和平移向量t(k);

(2)ICP迭代更新:

(4)計(jì)算加速值XAA。

Rd中的所有剛性變換都形成了特殊的歐幾里得群SE(d),這是一個(gè)李群,并產(chǎn)生了一個(gè)李代數(shù)SE(d),它是一個(gè)向量空間?？梢允褂胹e(d)中對應(yīng)的元素將剛性變換參數(shù)化。每個(gè)點(diǎn)的齊次坐標(biāo)p=[pT,1]T,剛性變換T通過旋轉(zhuǎn)矩陣平移向量表示:

(28)

對于齊次坐標(biāo),所有這些矩陣形成特殊的歐幾里得群SE(d)。它的李代數(shù)se(d)包含如下形式的矩陣:

(29)

(30)

4 實(shí)驗(yàn)和分析

實(shí)驗(yàn)選取不同的點(diǎn)云模型進(jìn)行研究,通過點(diǎn)云配準(zhǔn)的精度、時(shí)間作為配準(zhǔn)指標(biāo),所提算法和幾種先進(jìn)的算法進(jìn)行比較證實(shí)所提算法的先進(jìn)性。

4.1 實(shí)驗(yàn)數(shù)據(jù)和實(shí)驗(yàn)條件

為了驗(yàn)證本文算法的有效性,通過兩組不同數(shù)據(jù)對文獻(xiàn)[12]算法,文獻(xiàn)[13]算法、文獻(xiàn)[15]算法及所提的算法進(jìn)行比較。實(shí)驗(yàn)數(shù)據(jù)選用斯坦福3D掃描庫(http://graphics.stanford.edu)下載的Bunny模型和Dragon模型,Bunny模型選用bun000和bun045數(shù)據(jù),Dragon模型選用dragonStsndRight_0和dragonStsndRight_24點(diǎn)云數(shù)據(jù)。實(shí)驗(yàn)電腦配置為Intel(R)Core(TM)i5-6200的CPU,內(nèi)存12 GB,使用VS 2019配置PCL1.12.0點(diǎn)云庫展開實(shí)驗(yàn)。

實(shí)驗(yàn)中待配準(zhǔn)點(diǎn)云模型的初始位置如圖1,灰色為待配準(zhǔn)點(diǎn)云,黑色為目標(biāo)點(diǎn)云。

圖1 點(diǎn)云配準(zhǔn)前的Bunny、Dragon模型

4.2 評價(jià)指標(biāo)

(1)精確度指標(biāo)

(31)

表1 原始點(diǎn)云的維度

表1中/的左右數(shù)值分別表示待配準(zhǔn)點(diǎn)云、目標(biāo)點(diǎn)云屬性的具體值。X、Y、Z維度表示邊界框的三個(gè)維度,邊界框是包裹點(diǎn)云的體積最小的長方體。

(2)速率指標(biāo)

點(diǎn)云配準(zhǔn)的效率可以通過運(yùn)行的時(shí)間進(jìn)行評估,由于實(shí)驗(yàn)環(huán)境,算法原理不同,通過多次實(shí)驗(yàn)求取平均值作為點(diǎn)云配準(zhǔn)算法的最終時(shí)間。

4.3 點(diǎn)云配準(zhǔn)時(shí)間和精度

從配準(zhǔn)時(shí)間與精度方面,將所提算法與幾種常見的配準(zhǔn)算法進(jìn)行了對比,結(jié)果如表2所示。SAC-IA+NDT[12]首先計(jì)算FPFH特征,然后利用SAC-IA方法作為粗配準(zhǔn),NDT算法做為精配準(zhǔn)。SAC-IA+ICP[13]以DNT方法進(jìn)行粗配準(zhǔn),ICP方法進(jìn)行精配準(zhǔn)。WHI+ICP[15]通過體素下采樣,通過點(diǎn)云的WHI特征構(gòu)建對應(yīng)點(diǎn)對進(jìn)行粗配準(zhǔn),ICP算法完成精配準(zhǔn)。

所提方法利用ISS算法提取特征點(diǎn)完成點(diǎn)云精簡,然后利用WHI描述符進(jìn)行粗配準(zhǔn),基于安德森加速ICP的方法進(jìn)行精配準(zhǔn)。不同點(diǎn)云模型下的配準(zhǔn)精度和配準(zhǔn)效率見表2。

從表2可以看出,所提算法在Bunny點(diǎn)云數(shù)據(jù)的配準(zhǔn)時(shí)間為4 s左右,較SAC-IA+NDT、SAC-IA+ICP、WHI+ICP方法的22 s、26 s、6 s左右,在配準(zhǔn)效率上分別提高了450 %、550 %、50 %。所提算法在Bunny點(diǎn)云配準(zhǔn)的精度為0.0029943,較前三種算法的大致提升了10 %以上。在Dragon模型中,所提算法的配準(zhǔn)時(shí)間為5 s左右,較前三種算法的23 s、28 s、10 s,分別提升了360 %、440 %、50 %左右。所提算法在Dragon模型配準(zhǔn)的精度為0.00176953,較SAC-IA+ICP、cNDT+ICP三種算法分別提升了5 ‰左右,相對于SAC-IA+NDT算法提升了39 %左右。所提算法相較于其他三類算法在點(diǎn)云數(shù)據(jù)配準(zhǔn)過程中具有明顯優(yōu)勢。

4.4 點(diǎn)云配準(zhǔn)算法關(guān)鍵問題分析

(1)ISS算法分析

體素下采樣算法在精簡點(diǎn)云方面具有廣泛的應(yīng)用,下采樣的點(diǎn)云為原始點(diǎn)云的近似點(diǎn)云。ISS算法提取的特征點(diǎn)為配準(zhǔn)點(diǎn)云集中的點(diǎn),速度慢于體素下采樣算法,基于幾何特征的優(yōu)勢相比于體素下采樣算法更具顯著性。實(shí)驗(yàn)選用斯坦福的Armadillo模型進(jìn)行實(shí)驗(yàn),初始位姿如圖2所示。

圖2 點(diǎn)云配準(zhǔn)前的Armadillo模型

在實(shí)際中由于傳感器、掃描環(huán)境的影響,點(diǎn)云獲取過程中不可避免的產(chǎn)生噪聲,選取Armadillo模型驗(yàn)證算法在噪聲環(huán)境下的影響。ISS算法提取后的配準(zhǔn)點(diǎn)集如圖3所示。

圖3 Armadillo模型的ISS特征點(diǎn)集

提取后的配準(zhǔn)點(diǎn)集通過WHI進(jìn)行粗配準(zhǔn)如圖4所示。

圖4 Armadillo模型粗配準(zhǔn)

基于ISS與WHI特征描述子粗配準(zhǔn)后,模型大致重合,能夠?yàn)辄c(diǎn)云精確配準(zhǔn)提供良好的初始點(diǎn)集?；隗w素下采樣和WHI的粗配準(zhǔn)算法未能配準(zhǔn)成功?；隗w素下采樣的特征點(diǎn)包含噪聲點(diǎn)的信息,對點(diǎn)云粗配準(zhǔn)有很大的影響,ISS算法過濾了噪聲點(diǎn)。因此所提算法在噪聲環(huán)境下具有一定的魯棒性。

(2)安德森加速的ICP算法分析

圖5 Bunny模型三點(diǎn)配準(zhǔn)

為確定良好的m值,實(shí)驗(yàn)采取單一變量法,改變m值,記錄加速的ICP算法收斂時(shí)點(diǎn)云配準(zhǔn)的誤差和配準(zhǔn)時(shí)間,如圖6,圖7所示。m的取值對點(diǎn)云配準(zhǔn)的精確度影響比較小,m取值為5時(shí)獲得良好的配準(zhǔn)速度,與文獻(xiàn)[20]中安德森算法在幾何優(yōu)化中的理論相符。

圖6 先前迭代次數(shù)對點(diǎn)云配準(zhǔn)誤差影響

為驗(yàn)證改進(jìn)的精配準(zhǔn)算法的可行性,采用基于WHI的配準(zhǔn)算法對Bunny模型進(jìn)行粗配準(zhǔn),然后利用基于安德森算法的ICP算法進(jìn)行精配準(zhǔn)。所提算法與傳統(tǒng)的ICP算法配準(zhǔn)的RMSE隨著迭代次數(shù)的變化如圖8所示。

從圖8中看出,基于安德森的ICP配準(zhǔn)算法迭代速度快,精度略有提高。實(shí)驗(yàn)中基于安德森的ICP算法運(yùn)行時(shí)間約為0.976s,ICP算法約為3.225s,配準(zhǔn)效率提高了2.3倍左右。在同等配準(zhǔn)精度下,所提算法迭代速度快于ICP算法,可在滿足配準(zhǔn)精度要求下調(diào)整迭代次數(shù)進(jìn)一步提高點(diǎn)云配準(zhǔn)速度。

4.5 點(diǎn)云配準(zhǔn)性能測試

點(diǎn)云數(shù)據(jù)獲取過程中經(jīng)常會受到一些外界的干擾,點(diǎn)云配準(zhǔn)算法應(yīng)該具有一定的抗噪能力,在實(shí)驗(yàn)中選取Bunny模型以及Dragon模型分別進(jìn)行實(shí)驗(yàn),首先對兩種模型加入均值為0以及標(biāo)準(zhǔn)差以0.001為間隔的高斯噪聲得到含有噪聲的數(shù)據(jù)。

從圖9圖10中看出在點(diǎn)云配準(zhǔn)成功情況下,隨著噪聲的增加幾種算法的配準(zhǔn)精度都有所提高,這和精度的評價(jià)標(biāo)準(zhǔn)有關(guān),RMSE的評價(jià)指標(biāo)會過濾掉一些錯(cuò)誤的配準(zhǔn)點(diǎn)對,因此計(jì)算出的點(diǎn)云的配準(zhǔn)精度有所提高,SAC-IA+ICP算法在Bunny模型配準(zhǔn)成功,在Dragon實(shí)驗(yàn)中配準(zhǔn)失敗,其他幾種算法均能配準(zhǔn)成功,配準(zhǔn)精度相差無幾,所提算法相對精度略高一些。

圖9 Bunny模型配準(zhǔn)誤差

圖10 Dragon模型配準(zhǔn)誤差

4.6 真實(shí)環(huán)境下點(diǎn)云配準(zhǔn)性能測試

為了驗(yàn)證該算法在實(shí)際工程應(yīng)用中的有效性,分別選取室內(nèi)、室外真實(shí)點(diǎn)云數(shù)據(jù)進(jìn)行實(shí)驗(yàn),分別來自PCL官網(wǎng)[21]和文獻(xiàn)[22]提供的數(shù)據(jù)集,如圖11、圖12所示。

圖11 點(diǎn)云配準(zhǔn)前的Room模型

圖12 點(diǎn)云配準(zhǔn)前的Arch模型

圖11的點(diǎn)云模型灰色為room_scan1,黑色為room_scan2。圖12為室外真實(shí)場景,灰色點(diǎn)云為s01,黑色為s02。室內(nèi)室外場景的點(diǎn)云數(shù)據(jù)都存在噪聲與離群點(diǎn),最能真實(shí)反映算法的可行性,所提算法可視化結(jié)果見圖13、圖14,算法配準(zhǔn)時(shí)間見表3。

表3 真實(shí)場景配準(zhǔn)時(shí)間

圖13 Room模型配準(zhǔn)可視化

圖14 Arch模型配準(zhǔn)可視化

在噪聲和離群點(diǎn)存在的情況下利用RMSE進(jìn)行誤差計(jì)算不合適,因?yàn)闀恍o關(guān)點(diǎn)對的計(jì)算,從表中看出在含有噪聲、離群點(diǎn)的情況下所提算法配準(zhǔn)效率更高,在含有噪聲的不同場景中配準(zhǔn)速度提高了2倍以上。

5 結(jié) 語

針對現(xiàn)有配準(zhǔn)算法在大批量點(diǎn)云配準(zhǔn)效率低、配準(zhǔn)誤差大,容易受噪聲的干擾的問題,提出了ISS算法精簡點(diǎn)云,利用WHI描述符進(jìn)行采樣一致性算法完成點(diǎn)云粗配準(zhǔn),接著利用安德森算法加速ICP算法完成點(diǎn)云精確配準(zhǔn),與幾種先進(jìn)的算法做對比,實(shí)驗(yàn)表明所提的算法在3D掃描庫場景中點(diǎn)云配準(zhǔn)精度、配準(zhǔn)速度都有不同程度的提高,在有噪聲、離群點(diǎn)的室內(nèi)、外場景算法依然可用,在工程實(shí)際中具有重要的意義。同時(shí)也存在不足,ISS算法參數(shù)設(shè)置復(fù)雜,需要人工干預(yù),實(shí)驗(yàn)?zāi)Ｐ蛻?yīng)在更多的場景中進(jìn)行,這也是后期將要改進(jìn)的地方。