SIFT由David Lowe在1999年提出，在2004年加以完善 。SIFT在數字圖像的特征描述方面當之無愧可稱之為最紅最火的一種，許多人對SIFT進行了改進，誕生了SIFT的一系列變種。SIFT已經申請了專利。

SIFT特征是基于物體上的一些局部外觀的興趣點而與影像的大小和旋轉無關。對于光線、噪聲、微視角改變的容忍度也相當高。基于這些特性，它們是高度顯著而且相對容易擷取，在母數龐大的特征數據庫中，很容易辨識物體而且鮮有誤認。使用SIFT特征描述對于部分物體遮蔽的偵測率也相當高，甚至只需要3個以上的SIFT物體特征就足以計算出位置與方位。在現今的電腦硬件速度下和小型的特征數據庫條件下，辨識速度可接近即時運算。SIFT特征的信息量大，適合在海量數據庫中快速準確匹配。

SURF 算法，全稱是 Speeded-Up Robust Features。該算子在保持 SIFT 算子優良性能特點的基礎上，同時解決了 SIFT 計算復雜度高、耗時長的缺點，對興趣點提取及其特征向量描述方面進行了改進，且計算速度得到提高。

SURF （Speeded Up Robust Features）也是一種類似于SIFT的興趣點檢測及描述子算法。其通過Hessian矩陣的行列式來確定興趣點位置，再根據興趣點鄰域點的Haar小波響應來確定描述子，其描述子大小只有64維（也可以擴展到128維，效果更好），是一種非常優秀的興趣點檢測算法。本文主要從SURF原文出發，結合自己一些理解，并比較sift方法，對其算法原理進行總結。

一、FAST-Hessian檢測

首先同SIFT方法一樣，SURF也必須考慮如何確定興趣點位置，不過SIFT采用是DOG來代替LOG算子，找到其在尺度和圖像內局部極值視為特征點，而SURF方法是基于Hessian矩陣的，而它通過積分圖像極大地減少運算時間，并稱之為FAST-Hessian。（這里提一下，SIFT通過DOG來近似LOG，也實際上相當于計算Laplacian，即可以視為Hessian矩陣的跡，而SURF則利用的近似Hessian矩陣的行列式）

首先我們考慮一個Hessian矩陣：

這里的Lxx是指圖像經過高斯二階梯度模板卷積之后得到的，像素點關于x方向的二階梯度。SURF方法考慮將高斯二階梯度模板用盒函數來近似，如下圖：

如此以來，我們可以通過積分圖像非常方便地計算高斯二階梯度，得到其近似：

因為是近似，我們也需要平衡兩者之間的相關比，這里我們假設，尺度為1.2的高斯模板可以用9*9的盒函數模板代替，然后計算下式歸一化尺度的模板比值，這里的是指Frobenius范數：

最后Hessian矩陣的行列式，我們可以近似為：

由此，這里的0.9是歸一化比值，所以在任何尺度下，我們都可以通過這個比來補償近似造成的誤差，因此任何尺度下，我們都可以計算近似Hessian行列式的值。

二、SURF的尺度空間

尺度空間通常通過高斯金字塔來實施，圖像需要被重復高斯平滑，然后經過不斷子采樣，一層一層直到塔頂，如sift方法。而SUFR通過盒函數和積分圖像，我們就不需要像SIFT方法那樣，每組之間需要采樣，而且還需要對當前組應用同上層組相同的濾波器，而SURF方法不需要進行采樣操作，直接應用不同大小的濾波器就可以了。

為什么可以這樣呢？因為都是為了得到不同尺度的圖像，而sift通過采樣操作比圖像卷積操作計算量更少，而對于SURF來說，不存在這樣的問題，因為盒函數和積分圖像的操作計算量也非常小。另一方面，因為不需要采樣，所以也不會出現混疊現象。

下圖說明了這一情況，左圖是sift算法，其是圖像大小減少，而模板不變（這里只是指每組間，組內層之間還是要變的）。而SURF算法（右圖）剛好相反，其是圖像大小不變，而模板大小擴大。

