容来自OpenCV-Python Tutorials 自己翻译整理

目标：
学习FAST算法的基本原理
使用opencv中的FAST算法寻找角点

原理：

之前学习到的一些特征点探测算法效果都很好，但是在实际使用当中速度不够快。一个最好的例子就是SLAM（同步定位与地图构建），运动状态的机器人对计算资源要求有不小的限制。

为了解决此问题，两个科学家提出了FAST算法，详细内弄可以参考原文。
两篇论文在此

使用FAST算法提取特征：
原理非常简单

首先选取一个像素点p,并判断p点是否为关键点。设<span class="MathJax" id="MathJax-Element-1-Frame" tabindex="0" data-mathml="ip" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">ipip为像素点p的灰度值。

选取适当的阈值t。

如图，对p点周围的16个像素点进行检测。

如果16个点当中存在n个连续的像素点都高于<span class="MathJax" id="MathJax-Element-2-Frame" tabindex="0" data-mathml="Ip+t" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">Ip+tIp+t或者都小于<span class="MathJax" id="MathJax-Element-3-Frame" tabindex="0" data-mathml="Ip−t" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">Ip−tIp−t，那么像素点p可看作一个角点。
上图中n为12，如虚线所示。

为了取得更快的速度，对于每个待检测的像素点，使用何种顺序去寻找周围的16个像素点也是有讲究的。

首先先找12点、3点、6点、9点钟方向的四个点，先检测12点和6点钟方向的点，然后是3点和9点钟方向的点。如果p点为角点，那么四个点至少有3个符合要求。如果小于3个，那么p点不是角点，放弃治疗。

不过，上面的方法有如下的几条缺点：

• 当n＜12时不会舍弃数量过多的候选点
• 像素的选取不是最优的，因为效果取决于问题的要求和角点的分布。
• 高速检测的结果被丢弃
• 检测到的特征点互相连接
  

前三个问题使用机器学习的手段解决，最后一个问题使用非极大值抑制的方法解决。

机器学习方法检测角点：

• 首先要找一组训练图片，最好找和最后应用相关的训练数据集。
• 用FAST算法寻找每一张图片的特征点。
• 将所有特征点周围的16个点存储为一向量
• 每个特征点周围的16个像素分为三类，暗、相似、明亮。
• 特征向量也按照暗、相似、明亮的特点分为三个子集。
• 设置一个bool类型的变量KpKp，如果p点是特征点，那么KpKp为真，否则为假。
• 利用ID3 决策树算法来查询每个自己，使用布尔型变量KpKp来标记真实分类的信息。选取到的像素点x会产生很多关于候选特征点是否是一个像素点信息，该信息由KPKP的熵值决定。
• 此过程递归的进行到所有的子集，直到熵值为0。
• 实现好的决策树可以用来快速探测特征点在其他的图片当中。
  

非极大值抑制：

非极大值检测的主要目的是选取局部区域的最大值，在图像处理或者区域识别方面有不少应用。

探测到的特征点相互连接的问题可以使用非极大值抑制的方法来解决。

• 对所有检测到的特征点计算打分函数V，V是像素点p与周围16个像素点差值的绝对值的和。
• 计算临近两个特征点打分函数V。
• 抛弃V值低的点。
  

总结：
优点：FAST算法很快

缺点：在噪声高的时候鲁棒性差，性能依赖阈值的设定。

FAST特征点检测在OpenCV中的使用：

可以调用OpenCV中的函数，指定阈值，知否使用非极大值抑制，使用邻域大小等等。

邻域大小有下面的三个flags（和文档上面的不一样！）

v2.FAST_FEATURE_DETECTOR_TYPE_5_8

cv2.FAST_FEATURE_DETECTOR_TYPE_7_12

cv2.FAST_FEATURE_DETECTOR_TYPE_9_16

函数内容如下：

etval   =   cv.FastFeatureDetector_create([, threshold[, nonmaxSuppression[, type]]])#创建FAST检测器

retval  =   cv.FastFeatureDetector.getNonmaxSuppression()#返回布尔型 是否使用非极大值抑制

retval  =   cv.FastFeatureDetector.getThreshold()#返回阈值

None    =   cv.FastFeatureDetector.setNonmaxSuppression(f)#设定非极大值抑制 bool型

None    =   cv.FastFeatureDetector.setThreshold(threshold)#设定阈值

文档在此

import numpy as np

import cv2

from matplotlib import pyplot as plt

img = cv2.imread('1.jpg',0)

fast=cv2.FastFeatureDetector_create(threshold=20,nonmaxSuppression=True,type=cv2.FAST_FEATURE_DETECTOR_TYPE_9_16)#获取FAST角点探测器

kp=fast.detect(img,None)#描述符

img = cv2.drawKeypoints(img,kp,img,color=(255,0,0))#画到img上面

print ("Threshold: ", fast.getThreshold())#输出阈值

print ("nonmaxSuppression: ", fast.getNonmaxSuppression())#是否使用非极大值抑制

print ("Total Keypoints with nonmaxSuppression: ", len(kp))#特征点个数

cv2.imshow('sp',img)

cv2.waitKey(0)

结果如图：

基本上五官都被覆盖了. -_-

输出值：

Threshold: 20
nonmaxSuppression: True
Total Keypoints with nonmaxSuppression: 357

奈斯，优秀