8.4. 角点检测的快速算法

8.4.1. 目标

在本章中，
-我们将了解快速算法的基础知识-我们将使用OpenCV功能来查找快速算法的角点。

8.4.2. 理论

我们看到了几个特征检测器，其中很多非常好。但从实时应用的角度来看，它们还不够快。一个最好的例子是SLAM（同时定位和映射）移动机器人，它的计算资源有限。

为了解决这一问题，Edward Rosten和Tom Drummond在2006年的论文《高速角点检测的机器学习》中提出了FAST算法（加速段测试的特征）。算法的基本总结如下。更多细节请参阅原稿（所有图片均取自原稿）。

快速特征检测

  1. 选择像素 \(p\) 在图像中是否被识别为兴趣点。让它的强度 \(I_p\) .

  2. 选择适当的阈值 \(t\) .

  3. 假设被测像素周围有一个16像素的圆。（见下图）

> <img src="images/fast_speedtest.jpg" alt="A corner in the image" class="align-center" />

  1. 现在是像素 \(p\) 如果存在一组 \(n\) 圆圈中的连续像素（16像素），其亮度均大于 \(I_p + t\) ，或者比 \(I_p − t\) . （在上图中显示为白色虚线）。 \(n\) 被选为12岁。

  2. A high-speed test 被提议排除大量非拐角。此测试仅检查1、9、5和13处的四个像素（如果第一个1和9太亮或太暗，则测试它们）。如果是，则检查5和13）。如果 \(p\) 是一个角落，那么至少有三个角落比 \(I_p + t\) 或者比 \(I_p − t\) . 如果这两个都不是，那么 \(p\) 不能是角落。然后，通过检查圆中的所有像素，可以将全段测试标准应用于通过的候选对象。这种探测器本身表现出高性能，但有几个弱点：

> -   It does not reject as many candidates for n &lt; 12.
> -   The choice of pixels is not optimal because its efficiency
>     depends on ordering of the questions and distribution of
>     corner appearances.
> -   Results of high-speed tests are thrown away.
> -   Multiple features are detected adjacent to one another.

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

角点检测的机器学习

  1. 选择一组要训练的图像（最好来自目标应用程序域）

  2. 在每个图像中运行快速算法以找到特征点。

  3. 对于每个特征点，将其周围的16个像素存储为向量。对所有图像进行此操作以获得特征向量 \(P\) .

  4. 每个像素（比如 \(x\) )在这16个像素中，可以具有以下三种状态之一：

> <img src="images/fast_eqns.jpg" alt="FAST equation" class="align-center" />

  1. 根据这些状态，特征向量 \(P\) 分为3个子集， \(P_d\) ， \(P_s\) ， \(P_b\) .

  2. 定义一个新的布尔变量， \(K_p\) ，如果 \(p\) 是一个角落，否则就错了。

  3. 使用ID3算法（决策树分类器）使用变量查询每个子集 \(K_p\) 为了了解真正的班级。它选择 \(x\) 它产生了关于候选像素是否是角点的最大信息，由 \(K_p\) .

  4. 它递归地应用于所有子集，直到其熵为零。

  5. 这样生成的决策树用于其他图像的快速检测。

非最大抑制

在相邻位置检测多个兴趣点是另一个问题。采用非最大值抑制法求解。

  1. 计算得分函数， \(V\) 所有检测到的特征点。 \(V\) 是 \(p\) 以及16个周围像素值。

  2. 考虑两个相邻的关键点并计算它们 \(V\) 价值观。

  3. 丢弃较低的那个 \(V\) 价值。

总结

它比其他现有的角点探测器快几倍。

但它对高强度的噪声不具有鲁棒性。这取决于一个门槛。

8.4.3. OpenCV中的快速特征检测

它被称为OpenCV中的任何其他特征检测器。如果需要，可以指定阈值、是否应用非最大抑制、要使用的邻域等。

对于邻里，定义了三个标志， cv2.FAST_FEATURE_DETECTOR_TYPE_5_8 ， cv2.FAST_FEATURE_DETECTOR_TYPE_7_12 和 cv2.FAST_FEATURE_DETECTOR_TYPE_9_16 . 下面是一个关于如何检测和绘制快速特征点的简单代码。

>>> %matplotlib inline
>>>
>>> import numpy as np
>>> import cv2 as cv
>>> from matplotlib import pyplot as plt
>>> img = cv.imread('/cvdata/simple.jpg',0)
>>> # Initiate FAST object with default values
>>> fast = cv.FastFeatureDetector_create()
>>> # find and draw the keypoints
>>> kp = fast.detect(img,None)
>>> img2 = cv.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)) )
>>> cv.imwrite('xx_fast_true.png',img2)

Threshold: 10
nonmaxSuppression:True
neighborhood: 2
Total Keypoints with nonmaxSuppression: 431

True

>>> plt.imshow(img2)

<matplotlib.image.AxesImage at 0x7fbf813879b0>
../_images/sec06-fast_8_1.png 
>>> # Disable nonmaxSuppression
>>> fast.setNonmaxSuppression(0)
>>> kp = fast.detect(img,None)
>>> print( "Total Keypoints without nonmaxSuppression: {}".format(len(kp)) )
>>> img3 = cv.drawKeypoints(img, kp, None, color=(255,0,0))
>>> cv.imwrite('xx_fast_false.png',img3)

Total Keypoints without nonmaxSuppression: 1575

True

>>> plt.imshow(img3)

<matplotlib.image.AxesImage at 0x7fbf813fec50>
../_images/sec06-fast_10_1.png

看看结果。第一幅图像显示的是非轴抑制的快速图像，第二幅图像显示的是非轴抑制的快速图像：

8.4.4. 额外资源

  1. Edward Rosten和Tom Drummond，“用于高速拐角检测的机器学习”，第9届欧洲计算机视觉会议，2006年第1卷，第430-443页。

  2. Edward Rosten、Reid Porter和Tom Drummond，在IEEE Trans中，“更快更好：角点检测的机器学习方法”。模式分析和机器智能，2010年，第32卷，第105-119页。

8.4.5. 练习