抽樣一致性及其改進(jìn)算法綜述

魏若巖 金雅素

摘 要：抽樣一致性算法（Random Sample Consensus，RANSAC）是一種穩(wěn)健的模型估計方法，該方法廣泛應(yīng)用于機(jī)器視覺領(lǐng)域。針對圖像匹配模型的魯棒估計問題，首先分析了RANSAC改進(jìn)算法，然后對RANSAC、Optimal-RANSAC、NAPSAC、Mapsac以及RANSAC-Tdd等算法進(jìn)行了對比實驗，最后通過實驗結(jié)果分析了各種改進(jìn)算法的優(yōu)缺點。

關(guān)鍵詞： RANSAC;模型估計;圖像匹配;機(jī)器視覺

【Abstract】 RANSAC is a robust method for model estimation，this method has been widely used in machine vision.For the problem of estimating image matching model，this paper firstly analyzes the improved RANSAC algorithm; then，series of comparative experiments are conducted on the algorithms such as RANSAC，Optimal-RANSAC，NAPSAC，Mapsac and RANSAC-Tdd to test their performance; finally， the features analysis of various improved algorithms are given.

【Key words】 ?RANSAC; model estimation; image matching; machine vision

0 引 言

在機(jī)器視覺領(lǐng)域，大量的圖像匹配算法被提出[1～3]，其中較為常用的是Fischler等人[2， 4]在1981年提出的RANSAC，其易于實現(xiàn)而且魯棒性高，但是在準(zhǔn)確性、有效性和穩(wěn)定性方面存在一定的不足，針對這些問題，提出了一些改進(jìn)算法。對此可展開研究論述如下。

1 RANSAC算法概述

目前，RANSAC算法已廣泛應(yīng)用于機(jī)器視覺領(lǐng)域，是經(jīng)典的模型魯棒估計算法。該算法通過抽取最小樣本計算出可能的模型參數(shù)，再將模型參數(shù)回帶到所有的數(shù)據(jù)樣本并計算相應(yīng)的內(nèi)點率，直到迭代次數(shù)大于預(yù)定次數(shù)，或當(dāng)前最優(yōu)模型的內(nèi)點率達(dá)到設(shè)定的閾值，就把目前最優(yōu)結(jié)果作為最終模型、且停止抽樣，否則繼續(xù)抽樣。RANSAC算法的運(yùn)行步驟詳見如下。

Step 1 隨機(jī)抽取能計算出模型參數(shù)的最小數(shù)量的樣本。

Step 2 從抽取的樣本中計算出模型參數(shù)。

Step 3 將參數(shù)回帶到所有數(shù)據(jù)樣本并統(tǒng)計內(nèi)點率，若當(dāng)前內(nèi)點率最大，則將模型定為當(dāng)前最優(yōu)模型。

Step 4 若當(dāng)前最優(yōu)模型的內(nèi)點率大于設(shè)定的閾值或迭代次數(shù)大于預(yù)定次數(shù)，則迭代停止，否則重復(fù)Step 1～Step 3。

Step 5 輸出當(dāng)前最優(yōu)模型。

2.4 基于優(yōu)化的方法

2.4.1 LO-RANSAC

LO-RANSAC[22]（Locally optimized RANSAC）算法需要設(shè)置一個固定的迭代次數(shù)，并從返回的內(nèi)點集中重新抽樣計算模型，最后選取最優(yōu)的匹配模型作為改進(jìn)后的結(jié)果，從未受污染的最小樣本中計算出的模型總是包含大量內(nèi)點，因此將一個優(yōu)化步驟插入到RANSAC算法中，以當(dāng)前的最優(yōu)解作為優(yōu)化的起點。

文獻(xiàn)[15]指出LO-RANSAC可采用多種優(yōu)化策略，比如以精度換取效率，可以執(zhí)行一個inner-RANSAC過程;采用迭代方法，首先選擇誤差小于Kt的所有數(shù)據(jù)點，這里的K是預(yù)定義尺度因子，t是誤差閾值，然后用所有選定的點來估計新模型，降低閾值比例因子并將繼續(xù)迭代此過程，直到閾值達(dá)到t為止。兩種策略組合比較常見，其中inner-RANSAC中的每個（非最?。颖径际艿^程的制約，這種組合通常會減少RANSAC的迭代次數(shù)，使其與理論預(yù)期數(shù)一致。

