FAST (Features from Accelerated Segment Test)

FAST（Rosten & Drummond, 2006）是一种专为一件事而设计的角点检测器：速度。它不像Harris/Shi-Tomasi那样计算图像梯度和结构张量，也不像SIFT那样构建尺度空间，而是通过对候选像素周围一个小圆上若干像素的强度比较来判定是否为角点——足够廉价，可以在高帧率下对每一帧的每个像素运行，这使它成为实时SLAM前端（PTAM、SVO，以及通过ORB衍生出的ORB-SLAM系列）默认使用的检测器。

分段测试（segment test）

考虑一个强度为 $I_p$ 的候选像素 $p$ ，以及以其为中心、半径为3的Bresenham圆上的16个像素。如果在该圆上存在一段至少 $n$ 个像素组成的连续弧，且这些像素相对于阈值 $t$ 都明显比 $p$ 更亮或都明显比 $p$ 更暗，则将 $p$ 判定为角点：

\forall x \in \text{arc}: \quad I_x > I_p + t \qquad \text{或} \qquad \forall x \in \text{arc}: \quad I_x < I_p - t

经典的选择是 $n = 12$ （FAST-12：16个像素中的12个），这允许一个非常有效的高速测试：只检查四个罗盘方向的像素（上、右、下、左——位置1、5、9、13）。如果存在一段12像素的连续弧，那么这四个像素中至少三个必须比 $I_p + t$ 更亮或比 $I_p - t$ 更暗；如果通过的少于三个， $p$ 在仅仅四次比较之后就会被拒绝。由于绝大多数图像像素都不是角点，这种早退机制主导了平均开销。

机器学习变体

手工编码的罗盘测试有两个弱点：它不能推广到 $n < 12$ 的情形，且固定的提问顺序对真实图像统计而言并非最优。因此Rosten和Drummond学习了这个检测器：圆上的16个像素相对于 $I_p$ 各自被分类为更亮/更暗/相似，并用一棵决策树（用ID3算法构建，最大化信息增益）学习出能以最少期望比较次数在训练图像上分类角点的像素查询顺序。这棵树被编译为嵌套的if语句。正是这种方式让FAST-9（ $n = 9$ ）——通常是最具可重复性的变体——变得实用，也正是OpenCV的cv::FastFeatureDetector所实现的内容。

非极大值抑制

分段测试会在单个角点周围的许多相邻像素上都触发响应。为了让每个角点只保留一个响应，需要为每个检测点计算一个角点分数，

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),

即支持弧的最大总对比度，然后非极大值抑制只保留 $V$ 在3×3邻域内的局部极大值。在SLAM前端中，检测结果还会额外在图像网格上分桶，使特征覆盖整个画面，而不是聚集在某一块纹理丰富的区域。

变体

FAST-9 / FAST-12：弧长 $n$ ；FAST-9检测到更多角点，通常可重复性最好，FAST-12即使没有学习得到的决策树也能使用四像素早退。
AGAST（Mair 等，2010）：用一棵能在运行时适应局部图像统计的通用决策树取代单一的训练树，去除了对训练图像的依赖（被BRISK采用）。
oFAST：ORB版本的FAST，加入了从图像块的强度质心得到的方向角，并在图像金字塔上进行检测，再用Harris响应对检测结果排序和裁剪。

FAST不能给你的东西

没有描述子——FAST只能找到位置；它需要与BRIEF/ORB配对使用，或用于为KLT轨迹或直接法对齐提供种子点。
没有尺度不变性——它需要在图像金字塔的每一层上运行以检测多个尺度的角点。
没有方向信息——ORB的oFAST通过图像块的强度质心添加了方向。
对阈值敏感——单一的全局 $t$ 在对比度变化的场景中表现不佳；实际系统会按图像块自适应调整 $t$ ，或在检测到的特征太少时放宽阈值（正如ORB-SLAM所做的那样）。

对SLAM的意义

特征检测在跟踪循环中对每一帧都要运行，因此其开销直接限制了嵌入式硬件上可达到的帧率。FAST让完整的检测-描述-匹配流水线在CPU上实现了实时运行——PTAM在跟踪中使用FAST，SVO用FAST角点作为深度滤波器的种子点，VIO前端（VINS-Mono、多种MSCKF实现）检测FAST角点并用KLT跟踪它们，而ORB（oFAST + rBRIEF）把它变成了ORB-SLAM系列的完整特征方案。理解分段测试同样能解释你在实践中会观察到的FAST的失效模式：在噪声下边缘处产生响应、在高对比度纹理上聚集，以及对运动模糊的敏感性（当梯度被模糊涂抹时，圆上的对比度会崩溃）。

动手实践

Classical local feature detection