改進的多分辨率點云自動配準算法

王 勇,黎 春,何養(yǎng)明,陳薈西

(重慶理工大學(xué) 計算機科學(xué)與工程學(xué)院,重慶 400054)E-mail:2351583604@qq.com

1 引 言

點云自動配準方法一般分為粗配準和精配準兩步.粗配準方法包括標志點法、重心重合法、特征提取法等方法[1,2].標志點法需要人為貼上標志點,但人為因素會導(dǎo)致誤差等問題,影響后續(xù)配準精度;重心重合法要將點云的兩個中心重合在一起,適用于點云重疊度較高的情況;特征提取法一般不適用于物體特征不明顯的點云配準.由于粗配準算法存在的上述缺陷以及點云的拓撲結(jié)構(gòu)、稀疏程度、噪聲等的存在[1],導(dǎo)致粗配準的精度很難滿足人們的要求,因此,需要對粗配準結(jié)果進行精配準.

目前國內(nèi)外最常用的精配準算法是由 Besl[3]等人和 Chen[4]等人分別提出的迭代最近點算法(Iterative Close Point,ICP),但該算法存在以下缺陷:當(dāng)兩片點云沒有較好的初始位置時,易陷入局部最優(yōu);算法是對點云中的所有點進行處理,因此搜尋匹配點時間很長,且點云規(guī)模越大其效率越低.因此,眾多國內(nèi)外專家學(xué)者提出了一系列的優(yōu)化算法.LI[5]引入動態(tài)調(diào)整因子進行ICP 配準,在不影響配準精度的前提下,提高了算法的配準效率.文獻[6]提出利用局部深度信息、法線偏角和點云密度信息建立局部特征描述子,再根據(jù)該局部特征描述子的相關(guān)性完成配準,解決了點云覆蓋率較低時的配準問題.文獻[9]在經(jīng)典ICP算法的基礎(chǔ)上引入帶邊界的尺度因素和動態(tài)迭代因子,既解決了配準中尺度變換的問題,也提高了算法速度,但沒有考慮到旋轉(zhuǎn)角度、噪聲等因素.文獻[10]提出一種使用深度神經(jīng)網(wǎng)絡(luò)自動編碼器進行3D點云配準;該算法首先對點云分為超點集,并將超點集投影成深度圖;然后采用深度神經(jīng)網(wǎng)絡(luò)進行特征壓縮,獲取特征描述子并進行粗配準,最后采用ICP進行精配準;該算法在數(shù)據(jù)缺失的情況下,其配準精度也很高.文獻[11]提出一種NV關(guān)鍵點和快速點特征直方圖結(jié)合的快速點云配準算法,該算法提取點云關(guān)鍵點比較簡單,能實現(xiàn)點云快速配準;文獻[12]使用曲率特征指導(dǎo)點云配準,該算法對于表面平緩的點云數(shù)據(jù),其配準效果優(yōu)于結(jié)合法向量變換的ICP算法.上述方法相較于傳統(tǒng)ICP算法在精度、速度或尺度因素方面有所改進,但沒有考慮到噪聲因素存在下算法配準的穩(wěn)定性和魯棒性.

本文提出一種改進的多分辨率點云自動配準算法.為避免因點云初始位置而陷入局部最優(yōu)的問題,首先采用文獻[8]中的算法進行粗配準.為了進一步改善該算法的速度,分別對源點云和目標點云建立KD-tree;同時提出利用法向量夾角平均值的均值設(shè)置特征提取的閾值,能有效提取特征點,且不會損失大量特征不明顯的點云信息,進一步保證了配準的精度.為了解決粗配準精度不夠的問題,提出了一種改進的多分辨率迭代最近點算法進行精配準.該方法利用法向量夾角平均值對點云中的點進行分級,并根據(jù)特征點的稠密度計算點云分辨率,然后利用改進的采樣比例進行下采樣,并采用文獻[7]中的匹配度提取關(guān)鍵點對,避免了大量出現(xiàn)錯誤匹配點對的情況,最后迭代完成配準.

2 粗配準算法

本文粗配準采用精度較高的文獻[8]中的算法,并對特征點提取部分進行了改進.同時,為了解決該算法速度較慢的問題,本文對兩片點云建立KD-tree,對比窮盡搜索的方法其搜索速度得到了很大的提高,且隨著點云規(guī)模的遞增,其效果更明顯.然后分別對源點云和目標點云中的點計算特征度,并根據(jù)特征度提取特征點集.然后分別對源點云和目標點云中的特征點集建立直方圖特征描述子,并根據(jù)特征直方圖獲取初始匹配點對.對于含有誤匹配點對的初始匹配點對采用歐式距離約束和隨機抽樣一致性(Random Sample Consensus,RANSAC)算法剔除誤配點對,最后利用四元素法完成粗配準.算法的整個流程如圖1所示.

