FAST角点检测方法(Wikipedia翻译)

2020-07-20

Word count: 2.7k | Reading time≈ 10 min

加速分段特征点测试

原文地址：https://en.wikipedia.org/wiki/Features_from_accelerated_segment_test

第一次尝试翻译，渣翻请谅解，欢迎提出改进意见

加速分段特征点检测(FAST)是一种角点检测方法，在很多计算机视觉的课题当中，它可以用于提取特征点并追踪(track)和比对(map)物体。FAST角点检测最初由Edward Rosten和Tom Drummond开发，并于2006年正式发布。^[1]FAST角点检测的一大最有前途的优点在于它的计算效率。正如FAST的名字一样，它确实比许多众所周知的特征提取方法，诸如使用高斯差分(DoG)的SIFT检测、SUSAN检测和Harris检测，要更加快速(faster)。更加强大的是，如果结合机器学习技术，FAST可以在计算时间和资源上达到很高的性能(Superior Performance)。FAST角点检测的高速性能(high-speed performance)使得它非常适合应用在实时视频的处理上。

分段测试检测

FAST角点检测使用了一个16像素的圆(半径为3的Bresenham圆)来确定(classify)选中的点p是否确实是一个角点。圆上的每一个像素都以顺时针编号为1至16。如果圆上一组N个相邻的像素点的亮度(intensity)全部都比选中点p的亮度(记为I_p)要高出或低出阈值t，则点p被归类为一个角点。该条件可以写成：

条件一：一组N个相邻的像素点的集合记为S，$\forall x \in S$，x的亮度>I_p+阈值t，或$I_{x} > I_{p}+t$
条件二：一组N个相邻的像素点的集合记为S，$\forall x \in S$，x的亮度<I_p-阈值t，或$I_{x} < I_{p}-t$

在满足其中任意一个条件时，选中点p可以被归类为一个角点。在选择相邻像素点数量N与阈值t的数值上需要进行权衡。既不应该检测出过多的角点，又不应该为了达成高准确度(high performance)而牺牲计算效率。在没有机器学习的优化下，N的值一般取为12。一个高速检测方法(A high-speed test method)可以用于排除不是角点的点。

高速检测

用于排除非角点的高速检测是通过对编号为1,9,5,13的4个对照(example)像素点进行检测来实现的。因为对于角点来说，应该至少有全都比它更亮或更暗的12个连续点，所以在这4个对照像素点中，至少应该有3个像素点全都比选中点更亮或更暗。首先对点1和点9进行检测，如果它们的亮度都处于阈值范围[I_p-t,I_p+t]内，则选中点p不是角点，否则，对点5和点13进行进一步的检测，确认是否其中三个点全都比选中点更亮或更暗。如果有三个点确实满足条件，则对剩下的全部点进行检测来确定选中点的最终类型。根据发明者在他的第一篇论文中所说^[2]，对于一个角点平均需要检测3.8个像素点。与每个角点8.5个像素点(指分段测试检测？)相比，3.8是能够高度改善性能的巨大降低。

然而，这个检测方法有着几个缺点：

高速检测不能被很好地推广到N<12的情况，如果N<12，角点p的4个对照像素点中可能只存在两个全都比p更亮或更暗。
检测的效率取决于检测点的选取与顺序。但是不太可能结合角点的分布选出最优的检测点。(it is unlikely that the chosen pixels are optimal which take concerns about the distribution of corner appearances.)
检测到的多个特征点彼此相邻。(Multiple features are detected adjacent to one another.)

2020.7.20 16:20 by Jzjerry

机器学习优化

为了处理高速检测的前两个缺点，人们引入了一种机器学习的方法来帮助改进这一检测算法。这种机器学习方法分为两个阶段。第一阶段，在一个训练图像集上进行给定N值的角点检测，这个训练图像集偏向于特定的目标应用领域。通过最简单的实施方法，即提取一个16像素点的圆环并取其亮度和一个适当的阈值进行比较，可检测到角点。

对于选中点p，圆上的每一个位置x∈{1,2,3,…,16}表示为p→x。每个像素的状态S_p→x必须处于下列三种状态中的一种：

d，I_p→x ≤ I_p-t（更暗）
s，I_p-t ≤ I_p→x ≤ I_p+t（相似）
b，I_p→x ≥ I_p+t（更亮）

然后选取一个点x（对所有p都取同一个）分割P（所有训练图像的所有像素点的集合）为三个不同的子集，P_d,P_s,P_b，其中：

P_d = {p ∈ P : S_p→x = d}
P_s = {p ∈ P : S_p→x = s}
P_b = {p ∈ P : S_p→x = b}

第二阶段，使用决策树算法，将ID3算法用于16个位置上，取得最大的信息增益。取K_p为一个表示p是否为角点的布尔型变量，然后用K_p的熵来表示(measure)p是否为角点的信息。对于一组像素Q，K_p的总熵（未归一化）为：

$ H(Q)=(c+n)log_{2}(c+n)-clog_{2}c-nlog_{2}n$
- c = |{ i∈Q:K_i is true}|(角点数)
- n = |{ i∈Q:K_i is false}|(非角点数)

信息增益可以被表示为：

$H_{g} = H(P)-H(P_{b})-H(P_{s})-H(P_{d})$

为了选出每个能够的到最大信息增益的x点，对每个子集进行一个递归过程。例如，首先选出具有最多的信息的，用于分割P为P_d,P_s,P_b的x点；然后对每个子集P_d,P_s,P_b，选出能产生最大信息增益的y点（可能和x点为同一个）。这个递归过程在熵为0的时候结束，这时子集中所有像素不是角点就是非角点。

