?

?

本文翻譯自維基百科，英文原文地址是：http://en.wikipedia.org/wiki/ransac
??? RANSAC是“RANdom SAmple Consensus（隨機抽樣一致）”的縮寫。它可以從一組包含“局外點”的觀測數據集中，通過迭代方式估計數學模型的參數。它是一種不確定的算法——它有一定的概率得出一個合理的結果；為了提高概率必須提高迭代次數。該算法最早由Fischler和Bolles于1981年提出。他們使用該算法來解決3D重建中的位置確定問題（Location Determination Problem, LDP）。目前RANSAC算法被廣泛用于計算機視覺領域中圖像匹配、全景拼接等問題，比如從數對匹配的特征點中求得兩幅圖片之間的射影變換矩陣，OPENCV實現stitching類時即使用了該算法。?
RANSAC算法與最小二乘法的不同之處主要有以下兩點：?
1. 最小二乘法總是使用所有的數據點來估計參數，而RANSAC算法僅使用局內點；?
2. 最小二乘法是一種確定性算法，給定數據集，每一次所得到的模型參數都是相同的；而RANSAC算法是一種隨機算法，受迭代次數等的影響，每一次得到的參數一般都不相同。?
3. 一般而言，RANSAC算法先根據一定的準則篩選出局內點和局外點，然后對得到的局內點進行擬合，擬合方法可以是最小二乘法，也可以是其他優化算法，從這個角度來說，RANSAC算法是最小二乘法的擴展。
??? RANSAC的基本假設是：
（1）數據由“局內點”組成，例如：數據的分布可以用一些模型參數來解釋；
（2）“局外點”是不能適應該模型的數據；
（3）除此之外的數據屬于噪聲。
??? 局外點產生的原因有：噪聲的極值；錯誤的測量方法；對數據的錯誤假設。

??? RANSAC也做了以下假設：給定一組（通常很小的）局內點，存在一個可以估計模型參數的過程；而該模型能夠解釋或者適用于局內點。

?

算法的求解過程如下：

1. 首先從數據集中隨機選出一組局內點（其數目要保證能夠求解出模型的所有參數），計算出一套模型參數。
2. 用得到的模型去測試其他所有的數據點，如果某點的誤差在設定的誤差閾值之內，就判定其為局內點，否則為局外點，只保留目前為止局內點數目最多的模型，將其記錄為最佳模型。
3. 重復執行1,2步足夠的次數（即達到預設的迭代次數）后，使用最佳模型對應的局內點來最終求解模型參數，該步可以使用最小二乘法等優化算法。
4. 最后可以通過估計局內點與模型的錯誤率來評估模型。

?

本文內容
1 示例
2 概述

?

3 part1 算法

3 part2算法實例

4 參數
5 優點與缺點
6 應用
7 參考文獻
8 外部鏈接

一、示例
??? 一個簡單的例子是從一組觀測數據中找出合適的2維直線。假設觀測數據中包含局內點和局外點，其中局內點近似的被直線所通過，而局外點遠離于直線。簡單的最小二乘法不能找到適應于局內點的直線，原因是最小二乘法盡量去適應包括局外點在內的所有點。相反，RANSAC能得出一個僅僅用局內點計算出模型，并且概率還足夠高。但是，RANSAC并不能保證結果一定正確，為了保證算法有足夠高的合理概率，我們必須小心的選擇算法的參數。

左圖：包含很多局外點的數據集?????? 右圖：RANSAC找到的直線（局外點并不影響結果）