圖1 粗配準算法流程圖Fig.1 Rough registration algorithm flow diagram

·改進的特征點提取算法

本文根據(jù)公式(1)計算點云的特征度,即法向量夾角平均值,其中法向量采用文獻[7]所述的主成分分析法(PCA)求取.

(1)

式中,npi為源點云中某點pi的法向量,npj為pi的k近鄰點pj的法向量,pni為源點云中某一點與其k近鄰點法向量夾角的平均值.用pni描述點云的區(qū)域特性,若pni較小,則說明此區(qū)域幾何特征變化較平緩;若pni較大,說明此區(qū)域存在突出的幾何特征;本文根據(jù)pni值提取源點云中的特征點.在提取特征點時,去掉源點云中特征不明顯的部分,保留pni>ε1的點,然后對于保留的點中的每一點px,提取滿足公式(3)的點作為特征點.

在特征點提取過程中,閾值的選取相當(dāng)重要.若閾值取值過大,提取的特征點就會相對較少,可能會損失部分點云的關(guān)鍵特征信息和大量細節(jié)信息;若閾值選取過小,可以保留大量細節(jié)信息,但是會導(dǎo)致點云配準的速度變慢.在文獻[8]中,閾值ε1為根據(jù)實驗選取的經(jīng)驗值,針對不同的點云數(shù)據(jù)需要多次實驗選擇合適的閾值,在實際應(yīng)用中不方便.本文提出根據(jù)點云中每個點的法向量與其近鄰點法向量的乘積的均值來計算,該方法可根據(jù)法向量變化自適應(yīng)的計算閾值,從而自適應(yīng)的提取特征點,可以很好的保留點云的關(guān)鍵特征信息,同時剔除了大量影響較小的細節(jié)信息,加快了配準速度.其計算公式見公式(2):

(2)

pn(px)=max[pn(px1),pn(px2),…,pn(pxk)]

(3)

式中,Np為點云中的點數(shù),px是點云中的某一特征點,pn(pxi)(i=1,2,…,k)為點px的k近鄰點的法向量夾角平均值,根據(jù)此特征點提取方法對源點云和目標點云中的所有點進行特征點提取,分別得到P的特征點集pf和Q的特征點集Qf.

3 精配準算法

3.1 改進的多分辨率關(guān)鍵點采樣

多分辨率配準的精髓在于可以根據(jù)級數(shù)和分辨率來調(diào)整所提取的關(guān)鍵點.級數(shù)控制每一級提取的點數(shù),級數(shù)越大,采樣比例越大;分辨率控制整體提取的點數(shù),分辨率越大,整體采樣的點越多,精度越高,速度相對較慢.為了使點云快速收斂,利用低分辨率匹配點對進行快速配準,然后利用高分辨率匹配點對提高配準精度,以此來解決點云配準精度低、速度慢的問題.

分辨率可以用點云的稠密程度來反映,稠密程度[13]為點云中各點與其k近鄰點歐式距離的均值.但計算一片點云中的所有點的稠密程度其計算量很大,因此,本文提出利用特征點與其k近鄰點歐式距離的均值來計算,并根據(jù)調(diào)整因子動態(tài)調(diào)整分辨率的大小.該方法根據(jù)點云特征點的稠密度計算點云分辨率,比起憑經(jīng)驗設(shè)置更加合理.為了不重復(fù)提取特征點從而減少時間復(fù)雜度,在粗配準提取特征點時就計算并輸出點云的分辨率.其分辨率由公式(4)計算:

(4)

本文根據(jù)公式(1)計算的法向量夾角平均值對點云中的點分為m級,法向量夾角平均值越大,其特征越明顯,反之,法向量夾角平均值越小,特征越不明顯.但通常獲取的大多數(shù)點云數(shù)據(jù),特征明顯的點相對較少,特征不明顯的點相對較多,因此,在配準時,若僅依靠特征明顯的關(guān)鍵點進行配準其精度較低,且有可能會導(dǎo)致配準失敗.本文提出改進的采樣方式不僅充分利用了特征明顯的關(guān)鍵點,同時充分利用了特征不明顯的點.

