無(wú)序多視角點(diǎn)云的自主配準(zhǔn)方法

徐思雨,祝繼華,姜祖濤,郭瑞,李垚辰

(西安交通大學(xué)軟件學(xué)院,710049,西安)

點(diǎn)云配準(zhǔn)問(wèn)題是在計(jì)算機(jī)視覺(jué)[1-3]和移動(dòng)機(jī)器人[4]等研究領(lǐng)域中的基礎(chǔ)問(wèn)題。根據(jù)待配準(zhǔn)點(diǎn)云數(shù),該問(wèn)題可分為雙視角和多視角點(diǎn)云配準(zhǔn)兩種類型。

雙視角配準(zhǔn)是多視角配準(zhǔn)的基礎(chǔ),其實(shí)質(zhì)是通過(guò)定義相似性測(cè)度函數(shù),并建立兩幀點(diǎn)云之間點(diǎn)的對(duì)應(yīng)關(guān)系以計(jì)算最優(yōu)的變換關(guān)系。Besl等提出了基于迭代求解思想的迭代最近點(diǎn)(ICP)算法[5],對(duì)于解決剛體配準(zhǔn)問(wèn)題,該方法具有精度高和速度快的特點(diǎn),但它不能解決缺失點(diǎn)云配準(zhǔn)問(wèn)題且具有局部收斂性。為了解決缺失點(diǎn)云配準(zhǔn)問(wèn)題,Chetverikov等提出了裁剪ICP算法[6],該方法在原始ICP算法的基礎(chǔ)上,通過(guò)引入重疊百分比系數(shù)去除非重疊區(qū)域以準(zhǔn)確地計(jì)算雙視角配準(zhǔn)結(jié)果。為了解決局部收斂問(wèn)題,粒子濾波[7]和遺傳算法[8]均被用于搜索全局最優(yōu)的配準(zhǔn)結(jié)果,但這類方法的計(jì)算量較大。有的學(xué)者提出一些基于特征匹配的雙視角配準(zhǔn)方法[9-10],此類方法通過(guò)從待配準(zhǔn)的點(diǎn)云中提取并匹配特征,以快速計(jì)算雙視角點(diǎn)云之間的剛體變換關(guān)系。

給定多視角點(diǎn)云集,多視角點(diǎn)云配準(zhǔn)的目標(biāo)是計(jì)算各點(diǎn)云和基準(zhǔn)點(diǎn)云之間的剛體變換關(guān)系。與雙視角點(diǎn)云配準(zhǔn)問(wèn)題相比,多視角點(diǎn)云配準(zhǔn)問(wèn)題需要求解的參數(shù)較多。解決此問(wèn)題最簡(jiǎn)單的方法是順序配準(zhǔn)法[11],該方法通過(guò)不斷地將兩幀點(diǎn)云進(jìn)行配準(zhǔn)再合并以實(shí)現(xiàn)多視角配準(zhǔn)結(jié)果,此方法雖然簡(jiǎn)單但存在累積誤差問(wèn)題。為了消除累積誤差,Zhu等提出逐步求精的配準(zhǔn)方法,該方法順序遍歷基準(zhǔn)幀以外的各幀點(diǎn)云,并將所遍歷的點(diǎn)云與其他點(diǎn)云構(gòu)造的模型進(jìn)行雙視角配準(zhǔn),以修正單幀點(diǎn)云的多視角配準(zhǔn)參數(shù)[12];Govindu等提出了基于運(yùn)動(dòng)平均算法的多視角配準(zhǔn)方法[13],該方法將所有可獲得的雙視角配準(zhǔn)結(jié)果作為輸入,利用基于李群的運(yùn)動(dòng)平均算法計(jì)算多視角配準(zhǔn)參數(shù);Guo等給雙視角配準(zhǔn)結(jié)果賦予代表可靠度的權(quán)值,并提出了權(quán)重運(yùn)動(dòng)平均方法,以提高多視角配準(zhǔn)結(jié)果的精度[14];Arrigoni等提出了基于低秩稀疏矩陣分解的多視角配準(zhǔn)方法[15],該方法利用雙視角配準(zhǔn)結(jié)果構(gòu)造矩陣,并利用低秩稀疏矩陣分解方法近似得到低秩矩陣,以便恢復(fù)獲得多視角點(diǎn)云配準(zhǔn)結(jié)果;Georgios等將多視角配準(zhǔn)問(wèn)題轉(zhuǎn)化成聚類問(wèn)題,通過(guò)利用期望最大化(EM)算法估算高斯混合模型(GMM),以實(shí)現(xiàn)聚類及多視角配準(zhǔn)參數(shù)的計(jì)算[16],但該方法需要求解的參數(shù)較多,故算法的效率較低。

