FAST 角点检测算法

目标

在本章中，

• 我们将了解 FAST 算法的基本原理
• 我们将使用 OpenCV 的 FAST 算法功能查找角点。

理论知识

我们了解到若干特征检测器，其中许多非常好。但从实时应用角度来看，它们不够快。最好的例子是计算资源受限的 SLAM（同步定位与建图）移动机器人。

为此，Edward Rosten 和 Tom Drummond 在 2006 年的论文《用于高速角点检测的机器学习》中提出了 FAST（加速分段测试的特征）算法（2010 年进行了修订）。下文介绍了该算法的基本摘要。有关更多详细信息，请参阅原始论文（所有图像均取自原始论文）。

使用 FAST 进行特征检测

1. 在图像中选择要识别为关键点或非关键点的像素 \(p\)。其强度表示为 \(I_p\)。
2. 选择适当的阈值 \(t\)。
3. 考虑待测像素周围 16 个像素的圆形区域。（请参见下图）

image

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 时，它不会拒绝那么多候选像素。
   • 像素的选择不是最优的，因为其效率取决于问题的排序和角点外观的分布。
   • 高速测试的结果会被丢弃。
   • 检测到多个彼此相邻的角点。

使用机器学习方法解决前 3 个问题。最后一个问题使用非最大值抑制方法解决。

用机器学习方法构建角点检测器

1. 选择一组图像用于训练（最好来自目标应用领域）
2. 在每幅图像中运行 FAST 算法来查找特征点。
3. 对于每个特征点，将周围的 16 个像素存储为一个向量。对所有图像执行此操作以获取特征向量 \(P\)。
4. 这些 16 个像素中的每个像素（比如 \(x\））可具有以下三种状态之一

image

1. 根据这些状态，特征向量 \(P\) 被细分为 3 个子集，\(P_d\)、\(P_s\)、\(P_b\)。
2. 定义一个新的布尔变量 \(K_p\)，如果 \(p\) 是角点则为 true，否则为 false。
3. 使用 ID3 算法（决策树分类器）使用变量 \(K_p\) 查询每个子集，以获取有关真类的知识。它选择的信息熵 \(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( "阈值：{}".format(fast.getThreshold()) )
print( "非极大值抑制：{}".format(fast.getNonmaxSuppression()) )
print( "邻域：{}".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，第二张则不带非极大值抑制

image

其他资源

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

练习