RANSAC：随机抽样一致算法

发表于 更新于 分类于 ，
通过迭代的方式从含有离群点的噪声数据中拟合出数学模型参数，通常用在图像对应点确定并由此求解基础矩阵等应用中。

数据噪声与鲁棒估计

数据的噪声在真实世界中是无法绕开的问题。对于各类机器学习建模问题来说，通常都需要收集一定量的数据，而由于数据采集方法的固有缺陷、偶发的失误（比如测量工具在某些环境下失灵，从而不能给出正确结果）、测量误差等因素，数据中通常会带有各类噪声。

通常来说的数据噪声指的是由于测量误差，或者数据本身的随机性带来的与理想模型的失配。比如：如果我们想要建模力与加速度的关系，就需要一定数量的\(\{F_i, a_i\}\)的数据对，用来进行回归（regress）。但是由于对力的测量（比如通过弹簧秤）以及对加速度的测量（比如通过固定距离+计时器）这两者都会引入人为的误差，从而即便模型拟合的很好，也会与实测数据有差异。这种数据的噪声可以通过回归类的方法（比如最小二乘法等）进行处理，直观来看就是数据“围绕着”模型随机分布。如图所示。

回归中的带噪数据

然而除此之外，还有另一种更加令人困扰的数据噪声，通常称为异常值（anomaly），或者离群点（outlier，在有些场合也被翻译为野值，外点）。它的特点是完全无法用其他数据得到的模型建模，即不符合模型参数和假设，从而不能被考虑到建模过程中（一旦被考虑进去，就会影响其他正常值的建模效果）。举例来说，噪声就相当于弹簧秤读数的误差，而离群点相当于某次弹簧秤被卡住而给出一个错误的数值。带有离群点的噪声数据如下图所示。

带有离群点的训练数据

对于这种离群点的处理方式的总原则是将其识别出来，不让其参与模型参数的优化。这种操作通常称为异常检测（anomaly detection），而可以不受（或者尽可能少受到）离群点干扰的模型，我们称为对与离群点比较鲁棒（robust）。

但是一般的建模都需要利用全量数据进行，因此必然会受到离群点的影响，一个自然的思路就是：既然符合模型的点（非离群点，通常称为内点，inlier）总是比较多的，因此我们随机选一些点，大概率会选到内点，用它们建模后，再去看哪些点最不符合模型，这些点就是离群点。由此思路出发并详细设计，就可以得到本文中将要讲到的RANSAC算法。

RANSAC基本原理与分析

基本思路

RANSAC是随机抽样一致（RANdom SAmple Consensus）的缩写。其思路的核心在于：重复随机的子采样（sub-sampling）。这个可以进行的前提条件是，我们认为离群点明显偏离模型，而且内点数量足够多（足够拟合出对应的模型）。因为事先无法知道哪些样本是内点/外点，因此需要先验地知道数据的模型类型（比如是线性的还是二次的？），并且通过随机采样数据拟合模型来推理出哪些点不符合模型，从而将其筛选出来，不用来进行建模。

随机采样一部分数据的问题在于：有可能会采样到外点，从而拟合模型会有偏差。解决这个问题的思路就是：多次重复采样，并对于每次采样的效果进行评估，所谓的效果评估就是看有多少样本点是符合当前模型的，符合的越多说明越接近真实模型，而符合模型的点也可以当做内点被筛选出来；而那些不符合模型的则可能是外点，因为这里假设外点不能被模型捕获。

算法流程

