RANSAC - Random sample consensus

随机抽样一致性算法。
在对应点估计或者stereo matching中常常在用。这里进行一些知识点的归纳
先看基本思想，以下大部分翻译自wikipedia。

RANSAC算法是采用迭代的算法从一组包含离群点的被观测数据中估计一个数学模型的参数。RANSAC算法只会产生一个在一定概率下合理的结果，而更多次的迭代会使得这一概率增加。

RANSAC算法的基本假设是：

• “inliers”（内群）数据可以通过几组模型的参数来叙述其分布，而“outliers”（离群）数据则是不适合模型化的数据。
• 数据会受到噪声的影响，噪声指的是离群，例如从极端的噪声或错误解释有关数据的测量或不正确的假设。
• RANSAC假定，给定一组（通常很小）的内存，存在一个程序，可以估算最适用于这一组数据模型的参数。

RANSAC算法的基本步骤是：

1. 在数据中随机选择几个点设定为内群 - hypothetical inliers
2. 计算拟合内群的模型。
3. 把其他刚才没选到的点带入刚才建立的模型中，计算是否为内群。
   根据一些模型特定的损失函数(model specific loss function)，符合估计模型的那些点被认为是内群(consensus set)的一部分
4. 记下内群数量。
5. 重复以上步骤多做几次。
6. 比较哪次计算中内群数量最多，内群最多的那次所建的模型就是所要求的解。

小结：RANSAC是一种使用了投票机制（voting scheme）来寻找最佳结果的学习技术（learning technique）。
以从下图数据的拟合直线问题来看RANSAC：

line fitting

若使用Least squares method（最小二乘法），那么outliers会影响到最后的估计结果。
若使用RANSAC算法则不会有这样的问题。

Pesudo-code

    Given:
            data - a set of observed data points
            model - a model that can be fitted to data points
            n - the minimum number of data values required to fit the model
            k - the maximum number of iterations allowed in the algorithm
            t  - a threshold value for determining when a data point fits a model
            d - the number of close data values required to assert that a model fits well to data
    Return:
            bestfit - model parameters which best fit the data (or nul if no good model is found)
    
    iterations = 0
    bestfit = nul
    besterr = something really large
    while iterations < k {
            maybeinliers = n randomly selected values from data
            maybemodel = model parameters fitted to maybeinliers
            alsoinliers = empty set
            for every point in data not in maybeinliers {
            if point fits maybemodel with an error smaller than t
                     add point to alsoinliers
            }
            if the number of elements in alsoinliers is > d {
                % this implies that we may have found a good model
                % now test how good it is
                bettermodel = model parameters fitted to all points in maybeinliers and alsoinliers
                thiserr = a measure of how well model fits these points
                if thiserr < besterr {
                    bestfit = bettermodel
                    besterr = thiserr
                }
          }
          increment iterations
    }

matlab code: click here

最后，讨论一下RANSAC中的参数：
t和d需要结合实际的实验数据以及具体应用来决定。迭代次数k，可以从进行一定的理论分析。
假设数据集中每个点是真正内群的概率是w， 即：

    w = 真正内群点的数目/数据总共的数量

假设不知道w的值，那么选择n个点都是内群点的概率为w^n，那么选择n个点至少有一个是非内群点的概率为 1-w^n；重复k次都没有全部的n个点都是内群的概率是 (1-w^n)^k是表示重复k次，都至少有一个点是离群点，因此，RANSAC迭代k次后，n个点都是内群点的概率p的值是：

     1 - p = (1-w^n)^k 
     p = 1 - (1-w^n)^k

若希望成功率高的话，p = 0.99，当n不变，那么k越大，p越大；但w不变，n越大，那么k越大。