方博，岳曉峰，袁曉磊，馬國(guó)元

(長(zhǎng)春工業(yè)大學(xué) 機(jī)電工程學(xué)院，吉林 長(zhǎng)春 130012)

0 引言

點(diǎn)云數(shù)據(jù)是三維目標(biāo)模型的重要空間結(jié)構(gòu)數(shù)據(jù)，由點(diǎn)云驅(qū)動(dòng)的計(jì)算機(jī)圖形學(xué)在逆向工程、數(shù)字城市、智能機(jī)器人、無(wú)人駕駛和人機(jī)交互等領(lǐng)域發(fā)揮著越來越重要的作用[1-2]。

針對(duì)點(diǎn)云配準(zhǔn)這一關(guān)鍵性問題，迭代最近點(diǎn)算法(iteration closest point, ICP)[3]是目前應(yīng)用最廣的點(diǎn)云配準(zhǔn)算法，國(guó)內(nèi)外學(xué)者多采用特征點(diǎn)粗配準(zhǔn)來獲取點(diǎn)云間良好的初始配準(zhǔn)位置，再采用ICP算法進(jìn)行精確配準(zhǔn)。針對(duì)特征點(diǎn)的提取，CHEN Y等[4]采用待配準(zhǔn)點(diǎn)云的點(diǎn)法線與參考點(diǎn)點(diǎn)云的交點(diǎn)來確定對(duì)應(yīng)點(diǎn)，該方法能減少迭代次數(shù)并加快算法收斂速度，但在某些情況下魯棒性較差。RUSU R B等[5]提出快速特征直方圖(FPFH)特征，目的是通過點(diǎn)周圍的平均曲率來編碼其鄰域的幾何屬性，該算法能很好地應(yīng)對(duì)鄰域中存在不同采樣密度或不同噪聲水平的點(diǎn)，進(jìn)而提升配準(zhǔn)精度。RUSINKIEWICZ S等[6]提出基于法線空間的均勻采樣方法，在具有較少特征點(diǎn)的點(diǎn)云進(jìn)行配準(zhǔn)時(shí),該方法可以提高配準(zhǔn)速度。楊玲等[7]將普氏分析法與 ICP 算法結(jié)合，提出了 PICP(procrustes ICP)算法，在獲得點(diǎn)云初始位置的情況下，采用普氏分析法求解轉(zhuǎn)換參數(shù)，針對(duì)不同的點(diǎn)集均獲得較好的魯棒性。隨著提取場(chǎng)景點(diǎn)云的復(fù)雜程度、稠密程度提升帶來的噪聲、遮擋等問題，特征點(diǎn)提取的難度及特征描述子的計(jì)算量也隨之提升，計(jì)算效率也因此下降。

本文針對(duì)點(diǎn)云配準(zhǔn)效率問題進(jìn)行研究，提出了一種易于實(shí)現(xiàn)且魯棒性高的多分辨率點(diǎn)對(duì)特征配準(zhǔn)方法。在初始階段通過本文提出的自適應(yīng)體素網(wǎng)格濾波器對(duì)原始點(diǎn)云進(jìn)行自適應(yīng)分辨率采樣，合理、有效地減少了點(diǎn)云中的冗余點(diǎn)對(duì)，可節(jié)省內(nèi)存開銷并提高計(jì)算效率。位姿聚類結(jié)束后，再通過迭代最近點(diǎn)進(jìn)行位姿優(yōu)化提升算法的準(zhǔn)確性，進(jìn)一步改善了原始點(diǎn)對(duì)特征算法的識(shí)別性能。

1 點(diǎn)對(duì)特征

點(diǎn)對(duì)特征(point pair feature, PPF)描述的是一對(duì)有方向的點(diǎn)的相對(duì)位置和姿態(tài)，其中包含有4種簡(jiǎn)單幾何屬性構(gòu)成的四元數(shù)組。如圖1所示，假設(shè)有兩個(gè)點(diǎn)m1和m2，法向量分別為n1和n2。PPF[8]定義為

圖1 點(diǎn)對(duì)特征圖

(1)

式中：d=m2-m1；F表示m1、m2的點(diǎn)對(duì)特征；∠(a,b)表示兩向量間的夾角。由定義可知，F(xiàn)是不對(duì)稱的，即F(m1，m2)≠F(m2，m1)。