二、概述
??? RANSAC算法的輸入是一組觀測數據，一個可以解釋或者適應于觀測數據的參數化模型，一些可信的參數。
??? RANSAC通過反復選擇數據中的一組隨機子集來達成目標。被選取的子集被假設為局內點，并用下述方法進行驗證：
??? 1.有一個模型適應于假設的局內點，即所有的未知參數都能從假設的局內點計算得出。
??? 2.用1中得到的模型去測試所有的其它數據，如果某個點適用于估計的模型，認為它也是局內點。
??? 3.如果有足夠多的點被歸類為假設的局內點，那么估計的模型就足夠合理。
??? 4.然后，用所有假設的局內點去重新估計模型，因為它僅僅被初始的假設局內點估計過。
??? 5.最后，通過估計局內點與模型的錯誤率來評估模型。
??? 這個過程被重復執行固定的次數，每次產生的模型要么因為局內點太少而被舍棄，要么因為比現有的模型更好而被選用。

三、part one 算法
??? 偽碼形式的算法如下所示：
輸入：
data —— 一組觀測數據
model —— 適應于數據的模型
n —— 適用于模型的最少數據個數
k —— 算法的迭代次數
t —— 用于決定數據是否適應于模型的閥值
d —— 判定模型是否適用于數據集的數據數目
輸出：
best_model —— 跟數據最匹配的模型參數（如果沒有找到好的模型，返回null）
best_consensus_set —— 估計出模型的數據點
best_error —— 跟數據相關的估計出的模型錯誤

iterations = 0
best_model = null
best_consensus_set = null
best_error = 無窮大
while ( iterations < k )
??? maybe_inliers = 從數據集中隨機選擇n個點
??? maybe_model = 適合于maybe_inliers的模型參數
??? consensus_set = maybe_inliers

