加速穩健特徵

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