1. RANSAC简介

RANSAC(RAndom SAmple Consensus,随机采样一致)算法是从一组含有“外点”(outliers)的数据中正确估计数学模型参数的迭代算法。“外点”一般指的是数据中的噪声，比如说匹配中的误匹配和估计曲线中的离群点。所以，RANSAC也是一种“外点”检测算法。RANSAC算法是一种不确定算法，它只能在一种概率下产生结果，并且这个概率会随着迭代次数的增加而加大（之后会解释为什么这个算法是这样的）。

RANSAC主要解决样本中的外点问题，最多可处理50%的外点情况。

2. 基本思想

RANSAC通过反复选择数据中的一组随机子集来达成目标。被选取的子集被假设为局内点，并用下述方法进行验证：

一个模型适用于假设的局内点，即所有的未知参数都能从假设的局内点计算得出。
用1中得到的模型去测试所有的其它数据，如果某个点适用于估计的模型，认为它也是局内点。
如果有足够多的点被归类为假设的局内点，那么估计的模型就足够合理。
然后，用所有假设的局内点去重新估计模型，因为它仅仅被初始的假设局内点估计过。
最后，通过估计局内点与模型的错误率来评估模型。

这个过程被重复执行固定的次数，每次产生的模型要么因为局内点太少而被舍弃，要么因为它比现有的模型更好而被选用。
在这里插入图片描述对上述步骤，可以简单总结为以下步骤：
N：样本个数 K：求解模型需要的最少的点的个数（对于直线拟合来说就是两个点，对于计算Homography矩阵就是四个点）

随机采样K个点
对该K个点拟合模型
计算其他点到拟合模型的距离。如果小于一定阈值，该点被当作内点，统计内点个数
重复M次，选择内点数最多的模型
利用所有的内点重新估计模型（可选）

3. 范例

RANSAC用于拟合直线：
1.随机选取 $K = 2$ 个点：
在这里插入图片描述 2. 拟合一条直线：

3. 统计内点个数，内点为绿色，此时的内点个数为9：
4. 重复上述过程M次，找到内点数最大的模型

5. 利用所有的内点重新估计直线

4. 迭代次数推导

迭代的次数，是可以估算出来的。假设“内点”在数据中的占比为p：
$p=\frac{n_{inliers}}{n_{inliers}+n_{outliers}}$
那么我们每次计算模型使用N个点的情况下，选取的点至少有一个外点的情况(采样失败的概率）就是：
$1 - p^K$
也就是说，在迭代k次的情况下， $1-p^K)^M$ 就是 $M$ 次迭代计算模型都至少采样到一个“外点”去计算模型的概率。那么能采样到正确的K个点去计算出正确模型的概率是：
$z = 1 - (1-p^K)^M$
通过上式，可以求得：
$\frac{log(1-z)}{log(1-t^n)}$

“内点”的概率 $p$ 通常是一个先验值。然后 $z$ 是我们希望RANSAC得到正确模型的概率。如果事先不知道 $p$ 的值，可以使用自适应迭代次数的方法。也就是一开始设定一个无穷大的迭代次数，然后每次更新模型参数估计的时候，用当前的“内点”比值当成 $p$ 来估算出迭代次数。
在这里插入图片描述