王正家,蘇超全,聶 磊

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

1 引 言

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

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

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

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

2.1 局部坐標參考系

一個獨特的、可重復的、魯棒的局部坐標參考系對于特征描述是非常重要的[16]。LRF估計一般通過局部點云的協(xié)方差矩陣特征值分解得到:

(1)

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

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

C(pf)=QΛQT

(2)

(3)

(4)

(5)

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

(6)

(7)

signy=signx×signz

(8)

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

(9)

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

2.2 WHI特征描述符生成

(10)

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

0<η≤1

(11)

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

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

(12)

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

(13)

(14)

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

(15)

同理:

(16)

(17)

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

3 特征點提取及點云配準

3.1 ISS算法

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

Step1:利用kd_tree構(gòu)建三維點云k鄰域內(nèi)的拓撲結(jié)構(gòu),從而利于三維點云的搜索;

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

(18)

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

(19)

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

(20)

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

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

(21)

(22)

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

3.2 基于WHI的粗配準

(1)對源點云、目標點云提取ISS特征點計算點對的WHI特征;

(2)利用kdtree算法搜索相近特征的對應點對,作為對應點對;

(3)從對應的點集中隨機選取四個對應點對,采用SVD算法計算源點云與目標點云之間的變換矩陣;

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

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

3.3 基于ICP改進的精配準

3.3.1 安德森加速算法

(23)

(24)

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

3.3.2 安德森加速的ICP點云配準算法

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

(25)

(26)

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

(27)

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

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

(2)ICP迭代更新:

(4)計算加速值XAA。

Rd中的所有剛性變換都形成了特殊的歐幾里得群SE(d),這是一個李群,并產(chǎn)生了一個李代數(shù)SE(d),它是一個向量空間。可以使用se(d)中對應的元素將剛性變換參數(shù)化。每個點的齊次坐標p=[pT,1]T,剛性變換T通過旋轉(zhuǎn)矩陣平移向量表示:

(28)

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

(29)

(30)

4 實驗和分析

實驗選取不同的點云模型進行研究,通過點云配準的精度、時間作為配準指標,所提算法和幾種先進的算法進行比較證實所提算法的先進性。

4.1 實驗數(shù)據(jù)和實驗條件

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

實驗中待配準點云模型的初始位置如圖1,灰色為待配準點云,黑色為目標點云。

圖1 點云配準前的Bunny、Dragon模型

4.2 評價指標

(1)精確度指標

(31)

表1 原始點云的維度

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

(2)速率指標

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

4.3 點云配準時間和精度

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

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

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

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

(1)ISS算法分析

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

圖2 點云配準前的Armadillo模型

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

圖3 Armadillo模型的ISS特征點集

提取后的配準點集通過WHI進行粗配準如圖4所示。

圖4 Armadillo模型粗配準

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

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

圖5 Bunny模型三點配準

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

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

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

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

4.5 點云配準性能測試

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

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

圖9 Bunny模型配準誤差

圖10 Dragon模型配準誤差

4.6 真實環(huán)境下點云配準性能測試

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

圖11 點云配準前的Room模型

圖12 點云配準前的Arch模型

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

表3 真實場景配準時間

圖13 Room模型配準可視化

圖14 Arch模型配準可視化

在噪聲和離群點存在的情況下利用RMSE進行誤差計算不合適,因為會包含一些無關(guān)點對的計算,從表中看出在含有噪聲、離群點的情況下所提算法配準效率更高,在含有噪聲的不同場景中配準速度提高了2倍以上。

5 結(jié) 語

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