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/bw−nE(k) 1/b w^{-n}E(k)1/bw−nSDk[sqrt(1−wn)]×1/wnSDk[sqrt(1-w^{n})]×1/w^{n}SDk[sqrt(1−wn)]×1/wn$klog(1-z)/[log(1-b)]) if w^n\ll1then, k \approx log(1-z)E(k) $其中bwn其中b w^n其中bwn具体公式推导啥的还是子集看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.