雖然前述方法可獲得較好的多視角點(diǎn)云配準(zhǔn)結(jié)果,但它們需要外界提供可靠的多視角配準(zhǔn)初始值。為了獲得多視角配準(zhǔn)的初始值,Daniel等提出了全自主的多視角點(diǎn)云配準(zhǔn)方法[17],該方法首先計(jì)算所有雙視角配準(zhǔn)結(jié)果,然后通過(guò)設(shè)計(jì)相容性準(zhǔn)則找出可靠的雙視角配準(zhǔn)結(jié)果以分析獲得多視角配準(zhǔn)結(jié)果,由于該方法需要計(jì)算點(diǎn)云集中所有雙視角點(diǎn)云的配準(zhǔn)結(jié)果,故效率較低。Zhu等提出了基于生成樹的多視角點(diǎn)云配準(zhǔn)方法[18],該方法基于廣度優(yōu)先的搜索方式,利用所設(shè)計(jì)的判定準(zhǔn)則尋找可靠的雙視角配準(zhǔn)結(jié)果創(chuàng)建生成樹以獲得多視角配準(zhǔn)結(jié)果,由于大部分雙視角點(diǎn)云之間的重疊百分比(點(diǎn)云重疊區(qū)域的點(diǎn)數(shù)占總點(diǎn)數(shù)的比值)較低,需進(jìn)行多次雙視角配準(zhǔn)才能創(chuàng)建出完整的生成樹,故基于生成樹方法的效率有待進(jìn)一步提高。

針對(duì)多視角點(diǎn)云配準(zhǔn)問(wèn)題,本文提出了基于特征匹配的多視角點(diǎn)云全局配準(zhǔn)方法。該方法選取可靠的特征描述子快速實(shí)現(xiàn)雙視角配準(zhǔn);設(shè)計(jì)合理的判定準(zhǔn)則判別雙視角配準(zhǔn)結(jié)果的可靠性;提出有效的模型擴(kuò)展方法,利用可靠雙視角配準(zhǔn)結(jié)果進(jìn)行點(diǎn)云模型的擴(kuò)展。通過(guò)采用交替地執(zhí)行雙視角配準(zhǔn)、配準(zhǔn)結(jié)果判別和模型擴(kuò)展的方式,實(shí)現(xiàn)無(wú)序多視角點(diǎn)云的全局配準(zhǔn)。

1 裁剪ICP算法

給定具有非重疊區(qū)域的雙視角點(diǎn)云,分別包含Np個(gè)點(diǎn)的數(shù)據(jù)點(diǎn)云P和Nq個(gè)點(diǎn)的模型點(diǎn)云Q其中pi表示P中的第i個(gè)點(diǎn),qj表示Q中第j個(gè)點(diǎn)。設(shè)Px表示重疊區(qū)域的數(shù)據(jù)點(diǎn)云上的點(diǎn)所組成的子集,重疊百分比x定義為和Np的比值,其中表示子集Px所包含的點(diǎn)數(shù)。定義裁剪均方誤差

(1)

