RANSAC(随机抽样一致性算法)的原理及其在 SIFT 特征点匹配中的应用

喜欢ヅ旅行 2022-02-19 16:31 355阅读 0赞

# RANSAC(随机抽样一致性算法) #

## 1. OverView ##

RANSAC（RANdom SAmple Consensus， 译作 随机抽样一致性算法）是由Fischler和Bolles于1981年最先提出。它是根据一组包含异常数据的样本数据集，计算出数据的数学模型参数，得到有效样本数据的算法。  
该算法在计算机视觉的匹配问题中（比如相机配准， 特征点匹配等）被用来寻找最佳的匹配模型。

## 2. RANSAC算法 ##

对于一组观测数据和一个用于解释观测数据的参数化模型， 所以满足该模型的点为局内点，反之则为局外点。  
RANSAC算法的输入是一组观测数据（往往含有较大的噪声或无效点），一个用于解释观测数据的参数化模型以及一些可信的参数。RANSAC通过反复选择数据中的一组随机子集来达成目标。被选取的子集被假设为局内点，并用下述方法进行验证：

1.  有一个模型适应于假设的局内点，即所有的未知参数都能从假设的局内点计算得出。
2.  用1中得到的模型去测试所有的其它数据，如果某个点适用于估计的模型，认为它也是局内点。
3.  如果有足够多的点被归类为假设的局内点，那么估计的模型就足够合理。  
    然后，用所有假设的局内点去重新估计模型（譬如使用最小二乘法），因为它仅仅被初始的假设局内点估计过。
4.  最后，通过估计局内点与模型的错误率来评估模型。  
    上述过程被重复执行固定的次数，每次产生的模型要么因为局内点太少而被舍弃，要么因为比现有的模型更好而被选用。

举一个具体的例子， 比如利用RANSAC进行 SIFT 特征点匹配。

1.  在我们的匹配点中随机选择4对点。这四对叫做局内点或者内点，而其他的匹配点叫做局外点或者外点
2.  根据4对内点得到内部的单应性矩阵
3.  使用这个计算出的单应性矩阵测试所有其他外点，通过一个阈值将所有的外点分为两部分：

*  a 所有满足这个单应性的外点被归为是新的内点
 *  b 而所有不满足的外点被归为新的外点

1.  获取我们所有的内点（新的内点+旧的内点）并转到步骤2
2.  只要没有更改或我们已经迭代步骤2-步骤4 k次，结束迭代。  
    最终的单应矩阵将是我们想要的。

Given:
        data – a set of observations
        model – a model to explain observed data points
        n – minimum number of data points required to estimate model parameters
        k – maximum number of iterations allowed in the algorithm
        t – threshold value to determine data points that are fit well by model 
        d – number of close data points 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 betterModel fits these points
            if thisErr < bestErr {
                bestFit = betterModel
                bestErr = thisErr
            }
        }
        increment iterations
    }
    return bestFit

## 3. 参数选择 ##

从上面的RANSAC算法的过程知道，至少有两个参数需要确定：  
\-1. 阈值  
阈值由具体的应用和数据集决定，一般是一个经验值。  
\-2. 迭代次数k  
因为在实际应用中样本数通常会很大，那么从其中任选n个数据点（上面例子中为4对点）的组合就会很大，如果对所有组合都进行上面的操作（步骤2-步骤4）运算量就会很大，因此对于k的选择就很重要。通常情况下，只要保证模型估计需要的n个点都是内点的概率足够高即可。因此设w为N个数据中局内点的比例，z为进行k次选取后，至少有一次选取的n个点都是局内点的概率。则有  
 z = 1 − ( 1 − w n ) k z=1−(1−w^n)^k z=1−(1−wn)k  
其中 1 − w n 1−w^n 1−wn表示一次选取不都是局内点的概率， ( 1 − w n ) k (1−w^n)^k (1−wn)k 表示k次选取中没有一次都是局内点的概率。 则有  
 k = l o g ( 1 − z ) l o g ( 1 − w n ) k = \\frac \{log(1−z)\} \{log(1−w^n)\} k=log(1−wn)log(1−z)  
这里z一般要求满足大于95%即可.因此k的取值可以计算得出。

## 4. RANSAC 与 Least Squares Fit（最小二乘法）的区别 ##

最小二乘法只适合于误差较小的情况。试想一下这种情况，假使需要从一个噪音较大的数据集中提取模型（比方说只有20%的数据是符合模型的）时，最小二乘法就显得力不从心了。例如下图，肉眼可以很轻易地看出一条直线（模式），但算法却找错了。 而RANSAC算法的输入是一组观测数据（往往含有较大的噪声或无效点），一个用于解释观测数据的参数化模型以及一些可信的参数。RANSAC通过反复选择数据中的一组随机子集来达成目标。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2t1d2VpY2Fp_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2t1d2VpY2Fp_size_16_color_FFFFFF_t_70 1]

## 5. RANSAC 的优缺点 ##

RANSAC的一个优点是它能够对模型参数进行稳健估计，即，即使在数据集中存在大量异常值时，它也能够以高精度估计参数。  
RANSAC的一个缺点是计算这些参数所花费的时间没有上限（耗尽除外）。当计算的迭代次数受到限制时，所获得的解决方案可能不是最佳的，并且它甚至可能不是以良好方式拟合数据的解决方案。通过这种方式，RANSAC提供了权衡;通过计算更多次迭代，产生合理模型的概率增加。此外，即使对于中度污染的集合，RANSAC也不总能找到最佳集合，比如当内部（内点）数量小于50％时，它通常表现不佳。  
最佳RANSAC 被提出用于处理这两个问题，并且能够为严重污染的集合找到最佳集合，即使对于低于5％的内部比率。  
RANSAC的另一个缺点是它需要设置特定于问题的阈值。  
RANSAC只能为特定数据集估计一个模型。对于存在两个（或更多）模型实例的任何单模型方法，RANSAC可能无法找到任何一个。霍夫变换是一种可选的稳健估计技术，当存在多个模型实例时可能是有用的。多模型拟合的另一种方法被称为PEARL，它将RANSAC中的数据点的模型采样与内部的迭代重新估计相结合，多模型拟合被公式化为具有全局能量函数的优化问题。

## 6. 参考 ##

[1. wiki][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2t1d2VpY2Fp_size_16_color_FFFFFF_t_70]: /images/20220219/fb1d06bec23649caa5a14263c8deebac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2t1d2VpY2Fp_size_16_color_FFFFFF_t_70 1]: /images/20220219/5f982d51407a4871a5a1cd2323dcf14f.png
[1. wiki]: https://en.wikipedia.org/wiki/Random_sample_consensus