FAST，全称Features From Accelerated Segment Test，是一种快速的角点检测算法，本文记录相关内容。

特征点提取

特征点提取到底是提取的是什么？

• 首先，提取的是角点，边缘。提取角点可以进行跟踪，提取边就可以知道图像发生了怎样的旋转。反正都是提取的是那些周围发生颜色明显变化的那些地方
• 其次，提取的是周围信息（学术上叫做：描述子）。我们只要提到特征点提取就一定要想到提取完后我们是需要匹配的。为了判断这个点有没有移动，我们需要比较前后两帧图片中相同特征点之间是否有位移。为了判断是否是相同特征点那就要进行比对（匹配）。

怎么比较两个特征点是否是同一个？

• 这就需要比较这两个特征点周围信息是否一样。周围信息是一样那就认为是同一个特征点。

那么怎么比较周围信息？

• 一般会把周围的像素通过一系列计算方式变成一个数字。然后比较这个数字是否相同来判断周围信息是否相同。

特征提取与匹配算法通用流程

1. 找到那些周围有明显变化的像素点作为特征点。那些角点和边缘这些地方明显颜色变化的那些像素点被作为特征点。

2. 提取这些特征点周围信息。一般是在当前这个点周围随机采样选几个像素点作为当前特征点的周围信息，或者画个圈圈进行采样。不同采样方法构成了不同算法。反正你想一个采样方法那你就创建了一种算法。

3. 特征点匹配。比如我要跟踪某个物体，我肯定是要先从这个物体提取一些特征点。然后看下一帧相同特征点的位置在哪，计算机就知道这个物体位置在哪了。怎么匹配？前面提到了我们第2步有提取当前特征点周围信息，只要周围信息一样那就是相同特征点。

FAST

FAST (Features from Accelerated Segment Test)是一个特征点提取算法的缩写。

在此之前已经有多种图像特征点(角点、斑点、极值点)的检测算法，包括Harris、LoG、HoG以及SIFT、SURF等被提出，这些方法大多涉及图像局部邻域的梯度计算和统计，相比较而言，FAST(Features From Accelerated Segment Test)在进行角点检测时，计算速度更快，实时性更好。

FAST角点定义为：若某像素点与周围邻域足够多的像素点处于不同区域，则该像素可能为角点。考虑灰度图像，即若某像素点的灰度值比周围邻域足够多的像素点的灰度值大或小，则该点可能为角点。

这是一个点提取算法。它原理非常简单，遍历所有的像素点，判断当前像素点是不是特征点的唯一标准就是在以当前像素点为圆心以3像素为半径画个圆（圆上有16个点），统计这16个点的像素值与圆心像素值相差比较大的点的个数。超过9个差异度很大的点那就认为圆心那个像素点是一个特征点。

算法步骤

• 对于图像中一个像素点 $𝑝$，其灰度值为 $𝐼_𝑝$

• 以该像素点为中心考虑一个半径为 3 的离散化的 Bresenham 圆，圆边界上有16个像素 (如下图所示)

  

• 设定一个合适的阈值 $t$，如果圆上有 $n$ 个连续像素点的灰度值小于 $Ip−t$ 或者大于 $Ip+t$ ，那么这个点即可判断为角点( $n$ 的值可取12或9)

加速算法

为了获得更快的效果，还采用了而外的加速办法。首先对候选点的周围每个 90 度的点：1，9，5，13 进行测试（先测试 1 和 19, 如果它们符合阈值要求再测试 5 和 13）。如果 p 是角点，那么这四个点中至少有 3 个要符合阈值要求。如果不是的话肯定不是角点，就放弃。对通过这步测试的点再继续进行测试（是否有 12 的点符合阈值要求）。这个检测器的效率很高，但是它有如下几条缺点：

• 当 n<12 时它不会丢弃很多候选点 (获得的候选点比较多)。
• 像素的选取不是最优的，因为它的效果取决与要解决的问题和角点的分布情况。
• 高速测试的结果被抛弃
• 检测到的很多特征点都是连在一起的

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

角点分类器

选取需要检测的场景的多张图像进行FAST角点检测，选取合适的阈值n(n<12)，提取多个特征点作为训练数据

对于特征点邻域圆上的16个像素 $x \in {1,2,…,16 }$，按下式将其划分为3类

$$ S_{p\rightarrow x} = \begin{cases} d,  I_{p\rightarrow x} \leq I_p-t \\ s,  I_p-t \leq I_{p\rightarrow x} \leq I_p+t \\ b,  I_p+t \leq I_{p\rightarrow x} \end{cases} $$

对每个特征点定义一个bool变量 $K_p$，如果 $𝑝$ 是一个角点，则 $K_p$ 为真，否则为假

对提取的特征点集进行训练，使用ID3算法建立一颗决策树，通过第 $x$ 个像素点进行决策树的划分，对集合 $P$，得到熵值为
$$
H(P)=(c+\hat{c})log_2 (c+\hat{c})-clog_2 c - \hat{c}log_2 \hat{c}
$$
其中 $𝑐$ 为角点的数目，$\hat{c}$为非角点的数目。由此得到的信息增益为
$$
\Delta H = H(P) - H(P_d) - H(P_s) - H(P_b)
$$
选择信息增益最大位置进行划分，得到决策树

使用决策树对类似场景进行特征点的检测与分类

非极大值抑制

对于邻近位置存在多个特征点的情况，需要进一步做非极大值抑制(Non-Maximal Suppression)。

1. 对所有检测到到特征点构建一个打分函数 $V$。$V$ 就是像素点 p 与周围 16个像素点差值的绝对值之和。
2. 计算临近两个特征点的打分函数 $V$。
3. 忽略 $V$ 值最低的特征点

具体来说就是：给每个已经检测到的角点一个量化的值 $𝑉$，然后比较相邻角点的$𝑉$值，保留局部邻域内$𝑉$值最大的点。$𝑉$值可定义为

• 特征点与邻域16个像素点灰度绝对差值的和

• $V = max(\Sigma_{x \in S_{bright}} |I_{p\rightarrow x} - I_p| - t, \Sigma_{x \in S_{dark}} |I_{p\rightarrow x} - I_p| - t)$ 式中，$S_{bright}$ 是16个邻域像素点中灰度值大于 $I_p+t$ 的像素点的集合，而 $S_{dark}$ 表示的是那些灰度值小于 $I_p−t$ 的像素点。

算法特点

• FAST算法比其他角点检测算法要快
• 受图像噪声以及设定阈值影响较大
• 当设置 $𝑛<12$ 时，不能用快速方法过滤非角点
• FAST 不产生多尺度特征，不具备旋转不变性，而且检测到的角点不是最优

Python OpenCV 实现

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import numpy as np
import cv2 as cv
from matplotlib import pyplot as plt
img = cv.imread('test2.jpg',0)
# Initiate FAST object with default values
fast = cv.FastFeatureDetector_create()
# find and draw the keypoints
kp = fast.detect(img,None)
img2 = cv.drawKeypoints(img, kp, None, color=(255,0,0))
# Print all default params
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)
# Disable nonmaxSuppression
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)

参考资料

• https://github.com/varyshare/easy_slam_tutorial/blob/master/feature_extract/从零开始实现FAST特征点提取算法教程.md

• https://senitco.github.io/2017/06/30/image-feature-fast/

• https://opencv-python-tutorials.readthedocs.io/zh/latest/5. 特征检测和描述/5.6. 用于角点检测的FAST算法/

文章链接：
https://www.zywvvd.com/notes/study/image-processing/feature-extraction/fast-fea/fast-fea/