快速角点检测算法(FAST)

目标

本章节中，我们将：

• 了解FAST算法的基础知识。
• 使用OpenCV的功能来进行FAST算法的角点检测。

理论

我们已经学习了多种特征检测器，其中许多都非常优秀。但是，从实时应用的角度来看，它们的速度不够快。一个典型的例子是SLAM（同时定位与地图构建）移动机器人，它具有有限的计算资源。

为了解决这个问题，Edward Rosten和Tom Drummond在2006年的论文“用于高速角点检测的机器学习”（2010年进行了修订）中提出了FAST（加速分割测试特征）算法。以下是该算法的基本概要。更多细节请参考原文（所有图片均来自原文）。

使用FAST进行特征检测

1. 选择图像中一个像素\(p\)，判断它是否为兴趣点。设其强度为\(I_p\)。
2. 选择合适的阈值\(t\)。
3. 考虑被测像素周围一个包含16个像素的圆。(见下图)

图像

1. 如果在该16像素圆圈中存在一组\(n\)个连续像素，其亮度都高于\(I_p + t\)，或都低于\(I_p − t\)，则像素\(p\)为角点。（在上图中显示为白色虚线）。\(n\)通常选择为12。
2. 提出了一种高速测试方法来排除大量非角点。此测试仅检查位置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\)）可以具有以下三种状态之一：

图像

1. 根据这些状态，特征向量\(P\)被细分为3个子集，\(P_d\)，\(P_s\)，\(P_b\)。
2. 定义一个新的布尔变量\(K_p\)，如果\(p\)是角点则为真，否则为假。
3. 使用ID3算法（决策树分类器）使用变量\(K_p\)查询每个子集以了解真实类别。它选择产生关于候选像素是否为角点最多信息的\(x\)，其信息量由\(K_p\)的熵衡量。
4. 这被递归地应用于所有子集，直到其熵为零。
5. 创建的决策树用于在其他图像中进行快速检测。

非极大值抑制

在相邻位置检测多个兴趣点是另一个问题。它通过使用非极大值抑制来解决。

1. 为所有检测到的特征点计算分数函数\(V\)。\(V\)是\(p\)与其周围16个像素值之间绝对差的总和。
2. 考虑两个相邻的关键点并计算它们的\(V\)值。
3. 丢弃\(V\)值较低的一个。

总结

它比其他现有的角点检测器快几倍。

但它对高噪声不鲁棒。它依赖于阈值。

OpenCV中的FAST特征检测器

它像OpenCV中的任何其他特征检测器一样被调用。如果需要，可以指定阈值、是否应用非最大值抑制、使用的邻域等。

对于邻域，定义了三个标志，cv.FAST_FEATURE_DETECTOR_TYPE_5_8、cv.FAST_FEATURE_DETECTOR_TYPE_7_12和cv.FAST_FEATURE_DETECTOR_TYPE_9_16。以下是如何检测和绘制FAST特征点的简单代码。

import numpy as np
import cv2 as cv
from matplotlib import pyplot as plt
 
img = cv.imread('blox.jpg', cv.IMREAD_GRAYSCALE) # `<opencv_root>/samples/data/blox.jpg`
 
# 使用默认值初始化FAST对象
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( "启用非极大值抑制的关键点数目: {}".format(len(kp)) )
 
cv.imwrite('fast_true.png', img2)
 
# 禁用非极大值抑制
fast.setNonmaxSuppression(0)
kp = fast.detect(img, None)
 
print( "禁用非极大值抑制的关键点数目: {}".format(len(kp)) )
 
img3 = cv.drawKeypoints(img, kp, None, color=(255,0,0))
 
cv.imwrite('fast_false.png', img3)

查看结果。第一张图显示了使用非极大值抑制的FAST算法，第二张图则没有使用非极大值抑制。

图像

附加资源

1. Edward Rosten 和 Tom Drummond，“用于高速角点检测的机器学习”，第9届欧洲计算机视觉会议，第1卷，2006年，第430-443页。
2. Edward Rosten、Reid Porter 和 Tom Drummond，“更快更好：一种用于角点检测的机器学习方法”，IEEE模式分析与机器智能汇刊，2010年，第32卷，第105-119页。