特征提取的综合实验（多种角度比较SIFT、SURF、BRISK、ORB、FREAK等局部特诊点检测和描述算法)（版）

     编者按：这篇文章原本只是《学习OpenCV3.0(高级-特征点提取和运用)》中的一篇教案，自编成以来，多次受到读者关注，并且就其中细节问题的进行沟通了解。这里我结合近一段时间对这个方面问题的再次学习思考，将相关内容进行整理，希望能够为大家的学习提供帮助。

    本文初步计划分为四个部分。“基本概念”部分对局部特征识别方法进行总体了解；“检测算法”将按照一定顺序对现有算法进行拆解；“综合实验”部分将引入相关图像库为实际比较各种算法速度和准确率。其它部分都是对这三个主要部分的补充。

    一、基本概念

    “图像局部特征点的检测、描述和比对”在“目标识别、图像拼接、运动跟踪、图像检索、自动定位”等研究中起着重要作用。OpenCV作为一款开放源代码仓库，收录实现了多种具有代表性的检测和描述算法。其中包括以Harris为代表的角点算法、以Sift为代表的特征点算法和新出现的SimpleBlob 算法等。这些算法的理论和实现方面存在参考和借鉴的关系；在算法封装的过程中也层面出“由分散到统一”的趋势；从时间上也能够看出前后联系、

    角点算法包括:

    1、Kitchen-Rosonfeld角点算法；

    2、Canny边缘检测算法；

    3、Harris角点检测方法（1988）；

    4、Shi-Tomasi角点检测方法；

    特征点方法包括：

    1、SIFT,Distinctive Image Features from Scale-Invariant Keypoints（1999-2004）；

    2、SURF,Speeded Up Robust Features（2006-2008）；

    3、FAST ,Machine Learning for High-speed Corner Detection（2006-2009）；

    4、STAR，Censure: Center surround extremas for realtime feature detection and matching（2008）；

    5、BRIEF(2010);

    6、BRISK，BRISK: Binary Robust Invariant Scalable Keypoints（2011）；

    7、ORB: an efficient alternative to SIFT or SURF（2011）

    8、FREAK 视网膜方法 (2012)

    其中，即使是最新的FREAK算法也已经有10余年的历史了，相关技术应用都已经比较成熟且深入。在进入深度学习和人工智能全面推开应用的今日，我们研究经典算法仍然是非常有意义的：

    1、通过综合实验，能够明确每一种算法能够达到怎样的识别质量和速度，对于解决实际问题提供重要参考；

    2、通过对比研究，能够在求图像的一阶微分、二阶偏微分图像上获得很多实用技术，这对于我们解决图像增强、识别问题都很有帮助；

    3、通过研读代码，能够观看欣赏每一种算法的实现细节，由于特征点算法运算量比较大，所以经常能够看到优化算法，极具参考价值。

    另关于SimpleBlob 算法的应用可以参考这篇《OpenCV图像处理中“找圆技术”的使用》，这篇文章中比较了几种OpenCV中的找圆方法并提出一种综合应用方法，我认为已经比较完整，这里就不展开。

    二、检测算法

    详细的算法解析和实现请参考书籍《图像局部特征检测和描述--基于OpenCV源码分析的算法与实现》，这里我仅从学习者和普通角度出发，对角点、特征点算法中具有特性的地方进行简单思考。

    1、Kitchen-Rosenfeld是最早出现的角点算法，解决“从0到1”的问题。它的算法思想非常简单直接：“当某一点曲率与梯度值的乘积大于某一个阈值则认为是角点”。由于“曲率”和“梯度"都是可以被解析表示的。

    C=kg=k(Ix​2+Iy​2)21​

     k=div(∇I/|∇I|)=IyyI2x−2IxyIxIy+IxxI2y(I2x+I2y)3/2

    

     

    OpenCV中可以使用Sobel运算可以直接对标梯度计算，故它的实现简单（篇幅原因这里不贴，下同），从结果上来看，能够检测到明显的角点:

    2、Canny方法提出了特征检测评价标准，它实际上是一种边缘检测方法。可以分为以下5个步骤：1）应用高斯滤波来平滑图像，目的是去除噪声

