加速穩健特徵

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)