SURF特征提取分析

背景引言

计算机视觉中，引入尺度不变的特征，主要的思想是每个检测到的特征点都伴随着对应的尺寸因子。当我们想匹配不同图像时，经常会遇到图像尺度不同的问题，不同图像中特征点的距离变得不同，物体变成不同的尺寸，如果我们通过修正特征点的大小，就会造成强度不匹配。为了解决这个问题，提出一个尺度不变的SURF特征检测，在计算特征点的时候把尺度因素加入之中。SURF与SIFT算法相似，SIFT算法比较稳定，检测特征点更多，但是复杂度较高，而SURF要运算简单，效率高，运算时间短一点。相关SIFT算法请详见博文【图像分析】尺度不变特征变换(SIFT)特征提取分析。本节介绍SURF算法相关知识。

基本介绍

首先，我们引用[3]中对SURF描述为：“SURF (Speeded Up Robust Features)isa robust local feature detector, first presented by　Herbert Bay et al. in 2006, that can be used in computer vision tasks likeobject 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 of2D Haar wavelet responses and makes an efficient use ofintegral images.It uses an integer approximation to the determinant of Hessian blob detector, which can be computed extremely quickly with an integral image (3 integer operations). For features, it uses the sum of　the Haar wavelet response around the point of interest. Again, these can be computed with the aid of the integral image".

从上述对SURF描述，可知：第一、SURF算法是对SIFT算法加强版，同时加速的具有鲁棒性的特征。第二、标准的SURF算子比SIFT算子快好几倍，并且在多幅图片下具有更好的鲁棒性。SURF最大的特征在于采用了harr特征以及积分图像integral image的概念，这大大加快了程序的运行时间。

算法描述

为了实现尺度不变性的特征点检测与匹配，SURF算法则先利用Hessian矩阵确定候选点，然后进行非极大抑制，计算复杂度降低多了。整个算法由以下几个部分组成。

1.Hessian黑森矩阵构建

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

从而每一个像素点都可以求出一个Hessian Matrix. Hessian矩阵判别式为：

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

但是由于我们的特征点需要尺度无关性，所以在进行Hessian矩阵构造前，需要对其进行高斯滤波。这样，经过滤波后在进行Hessian的计算，其公式如下：

L(x,t)是一幅图像在不同解析度下的表示，可以利用高斯核G(t)与图像函数I(x)在点x的卷积来实现，其中高斯核G(t)为：

其中g(t)为高斯函数，t 为高斯方差。通过这种方法可以为图像中每个像素计算出其H矩阵的决定值，并用这个值来判别特征点。为此Herbert Bay提出用近似值现代替L(x,t)。为平衡准确值与近似值间的误差引入权值。权值随尺度变化，则H矩阵判别式可表示为：

其中为何式中0.9呢.请详见[1]。因求Hessian时要先高斯平滑，然后求其二阶导数，这在离散的像素是用模板卷积形

成的。这比如说y方向上的模板Fig1(a)和Fig1(c).Fig1(a)即用高斯平滑后在y方向上求二阶导数的模板。为了加快运算用了近似处理，其处理结果如Fig1(b)所 示，这样就简化了很多。并且可以采用积分图来运算，大大的加快了速度。同理，x和y方向的二阶混合偏导模板Fig1(b)与Fig1(d)。

2. 尺度空间生成

图像的尺度空间是这幅图像在不同解析度下的表示。上面讲的这么多只是得到了一张近似Hessian行列式图，这类似SIFT中的DOG图，但是在金字塔图像中分为很多层，每一层叫做一个octave，每一个octave中又有几张尺度不同的

图片。在SIFT算法中，同一个octave层中的图片尺寸(即大小)相同，但是尺度(即模糊程度)不同，而不同的octave层中的图片尺寸大小也不相同，因为它是由上一层图片降采样得到的。在进行高斯模糊时，SIFT的高斯模板大小是始终不变的，只是在不同的octave之间改变图片的大小。而在SURF中，图片的大小是一直不变的，不同的octave层得到的待检测图片是改变高斯模糊尺寸大小得到的，当然了，同一个octave中个的图片用到的高斯模板尺度也不同。算法允许尺度空间多层图像同时被处理，不需对图像进行二次抽样，从而提高算法性能。上图左边是传统方式建立一个如图所示的金字塔结构，图像的寸是变化的，并且运 算会反复使用高斯函数对子层进行平滑处理，上图右边说明SURF算法使原始图像保持不变而只改变滤波器大小。SURF采用这种方法节省了降采样过程，其处理速度自然也就提上去了(注：上图片来自于网络)。

3. 利用非极大值抑制初步确定特征点和精确定位特征点

将经过hessian矩阵处理过的每个像素点与其3维领域的26个点进行大小比较，如果它是这26个点中的最大值或者最小值，则保留下来，当做初步的特征点。检测过程中使用与该尺度层图像解析度相对应大小的滤波器进行检测，以3×3的滤波器为例，该尺度层图像中9个像素点之一.如下图中检测特征点与自身尺度层中其余8个点和在其之上及之下的两个尺度层9个点进行比较，共26个点，图中标记‘x’的像素点的特征值若大于周围像素则可确定该点为该区域的特征点。

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

4. 选取特征点主方向确定

为了保证旋转不变性，在SURF中，不统计其梯度直方图，而是统计特征点领域内的Harr小波特征。即以特征点为中心，计算半径为6s(S为特征点所在的尺度值)的邻域内，统计60度扇形内所有点在x(水平)和y(垂直)方向的Haar小波响应总和(Haar小波边长取4s)，并给这些响应值赋高斯权重系数，使得靠近特征点的响应贡献大，而远离特征点的响应贡献小，然后60度范围内的响应相加以形成新的矢量，遍历整个圆形区域，选择最长矢量的方向为该特征点的主方向。这样，通过特征点逐个进行计算，得到每一个特征点的主方向。该过程的示意图如下：

