随机抽样一致

随机抽样一致算法（RANdom SAmple Consensus，RANSAC）。它采用迭代的方式从一组包含离群的被观测数据中估算出数学模型的参数。RANSAC是一个非确定性算法，在某种意义上说，它会产生一个在一定概率下合理的结果，而更多次的迭代会使这一概率增加。此RANSAC算法在1981年由Fischler和Bolles首次提出。

RANSAC的基本假设是

这里用一个简单的例子来说明，在一组数据点中找到一条最适合的线。假设，此有一组集合包含了内群以及离群，其中内群为可以被拟合到线段上的点，而离群则是无法被拟合的点。如果我们用简单的最小二乘法来找此线，我们将无法得到一条适合于内群的线，因为最小二乘法会受离群影响而影响其结果。而RANSAC，可以只由内群来计算出模型，而且概率还够高。然而，RANSAC无法保证结果一定最好，所以必须小心选择参数，使其能有足够的概率。

包含许多离群的一组数据，要找一条最适合的线。

RANSAC找到的线，离群值对结果没影响（蓝色点为内群，红色点为离群）

这里有几个问题

假设每个点是真正内群的几率是 ${\displaystyle w}$，则：

通常我们不知道 ${\displaystyle w}$ 是多少，${\displaystyle w^n}$ 是所选择的 ${\displaystyle n}$ 个点都是内群的几率，${\displaystyle 1-<!--\; -\; -->w^n}$ 是所选择的 ${\displaystyle n}$ 个点至少有一个不是内群的几率，${\displaystyle (1-<!--\; -\; -->w^n{)}^k}$ 是表示重复 ${\displaystyle k}$ 次都没有全部的 ${\displaystyle n}$ 个点都是内群的几率，假设算法跑 ${\displaystyle k}$ 次以后成功的几率是 ${\displaystyle p}$，那么：

所以如果希望成功几率高，${\displaystyle p=0.99}$，当 ${\displaystyle n}$ 不变时，${\displaystyle k}$ 越大，${\displaystyle p}$ 越大，当 ${\displaystyle w}$ 不变时，${\displaystyle n}$ 越大，所需的 ${\displaystyle k}$ 就越大，通常 ${\displaystyle w}$ 未知，所以 ${\displaystyle n}$ 选小一点比较好。

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