基于改進(jìn)RANSAC的點(diǎn)云關(guān)鍵點(diǎn)匹配

趙 凱， 朱 愿， 謝 楓

(1 陸軍軍事交通學(xué)院， 天津 300161； 2 軍事交通運(yùn)輸研究所， 天津 300161)

引言

隨機(jī)抽樣一致性(RANdom SAmple Consensus, RANSAC)算法是目前熱門流行的特征點(diǎn)匹配算法之一[1]，該算法是由Fischler 和 Bolles 于 1981 年研發(fā)提出的一種魯棒性模型參數(shù)估計(jì)算法[2]。由于其表現(xiàn)出結(jié)構(gòu)簡單及方法的魯棒性高等優(yōu)點(diǎn)，已廣泛地應(yīng)用于解決各個(gè)研究領(lǐng)域的模型參數(shù)估計(jì)問題。Chen等人[3]首次將 RANSAC 算法應(yīng)用于三維點(diǎn)云數(shù)據(jù)的配準(zhǔn)中，該算法在處理重疊部分較小的點(diǎn)云數(shù)據(jù)集時(shí)，具有一定的魯棒性。然而，當(dāng)點(diǎn)云配準(zhǔn)問題中外點(diǎn)比例較高時(shí)，難以兼顧效率、精度和魯棒性。為此，本文對標(biāo)準(zhǔn)RANSAC算法加以改進(jìn)，提高了算法的執(zhí)行性能和適應(yīng)能力。

1 標(biāo)準(zhǔn)RANSAC算法

RANSAC算法是基于假設(shè)和檢驗(yàn)的框架來實(shí)現(xiàn)的。首先從輸入的數(shù)據(jù)點(diǎn)集中隨機(jī)地選擇一個(gè)可保證模型估計(jì)的最小數(shù)量的點(diǎn)集，并用該數(shù)據(jù)點(diǎn)集來估計(jì)模型的參數(shù)。然后，用點(diǎn)集中的所有數(shù)據(jù)對模型進(jìn)行檢驗(yàn)，進(jìn)而確定模型的支持度、即適應(yīng)該模型的數(shù)據(jù)點(diǎn)的數(shù)量，以此來評估該模型的正確程度。通過不斷地執(zhí)行假設(shè)與檢驗(yàn)的循環(huán)，期望獲得一個(gè)具有全局最優(yōu)模型估計(jì)參數(shù)。

假設(shè)需要將源點(diǎn)云數(shù)據(jù)集U，配準(zhǔn)到目標(biāo)點(diǎn)云數(shù)據(jù)集V所在的坐標(biāo)系下，基于RANSAC的配準(zhǔn)算法的步驟可設(shè)計(jì)分述如下：

(1)從n對預(yù)匹配的點(diǎn)對{(a1,b1), (a2,b2),...,(an,bn)}中隨機(jī)選取3對關(guān)鍵點(diǎn)點(diǎn)對作為初始匹配點(diǎn)對，求解位姿變換矩陣T。

(2)計(jì)算源點(diǎn)云中剩余n-3個(gè)關(guān)鍵點(diǎn)ai(1,2,...,n-3)經(jīng)過矩陣T變換后得到的對應(yīng)點(diǎn)Tai，并計(jì)算這些點(diǎn)與原先配對的n-3個(gè)關(guān)鍵點(diǎn)bi(1,2,...,n-3)之間的歐氏距離di，其計(jì)算公式如下：

di=‖bi,Tai‖

(1)

若di<ε(ε表示距離閾值)，則該關(guān)鍵點(diǎn)對(ai,bi)為內(nèi)點(diǎn)，即正確的匹配點(diǎn)對，反之則為外點(diǎn)。

(3)比較當(dāng)前內(nèi)點(diǎn)數(shù)目，若大于當(dāng)前最佳內(nèi)點(diǎn)數(shù)Ni(設(shè)初始最佳內(nèi)點(diǎn)數(shù)Ni為0)，則將當(dāng)前變換矩陣T計(jì)作當(dāng)前最佳矩陣估計(jì)，并更新最大內(nèi)點(diǎn)數(shù)Ni值。

(4)跳轉(zhuǎn)至步驟(1)，在匹配點(diǎn)對中重新隨機(jī)抽取3組點(diǎn)對。