5. 构造SURF特征点描述算子

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

综上所述，目前，对SURF算法有了一定了解。所以，可知SURF采用Henssian矩阵获取图像局部最值还是十分稳定的，但是在求主方向阶段太过于依赖局部区域像素的梯度方向，有可能使得找到的主方向不准确，后面的特征向量提取以及匹配都严重依赖于主方向，即使不大偏差角度也可以造成后面特征匹配的放大误差，从而匹配不成功；另外图像金字塔的层取得不足够紧密也会使得尺度有误差，后面的特征向量提取同样依赖相应的尺度，在这个问题上我们只能采用折中解决方法：取适量的层然后进行插值。

实验结果：

图像特征提取效果图如下所示：

图像匹配效果图所示：

补充思考问题

1. 为什么选用高斯金字塔来作特征提取？

首先，采用DOG的金字塔原因是：因为它接近LOG，而LOG的极值点提供了最稳定的特征，而且DOG方便计算(只要做减法).而LOG的极值点提供的特征最稳定。其次，我们从直观理解：特征明显的点经过不同尺度的高斯滤波器进行滤波后，差别较大，所以用到的是DOG。但是直观上怎么理解呢. 如果相邻Octave的sigma不是两倍关系还好理解：如果两幅图像只是缩放的关系，那么假设第一个Octave找到了小一倍图像的极值点，那么大一倍图像的极值点会在下一个Octave找到相似的。但是现在，如果把大一倍图像进行一次下采样(这样和小的图像就完全一样了)，进行Gauss滤波时，两个图像滤波系数(sigma)是不一样的，不就找不到一样的极值点了么.

2.Hessian矩阵为什么能用来筛选极值点？

SIFT先利用非极大抑制，再用到Hessian矩阵进行滤除。SURF先用Hessian矩阵，再进行非极大抑制。SURF的顺序可以加快筛选速度么(Hessian矩阵滤除的点更多?)至于SURF先用Hessian矩阵，再进行非极大抑制的原因，是不管先极大值抑制还是判断Hessian矩阵的行列式，金字塔上的点的行列式都是要计算出来的。先判断是否大于0只要进行1次判断，而判断是否是极大值点或者极小值点要与周围26个点比较，只比较1次肯定快。而在SIFT中，构建的高斯金字塔只有一座(不想SURF是有3座)，要进行非极大抑制可以直接用金字塔的结果进行比较。而如果计算Hessian矩阵的行列式，还要再计算Dxx、Dxy、Dyy。因此先进行非极大抑制。这两个步骤的先后与SIFT/SURF的实际计算情况有关的，都是当前算法下的最佳顺序，而不是说哪种先计算一定更好。

3、为什么采用梯度特征作为局部不变特征？

这与人的视觉神经相关。采用梯度作为描述子的原因是，人的视觉皮层上的神经元对特定方向和空间频率的梯度相应很敏感，经过SIFT作者的一些实验验证，用梯度的方法进行匹配效果很好。

4、为什么可以采用某些特征点的局部不变特征进行整幅图像的匹配？

从直观的人类视觉印象来看，人类视觉对物体的描述也是局部化的，基于局部不变特征的图像识别方法十分接近于人类视觉机理，通过局部化的特征组合，形成对目标物体的整体印象，这就为局部不变特征提取方法提供了生物学上的解释，因此局部不变特征也得到了广泛应用。图像中的每个局部区域的重要性和影响范围并非同等重要，即特征不是同等显著的，其主要理论来源是Marr的计算机视觉理论和Treisman的特征整合理论，一般也称为“原子论”。该理论认为视觉的过程开始于对物体的特征性质和简单组成部分的分析，是从局部性质到大范围性质。SIFT/SURF都是对特征点的局部区域的描述，这些特征点应该是影响重要的点，对这些点的分析更加重要。所以在局部不变特征的提取和描述时也遵循与人眼视觉注意选择原理相类似的机制，所以SIFT/SURF用于匹配有效果。

5. 为什么Hessian矩阵可以用来判断极大值/极小值?

在x0点上，hessian矩阵是正定的，且各分量的一阶偏导数为0，则x0为极小值点。在x0点上，hessian矩阵是负定的，且各分量的一阶偏导数为0，则x0为极大值点。

对于某个局部区域，若hessian矩阵是半正定的，则这个区域是凸的（反之依然成立）；若负定，则这个区域是凹的(反之依然成立)。而对于正定和负定来说，Hessian矩阵的行列式总是大于等于0的。反过来就是说：某个点若是极大值/极小值，hessian矩阵的行列式必然要大于等于0，而大于等于0如果是满足的，这个点不一定是极大值/极小值(还要判断一阶导数)。所以后面还要进行极大值抑制.

补充知识

[1] OpenSURF-The Offical Home of the Image Processing Libary. http://www./computer-vision-opensurf.html.(补充时间：2013年12月5日)

参考资料

[1] Herbert Bay, Andreas Ess, Tinne Tuytelaars, Luc Van Gool, "SURF: Speeded Up Robust Features", Computer Vision and Image Understanding (CVIU), Vol. 110, No. 3, pp. 346--359, 2008.

[2] The Website of SURF: Speeded Up Robust Features.

[3] Speeded Up Robust Features(SURF) ,Wikipedia, the free encyclopedia .

关于Image Engineering & Computer Vision的更多讨论与交流，敬请关注本博和新浪微博songzi_tea.