RANSAC算法原理

RANSAC是“RANdom SAmple Consensus（随机抽样一致）”的缩写。它可以从一组包含“局外点”的观测数据集中，通过迭代方式估计数学模型的参数。它是一种不确定的算法，有一定的概率得出一个合理的结果。为了提高得出合理结果的概率必须提高迭代次数。

1、基本思想：

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

1. 有一个模型适用于假设的局内点，即所有的未知参数都能从假设的局内点计算得出。

2. 用1中得到的模型去测试所有的其它数据，如果某个点适用于估计的模型，认为它也是局内点。

3. 如果有足够多的点被归类为假设的局内点，那么估计的模型就足够合理。

4. 然后，用所有假设的局内点去重新估计模型，因为它仅仅被初始的假设局内点估计过。

5. 最后，通过估计局内点与模型的错误率来评估模型。

这个过程被重复执行固定的次数，每次产生的模型要么因为局内点太少而被舍弃，要么因为它比现有的模型更好而被选用。

2、对上述步骤，进行简单总结如下：

N：样本点个数，K：求解模型需要的最少的点的个数

1. 随机采样K个点
2. 针对该K个点拟合模型
3. 计算其它点到该拟合模型的距离，小于一定阈值当做内点，统计内点个数
4. 重复M次，选择内点数最多的模型
5. 利用所有的内点重新估计模型（可选）

3、举例：利用RANSAC算法拟合一条直线

4、计算需要的采样次数M

N：样本点个数，K：求解模型需要的最少的点的个数，P：该点为内点的概率

：K个点都是内点的概率

：K个点至少有一个外点的概率（采样失败）

：M次采样全部失败的概率

：M次采样至少有一次成功的概率

计算P=0.9，K=8，想要采样成功率达到Z>=0.99时，所需要的采样次数M

                                                                    

参考文章：https://blog.****.net/robinhjwy/article/details/79174914