式中:R與t表示剛體變換中的旋轉(zhuǎn)矩陣和平移變量;(pi,qc(i))表示模型點(diǎn)云和數(shù)據(jù)點(diǎn)云在重疊區(qū)域的具有對(duì)應(yīng)關(guān)系的點(diǎn)對(duì)。雙視角配準(zhǔn)問(wèn)題可表示為如下的最小化問(wèn)題

(2)

式中λ是預(yù)設(shè)的參數(shù),λ=2。

給定初始剛體變換(R0,t0),裁剪ICP算法采用交替迭代的思想求解最優(yōu)的配準(zhǔn)參數(shù),且第k次迭代包含以下步驟。

步驟1基于當(dāng)前剛體變換,建立點(diǎn)的對(duì)應(yīng)關(guān)系

i=1,2,…,Np

(3)

步驟2根據(jù)當(dāng)前點(diǎn)對(duì)關(guān)系,計(jì)算第k次迭代中的重疊百分比xk和子集Px

(4)

步驟3更新剛體變換關(guān)系

(5)

迭代執(zhí)行步驟1～3,直到迭代步數(shù)達(dá)到預(yù)設(shè)的上限K或|ψk-ψk-1|<ε(ε為任意小的正數(shù)),即可停止迭代輸出最優(yōu)的配準(zhǔn)參數(shù)(R,t)。與原始ICP算法相似,裁剪ICP算法也具有局部收斂性,但是為獲得可靠的雙視角配準(zhǔn)結(jié)果,需要外界提供較好的配準(zhǔn)初始值。

圖1 無(wú)序多視角點(diǎn)云配準(zhǔn)方法框架圖

2 無(wú)序多視角點(diǎn)云全局配準(zhǔn)

為了實(shí)現(xiàn)無(wú)序多視角點(diǎn)云的全局配準(zhǔn),本文提出了如圖1所示的解決方法。該方法選定基準(zhǔn)幀作為初始模型點(diǎn)云,順序遍歷點(diǎn)云集里的每一幀點(diǎn)云,然后利用雙視角配準(zhǔn)方法將所遍歷的點(diǎn)云與模型點(diǎn)云進(jìn)行配準(zhǔn),通過(guò)設(shè)計(jì)有效的判定準(zhǔn)則,將判別出的可靠雙視角配準(zhǔn)結(jié)果用于模型點(diǎn)云擴(kuò)展,直到全部點(diǎn)云被加入擴(kuò)展模型中。

2.1 基于特征匹配的雙視角配準(zhǔn)

為了解決雙視角配準(zhǔn)問(wèn)題,已有各種局部收斂的方法。在給定配準(zhǔn)初始值時(shí),這些方法可以計(jì)算出兩個(gè)點(diǎn)云之間最優(yōu)的剛體變換。然而,在無(wú)序多視角點(diǎn)云配準(zhǔn)問(wèn)題中,雙視角配準(zhǔn)初值是未知的,因此需要可實(shí)現(xiàn)全局配準(zhǔn)的雙視角配準(zhǔn)方法。

Lei等提出了基于特征匹配的雙視角全局配準(zhǔn)方法[10],該方法先對(duì)原始點(diǎn)云進(jìn)行降采樣,以降采樣獲得的每個(gè)點(diǎn)為中心定義4個(gè)具有不同半徑的圓球,接著利用球內(nèi)所包含的原始點(diǎn)云,計(jì)算該點(diǎn)的4組法向量和特征值向量,并用9維的特征值差向量D和12維的法向量N作為特征描述子。由于特征值差向量具有旋轉(zhuǎn)不變形性,可基于歐氏距離最近的原則建立簡(jiǎn)單的特征對(duì)應(yīng)關(guān)系,隨后將每個(gè)特征對(duì)作為種子匹配對(duì),通過(guò)檢驗(yàn)其他特征點(diǎn)與種子特征點(diǎn)之間的距離差和法向量夾角,選取兼容的特征匹配對(duì)形成特征匹配對(duì)集。為了消除錯(cuò)誤的匹配對(duì),可進(jìn)一步利用隨機(jī)一致性算法對(duì)匹配對(duì)集中的特征對(duì)進(jìn)行篩選,選出可靠特征對(duì)確定雙視角配準(zhǔn)結(jié)果。由于種子匹配對(duì)不一定可靠,因此需要遍歷全部種子匹配對(duì),如果利用該種子點(diǎn)匹配對(duì)所找的相容特征匹配對(duì)數(shù)較少,則直接丟棄,否則需要采用隨機(jī)一致性算法進(jìn)行后續(xù)處理以確定雙視角配準(zhǔn)結(jié)果。最后,比較所有配準(zhǔn)結(jié)果所對(duì)應(yīng)的裁剪均方誤差選出最可靠的雙視角配準(zhǔn)結(jié)果。

