(四)OpenCV中的特征检测之用于角点检测的FAST算法
注释：本文翻译自OpenCV3.0.0 document->OpenCV-Python Tutorials，包括对原文档种错误代码的纠正
1.目标
- 了解fast算法的基础
- 我们将使用OpenCV中带FAST算法的函数好到角点
2.理论
我们看到了几个特征探测器，其中很多都非常棒。 但从实时应用角度来看，它们速度不够快。 一个最好的例子是SLAM（同时定位和映射）移动机器人，其计算资源有限。
作为一种解决方案，Edward Rosten和Tom Drummond在2006年的论文“用于高速角点检测的机器学习”（稍后在2010年对其进行了修订）中提出了FAST（来自加速段测试的特征）算法。 下面介绍该算法的基本概述。 有关更多详细信息，请参阅原稿纸张（所有图像均取自原始纸张）3.使用fast算法进行特征检测(feature detection using fast)
3.1选择要识别的兴趣点的图像中的像素p。让它的强度是I_p。
3.2选择合适的阈值t。
3.3考虑围绕被检测像素的16个像素的圆圈。(见下图）
3.4现在像素p是一个角落，如果在圆圈（16个像素）中存在一组n个连续像素，这些像素比I_p + t明亮，或者比I_p-t更暗。 （在上图中显示为白色虚线）。 n被选为12。
3.5提出了一个高速测试来排除大量的非角落。 这个测试只检测1个，9个，5个和13个四个像素（首先测试1和9是否太亮或太暗，如果是，则检查5和13）。 如果p是一个角，那么至少有三个必须比I_p + t亮或比I_p-t暗。 如果这两种情况都不是这样，那么p不能是角落。 然后可以通过检查圆中的所有像素，将全部分段测试标准应用于通过的候选。 这种探测器本身表现出高性能，但有几个缺点：
- 它不会拒绝n<12的候选人；
- 像素的选择不是最优的，因为它的效率取决于问题的排序和角落外观的分布；
- 高速测试的结果被抛弃；
- 多个特征被检测为彼此相邻；
机器学习算法解决了前3个问题。最后一个采用非最大抑制来解决的。
4.机器学习角点检测(machine learning a corner detector)
4.1选择一组用于训练的图像(最好来自目标应用程序域)
4.2在每个图像中运行FAST算法以查找特征
4.3对于每个特征点，将它周围的16个像素存储为一个向量。对所有图像进行处理以获得特征矢量p
4.4这16个像素中的每个像素(比如x)都可以具有以下三种形态之一：
4.5根据这些状态，特征向量P被细分为3个子集，P_d,P_s,P_b
4.6定义一个新的布尔变量K_p,如果p是一个角，则为true，否则为false
4.7使用ID3算法(决策树分类器)使用变量K_p查询每个子集以获得关于真实类的知识。它选择产生关于候选像素是否是角的最多信息的x，由K_p的熵测量。
4.8这是递归应用于所有的子集，直到它的熵为零
4.9如此创建的决策树用于其它图像中的快速检测
5.非最大抑制(Non-maximal Suppression)
在相邻位置检测多个兴趣点是另一个问题，它通过使用非最大抑制来解决。
5.1计算所有检测到的特征点的得分函数V。V是p和16个周围像素之间绝对差值的总和
5.2考虑两个相邻的关键点并计算它们的v值
5.3丢弃V值较低的那个
总结：它比其它现有的角落探测器快几倍。但是它对于高噪声水平并不稳健。它取决于阈值。
6.OpenCV中的FAST特征检测器(FAST Feature Detector in OpenCV)
它在OpenCV中被称为任何其他特征检测器。 如果您愿意，您可以指定阈值，是否应用非最大抑制，要使用的邻域等
对于邻域，定义了三个标志，cv2.FAST_FEATURE_DETECTOR_TYPE_5_8，cv2.FAST_FEATURE_DETECTOR_TYPE_7_12和cv2.FAST_FEATURE_DETECTOR_TYPE_9_16。以下是关于如何检测和绘制FAST特征点的简单代码。
# -*- coding: utf-8 -*-
'''
用于角点检测的Fast算法
'''
import cv2
import numpy as np
from matplotlib import pyplot as plt
img = cv2.imread('5.jpg', 0)
fast = cv2.FastFeatureDetector_create()
kp = fast.detect(img, None)
img2 = cv2.drawKeypoints(img, kp, None, color=(255, 0, 0))
cv2.imwrite('fast_true.jpg', img2)
# 输出所有默认参数
print('help of fast: ', help(fast))
print("Threshold: ", fast.getThreshold())
print("nonmaxSuppression", fast.getNonmaxSuppression())
fast.setNonmaxSuppression(0)
kp = fast.detect(img, None)
img3 = cv2.drawKeypoints(img, kp, None, color=(0, 255, 0))
cv2.imwrite('fast_false.jpg', img3)
res = cv2.bitwise_and(img2, img3)
res = np.hstack([img2, img3, res])
cv2.imshow('res',res)
cv2.waitKey(0) & 0xFF
cv2.destroyAllWindows()
结果：第一张图片显示了使用nonmaxSuppression的FAST和没有nonmaxSuppression的第二张图片，第三张图片是前两张做与运算