上述F即為一對(duì)點(diǎn)的點(diǎn)對(duì)特征，在點(diǎn)對(duì)特征算法中，需要計(jì)算model表面所有點(diǎn)對(duì)的特征矢量F。

2 體素網(wǎng)格方法

目前，隨著點(diǎn)云采集儀器精度的提高，需要處理和計(jì)算的點(diǎn)云數(shù)目不斷增加，傳統(tǒng)點(diǎn)對(duì)特征算法已經(jīng)無(wú)法適應(yīng)點(diǎn)云數(shù)目巨大的模型點(diǎn)云處理。下采樣時(shí)，通常會(huì)盡可能地保留源點(diǎn)云的表面特征和保證一定質(zhì)量的密度分布，否則將不利于點(diǎn)云的后續(xù)處理。若使用隨機(jī)采樣方法，則點(diǎn)云的輪廓信息會(huì)變?nèi)?，且點(diǎn)云分布也會(huì)不均勻。而使用體素網(wǎng)格濾波器對(duì)源點(diǎn)云進(jìn)行下采樣，在減少點(diǎn)云數(shù)量的同時(shí)，還可以保持源點(diǎn)云的形態(tài)特征。

體素網(wǎng)格下采樣[9-13]的主要思路是：根據(jù)原始點(diǎn)云數(shù)據(jù)創(chuàng)建一個(gè)三維體素柵格，計(jì)算出需要?jiǎng)澐值娜S立方柵格的邊長(zhǎng)L，然后計(jì)算每個(gè)立方體內(nèi)所有點(diǎn)的質(zhì)心來替代這個(gè)立方體柵格中的所有點(diǎn)。該方法從整體上對(duì)點(diǎn)云數(shù)量進(jìn)行簡(jiǎn)化，并可以保持源點(diǎn)云的形態(tài)特征。具體計(jì)算方法如下所示。

1)求出初始點(diǎn)云模型中的最大、最小值頂點(diǎn)(xmax，ymax，zmax)和(xmin，ymin，zmin)。以這兩個(gè)頂點(diǎn)構(gòu)建一個(gè)包圍盒，在頂點(diǎn)(xmin，ymin，zmin)上固定一個(gè)坐標(biāo)系，方向與歐氏空間的(x，y，z)方向相同，構(gòu)成體素空間Z3。

2)確定立方體邊長(zhǎng)L，并將點(diǎn)云分成多個(gè)大小為L(zhǎng)×L×L的立方體。L的值越小，采樣后的點(diǎn)云分辨率越高；值越大，采樣后的點(diǎn)云分辨率則越低。采樣立方體的個(gè)數(shù)為A×B×C，計(jì)算方法如下：

(2)

3)計(jì)算每個(gè)立方體的質(zhì)心，計(jì)算方法如下：

(3)

式中m為該立方體中點(diǎn)的數(shù)目。

3)以質(zhì)心(x′，y′，z′)代替該立方體中所有的點(diǎn)，并將所有立方體的質(zhì)心重新整合成新的點(diǎn)云。

4)由式(2)不難看出，采樣立方體的個(gè)數(shù)，受立方體邊長(zhǎng)L的影響，而傳統(tǒng)體素化網(wǎng)格中的邊長(zhǎng)L在下采樣時(shí)需要手動(dòng)設(shè)定體素立方體的邊長(zhǎng)，這就降低了算法效率。本文提出了一種改進(jìn)的自適應(yīng)體素網(wǎng)格濾波器，可以根據(jù)源點(diǎn)云中點(diǎn)云的數(shù)量自動(dòng)計(jì)算體素網(wǎng)格的邊長(zhǎng)，并可根據(jù)自適應(yīng)系數(shù)的調(diào)節(jié)采樣分辨率，以適應(yīng)不同尺度的點(diǎn)云集合。

3 自適應(yīng)體素網(wǎng)格濾波器

針對(duì)不同數(shù)量的點(diǎn)云，本文改進(jìn)了體素網(wǎng)格濾波器，對(duì)邊長(zhǎng)L的立方體運(yùn)用了自適應(yīng)采樣分辨率更新策略，方法如下：

L=Davg×ω(s)

(4)

