Random Sample Consensus(RANSAC)的一点读后总结

RANSAC算法不同与传统的平滑过程，传统方法是利用尽可能多的数据来获得一个比较原始的解，然后尝试使用一些优化算法来消除invalid的数据点。对于RANSAC则是使用一个比较小的数据集，然后再尽可能的使用一致的数据来扩大原来初始化的数据集。

举个例子来说，如果我们要拟合一段二维点中的弧线，RANSAC会选择三个点作为一个集合（确定一个弧线需要三个点），然后计算中心和半径，也就是说这样圆的弧线就基本确定了，然后在计算其他点是否足够靠近这个圆弧，其他点的偏差足够小可以认为是测量的误差。如果有足够符合这个圆弧的点，RANSAC将会使用一个平滑的技术（最小二乘），来更好的估计这个圆的参数，到了这一步，相互一致的点的数据集也就确定了。（如果是拟合直线，应该是选择两个点；如果是拟合平面，应该选择三个点）

RANSAC一个比较正式的陈述如下：

给定一个模型，需要最小为n的数据集来实例化它的自由参数，给定一个数据集，含有P个数据（P大于或者等于n）；随机从P中选择n个数据点作为一个子集S1，然后对模型进行实例化。使用实例化后的模型为M1，然后再决定在整个数据集P中能够符合错误阈值的子集S1’,S1’就是S1的共识集。

如果S1’数量大一某些设定的阈值t，是在数据集P中对总的错误数量的估计函数，使用S1’来计算（可能是使用最小二乘）一个新的模型M1‘。

如果S1’的数量小于t，随机选择一个新的子集S2，重复之前的步骤，如果经过预先设定的实验次数过后，没有共识集满足t或者更多的数量，要么通过最大的共识集来解出模型，要么以失败告终。

以上就是完整的RANSAC的算法流程，如果需要更多详细的理解，可能还是需要小伙伴们自己阅读paper。

RANSAC有三个不确定的参数：

1.error tolerance：用来确定一个点是否与产生的模型兼容：

error tolerance可以设置成比平均测量误差高1到2个标准差，这个设置还是很经验值的，所以可以多多尝试一下。同时值得注意的是针对不同的数据集，这个值应该是不同的，但是一个数据集也只需要一个error tolerance也就足够了。

2.maximum number of attempts：选择尝试的子集的数量

怎么选择具体的实验次数？当然在理想状态下，当然是实验的次数越多越好，但实际上在工程应用的时候，是不现实的，所以要比较合理的设置实验次数。实验次数太多，浪费资源，如果实验次数过少，那么很有可能都找不到正确的模型，所以这个参数设置还是很重要的。

假设实验次数为k，即从整个数据集P中选择k次n个内点的子集,w是在模型的error tolerance中任一一个数据点选到的概率，z是至少一次随机选择在无外点的n个数据点集中的概率。
可以推导出：

$E(k) = 1/b =w^{-n}$

$SD（k）=[sqrt(1-w^{n})]×（1/w^{n}）$

$k=log(1-z)/[log(1-b)]) ，if， w^n\ll1，then, k \approx log(1-z)E(k)$

$其中b = w^n$ 具体公式推导啥的还是子集看paper吧。

3.size of an acceptable consensus set：就是上文中定义的t

这个参数是用来决定在P中一个含有n个点的子集的basis,也就是说已经找到了一个足够大的共识集来允许算法进行终止。所以t的选择必须足够大来满足两个目的：第一，针对数据集，正确的模型已经找到了；第二，被找到的相互共识的点的数量满足最后进行平滑的过程（就是说可以提高模型参数的估值）。这个还是有很多方法，就自行查阅和解决吧。

好像非要上张图，不然这篇文章太单调了。。。

参考文献：
[1]Martin A. Fischler and Robert C. Bolles (June 1981). “Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography”. Comm. of the ACM 24: 381–395. doi:10.1145/358669.358692.