與原始點(diǎn)云相比,降采樣后的特征點(diǎn)數(shù)較少,根據(jù)特征點(diǎn)所計(jì)算出的雙視角配準(zhǔn)結(jié)果精度有限。為提高配準(zhǔn)結(jié)果精度,本文利用裁剪ICP算法對(duì)基于特征點(diǎn)匹配所求出的雙視角配準(zhǔn)結(jié)果進(jìn)行了修正,以獲得更好的雙視角配準(zhǔn)結(jié)果。

2.2 配準(zhǔn)結(jié)果評(píng)判的設(shè)計(jì)

為了獲得精確的擴(kuò)展模型,需要選取可靠的雙視角配準(zhǔn)結(jié)果,為此必須設(shè)計(jì)有效的判定準(zhǔn)則。

在多視角點(diǎn)云配準(zhǔn)問(wèn)題中,每對(duì)點(diǎn)云之間存在非重疊區(qū)域甚至無(wú)重疊區(qū)域。對(duì)于重疊百分比較高的雙視角點(diǎn)云,裁剪ICP算法可準(zhǔn)確地找出兩點(diǎn)云之間的重疊區(qū)域,并計(jì)算出可靠的配準(zhǔn)參數(shù);對(duì)于具有低重疊百分比或無(wú)重疊區(qū)域的雙視角點(diǎn)云,裁剪ICP算法會(huì)找出虛假的重疊區(qū)域,并計(jì)算出不可靠的配準(zhǔn)參數(shù)。圖2給出了具有不同重疊百分比的雙視角點(diǎn)云配準(zhǔn)結(jié)果,其中圖2a所示的雙視角點(diǎn)云具有較高的重疊百分比,圖2b所示的雙視角點(diǎn)云分別來(lái)源于兔子模型的正反面,具有較低的重疊百分比。由圖2可知,可靠的配準(zhǔn)結(jié)果使得位于重疊區(qū)域的點(diǎn)對(duì)誤差距離較小,而不可靠的配準(zhǔn)結(jié)果造成虛假重疊區(qū)域的點(diǎn)對(duì)誤差距離較大,因此可將裁剪ICP算法所確定的重疊區(qū)域內(nèi)的點(diǎn)對(duì)誤差,即裁剪均方誤差E,作為判定配準(zhǔn)結(jié)果可靠性的依據(jù)。

(a)可靠的配準(zhǔn)結(jié)果 (b)不可靠的配準(zhǔn)結(jié)果

對(duì)于相同的數(shù)據(jù)點(diǎn)云和配準(zhǔn)結(jié)果,裁剪均方誤差會(huì)受模型點(diǎn)云點(diǎn)密度的影響。圖3給出了模型點(diǎn)云點(diǎn)密度對(duì)裁剪均方誤差的影響。由圖3可知,低密度的模型點(diǎn)云將導(dǎo)致裁剪均方誤差增大,高密度的模型點(diǎn)云有利于降低裁剪均方誤差。根據(jù)裁剪均方誤差受模型點(diǎn)云點(diǎn)密度之間影響的現(xiàn)象,本文給出如下雙視角配準(zhǔn)結(jié)果的判定準(zhǔn)則