式中：Davg表示初始輸入點(diǎn)云中兩點(diǎn)之間的平均距離；ω(s)為邊長(zhǎng)L的自適應(yīng)比例因子，用以控制邊長(zhǎng)L的增長(zhǎng)率。計(jì)算方法分別如下：

(5)

式中：M為初始點(diǎn)云中點(diǎn)云的總數(shù)；Ni為M中的第i個(gè)點(diǎn)；Ndi為M中離Ni距離最近的點(diǎn)。

(6)

在立方體邊長(zhǎng)計(jì)算中引入式(6)用以控制立方體邊長(zhǎng)的增長(zhǎng)率。由式(6)可知，當(dāng)初始輸入點(diǎn)云的數(shù)量越多，ω(s)的值就越大，立方體邊長(zhǎng)自適應(yīng)變大，點(diǎn)數(shù)減少更快；當(dāng)初始輸入點(diǎn)云的數(shù)量少時(shí)，ω(s)的值就會(huì)變小，立方體邊長(zhǎng)自適應(yīng)變小，點(diǎn)數(shù)減少速度就放慢，實(shí)現(xiàn)了自適應(yīng)的分辨率調(diào)節(jié)，不僅可以有效地減少點(diǎn)云中的冗余點(diǎn)對(duì)，還提高了整體點(diǎn)云配準(zhǔn)算法的效率。在加入激活函數(shù)后，實(shí)現(xiàn)了立方體邊長(zhǎng)的自適應(yīng)控制，更加簡(jiǎn)便快捷。

4 算法的實(shí)現(xiàn)

本文提出的算法，在離線訓(xùn)練階段將點(diǎn)云下采樣后得到的具有相同點(diǎn)對(duì)特征F的點(diǎn)對(duì)集合在一起，即哈希表的鍵(key)實(shí)際上為F，內(nèi)存的值為具有相同特征矢量的點(diǎn)集A；在線識(shí)別階段，隨機(jī)選取一點(diǎn)作為種子點(diǎn)ps，搜索與之距離不超過半徑r的點(diǎn)，組成點(diǎn)集Q(ps)={q1，q2，…，qk}，計(jì)算ps與Q(ps)中每個(gè)點(diǎn)的點(diǎn)對(duì)特征F，并根據(jù)哈希值查找與之匹配的候選點(diǎn)對(duì)集合D[F(ps，pk)]。通過場(chǎng)景點(diǎn)對(duì)和哈希表中查找到的候選點(diǎn)對(duì)進(jìn)行匹配，采用投票策略，選取投票較多的位姿組成新的集合，得到初步候選位姿集合C；采用聚類策略對(duì)候選位姿集合進(jìn)行處理，從中提取出正確的位姿；最后返回中進(jìn)行位姿優(yōu)化得到最終位姿作為目標(biāo)點(diǎn)云配準(zhǔn)的結(jié)果。算法流程圖如圖2所示。

圖2 配準(zhǔn)流程圖

5 實(shí)驗(yàn)結(jié)果與分析

本文采用的實(shí)驗(yàn)平臺(tái)為Window10系統(tǒng)，Visual Studio2019，配置為啟天M4500-N000，酷睿TMi5-4590，CPU 3.8 GHz，8 GB DDR3的聯(lián)想臺(tái)式計(jì)算機(jī)上。算法沒有依賴GPU等其他的加速優(yōu)化工具，為驗(yàn)證算法的有效性和魯棒性，分別與傳統(tǒng)ICP算法和文獻(xiàn)[14]中算法的配準(zhǔn)時(shí)間和精度進(jìn)行比較，實(shí)驗(yàn)使用Stanford University開放點(diǎn)云數(shù)據(jù)庫(kù)的Bunny(兔子)和Dragon(龍)模型進(jìn)行對(duì)比實(shí)驗(yàn)。

圖3是兔子和龍的初始點(diǎn)云模型。圖4分別為兔子和龍模型在不同分辨率下的點(diǎn)云模型，由式(4)-式(6)計(jì)算可得自適應(yīng)邊長(zhǎng)L。下采樣后的點(diǎn)數(shù)設(shè)置為不低于3 000個(gè)。圖4(a)為兔子模型下采樣一次，自適應(yīng)系數(shù)為2.53；圖4(b)為龍模型下采樣，自適應(yīng)系數(shù)為2.51。表1為兔子和龍?jiān)谧赃m應(yīng)下采樣下的采樣點(diǎn)數(shù)和所耗費(fèi)時(shí)長(zhǎng)。下采樣結(jié)果表明，使用本文所提自適應(yīng)下采樣體素濾波器采樣得到的點(diǎn)云模型，即使在大量減少點(diǎn)云點(diǎn)數(shù)之后，仍可以保留原始點(diǎn)云的形態(tài)特征，且自適應(yīng)策略下的下采樣所耗費(fèi)的時(shí)間也是極短的。

