随机抽样一致

随机抽样一致算法（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]