趙 凱， 朱 愿， 謝 楓

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

引言

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

1 標準RANSAC算法

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

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

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

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

di=‖bi,Tai‖

(1)

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

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

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

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

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

2 改進型RANSAC算法

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

該算法主要從3個方面對標準RANSAC算法做出改進。研究將對此展開探討論述如下。

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

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

圖1 改進RANSAC算法框圖

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

(2)

(3)

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

2.2 預檢驗

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

(1)從集合M中隨機選取一個包含ξn對關鍵點的子集M′。

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

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

其中，ξ為系數(shù)，通常取值為ξ∈[0.1,0.3]?？梢詫ⅵ卫斫鉃槌闃庸烙嫷哪Ｐ蛥?shù)所能接受的內(nèi)點率。只有潛在的準確模型估計, 才能通過預檢驗并在數(shù)據(jù)集D上接受所有數(shù)據(jù)的檢驗。

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

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

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

3 實驗結果與分析

為了驗證本文提出方法的有效性和魯棒性，對模擬數(shù)據(jù)和真實點云數(shù)據(jù)分別進行實驗，同時將本文算法與RANSAC算法的計算精度和計算耗時作以實驗對比分析。采用Velodyne HDL-64E型64線激光雷達所采集的城市復雜動態(tài)環(huán)境下的三維點云數(shù)據(jù)為真實點云數(shù)據(jù)。實驗平臺為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算法對相鄰點云幀進行特征點檢測，并使用匹配算法對特征點進行匹配；然后分別利用本文算法和RANSAC算法對匹配點對進行篩選，在此基礎上得到了研究選用的抽樣集合和參數(shù)模型；最后將歐氏適應度值(Euclidean fitness score)[5]作為點云匹配準確度的衡量指標，歐氏適應度值是參與匹配的兩幀點云中各個對應點對之間歐式距離的均方差。設置預檢驗樣本數(shù)為n=10。仿真研究的結果分析如下。

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

圖2 2種算法計算精度對比

Fig.2Comparisonofcalculationaccuracybetweenthetwoalgorithms

表1 2種算法匹配結果對比

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

圖3 2種算法計算時間對比

圖4 計算時間箱型圖

4 結束語

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