(5) 經(jīng)過若干次隨機(jī)抽樣計(jì)算后(達(dá)到最大迭代次數(shù)或是內(nèi)點(diǎn)數(shù)量基本保持不變)，比較各次所得的內(nèi)點(diǎn)個(gè)數(shù)，最大內(nèi)點(diǎn)數(shù)Ni所對應(yīng)的變換矩陣T就是需要求取的兩幀點(diǎn)云之間的位姿變換關(guān)系。

綜合以上步驟，即可迭代計(jì)算出歐式變換矩陣T，從而實(shí)現(xiàn)源點(diǎn)云U到目標(biāo)點(diǎn)云V的配準(zhǔn)。通常情況下，RANSAC 算法可以通過不斷迭代的方式來得到一組全局最優(yōu)解。但是隨著測試點(diǎn)中外點(diǎn)比例的增加，過程中需要的迭代次數(shù)將呈指數(shù)增長，大大地增加了計(jì)算成本。

2 改進(jìn)型RANSAC算法

為了提高 RANSAC 算法的效率及性能，本文提出一種基于樣本內(nèi)在約束的最優(yōu)RANSAC算法。該算法在隨機(jī)抽樣階段，以樣本之間存在的內(nèi)在約束作為先驗(yàn)信息來引導(dǎo)算法的抽樣過程，以此來提高算法的抽樣效率；在模型檢驗(yàn)之前增加了預(yù)檢驗(yàn)步驟, 可以排除大部分具有明顯偏差的模型, 避免不必要的模型參數(shù)檢驗(yàn)計(jì)算；當(dāng)達(dá)到停止條件退出循環(huán)后，借鑒O-RANSAC 算法[4]的思想，再依據(jù)一個(gè)更小的誤差閾值, 采取逐步移除誤差最大的數(shù)據(jù)的方法對準(zhǔn)最優(yōu)內(nèi)點(diǎn)集進(jìn)行提純優(yōu)化; 最后用提純得到的最優(yōu)內(nèi)點(diǎn)集來計(jì)算模型的參數(shù)。算法的整體設(shè)計(jì)流程如圖1所示。

該算法主要從3個(gè)方面對標(biāo)準(zhǔn)RANSAC算法做出改進(jìn)。研究將對此展開探討論述如下。

2.1 基于樣本內(nèi)在約束的隨機(jī)抽樣

RANSAC 算法采取獨(dú)立隨機(jī)方式進(jìn)行抽樣，沒有利用數(shù)據(jù)的先驗(yàn)知識來引導(dǎo)抽樣過程, 因而抽樣效率較低。在點(diǎn)云的配準(zhǔn)問題中，需要在兩幀點(diǎn)云數(shù)據(jù)的重疊區(qū)域，找到至少3對對應(yīng)關(guān)鍵點(diǎn)，且要求各點(diǎn)云中的3個(gè)關(guān)鍵點(diǎn)不能共線，才能完成剛體變換矩陣參數(shù)的估計(jì)。考慮到關(guān)鍵點(diǎn)之間的空間位置關(guān)系不會隨著點(diǎn)云間的剛體變換而改變，因此抽樣所得的最小樣本集也必須滿足這些約束，同時(shí)這也是正確估計(jì)模型參數(shù)的必要條件。改進(jìn)RANSAC算法通過判斷關(guān)鍵點(diǎn)之間的空間位置關(guān)系是否滿足相應(yīng)條件來引導(dǎo)算法的抽樣過程，以此提高抽樣效率。

圖1 改進(jìn)RANSAC算法框圖

假設(shè)，從待匹配集合M中抽取了3對關(guān)鍵點(diǎn)點(diǎn)對{(a1,b1),(a2,b2),(a3,b3)}，其中{a1,a2,a3}來自于源點(diǎn)云，{b1,b2,b3}分別是在目標(biāo)點(diǎn)云中的對應(yīng)點(diǎn)。且這3對關(guān)鍵點(diǎn)均來自兩幀點(diǎn)云的重疊區(qū)域，那么其中的各項(xiàng)數(shù)值將滿足以下約束：

(2)

(3)

將式(2)稱為距離約束，將式(3)稱為角度約束。在抽樣階段，若所抽取的樣本滿足這2種約束，則進(jìn)行后續(xù)處理。反之，將轉(zhuǎn)入重新抽樣。

2.2 預(yù)檢驗(yàn)