(c) 可靠的配準(zhǔn)結(jié)果 (d) 不可靠的配準(zhǔn)結(jié)果的橫截面圖 的橫截面圖圖2 雙視角配準(zhǔn)結(jié)果的橫截面圖

(6)

式中:E為雙視角配準(zhǔn)結(jié)果所對(duì)應(yīng)的裁剪均方誤差;dM為模型點(diǎn)云的平均密度;a為設(shè)定的常數(shù)。如果E滿足式(6),則可判定雙視角配準(zhǔn)結(jié)果較可靠,否則為不可靠。

為了改善判定準(zhǔn)則,當(dāng)獲得一部分可靠的多視角配準(zhǔn)結(jié)果后,可將這些配準(zhǔn)結(jié)果所對(duì)應(yīng)的均方誤差的均值加入判定準(zhǔn)則,即

E≤max(adM,bmE)

(7)

式中mE表示可靠配準(zhǔn)結(jié)果裁剪均方誤差E的平均值。參數(shù)a和b的選取將在實(shí)驗(yàn)部分進(jìn)行討論。

(a)低分辨率模型

(b)高分辨率模型圖3 模型點(diǎn)云的分辨率對(duì)裁剪均方誤差的影響

2.3 點(diǎn)云模型的擴(kuò)展

根據(jù)本文所設(shè)計(jì)的判定準(zhǔn)則可判別雙視角配準(zhǔn)結(jié)果是否可靠,對(duì)于可靠的雙視角配準(zhǔn)結(jié)果則需要進(jìn)行模型擴(kuò)展。由于模型形狀的點(diǎn)云密度會(huì)影響后續(xù)雙視角配準(zhǔn)的裁剪均方誤差,為了保證判定準(zhǔn)則的有效性,需要盡量保持模型點(diǎn)云密度的恒定性。為此,本文設(shè)計(jì)如圖4所示的模型擴(kuò)展方法。

利用雙視角結(jié)果(R,t)將數(shù)據(jù)點(diǎn)云進(jìn)行變換,以獲得變換后的數(shù)據(jù)點(diǎn)云P′

