随机抽样一致

随机抽样一致算法RANdom SAmple Consensus,RANSAC)。它采用迭代的方式从一组包含离群的被观测数据中估算出数学模型的参数。 RANSAC是一个非确定性算法,在某种意义上说,它会产生一个在一定概率下合理的结果,而更多次的迭代会使这一概率增加。此RANSAC算法在1981年由Fischler和Bolles首次提出。

RANSAC的基本假设是

  1. 内群”(inlier, 似乎译为内点群更加妥当,即正常数据,正确数据)数据可以通过几组模型的参数来叙述其分布,而“离群”(outlier,似乎译为外点群更加妥当,异常数​​据)数据则是不适合模型化的数据。
  2. 数据会受噪声影响,噪声指的是离群,例如从极端的噪声或错误解释有关数据的测量或不正确的假设。
  3. RANSAC假定,给定一组(通常很小)的内点群,存在一个程序,这个程序可以估算最佳解释或最适用于这一数据模型的参数。

范例

这里用一个简单的例子来说明,在一组数据点中找到一条最适合的线。假设,此有一组集合包含了内点群以及外点群,其中内点群包含可以被拟合到线段上的点,而外点群则是无法被拟合的点。如果我们用简单的最小二乘法来找此线,我们将无法得到一条适合于内点群的直线,因为最小二乘法会受外点群影响而影响其结果。而用RANSAC,可以只由内点群来计算出模型,而且概率还够高。然而,RANSAC无法保证结果一定最好,所以必须小心选择参数,使其能有足够的概率。

概述

  1. 在数据中随机选择若干个点设定为内点群
  2. 计算拟合内点群的模型
  3. 把其它刚才没选到的点带入刚才建立的模型中,计算是否属于内点群
  4. 记下内点群数量
  5. 重复以上步骤
  6. 比较哪次计算中内点群数量最多,内点群最多的那次所建的模型就是我们所要求的解

这里有几个问题

  1. 一开始的时候我们要随机选择多少点(n)
  2. 以及要重复做多少次(k)

参数决定

假设每个点是真正内点群的几率是  ,则:

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

通常我们不知道   是多少,  是所选择的   个点都是内点群的几率,  是所选择的   个点至少有一个不是内点群的几率,  是表示重复   次都没有全部的   个点都是内点群的几率,假设算法跑   次以后成功的几率是  ,那么:

 
 
 

所以如果希望成功几率高, , 当   不变时,  越大,  越大, 当   不变时,  越大,所需的   就越大, 通常   未知,所以   选小一点比较好。

应用

RANSAC算法经常用在计算机视觉领域,例如,对于一对立体相机,同时求解其对应点问题英语Correspondence_problem和估计它们之间的基础矩阵

参考资料

外部链接