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

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

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

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

一、FAST-Hessian檢測

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

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

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

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

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

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

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

二、SURF的尺度空間

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

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

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

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

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

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

三、興趣點主方向獲得

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

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

四、SURF描述子

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

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

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

所以最后在所有的16個子區(qū)域內(nèi)的四位描述子結(jié)合，將得到該興趣點的64位描述子

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

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

五、快速索引匹配

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

考慮到檢測時，我們?nèi)菀子龅絻蓚€這樣類似的結(jié)構(gòu)（因為特征興趣點經(jīng)常是這樣的斑點形狀），原來我們必須為這兩個結(jié)構(gòu)分別建立描述子，現(xiàn)在我們只需要為其中一個建立描述子，而給另一個索引，而在匹配過程中，只要比較一個描述子，就能確定兩個位置，是不是屬于這兩個結(jié)構(gòu)中的一種，如果是，再通過跡來判斷其是這兩個結(jié)構(gòu)中的那一種。

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