2.4.2 OPTIMAL-RANSAC

OPTIMAL-RANSAC[23]類似于LO-RANSAC算法，可對一組初始值進(jìn)行多次重采樣，再對模型進(jìn)行迭代估計并給出相應(yīng)的內(nèi)點數(shù)。分析可知，此算法與LO-RANSAC存在差異，對此可表述如下：

（1）當(dāng)發(fā)現(xiàn)一組具有5個以上暫定變量的集合時，就會執(zhí)行優(yōu)化，對于低內(nèi)點率的集合很重要。

（2）集合大于當(dāng)前最大的暫定內(nèi)點集合時，從該集合開始重采樣，不斷迭代直至找到最大集合。

（3）迭代重估計和取心使用相同的公差，即集合將不斷增長，直到集合停止變化，迭代停止，即找到最優(yōu)集合的概率很高。

（4）以較低的公差進(jìn)行修剪以保留最好的內(nèi)點，在每一步中使用剩余內(nèi)點重新計算。

該算法的缺點主要是當(dāng)圖像包含多個平面時，不能保證找到最優(yōu)集，因為可以有多個次優(yōu)集以給定的公差完成轉(zhuǎn)換。在任何情況下，該算法都能有效地找到次優(yōu)集，但是無法保證每次都會找到相同的次優(yōu)集。OPTIMAL-RANSAC具有較好的性能，該方法能處理外點率高于95%的樣本。

3 實驗分析

本節(jié)將從2個方面來做研究探討。其一，是利用模擬數(shù)據(jù)對上述算法進(jìn)行對比實驗并得出結(jié)論;其二，是利用真實圖像對上述算法進(jìn)行對比實驗并得出結(jié)論。由于資源有限，本文只對部分算法進(jìn)行實驗，分別為：RANSAC、OPTIMAL-RANSAC、Mlesac、Mapsac、NAPSAC、RANSAC-Tdd。對此研究可做詳盡表述如下。

3.1 基于模擬數(shù)據(jù)的對比實驗

模擬數(shù)據(jù)由1 000個匹配點構(gòu)成，設(shè)置內(nèi)點率從0.2到0.8，0.05為步長，假設(shè)經(jīng)過數(shù)據(jù)過濾后有n個匹配點，則參數(shù)信息見表2。

圖1給出了3組原始數(shù)據(jù)與過濾后數(shù)據(jù)的對比圖像。圖1（a）為原始數(shù)據(jù)，其內(nèi)點率分別為0.2、0.5、0.8;圖1（b）為對應(yīng)的過濾后的數(shù)據(jù)。由圖1可知內(nèi)點率越高，過濾的效果越好，模型越準(zhǔn)確。

圖2給出了部分算法在不同內(nèi)點率下的完成時間。各算法在每個內(nèi)點率上運(yùn)行20次后求其平均時間。從圖2中可以看出，所有算法的運(yùn)行時間與數(shù)據(jù)內(nèi)點率的上升成反比例關(guān)系，OPTIMAL-RANSAC在各個內(nèi)點率下所使用的時間最少，其余算法在內(nèi)點率0.1～0.2內(nèi)需較長的時間，當(dāng)內(nèi)點率大于0.3時，NAPSAC、OPTIMAL-RANSAC、Mapsac的運(yùn)行時間接近。

圖3～圖4給出了6個算法在不同迭代次數(shù)下的內(nèi)點查全率。由圖3～圖4可以看出，無論內(nèi)點率是0.1還是0.3，所有算法的內(nèi)點查全率隨著迭代次數(shù)的增加均呈增長趨勢，當(dāng)內(nèi)點率為0.1時，迭代次數(shù)在100～800之間時，OPTMAL-RANSAC的優(yōu)勢明顯。當(dāng)內(nèi)點率為0.3時，OPTIMAL-RANSAC、RANSAC、NAPSAC的內(nèi)點查全率較為接近。

3.2 基于真實圖像的對比實驗