在文獻[7]中,當(dāng)分辨率為j(1≤j≤n),級數(shù)為i(1≤i≤m)時,其提取關(guān)鍵點的采樣比例Ri,j由公式(5)計算:

(5)

式中,countm表示第m級的點數(shù),counti表示第i級的點數(shù),fix為向下取整函數(shù).該采樣比例在級數(shù)較低時,提取的關(guān)鍵點太少,丟失了大量特征不明顯的關(guān)鍵點信息,導(dǎo)致配準精度相對較低.

本文改進的采樣比例Ri,j由公式(6)計算,每一分辨率下各級提取的關(guān)鍵點keypointi,j由公式(7)計算:

(6)

keypointi,j=round(Ri,j·counti)

(7)

該采樣方式提高了級數(shù)較低時的采樣比例,充分利用了特征不明顯的點.由于采樣的關(guān)鍵點數(shù)增多其速度稍慢,但極大的提高了配準的精度.

3.2 改進的多分辨率迭代配準點算法

點云配準就是求解旋轉(zhuǎn)矩陣R和平移矩陣T,使公式(8)最小化:

(8)

式中,qi為目標點集中的點,pi為源點集中的點,Np為源點集中的點數(shù).

為解決傳統(tǒng)ICP算法計算效率、精度及易受噪聲干擾的問題,本文算法首先通過初始配準獲取較好的初始位姿,并改進文獻[7]中多分辨率配準點ICP算法.在文獻[7]中,分辨率是憑經(jīng)驗設(shè)置的,對于不同規(guī)模的點云數(shù)據(jù)需要多次實驗確定其值,在應(yīng)用上不是很方便.本文在初始配準階段通過計算點云中各特征點與其近鄰點距離的均值來確定點云分辨率.其次,采用匹配度提取關(guān)鍵點對,減少了錯誤匹配率,提高了算法的精度和魯棒性.改進ICP算法流程如算法1所示.

算法1.改進的多分辨率迭代配準點算法

輸入:通過初始配準轉(zhuǎn)換后的源點云P1,目標點云Q,迭代次數(shù),級數(shù)m,初始配準中輸出的分辨率n;

輸出:旋轉(zhuǎn)矩陣R,平移矩陣T,均方根誤差ER;

Step 1.初始化:R,T,ER;

Step 2.對源點云P1、目標點云Q建立KD-tree,并計算P1和Q的法向量;

Step 4.

fori=1:n

forj=1:m

計算提取關(guān)鍵點的采樣比例Ri,j;

計算各級提取的關(guān)鍵點keypointi,j;

end for

end for

Step 5.

while(目標函數(shù)不是最優(yōu)‖迭代次數(shù)沒有達到最大)

根據(jù)文獻[7]中的方式求采樣點的匹配度,并提取關(guān)鍵點對;

使用四元素法對獲得的匹配點對計算旋轉(zhuǎn)矩陣R和平移矩陣T;

end while

4 實驗與分析

本文實驗在Intel(R)Core(TM)i5-6300 CPU、8GB內(nèi)存、Windows 10操作系統(tǒng)、Matlab R2015a環(huán)境下進行.為了驗證本文算法的有效性,采用了Standford 3D Scanning Repository(1)https://graphics.stanford.edu/data/3Dscanrep/的Bunny和Buddha點云進行粗配準與精配準.并分別與經(jīng)典ICP、文獻[7]、文獻[8]中的算法進行了比較.本文粗配準算法中的參數(shù)設(shè)置:ε1通過計算得到,ε2=0.05,ε3=0.02,k=16;本文精配準算法中的參數(shù)設(shè)置:分辨率n通過計算得到,m=3,k=8.

4.1 實驗1

實驗1選取0度和24度的Bunny點云數(shù)據(jù)進行配準.圖2為不加入噪聲時各種算法對Bunny點云進行配準的效果圖,圖3為加入1000個高斯白噪聲點后各種算法對Bunny點云進行配準的效果圖.其中圖2(a)和圖3(a)為兩視角的原始數(shù)據(jù)圖，圖2(b)和圖3(b)為經(jīng)典ICP算法的配準效果圖，圖2(c)和圖3(c)為文獻[7]算法的配準效果圖，圖2(d)和圖3(d)為文獻[8]算法的粗配準效果圖，圖2(e)和圖3(e)為本文粗配準算法的效果圖，圖2(f)和圖3(f)為本文精配準算法的效果圖.

圖2 Bunny配準實驗Fig.2 Bunny registration experiment

圖3 帶噪聲的Bunny配準實驗Fig.3 Bunny registration experiment with noise

