抽樣一致性及其改進算法綜述

魏若巖 金雅素

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

關鍵詞： RANSAC;模型估計;圖像匹配;機器視覺

【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 引 言

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

1 RANSAC算法概述

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

Step 1 隨機抽取能計算出模型參數的最小數量的樣本。

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

Step 3 將參數回帶到所有數據樣本并統計內點率，若當前內點率最大，則將模型定為當前最優模型。

Step 4 若當前最優模型的內點率大于設定的閾值或迭代次數大于預定次數，則迭代停止，否則重復Step 1～Step 3。

Step 5 輸出當前最優模型。

2.4 基于優化的方法

2.4.1 LO-RANSAC

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

文獻[15]指出LO-RANSAC可采用多種優化策略，比如以精度換取效率，可以執行一個inner-RANSAC過程;采用迭代方法，首先選擇誤差小于Kt的所有數據點，這里的K是預定義尺度因子，t是誤差閾值，然后用所有選定的點來估計新模型，降低閾值比例因子并將繼續迭代此過程，直到閾值達到t為止。兩種策略組合比較常見，其中inner-RANSAC中的每個（非最小）樣本都受迭代精化過程的制約，這種組合通常會減少RANSAC的迭代次數，使其與理論預期數一致。

2.4.2 OPTIMAL-RANSAC

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

（1）當發現一組具有5個以上暫定變量的集合時，就會執行優化，對于低內點率的集合很重要。

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

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

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

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

3 實驗分析

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

3.1 基于模擬數據的對比實驗

模擬數據由1 000個匹配點構成，設置內點率從0.2到0.8，0.05為步長，假設經過數據過濾后有n個匹配點，則參數信息見表2。

圖1給出了3組原始數據與過濾后數據的對比圖像。圖1（a）為原始數據，其內點率分別為0.2、0.5、0.8;圖1（b）為對應的過濾后的數據。由圖1可知內點率越高，過濾的效果越好，模型越準確。

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

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

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

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

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

4 結束語

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

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

（1）完善外點的過濾策略，提高內點在算法迭代中的權重。

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

（3）將多個算法進行融合來克服單個算法的缺點，以提高算法的準確性。

參考文獻

[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.