加速稳健特征

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

SURF使用海森矩阵的行列式值作特征点侦测并用积分图加速运算；SURF 的描述子基于 2D 离散小波变换响应并且有效地利用了积分图。

演算法

SURF演算法的概念及步骤均建立在SIFT之上，但详细的流程略有不同。SURF演算法包含以下三个步骤:特征点侦测、特征邻近描述、描述子配对。

特征点侦测

SIFT使用了连续不同尺度的高斯滤波器处理影像，并且经由高斯差来侦测影像中尺度不变的特征点。

SURF使用了方型滤波器取代SIFT中的高斯滤波器，借此达到高斯糢糊的近似。其滤波器可表示为:

$S(x,y)=\sum _{i=0}^{x}\sum _{j=0}^{y}I(i,j)$

此外使用方型滤波器可利用积分图大幅提高运算速度，仅需计算位于滤波器方型的四个角落値即可。

SURF使用了斑点侦测的海森矩阵来侦测特征点，其行列式值代表像素点周围的变化量，因此特征点需取行列式值为极大、极小值。除此之外，为了达到尺度上的不变，SURF还使用了尺度σ的行列式值作特征点的侦测，给定图形中的一点p=(x, y)，在尺度σ的海森矩阵为H(p, σ):

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

其中矩阵内的 $L_{xx}(p,\sigma )$ 等函数为二阶微分后的灰阶图像。

9*9的方型滤波器被作为SURF最底的尺度，近似于σ=1.2的高斯滤波器。

尺度空间描述与特征点定位

因为影像会在不同的尺度下作比较，特征点往往会在不同尺度下被侦测到。在SIFT中，由于连续的高斯糢糊处理以及影像的降采样，在尺度上会型成类似金字塔的概念，例如高斯金字塔。

而SURF中尺度是由方型滤波器的大小决定的，并不是连续的高斯糢糊及降采样处理。其中最底层的尺度(初始尺度)的方型滤波器大小为9*9，近似于σ=1.2的高斯滤波器。越往上层的尺度滤波器的大小也就跟著增加，例如15*15、21*21、27*27......。

其尺度的转换公式为:

$\sigma _{approx}=Currentfiltersize*\left({\frac {\left(BaseFilterscale\right)}{BaseFilterSize}}\right)$

与SIFT相同，SURF会使用特征点海森矩阵的行列式值作邻近资料插补来定位特征点。

特征点描述子

为了保留特征点不变的特性，例如旋转、尺度上的不变性，需要赋予特征点一个描述子，使其能保有其不变性且能够轻易地被区分。大多数的描述子建立的方法为描述特征点与其相邻的相素点间的变化，因此描述子往往都是区域性的。

同时描述子的维度也是描述子重要的考量之一，一个维度不足的描述子可能会使能特征点不易区分，然而维度过大的描述子要耗费的计算也就越复杂。SURF的描述子使用了哈尔小波转换的概念，并利用积分图简化描述子的计算。

方位定向

为了使得特征点拥有转动不变性，需要赋予特征点一个方向。SURF的描述子计算特征点周围半径为6σ个像素点的x,y方向的哈尔小波转换，其中σ是此特征点位于的尺度。所得到的小波响应以特征点为中心的高斯函数作加权，并将其值标于一xy作标平面上作图。最后在xy作标平面上以π/3为一个区间，将区间内小波响应的x、y分量加总得到一向量，在所有的向量当中最长的(即x、y分量最大的)即为此特征点的方向。

此外在xy平面上选择角度的区间大小可由角度的解析度、描述子的独特程度等因素来作为调整的考量。

描述子量值

选定了特征点的方向后，其周围像素点需要以此方向为基准来建立描述子。此时以5*5个像素点为一个子区域，取特征点周围20*20个像素点的范围共16个子区域，计算子区域内的x、y方向(此时以平行特征点方向为x、垂直特征点方向为y)的哈尔小波转换总合 $\sum dx$ 、 $\sum dy$ 与其向量长度总合 $\sum |dx|$ 、 $\sum |dy|$ 共四个量值，共可产生一个64维资料的描述子。