隨機抽樣一致

随机抽样一致算法（RANdom SAmple Consensus，RANSAC）。它采用迭代的方式从一組包含離群的被觀測數據中估算出數學模型的參數。 RANSAC是一個非确定性算法，在某種意義上說，它會產生一個在一定概率下合理的結果，而更多次的迭代会使这一概率增加。此RANSAC算法在1981年由Fischler和Bolles首次提出。

RANSAC的基本假設是

1. 「內群」(inlier, 似乎譯為內點群更加妥當，即正常數據，正確數據)數據可以通過幾組模型的參數來敘述其分佈，而｢離群」(outlier,似乎譯為外點群更加妥當，異常數​​據)數據則是不適合模型化的數據。
2. 數據會受雜訊影響，雜訊指的是離群，例如從極端的雜訊或錯誤解釋有關數據的測量或不正確的假設。
3. RANSAC假定，給定一組（通常很小）的內點群，存在一個程序，這個程序可以估算最佳解釋或最適用於這一數據模型的參數。

範例

這裡用一個簡單的例子來說明，在一組數據點中找到一條最適合的線。假設，此有一組集合包含了內點群以及外點群，其中內點群包含可以被擬合到線段上的點，而外點群則是無法被擬合的點。如果我們用簡單的最小二乘法來找此線，我們將無法得到一條適合於內點群的直線，因為最小二乘法會受外點群影響而影響其結果。而用RANSAC，可以只由內點群來計算出模型，而且概率還夠高。然而，RANSAC無法保證結果一定最好，所以必須小心選擇參數，使其能有足夠的概率。

• 
  包含許多離群的一組數據，要找一條最適合的線。
• 
  RANSAC找到的線，離群值對結果沒影響（藍色點為內群，紅色點為離群）

概述

1. 在數據中隨機選擇若干個點設定為內點群
2. 計算拟合內點群的模型
3. 把其它剛才沒選到的點帶入剛才建立的模型中，計算是否屬於內點群
4. 記下內點群數量
5. 重複以上步驟
6. 比較哪次計算中內點群數量最多，內點群最多的那次所建的模型就是我們所要求的解

這裡有幾個問題

1. 一開始的時候我們要隨機選擇多少點（n）
2. 以及要重複做多少次（k）

參數決定

假設每個點是真正內點群的機率是 $w$，则：

$w$ = 真正內點群的數目 / 數據總數

通常我們不知道 $w$ 是多少，$w^{n}$ 是所選擇的 $n$ 個點都是內點群的機率，$1-w^{n}$ 是所選擇的 $n$ 個點至少有一個不是內點群的機率，$(1-w^{n})^{k}$ 是表示重複 $k$ 次都沒有全部的 $n$ 個點都是內點群的機率，假設算法跑 $k$ 次以後成功的機率是 $p$，那麼：

$1-p=(1-w^{n})^{k}\,$

$p=1-(1-w^{n})^{k}\,$

$k={\frac {\log(1-p)}{\log(1-w^{n})}}$

所以如果希望成功機率高，$p=0.99$， 當 $n$ 不變時，$k$ 越大，$p$ 越大， 當 $w$ 不變時，$n$ 越大，所需的 $k$ 就越大， 通常 $w$ 未知，所以 $n$ 選小一點比較好。

應用

RANSAC算法经常用在计算机视觉领域，例如，对于一对立体相机，同时求解其对应点问题和估计它们之间的基础矩阵。

参考资料

• Martin A. Fischler and Robert C. Bolles. Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography. Comm. of the ACM. June 1981, 24 (6): 381–395. doi:10.1145/358669.358692. 
• David A. Forsyth and Jean Ponce. Computer Vision, a modern approach. Prentice Hall. 2003. ISBN 0-13-085198-1. 
• Richard Hartley and Andrew Zisserman. Multiple View Geometry in Computer Vision 2nd. Cambridge University Press. 2003. 
• P.H.S. Torr and D.W. Murray. The Development and Comparison of Robust Methods for Estimating the Fundamental Matrix. International Journal of Computer Vision. 1997, 24 (3): 271–300. doi:10.1023/A:1007927408552. 
• Ondrej Chum. Two-View Geometry Estimation by Random Sample and Consensus (PDF). PhD Thesis. 2005. （原始内容 (PDF)存档于2009-08-16）. 
• Sunglok Choi, Taemin Kim, and Wonpil Yu. Performance Evaluation of RANSAC Family (PDF). In Proceedings of the British Machine Vision Conference (BMVC). 2009 [2011-11-17]. （原始内容存档 (PDF)于2020-08-31）. 

外部链接

• 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 （页面存档备份，存于互联网档案馆）
• （[//web.archive.org/web/20150515081026/http://www.csse.uwa.edu.au/~pk/Research/MatlabFns/#robust 页面存档备份，存于互联网档案馆） Source code for RANSAC in MATLAB]