FAST是一种角点检测方法，用于图像的特征点的提取，然后用在追踪和映射物体等计算机视觉任务中。
FAST - Features from accelerated segment test
FAST是一种角点检测方法，用于图像的特征点的提取，然后用在追踪和映射物体等计算机视觉任务中。FAST最明显的优势是它的效率。就像它的名字——FAST，它很快并且比其它著名的特征点提取方法，比如SIFT，SUSAN和Harris检测中的DoG(difference of Gaussians)方法。另外，结合机器学习的应用，算法在计算时间和资源上的性能还能够继续提高。
片段测试检测器(Segment test detector)
FAST角点检测算法使用一个16个像素组成的圆(半径为3的Bresenham圆)来区分候选点p是否是角点。16个像素按照顺时针方向以此标记为1-16号。如果连续的N的点都比p点的亮度值加上一个阈值t高或者比p点的亮度值减去阈值t低，那么就认为p是一个角点。这个条件可以写作：
- 条件1: N个连续点的集合S, $\forall x \in S$, x点的亮度$I_x>I_p + 阈值t$
- 条件2: N个连续点的集合S, $\forall x \in S$, x点的亮度$I_x<I_p - 阈值t$
没有机器学习参与的情况下，N通常选择为12。在排除候选点的时候，应用一些方法来保证算法的性能。
高速检测
通过先后检测编号为1，9，5，13来快速排除非角点的候选点。因为至少有12个点满足上述的两个条件时，p才是角点，所以这四个点中至少要有三个比候选的点同时亮（条件1）或者暗（条件2）。
首先检测1，9，如果$I_1, I_9$都在区间$[I_p - t, I_p + t]$内，那么候选点必然不是角点。
否则就检测5，13号点，检查这四个点是否有三个同时比$I_p + t$亮或者同时比$I_p - t$暗。
如果4个点中有3个同时比p亮或者暗，那么再检查剩余的点，看是否真正满足角点定义中的条件。
这样的方法相比完全按照定义的条件进行检测要快得多。但是，这样的做法仍然有短板：
- 当N<12时，这里介绍的高速检测方法就失效了
- 算法的效率受到待测点（圆上的点）的选择和顺序。但是考虑角点外部的分布，选择的点不可能是最优的
- 多个特征点会聚集在一起
使用机器学习的方法，可以帮助克服上述短板。具体可以参考wiki及论文。
非极大值抑制(Non-maximum suppression)
这个方法用来去除集束的特征点，去掉紧邻的特征点中角点强度较小的点，解决了上述的第三个短板。
定义： 如果N固定，称能使点p仍然为角点的最大的t为角点强度。两种方法可以用来找到角点强度：
- 二叉树可以用来搜索t的最大值。每次将一个不同的t放入决策树中时，决策树会试图找到最大的t，那个t就可以视为角点强度
- 另一种方法是在每次高速检测通过时，t递增一个小的量，最终可以找到t的最大值。
参考：
https://en.wikipedia.org/wiki/Features_from_accelerated_segment_test
http://www.cnblogs.com/ronny/p/4078710.html
