OpenCV FAST 角点检测算法：原理、Python 实现与源码级深度解析

OpenCV FAST 角点检测算法：原理、Python 实现与源码级深度解析

【免费下载链接】opencvOpen Source Computer Vision Library项目地址: https://gitcode.com/GitHub_Trending/opencv31/opencv

FAST（Features from Accelerated Segment Test）是实时视觉应用中最重要的角点检测器之一。本文基于 OpenCV 官方 Python 教程py_fast.markdown，完整讲解 FAST 的圆环测试原理、高速预测试、机器学习优化与非极大值抑制，给出可直接运行的cv.FastFeatureDetector_create()检测与绘图代码，并结合当前仓库中 modules/features/src/fast.cpp 的实现细节（查找表加速、SIMD 预测试、HAL 替换、OpenCL 路径、NMS 邻域比较）与回归测试，帮助你在掌握 API 用法的同时理解其底层性能来源。

为什么需要 FAST：实时场景的取舍

传统的特征检测器（如 Harris、Shi-Tomasi 等）精度良好，但从实时应用角度看速度不够快。官方教程给出的典型场景是 SLAM（Simultaneous Localization and Mapping，同步定位与建图）移动机器人：这类设备计算资源有限，却要求每一帧都快速给出大量特征点。

为此，Edward Rosten 与 Tom Drummond 在 2006 年论文 "Machine learning for high-speed corner detection"（2010 年修订）中提出了 FAST 算法。它的核心思想是：只用整数加减法和比较就能判断一个像素是不是角点，不需要做图像导数、矩阵运算，天然适合流水线化与 SIMD 加速。

FAST 特征检测基本算法

16 像素圆环测试

算法按以下步骤对每个候选像素进行判断：

1. 选出图像中待判断的像素 $p$，其灰度值为 $I_p$。
2. 选出合适的阈值 $t$。
3. 考虑该像素周围的一个由 16 个像素组成的圆环（下图中 1–16 编号的环形位置，中心为 $p$）：

4. 如果在这 16 个像素中，存在 $n$ 个连续的像素全部亮于 $I_p + t$，或全部暗于 $I_p - t$，则 $p$ 是角点。论文中 $n$ 取 12。
5. 为进一步提速，论文提出了高速测试（high-speed test）：只检查环上的 4 个像素（1、5、9、13 位置）。若 $p$ 是角点，则这 4 个像素中至少 3 个必须亮于 $I_p + t$ 或暗于 $I_p - t$；否则 $p$ 一定不是角点，直接排除。只有通过了快速预测试的候选像素才会进入完整的 16 像素段测试。

这个高速测试可以排除绝大多数非角点候选，是 FAST 快于其他角点检测器的关键。但它也有几个弱点：对 $n < 12$ 时排除能力不足；所选 4 个像素并非最优（效率取决于提问顺序与角点分布）；高速测试的结果被丢弃；相邻位置可能检测出多个重复特征点。前三点用机器学习方法解决，第四点用非极大值抑制解决。

用机器学习训练检测器

2010 年的改进版 FAST 用决策树学习来组织判断顺序，步骤如下：

1. 选取一组训练图像（最好来自目标应用域）。
2. 对每张图像运行 FAST 算法找出特征点。
3. 对每个特征点，把其周围 16 个像素存储为一个向量，汇总所有图像得到特征向量集合 $P$。
4. 这 16 个像素中的任意像素（记为 $x$）只有三种状态：

5. 依据这些状态，把 $P$ 划分为 $P_d$、$P_s$、$P_b$ 三个子集。
6. 定义布尔变量 $K_p$：$p$ 是角点为真，否则为假。
7. 使用 ID3 算法（决策树分类器），以 $K_p$ 作为真实类别的知识，对每个子集查询：选择能使 $K_p$ 熵获得最多信息的 $x$ 作为下一次测试的像素。
8. 递归地对所有子集应用上述过程，直到熵为零。
9. 这样构造出的决策树即可在其他图像中用于快速角点检测——像素检查顺序不再是写死的 1、5、9、13，而是按信息增益最优动态排列。

非极大值抑制（NMS）

在相邻位置检测到多个兴趣点是另一个问题，用非极大值抑制解决：

1. 对所有检测到的特征点计算得分函数 $V$：$V$ 是中心像素 $p$ 与周围 16 个像素灰度之差的绝对值之和。
2. 对两个相邻关键点比较各自的 $V$ 值。
3. 丢弃 $V$ 值较低的那个。

小结

FAST 比其他已有角点检测器快数倍，但它对高噪声不鲁棒，且结果依赖于阈值 $t$ 的选择。

OpenCV 中的 FAST 检测器

OpenCV 提供了两个入口：自由函数cv::FAST()和特征检测器类FastFeatureDetector。在 modules/features/include/opencv2/features.hpp 中可以看到其定义：