由于大部分模型參數(shù)都受到外點(diǎn)的影響，此時(shí)只需從原始數(shù)據(jù)中隨機(jī)選取少量數(shù)據(jù)就可以用較少的計(jì)算代價(jià)去除大部分質(zhì)量不高的模型，這就可以有效減少算法的計(jì)算時(shí)間。預(yù)檢驗(yàn)過程的主要步驟可表述如下。

(1)從集合M中隨機(jī)選取一個(gè)包含ξn對關(guān)鍵點(diǎn)的子集M′。

(2) 用M′中的所有元組對模型參數(shù)進(jìn)行預(yù)檢驗(yàn)。

(3)若M′中包含的ξn個(gè)關(guān)鍵點(diǎn)對全都符合所估計(jì)的模型參數(shù)，將通過預(yù)檢驗(yàn)。反之，則拒絕該模型。

其中，ξ為系數(shù)，通常取值為ξ∈[0.1,0.3]。可以將ξ理解為抽樣估計(jì)的模型參數(shù)所能接受的內(nèi)點(diǎn)率。只有潛在的準(zhǔn)確模型估計(jì), 才能通過預(yù)檢驗(yàn)并在數(shù)據(jù)集D上接受所有數(shù)據(jù)的檢驗(yàn)。

2.3 準(zhǔn)最優(yōu)內(nèi)點(diǎn)集提純

為了對 RANSAC 算法精度進(jìn)行優(yōu)化，采用減小距離閾值ε的方式對準(zhǔn)最優(yōu)內(nèi)點(diǎn)集進(jìn)行提純。在達(dá)到停止條件退出循環(huán)后，依據(jù)預(yù)先設(shè)置的距離閾值ε可以得到一個(gè)潛在的最優(yōu)內(nèi)點(diǎn)集，稱其為準(zhǔn)最優(yōu)內(nèi)點(diǎn)集。然而由于閾值ε的存在，根據(jù)準(zhǔn)最優(yōu)內(nèi)點(diǎn)集計(jì)算得到的位姿變換矩陣T并不是最優(yōu)的，該內(nèi)點(diǎn)集中仍然包含了一些需要剔除的外點(diǎn)。因此可以再次采用一個(gè)較小的閾值ε′對準(zhǔn)內(nèi)點(diǎn)集進(jìn)行提純，從而得到最優(yōu)內(nèi)點(diǎn)集。

核心思想是：通過迭代來逐一檢驗(yàn)并移除外點(diǎn)。每次迭代，利用現(xiàn)有模型計(jì)算全部準(zhǔn)內(nèi)點(diǎn)的誤差, 然后從準(zhǔn)內(nèi)點(diǎn)集中移除一項(xiàng)誤差最大的數(shù)據(jù), 再利用新的準(zhǔn)內(nèi)點(diǎn)集計(jì)算模型參數(shù)。重復(fù)這一過程, 直到剩余內(nèi)點(diǎn)的誤差全部處于閾值ε′范圍內(nèi)。分析可知,這時(shí)的內(nèi)點(diǎn)率遠(yuǎn)遠(yuǎn)高于集合M中的內(nèi)點(diǎn)率，因此僅需要很少的迭代次數(shù)就能找到最終的最優(yōu)內(nèi)點(diǎn)集并得到最終的最優(yōu)模型。

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

為了驗(yàn)證本文提出方法的有效性和魯棒性，對模擬數(shù)據(jù)和真實(shí)點(diǎn)云數(shù)據(jù)分別進(jìn)行實(shí)驗(yàn)，同時(shí)將本文算法與RANSAC算法的計(jì)算精度和計(jì)算耗時(shí)作以實(shí)驗(yàn)對比分析。采用Velodyne HDL-64E型64線激光雷達(dá)所采集的城市復(fù)雜動(dòng)態(tài)環(huán)境下的三維點(diǎn)云數(shù)據(jù)為真實(shí)點(diǎn)云數(shù)據(jù)。實(shí)驗(yàn)平臺為Intel(R) Core(TM) i7-6700 CPU @ 3.40 GHz，16 GB ARM，Ubuntu 16.04操作系統(tǒng)，Qt Creator 5.7開發(fā)環(huán)境，開發(fā)語言為C++。

