SURF (Speeded Up Robust Features, 加速稳健特征) 是一个稳健的图像识别和描述算法，首先于2006年发表在ECCV大会上。这个算法可被用于计算机视觉任务，如物件识别和3D重构。他部分的灵感来自于SIFT算法。SURF标准的版本比SIFT要快数倍，并且其作者声称在不同图像变换方面比SIFT更加稳健。

SURF算子——原理

特征点检测

基于Hessian矩阵的特征点检测

对于输入图像中的一点$X=(x,y)$，其Hessian矩阵定义如下

$H(X,\sigma)= \begin{bmatrix} L_{xx}(X,\sigma)&L_{xy}(X,\sigma)\\ L_{xy}(X,\sigma)&L_{yy}(X,\sigma) \end{bmatrix}$

其中$\sigma$为Hessian矩阵的尺度，$L_{xx}$是高斯二阶偏导数$\frac {\partial^2}{\partial x^2}g(\sigma)$与输入图像在点$X$处的卷积，其余类似。

行列式的值$det(H)$即为点$X$处的响应

$det(H)=L_{xx}L_{yy}-L_{xy}^2$

基于Box滤波器的Hessian矩阵近似计算

利用Box滤波器做Hessian矩阵近似计算，加快计算速度。

在LoG算子中，

$h(x,y)=e^{-\frac {x^2+y^2}{2\sigma^2}}$ $\triangledown^2h(r)=(\frac{r^2-\sigma^2}{\sigma^4})e^{-\frac {r^2}{2\sigma^2}},\quad r^2=x^2+y^2$

可以用Box滤波器近似计算$\triangledown^2h(r)$

如此对高斯二阶微分模板进行简化，从而降低计算量，高斯二阶导数函数的离散化和截断会造成一定的误差。

利用简化后的Box滤波模版对图像进行卷积，得到Hessian矩阵的近似计算

$H(X,N)= \begin{bmatrix} D_{xx}(X,N)&D_{xy}(X,N)\\ D_{xy}(X,N)&D_{yy}(X,N) \end{bmatrix}$

其中，N为Box滤波器的大小。

行列式的值$det(H)$即为点$X$处的响应（但是要加上权重）

$det(H_{approx})=D_{xx}D_{yy}-(wD_{xy})^2,\quad w \approx 0.9$

其中，权重$w$为平衡因子

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

基于积分图的Box滤波器快速计算

利用积分图快速计算Box卷积滤波。

积分图是输入图像经过像素间的累加运算得到的新图像。任意一点$(x,y)$的值是从输入图像的左上角到这个点所构成的矩形区域内所有点的灰度值之和。

每个点的积分可以用迭代的方式获得

$II(x,y)=II(x,y-1)+S(x-1,y)+I(x,y)$

计算矩阵ABCD中像素和只需要积分图中A、B、C、D四点的值和3次加法运算

尺度金字塔构建

一般尺度金字塔采用对图像的下采样，使用同一个滤波器滤波。

在SURF算子中，由于积分图和Box滤波的计算便利性，固定图像尺度，上采样滤波器。

与SIFT算子类似，

将尺度空间划分为若干组(Octaves)，每组又由若干固定层（Interval）组成
每组尺度金字塔的各层尺度成等差数列
不同组的尺度金字塔的公差等比增长（$O,S$为组索引、层索引，从$0$开始）

$Filter Size = 3\times[2^{o+1}\times (s+1)+1]$

为了保持尺度空间的连续性，相邻组尺度金字塔有部分层重叠（SIFT中同样，$S+3$个图才能得到$S$个尺度的特征点检测结果）

特征点定位

非极大抑制

与SIFT中的做法相似，
- 每组中选相邻3层Hessian行列式图像，对于中间层图像中的每个待比较点，选取同层的8个相邻点和上下层的9个相邻点进行比较
- 若该点值大于其他26点，则为特征点
尺度空间插值

与SIFT中的做法相同，得到亚像素级的特征值，减小不同组第一层之间的差异。

特征点描述

特征点主方向

为了保证特征描述子具有旋转不变性，与SIFT一样，需要对每个特征点分配一个主方向。

选择以特征点为中心、半径为$6s$（$s$为特征点的尺度）的圆形邻域
计算该圆形邻域内各点的$x$、$y$方向Haar小波响应（Haar小波边长取$4s$）

计算图像的Haar小波响应，实际上就是对图像进行梯度运算，只不过需要利用积分图，提高梯度计算效率。
用$\sigma = 2.5s$的高斯函数对响应加权
以特征点为中心，张角为$\pi /3$的扇形滑动窗口，计算窗口内的Haar小波响应值$dx$、$dy$的累加
$m_w=\sum\limits_w dx+\sum\limits_w dy\\ \theta_w=\arctan(\sum\limits_w dx/\sum\limits_w dy)$
特征点主方向为最大的Haar响应累加值所对应的方向
$\theta = \theta_w|max\{m_w\}$

Haar小波响应和描述符

构建以特征点为中心、方向为特征点主方向、边长为$20s$的正方形区域
将区域划分成$4\times 4$子块
每个子块均匀采样$5\times 5$个样本点
计算各采样点的Haar小波响应（Haar小波边长为$2s$）
用以特征点为中心点，$\sigma =3.3s$的高斯函数对响应加权
在各子块内统计$\sum dx$、$\sum |dx|$、$\sum dy$、$\sum |dy|$形成子块特征向量
每个子块统计一个四维特征向量$\vec v$
$\vec v = (\sum dx,\sum |dx|,\sum dy,\sum |dy|)$
将$4\times 4$个子块的特征向量$\vec v$相连，得长度为64的特征向量，具有亮度不变性
将特征向量归一化，具有对比度不变性

SURF描述子对于不同纹理的区分性

快速索引匹配

在检测阶段，记录拉普拉斯算子的符号（Hessian矩阵的迹的符号）
在匹配阶段，匹配拉普拉斯算子符号相同的特征，从而降低运算量