本章将学习以下内容：

• 理解FAST算法的基本原理
• 学习使用OpenCV提供的FAST算法功能进行角点检测

理论基础

我们已了解多种特征检测算法，其中不少表现优异。但从实时应用的角度考量，它们的处理速度仍显不足。 典型案例如计算资源受限的SLAM（同步定位与建图）移动机器人系统。

针对此问题，Edward Rosten与Tom Drummond在2006年发表论文《机器学习在高速角点检测中的应用》（2010年修订）提出了FAST（加速分段测试特征）算法。 以下为算法基础概要（所有图示均引自原论文），详细实现请参阅原始文献。

特征检测原理

1. 在图像中选取待检测像素点 $p$，其灰度强度值为 $I_p$。
2. 设定适当阈值 $t$。
3. 以待测像素为中心，构建16像素的环形检测区域（如下图所示）。

4. 若在16像素的环形区域中存在连续 $n$ 个像素（$n$ 取值为12），这些像素的亮度均高于 $I_p + t$ 或均低于 $I_p − t$（如上图白色虚线所示），则该像素 $p$ 被判定为角点。
5. 算法提出高速测试环节以快速排除大量非角点：首先检测1、9、5、13四个位置像素（先检测1和9位置，若符合条件再检测5和13）。 若 $p$ 为角点，则这四个检测点中至少有三个必须同时满足亮度高于 $I_p + t$ 或同时低于 $I_p − t$。 若不满足该条件，则 $p$ 必然不是角点。通过初步检测的候选点将继续接受完整环形区域检测。 虽然该检测器本身具有高性能，但仍存在若干不足：
   • 当n<12时，无法有效排除足够多的候选点
   • 像素点的选择并非最优，其效率取决于检测顺序的设定和角点分布特征
   • 高速测试阶段的结果数据未被充分利用
   • 相邻区域会重复检测出多个特征点

前三点通过机器学习方法解决，最后一点则采用非极大值抑制处理。

机器学习角点检测器

1. 选择一组训练图像（最好来自目标应用领域）
2. 在每张图像上运行FAST算法寻找特征点
3. 对每个特征点，将其周围16个像素存储为向量。对所有图像执行此操作，得到特征向量 $P$
4. 这16个像素中的每个像素（记为 $x$ ）可能处于以下三种状态之一：

5. 根据这些状态，特征向量 $P$ 被划分为3个子集 $P_d$, $P_s$, $P_b$
6. 定义布尔变量 $K_p$，当 $p$ 为角点时值为真，反之为假
7. 使用ID3算法（决策树分类器），通过变量 $K_p$ 查询各子集的真实类别信息。算法选择能提供最大信息熵的像素 $x$ 作为判断依据
8. 递归应用于所有子集，直至熵值为零
9. 生成的决策树将用于其他图像的快速检测

非极大值抑制

相邻位置检测出多个特征点的问题通过非极大值抑制解决：

1. 为所有特征点计算评分函数 $V$，$V$ 为 $p$ 点与周围16像素的绝对差值和）
2. 对相邻关键点比较其 $V$ 值
3. 舍弃 $V$ 值较低的特征点

算法特点总结

• 检测速度数倍于传统角点检测器
• 对高噪声敏感
• 依赖阈值设定

OpenCV 中的 FAST 特征检测器

调用方式与其他特征检测器一致，可指定以下参数：

• 检测阈值
• 是否启用非极大值抑制
• 检测邻域类型（可选以下枚举）：
  • cv2.FAST_FEATURE_DETECTOR_TYPE_5_8
  • cv2.FAST_FEATURE_DETECTOR_TYPE_7_12
  • cv2.FAST_FEATURE_DETECTOR_TYPE_9_16

以下为特征检测与绘制的示例代码：

查看检测结果：第一张图显示启用非极大值抑制的FAST检测效果，第二张图则为未启用该功能的效果。

扩展阅读

• Edward Rosten与Tom Drummond合著的《机器学习在高速角点检测中的应用》，发表于第九届欧洲计算机视觉会议论文集第1卷（2006年），430-443页
• Edward Rosten、Reid Porter及Tom Drummond共同发表的《更快更好：基于机器学习的角点检测方法》，刊载于IEEE模式分析与机器智能汇刊（2010年）第32卷，105-119页