圖3

圖4 模型簡(jiǎn)化圖

表1 自適應(yīng)下采樣計(jì)算耗時(shí)和點(diǎn)云簡(jiǎn)化率

圖5為兔子和龍的配準(zhǔn)實(shí)驗(yàn)結(jié)果?？梢钥闯鑫墨I(xiàn)[14]的匹配結(jié)果效果略差，部分地方出現(xiàn)了重影，傳統(tǒng)ICP算法和本文所提算法配準(zhǔn)結(jié)果基本一致，但配準(zhǔn)時(shí)間花費(fèi)較長(zhǎng)。

圖5 配準(zhǔn)結(jié)果

表2所示為3種算法在兔子和龍模型中的配準(zhǔn)時(shí)間之間的比較。由表中數(shù)據(jù)表明：在配準(zhǔn)精度相當(dāng)?shù)那闆r下，本文算法所需時(shí)間相對(duì)于傳統(tǒng)ICP算法和文獻(xiàn)[14]大大縮短。尤其是在點(diǎn)云較稠密，數(shù)量較多的龍模型中，更能體現(xiàn)本文算法的快速性和準(zhǔn)確性。原始ICP算法由于點(diǎn)數(shù)過多，導(dǎo)致配準(zhǔn)時(shí)長(zhǎng)迅速增長(zhǎng)，文獻(xiàn)[14]雖然將時(shí)間縮短至原始ICP算法的2/3，但是耗時(shí)仍然很長(zhǎng)。

表2 配準(zhǔn)誤差相近的情況下算法性能比較

為了進(jìn)一步驗(yàn)證本算法在準(zhǔn)確性和省時(shí)性上的提升，選取4組不同點(diǎn)云數(shù)目的點(diǎn)云進(jìn)行配準(zhǔn)實(shí)驗(yàn)，配準(zhǔn)誤差的要求依然不變。在保證配準(zhǔn)精度的同時(shí)，再次將本文算法、文獻(xiàn)[14]和原始傳統(tǒng)點(diǎn)對(duì)特征算法進(jìn)行比較，如表3所示。本文算法在點(diǎn)云數(shù)目較少時(shí)，相較于傳統(tǒng)ICP算法，耗時(shí)僅為原先的36%；在點(diǎn)云數(shù)目較多時(shí)，相較于傳統(tǒng)ICP算法，耗時(shí)僅為原始ICP的17%。且在各種規(guī)模的點(diǎn)云模型中，耗時(shí)均少于文獻(xiàn)[14]。結(jié)合圖6實(shí)驗(yàn)結(jié)果表明，本文所提出的自適應(yīng)分辨率的點(diǎn)對(duì)特征配準(zhǔn)算法在保證配準(zhǔn)精度的同時(shí)，還可以快速收斂。

表3 不同稠密度點(diǎn)云的配準(zhǔn)耗時(shí) 單位：s

圖6 不同方法配準(zhǔn)耗時(shí)

6 結(jié)語(yǔ)

本文提出了一種改進(jìn)的自適應(yīng)分辨率點(diǎn)對(duì)特征配準(zhǔn)算法。算法通過構(gòu)造的自適應(yīng)分辨率體素化網(wǎng)格方法，對(duì)原始點(diǎn)云進(jìn)行下采樣處理，在減少冗余點(diǎn)云數(shù)量的同時(shí)，有效地保留了點(diǎn)云的原始特征，提升了配準(zhǔn)的效率。實(shí)驗(yàn)表明：本文算法與傳統(tǒng)ICP算法相比，在配準(zhǔn)誤差相同的情況下，配準(zhǔn)效率提升顯著。隨著點(diǎn)云數(shù)量和稠密度的提升，本文算法的優(yōu)勢(shì)將呈遞增的趨勢(shì)。