class CV_EXPORTS_W FastFeatureDetector : public Feature2D { public: enum DetectorType { TYPE_5_8 = 0, TYPE_7_12 = 1, TYPE_9_16 = 2 }; CV_WRAP static Ptr<FastFeatureDetector> create( int threshold=10, bool nonmaxSuppression=true, FastFeatureDetector::DetectorType type=FastFeatureDetector::TYPE_9_16 ); CV_WRAP virtual void setThreshold(int threshold) = 0; CV_WRAP virtual int getThreshold() const = 0; CV_WRAP virtual void setNonmaxSuppression(bool f) = 0; CV_WRAP virtual bool getNonmaxSuppression() const = 0; CV_WRAP virtual void setType(FastFeatureDetector::DetectorType type_) = 0; CV_WRAP virtual FastFeatureDetector::DetectorType getType() const CV 0; }; CV_EXPORTS void FAST( InputArray image, CV_OUT std::vector<KeyPoint>& keypoints, int threshold, bool nonmaxSuppression=true, FastFeatureDetector::DetectorType type=FastFeatureDetector::TYPE_9_16 );

可调参数说明：

其中type的命名来自论文中TYPE_m_n的含义：m表示连续像素长度（角点判定需要连续超过 $m$ 个相同状态的环像素），n表示实际检查的环像素数。TYPE_9_16即"16 像素圆环中连续 9 个（> 8）同侧像素"，是最常用也最严格的模式；TYPE_5_8只检查 8 像素环，速度最快但误报更多。三种类型在源码中分别映射到模板实例FAST_t<8>、FAST_t<12>、FAST_t<16>（见 fast.cpp）。

完整 Python 示例

下面的示例代码继承自官方教程，使用仓库自带的数据图 samples/data/blox.jpg，对比开启与关闭非极大值抑制两种模式下的检测效果：

import numpy as np import cv2 as cv from matplotlib import pyplot as plt # 读取灰度图，blox.jpg 位于 <opencv_root>/samples/data/blox.jpg img = cv.imread('blox.jpg', cv.IMREAD_GRAYSCALE) # 用默认参数创建 FAST 检测器 # 默认：threshold=10, nonmaxSuppression=True, type=TYPE_9_16 fast = cv.FastFeatureDetector_create() # 检测并绘制关键点 kp = fast.detect(img, None) img2 = cv.drawKeypoints(img, kp, None, color=(255, 0, 0)) # 打印当前全部默认参数 print("Threshold: {}".format(fast.getThreshold())) print("nonmaxSuppression:{}".format(fast.getNonmaxSuppression())) print("neighborhood: {}".format(fast.getType())) print("Total Keypoints with nonmaxSuppression: {}".format(len(kp))) cv.imwrite('fast_true.png', img2) # 关闭非极大值抑制 fast.setNonmaxSuppression(0) kp = fast.detect(img, None) print("Total Keypoints without nonmaxSuppression: {}".format(len(kp))) img3 = cv.drawKeypoints(img, kp, None, color=(255, 0, 0)) cv.imwrite('fast_false.png', img3)

几点使用细节：

• detect(img, None)的第二个参数是掩膜，None表示全图检测。若传入掩膜，实现中会调用KeyPointsFilter::runByPixelsMask()过滤掩膜外的点（见 fast.cpp）。
• 输入若不是 8 位灰度图，实现内部会自动cvtColor转灰度，因此直接传彩色图也能工作，但显式IMREAD_GRAYSCALE更省一次转换。
• 关闭 NMS 后检测到的点数通常明显多于开启时，且同一角点周围会出现一簇重叠的圆——这正是"相邻位置检测出多个特征"问题的直观体现。

左图（非极大值抑制开启）每个角点只保留一个代表点；右图（关闭抑制）则能看到大量相邻重复的关键点簇，直观验证了 NMS 的作用。

源码级实现剖析

主流程：预测试 + 完整段测试

核心检测函数是模板函数FAST_t<patternSize>（fast.cpp），模板参数patternSize取 8、12 或 16，对应三种DetectorType。其 CPU 标量路径（fast.cpp）完整体现了论文的两级测试：

int v = ptr[0]; const uchar* tab = &threshold_tab[0] - v + 255; int d = tab[ptr[pixel[0]]] | tab[ptr[pixel[8]]]; // 高速测试：像素 1 和 9 if( d == 0 ) continue; d &= tab[ptr[pixel[2]]] | tab[ptr[pixel[10]]]; // 像素 5 和 13 d &= tab[ptr[pixel[4]]] | tab[ptr[pixel[12]]]; d &= tab[ptr[pixel[6]]] | tab[ptr[pixel[14]]]; if( d == 0 ) continue; d &= tab[ptr[pixel[1]]] | tab[ptr[pixel[9]]]; // ... 其余环像素