研究仿真中首先使用IRON算法對相鄰點(diǎn)云幀進(jìn)行特征點(diǎn)檢測，并使用匹配算法對特征點(diǎn)進(jìn)行匹配；然后分別利用本文算法和RANSAC算法對匹配點(diǎn)對進(jìn)行篩選，在此基礎(chǔ)上得到了研究選用的抽樣集合和參數(shù)模型；最后將歐氏適應(yīng)度值(Euclidean fitness score)[5]作為點(diǎn)云匹配準(zhǔn)確度的衡量指標(biāo)，歐氏適應(yīng)度值是參與匹配的兩幀點(diǎn)云中各個(gè)對應(yīng)點(diǎn)對之間歐式距離的均方差。設(shè)置預(yù)檢驗(yàn)樣本數(shù)為n=10。仿真研究的結(jié)果分析如下。

(1)2種算法計(jì)算精度對比。連續(xù)100幀點(diǎn)云幀間匹配的歐式適應(yīng)度可如圖2所示。由圖2可以看出本文算法的匹配歐式適應(yīng)度低于傳統(tǒng)的RANSAC算法，即利用本文算法進(jìn)行幀間配準(zhǔn)時(shí)的精度高于使用RANSAC算法。2種配準(zhǔn)算法的實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)可見表1。實(shí)驗(yàn)結(jié)果取100次計(jì)算結(jié)果的平均值。內(nèi)點(diǎn)數(shù)為正確的特征點(diǎn)匹配點(diǎn)對，內(nèi)點(diǎn)比率為內(nèi)點(diǎn)數(shù)占特征點(diǎn)數(shù)的比率。實(shí)驗(yàn)結(jié)果表明，本文算法在進(jìn)行特征匹配點(diǎn)點(diǎn)對篩選時(shí)優(yōu)于RANSAC算法，由此即驗(yàn)證了本文算法的計(jì)算精度高于RANSAC算法。

圖2 2種算法計(jì)算精度對比

Fig.2Comparisonofcalculationaccuracybetweenthetwoalgorithms

表1 2種算法匹配結(jié)果對比

(2)2種算法的計(jì)算時(shí)間對比。100幀連續(xù)點(diǎn)云的匹配耗時(shí)，也就是2種算法的計(jì)算時(shí)間對比如圖3所示。由圖3可以看出本文算法所需的計(jì)算時(shí)間優(yōu)于RANSAC算法，究其原因即在于本文算法在傳統(tǒng)RANSAC算法的基礎(chǔ)上加入了基于樣本內(nèi)在約束的隨機(jī)抽樣，可以有效地規(guī)避錯(cuò)誤的抽樣樣本所帶來的計(jì)算耗時(shí)；另外，預(yù)檢驗(yàn)過程只需從原始數(shù)據(jù)中隨機(jī)選取少量數(shù)據(jù)就可以用較少的計(jì)算代價(jià)排除大部分質(zhì)量不高的模型，這2方面因素的綜合作用就大大減少了本文改進(jìn)RANSAC算法的計(jì)算時(shí)間。圖4為2種算法計(jì)算時(shí)間的箱型圖。由圖4可以直觀地看出2種算法在計(jì)算耗時(shí)上的差異，改進(jìn)RANSAC算法的平均計(jì)算耗時(shí)僅為RANSAC算法的42.3%。

圖3 2種算法計(jì)算時(shí)間對比

圖4 計(jì)算時(shí)間箱型圖

4 結(jié)束語

本文通過基于樣本內(nèi)在約束、預(yù)檢驗(yàn)和準(zhǔn)最優(yōu)內(nèi)點(diǎn)集提純3部分設(shè)計(jì)對標(biāo)準(zhǔn)RANSAC算法加以改進(jìn)，以提高算法的整體性能?；跇颖緝?nèi)在約束的隨機(jī)抽樣和預(yù)檢驗(yàn)過程在抽樣及檢驗(yàn)階段有效地降低了計(jì)算耗時(shí)。準(zhǔn)最優(yōu)內(nèi)點(diǎn)集提純則是以更小的閾值限制得到最終的最優(yōu)內(nèi)點(diǎn)集，從而提高了RANSAC算法的計(jì)算精度。最后通過點(diǎn)云數(shù)據(jù)特征點(diǎn)匹配實(shí)驗(yàn)驗(yàn)證了本文算法的有效性，結(jié)果表明改進(jìn)RANSAC的計(jì)算精度優(yōu)于RANSAC算法，且計(jì)算時(shí)間僅為RANSAC算法的42.3%。