EEPW论坛

OpenCV-Python系列之FAST算法

我们已经学习带走几个特征检测器，它们都really good , 但是从实时的角度来说，它们的速度还不够快.作为解决方案，FAST（加速段测试的特征）算法由Edward Rosten和Tom Drummond在2006年的论文“Machine learning for high-speed corner detection”中提出（后来在2010年修订）。

FAST 全称 Features from accelerated segment test,一种用于角点检测的算法，该算法的原理是取图像中检测点，以该点为圆心的周围的16个像素点判断检测点是否为角点，通俗的讲就是中心的的像素值比大部分周围的像素值要亮一个阈值或者暗一个阈值则为角点：

实现步骤：

1.        一个以像素p为中心，半径为3的圆上，有16个像素点（p1、p2、...、p16）

2.        定义一个阈值，计算p1、p9与中心p的像素差，若它们绝对值都小于阈值，则p点不可能是特征点，直接pass掉，否则，当做候选点

3.        若p是候选点，则计算p1、p9、p5、p13与中心p的像素差，若它们的绝对值有至少3个超过阈值，则当做候选点，否则，直接pass掉

4.        若p是候选点，则计算p1到p16这16个点与中心p的像素差，若它们有至少9个超过阈值，则是特征点，否则，直接pass掉

5.        对图像进行非极大值抑制：计算特征点出的FAST得分值（即score值，也即s值），判断以特征点p为中心的一个邻域（如3x3或5x5）内，计算若有多个特征点，则判断每个特征点的s值（16个点与中心差值的绝对值总和），若p是邻域所有特征点中响应值最大的，则保留；否则，抑制。若邻域内只有一个特征点（角点），则保留，得分计算公式如下（公式中用V表示得分，t表示阈值）：

该检测器本身具有很高的性能，但有几个缺点：

• 它不会拒绝n < 12的候选对象。

• 像素的选择不是最佳的，因为其效率取决于问题的顺序和角落外观的分布。

• 高速测试的结果被丢弃了。

• 彼此相邻地检测到多个特征。

机器学习的方法解决了前三点。使用非最大抑制来解决最后一个问题。

让机器学习一个角检测器

1.选择一组图像进行训练（最好从目标应用范围内）

2.运行FAST算法来对每个图像进行特征点查找

3.对每个特征点，存下周围的16个像素作为向量。所有图像做完以后得到特征向量P。

4.这16个像素里的每个像素（设为x）可以有下面的三个状态：

5.根据这些状态，特征向量P被分成3个子集，Pd, Ps, Pb.

6.定义个新的布尔变量Kp,如果p是角就是真反之为假。

7.使用ID3算法（决策树分类）来查询每个子集，对于每个true类用变量Kp，它选择x来得出一个备选像素是否是角的信息。

8.对所有子集迭代直到为0

9.创建的决策树用来对其他图形做fast检测

非极大值抑制

在临近位置检测多个兴趣点是另一个问题，可以使用非极大值抑制来解决。

1.计算一个分数函数，V是所有检测到的特征点，V是p和16个围着的像素值得绝对差。

2.计算两个相邻关键点的V值

3.丢掉V值低的那个

现在我们开始进行试验：

来看代码：

def FAST(img):
     fast = cv2.FastFeatureDetector_create()
 
     # find and draw the keypoints
     kp = fast.detect(img, None)
     img2 = cv2.drawKeypoints(img, kp, None, color=(255, 0, 0))
 
     # Print all default params
     print("Threshold: {}".format(fast.getThreshold()))
     print("nonmaxSuppression:{}".format(fast.getNonmaxSuppression()))
     print("neighborhood: {}".format(fast.getType()))
     print("Total Keypoints with nonmaxSuppression: {}".format(len(kp)))
 
     cv2.imshow('fast_true', img2)
 
     # Disable nonmaxSuppression
     fast.setNonmaxSuppression(0)
     kp = fast.detect(img, None)
 
     print("Total Keypoints without nonmaxSuppression: {}".format(len(kp)))
 
     img3 = cv2.drawKeypoints(img, kp, None, color=(255, 0, 0))
 
     cv2.imshow('fast_false', img3)
 
     cv2.waitKey()

我们先来看看没有使用非极大值抑制的结果：

可以看到，特征点检测过多，现在我们来看看采用了非极大值抑制的方法输出的结果：

效果好的多。

最后总结：

  1、FAST算法比其他现有的角点探测器快几倍

  2、它对高水平的噪音并不鲁棒，效果取决于阈值的选择