理论
我们看到了一些特征检测算法,他们很多都不错,但是从实时应用的角度看,他们都不够快,一个最好的例子是SLAM(同步定位与地图创建)移动机器人没有足够的计算能力。
作为解决方案,FAST(加速切片测试特征)算法被提出,Edward Rosten和Tom Drummond 2006年在他们的论文“Machine learning for high-speed corner detection”提出,并在2010年最后修订,算法的基本大意如下:
使用FAST进行特征检测
1.选择一个图像里的像素p用来识别是不是一个兴趣点,它的强度是Ip
2.选择一个合适的阈值t
3.在要测试的像素周围找16个像素的圆
4.现在如果存在一个在圆内(16像素的)的n个连续像素集合,他们都比Ip + t要亮,或者都比Ip - t 要暗(用白虚线显示),那p就是角, n取12。
5.用一个高速测试来排除大量非角。这个测试只检查1,9,5和13位置的像素(首先1和9会测试是否他们太亮或者太暗,如果是,再检查5和13)。如果p是角,那么至少3个都比Ip+t要亮或者比Ip-t要暗,如果不是这样,那么p不可能是角。这个检测器展现了高性能,但是有几个缺陷:
·当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值低的那个
总结:
它比其他存在的角点算法要快几倍
但是它对高噪点情况来说不健壮,依赖阈值
OpenCV里的FAST特征检测
它和其他OpenCV里的特征检测类似,如果你愿意,你可以指定阈值,是否使用非极大值抑制,要用的邻居等。
对于邻居,定义了三个标志位, cv2.FAST_FEATURE_DETECTOR_TYPE_5_8, cv2.FAST_FEATURE_DETECTOR_TYPE_7_12和cv2.FAST_FEATURE_DETECTOR_TYPE_9_16.
import numpy as np
import cv2
from matplotlib import pyplot as pltimg = cv2.imread('simple.jpg',0)
# Initiate FAST object with default values
fast = cv2.FastFeatureDetector()# find and draw the keypoints
kp = fast.detect(img,None)
img2 = cv2.drawKeypoints(img, kp, color=(255,0,0))# Print all default params
print "Threshold: ", fast.getInt('threshold')
print "nonmaxSuppression: ", fast.getBool('nonmaxSuppression')
print "neighborhood: ", fast.getInt('type')
print "Total Keypoints with nonmaxSuppression: ", len(kp)cv2.imwrite('fast_true.png',img2)
# Disable nonmaxSuppression
fast.setBool('nonmaxSuppression',0)
kp = fast.detect(img,None)print "Total Keypoints without nonmaxSuppression: ", len(kp)
img3 = cv2.drawKeypoints(img, kp, color=(255,0,0))
cv2.imwrite('fast_false.png',img3)
看结果,第一个图像显示了使用了非极大值抑制的FAST,第二个是没有使用非极大值抑制的。
END