「图像识别算法」Opencv图像识别从零到精通（35）---SURF

图像识别算法

SIFT在前面已经说过了，可以说在实现过程中是精益求精，用了各种手段来删除不符合条件的特征点，同时也得到了很好的效果但是实时性不高，于是就有了SURF（speeded up robusr features）.SURF是一种尺度，旋转不变的detector和descriptor.最大的特点是快！在快的基础上保证性能（repeatability,distinctiveness和robustness）

1、总体概括

首先，先对SURF算法的中特征点的提取

在SURF算法中，特征点的判据为某像素亮度的Hessian矩阵的行列式(Dxx*Dyy-Dxy*Dxy)为一个极值。由于Hessian矩阵的计算需要用到偏导数的计算，这一般通过像素点亮度值与高斯核的某一方向偏导数卷积而成；在SURF算法里，为提高算法运行速度，在精度影响很小的情况下，用近似的盒状滤波器（0，1，1组成的box filter）代替高斯核。因为滤波器仅有0，-1,1，因此卷积的计算可以用积分图像（Integral image）来优化（O(1)的时间复杂度），大大提高了效率。每个点需计算Dxx，Dyy，Dxy三个值，故需要三个滤波器；用它们滤波后，得到一幅图像的响应图（response image，其中每个像素的值为原图像素的Dxx*Dyy-Dxy*Dxy）。对图像用不同尺寸的滤波器进行滤波，得到同一图像在不同尺度的一系列响应图，构成一个金字塔（该金字塔无需像SIFT中的高斯一样进行降采样，即金字塔每组中的每层图像分辨率相同）。

特征点的检测与SIFT一致，即若某点的Dxx*Dyy-Dxy*Dxy大于其邻域的26个点（与SIFT一致）的Dxx*Dyy-Dxy*Dxy，则该点为特征点。特征点的亚像素精确定位与SIFT一致。

其次，描述子的建立。为保证特征点描述子的旋转不变性，需对每个特征点计算主方向。计算主方向的过程如下：

1. 统计以特征点为中心，正比于特征点尺度的某个数位半径，张角为60°的扇形区域内所有像素点的 sumX=（y方向小波变换响应）*（高斯函数），sumY=（x方向小波变换响应）*（高斯函数），计算合成向量角度θ=arctan(sumY/sumX)，模长sqrt(sumy*sumy+sumx*sumx)。

2. 将扇形沿逆时针旋转（一般取步长为0.1个弧度），以同样方法计算合成向量。

3. 求出各方向扇形的合成向量模长最大值，其对应的角度即特征点主方向。

描述子的建立过程如下：

1. 选定以特征点为中心的一块正方形区域，将其旋转与主方向对齐。

2. 将正方形分为4x4的16个子区域，对每个区域进行Haar 小波变换（同样用积分图像加速），得到4个系数。

3. 由上述两步，生成4x4x4=64维向量，即描述子，用它可以进行匹配等工作。

算法的优点在于大量合理使用积分图像降低运输量，而且在运用的过程中并未降低精度(小波变换，Hessian矩阵行列式检测都是成熟有效的手段)。在时间上，SURF运行速度大约为SIFT的3倍；在质量上，SURF的鲁棒性很好，特征点识别率较SIFT高，在视角、光照、尺度变化等情形下，大体上都优于SIFT。

2、分开来说

一、积分图

SURF是对积分图像进行操作，从而实现了加速，采用盒子滤波器计算每个像素点的Hessian矩阵行列式时，只需要几次加减法运算，而且运算量与盒子滤波器大小无关，所以能够快速的构成出SURF的尺度金字塔。

积分图像中每个像元的值，是原图像上对应位置的左上角所有元素之和

二、尺度空间的构造

2.1 DOH近似

SIFT算法建立一幅图像的金字塔，在每一层进行高斯滤波并求取图像差(DOG)进行特征点的提取，而SURF则用的是Hessian Matrix进行特征点的提取，所以黑森矩阵是SURF算法的核心。假设函数f(x,y)，Hessian矩阵H是由函数偏导数组成。首先来看看图像中某个像素点的HessianMatrix的定义为：

