加速分段测试的特点

FAST角点检测器使用16像素的圆(半径为3的布雷森汉圆)来分类候选点p是否实际上是角点。圆圈中的每个像素都是从整数1到16顺时针标记的。如果圆中的一组N个连续像素都比候选像素p的强度(由I_p表示)加上阈值t的强度亮，或者都比候选像素p的强度减去阈值t的强度暗，则p被分类为角点。条件可以写成:

• 条件1:一组n个连续像素s，∀ x ∈ S，x (I_x)的强度> I_p +阈值t

• 条件2:一组n个连续像素s，∀ x ∈ S，I_x < I_p - t

因此，当满足这两个条件中的任何一个时，候选p可以被分类为角点。存在选择N，连续像素的数量和阈值t之间的权衡。一方面，检测到的角点的数量不应太多，另一方面，不应通过牺牲计算效率来实现高性能。如果没有机器学习的改进，通常选择N为12。可以应用高速测试方法来排除非角点。

通过检查4个示例像素，即像素1、9、5和13，来操作用于拒绝非角点的高速测试。因为应该有至少12个连续的像素都比候选角更亮还是更暗，所以在这4个示例像素中应该有至少3个像素比候选角更亮或更暗。首先检查像素1和9，如果I₁和I₉都在[I_p - t，I_p + t]之内，那么候选p不是角点。否则，进一步检查像素5和13，以检查它们中的三个像素是比I_p + t亮还是比I_p - t暗。如果存在其中的三个像素是亮还是暗，则检查其余像素以获得最终结论。根据发明者在他的第一篇论文中所说，^[2] 平均需要3.8个像素来检查候选角像素。与每个候选角点的8.5像素相比，3.8像素确实是一个很大的减少，可以大大提高性能。

然而，这种测试方法有几个缺点:

1.     对于N < 12，高速测试不能很好地推广。如果N < 12，候选p可能是一个角点，并且4个示例测试像素中只有2个既比I_p + t亮或者比I_p - t暗

2.     检测器的效率取决于这些选定测试像素的选择和排序。然而，考虑到角点外观的分布，所选择的像素不太可能是最佳的。

3.     检测到彼此相邻的多个特征

为了解决高速测试的前两个弱点，引入了机器学习方法来改进检测算法。这种机器学习方法分两个阶段进行。首先，在一组优选来自目标应用领域的训练图像上进行给定N条件的角点检测。通过最简单的实现来检测角点，该实现从字面上提取16个像素的环，并将强度值与适当的阈值进行比较。

对于候选p，圆x∈{ 1，2，3，...，16}可以用p→x表示。每个像素的状态，S_p→x必须处于以下三种状态之一:

l d，I_p→x ≤ I_p - t(更暗)

l s，I_p - t ≤ I_p→x ≤ I_p + t(相似)

l b，I_p→x≥ I_p + t(更亮)

然后选择一个x(对所有p相同)分区P(所有训练图像的所有像素的集合)分成3个不同的子集，P_d、P_s、P_b，其中:

l P_d = {p ∈ P : S_p→x = d }

l P_s = {p ∈ P : S_p→x = s }

l P_b = {p ∈ P : S_p→x = b }

其次，采用决策树算法，将ID3算法应用于16个位置，以获得最大的信息增益。让K_p是一个布尔变量，它指示p是否是一个角点，然后用K_p的熵来度量p是否是一个角点的信息。对于一组像素Q，K_Q的总熵(未标准化)为:

l H(Q)=(c+n)log₂(c+n)-clog ₂c-nlog₂n

○        其中c = |{ i ∈ Q: K_i为真}|(角数)

○        其中n = |{ i ∈ Q: K_i为假}|(非角数)

信息增益可以表示为:

·        H_g= H(P) - H(P_b) - H(P_s) - H(P_d)

对每个子集应用递归过程，以便选择可以最大化信息增益的每个x。例如，首先选择一个x来将P分成具有最多信息的P_d、P_s、P_b；然后，对于每个子集P_d、P_s、P_b，选择另一个y来产生最大的信息增益(注意，y可以与x相同)。当熵为零时，这个递归过程结束，因此该子集中的所有像素要么是角点，要么是非角点。

然后，生成的决策树可以被转换成编程代码，如C和C++，这只是一堆嵌套的if-else语句。出于优化目的，使用配置引导引导优化来编译代码。编译后的代码稍后将用作其他图像的角点检测器。

请注意，使用决策树算法检测到的角点应该与使用分段测试检测器的结果略有不同。这是因为决策树模型依赖于训练数据，不能覆盖所有可能的角落。

“由于分段测试不计算角点响应函数，因此非最大抑制不能直接应用于结果特征。”然而，如果N是固定的，对于每个像素p，角点强度被定义为使p成为角点的t的最大值。因此，可以使用两种方法:

• 可以应用二进制搜索算法来找到p仍然是角点的最大t。所以每次为决策树算法设置不同的t。当它设法找到最大的t时，这个t可以被视为角点强度。
• 另一种方法是迭代方案，其中每次t增加到通过测试的最小值。

快速ER检测器是在快速检测器的基础上改进的一种元启发式算法，即模拟退火算法。从而优化后使得决策树的结构将得到优化，并适用于重复性高的点。然而，由于模拟退火是一种元启发式算法，每次该算法都会生成不同的优化决策树。因此，最好高效地进行大量迭代，以找到一个接近真正最优的解决方案。根据Rosten的说法，在3GHz的奔腾4上大约需要200小时，这是100次重复100,000次迭代以优化快速检测器。

在Rosten的研究中，^[3] FAST和FAST-ER检测器在几个不同的数据集上进行评估，并与DoG、Harris、Harris-Laplace、Shi-Tomasi和SUSAN角检测器进行比较。

检测器的参数设置(快速以外)如下:

• 重复性测试结果显示为所有数据集上每帧0-2000个角的重复性曲线下的平均面积(附加噪声除外):

• 速度测试是在3.0GHz奔腾4-D计算机上进行的。数据集分为训练集和测试集。训练集由101幅分辨率为992×668像素的单色图像组成。测试集由4968帧单色352×288视频组成。结果是: