SURF特征详解

简介

SIFT特征之后的SURF特征。

综合转载以下文章：

• 图像特征— —SURF特征
• Surf特征提取分析
• SURF特征提取算法原文翻译与理解（上）
• 图像处理之积分图算法
• haar
• (含代码)图像的Haar小波变换

看了以上几篇关于SURF特征的介绍，都是先从Hessian矩阵，当然，这也是原论文的顺序，但是我刚看还是有些难理解的，所以这篇博客我还是按照SIFT特征的步骤，一步步比较。

尺度空间

外部构造

图像的尺度空间是这幅图像在不同解析度下的表示。在金字塔图像中分为很多层，每一层叫做一个octave，每一个octave中又有几张尺度不同的图片。

在SIFT算法中，同一个octave层中的图片尺寸(即大小)相同，但是尺度(即模糊程度)不同，而不同的octave层中的图片尺寸大小也不相同，因为它是由上一层图片降采样得到的。在进行高斯模糊时，SIFT的高斯模板大小是始终不变的，只是在不同的octave之间改变图片的大小。

而在SURF中，图片的大小是一直不变的，不同的octave层得到的待检测图片是改变高斯模糊尺寸大小得到的，当然了，同一个octave中个的图片用到的高斯模板尺度也不同。这样没有上下octave层的迭代降采样操作，允许了多个octave层同时操作，从而提高了速度。

内部构造

首先是LoG算子的改进，在LoG中首先使用高斯平滑，然后对平滑后的图形进行Laplace获得二阶梯度特征。

而Fast-Hessian Detector则是首先使用盒滤波器来滤波，然后使用Hessian矩阵表示二阶梯度。

图中的(a)和(b)是在$y$轴方向和$xy$方向进行高斯二阶微分经过采样和离散化得到的结果，即$L_{xx}$和$L_{xy}$，而(c)和(d)是使用盒滤波器得到的近似高斯二阶微分，即$D_{xx}$和$D_{xy}$。由此，进一步提高性能。

另外地，因为使用了盒滤波器，所以可以使用积分图提高计算速度。

为了得到卷积结果，我们只需要计算4个块的和。这比Hessian快5倍，比DoG快3倍。计算块越大，加速越明显。

积分图

积分图是Crow在1984年首次提出，是为了在多尺度透视投影中提高渲染速度。积分图是一种在图像中快速计算矩形区域和的方法，这种算法主要优点是一旦积分图像首先被计算出来我们可以计算图像中任意大小矩形区域的和而且是在常量时间内。这样在图像模糊、边缘提取、对象检测的时候极大降低计算量、提高计算速度。

在积分图像(Integral Image - $ii$)上任意位置$(x, y)$处的$ii(x, y)$表示该点左上角所有像素之和，表示如下：

$$ii(x,y)=\sum_{x'<x \space y'<y}i(x',y')$$

其中$i(x,y)$表示输入图像上相关位置的像素点。

从给定图像$I$从上到下、从左到右计算得到和的积分图像公式如下：

$$ii(x,y)=ii(x-1,y)+I(x,y)+ii(x,y-1)-ii(x-1,y-1)$$

其中，$(x<0||y<0)$时$ii(x,y)=0$,$i(x,y)=0$。

得到积分图之后，图像中任意矩形区域和通过如下公式计算：

$$sum(m,n)=ii(x,y)+ii(u,v)-ii(x,v)-ii(u,y)$$

其中矩形大小为：$m=x-u,n=y-u$

Hessian矩阵

假设函数$f(x,y)$，Hessian矩阵$H$是由函数偏导数组成。首先来看看图像中某个像素点的Hessian矩阵的定义为：

$$H(f(x,y))= {\left[ \begin{array}{c} \frac{\partial^2f}{\partial x^2} & \frac{\partial^2f}{\partial x\partial y}\\ \frac{\partial^2f}{\partial x\partial y} & \frac{\partial^2f}{\partial y^2} \end{array} \right ]}$$

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

$$det(H)=\frac{\partial^2f}{\partial x^2}\frac{\partial^2 f}{\partial y^2}-(\frac{\partial^2 f}{\partial x \partial y})^2$$

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

$$H(x,\sigma)= {\left[ \begin{array}{c} L_{xx}(x,\sigma) & L_{xy}(x, \sigma)\\ L_{xy}(x,\sigma) & L_{yy}(x,\sigma) \end{array} \right ]}$$

再使用上图的类似算子，就可以表示成：

$$H(x,\sigma)= {\left[ \begin{array}{c} D_{xx}(x,\sigma) & D_{xy}(x, \sigma)\\ D_{xy}(x,\sigma) & D_{yy}(x,\sigma) \end{array} \right ]}$$

但是近似毕竟是近似，这里近似一点，那里近似一点，累积的方差就大了，所以在计算Hessian矩阵行列式时进行了修正，

