对RANSAC算法的个人理解

写在前面，最小二乘法：

https://baijiahao.baidu.com/s?id=1613474944612061421&wfr=spider&for=pc

其实就是根据给定的点求一个拟合函数的未知参数，使得给定的点和拟合得到的函数在Y方向的差值的平方和最小。

首先说一下RANSAC的作用，此算法可以在大量噪声情况下，提取特定的成本，也就是有用的数据点进行建模之类的操作。比如下面这张图片。

图中有一部分点是满足图像的，另外一团点是噪声，可以看出噪声点数量较多，估算噪声数据量是直线的三倍。此算法可以让我们在存在大量噪声点的状况下，找到直线方程。

首先以一个简单易懂的例子阐述一下这个算法（小女生找男朋友）

1.从人群中随便找个男生（实际过程中就是找几个点构成的点集），看看他条件怎么样，然后和他谈恋爱（用最小二乘法等方法得到该点集对应的模型），实际中以拟合直线为例，平面中随机找两个点，拟合一条直线，并计算在容忍误差e中有多少个点满足这条直线。

2.第二天，再重新找个男生，看看他条件怎么样，和现在找到的最好的男朋友比比，如果更好就换新的（依旧以拟合直线为例，重新随机选两个点，拟合直线，看看这条直线是不是能容忍更多的点，也就是在容忍误差e中有多少个点能满足这条直线，如果能容忍更多的点，则记录这条直线为当前为止的最好结果）

3.第三天，重复第二天的行为（迭代循环）

4.终于到了某个年龄，和现在的男朋友结婚（迭代结束，记录当前结果）

显然，这样找男朋友，最后一定会嫁一个好的，也就是我们会得到心仪的拟合结果（分割结果）。只要这个模型在直观上存在，该算法就一定有机会能找到它。

其优点是噪声可以分布的任意广，噪声可以远大于模型信息。

其缺点是第一，必须先制定一个合适的容忍误差e。第二，必须指定迭代次数作为收敛条件。

RANSAC算法的输入是一组观测数据，一个可以解释或者适应于观测数据的参数化模型，一些可信的参数。

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

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

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

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

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

5.最后，通过估计局内点与模型的错误率来评估模型。 这个过程被重复执行固定的次数，每次产生的模型要么因为局内点太少而被舍弃，要么因为比现有的模型更好而被选用。

可以参考的CSDN博客

https://blog.csdn.net/fandq1223/article/details/53175964

https://blog.csdn.net/laobai1015/article/details/51682596

此算法的改进（比较难，数学方面的东西较多）

https://blog.csdn.net/tianwaifeimao/article/details/48543361