作者：王先榮 原文鏈接： http://blog.csdn.net/dadaadao/article/details/6247345

本文翻譯自維基百科，英文原文地址是：http://en.wikipedia.org/wiki/ransac，如果您英語不錯，建議您直接查看原文。
RANSAC是“RANdom SAmple Consensus（隨機(jī)抽樣一致）”的縮寫。它可以從一組包含“局外點”的觀測數(shù)據(jù)集中，通過迭代方式估計數(shù)學(xué)模型的參數(shù)。它是一種不確定的算法——它有一定的概率得出一個合理的結(jié)果；為了提高概率必須提高迭代次數(shù)。該算法最早由Fischler和Bolles于1981年提出。
RANSAC的基本假設(shè)是：
（1）數(shù)據(jù)由“局內(nèi)點”組成，例如：數(shù)據(jù)的分布可以用一些模型參數(shù)來解釋；
（2）“局外點”是不能適應(yīng)該模型的數(shù)據(jù)；
（3）除此之外的數(shù)據(jù)屬于噪聲。
局外點產(chǎn)生的原因有：噪聲的極值；錯誤的測量方法；對數(shù)據(jù)的錯誤假設(shè)。
RANSAC也做了以下假設(shè)：給定一組（通常很小的）局內(nèi)點，存在一個可以估計模型參數(shù)的過程；而該模型能夠解釋或者適用于局內(nèi)點。

本文內(nèi)容
1 示例
2 概述
3 算法
4 參數(shù)
5 優(yōu)點與缺點
6 應(yīng)用
7 參考文獻(xiàn)
8 外部鏈接

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

左圖：包含很多局外點的數(shù)據(jù)集 右圖：RANSAC找到的直線（局外點并不影響結(jié)果）

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

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

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

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

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

四、參數(shù)
我們不得不根據(jù)特定的問題和數(shù)據(jù)集通過實驗來確定參數(shù)t和d。然而參數(shù)k（迭代次數(shù)）可以從理論結(jié)果推斷。當(dāng)我們從估計模型參數(shù)時，用p表示一些迭代過程中從數(shù)據(jù)集內(nèi)隨機(jī)選取出的點均為局內(nèi)點的概率；此時，結(jié)果模型很可能有用，因此p也表征了算法產(chǎn)生有用結(jié)果的概率。用w表示每次從數(shù)據(jù)集中選取一個局內(nèi)點的概率，如下式所示：
w = 局內(nèi)點的數(shù)目 / 數(shù)據(jù)集的數(shù)目
通常情況下，我們事先并不知道w的值，但是可以給出一些魯棒的值。假設(shè)估計模型需要選定n個點， w ⁿ 是所有n個點均為局內(nèi)點的概率； 1 ? w ⁿ 是n個點中至少有一個點為局外點的概率，此時表明我們從數(shù)據(jù)集中估計出了一個不好的模型。 (1 ? w ⁿ ) ^k 表示算法永遠(yuǎn)都不會選擇到n個點均為局內(nèi)點的概率，它和1-p相同。因此，
1 ? p = (1 ? w ⁿ ) ^k
我們對上式的兩邊取對數(shù)，得出

值得注意的是，這個結(jié)果假設(shè)n個點都是獨立選擇的；也就是說，某個點被選定之后，它可能會被后續(xù)的迭代過程重復(fù)選定到。這種方法通常都不合理，由此推導(dǎo)出的k值被看作是選取不重復(fù)點的上限。例如，要從上圖中的數(shù)據(jù)集尋找適合的直線，RANSAC算法通常在每次迭代時選取2個點，計算通過這兩點的直線maybe_model，要求這兩點必須唯一。
為了得到更可信的參數(shù)，標(biāo)準(zhǔn)偏差或它的乘積可以被加到k上。k的標(biāo)準(zhǔn)偏差定義為：

五、優(yōu)點與缺點
RANSAC的優(yōu)點是它能魯棒的估計模型參數(shù)。例如，它能從包含大量局外點的數(shù)據(jù)集中估計出高精度的參數(shù)。RANSAC的缺點是它計算參數(shù)的迭代次數(shù)沒有上限；如果設(shè)置迭代次數(shù)的上限，得到的結(jié)果可能不是最優(yōu)的結(jié)果，甚至可能得到錯誤的結(jié)果。RANSAC只有一定的概率得到可信的模型，概率與迭代次數(shù)成正比。RANSAC的另一個缺點是它要求設(shè)置跟問題相關(guān)的閥值。
RANSAC只能從特定的數(shù)據(jù)集中估計出一個模型，如果存在兩個（或多個）模型，RANSAC不能找到別的模型。

六、應(yīng)用
RANSAC算法經(jīng)常用于計算機(jī)視覺，例如同時求解相關(guān)問題與估計立體攝像機(jī)的基礎(chǔ)矩陣。

七、參考文獻(xiàn)

• 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

九、后話

本文在翻譯的過程中參考了沈樂君的文章《 隨機(jī)抽樣一致性算法RANSAC源程序和教程 》。Ziv Yaniv已經(jīng)用C++實現(xiàn)了RANSAC，您可以 點擊這里下載 源程序。

不過，如果時間允許的話，我打算自己動手用C#去實現(xiàn)RANSAC算法，原因有兩個：

（1）熟悉算法的最佳途徑是自己去實現(xiàn)它；

（2）方便使用.net的同志們利用RANSAC。

感謝您耐心看完我的蹩腳翻譯，希望對您有所幫助。

隨機(jī)抽樣一致性算法（RANSAC）