SURF

**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 維資料的描述子。

### 描述子配對

替所有的特徵點建立描述子後便能使用描述子達成特徵點的配對，藉此應用在物體辨識、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)