图像处理特征不变算子系列之FAST算子（四）
图像处理特征不变算子系列之FAST算子（四）
kezunhai@gmail.com
http://blog.csdn.net/kezunhai
在前面分别介绍了：图像处理特征不变算子系列之Moravec算子（一）、图像处理特征不变算子系列之Harris算子（二）和图像处理特征不变算子系列之SUSAN算子（三）。今天我们将介绍另外一个特征检测算子---FAST算子， FAST算子是Rosten等人在SUSAN角点特征检测方法的基础上利用机器学习方法提出的，本文将对FAST算子进行详细地分析。
前面的SUSAN算子，这里的FAST算子，读起来真的是上口，尤其是与其全名比起来。FAST的全名是：Features from Accelerated Segment Test（翻译成：加速分割测试特征，多少有点别扭）。FAST算子如其名，计算速度快，可以应用与实时场景中。在FAST特征提出之后，实时计算机视觉应用中特征提取性能才有显著改善。目前以其高计算效率(computational performance)、高可重复性(high repeatability)成为计算机视觉领域最流行的角点检测方法。
FAST算法包含3个主要步骤：
（1）对固定半径圆上的像素进行分割测试，通过逻辑测试可以去处大量的非特征候选点；
（ 2）基于分类的角点特征检测，利用ID3 分类器根据16个特征判决候选点是否为角点特征，每个特征的状态为一1，0，1。
（3）利用非极大值抑制进行角点特征的验证。
下面我们对这3个步骤进行分析。
1）固定半径圆上的像素进行分割测试（Segment Test）
在分割测试中，可以去除大量的非候选角点，这样就可以把可能的角点帅选出来。分割测试是通过对一固定半径的圆形模板的比较和计算进行的，在FAST角点检测算子中，一般是通过半径为3.4 pixel、外围16个像素的圆的作为模板，通过下图我们来具体分析下分割测试。
在上图中，是12点的分割测试角点检测算法的示意图（还有9点的分割测试角点检测，具体参考后面的参考资料）。12点分割测试角点检测算法是在一个图像块上进行，如上图中的左边方块，其中p是中心像素点，12点取的是图上用弧线连接的12个点的像素值都大于或都小于中心像素值，则认为该点处是候选角点（为什么选择12点，因为通过测试，12点的角点检测性能最稳定、速度更快、效果也很好，当然有些文献指出9点的方式也很好）。分割测试是怎么进行的呢？用下面的公式来说，便可一目了然。
上式中，t是一个阈值（默认取值为10，不同场景取值有差异），Ip表示的是中心像素的像素值，Ip->x表示的是圆形模板中的像素值上式的意思是：当中心像素的像素值Ip小于x处的像素值Ip->x+t时，则该像素属于darker，Sp->x=d，其他两种情况分别表示亮些和相似。这样一个块（圆形）区域就可以分成d、s和b三种类型。这时候只要统计圆形区域中d或b的次数，只要d或b出现的次数大于n（（当是12点分割测试角点检测时，n=12；当是9点时，则n=9），那么该点就被认为是候选角点。
在分割测试步骤中，为了加快速度，其实不需要对这些像素进行逐一的比较。简单来说：首先比较1、5、9、13处点的像素值（也即水平方向和垂直方向上的4个点）与中心像素值的大小，如果这四个点中的像素值有3个或3个以上大于Ip+t或小于Ip-t，那么则认为该处是一个候选角点，否则就不可能是角点。
2）ID3决策树算法来训练角点检测
通过上式中比较，可以将模板内的像素分成三部分d、s、b，分别记为：Pd，Ps，Pb。因此对于每个Sp->x都属于Pd，Ps，Pb中的一个。另外，令Kp为true，如果p为角点，否则为false。通过ID3算法来选择具有最大信息增益的像素来判断一个像素是否为角点。Kp的熵用下式来计算：
某一像素的信息增益通过下式来表示：
对上述像素依次进行如上处理，选择像素增益最大的像素作为判断角点的依据，生成决策树，从而实现角点的正确分类。
3）非极大值抑制
在上面的分割测试中，没有计算角点响应函数（Corner Response Function），非极大值抑制无法直接应用于提取的特征。因此，定义一个角点响应函数V，考虑到分割测试的特征以及计算速度的需要，角点响应函数的定义如下：
定义了角点响应函数后，就可以采用常规的非极大值抑制方法对非角点进行排除了。
总结：FAST角点检测算法是一种具有高计算效率(computational performance)、高可重复性(high repeatability)特征提取算子，在立体图像匹配、图像配准、目标识别、目标跟踪、场景重构等领域得到了广泛的应用，成为计算机视觉领域最流行的角点检测方法。但是，噪声对该算子的影响比较大，而且阈值t对算子的影响比较大。
更多信息请参考：
1、FAST Corner Detection -- Edward Rosten：http://www.edwardrosten.com/work/fast.html
2、A Brief History of FAST corner detector：http://blog.csdn.net/anshan1984/article/details/8867653
3、AGAST Corner Detector: faster than FAST and even FAST-ER：http://www6.in.tum.de/Main/ResearchAgast
作者：kezunhai 出处：http://blog.csdn.net/kezunhai 欢迎转载或分享，但请务必声明文章出处。