判别式的值是H矩阵的特征值，可以利用判定结果的符号将所有点分类，根据判别式取值正负，从来判别该点是或不是极点的值。在SURF算法中，通常用图像像素I(x,y)取代函数值f(x,y)。然后选用二阶标准高斯函数作为滤波器。通过特定核间的卷积计算二阶偏导数，这样便能计算出H矩阵的三个矩阵元素Lxx,Lxy, Lyy，从而计算出H矩阵公式如下

2.2 构造尺度空间

算法的尺度不变性主要靠不同尺度下寻找感兴趣点。谈到不同尺度就不得不说‘金字塔’。Lowe在其SIFT大作中是这样构造尺度空间的：对原图像不断地进行Gauss平滑+降采样。得到金字塔图像后，有进一步得到了DoG图，边和斑状结构就是通过DoG图得到其在原图的位置。

SURF中的做法与SIFT是有所不同的。SIFT算法在构造金字塔图层时Gauss滤波器大小不变，改变的是图像的大小；而SURF则恰恰相反：图像大小保持不变，改变的是滤波器的大小。

SURF首先采用9×9的盒子滤波器（近似等于σ=1.2时的高斯二阶微分，记为尺度s=1.2）得到的响应图像作为最底层的图像，然后逐渐增大盒子的尺寸，对原图像继续进行滤波处理。与SIFT类似，把响应图像分成若干组，每组若干层。每组都是采用逐渐增大的滤波器尺寸进行处理。层与层之间的尺度变化量是高斯二阶微分模板决定的。对于9×9的滤波器，由于要保证滤波器的结构比例不变同时要求存在滤波器模板中心，每个块最小增加量是2，由于有三个块，所以最小增加量是6，即下一个滤波器的大小为15×15，依次增加为21×21,27×27，...；利用这样的模板序列，就构造出尺度空间。

每一个octave中的filter的size可以表示如下

三、关键点

3.1非极大值点位

与SIFT类似，对每层图像上的每个像素与空间邻域内和尺度邻域内的响应值比较（不包括第一层与最后一层图像），同层上有8个邻域像元，向量尺度空间共有2×9=18个，共计26个像元的值进行比较，如果是极大值则保留下来，作为候选特征点。

同时如果特征点的响应值小于Hessia行列式的阈值，也被排除。

3.2删除不符合条件的极值点

然后，采用3维线性插值法得到亚像素级的特征点，同时也去掉那些值小于一定阈值的点，增加极值使检测到的特征点数量减少，最终只有几个特征最强点会被检测出来，参考SIFT的方法

四，特征点描述子

4.1主方向

为了保证旋转不变性，在SURF中，不统计其梯度直方图，而是统计特征点领域内的Harr小波特征。即以特征点为中心，计算半径为6s(S为特征点所在的尺度值)的邻域内，统计60度扇形内所有点在x(水平)和y(垂直)方向的Haar小波响应总和(Haar小波边长取4s)

并给这些响应值赋高斯权重系数（σ=2.5s），使得靠近特征点的响应贡献大，而远离特征点的响应贡献小，然后60度范围内的响应相加以形成新的矢量，遍历整个圆形区域，选择最长矢量的方向为该特征点的主方向。这样，通过特征点逐个进行计算，得到每一个特征点的主方向。该过程的示意图如下：

4.2形成特征矢量

在SURF中，也是在特征点周围取一个正方形框，框的边长为20s(s是所检测到该特征点所在的尺度)。该框带方向，方向当然就是第4步检测出来的主方向了。然后把该框分为16个子区域，每个子区域统计25个像素的水平方向和垂直方向的haar小波特征，这里的x(水平)和y(垂直)方向都是相对主方向而言的。该haar小波特征为x(水平)方向值之和，水平方向绝对值之和，垂直方向之和，垂直方向绝对值之和。该过程的示意图如下所示：

这样每个子区域携带4个信息，共有16个子区域，共64维。最后为了防止光照与对比度的影响，对特征矢量归一化处理。

五、OpenCV

<span style="font-family:SimSun;font-size:18px;">函数的定义看SIFT基本相同，只是SIFT换了SURF</span>

程序的核心思想是：

