• 1 RANSAC算法介绍

• 2 算法流程

• 3 迭代次数

1 RANSAC算法介绍

RANSAC^[1] (随机抽样一致)是一种迭代算法，该算法从一组包含“外点(outlier)”的观测数据中估计数学模型的参数。“外点”指观测数据中的无效数据，通常为噪声或错误数据，比如图像匹配中的误匹配点和曲线拟合中的离群点。与“外点”相对应的是“内点(inlier)”，即用来估计模型参数的有效数据。因此，RANSAC也是一种“外点”检测算法。此外，RANSAC算法是一种非确定算法，它只能在一定概率下产生可信的结果，当迭代次数增加时，准确的概率也会增加。

2 算法流程

RANSAC的基本思想和算法流程如下：

1. 随机采样K个点，K是求解模型参数的最少点个数；
2. 使用K个点估计模型参数；
3. 计算剩余点到估计模型的距离，距离小于阈值则为内点，统计内点的数目；
4. 重复步骤1~3，重复次数M且保留数目最多的内点；
5. 使用所有的内点重新估计模型。

---

举例：RANSAC拟合直线

1. 随机选取K=2个点

2. 拟合直线

3. 统计内点个数

4. 重复步骤1-3，重复次数M且保留数目最多的内点

5. 使用所有的内点重新拟合直线

3 迭代次数

设为所有样本点数目，为求解模型需要的最少点数，表示所有样本点中内点的概率，则：

因此，

当 时，如果RANSAC要满足，需要的迭代次数为：

RANSAC开源代码:

https://github.com/drsrinathsridhar/GRANSAC

参考资料

[1]

RANSAC: Random-Sample-Consensus