$$\frac{|L_{xy}(1.2)|_F|D_{xx}(9)|_F}{L_{xx}(1.2)|_F|D_{xy}(9)|_F}=0.912 ...\approx 0.9$$

$1.2$是LoG的尺度，$9$是盒滤波器的边长。

$$det(H_{approx})=det(D)=D_{xx}D_{yy}-(0.9D_{xy})^2$$

推一推，目的是$det(H)=det(D)$。
设$det(D)=D_{xx}D_{yy}-(\alpha D_{xy})^2$，
于是，

$$det(H)=det(D) \\ L_{xx}L_{yy}-(L_{xy})^2 = D_{xx}D_{yy}-(\alpha D_{xy})^2\\ \frac{(L_{xy})^2}{L_{xx}L_{yy}}=\frac{\alpha(D_{xy})^2}{D_{xx}D_{yy}} \\ \alpha^2 = \frac{(L_{xy})^2D_{xx}D_{yy}}{(D_{xy})^2L_{xx}L_{yy}}$$

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

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

特征点定位

这里和LoG，DoG相同，都是在生成尺度空间后，找在三维上找极值点。

这里和DoG不同的是不用剔除边缘导致的极值点了，因为Hessian矩阵的行列式就已经考虑到边缘的问题了，而DoG计算只是把不同方向变化趋势给出来，后续还需要使用Hessian矩阵的特征值剔除边缘产生的影响。

求特征点的主方向

不像sift中依靠梯度方向直方图确定主方向，Surf首先将周围$6s$的圆形区域分成6个扇形区间，s是对应的尺度。然后在每个扇形区域使用提取x方向和y方向的Haar小波特征(Haar小波的边长为4s),将该区域每个样本点这两个响应的高斯加权和作为该区域的方向，最后扫面了整个圆形区域，选择最大方向就是该关键点的方向。

Haar小波

一维haar小波

例如我们有一个一维的图像[2,4,6,8,10,12,14,16]。

1. 求均值：我们求相邻像素的均值[3,7,11,15]。这个新的图像分辨率就成了原来的一半(8/2=4)。
2. 求差值。上面的均值我们存储了图像的整体信息。但是很多细节信息我们丢掉了，所以我们同时要记录图像的细节信息，这样在重构时能够恢复图像的全部信息。经过计算我们得到了结果[-1,-1,-1,-1]。
3. 此时上面两步形成了第一次分解的结果[3,7,11,15,-1,-1,-1,-1]。包含了图像的整体信息和细节信息。接下来的分解我们重复1,2步，将整体信息再次进行分解，得到了二级分解结果[5,13,-2,-2]。同样的，前面的[5,13]是整体信息，后面的[-2,-2]是细节信息。

分辨率	整体信息	细节信息
4	3,7,11,15	-1,-1,-1,-1
2	5,13	-2,-2
1	9	-4

经过三次分解，我们得到了一个整体信息和三个细节系数，这个就是一维小波变换。

二维haar小波

一维小波变换其实是将一维原始信号分别经过低通滤波和高通滤波以及二元下抽样得到信号的低频部分L和高频部分H。而根据Mallat算法，二维小波变换可以用一系列的一维小波变换得到。对一幅m行n列的图像，二维小波变换的过程是先对图像的每一行做一维小波变换，得到L和H两个对半部分；然后对得到的LH图像（仍是m行n列）的每一列做一维小波变换。这样经过一级小波变换后的图像就可以分为LL，HL，LH，HH四个部分，如下图所示，就是一级二维小波变换的塔式结构：

而二级、三级以至更高级的二维小波变换则是对上一级小波变换后图像的左上角部分（LL部分）再进行一级二维小波变换，是一个递归过程。下图是三级二维小波变换的塔式结构图：

唔

看了上面这些，我还是不知道主方向中haar小波具体怎么计算的，水平方向和垂直方向不是只有两个方向吗，怎么计量八个方向或者十个方向呢，当扩展知识吧。

生成特征描述

统计特征时，再该关键点周围选取$20s \times 20s$的区域，划分成$4 \times 4$的子区域，在每个子区域内使用$x$方向，$y$方向的的haar小波特征算子提取haar小波特征，然后使用提取结果统计$\sum dx$,$\sum dy$,$\sum|dx|$,$\sum |dy|$四个值作为该子区域的特征，那么一个关键点就可以使用16个子区域的特征联合表示，即64维向量。

64维向量与sift的128维向量相比，匹配的时间也会更短。

总结

总的来说，surf与sift相比，有三点提高了速度：

1. 尺度空间，图像的分辨率不变，能够同时操作；
2. 极值点检测，使用了盒滤波器近似，再使用积分图辅助；
3. 最后生成的特征为64维，与sift相比少了64维。