• threshold_tab是一张 512 项的查找表：tab[i + v]直接给出邻域像素相对中心像素是"更暗（1）/ 更亮（2）/ 相近（0）"，把比较运算压缩成一次内存读取。
• d的位 1 表示"存在足够多的更暗像素"，位 2 表示"存在足够多的更亮像素"，两者都不满足（d == 0）就跳过，这正是高速测试的实现。
• 通过预测试后，代码按d & 1/d & 2分别做完整段测试：沿环形偏移数组pixel[0..15]顺序扫描，统计连续满足x < v - t（或x > v + t）的计数，count > K（K = patternSize/2）才判定为角点，并立即break——连续段测试与"超过一半即判定"的策略让最坏情况也被提前截断。

SIMD 向量化路径

当patternSize == 16且编译启用了 128 位 SIMD（CV_SIMD128）时，实现会以 16 像素为一组并行执行高速预测试（fast.cpp）：一次性加载 16 个中心像素和 4 个关键环像素，用v_lt/v_and/v_or组合计算 4 选 3 的组合条件，再用v_check_any快速跳过整组全非角点的行段。若检测到 AVX2 支持，还会调用opt_AVX2::FAST_t_patternSize16_AVX2专用实例进一步加速。这就是"FAST 比其他角点检测器快数倍"的底层来源：预测试本身被完全向量化，且绝大多数像素在预测试阶段就被丢弃。

非极大值抑制的邻域比较

论文中"比较相邻关键点、丢弃 V 小的那个"在实现中具体化为 3×3 邻域内的最大值判定。检测到角点后，用cornerScore<patternSize>()（定义在 fast_score.hpp）计算得分 $V$ 存入行缓冲，随后（fast.cpp）：

if( !nonmax_suppression || (score > prev[j+1] && score > prev[j-1] && score > pprev[j-1] && score > pprev[j] && score > pprev[j+1] && score > curr[j-1] && score > curr[j] && score > curr[j+1]) ) { keypoints.push_back(KeyPoint((float)j, (float)(i-1), 7.f, -1, (float)score)); }

即只有当该点得分严格大于上、下两行及其左右邻点共 8 个候选的得分时才保留，最终关键点size固定为 7、response存得分 $V$，可供后续KeyPointsFilter::runByScore之类的二次筛选使用。

HAL 替换与 OpenCL 路径

FAST()入口（fast.cpp）还体现了 OpenCV 的分层加速架构：

1. 参数校验：type不合法时直接抛出StsBadArg异常（测试 test_fast.cpp 的invalidDetectorType用例即验证此行为）。
2. OpenCL：当输入是UMat且类型为TYPE_9_16时走ocl_FAST()，由FAST_findKeypoints与FAST_nonmaxSupression两个 OpenCL 核完成，且关键点数量上限取max(图像总像素数/100, 1000)这一简单启发式（fast.cpp）。
3. HAL：优先尝试cv_hal_FASTv2/cv_hal_FAST硬件抽象层钩子（供 ARM 等平台的优化库替换）。注意 HAL 密集接口hal_FAST（fast.cpp）在threshold > 20时主动返回未实现并回退到通用 CPU 路径——阈值过大时密集打分收益有限。
4. 通用 CPU：最后回退到FAST_t<8/12/16>模板实现。

测试与回归验证

仓库为 FAST 提供了三类测试，可作为行为依据：

• modules/features/test/test_fast.cpp 中的Features2d_FAST.regression：对 3 种DetectorType分别在两张标定图上以固定阈值调用FAST()，并将关键点序列与 XML 基线做 L2 零差比较，保证结果跨平台可复现；
• Features2d_FAST.noNMS：验证nonmaxSuppression=false时的独立回归结果；
• Features2d_FAST.invalidDetectorType：验证非法type抛出异常。

此外 modules/features/perf/perf_fast.cpp 提供性能基准测试，可量化TYPE_5_8 / 7_12 / 9_16与 NMS 开关的耗时差异，供调参参考。

调参实践建议

• 阈值threshold：默认 10。噪声大的图像可以适当调高（如 20–40），减少误检但会丢失弱角点；图像对比度高、角点密集时可适当调低。由于 FAST"对高噪声不鲁棒、结果依赖阈值"，建议对同一图像组扫一遍阈值，观察关键点数稳定性。
• type的选择：TYPE_9_16（默认）最严格、最稳定，且是唯一走 OpenCL 加速的类型；TYPE_5_8检测最快、点数最多，适合需要稠密点且算力极受限的场景。
• NMS 开关：交互式调参与可视化时建议保持默认开启；做匹配、跟踪等需要稳定点集的场景务必开启，否则相邻冗余点会干扰描述子计算。

参考资料

1. Edward Rosten 和 Tom Drummond，"Machine learning for high speed corner detection"，第 9 届欧洲计算机视觉大会（ECCV），vol. 1，2006，pp. 430–443。
2. Edward Rosten、Reid Porter 和 Tom Drummond，"Faster and better: a machine learning approach to corner detection"，IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，vol. 32，pp. 105-119。

【免费下载链接】opencvOpen Source Computer Vision Library项目地址: https://gitcode.com/GitHub_Trending/opencv31/opencv