??? for ( 每個數據集中不屬于maybe_inliers的點 ）
??? ??? if ( 如果點適合于maybe_model，且錯誤小于t ）
??? ??? ??? 將點添加到consensus_set
??? if （ consensus_set中的元素數目大于d ）
??? ??? 已經找到了好的模型，現在測試該模型到底有多好
??? ??? better_model = 適合于consensus_set中所有點的模型參數
??? ??? this_error = better_model究竟如何適合這些點的度量
??? ??? if ( this_error < best_error )
??? ??? ??? 我們發現了比以前好的模型，保存該模型直到更好的模型出現
??? ??? ??? best_model =? better_model
??? ??? ??? best_consensus_set = consensus_set
??? ??? ??? best_error =? this_error
??? 增加迭代次數
返回 best_model, best_consensus_set, best_error

??? RANSAC算法的可能變化包括以下幾種：
??? （1）如果發現了一種足夠好的模型（該模型有足夠小的錯誤率），則跳出主循環。這樣可能會節約計算額外參數的時間。
??? （2）直接從maybe_model計算this_error，而不從consensus_set重新估計模型。這樣可能會節約比較兩種模型錯誤的時間，但可能會對噪聲更敏感。

?

三、part two算法實例

?

C++代碼實現

Ziv Yaniv以最簡單的直線擬合為例，寫過一版RANSAC算法的C++實現，沒有依賴任何其他庫，但該版代碼對C++的依賴較重，使用了C++的一些高級數據結構，比如vector, set，在遍歷時還使用了遞歸算法。詳細代碼可參見RANSAC代碼示例?
部分代碼及相關注釋如下：

//頂層變量定義
vector<double> lineParameters;//存儲模型參數
LineParamEstimator lpEstimator(0.5);//誤差閾值設置為0.5
vector<Point2D> pointData;//數據點集
int numForEstimate=2;//進行一次參數估計所需的最小樣本點數，因為是直線擬合，所以可以直接設為2//頂層函數的定義/*** Estimate the model parameters using the maximal consensus set by going over ALL possible* subsets (brute force approach).* Given: n -  data.size()*        k - numForEstimate* We go over all n choose k subsets       n!*                                     ------------*                                      (n-k)! * k!* @param parameters A vector which will contain the estimated parameters.*                   If there is an error in the input then this vector will be empty.*                   Errors are: 1. Less data objects than required for an exact fit.* @param paramEstimator An object which can estimate the desired parameters using either an exact fit or a*                       least squares fit.* @param data The input from which the parameters will be estimated.* @param numForEstimate The number of data objects required for an exact fit.* @return Returns the percentage of data used in the least squares estimate.** NOTE: This method should be used only when n choose k is small (i.e. k or (n-k) are approximatly equal to n)**///T是數據的類型，該例子中是二維坐標點，作者自己定義了一個類Point2D來表示；S是參數的類型，此處為雙精度double型
template  <class T, class S>
double Ransac<T, S>::compute(std::vector<S> &parameters,ParameterEsitmator<T, S> *paramEstimator,
std::vector<T> &data,
int numForEstimate)
{std::vector<T *> leastSquaresEstimateData;int numDataObjects = data.size();//數據集的大小，100int numVotesForBest = -1;//最佳模型所對應的局內點數目初始化為-1int *arr = new int[numForEstimate];//要進行一次計算所需的樣本數：2
short *curVotes = new short[numDataObjects];  //one if data[i] agrees with the current model, otherwise zeroshort *bestVotes = new short[numDataObjects];  //one if data[i] agrees with the best model, otherwise zero//there are less data objects than the minimum required for an exact fitif (numDataObjects < numForEstimate)return 0;//computeAllChoices函數尋找局內點數目最多的模型，并將局內點信息存儲在bestVotes數組中，作為最終的模型computeAllChoices(paramEstimator, data, numForEstimate,bestVotes, curVotes, numVotesForBest, 0, data.size(), numForEstimate, 0, arr);//將所有的局內點取出，存儲在leastSquareEstimateData數組中
for (int j = 0; j<numDataObjects; j++) {if (bestVotes[j])leastSquaresEstimateData.push_back(&(data[j]));}
//利用所有局內點進行最小二乘參數估計，估計的結果存儲在parameters數組中paramEstimator->leastSquaresEstimate(leastSquaresEstimateData, parameters);//釋放動態數組delete[] arr;delete[] bestVotes;delete[] curVotes;
//返回值為局內點占所有數據點的比值return (double)leastSquaresEstimateData.size() / (double)numDataObjects;
}//尋找最佳模型的函數定義如下：
//使用遞歸算法來對數據集進行n!/((n-k)!k!)次遍歷
template<class T, class S>
void Ransac<T, S>::computeAllChoices(ParameterEsitmator<T, S> *paramEstimator, std::vector<T> &data, int numForEstimate,short *bestVotes, short *curVotes, int &numVotesForBest, int startIndex, int n, int k, int arrIndex, int *arr)
{//we have a new choice of indexes//每次k從2開始遞減到0的時候，表示新取了2個數據點，可以進行一次參數估計if (k == 0) {estimate(paramEstimator, data, numForEstimate, bestVotes, curVotes, numVotesForBest, arr);return;}//continue to recursivly generate the choice of indexesint endIndex = n - k;for (int i = startIndex; i <= endIndex; i++) {arr[arrIndex] = i;computeAllChoices(paramEstimator, data, numForEstimate, bestVotes, curVotes, numVotesForBest,i + 1, n, k - 1, arrIndex + 1, arr);//遞歸調用 }}
//進行參數估計，并根據情況更新當前最佳模型的函數，最佳模型的局內點信息存儲在數組bestVotes中，而局內點的數目則是由numVotesForBest存儲
//arr數組存儲的是本輪兩個樣本點在data中的索引值
template<class T, class S>
void Ransac<T, S>::estimate(ParameterEsitmator<T, S> *paramEstimator, std::vector<T> &data, int numForEstimate,short *bestVotes, short *curVotes, int &numVotesForBest, int *arr){std::vector<T *> exactEstimateData;std::vector<S> exactEstimateParameters;int numDataObjects;int numVotesForCur;//initalize with -1 so that the first computation will be set to bestint j;numDataObjects = data.size();memset(curVotes, '\0', numDataObjects * sizeof(short));//數組中的點全部初始化為局外點numVotesForCur = 0;for (j = 0; j<numForEstimate; j++)exactEstimateData.push_back(&(data[arr[j]]));// 取出兩個數據的地址paramEstimator->estimate(exactEstimateData, exactEstimateParameters);//用取出的兩點來擬合出一組參數for (j = 0; j<numDataObjects; j++) {//依次判斷是否為局內點if (paramEstimator->agree(exactEstimateParameters, data[j])) {curVotes[j] = 1;numVotesForCur++;}}//如果當前模型inlier的數目大于目前最佳模型inlier的數目，則取代目前最佳模型，并更新信息if (numVotesForCur > numVotesForBest) {numVotesForBest = numVotesForCur;memcpy(bestVotes, curVotes, numDataObjects * sizeof(short));}
}

---

RANSAC算法的優缺點

• 該算法最大的優點就是具有較強的魯棒性，即使數據集中存在明顯錯誤的數據時，也可以得到較好的模型參數。但是要求局外點的數目不能太多，雖然我沒有做過具體的實驗，一般而言，局外點所占比例不能超過50%。當然后來又出現了一些改進的RANSAC算法，比如2013年Anders Hast提出的：Optimal RANSAC算法。
• 同時，RANSAC算法的缺點也是顯而易見的，在本文給出的示例中，N個數據點，每次估計需要K個數據點，那么如果要遍歷所有的情況，需要進行N!(N?K)!K!N!(N?K)!K!次參數估計過程，十分耗費資源。實際中一般不會全部遍歷，而是根據經驗設置一個合理的迭代次數，這顯然不能保證最終得到的是最佳參數。此外，還涉及到誤差閾值的選取問題，增加了算法的復雜度。

四、參數
??? 我們不得不根據特定的問題和數據集通過實驗來確定參數t和d。然而參數k（迭代次數）可以從理論結果推斷。當我們從估計模型參數時，用p表示一些迭代過程中從數據集內隨機選取出的點均為局內點的概率；此時，結果模型很可能有用，因此p也表征了算法產生有用結果的概率。用w表示每次從數據集中選取一個局內點的概率，如下式所示：
??? w = 局內點的數目 / 數據集的數目
??? 通常情況下，我們事先并不知道w的值，但是可以給出一些魯棒的值。假設估計模型需要選定n個點，wn是所有n個點均為局內點的概率；1 ??wn是n個點中至少有一個點為局外點的概率，此時表明我們從數據集中估計出了一個不好的模型。?(1 ??wn)k表示算法永遠都不會選擇到n個點均為局內點的概率，它和1-p相同。因此，
????1 ??p?= (1 ??wn)k
??? 我們對上式的兩邊取對數，得出
????
??? 值得注意的是，這個結果假設n個點都是獨立選擇的；也就是說，某個點被選定之后，它可能會被后續的迭代過程重復選定到。這種方法通常都不合理，由此推導出的k值被看作是選取不重復點的上限。例如，要從上圖中的數據集尋找適合的直線，RANSAC算法通常在每次迭代時選取2個點，計算通過這兩點的直線maybe_model，要求這兩點必須唯一。
??? 為了得到更可信的參數，標準偏差或它的乘積可以被加到k上。k的標準偏差定義為：
????
五、優點與缺點
??? RANSAC的優點是它能魯棒的估計模型參數。例如，它能從包含大量局外點的數據集中估計出高精度的參數。RANSAC的缺點是它計算參數的迭代次數沒有上限；如果設置迭代次數的上限，得到的結果可能不是最優的結果，甚至可能得到錯誤的結果。RANSAC只有一定的概率得到可信的模型，概率與迭代次數成正比。RANSAC的另一個缺點是它要求設置跟問題相關的閥值。
??? RANSAC只能從特定的數據集中估計出一個模型，如果存在兩個（或多個）模型，RANSAC不能找到別的模型。

六、應用
??? RANSAC算法經常用于計算機視覺，例如同時求解相關問題與估計立體攝像機的基礎矩陣。

七、參考文獻

• Martin A. Fischler and Robert C. Bolles (June 1981). "Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography".?Comm. of the ACM?24: 381–395.?doi:10.1145/358669.358692.
• David A. Forsyth and Jean Ponce (2003).?Computer Vision, a modern approach. Prentice Hall.?ISBN?0-13-085198-1.
• Richard Hartley and?Andrew Zisserman?(2003).?Multiple View Geometry in Computer Vision?(2nd ed.). Cambridge University Press.
• P.H.S. Torr and D.W. Murray (1997). "The Development and Comparison of Robust Methods for Estimating the Fundamental Matrix".?International Journal of Computer Vision?24: 271–300.?doi:10.1023/A:1007927408552.
• Ondrej Chum (2005).?"Two-View Geometry Estimation by Random Sample and Consensus".?PhD Thesis.?http://cmp.felk.cvut.cz/~chum/Teze/Chum-PhD.pdf
• Sunglok Choi, Taemin Kim, and Wonpil Yu (2009).?"Performance Evaluation of RANSAC Family".?In Proceedings of the British Machine Vision Conference (BMVC).?http://www.bmva.org/bmvc/2009/Papers/Paper355/Paper355.pdf.

八、外部鏈接

• RANSAC Toolbox for MATLAB. A research (and didactic) oriented toolbox to explore the RANSAC algorithm in?MATLAB. It is highly configurable and contains the routines to solve a few relevant estimation problems.
• Implementation in C++?as a generic template.
• RANSAC for Dummies?A simple tutorial with many examples that uses the RANSAC Toolbox for MATLAB.
• 25 Years of RANSAC Workshop

?

1. 經典RANSAC

?

? ? ? ?由Fischer和Bolles在1981年的文章[1]中首先提出，簡要的說經典RANSAC的目標是不斷嘗試不同的目標空間參數，使得目標函數?C?最大化的過程。這個過程是隨機（Random）、數據驅動（data-driven）的過程。通過反復的隨機選擇數據集的子空間來產生一個模型估計，然后利用估計出來的模型，使用數據集剩余的點進行測試，獲得一個得分，最終返回一個得分最高的模型估計作為整個數據集的模型。

1.1 目標函數

? ? ? ? 在經典的RANSAC流程中，目標函數C?可以被看作：在第k次迭代過程中，在當前變換參數作用下，數據集中滿足變換參數的點的個數，也就是在當前變換條件下類內點的個數，而RANSAC就是最大化?C?的的過程。而判斷當前某個點是否為類內需要一個閾值t。

?

1.2 子集大小

在迭代的過程中，當前變換參數?θ?的計算需要中的一個子集?I?來計算，RANSAC是一個隨機從中采樣一個子集，然后對參數“估計-確認”的循環。每一個子集應是一個大小為m?的最小采樣。所謂最小采樣，就是m?的大小剛好滿足計算θ?的個數即可。

1.3 循環終止條件

? ? ? ? 按照參考文獻[1]中的說明，在置信度為的條件下，在循環過程中，至少有一次采樣，使得采樣出的m?個點均為類內點，這樣才能保證在循環的過程中，至少有一次采樣能取得目標函數的最大值。因此，采樣次數k應該滿足以下條件：

?

? ? ? ? 這里除了置信度外，m?為子集大小，ε?為類內點在中的比例，其中置信度一般設置為[0.95, 0.99]的范圍內。然而在一般情況下，ε?顯然是未知的，因此?ε?可以取最壞條件下類內點的比例，或者在初始狀態下設置為最壞條件下的比例，然后隨著迭代次數，不斷更新為當前最大的類內點比例。

? ? ? ? 另外一種循環終止條件可以將選取的子集看做為“全部是類內點”或“不全部是類內點”這兩種結果的二項分布，而前者的概率為。對于?p?足夠小的情況下，可以將其看作為一種泊松分布，因此，在?k?次循環中，有?n個“子集全部是類內點”的概率可以表達為：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ??λ?表示在?k?次循環中，“子集全都是類內點”的選取次數的期望。例如在RANSAC中，我們希望在這k次循環中所選子集“沒有一個全是類內點”的概率小于某個置信度，即：，以置信度為95%為例，λ約等于3，表示在95%置信度下，在?k?次循環中，平局可以選到3次“好”的子集。

?

?

1.4 判斷閾值的選取

閾值?t?是判斷在當前的獲得的參數?θ?下，中某一點是類內點還是類外點的判斷依據。在這里，假定類外點是高斯白噪聲，其均值為0，方差為?σ，誤差的殘差（residuals）符合?n?維的卡方分布（chi-square）。而誤差閾值的選取即可以按照以下的公式計算[2]。

? ? ? ? α為置信概率，若?α=0.95，那么一個真實的類內點被誤分類為類外點的概率為5%。

?

? ? ? ? ?經典RANSAC算法的流程如下圖所示：

?

?

2. Universal-RANSAC

?

? ? ? ? 經典RANSAC有以下三個主要的局限性：
? ? ? ? （1） 效率：經典方法效率與子集大小、類內點比例以及數據集大小有關，因此在某些場景下效率較低。

? ? ? ? （2） 精度：經典方法計算參數時選取最小子集是從效率的角度考慮，往往得到的是非最佳參數，在應用產參數 之前還需要再經過細化處理。

? ? ? ? （3） 退化：經典方法的目標函數求取最大化的過程基于一個假設：“選取的最小子集中如果有類外點，那么在這種情況下估計的參數獲得的目標函數（數據集中點的個數）往往較少“但這種情況在退化發生時有可能是不對的。

? ? ? ? ?針對經典方法的這幾項局限性，有很多改進，在這里提出了一種全局RANSAC(Universal-RANSAC)的結構圖，每一種改進方法都可以看做是這種USAC的特例，如下圖所示。

?

2.1 預濾波(Stage 0)

? ? ? ?輸入數據集，含有?N?個點，在這一步中，SCRNMSAC[3]，用一個一致性濾波器對初始的數據集進行濾波減少數量，然后將數據根據梯度排序。

?

?

2.2 最小子集采樣(Stage 1)

?

? ? ? ?對進行采樣時，經典算法采用完全隨機的方式，這種方式的前提是我們對數據的情況完全不知道，在實際應用中，很多情況對數據的先驗知識是了解的，這對減少采樣次數，尤其是類內點比例較低的數據集，有很大幫助，以下是幾種在最小集采樣當中對經典算法進行改進的方法。

?

??Stage 1.a 采樣

2.2.1 NAPSAC[4]

? ? ? ?N-Adjacent points sample consensus(NAPSAC)算法認為：”數據集中，一個類內點與數據集中其他類內點的距離比類外點要近。”在一個n維空間中，假定：將數據集的n維空間看做一個超球面，隨著半徑的減少，類外點減少的速度比類內點要快（類外點距離球心更遠）。這種算法可以描述為：

? ? ? ?a.?中隨機選取一個點?x?，設定一個半徑?r，以?x?為中心?r?為半徑建立超球面；

? ? ? ?b. ?超球面內包裹的點少于最小數據集的個數？返回 a，否則c

? ? ? ?c. ? 均勻的從球體內取點，直至滿足最小集中的個數。

? ? ? ?這種方法對高維、類內點比例低的數據集效果明顯，但是容易產生退化，且對于距離都很近的數據集效果差。

?

2.2.2 PROSAC[5]

The progressive sample consensus(PROSAC)將點初始集匹配的結果作為排序的依據，使得在采樣時根據匹配結果由高到低的得分進行排序，這樣最有可能得到最佳參數的采樣會較早出現，提高了速度。

?

2.2.3 GroupSAC[6]

? ? ? ?與NAPSAC類似，GroupSAC認為類內點更加的“相似”，根據某種相似性將數據集中的點分組。以圖像匹配為例，分組可以基于光流聚類（optical flow-based clustering）、圖像分割等，然后按照PROSAC思想，采樣可以從最大的聚類開始，因為這里應該有更高的類內點比例。但是這種方法首先要保證有一種先驗知識可以用于分類，還有就是要保證分類算法的有效性和實時性。

?

?

? Stage 1.b 采樣驗證

經典算法在采樣完成后開始進行參數計算，而有的算法在采樣完成后加了一步驗證采樣結果適不適合進行參數計算的步驟。比如參數是計算單映性矩陣（4個點），可以根據chirality constraints 來首先驗證采樣是否合法。這種驗證計算量小，比多余的一次參數計算劃算。

2.3 根據最小集產生模型（參數計算）(Stage 2)

?

?

? Stage 2.a 模型計算

?

? ? ? ? 在這一步驟根據上一步選取的最小集計算參數，獲得模型。

?

? Stage 2.b 模型驗證

?

? ? ? ? 還是利用先驗知識，比如點集與圓形匹配，驗證時候沒必要將數據集中所有的點進行驗證，而只是在得到模型（圓）的一個半徑范圍左右驗證即可。

?

2.4 驗證參數(Stage 3)

? ? ? ?傳統的方法在得到最小集產生的參數后計算全部集合中滿足參數點的個數（目標函數），在此，加兩步驗證，分為兩點：第一，驗證當前的模型是否可能獲得最大的目標函數。第二，當前模型是非退化的。

? Stage 3.a 可能性驗證

2.4.1 T(d,d)測試[5]

? ? ? ? 選取遠小于數據集綜述的?d?個點作為測試，只有當這?d?個點全都為類內點時，再對剩余的點進行測試，否則拋棄當前的模型。具體選取辦法見論文[5].

?

?

2.4.2 Bail-Out測試[7]

? ? ? ? 選取集合中的若干點進行測試，若類內點的比例顯著低于當前最佳模型類內點的比例，拋棄此模型。

?

?

2.4.3 SPRT測試[8,9]

? ? ? ?挨個點測試，表示隨機選取一個點符合當前模型的概率(good),為“bad”的概率。根據以下公式，當閾值λ超過某閾值的時候拋棄當前模型。

?

?

?

?

2.4.4 Preemptive測試[10]

? ? ? ?ARRSAC算法[11]，首先產生多個模型，而不是產生一個后即對其評價，然后根據選取的一部分子集對所產生的模型按照目標函數得分排序，選取前若干個，做若干輪類似排序，選取最佳模型。 ?

?

?

? Stage 3.b 退化驗證

? ? ? ? 數據退化的意思是無法提供足夠的限制條件產生唯一解。傳統RANSAC即沒有這種安全的保障。

?

?

2.5 模型細化(Stage 4)

? ? ? ? 含有噪聲的數據集有兩個重要特點：1，即使子集中全都是類內點，產生的模型也并不一定適用于數據集中所有的類內點，這個現象增加了迭代的次數；2，最終收斂的RANSAC結果可能受到噪聲未完全清理的影響，并不是全局最優的結果。

? ? ? ? 第一個影響往往被忽略，因為雖然增加了迭代次數，但是仍然返回的是一個準確的模型。而第二種影響就要增加一種模型細化的后處理。

?

2.5.1 局部最優化[12]

?

? ? ? ? Lo-RANSAC，局部最優RANSAC。在迭代過程中，出現當前最優解，進行Lo-RANSAC。一種方法是從返回結果的類內點中再進行采樣計算模型，設置一個固定的迭代次數（10-20次）然后選取最優的局部結果作為改進的結果，另一種方法是設置一個優化參數K（2~3），選取結果中判斷閾值（t）小于等于Kt?的結果作為優化結果，K?減小，直至減小至?t?終止。

?

2.5.1 錯誤傳播法[13]

?

? ? ? ?思想與Lo-RANSAC一致，但是更為直接，因為初始的RANSAC結果產生自含有噪聲的數據集，因此這個錯誤“傳播”到了最終的模型，協方差可以看做是估計兩個數據集關系是一種不確定的信息（而如上所述，判斷閾值的計算是固定的）。具體方法參見文獻[13]。

?

2.6 最終方案--USAC-1.0

?

? ? ? 最終選取的結果如下圖所示：

stage1： 最小集采樣方法采用2.2.2節中的PROSAC。

stage3： 模型（參數）驗證采用2.4.3的SPRT測試。

stage4： 產生最終模型，采用2.5.1介紹的Lo-RANSAC。

?

論文翻譯自：文獻[0]。

----------------------------參考文獻---------------------------

[0]??Raguram R, Chum O, Pollefeys M, et al. USAC: A Universal Framework for Random Sample Consensus[J]. Pattern Analysis & Machine Intelligence IEEE Transactions on, 2013, 35(8):2022-2038.

[1]?M.A. Fischler and R.C. Bolles, “Random Sample Consensus: A?Paradigm for Model Fitting ?with?Applications to Image Analysis?and Automated Cartography,” Comm. ACM, vol. 24, no. 6, pp.?381-?395,1981.

[2]?R.I. Hartley and A. Zisserman, Multiple View Geometry in Computer?Vision. Cambridge Univ. Press, 2000

[3]?T. Sattler, B. Leibe, and L. Kobbelt, “SCRAMSAC: Improving?RANSAC’s Efficiency with a Spatial ?Consistency Filter,” Proc. 12th?IEEE Int’l Conf. Computer Vision, 2009.

[4]?D.R. Myatt, P.H.S. Torr, S.J. Nasuto, J.M. Bishop, and R. Craddock,“NAPSAC: High Noise, High ?Dimensional Robust Estimation,”Proc. British Machine Vision Conf., pp. 458-467, 2002.

[5]?O. Chum and J. Matas, “Matching with PROSAC—Progressive?Sample Consensus,” Proc. IEEE Conf.?Computer Vision and Pattern?Recognition, 2005.

[6]?K. Ni, H. Jin, and F. Dellaert, “GroupSAC: Efficient Consensus in?the Presence of Groupings,” Proc. 12th IEEE Int’l Conf. Computer?Vision, Oct. 2009.

[7] D. Capel, “An Effective Bail-Out Test for RANSAC Consensus?Scoring,” Proc. British Machine Vision?Conf., 2005.

[8] O. Chum and J. Matas, “Optimal Randomized RANSAC,” IEEE?Trans. Pattern Analysis and Machine ?Intelligence, vol. 30, no. 8,pp. 1472-1482, Aug. 2008.

[9]?J. Matas and O. Chum, “Randomized RANSAC with Sequential?Probability Ratio Test,” Proc. 10th IEEE Int’l Conf. Computer Vision,vol. 2, pp. 1727-1732, Oct. 2005.

[10]?D. Niste′r, “Preemptive RANSAC for Live Structure and Motion?Estimation,” Proc. Ninth IEEE Int’l Conf. Computer Vision, 2003.

[11]?R. Raguram, J.-M. Frahm, and M. Pollefeys, “A Comparative?Analysis of RANSAC Techniques Leading?to Adaptive Real-Time?Random Sample Consensus,” Proc. European Conf. Computer?Vision, pp. 500- 513. 2008,

[12]?O. Chum, J. Matas, and J. Kittler, “Locally Optimized RANSAC,”Proc. DAGM-Symp. Pattern Recognition, pp. 236-243, 2003.

[13]?R. Raguram, J.-M Frahm, and M. Pollefeys, “Exploiting Uncertainty?in Random Sample Consensus,” Proc. 12th IEEE Int’l?Conf. Computer Vision, Oct. 2009.

總結

以上是生活随笔為你收集整理的SLAM之特征匹配(二)————RANSAC--------翻译以及经典RANSAC以及其相关的改进的算法小结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。