使用 Descriptorextractor 接口来寻找关键点对应的特征向量。
使用 SurfDescriptorExtractor 以及它的函数 compute 来完成特定的计算。
使用 BruteForceMatcher 来匹配特征向量。
使用函数 drawMatches 来绘制检测到的匹配点。

<span style="font-family:SimSun;font-size:18px;">#include "opencv2/core/core.hpp"  
#include "opencv2/features2d/features2d.hpp"  
#include "opencv2/highgui/highgui.hpp"  
#include <opencv2/nonfree/nonfree.hpp>  
#include<opencv2/legacy/legacy.hpp>  
#include <iOStream>  
using namespace cv;  
using namespace std;  
   
int main(  )  
{  


    Mat srcImage1 = imread("hand1.jpg",1);  
    Mat srcImage2 = imread("hand3.jpg",1);  
    if( !srcImage1.data || !srcImage2.data )  
    { printf("读取图片错误，请确定目录下是否有imread函数指定的图片存在~！ \n"); return false; }    
    int minHessian = 700;
    SurfFeatureDetector detector( minHessian );    
    std::vector<KeyPoint> keyPoint1, keyPoints2;
    detector.detect( srcImage1, keyPoint1 );  
    detector.detect( srcImage2, keyPoints2 );  
    SurfDescriptorExtractor extractor;  
    Mat descriptors1, descriptors2;  
    extractor.compute( srcImage1, keyPoint1, descriptors1 );  
    extractor.compute( srcImage2, keyPoints2, descriptors2 );  
  
    BruteForceMatcher< L2<float> > matcher;  
    std::vector< DMatch > matches;  
    matcher.match( descriptors1, descriptors2, matches );  
  
    Mat imgMatches;  
    drawMatches( srcImage1, keyPoint1, srcImage2, keyPoints2, matches, imgMatches );//进行绘制  
    imshow("匹配图", imgMatches );  
  
    waitKey(0);  
    return 0;  
}  
  
</span>

六、Matlab

程序源码由荷兰特温特大学的Dirk-Jan Kroon博士提供,可以自己去下载，比较复杂，这里提供一下结果

  I1=imread('TestImages/testc1.png');
  I2=imread('TestImages/testc2.png');
  Options.upright=true;
  Options.tresh=0.0001;
  Ipts1=OpenSurf(I1,Options);
  Ipts2=OpenSurf(I2,Options);
  D1 = reshape([Ipts1.descriptor],64,[]); 
  D2 = reshape([Ipts2.descriptor],64,[]); 
  err=zeros(1,length(Ipts1));
  cor1=1:length(Ipts1); 
  cor2=zeros(1,length(Ipts1));
  for i=1:length(Ipts1),
      distance=sum((D2-repmat(D1(:,i),[1 length(Ipts2)])).^2,1);
      [err(i),cor2(i)]=min(distance);
  end
  [err, ind]=sort(err); 
  cor1=cor1(ind); 
  cor2=cor2(ind);
  I = zeros([size(I1,1) size(I1,2)*2 size(I1,3)]);
  I(:,1:size(I1,2),:)=I1; I(:,size(I1,2)+1:size(I1,2)+size(I2,2),:)=I2;
  figure, imshow(I/255); hold on;
  for i=1:30,
      c=rand(1,3);
      plot([Ipts1(cor1(i)).x Ipts2(cor2(i)).x+size(I1,2)],[Ipts1(cor1(i)).y Ipts2(cor2(i)).y],'-','color',c)
      plot([Ipts1(cor1(i)).x Ipts2(cor2(i)).x+size(I1,2)],[Ipts1(cor1(i)).y Ipts2(cor2(i)).y],'o','Color',c)
  end

http://blog.csdn.net/luoshixian099/article/details/47807103

http://blog.csdn.net/cxp2205455256/article/details/41311013

http://www.open-open.com/lib/view/open1440832074794.html

http://blog.csdn.net/poem_qianmo/article/details/33320997

图像识别算法交流 qq群：145076161，欢迎图像识别与图像算法，共同学习与交流

Opencv图像识别从零到精通（35）---SURF

图像识别算法

相关阅读

栏目导航

推荐阅读

热门阅读