有7組真實圖像見表3，依次為：Building、Wall、Graft、Book、Boat1、Boat2、Asteroid。其中，Building、Wall與Graft體現(xiàn)了圖像間的透視變化，其余圖像體現(xiàn)了圖像間的水平旋轉(zhuǎn)變化。所有算法實驗的最大迭代次數(shù)均為5 000，在匹配過程中使用SIFT特征點和描述方式，選取4個指標(biāo)分別為：查找到的內(nèi)點數(shù)I、算法的迭代次數(shù)t、每個模型所需檢測的次數(shù)vpm（number of verification per model）、算法運(yùn)行時間times（/s）。研究中得到的上述指標(biāo)的比較結(jié)果見表4。所有算法在每對圖像上均運(yùn)行20次，而后計算出每個指標(biāo)的平均值，通過分析可發(fā)現(xiàn)以下特點：

在查找內(nèi)點數(shù)I方面，OPTIMAL-RANSAC具有較好的性能，尤其在Graft和Wall兩對圖像中查找到的內(nèi)點數(shù)較多;在迭代次數(shù)t與運(yùn)行時間times上，OPTIMAL-RANSAC顯然要勝過其它算法，這是因為OPTIMAL-RANSAC是一種優(yōu)化算法，每次迭代都要計算出一個數(shù)據(jù)核，并且在數(shù)據(jù)核中再進(jìn)行抽樣和模型檢驗，因此必然增大了每次迭代的時間成本;在模型的整體檢測次數(shù)上，RANSAC-Tdd具有明顯的優(yōu)勢，主要原因在于RANSAC-Tdd選取遠(yuǎn)小于匹配點數(shù)目的d個匹配點作為測試點，只有當(dāng)d個匹配點都符合當(dāng)前匹配模型時再對剩余的匹配點進(jìn)行測試，否則拋棄當(dāng)前模型，這就必然會減少每個模型的驗證次數(shù)。

4 結(jié)束語

本文先是分析了RANSAC算法的缺點，然后研究了4類改進(jìn)算法，并論證了各自的性能?？偟貋碚f，基于模型求解的方法，其中的M估計和LMedS當(dāng)內(nèi)點率大于50%時，不能得到理想模型，Mlesac和Mapsac對于較高外點率的數(shù)據(jù)能估計出理想模型，但是當(dāng)外點率大于80%時，效果急劇下降;而針對基于樣本預(yù)檢驗的方法，其中的RANSAC-Tdd在樣本內(nèi)點率較高時能得到較為理想的效果，但是當(dāng)內(nèi)點率很低時，就會陷入無限次抽樣與檢驗中，Bail-out Test與RANSAC相比，性能提高2～7倍;與此同時，針對基于樣本選擇的方法，其中的PROSAC主要依賴于樣本特征點的相關(guān)描述，NAPSAC卻依賴于內(nèi)點的聚集性，GROUPSAC則綜合了PROSAC和NAPSAC算法的優(yōu)缺點，抽樣效率很高;此外，針對基于優(yōu)化的方法，其中的OPTIMAL-RANSAC能處理外點率高于95%的樣本。

所以，RANSAC及其改進(jìn)算法有待從如下方面加以研究，對此可表述為：

（1）完善外點的過濾策略，提高內(nèi)點在算法迭代中的權(quán)重。

（2）提高算法對各種圖像的適應(yīng)性及時效性。

（3）將多個算法進(jìn)行融合來克服單個算法的缺點，以提高算法的準(zhǔn)確性。

參考文獻(xiàn)

[1]CHOI S，KIM T，YU W. Performance evaluation of RANSAC family[C]//British Machine Vision Conference，BMVC 2009.London，UK： Dblp，2009：1-13.

[2]RAGURAM R，CHUM O，POLLEFEYS M，et al.USAC： A universal framework for random sample consensus[J].IEEE Transactions on Pattern Analysis & Machine Intelligence，2013，35（8）：2022-2038.

[3]魏若巖，阮曉鋼，于乃功，等.基于Skinner操作條件反射的抽樣一致性算法[J].控制與決策，2015，30（2）：235-240.

[4]FISCHLER M A，BOLLES R C. Random sample consensus：A paradigm for model fitting with applications to image analysis and automated cartography[J]. Communications of the ACM，1981，24（6）： 381-395.

[5]CHEN J H，CHEN C S，CHEN Y S.Fast algorithm for robust template matching with M-estimators[J].IEEE Transactions on Signal Processing，2003，51（1）：230-243.

[6]CHUM O，WERNER T，MATAS J.Epipolar geometry estimation via RANSAC benefits from the oriented epipolar constraint[C]// Proceedings of the 17th International Conference on Pattern Recognition， ICPR 2004.Cambridge， UK：IEEE，2004，1：1-4.