目标
在本章中,将了解
- FAST算法的基础知识
- 使用OpenCV功能对FAST算法进行探索
理论
在之前的文章中,已经了解了几个特征检测器,其中很多表现是非常优秀的。但是,从实时应用程序的角度来看,它们并不够快。最好的例子是计算资源有限的SLAM(同时定位和制图)移动机器人
为了解决这个问题,Edward Rosten和Tom Drummond在2006年的论文“Machine learning for high-speed corner detection”中提出了FAST(Features from Accelerated Segment Test)算法(后来在2010年对其进行了修订)。该算法的基本内容如下。有关更多详细信息,请参阅原始论文。
使用FAST进行特征检测
- 1选择图像中是否要识别为兴趣点的像素pp,假设其强度为IpI_p
- 2 选择适当的阈值tt
- 3 考虑被测像素周围有16个像素的圆圈(见下图)
- 4 现在,如果以pp点为圆心的圆中存在一组(共16个像素)n个连续的像素,它们均比Ip+tI_p + t 亮,或者比Ip−tI_p-t 都暗,则像素pp是一个角。(在上图中显示为白色虚线)。n被选为12。
- 5 建议使用高速测试以排除大量的非角区域。此测试仅检查1、9、5和13处的四个像素(如果第一个1和9太亮或太暗,则对其进行测试。如果是,则检查5和13)。如果pp是一个角,则其中至少三个必须全部比Ip+tI_p + t 亮或比Ip−tI_p-t 暗。如果以上两种情况都不是,则pp不能为角。然后,可以通过检查圆中的所有像素,将完整的分段测试标准应用于通过的候选项。该检测器本身具有很高的性能,但有几个缺点:
- 不会拒绝n<12n < 12的候选对象
- 像素的选择不是最佳的,因为其效率取决于问题的顺序和角外观的分布
- 高速测试的结果被丢弃
- 彼此相邻地检测到多个特征
使用机器学习的方法解决前三点。使用非最大抑制来解决最后一个问题
机器学习角点检测器
- 选择一组图像进行训练(最好从目标应用程序域中进行训练)
- 在每个图像中运行FAST算法以查找特征点
- 对于每个特征点,将其周围的16个像素存储为矢量。对所有图像执行此操作以获得特征向量P
- 这16个像素中的每个像素(例如x)可以具有以下三种状态之一:
- 取决于这些状态,特征矢量P被分为3个子集,PdP_d , PsP_s ,PbP_b
- 定义一个新的布尔变量KpK_p, 如果pp是一个角,则为true,否则为false
- 使用ID3算法(决策树分类器)使用变量KpK_p查询每个子集,以获取有关真实类的知识。它选择x,该x通过KpK_p的熵测得的有关候选像素是否为角的信息最多
- 递归地将其应用于所有子集,直到其熵为零为止
- 创建的决策树用于其他图像的快速检测
理解: 将特征点P及相邻的16个点计算距离并统计落在那个子集中,统计每个子集的数量作为特征,然后基于标签KpK_p来使用ID3决策树
非最大抑制(Non-maximal Suppression)
在相邻位置检测出多个兴趣点是另一个问题。通过使用非极大抑制来解决
- 计算所有检测到的特征点的得分函数,VV用于所有检测到的特征点, VV是pp与16个周围像素值之间的绝对差之和
- 考虑两个相邻的关键点并计算它们的VV值
- 丢弃较低VV值的那个关键点
总结
- 它比其他现有的拐角检测器快几倍。
- 但是它对高水平的噪声并不鲁棒, 取决于阈值的设定
OpenCV中的FAST角点检测器
它被称为OpenCV中的任何其他特征检测器。
如果需要,也可以指定阈值,是否要应用非极大抑制以及要使用的邻域等。
对于邻域,定义了三个标志,分别为*
cv.FAST_FEATURE_DETECTOR_TYPE_5_8
cv.FAST_FEATURE_DETECTOR_TYPE_7_12
cv.FAST_FEATURE_DETECTOR_TYPE_9_16
以下是有关如何检测和绘制FAST特征点的简单代码。
import cv2
import numpy as np
from matplotlib import pyplot as plt
img = cv2.imread('fly.png')
# Initiate FAST object with default values
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)) )
# Disable nonmaxSuppression
fast.setNonmaxSuppression(0)
kp = fast.detect(img, None)
img3 = cv2.drawKeypoints(img, kp, None, color=(255, 0, 0))
# plot
plt.subplot(131)
plt.imshow(img)
plt.xticks([])
plt.yticks([])
plt.title('origin')
plt.subplot(132)
plt.imshow(img2)
plt.xticks([])
plt.yticks([])
plt.title('nms')
plt.subplot(133)
plt.imshow(img3)
plt.xticks([])
plt.yticks([])
plt.title('non nms')
plt.show()
查看结果。第二张图片显示了带有nonmaxSuppression的FAST,第三张图片显示了没有nonmaxSuppression的FAST:
附加资源
- docs.opencv.org/4.1.2/df/d0…
- Edward Rosten and Tom Drummond, “Machine learning for high speed corner detection” in 9th European Conference on Computer Vision, vol. 1, 2006, pp. 430–443.
- Edward Rosten, Reid Porter, and Tom Drummond, “Faster and better: a machine learning approach to corner detection” in IEEE Trans. Pattern Analysis and Machine Intelligence, 2010, vol 32, pp. 105-119.
- ID3