SURF也是將金字塔分為組（Octaves），而每組分為若干層。其將9*9大小的濾波器結果作為初始尺度組，即指的高斯尺度為1.2。那么接下來的每組，是通過逐漸增大的模板來進行濾波圖像，一般情況下，濾波器的大小以9*9，15*15，21*21，27*27等變化，隨著尺度增加，濾波器大小之間的差別也在增加。因此，對于每組來說，其濾波器大小增加數（15-9）是以雙倍增長的（如6到12再24）。與此同時，提取興趣點的采樣間隔也是在以雙倍增長的（這樣可以獲得小的尺度變化范圍）。下面是模板的變化圖：

下圖反映了組及層之間尺度變化，及濾波模板長度變化過程，我們可以發現層間采樣間隔以2倍擴大，所以隨著層尺度增加，其尺度變化的粒度減少了，但是我們發現第一組每一層的尺度變化粒度太大了，所以在這里我們需要引入尺度空間更為精細的插值操作。

尺度空間搭建好了之后，同sift運算一樣，我們找到在尺度及圖像空間的3*3*3的范圍內進行非極大值抑制，找到局部極值點（Hessian行列式），最后再應用尺度和圖像空間的插值操作，以獲得精確的興趣點位置（原文用的是Brown的方法，也可以參考sift方法，不再詳細講解了）

三、興趣點主方向獲得

為了獲得旋轉不變性，我們需要識別興趣點區域的一個主方向。SIFT方法采用的是計算興趣點附近3*1.5?大小的圓形區域內方向直方圖，選擇最大的方向為主方向。而SURF方法則是通過計算其在x，y方向上的haar-wavelet響應，這是在興趣點周圍一個6s半徑大小的圓形區域內。當然小波變換的大小也同尺度參數s有關，其步長為s，其大小為4s。

一旦區域內所有小波響應被計算，再對所有小波響應進行高斯加權（以興趣點為中心，尺度為2.5s），然后建立小波響應dx，dy的坐標系（dx是小波在x方向上的響應，而dy是小波在y方向上的響應），將區域內的每點在這個坐標系來表示，如下圖所示，選擇一個60度的扇區（下圖灰色區域），統計這個扇區所有響應的總和，就獲得了一個總的方向（下圖紅箭頭），旋轉整個扇區，找到最長的矢量方向即為主方向。

四、SURF描述子

同sift算法一樣，SURF也是通過建立興趣點附近區域內的信息來作為描述子的，不過sift是利用鄰域點的方向，而SURF則是利用Haar小波響應。

SURF首先在興趣點附近建立一個20s大小的方形區域，為了獲得旋轉不變性，同sift算法一樣，我們需要將其先旋轉到主方向，然后再將方形區域劃分成16個（4*4）子域。對每個子域（其大小為5s*5s）我們計算25（5*5）個空間歸一化的采樣點的Haar小波響應dx和dy。

之后我們將每個子區域（共4*4）的dx，dy相加，因此每個區域都有一個描述子（如下式），為了增加魯棒性，我們可以給描述子再添加高斯權重（尺度為3.3s，以興趣點為中心）

所以最后在所有的16個子區域內的四位描述子結合，將得到該興趣點的64位描述子

由于小波響應對于光流變化偏差是不變的，所以描述子具有了光流不變性，而對比性不變可以通過將描述子歸一化為單位向量得到。

另外也建立128位的SURF描述子，其將原來小波的結果再細分，比如dx的和將根據dy的符號，分成了兩類，所以此時每個子區域內都有8個分量，SURF-128有非常好效果，如下圖所示。

五、快速索引匹配

我們發現興趣點其Laplacian（Hessian矩陣的跡）的符號（即正負）可以將區分相同對比形狀的不同區域，如黑暗背景下的白斑和相反的情況。

考慮到檢測時，我們容易遇到兩個這樣類似的結構（因為特征興趣點經常是這樣的斑點形狀），原來我們必須為這兩個結構分別建立描述子，現在我們只需要為其中一個建立描述子，而給另一個索引，而在匹配過程中，只要比較一個描述子，就能確定兩個位置，是不是屬于這兩個結構中的一種，如果是，再通過跡來判斷其是這兩個結構中的那一種。

因為引入特性不需要額外的計算（檢測過程中已經計算了）。所以在匹配過程中，可以達到快速的效果。