引例——外点

我们知道,在得到一些数据进行参数估计时,总会出现一些异常的点,可能会导致最终的模拟的模型偏离理性模型。

当然为了解决这一问题,已经提出了几种启发式方法。通常采用的技术是首先使用所有数据推导出模型参数,然后定位与实例化模型最不一致的数据,假设它是一个严重错误,删除它,并重复这个过程直到最大偏差小于某个预设阈值或直到没有足够的数据继续进行。但是这种做法,仍然不能解决严重偏差的数据带来的影响。

我们来感受一下最小二乘法通过”平均“消除偏差,来拟合数据的弊端。

四次迭代,每次消除一个偏差点:

迭代消除偏差点

消除后图像上点的变化如下图所示:

最小二乘法通过”平均“消除偏差

最终理想的模型和实际拟合的模型对比如下:

理想的模型和实际拟合的模型对比

可以发现,由于一个严重错误点的存在,导致最小二乘法最终拟合的模型与理想模型出现严重的偏离。

因此,作者提出了RANSAC算法。

RANSAC算法

RANSAC(RANdom SAmple Consensus,随机采样一致)算法是 1981年发表的论文,RANSAC 过程与传统平滑技术相反:RANSAC 不是使用尽可能多的数据来获得初始解,然后尝试消除无效数据点,而是使用尽可能小的初始数据集,并且尽可能用一致的数据扩大这个集合。例如,给定将圆弧拟合到一组二维点的任务,RANSAC 方法将是选择一组三个点(因为需要三个点来确定一个圆),计算圆心和隐含圆的半径,并计算与该圆足够接近的点的数量以表明它们与它的兼容性(即,它们的偏差小到足以成为测量误差)。如果有足够的兼容点,RANSAC 将采用最小二乘法等平滑技术,在已经识别出一组相互一致的点后,计算对圆参数的改进估计。

符号约定

$P$:为“局部特征检测器”检测获得的所有数据,包括重大误差点;

$n$:为构建一个模型所需的最少数据,例如一个圆需要 $3$ 个点才能确定下来,那么 $n=3$;

  • 注意:RANSAC算法第一次拟合模型 圆 时,用的数据只有 $n=3$ 个,但是第二次、第三次…..拟合所用的数据会更多 $n>3$。

$S1$:内点的集合;

$M1$:每次迭代后,拟合出的那个模型;

$the\ error\ tolerance$ :容限误差,论文中没有提到用什么符号表示,我假设用 “$\epsilon $” 表示。当一个点与模型的残差小于ε ,那么我就判定该点为内点,否则为外点;

$t$:阈值,当内点的数量大于t时,判定拟合出的那个模型合理,否则不合理;

算法流程

  1. 假设我们需要将 $P$ 个数据点 $\{x_1,x_2,···,x_n\}$ 拟合一个至少 $n$ 个点决定的模型 ($P\ge n$,对于圆来说,$n=3$)
  2. 设迭代计数 $k=1$
  3. 从 $P$ 中随机选取 $n$ 个点拟合一个模型,记为 $M1$
  4. 给定容限误差 $\epsilon$ ,计算数据点 $\{x_1,x_2,···,x_n\}$ 中相对于模型的残差在偏差 $\epsilon$ 内的元素个数,称之为内点,如果内点个数大于阈值 $t$ ,根据内点集合重新拟合模型(可以使用最小二乘法或其变种进K行拟合),算法终止;
  5. 设 $k=k+1$ ,如果 $k$ 小于预设的 $K$ ,跳至第 $3$ 步,新的内点集合和模型分别记为 $S1^*$ 和 $M1^*$;否则采用具有当前内点最多的点集的模型,或者算法失败;

拟合模型圆

迭代以上步骤,把具有最小残差和的或是最多内点数的模型作为最佳模型。

RANSAC是一种概率算法,为了能确保有更好的概率找到真正的内点集合,必须实验足够多的次数。以下为试验次数的计算过程:
1、假设每次选取测量点都是相互独立的,且每个测量点为内点的概率均为 $w$,$p$ 为经过 $k$ 次试验后成功的总体概率;
2、那么在某次实验中,$n$ 个随机样本都是内点的可能性是$w^n$(这里 $n$ 表示为拟合该模型需要的最少数据个数);
3、因此经过了 $p$ 次试验,失败的概率是:

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

得到最少需要的试验次数为:

$$ k=\frac{\log(1-p)}{\log(1-w^n)} $$

事实上,这个k值被看作是选取不重复点的上限,因为这个结果假设n个点都是独立选择的,也就是说,某个点被选定之后,它可能会被后续的迭代过程重复选定到。而数据点通常是顺序选择的。

核函数

SLAM中的很多状态估计都是以最小化误差平方和作为代价函数,一个偏离较大的外点会对估计结果产生巨大的影响。比如特征点的提取,我们很难保证不出现一些比较离谱的数据。

而M估计的主要思想便是将原先误差的平方项替换为一个增长没那么快的函数,同时保证自己的光滑性质(能求导),获得更加鲁棒的最小二乘,这个函数又称为鲁棒核函数。

_images/loss.png

图片来源:http://ceres-solver.org/nnls_modeling.html#instances
🧐 本文作者:
😉 本文链接:https://lukeyalvin.site/archives/83.html
😊 版权说明:本博客所有文章除特别声明外,均默认采用 CC BY-NC-SA 4.0 许可协议。
最后修改:2022 年 07 月 12 日
赏杯咖啡