加速稳健特征

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} = Current filter size * \left( \frac{\left(Base Filter scale\right) }{Base Filter Size} \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维资料的描述子。

### 描述子配对

替所有的特征点建立描述子后便能使用描述子达成特征点的配对，借此应用在物体辨识、3D模型建立等应用上。

## 实现

- 原始实现 (闭源)
- OpenSURF (开源) 有详细的文档和参考手册的实现(C++, C#, Java, Android, iPhone)
- OpenSurfCL (开源) OpenSURF 在 OpenCL 上的免费实现(C++, C# Wrapper, JNI)
- OpenCV SURF (开源) SURF 的特征分离实现 (OpenCV 2.0)
- SURFmex Matlab OpenCV的 SURF 接口(MEX)代码。
- OpenSURF Matlab (开源) 到 OpenSURF (Matlab) 的接口
- libmv SURF (开源) 分离与匹配的实现
- Python mahotas (开源) 包含 SURF 实现的计算机视觉包
- Dlib C++ Library (开源) SURF 特征分离的实现
- Pan-o-matic (开源) 包含 SURF 算法的软件
- Parallel SURF 基于 Pan-o-matic 的多线程实现
- C# SURF plugin for Multi-Agent Serving System (开源) 分离和匹配的实现
- JavaSurf (开源) java 实现 (平台独立)
- JOpenSURF (开源) java 翻译的 OpenSURF
- ImageJ SURF (开源) 作为 ImageJ 插件，拥有舒适的GUI和输出统计的SURF实现(平台独立)
- ASSURF (开源) 在 Adobe Flash 平台中基于 ActionScript 的SURF实现
- Speeded Up SURF (开源) GPU 实现
- CUDA SURF (开源) GPU 使用 CUDA 的实现, 接口与 OpenSURF (C++, CUDA) 类似
- Mathematica 实现
- GPU SURF (开源) GPU 实现

## 参见

- 尺度不变特征变换 (SIFT)
- Gradient Location and Orientation Histogram
- LESH - Local Energy based Shape Histogram
- Blob detection
- 特征检测

## 引用

- 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
- Christopher Evans "Notes on the OpenSURF Library", MSc Computer Science, University of Bristol
- P. M. Panchal, S. R. Panchal, S. K. Shah, " A Comparison of SIFT and SURF ", International Journal of Innovative Research in Computer and Communication Engineering Vol. 1, Issue 2, April 2013

## 外部链接

- SURF on Github
- Website of SURF: Speeded Up Robust Features* First publication of Speeded Up Robust Features (2006)
- Revised publication of SURF (2008)