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

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

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

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

一、FAST-Hessian檢測(cè)

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

首先我們考慮一個(gè)Hessian矩陣：

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

如此以來(lái)，我們可以通過(guò)積分圖像非常方便地計(jì)算高斯二階梯度，得到其近似：

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

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

由此，這里的0.9是歸一化比值，所以在任何尺度下，我們都可以通過(guò)這個(gè)比來(lái)補(bǔ)償近似造成的誤差，因此任何尺度下，我們都可以計(jì)算近似Hessian行列式的值。

二、SURF的尺度空間

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

為什么可以這樣呢？因?yàn)槎际菫榱说玫讲煌叨鹊膱D像，而sift通過(guò)采樣操作比圖像卷積操作計(jì)算量更少，而對(duì)于SURF來(lái)說(shuō)，不存在這樣的問(wèn)題，因?yàn)楹泻瘮?shù)和積分圖像的操作計(jì)算量也非常小。另一方面，因?yàn)椴恍枰蓸樱砸膊粫?huì)出現(xiàn)混疊現(xiàn)象。

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

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

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

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

三、興趣點(diǎn)主方向獲得

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

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

四、SURF描述子

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

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

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

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

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

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

五、快速索引匹配

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

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

因?yàn)橐胩匦圆恍枰~外的計(jì)算（檢測(cè)過(guò)程中已經(jīng)計(jì)算了）。所以在匹配過(guò)程中，可以達(dá)到快速的效果。