OpenCV基础教程——特征提取与描述（FAST算法）

角点检测的FAST算法

目标：

本章节你需要学习以下内容:

    *我们将了解FAST算法的基础知识
    *我们将使用OpenCV功能为FAST算法找到角点
    
    
      
      
    
    代码解读

1、理论

在分析中发现了一些特征探测器，在性能上相当出色。然而，在实时应用中的效率考量下，这些设备仍显不足。其中最具代表性的案例是基于有限计算资源实现的SLAM（同步构建与地图定位）机器人系统。

为了求解这一问题，Edward Rosten 和 Tom Drummond 在 2006 年提出了 FAST 算法。我们将详细介绍该算法的基本原理和实现过程。你可以参考原始文献进一步了解（本节中所有图片均为来自原始文章）。

（1）使用 FAST 算法进行特征提取

在图像中选择一个像素点p，并判定该像素点是否为关键点。其中I_p代表该像素点对应的灰度值。

选择适当的阈值 t。

如下图所示在像素点 p 的周围选择 16 个像素点进行测试。

如果在这16个像素点中至少存在连续n个像素点其灰度值均高于I_p + t或低于I_p - t则认为该像素点p为角点如图所示n取值为12

为了提高运行效率，并非仅依赖于现有方法，在此我们采用了额外优化策略。具体而言，在候选点选择阶段，默认会考察围绕该点每隔一定角度选取四个关键点（编号为1、9、5、13）进行初步测试。在这一过程中，“先测试1和19, 如果它们均满足阈值条件，则继续测试5和13”。当检测到目标点p为角点时，则要求这四个关键点中至少有三个必须满足阈值条件；如果未能达到这一标准，则直接判定该点并非角点而予以排除。对于通过上述筛选阶段确认的候选点，则需进一步进行二次验证（是否存在第十二个方向上的特征满足特定指标）。该检测系统具有较高的识别准确率但存在以下几点不足：其主要缺陷包括计算复杂度较高以及对噪声敏感等问题。

• 当n小于12时它未舍弃大量候选点（产出较多）。
  • 像素选取并非最佳方案 因为其效果受制于所解决的问题以及角点分布的情况。
  • 高速测试结果未能保留
  • 检测到的特点多数呈现连贯性

前三项问题可由机器学习的具体方案来处理，剩余的问题则可应用非最大值抑制的技术手段。

（2）机器学习的角点检测器

选择一组训练图片（最好是跟最后应用相关的图片）

使用 FAST 算法找出每幅图像的特征点

对于每一个特征点，在其邻近区域存储并形成16个像素组成的向量。针对所有图像分别进行该操作以生成特征向量P

每一个特征点的 16 像素点都属于下列三类中的一种。

根据这些像素点的分类，特征向量 P 也被分为 3 个子集：P d ，P s ，P b

我们命名一个新的布尔变量K_p为True或False。当p是角点时将其设为True；否则设为False。

基于ID3算法（一种基于决策树的分类器）采用变量 K_p 对各个子集进行查询操作。该算法通过分析候选像素是否为拐角时所获得的信息量最大来确定最佳分割位置；其信息增益基于对变量 K_p 计算熵值的基础上得出最优解

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

将构建好的决策树运用于其他图像的快速的检测。

（3）非极大值抑制

使用极大值抑制的方法可以解决检测到的特征点相连的问题

对所有检测到的特征点建立一个打分函数 V。V 是由像素点 p 与其周围的 16 个像素点之间的差值绝对值累加而得。

计算临近两个特征点的打分函数 V。

忽略 V 值最低的特征点

（4）总结

FAST 算法相较于其它角点检测算法更快运行。然而，在噪声非常高的情况下不够稳定，这归因于其阈值设置。

2、OpenCV中的FAST特征检测器

它被称为OpenCV中的其他特征检测器。如果你愿意，则可以选择指定以下参数：阈值、是否采用非最大抑制以及所使用的邻域。

在邻域范围内设置了三个特定类型的标志参数，并分别为它们指定了不同的计算公式：cv.FAST_FEATURE_DETECTOR_TYPE_5_8、cv.FAST_FEATURE_DETECTOR_TYPE_7_12以及cv.FAST_FEATURE_DETECTOR_TYPE_9_16。以下将介绍一个使用OpenCV实现FAST特征点检测与绘制的示例代码。

    import numpy as np
    import cv2 as cv
    from matplotlib import pyplot as plt
    
    img = cv.imread('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('fast_true.png',img2)
    
    # 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('fast_false.png',img3)
    
    
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
    
    代码解读

结果显示如下图所示。第一张图片展示了该方法结合非极大值抑制法的运行情况（fAST with nonmaxSuppression），而另一张图片则未采用非极大值抑制法