1. 概述

若某像素点与周围邻域足够多的像素点处于不同区域，则该像素可能为角点。考虑灰度图像，即若某像素点的灰度值比周围邻域足够多的像素点的灰度值大或小，则该点可能为角点
Viswanathan D G. Features from accelerated segment test (fast)[J]. Homepages. Inf. Ed. Ac. Uk, 2009.
算法特点
- FAST算法比其他角点检测算法要快
- 受图像噪声以及设定阈值影响较大
- 当设置n<12时，不能用快速方法过滤非角点
- FAST不产生多尺度特征，不具备旋转不变性，而且检测到的角点不是最优

2. 算法详解

对于图像中一个像素点p，其灰度值为Ip
以该像素点为中心考虑一个半径为3的离散化的Bresenham圆，圆边界上有16个像素(如下图所示)
设定一个合适的阈值tt，如果圆上有n个连续像素点的灰度值小于Ip−t或者大于Ip+t，那么这个点即可判断为角点(n的值可取12或9)

一种快速排除大部分非角点像素的方法就是检查周围1、5、9、13四个位置的像素，如果位置1和9与中心像素P点的灰度差小于给定阈值，则P点不可能是角点，直接排除；否则进一步判断位置5和13与中心像素的灰度差，如果四个像素中至少有3个像素与P点的灰度差超过阈值，则考察邻域圆上16个像素点与中心点的灰度差，如果有至少9个超过给定阈值则认为是角点。

3. 角点分类器

选取需要检测的场景的多张图像进行FAST角点检测，选取合适的阈值n(n<12)，提取多个特征点作为训练数据
对于特征点邻域圆上的16个像素x∈1,2,…,16x∈1,2,…,16，按下式将其划分为3类

对每个特征点定义一个bool变量KpKp，如果pp是一个角点，则KpKp为真，否则为假
对提取的特征点集进行训练，使用ID3算法建立一颗决策树，通过第x个像素点进行决策树的划分，对集合P，得到熵值为

选择信息增益最大位置进行划分，得到决策树
使用决策树对类似场景进行特征点的检测与分类

4. 非极大值抑制

对于邻近位置存在多个特征点的情况，需要进一步做非极大值抑制(Non-Maximal Suppression)。给每个已经检测到的角点一个量化的值V，然后比较相邻角点的V值，保留局部邻域内VV值最大的点。V值可定义为
- 特征点与邻域16个像素点灰度绝对差值的和

5. 代码实现

OpenCV3中FAST方法以FastFeatureDetector类的形式封装，为Feature2D类的子类

class CV_EXPORTS_W FastFeatureDetector : public Feature2D
{
public:
    enum
    {
        TYPE_5_8 = 0, TYPE_7_12 = 1, TYPE_9_16 = 2,
        THRESHOLD = 10000, NONMAX_SUPPRESSION=10001, FAST_N=10002,
    };
    CV_WRAP static Ptr<FastFeatureDetector> create( 
int threshold=10, 
bool nonmaxSuppression=true,
int type=FastFeatureDetector::TYPE_9_16 );
    CV_WRAP virtual void setThreshold(int threshold) = 0;
    CV_WRAP virtual int getThreshold() const = 0;
    CV_WRAP virtual void setNonmaxSuppression(bool f) = 0;
    CV_WRAP virtual bool getNonmaxSuppression() const = 0;
    CV_WRAP virtual void setType(int type) = 0;
    CV_WRAP virtual int getType() const = 0;
};