RANSAC(RAndom SAmple Consensus,随机采样一致)算法在很多方面如图像匹配、曲线/平面拟合取得了良好的应用。这里以笔记的形式对其进行一个简要的介绍总结。

RANSAC算法的一个基本的假设是：一组数据由“内点”（inliers）和“外点”（outliers）组成，其中“内点”就是组成模型参数的数据，而“外点”就是不适合模型的数据。

RANSAC算法的目标就是在一组含有少量“内点”，大量“外点”的数据中，估计出一个符合“内点”数据的模型。

RANSAC算法基本思想

假设存在一个样本集 P ，考虑一个能够估计出模型 M所需的大小为 n最小抽样子集 S（比如说直线拟合，则抽样子集大小 n = 2，平面拟合，则抽样子集大小 n = 3）；

使用这个抽样选取的子集进行计算初始化数据模型；

针对余集 S C = P − S，代入步骤2中所估计出的模型，若其误差小于设置的阈值 t 则认为其是内点，所有的内点组成内点集 S ∗

(也成为子集 S的一致集）统计个数。

比较此次迭代和之前迭代中内点集中内点个数的大小，记录较大“内点”数的模型参数和“内点”数。

重复上述步骤1-4的过程，直到当前迭代已经足够好了，即内点集 S ∗ 的大小 N大于一定的阈值 N t 则认为此数据模型符合要求。并利用 S ∗ 中的内点采用最小二乘等方法进行重新计算数据模型 M ∗。

讨论

由上述过程中，我们可以了解到在RANSAC算法需要设置以下四个参数：

抽样子集大小 n

用于决定数据是否适应于模型的误差阀值 t

判断内点集 S ∗的大小是否适用于数据集的阈值 N t

迭代次数 K

分别对其进行讨论：

抽样子集大小 n

其中抽样子集的大小 n可以通过模型的类型进行判断，如直线拟合选取2个点，平面选取3个点。

误差阀值 t

可以根据适用模型需要自主设置。比如说曲线拟合的偏差、图像匹配中的错误匹配点对等等。

判断内点集 S ∗的大小是否适用于数据集的阈值 N t

由于RANSAC算法是基于数据驱动的模型估计方法，所以在处理粗差小于50%的情况时，其效果比较可靠。因此，内点集 S ∗  大小的阈值 N t可以设置为数据集总体大小的一半。

迭代次数 K

假设在数据中，“内点”个数的占比为 W

实际实验过程中，我们并不会知道 W W W的值，但是可以给出一个鲁棒的经验值。

对于每一次迭代过程中选取 n个点作为子集 S，则子集 S中至少存在一个点不为“内点”的概率为：

那么 K次迭代中，每次都至少有一个“外点”的情况所发生的概率为：

即，能够在 K 次迭代中正确选取 n个点，且都为“内点”的概率为：

这个 P P P值就代表了我们所期待RANSAC算法能够正确计算出数据模型的概率，可以根据自己的需求进行设置。

变换上式：

上式中 W W W可以根据经验值进行设置， P是我们所期待的正确计算数据模型的概率，可以自主设置，这样就得到了迭代次数。

当然，如果我们事先实在不知道 W的值，可以使用自适应迭代次数的方法。即开始时设定一个较大的迭代次数，然后每次更新模型参数估计的时候，用当前的“内点”比值代入公式中的 W来估算出迭代次数。