跳到主要内容

FAST 角点检测:为 SLAM 而生的速度怪兽

2006 年 Rosten 与 Drummond 在 ECCV 上发表 Machine learning for high-speed corner detection,提出了 FAST(Features from Accelerated Segment Test)。这个名字直白得几乎不像论文——它就是想要"快"。当时的背景是:视觉 SLAM、AR、无人机上的实时定位刚开始起步,Harris 和 Shi-Tomasi 精确、稳定,但对每像素都要算二阶矩矩阵、求特征值,一帧 640×480 的画面在当年的嵌入式硬件上跑不到 30 fps。FAST 把每个像素的判定简化成对 16 个邻居的整数比较,一路把速度拉到 Harris 的 10–100 倍。

1. 核心思想:分段测试​

FAST 不再问"这里的自相关矩阵长什么样",而是问一个几何问题:在以候选像素 pp 为中心、半径为 3 的 Bresenham 圆上,是否存在一段连续的圆弧,其亮度显著地全都比 pp 亮或全都比 pp 暗?

Bresenham 圆的 16 个像素按顺时针编号 1 到 16:

              16  1  2
15 3
14 4
13 p 5
12 6
11 7
10 9 8

给定阈值 tt,把 16 个像素分成三类:

Sp→x={darker,Ix≤Ip−tsimilar,Ip−t<Ix<Ip+tbrighter,Ip+t≤IxS_{p \to x} = \begin{cases} \text{darker}, & I_x \le I_p - t \\ \text{similar}, & I_p - t < I_x < I_p + t \\ \text{brighter}, & I_p + t \le I_x \end{cases}

如果连续 NN 个像素同属 darker 或同属 brighter,pp 就是一个角点。原论文默认 N=12N=12,后来的 FAST-9(N=9N=9)在 repeatability 上表现更好,成为 OpenCV 的默认。

2. 为什么这个准则能抓角点​

想象一个直角楔形——像素 pp 处在楔尖内侧。绕 pp 转一圈,圆弧的一部分穿过楔子外面(亮),另一部分穿过楔子内部(暗)。至少有一段连续圆弧的亮度是一致地偏离 pp 的。而在边缘上,圆弧被对半分成两段,最长的连续同色弧长约为 8;在平坦区域,同色弧长可以任意长,但因为亮度与 pp 相近(similar),不算 darker/brighter。这个"12 个连续"的门槛正好卡在直角以内、边缘以外。

NN 越大越保守,检出的角点越少但越尖锐;NN 越小越激进,也越容易被边缘和噪声骗到。N=9N=9 是训练出来的实用最优点。

3. 高速剪枝:先测 4 个点​

朴素算法要对 16 个像素做比较,但绝大多数像素并不是角点,判定时不该花全部代价。Rosten 的第一个优化是先测 1、5、9、13 号像素(圆上对称的四个点):

  • 如果 12 个连续满足条件成立,那么这 4 个点里至少 3 个必须同属 brighter 或同属 darker
  • 换言之,如果这 4 个点里 brighter 数 < 3 且 darker 数 < 3,pp 立刻被判非角点,不再检查剩下 12 个像素

对于 N=9N=9,条件放宽到 4 个点里至少 2 个同属一类。这一步剪掉了图像里 90% 以上的候选像素,是 FAST 快的第一个来源。

4. 机器学习加速:决策树版本​

论文的第二部分才是真正的巧思。人工写的"先测 4 个点再测其他"顺序未必最优——最优顺序依赖于目标图像的统计特性。Rosten 用 ID3 训练了一棵决策树:

  • 训练样本是若干图像上所有像素的 16 元组 (x1,…,x16)(x_1, \dots, x_{16}),每个 xi∈{d,s,b}x_i \in \{d, s, b\}(darker/similar/brighter)
  • 标签是"pp 是不是 FAST 角点"
  • 用信息增益选下一个要测的像素

学出来的决策树对当前场景是熵最小的测试顺序,每个像素平均只需要测 2.26 个圆上像素就能判定。这就是 OpenCV cv::FAST 里的 type == TYPE_9_16 分支的做法——它内部展开了一棵极深的 if-else 树,代码由训练结果自动生成。

作者把训练脚本和生成的 C 代码都开源了,任何人可以针对自己的图像集重新训一棵。工程上大部分场景直接用默认树,效果就已经很好。

5. 非极大值抑制的难题​

FAST 的判定是二值的——像素要么是角点要么不是。这带来一个 Harris/Shi-Tomasi 没有的问题:在真正的角点附近,往往一整片相邻像素都通过了测试,得到一坨角点而不是一个。

要 NMS 就必须先给每个候选一个响应分数 VV。原论文提出的分数是"能让 pp 仍被判为角点的最大阈值 tt":

V=max⁡{t:p 仍是 N-段角点}V = \max\left\{ t : p \text{ 仍是 } N\text{-段角点} \right\}

等价定义(更常用):

V=max⁡(∑x∈Sbright∣Ix−Ip∣−t,  ∑x∈Sdark∣Ip−Ix∣−t)V = \max\left( \sum_{x \in S_{\text{bright}}} |I_x - I_p| - t,\; \sum_{x \in S_{\text{dark}}} |I_p - I_x| - t \right)

选圆上 brighter/darker 两类里累加绝对差更大的那一类,减去阈值。这个 VV 是启发式的,没有 Harris 那种"自相关矩阵特征值"的清晰几何含义——它只是一个能排序的量。实践上够用,但 FAST 输出的响应图不平滑,多尺度金字塔上做 NMS 时角点位置的稳定性明显不如 Harris。这也是后来 ORB 要在 FAST 之上再套一层 Harris 响应重排序的原因。

6. FAST-ER:训练检测器本身​

2008 年 Rosten 再发了 FASTER and better: A machine learning approach to corner detection(后来收在 PAMI),把训练目标从"决策顺序"上升到"检测器定义本身":

  • 不再固定 N=9N=9、不再固定 Bresenham 圆,而是把"什么样的 16 元组算角点"作为标签空间
  • 用 simulated annealing 搜索最能提高 repeatability 的检测器规则

FAST-ER 在 repeatability 上比 FAST-9 又提升了 10–20%,代价是训练成本高。工程界大部分场景还是用 FAST-9,因为差距不足以抵消训练/复现的麻烦。

7. FAST 与 ORB / BRISK / SLAM 的关系​

FAST 本身不是描述子,它只回答"这里有没有兴趣点"。要做匹配还得配一个描述子:

系统检测器描述子说明
ORB (2011)FAST-9 + Harris 重排rBRIEFOriented FAST + Rotated BRIEF,OpenCV 主力
BRISK (2011)AGAST (FAST 变体)BRISK 二进制串尺度空间上的 FAST
FREAK (2012)任意视网膜采样二进制常配 FAST
ORB-SLAM2/3FAST-9ORB学术界事实标准

ORB 里的 Harris 重排是必要的:FAST 输出的响应值不稳定,直接按 FAST 分数排会挑到边缘上的伪角点。给每个 FAST 点算一次 Harris 响应 det⁡(M)−k tr(M)2\det(M) - k\,\mathrm{tr}(M)^2,按 Harris 分数取 top-N,兼顾了 FAST 的速度和 Harris 的判别力。

8. 为什么比 Harris 快 10–100 倍​

对每个像素:

  • Harris:3×33\times 3 邻域算 Ix,IyI_x, I_y(两次卷积),构造 2×22\times 2 矩阵 MM(三次乘加与高斯加权求和),求响应 det⁡−k tr2\det - k\,\mathrm{tr}^2。约 25–40 次浮点乘加。
  • FAST-9:先测 4 个像素(4 次整数比较),大部分像素被这一步判掉;剩下的进入决策树,平均再测 1–2 个像素。约 2.3 次整数比较,无乘法、无浮点。

差距不只是"少几次乘法",更关键的是 FAST 绝大多数像素在头几次比较后就跳出,分支预测器和 L1 cache 都对它极其友好。在 ARM Cortex 或 x86 上,Harris 需要 SIMD 才能追上标量 FAST 的速度。这也是 FAST 成为移动端 AR、无人机 VIO 首选的原因。

9. 弱点与工程建议​

  • 对高频噪声敏感:噪声容易让 similar 变成 brighter/darker,配 FAST 前建议先做一次 Gaussian 或 双边滤波。σ=1.0\sigma=1.0 的高斯基本够用。
  • 不天然多尺度:单尺度 FAST 只找当前分辨率下的角点。要做匹配必须自己搭金字塔,逐层跑 FAST(这也是 ORB 的做法,一般 8 层,缩放因子 1.2)。
  • 不天然带方向:需要在检测后另算方向。ORB 用灰度质心法——计算 patch 的一阶矩 m10,m01m_{10}, m_{01},方向 θ=arctan⁡(m01/m10)\theta = \arctan(m_{01}/m_{10})。
  • 响应分数不平滑:如需高精度定位,建议 FAST 出粗位置后再用 亚像素级角点 精化。
  • 参数只有一个 tt:直观但也粗糙。经验值 t=10t=10 到 3030(0–255 图像),噪声大的场景取大值。

10. 一个思维实验:FAST 是不是"角点"检测器​

FAST 的准则里没出现"角"这个字,也没有微分几何含义。它检测的其实是"中心像素与圆上大多数像素亮度显著不同"的模式——包括真正的角点、也包括圆点、斑点,甚至粗线的端点。这既是它的弱点(选择性差,比 SUSAN 更缺几何解释)也是它的强项(对各种"局部显著点"都响应,实际上做特征匹配时反而更鲁棒)。

从这个角度看,FAST 更接近一个兴趣点(interest point)检测器而不是严格的角点检测器。Rosten 的原论文标题就叫 "corner detection",但引言里马上把它松绑到 "features"。工程实践中,只要下游描述子能吃这些点、匹配稳定,就算成功——精确的几何定义反而次要。这也是 2010 年代之后特征点检测领域的整体走向:从追求"数学上正确的角点"(Harris)到追求"匹配好用的兴趣点"(FAST, SIFT, SuperPoint)。