從圖2中可看出,經(jīng)典ICP、文獻[8]和本文算法配準效果很好,文獻[7]算法在頭部和前腳部分配準效果不是很好.從圖3中可看出,在噪聲存在的情況下經(jīng)典ICP、文獻[7]配準效果很差,文獻[8]在耳朵部分、頭部區(qū)域及前腳部分配準效果也不是很好,本文粗配準效果比文獻[8]略差,但本文精配準效果在幾種算法中最好.

表1 不同算法配準對比Table 1 Different algorithm registration comparison

表1為各種配準算法對原Bunny點云和帶噪聲的Bunny點云配準速度和配準誤差的對比.可以看出經(jīng)典ICP算法最耗時,同時容易受噪聲干擾,在噪聲點云配準中其精度很低;文獻[7]算法配準速度得到了極大的提升,在原Bunny點云配準時其精度比經(jīng)典ICP低,但同樣易受噪聲干擾;文獻[8]粗配準算法精度比經(jīng)典ICP和文獻[7]高,同時受噪聲干擾的程度比以上兩種算法小,但其速度較慢;本文粗配準算法在原Bunny點云配準和帶噪聲點云配準時精度比文獻[8]略低,但其速度比文獻[8]快將近3倍;本文精配準算法在粗配準的基礎(chǔ)上進一步提升了精度,尤其是對帶噪聲的點云配準其穩(wěn)定性更好、精度更高.

4.2 實驗2

實驗2選取不同視角不同規(guī)模的Buddha點云數(shù)據(jù)進行實驗,表2為各種算法對不同規(guī)模的Buddha點云進行配準的對比,表3為對Buddha(0度和24度)點云數(shù)據(jù)加入不同規(guī)模噪聲進行配準的對比.

表2 不同規(guī)模Buddha點云配準Table 2 Buddha point cloud registration of different scales

從表2中可以看出,無論是哪種配準算法,點云規(guī)模越大,其配準所花時間越多;無論是哪種規(guī)模的點云數(shù)據(jù),本文算法總體性能最佳.經(jīng)典ICP雖然配準精度較好,但是其速度太慢;文獻[7]和文獻[8]精度差不多,但文獻[7]速度更快,本文方法通過二次配準進一步提高了配準精度,其配準精度在幾種對比算法中最高,總體速度比文獻[8]更快.

從表3中可以看出,各種算法在加入噪聲點后其精度和速度都受到了不同程度的影響.其中,經(jīng)典ICP和文獻[7]受噪聲影響的程度最大,隨著噪聲的加入其精度變得較差.經(jīng)典ICP在加入噪聲點后,其運算效率變快、精度變低,但并不是隨著加入的噪聲越多其精度越差,這是由于噪聲點的位置分布所導(dǎo)致.文獻[7]在加入噪聲點后,其速度變化不是很大,精度變低,但精度不是隨著噪聲點的規(guī)模呈現(xiàn)線性增長.文獻[8]粗配準算法和本文粗配準、精配準算法魯棒性都比較好,其精度基本不受噪聲影響,文獻[8]和本文粗配準算法中由于加入了RANSAC算法進一步剔除了誤匹配點,增強了算法的魯棒性,且本文粗配準算法速度比文獻[8]快近3倍.本文精配準算法在粗配準的基礎(chǔ)上進一步進行配準,同時改進了采樣比例,使其配準精度在本文各種算法中更高、配準穩(wěn)定性更好.

5 結(jié) 論

提出一種改進的多分辨率點云自動配準算法,該算法針對ICP算法對點云初始位姿的要求,結(jié)合文獻[8]中的粗配準算法進行快速配準,然后對位姿較好的點云進行精確配準,進一步提高算法的精度.

為了盡可能的提高配準精度、增強算法的抗噪性,本文算法在粗配準部分采用歐式距離約束和RANSAC算法進行外點剔除,提高了粗配準的精度,確保其對于含噪聲的和部分重疊度的點云都能為精配準提供較好的初始位姿.在精確配準部分,首先改進了分辨率的設(shè)置問題,分辨率可通過點云特征點的稠密度自適應(yīng)的取值,避免了分辨率設(shè)置過大而導(dǎo)致的配準速度較慢的問題和分辨率設(shè)置過小而導(dǎo)致的精度不高的問題.其次改進了算法的采樣比例,提高了其對于特征信息不明顯的點云的配準精度,增強了算法的適用性.本文通過實驗證明了算法的可行性和有效性,無論對哪種規(guī)模的點云進行配準,本文算法精度都比較高,同時速度較快.