找寻图像的强度梯度（intensity gradients）；2）应用非最大抑制（non-maximum suppression）技术来消除边误检；3）应用双阈值的方法来决定可能的（潜在的）边界；4）利用滞后技术来跟踪边界。

    它的思路自成一体，非常经典，但是并没有得到后期算法延续发展；OpenCV中的实现将所有的Mat内容转换为int指针来进行，造成代码比较晦涩，无法判断是否符合现代方法。

    3、Harris

    当一个窗口在图像上移动，在平滑区域如图(a)，窗口在各个方向上没有变化。在边缘上如图(b)，窗口在边缘的方向上没有变化。在角点处如图(c)，窗口在各个方向上具有变化。Harris角点检测正是利用了这个直观的物理现象，通过窗口在各个方向上的变化程度，决定是否为角点。

 

    实际计算过程中，通过特征值 λ1 和 λ2 来决定一个窗口是平面、边缘还是角点：

     

 

 

    平面: 该窗口在平坦区域上滑动，窗口内的灰度值基本不会发生变化，所以  值非常小，在水平和竖直方向的变化量均较小，即和都较小，那么 λ1 和 λ2 都较小；

    边缘: 值为负数，仅在水平或竖直方向有较大的变化量，即和 只有一个较大，也就是 λ1>>λ2 或 λ2>>λ1；

    角点: 值很大，在水平、竖直两个方向上变化均较大的点，即和都较大，也就是 λ1 和 λ2 都很大

    

    我认为Harris方法比较重要 ，因为显而易见它提出的这种类似卷积的扫描方法在未来的算法中被不断运用。

    4、Shi-Tomasi

    Shi-Tomasi 的重要发现是角点的稳定性其实和矩阵 M 的较小特征值有关，于是直接用较小的那个特征值作为分数。这样就不用调整k值了。所以 Shi-Tomasi 将分数公式改为如下形式：

   此外它在实现过程中集成了大量优化方法，所以最后结果在角点检测中是最好的。

   

 

     以上“角点”算法大多基于图像的1阶导进计算，往往是提出一个函数模型，而后将计算出来的特征值带入到这个模型中，得出最终定量结果。从Sift开始，引入更有系统的模型和更复杂的描述符。由于特征点识别算法都比较系统和复杂，所以这里我只是将一些个人认为最有价值的知识点一点。

    5、SIFT,Distinctive Image Features from Scale-Invariant Keypoints（1999-2004）

    SIFT方法是特征点算法的开山之作，它的算法定义和实现比较复杂（甚至比后面出现的算法还要复杂），让我印象深刻的是这些：

    

    高斯差分金字塔，这种使用方法在未来很多算法中被重复使用。

    

    空间局域最大值搜索，个人认为这是一种低效的搜索方法，在未来的算法中比较少见。

    6、SURF,Speeded Up Robust Features（2006-2008）

    

    积分图像，这种技术不仅在特征点识别领域得到应用，在其他很多领域也是同样有用。

   

    此外，SURF采用的简化的滤波运算。这对于特征点识别来说可能是有用的，但是对于滤波来说是不行的。因为BoxFilter将带来无法避免的颗粒感，这是无法接受的。

    SURF算法在很多方面借鉴了SIFT的成功经验，正是由于它采用了简化的算子，所以SURF的抗干扰能力强于SIFT算法、SURF可以实现并行计算但是SURF算法的精度略逊于SIFT算法,且在亮度不变性和视角不变性方面，SURF算法不如SIFT算法。

    7、FAST ,Machine Learning for High-speed Corner Detection（2006-2009）

    

    Fast方法第一次丢弃了上面提出的“空间局域最大值搜索”，转而采用二维平面算子的方法进行特征搜索。个人认为这是最大的特点。

    8、STAR，Censure: Center surround extremas for realtime feature detection and matching（2008）

     Star特征，也被称为中心环绕极值（或CenSurE）功能，试图解决提供哈尔角点或FAST特征的局部化水平的问题，同时还提供尺度不变性。

    Star方法使用的是类似五角星的平面算子。在后出现的算法中，Star存在复用的情况。

    9、BRIEF(2010)

    BRIEF，即二进制鲁棒独立基本特征，是一种相对较新的算法，BRIEF不找到关键点；相反，它用于生成可通过任何其他可用的特征检测器算法定位的关键点的描述符。

    听别人说比较适合永远嵌入式系统，并且它只是一种描述符方法。

    10、BRISK，BRISK: Binary Robust Invariant Scalable Keypoints（2011）

    Leutenegger等人介绍的BRISK40描述符,试图以两种不同的方式改进Brief。 首先，BRISK引入了自己的一个特征检测器； 其次，BRISK的特征本身虽然与BRIEF原则相似，却尝试以提高整体功能的鲁棒性的方式进行二值比较。

    

    它使用金子塔的方式较SIFT/SURF等更为简单。

    11、ORB: an efficient alternative to SIFT or SURF（2011）

    创建了ORB功能[，其目标是为SIFT或SURF提供更高速的替代品。一定需要注意这个算法是真正的开放源代码，而且提供了不错的准确率。

    12、FREAK 视网膜方法 (2012)

    FREAK描述符最初是作为Brief，BRISK和ORB的改进引入的，它是一个生物启发式的描述符，其功能非常类似于BRIEF，主要在于它计算二进制比较的领域的方式[Alahi12]。

  

    基础视网膜的特征提取，个人认为优势不是很明显。

    

     三、综合实验

    3.1数据集

  为pascal中取出的6个数据，分别针对特征点提取的6个部分。（http://www.robots.ox.ac.uk/~vgg/research/affine/）

    请注意，这几个数据集并不是简单的不同场景的图像采集，而是各有侧重：

    1、算法匹配速度比较 ubc

    测试方法：在相同的匹配环境下，即使用同样配置的计算机，对相同的一对图像进行比较，测试算法的执行时间

    2、旋转变换鲁棒性比较 bark 

    测试方法：对同一图像进行一定角度的旋转，旋转角度逐步递增，旋转后的图像逐一与原始图像进行匹配，比较能够正确匹配的特征点对数，并观察正确匹配对数的变化幅度

    3、模糊变换鲁棒性比较 bikes

    测试方法：对同一图像用不同的高斯核进行模糊处理，模糊处理后的图像逐一与原始图像进行匹配，比较能够正确匹配的特征点对数，并观察正确匹配对数的变化幅度 

    4、光照变换鲁棒性比较 leuven

    测试方法：对同一图像的亮度进行改变，逐渐降低亮度，改变亮度后的图像逐一与原始图像进行匹配，比较能够正确匹配的特征点对数，并观察正确匹配对数的变化幅度

    5、尺度变换鲁棒性比较 bark

    测试方法：对原图像的尺度大小进行改变，尺度变化后的图像逐一与原始图像进行匹配，比较能够正确匹配的特征点对数，并观察正确匹配对数的变化幅度

    6、视角变换鲁棒性比较 graf

    测试方法：对原场景转一定角度进行拍摄，不同视角的图像逐一与原始图像进行匹配，比较能够正确匹配的特征点对数，并观察正确匹配对

    3.2 比较方法

    综合考虑实际情况，只选择SIFT、SURF、BRISK、ORB、FREAK这五种方法进行比较。比较过程中，依次对各个数据集进行特征点提取并进行两两特征点的比较；进一步对match的结果进行RANSAC提纯计算，计算“内点”；

    最终结果 = “内点比例”/“耗时”

    比如对于其中一组图像：

    

    那么最后，“模型平均”就是最终评价模型在这组图片上多次运算的平均结果。由于“内点比例”越高、“耗时”越少，代表匹配地越好，所以最终结果越大越好。

    3.3 结果分析

   

    通过折线图来分析：

    其中ORB算法体现出较高模型值。

    

    如果不考虑ORB算法：

    

    则总体差距不是很大。

    四、初步小结

    1、sift和surf一直提供了较高的准确率，并且结果比较稳定；sift较surf更准一些，但是也有brisk最好的时候；

    

    2、orb的速度非常快，但是最容易出现问题；

    

     3、和”支撑点“算法的比较，角点方法只能处理自然图片，不适宜处理轮廓 

    最终，在解决使用问题的时候，还是建议在以ＯＲＢ作为基准的基础上，围绕具体业务，灵活构建算法。（ＥＮＤ）

来自为知笔记(Wiz)