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 不再问"这里的自相关矩阵长什么样",而是问一个几何问题:在以候选像素 为中心、半径为 3 的 Bresenham 圆上,是否存在一段连续的圆弧,其亮度显著地全都比 亮或全都比 暗?
Bresenham 圆的 16 个像素按顺时针编号 1 到 16:
16 1 2
15 3
14 4
13 p 5
12 6
11 7
10 9 8
给定阈值 ,把 16 个像素分成三类:
如果连续 个像素同属 darker 或同属 brighter, 就是一个角点。原论文默认 ,后来的 FAST-9()在 repeatability 上表现更好,成为 OpenCV 的默认。
2. 为什么这个准则能抓角点
想象一个直角楔形——像素 处在楔尖内侧。绕 转一圈,圆弧的一部分穿过楔子外面(亮),另一部分穿过楔子内部(暗)。至少有一段连续圆弧的亮度是一致地偏离 的。而在边缘上,圆弧被对半分成两段,最长的连续同色弧长约为 8;在平坦区域,同色弧长可以任意长,但因为亮度与 相近(similar),不算 darker/brighter。这个"12 个连续"的门槛正好卡在直角以内、边缘以外。
越大越保守,检出的角点越少但越尖锐; 越小越激进,也越容易被边缘和噪声骗到。 是训练出来的实用最优点。
3. 高速剪枝:先测 4 个点
朴素算法要对 16 个像素做比较,但绝大多数像 素并不是角点,判定时不该花全部代价。Rosten 的第一个优化是先测 1、5、9、13 号像素(圆上对称的四个点):
- 如果 12 个连续满足条件成立,那么这 4 个点里至少 3 个必须同属 brighter 或同属 darker
- 换言之,如果这 4 个点里 brighter 数 < 3 且 darker 数 < 3, 立刻被判非角点,不再检查剩下 12 个像素
对于 ,条件放宽到 4 个点里至少 2 个同属一类。这一步剪掉了图像里 90% 以上的候选像素,是 FAST 快的第一个来源。
4. 机器学习加速:决策树版本
论文的第二部分才是真正的巧思。人工写的"先测 4 个点再测其他"顺序未必最优——最优顺序依赖于目标图像的统计特性。Rosten 用 ID3 训练了一棵决策树:
- 训练样本是若干图像上所有像素的 16 元组 ,每个 (darker/similar/brighter)
- 标签是" 是不是 FAST 角点"
- 用信息增益选下一个要测的像素
学出来的决策树对当前场景是熵最小的测试顺序,每个像素平均只需要测 2.26 个圆上像素就能判定。这就是 OpenCV cv::FAST 里的 type == TYPE_9_16 分支的做法——它内部展开了一棵极深的 if-else 树,代码由训练结果自动生成。
作者把训练脚本和生成的 C 代码都开源了,任何人可以针对自己的图像集重新训一棵。工程上大部分场景直接用默认树,效果就已经很好。
5. 非极大值抑制的难题
FAST 的判定是二值的——像素要么是角点要么不是。这带来一个 Harris/Shi-Tomasi 没有的问题:在真正的角点附近,往往一整片相邻像素都通过了测试,得到一坨角点而不是一个。
要 NMS 就必须先给每个候选一个响应分数 。原论文提出的分数是"能让 仍被判为角点的最大阈值 ":
等价定义(更常用):
选圆上 brighter/darker 两类里累加绝对差更大的那一类,减去阈值。这个 是启发式的,没有 Harris 那种"自相关矩阵特征值"的清晰几何含义——它只是一个能排序的量。实践上够用,但 FAST 输出的响应图不平滑,多尺度金字塔上做 NMS 时角点位置的稳定性明显不如 Harris。这也是后来 ORB 要在 FAST 之上再套一层 Harris 响应重排序的原因。
6. FAST-ER:训练检测器本身
2008 年 Rosten 再发了 FASTER and better: A machine learning approach to corner detection(后来收在 PAMI),把训练目标从"决策顺序"上升到"检测器定义本身":
- 不再固定 、不再固定 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 重排 | rBRIEF | Oriented FAST + Rotated BRIEF,OpenCV 主力 |
| BRISK (2011) | AGAST (FAST 变体) | BRISK 二进制串 | 尺度空间上的 FAST |
| FREAK (2012) | 任意 | 视网膜采样二进制 | 常配 FAST |
| ORB-SLAM2/3 | FAST-9 | ORB | 学术界事实标准 |
ORB 里的 Harris 重排是必要的:FAST 输出的响应值不稳定,直接按 FAST 分数排会挑到边缘上的伪角点。给每个 FAST 点算一次 Harris 响应 ,按 Harris 分数取 top-N,兼顾了 FAST 的速度和 Harris 的判别力。
8. 为什么比 Harris 快 10–100 倍
对每个像素:
- Harris: 邻域算 (两次卷积),构造 矩阵 (三次乘加与高斯加权求和),求响应 。约 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 或 双边滤波。 的高斯基本够用。
- 不天然多尺度:单尺度 FAST 只找当前分辨率下的角点。要做匹配必须自己搭金字塔,逐层跑 FAST(这也是 ORB 的做法,一般 8 层,缩放因子 1.2)。
- 不天然带方向:需要在检测后另算方向。ORB 用灰度质心法——计算 patch 的一阶矩 ,方向 。
- 响应分数不平滑:如需高精度定位,建议 FAST 出粗位置后再用 亚像素级角点 精化。
- 参数只有一个 :直观但也粗糙。经验值 到 (0–255 图像),噪声大的场景取大值。
10. 一个思维实验:FAST 是不是"角点"检测器
FAST 的准则里没出现"角"这个字,也没有微分几何含义。它检测的其实是"中心像素与圆上大多数像素亮度显著不同"的模式——包括真正的角点、也包括圆点、斑点,甚至粗线的端点。这既是它的弱点(选择性差,比 SUSAN 更缺几何解释)也是它的强项(对各种"局部显著点"都响应,实际上做特征匹配时反而更鲁棒)。
从这个角度看,FAST 更接近一个兴趣点(interest point)检测器而不是严格的角点检测器。Rosten 的原论文标题就叫 "corner detection",但引言里马上把它松绑到 "features"。工程实践中,只要下游描述子能吃这些点、匹配稳定,就算成功——精确的几何定义反而次要。这也是 2010 年代之后特征点检测领域的整体走向:从追求"数学上正确的角点"(Harris)到追求"匹配好用的兴趣点"(FAST, SIFT, SuperPoint)。