3.3 实例：RANSAC算法及直线拟合

RANSAC是一种从一组含有“外点”（Outliers）的数据中正确估计数学模型参数的迭代算法。“外点”一般是指数据中的噪声，例如，匹配中的“误匹配”和估计曲线中的“离群点”。所以，RANSAC也被视为一种“外点”检测算法。RANSAC是一种非确定性算法，它只能在一种概率下产生结果，并且这个概率会随着迭代次数的增加而加大。

对于RANSAC算法而言，其基本假设是数据由“内点”和“外点”组成，其中“内点”是组成模型参数的数据，“外点”则是不适合模型的数据。同时，RANSAC算法还假设：对于给定的一组含有少部分“内点”的数据，存在一个程序，可以估计出符合“内点”的模型。本节代码部分参考了知乎上的一篇文章（见“链接1”），用来说明如何利用RANSAC算法进行直线检测。

3.3.1 算法思路

RANSAC算法通过反复选择数据集以估计出模型，迭代过程一直持续到估计出比较好的模型为止。具体的实现步骤如下：

（1）选择可以估计出模型的最小数据集[对于直线拟合，就是2个点；而对于计算单应性（Homography）矩阵，就是4个点]。

（2）使用这个数据集计算出数据模型。

（3）将所有数据置入这个模型中，并计算出“内点”数（累加在一定的误差范围内，且适合当前迭代推理模型的数据）。

（4）比较当前模型和之前推理的最好模型的“内点”数，记录最大“内点”数的模型参数和“内点”数。

（5）重复第1步至第4步，直到迭代结束，或者当前模型已经足够好（“内点”数大于一定的值）。

3.3.2 用Python实现直线拟合

代码3-5 用Python实现直线拟合 8K9hOew7WVwqAfUFYisSzUA38QBAjuX18uu8aKX6ZkuCDrJdi4xz0VtBV3fNuaXb