RANSAC算法整体流程如下：

  1. 确定要拟合的模型类型\(M(x;\theta)\)，比如线性模型等（这一步可能影响后续采样点数的选择）；
  2. 在所有样本数据集\(D=\{x_i, y_i\}\)中随机抽取\(k\)个样本数据\(x_i\)（注意这里的\(k\)应当足够用来拟合目标模型）；
  3. 用1中得到的样本数据来拟合目标模型，得到模型参数\(\theta_{opt}\) ，该模型记为\(M(x,\theta_{opt})\);
  4. 确定所有数据中有多少个点符合该模型，这里的“符合”指的是\(d(y_i, M(x_i,\theta_{opt})) < \epsilon\)，其中\(d\)为某种损失函数，\(\epsilon\)为预先设定好的tolerance参数，符合模型的点就是我们估计的内点，这个点集称为consensus set，即一致集。
  5. 如果估计的内点超过了一定的阈值\(thr\)，则说明这个模型参数还是比较准确的，因此估计的内点也准确度较高，我们用所有符合模型的内点组成的集合\(D_{in}\)重新对模型参数进行估计，得到\(M(x, \theta_{opt}^{'})\)。就是所需的模型（排除了outlier的干扰）。用该模型估计拟合效果\(m\)（这里的\(m\)是一个用来度量模型对数据拟合效果的一个测量指标）；
  6. 重复1-4步骤\(N\)个迭代次数，并更新最优的拟合效果\(m_{best}\)（该值保持所有迭代次数中最优的\(m\)值）。迭代结束后，最优的拟合效果对应的参数就是最终的输出结果。

在不同的地方或者对于不同的任务，可能与上述过程由微小差异，但整体思路是类似的。

参数分析

RANSAC模型本质上是以一定概率去鲁棒拟合带噪数据中的真实模型参数的，也就是说，不能保证其最终一定可以得到正确的结果。但是只要采样次数够多，并且设计好参数，那么通常会收敛到符合要求的结果。下面简单分析一些参数的影响。

假设数据集\(D\)中，真实的内点率（内点占总体的比例）为\(p\)，每次取样点数为\(k\)，总共迭代\(N\)次，那么，我们认为只要有一次采样拟合中，全部采样到内点，RANSAC就算成功了（因为我们记录的是拟合效果最优的模型，当然前提条件是拟合效果的评估足够准确）。

将RANSAC成功率记为\(p_{succ}\)，考虑到一次实验中，采样的\(k\)个点全是内点的概率为\(p^k\)，那么相反地，至少采样到一个outlier的概率为\(1-p^k\)，对于\(N\)次迭代，每次实验都采到outlier（即每次都不成功）的概率为\((1-p^k)^N\)，同样相反地，至少有一次成功的概率为\(1-(1-p^k)^N\)。而只要一次成功，RANSAC就成功了。因此我们有： \[ p_{succ} = 1 - (1-p^k)^N \] 根据此式分析：

  • 如果\(p\)越大，右边的括号内的项就越小，从而成功率越大。这和直觉相符，即outlier比例越低，越容易收敛。
  • 如果\(p\)固定，\(k\)越小右边括号内的项越小，从而成功率越大，而\(N\)越大，右边减号后面整体越小，成功率越大。也就是说，我们应该尽可能采取“少量多次”的策略，才能提高成功率。

算法局限

RANSAC的几个主要局限：

  • 概率收敛，运气不好的时候会迭代很多很多次才能成功（尽管是小概率），通常设定最大迭代次数，也就意味着有时RANSAC会不成功；
  • 内点比例少的时候（<50%），可能收敛不到最优；
  • 只适用于单模型，如果数据符合多模型结构，则没法处理；

简单的代码实例

下面是RANSAC的一个简单的Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import numpy as np
import matplotlib.pyplot as plt
from sklearn.linear_model import LinearRegression


def ransac_line_fit(x, y, k, n_iter, tolerance, consensus_thr):
    n_pt = len(x)
    best_model = None
    best_metric = np.inf
    for iter in range(n_iter):
        sample_idx = np.random.permutation(range(n_pt))[:k]
        x_sample = x[sample_idx]
        y_sample = y[sample_idx]
        model = LinearRegression().fit(x_sample, y_sample)
        consensus_idx = np.where(np.sqrt((y - model.predict(x)) ** 2) < tolerance)[0]
        # print(np.sqrt((y - model.predict(x)) ** 2))
        # print(consensus_idx)
        if len(consensus_idx) > consensus_thr:
            x_con = x[consensus_idx]
            y_con = y[consensus_idx]
            con_model = LinearRegression().fit(x_con, y_con)
            metric = np.mean(np.sqrt((y_con - con_model.predict(x_con)) ** 2))
            if metric < best_metric:
                best_metric = metric
                best_model = con_model
    return best_model, best_metric

if __name__ == "__main__":

    slope = 5
    inlier_eps = 2
    outlier_eps = 20
    inlier_ratio = 0.2
    x = np.arange(0, 6, 0.1)
    n = np.array([np.random.randn() for _ in range(len(x))])
    y = slope * x + inlier_eps * n

    n_y = len(y)
    n_inliers = int(n_y * inlier_ratio)
    sel_idx = np.random.permutation(range(n_y))[:n_inliers]
    y[sel_idx] += np.array([np.random.randn() * outlier_eps for _ in range(n_inliers)])

    model, _ = ransac_line_fit(x.reshape(-1, 1), y, 20, 50, 8, 10)
    if model is not None:
        y_pred = model.predict(x.reshape(-1, 1))
    else:
        raise ValueError

    plt.figure()
    plt.plot(x, y, 'ob')
    plt.plot(x, y_pred, 'r')
    plt.show()

运行结果如图：

RANSAC拟合结果

Changelog:

v1: 2023年12月26日23:52:53 文档初版

v2: 2024年01月04日10:50:55 添加示例代码和结果