图像匹配算法研究之surf算法

学海无涯GL 2012-09-11

展开全文

图像匹配算法研究之surf算法

今天碰巧和朋友讨论这个，才想起来好久没碰，都生疏了，趁着暑假还有点闲时，先写写再说。有错误的地方希望大家指正。

SURF (Speeded Up 
Robust Feature) is a robust local feature detector, first presented by Herbert 
Bay et al. in 2006, that can be used in computer vision tasks like object 
recognition or 3D reconstruction. It is partly inspired by the SIFT descriptor. 
The standard version of SURF is several times faster than SIFT and claimed by 
its authors to be more robust against different image transformations than SIFT. 
SURF is based on sums of 2D Haar wavelet responses and makes an efficient use of 
integral images.

上面这段文字的大体意思就是说：

SURF意指加速的具有鲁棒性的特征，由Bay在2006年首次提出，这项技术可以应用于计算机视觉的物体识别以及3D重构中。SURF算子由SIFT算子改进而来，一般来说，标准的SURF算子比SIFT算子快好几倍，并且在多幅图片下具有更好的鲁棒性。SURF最大的特征在于采用了harr特征以及积分图像integral image的概念，这大大加快了程序的运行时间。

surf提出算法参见http://www.vision.ee./~surf/papers.html 有paper下载地址。

1、提取特征点

2、提取特征描述符

1. 特征点的提取

1）利用Hessian矩阵，计算特征值α

Hessian矩阵

其中Lxx(x, σ)是高斯滤波后图像g(σ)的在x方向的二阶导数,其他的Lyy(x, σ)、Lxy(x, σ)都是g(σ)的二阶导数。

为了减小计算量，原文使用了一个简单的方法，并利用了积分图像的优势（大大的减少计算量），方法其实很简单就是在模糊的基础上将原本的模块近似下。

总所周知，一般计算图像的二阶导时，利用下面的公式d²f(x)/dx²=(f(x+1)-f(x))-(f(x)-f(x-1))=-2*f(x)+f(x+1)+f(x-1)。但是f(x)=g(h(x))【h(x)为图像的灰度值，f(x)

是将h(x)高斯滤波处理的灰度函数】

图一模板近似

以9X9滤波器为例，如上图所示，左边两幅图分别为灰度图像在中心点（黑色点）处的二阶导数d²f(x)/dx²和d²f(x)/dxdy的模板对应的值, 近似后变成右边的两幅图，图中灰色部分像素值为0。可是这样计算特征值不是也很复杂么？当然，所以作者提供了一种新思路--使用积分图像。

积分图像，顾名思义，即指当前像素点所在位置距原点（0,0）所包围面的所有灰度之和。

绿色的部分为当前像素点，红色为积分区域。

这样计算图像中任意一块矩形区域的灰度之和Sx只需要利用矩形4个顶点(Xi,Yi)(i=1,2,3,4 顺序为从上之下，先左后右)的积分值S（x,y）即可。

Sx=S(X1,Y1)+S(X4,Y4)-S(X2,Y2)-S(X3,Y3)

至此，大家应该知道近似二阶导数的高斯模板并引入积分图像的好处了吧，只需要在函数定义之前计算各个坐标点的积分图像，然后就能方便的求出hessian的特征值。

不过由于函数模板的近似，这里需要修正下特征值α的求解公式：

这里Dxx和Dxy就是根据图一得到的，而Dyy和Dxx类似，只需要导致一下模板即可。

2）根据是否为领域极大值判断特征点

这里要引入图像堆的概念，说简单点，就是一组大小相同的图像，这些图像都是根据不同大小高斯滤波二阶导模板，如图一所示得到的平滑后图像Pi 。

按照模板大小从小到大将Pi沿z轴方向排布，这样中间层的每个像素点的领域就为3X3X3（包括上下两层）。若该点的特征值α为这27个点中的最大值，那么可以认为该点为Feature points--特征点（图像依据这些特征点的匹配进行更多的操作，比如拼接，比较相似性等等）。

2.特征点的匹配

1）寻找特征向量

欲进行特征点的匹配，必须提取出特征点的特征向量再利用两个向量的相似程度认为两个点是否为两幅图像相互对应的点。

第一步.计算特征点的主方向

以特征点为圆心半径为6像素建立圆领域，计算得出里面有109个像素点。计算这些点的harr特征harrx和harry.

那么该怎样计算任意一点的harr特征值？

图二 harr-like特征

选取edge features前两个作为harrx和harry值，这个方向有些类似与梯度方向，不过这里的领域显然更广。至于计算么，依旧是利用积分图像。

对这109个像素点分别求出各自的向量的方向angle=acrtan(harry/harrx) ，根据最近邻原则将这些 angle划分到60，120，...，300，360等6个值上。划分在同一范围上的像素点分别将他们的harrx和harry相加即可。不过为了体现相邻像素点的更大影响，还需要考虑高斯权重系数。这样得到最大的harrx和最大的harry,组成了主方向向量。

第二步.提取特征描述符

图3.选取特征区域