生成的决策树可以转换为程序代码，例如C与C++代码，只需要一串嵌套的if-else语句就可以实现。如果想要得到最优化，可以使用按配置优化（Profile-guided Optimization）编译代码。编译后的代码可以用于对其它图像进行角点检测。

值得注意的是，使用决策树算法检测的角点会与分段测试检测得到的角点有微小的差异。这是因为决策树模型是基于训练数据的，并不能覆盖所有可能的角点。

非极大值抑制

“由于分段检测并不能计算出角点响应函数，非极大值抑制不能直接用于产生特征。”然而，如果N是固定的，对于每一个像素点p，角点强度(corner strength)可定义为使p成为角点的阈值t的极大值。因此，有两种方法可以用于计算角点强度：

二分搜索算法可以被用于找到使p点仍是一个角点的t的极大值。每次都会为决策树算法设定一个不同的t值。当算法找到了最大的t值时，就可以将该值作为角点强度。
另外一种方法是使用迭代法(iteration scheme)，每次使t值增加一个能使p通过角点检测的极小值。

FAST-ER:更强的重复性

FAST-ER检测是一种使用元启发式算法的FAST检测优化算法，其使用元启发式算法是模拟退火算法。在最优化之后，决策树的结构将会最优化，且适合于检测重复率高的点。但是模拟退火算法作为一种元启发式算法，每次会生成不同的最优决策树。因此，最好有效地进行大量的迭代，来寻找接近实际最优的方案。根据Rosten所说，在3GHz主频的Pentium4上重复100遍10万次的FAST迭代优化需要大约200个小时。

与其他检测的对比

在Rosten的研究中^[3]，他对不同数据集下的FAST和FAST-ER检测进行了评价，并与DoG，Harris，Harris-Laplace，Shi-Tomasi和SUSAN角点检测进行了比较。

除了FAST检测之外，其他检测的参数设置如下：

检测类型	参数设置	值
DoG	八分尺度(Scales per octave)	3
	初始模糊 σ	0.8
	八分组数(Octaves)	4
SUSAN	距离阈值	4.0
Harris，Shi-Tomasi	模糊 σ	2.5
Harris-Laplace	初始模糊 σ	0.8
	Harris 模糊	3
	八分组数(Octaves)	4
	八分尺度(Scales per octave)	10
通用参数	ε	5像素

译者注：各参数的具体中文译名与意义有待考证

重复性测试结果以所有数据集上，每帧0-2000个角点的重复性曲线下的平均面积（多余的噪声干扰除外）表示：

检测类型 A

FAST-ER 1313.6

FAST-9 1304.57

DOG 1275.59

Shi & Tomasi 1219.08

Harris 1195.2

Harris-Laplace 1153.13

FAST-12 1121.53

SUSAN 1116.79

随机 271.73

检测类型	A
FAST-ER	1313.6
FAST-9	1304.57
DOG	1275.59
Shi & Tomasi	1219.08
Harris	1195.2
Harris-Laplace	1153.13
FAST-12	1121.53
SUSAN	1116.79
随机	271.73

速度测试在主频3.0GHz的Pentium4-D处理器上进行。数据集被分为训练集与测试集。训练集由101个分辨率为992×668像素的单色图像组成。测试集由4968帧352×288像素的单色视频组成。测试结果如下：

检测类型	训练集像素速率	测试集像素速率
FAST n=9	188	179
FAST n=12	158	154
Original FAST n=12	79	82.2
FAST-ER	75.4	67.5
SUSAN	12.3	13.6
Harris	8.05	7.90
Shi-Tomasi	6.50	6.50
DoG	4.72	5.10

译者注：这里的原文是pixel rate，考虑到是速度测试就翻译成了速率，我认为是每秒处理的像素数。

2020.7.24 14:03 by Jzjerry 粗译完成

2020.8.17 18:44 by Jzjerry 修改一处名词翻译与一处数据空缺

参考

Rosten, Edward; Drummond, Tom (2006). “Machine Learning for High-speed Corner Detection”. Computer Vision – ECCV 2006. Lecture Notes in Computer Science. 3951. pp. 430–443. doi:10.1007/11744023_34. ISBN 978-3-540-33832-1. S2CID 1388140.
Edward Rosten, Real-time Video Annotations for Augmented Reality
Edward Rosten, FASTER and better: A machine learning approach to corner detection

文献

Rosten, Edward; Tom Drummond (2005). Fusing points and lines for high performance tracking (PDF). IEEE International Conference on Computer Vision. 2. pp. 1508–1511. CiteSeerX 10.1.1.60.4715. doi:10.1109/ICCV.2005.104. ISBN 978-0-7695-2334-7.
Rosten, Edward; Reid Porter; Tom Drummond (2010). “FASTER and better: A machine learning approach to corner detection”. IEEE Transactions on Pattern Analysis and Machine Intelligence. 32 (1): 105–119. arXiv:0810.2434. doi:10.1109/TPAMI.2008.275. PMID 19926902.
Rosten, Edward; Tom Drummond (2006). Machine learning for high-speed corner detection (PDF). European Conference on Computer Vision. Lecture Notes in Computer Science. 1. pp. 430–443. CiteSeerX 10.1.1.64.8513. doi:10.1007/11744023_34. ISBN 978-3-540-33832-1.