P′{Rpi+t

(8)

(a)擴(kuò)展前建立的點(diǎn)對(duì)關(guān)系

(b)模型擴(kuò)展結(jié)果圖4 模型擴(kuò)展方法示意圖

可將模型點(diǎn)云和變換后的數(shù)據(jù)點(diǎn)云分解為兩部分

(9)

Q′=A∪F∪B

(10)

(11)

模型擴(kuò)展時(shí),對(duì)均勻采樣所獲得的特征同樣需要進(jìn)行擴(kuò)展。本文所采用的特征包含特征點(diǎn)和特征描述兩部分,其中特征描述分為法向量N和特征值差向量D兩部分。在進(jìn)行特征擴(kuò)展時(shí),可利用裁剪ICP算法建立重疊區(qū)域特征點(diǎn)的對(duì)應(yīng)關(guān)系,并采用處理點(diǎn)云的方式確定新特征的特征點(diǎn)。由于特征值差向量具有旋轉(zhuǎn)不變性,故新特征值差向量可由對(duì)應(yīng)特征對(duì)的特征值差向量的均值所代替,即

(12)

而法向量不具有旋轉(zhuǎn)不變形性,故在求平均法向量前,需要對(duì)數(shù)據(jù)點(diǎn)云中特征點(diǎn)的法向量進(jìn)行旋轉(zhuǎn),然后再求平均

(13)

其中旋轉(zhuǎn)矩陣R由雙視角配準(zhǔn)結(jié)果所確定。

與直接合并法相比,本文所設(shè)計(jì)的模型擴(kuò)展法可有效地減少重疊區(qū)域的點(diǎn)云和特征的數(shù)目,從而有利于提高后續(xù)配準(zhǔn)的效率。

2.4 多視角點(diǎn)云配準(zhǔn)算法的實(shí)現(xiàn)

根據(jù)上述描述,結(jié)合圖1的循環(huán)過(guò)程,可給出如下無(wú)序多視角點(diǎn)云全局配準(zhǔn)方法。

步驟1從點(diǎn)云集里隨機(jī)選出基準(zhǔn)幀作為模型點(diǎn)云。

步驟2順序遍歷點(diǎn)云集的剩余點(diǎn)云,如點(diǎn)云集非空則轉(zhuǎn)至步驟3;否則,轉(zhuǎn)至步驟5。

步驟3視所遍歷點(diǎn)云Pi為數(shù)據(jù)點(diǎn)云,利用2.1節(jié)中的方法計(jì)算(Ri,ti)和Ex,i。

步驟4根據(jù)式(7)判定(Ri,ti)的可靠性,如滿足條件,轉(zhuǎn)至步驟5;否則,轉(zhuǎn)至步驟2。

步驟5從點(diǎn)云集里取出Pi,利用2.3節(jié)中的方法進(jìn)行模型擴(kuò)展,并更新平均值mE。

給定無(wú)序多視角點(diǎn)云集,利用本文方法可快速實(shí)現(xiàn)多視角點(diǎn)云配準(zhǔn)。一般情況下,默認(rèn)將點(diǎn)云集里的第一幀選為基準(zhǔn)幀。

3 多視角點(diǎn)云配準(zhǔn)實(shí)驗(yàn)結(jié)果

3.1 參數(shù)選取

本文方法所包含的兩個(gè)自由參數(shù)α和b的取值將影響本文方法的性能。為了選取合理的值,在Bunny和Armadillo數(shù)據(jù)集上對(duì)本文方法進(jìn)行了測(cè)試,采用人工的方式挑選出了可靠的雙視角配準(zhǔn)結(jié)果,并在圖5中記錄了每次獲得可靠雙視角配準(zhǔn)結(jié)果所對(duì)應(yīng)的裁剪均方誤差E和模型點(diǎn)云的平均密度dM。

(a)Bunny數(shù)據(jù)集

(b)Armadillo數(shù)據(jù)集圖5 可靠雙視角配準(zhǔn)結(jié)果所對(duì)應(yīng)的E和dM

如圖5所示,對(duì)于可靠的雙視角配準(zhǔn)結(jié)果,點(diǎn)云密度dM一般小于裁剪均方誤差E,且可靠雙視角配準(zhǔn)結(jié)果所對(duì)應(yīng)的E波動(dòng)比較大,為了確保配準(zhǔn)結(jié)果判定準(zhǔn)則的有效性,a和b的取值應(yīng)該大于1。理論上,a和b越大越能確保挑選出全部可靠的雙視角配準(zhǔn)結(jié)果,但過(guò)大的a和b會(huì)引入不可靠的雙視角配準(zhǔn)結(jié)果,從而導(dǎo)致多視角點(diǎn)云配準(zhǔn)結(jié)果的失敗。通常情況下,不可靠的雙視角點(diǎn)云配準(zhǔn)結(jié)果是由低重疊百分比而導(dǎo)致的。如將a和b設(shè)置得較小,本文方法會(huì)將一部分點(diǎn)云的雙視角配準(zhǔn)結(jié)果誤判為不可靠,但隨著模型點(diǎn)云的不斷擴(kuò)展,待配準(zhǔn)點(diǎn)云的重疊百分比將不斷增加,前一次判定為配準(zhǔn)失敗的點(diǎn)云,下一次配準(zhǔn)所獲得的E將會(huì)變小,從而實(shí)現(xiàn)正確的判定,即較小的a和b僅降低了本文方法的效率,但較大的a和b值將降低本文方法的可靠性。鑒于此,可將參數(shù)a和b分別設(shè)置為a=2和b=1.5,以確保算法的可靠性。

3.2 配準(zhǔn)算法的精度和效率

給定一組無(wú)序多視角點(diǎn)云,可以利用不同的多視角配準(zhǔn)方法進(jìn)行配準(zhǔn)并進(jìn)行性能對(duì)比。圖6給出了不同方法在各個(gè)測(cè)試數(shù)據(jù)集上的效率對(duì)比結(jié)果,表1給出了不同方法在各個(gè)測(cè)試數(shù)據(jù)集上的精度對(duì)比結(jié)果,其中黑體數(shù)值代表最佳結(jié)果。為了進(jìn)一步對(duì)比各種配準(zhǔn)方法的精度,圖7以橫截面形式給出了各種方法關(guān)于Dragon和Buddha數(shù)據(jù)集的配準(zhǔn)結(jié)果。

(a)雙視角配準(zhǔn)次數(shù)

(b)程序運(yùn)行時(shí)間圖6 不同方法在4個(gè)測(cè)試數(shù)據(jù)集上的效率對(duì)比結(jié)果

由圖6a可知,本文方法需要執(zhí)行的雙視角配準(zhǔn)次數(shù)最少,算法效率最高;SurfC方法需要執(zhí)行的雙視角配準(zhǔn)次數(shù)最多,算法效率最低。為了實(shí)現(xiàn)多視角全局配準(zhǔn),SurfC方法對(duì)點(diǎn)云集里所有的點(diǎn)云對(duì)進(jìn)行雙視角配準(zhǔn),并利用兼容性檢測(cè)出可靠的雙視角配準(zhǔn)結(jié)果,以分析多視角配準(zhǔn)結(jié)果。由于該方法需要執(zhí)行雙視角配準(zhǔn)的次數(shù)最多,因此程序運(yùn)行時(shí)間最長(zhǎng)。SpanT方法采用深度優(yōu)先的方式,通過(guò)執(zhí)行雙視角配準(zhǔn)和尋找可靠的雙視角配準(zhǔn)結(jié)果創(chuàng)建完整的生成樹。通常,雙視角點(diǎn)云的重疊百分比影響其配準(zhǔn)結(jié)果的可靠性,高重疊百分比的點(diǎn)云更容易獲得可靠的配準(zhǔn)結(jié)果。

在無(wú)序多視角點(diǎn)云集里,只有一部分點(diǎn)云具有高重疊百分比。為了創(chuàng)建完整的生成樹,SpanT方法需要執(zhí)行的雙視角配準(zhǔn)的次數(shù)較多,算法的效率較差。除執(zhí)行雙視角配準(zhǔn)和尋找可靠雙視角配準(zhǔn)結(jié)果之外,本文方法引入了模型點(diǎn)云擴(kuò)展步驟,利用可靠雙視角配準(zhǔn)結(jié)果進(jìn)行模型擴(kuò)展,可擴(kuò)大模型點(diǎn)云所覆蓋的區(qū)域,增加待配準(zhǔn)雙視角點(diǎn)云的重疊百分比,以減少雙視角點(diǎn)云配準(zhǔn)的執(zhí)行次數(shù),因此本文方法具有較高的效率。

由表1可知,本文方法配準(zhǔn)精度最高,另外兩種方法的精度較低。由于3種方法都采用雙視角配準(zhǔn)方法實(shí)現(xiàn)多視角配準(zhǔn),故均面臨累積誤差問(wèn)題。其中SpanT和SurfC方法直接利用點(diǎn)云集里的原始點(diǎn)云對(duì)進(jìn)行配準(zhǔn),通過(guò)不同的策略選取N-1組可靠的雙視角配準(zhǔn)結(jié)果計(jì)算多視角配準(zhǔn)參數(shù)。通常情況下,雙視角配準(zhǔn)結(jié)果的精度受雙視角點(diǎn)云重疊百分比的影響,且重疊百分比越低,配準(zhǔn)精度越差。在多視角點(diǎn)云集中,許多原始點(diǎn)云對(duì)之間的重疊區(qū)域較少,對(duì)應(yīng)的雙視角配準(zhǔn)結(jié)果精度有限,隨著點(diǎn)云數(shù)的增加,多視角配準(zhǔn)結(jié)果的累計(jì)誤差將不斷增大,從而導(dǎo)致SpanT和SurfC方法配準(zhǔn)結(jié)果的精度變低。雖然本文方法也利用雙視角配準(zhǔn)結(jié)果實(shí)現(xiàn)多視角配準(zhǔn),但待配準(zhǔn)的模型點(diǎn)云并不是點(diǎn)云集里的原始點(diǎn)云,而是不斷擴(kuò)展的點(diǎn)云。與原始點(diǎn)云相比,擴(kuò)展后的模型點(diǎn)云可增加待配準(zhǔn)的雙視角點(diǎn)云重疊百分比,提高雙視角配準(zhǔn)結(jié)果的精度,從而減少多視角配準(zhǔn)結(jié)果的累積誤差,因此本文方法可獲得最高精度的多視角配準(zhǔn)結(jié)果。

表1 不同方法在各個(gè)測(cè)試數(shù)據(jù)集上的誤差對(duì)比結(jié)果

(a)輸入數(shù)據(jù)(b)重建模型(c)SurfC方法(d)SpanT方法(e)本文方法圖7 以橫截面形式表示的配準(zhǔn)結(jié)果對(duì)比

3.3 配準(zhǔn)算法的魯棒性

以Bunny數(shù)據(jù)集為實(shí)驗(yàn)對(duì)象,通過(guò)調(diào)整點(diǎn)云順序測(cè)試所本文提出的多視角配準(zhǔn)方法的可靠性,并與另外兩種方法進(jìn)行對(duì)比。表2給出了不同順序下的Bunny數(shù)據(jù)集的配準(zhǔn)結(jié)果。由表2可知,3種多視角配準(zhǔn)方法對(duì)于點(diǎn)云的順序都不敏感,即具有較好的可靠性。為了實(shí)現(xiàn)多視角配準(zhǔn),3種方法都設(shè)計(jì)了相應(yīng)的準(zhǔn)則,以確定可靠的雙視角配準(zhǔn)結(jié)果計(jì)算多視角配準(zhǔn)參數(shù)。即使調(diào)整了點(diǎn)云順序,這些方法仍可以選出可靠的雙視角配準(zhǔn)結(jié)果以實(shí)現(xiàn)多視角配準(zhǔn)。與其他兩種方法相似,本文方法對(duì)點(diǎn)云順序具有較好的可靠性,是最佳的結(jié)果。

表2 不同方法關(guān)于Bunny數(shù)據(jù)集在不同順序下的測(cè)試結(jié)果

4 結(jié) 論

針對(duì)無(wú)序多視角點(diǎn)云的配準(zhǔn)問(wèn)題,本文提出了基于特征匹配的全局配準(zhǔn)方法,采用合理的特征描述算子實(shí)現(xiàn)雙視角配準(zhǔn),并設(shè)計(jì)了判斷雙視角配準(zhǔn)結(jié)果可靠性的準(zhǔn)則,挑選出可靠的雙視角配準(zhǔn)結(jié)果,用于擴(kuò)展模型點(diǎn)云。為實(shí)現(xiàn)多視角配準(zhǔn),該方法需要交替地執(zhí)行雙視角配準(zhǔn)、配準(zhǔn)結(jié)果判別和模型點(diǎn)云擴(kuò)展,直到所有點(diǎn)云被擴(kuò)展至模型點(diǎn)云。在斯坦福大學(xué)圖形學(xué)實(shí)驗(yàn)室的公開數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明,與現(xiàn)有的多視角配準(zhǔn)方法相比,本文方法具有較高的精度和效率。