SIFT算法原理：SIFT算法詳細(xì)介紹

前面我們介紹了Harris和Shi-Tomasi角點(diǎn)檢測(cè)算法，這兩種算法具有旋轉(zhuǎn)不變性，但不具有尺度不變性，以下圖為例，在左側(cè)小圖中可以檢測(cè)到角點(diǎn)，但是圖像被放大后，在使用同樣的窗口，就檢測(cè)不到角點(diǎn)了。

所以，下面我們來(lái)介紹一種計(jì)算機(jī)視覺(jué)的算法，尺度不變特征轉(zhuǎn)換即SIFT (Scale-invariant feature transform)。它用來(lái)偵測(cè)與描述影像中的局部性特征，它在空間尺度中尋找極值點(diǎn)，并提取出其位置、尺度、旋轉(zhuǎn)不變量，此算法由 David Lowe在1999年所發(fā)表，2004年完善總結(jié)。應(yīng)用范圍包含物體辨識(shí)、機(jī)器人地圖感知與導(dǎo)航、影像縫合、3D模型建立、手勢(shì)辨識(shí)、影像追蹤和動(dòng)作比對(duì)等領(lǐng)域。

SIFT算法的實(shí)質(zhì)是在不同的尺度空間上查找關(guān)鍵點(diǎn)(特征點(diǎn))，并計(jì)算出關(guān)鍵點(diǎn)的方向。SIFT所查找到的關(guān)鍵點(diǎn)是一些十分突出，不會(huì)因光照，仿射變換和噪音等因素而變化的點(diǎn)，如角點(diǎn)、邊緣點(diǎn)、暗區(qū)的亮點(diǎn)及亮區(qū)的暗點(diǎn)等。

1.1 基本流程

Lowe將SIFT算法分解為如下四步：

尺度空間極值檢測(cè)：搜索所有尺度上的圖像位置。通過(guò)高斯差分函數(shù)來(lái)識(shí)別潛在的對(duì)于尺度和旋轉(zhuǎn)不變的關(guān)鍵點(diǎn)。

關(guān)鍵點(diǎn)定位：在每個(gè)候選的位置上，通過(guò)一個(gè)擬合精細(xì)的模型來(lái)確定位置和尺度。關(guān)鍵點(diǎn)的選擇依據(jù)于它們的穩(wěn)定程度。

關(guān)鍵點(diǎn)方向確定：基于圖像局部的梯度方向，分配給每個(gè)關(guān)鍵點(diǎn)位置一個(gè)或多個(gè)方向。所有后面的對(duì)圖像數(shù)據(jù)的操作都相對(duì)于關(guān)鍵點(diǎn)的方向、尺度和位置進(jìn)行變換，從而保證了對(duì)于這些變換的不變性。

關(guān)鍵點(diǎn)描述：在每個(gè)關(guān)鍵點(diǎn)周圍的鄰域內(nèi)，在選定的尺度上測(cè)量圖像局部的梯度。這些梯度作為關(guān)鍵點(diǎn)的描述符，它允許比較大的局部形狀的變形或光照變化。

我們就沿著Lowe的步驟，對(duì)SIFT算法的實(shí)現(xiàn)過(guò)程進(jìn)行介紹：

1.2 尺度空間極值檢測(cè)

在不同的尺度空間是不能使用相同的窗口檢測(cè)極值點(diǎn)，對(duì)小的關(guān)鍵點(diǎn)使用小的窗口，對(duì)大的關(guān)鍵點(diǎn)使用大的窗口，為了達(dá)到上述目的，我們使用尺度空間濾波器。

高斯核是唯一可以產(chǎn)生多尺度空間的核函數(shù)。-《Scale-space theory: A basic tool for analysing structures at different scales》。

一個(gè)圖像的尺度空間L(x,y,σ)，定義為原始圖像I(x,y)與一個(gè)可變尺度的2維高斯函數(shù)G(x,y,σ)卷積運(yùn)算 ，即：

$L(x,y,\sigma) = G(x,y,\sigma)* I(x,y)$ 其中： $G(x,y,\sigma)=\frac{1}{2\pi\sigma^2}e^{-\frac{x^2+y^2}{2\sigma^2}}$ $\sigma$是尺度空間因子，它決定了圖像的模糊的程度。在大尺度下（$\sigma$值大）表現(xiàn)的是圖像的概貌信息，在小尺度下（$\sigma$值小）表現(xiàn)的是圖像的細(xì)節(jié)信息。

在計(jì)算高斯函數(shù)的離散近似時(shí)，在大概3σ距離之外的像素都可以看作不起作用，這些像素的計(jì)算也就可以忽略。所以，在實(shí)際應(yīng)用中，只計(jì)算(6σ+1)*(6σ+1)的高斯卷積核就可以保證相關(guān)像素影響。

下面我們構(gòu)建圖像的高斯金字塔，它采用高斯函數(shù)對(duì)圖像進(jìn)行模糊以及降采樣處理得到的，高斯金字塔構(gòu)建過(guò)程中，首先將圖像擴(kuò)大一倍，在擴(kuò)大的圖像的基礎(chǔ)之上構(gòu)建高斯金字塔，然后對(duì)該尺寸下圖像進(jìn)行高斯模糊，幾幅模糊之后的圖像集合構(gòu)成了一個(gè)Octave，然后對(duì)該Octave下選擇一幅圖像進(jìn)行下采樣，長(zhǎng)和寬分別縮短一倍，圖像面積變?yōu)樵瓉?lái)四分之一。這幅圖像就是下一個(gè)Octave的初始圖像，在初始圖像的基礎(chǔ)上完成屬于這個(gè)Octave的高斯模糊處理，以此類推完成整個(gè)算法所需要的所有八度構(gòu)建，這樣這個(gè)高斯金字塔就構(gòu)建出來(lái)了，整個(gè)流程如下圖所示：

利用LoG(高斯拉普拉斯方法)，即圖像的二階導(dǎo)數(shù)，可以在不同的尺度下檢測(cè)圖像的關(guān)鍵點(diǎn)信息，從而確定圖像的特征點(diǎn)。但LoG的計(jì)算量大，效率低。所以我們通過(guò)兩個(gè)相鄰高斯尺度空間的圖像的相減，得到DoG(高斯差分)來(lái)近似LoG。

為了計(jì)算DoG我們構(gòu)建高斯差分金字塔，該金字塔是在上述的高斯金字塔的基礎(chǔ)上構(gòu)建而成的，建立過(guò)程是：在高斯金字塔中每個(gè)Octave中相鄰兩層相減就構(gòu)成了高斯差分金字塔。如下圖所示：

高斯差分金字塔的第1組第1層是由高斯金字塔的第1組第2層減第1組第1層得到的。以此類推，逐組逐層生成每一個(gè)差分圖像，所有差分圖像構(gòu)成差分金字塔。概括為DOG金字塔的第o組第l層圖像是有高斯金字塔的第o組第l+1層減第o組第l層得到的。后續(xù)Sift特征點(diǎn)的提取都是在DOG金字塔上進(jìn)行的

在 DoG 搞定之后，就可以在不同的尺度空間中搜索局部最大值了。對(duì)于圖像中的一個(gè)像素點(diǎn)而言，它需要與自己周圍的 8 鄰域，以及尺度空間中上下兩層中的相鄰的 18（2x9）個(gè)點(diǎn)相比。如果是局部最大值，它就可能是一個(gè)關(guān)鍵點(diǎn)?；旧蟻?lái)說(shuō)關(guān)鍵點(diǎn)是圖像在相應(yīng)尺度空間中的最好代表。如下圖所示：

搜索過(guò)程從每組的第二層開(kāi)始，以第二層為當(dāng)前層，對(duì)第二層的DoG圖像中的每個(gè)點(diǎn)取一個(gè)3×3的立方體，立方體上下層為第一層與第三層。這樣，搜索得到的極值點(diǎn)既有位置坐標(biāo)（DoG的圖像坐標(biāo)），又有空間尺度坐標(biāo)（層坐標(biāo)）。當(dāng)?shù)诙铀阉魍瓿珊?，再以第三層作為?dāng)前層，其過(guò)程與第二層的搜索類似。當(dāng)S=3時(shí)，每組里面要搜索3層，所以在DOG中就有S+2層，在初使構(gòu)建的金字塔中每組有S+3層。

1.3 關(guān)鍵點(diǎn)定位

由于DoG對(duì)噪聲和邊緣比較敏感，因此在上面高斯差分金字塔中檢測(cè)到的局部極值點(diǎn)需經(jīng)過(guò)進(jìn)一步的檢驗(yàn)才能精確定位為特征點(diǎn)。

使用尺度空間的泰勒級(jí)數(shù)展開(kāi)來(lái)獲得極值的準(zhǔn)確位置， 如果極值點(diǎn)的 灰度值小于閾值（一般為0.03或0.04）就會(huì)被忽略掉。 在 OpenCV 中這種閾值被稱為 contrastThreshold。

DoG 算法對(duì)邊界非常敏感， 所以我們必須要把邊界去除。 Harris 算法除了可以用于角點(diǎn)檢測(cè)之外還可以用于檢測(cè)邊界。從 Harris 角點(diǎn)檢測(cè)的算法中，當(dāng)一個(gè)特征值遠(yuǎn)遠(yuǎn)大于另外一個(gè)特征值時(shí)檢測(cè)到的是邊界。那在DoG算法中欠佳的關(guān)鍵點(diǎn)在平行邊緣的方向有較大的主曲率，而在垂直于邊緣的方向有較小的曲率，兩者的比值如果高于某個(gè)閾值（在OpenCV中叫做邊界閾值），就認(rèn)為該關(guān)鍵點(diǎn)為邊界，將被忽略，一般將該閾值設(shè)置為10。

將低對(duì)比度和邊界的關(guān)鍵點(diǎn)去除，得到的就是我們感興趣的關(guān)鍵點(diǎn)。

1.4 關(guān)鍵點(diǎn)方向確定

經(jīng)過(guò)上述兩個(gè)步驟，圖像的關(guān)鍵點(diǎn)就完全找到了，這些關(guān)鍵點(diǎn)具有尺度不變性。為了實(shí)現(xiàn)旋轉(zhuǎn)不變性，還需要為每個(gè)關(guān)鍵點(diǎn)分配一個(gè)方向角度，也就是根據(jù)檢測(cè)到的關(guān)鍵點(diǎn)所在高斯尺度圖像的鄰域結(jié)構(gòu)中求得一個(gè)方向基準(zhǔn)。

對(duì)于任一關(guān)鍵點(diǎn)，我們采集其所在高斯金字塔圖像以r為半徑的區(qū)域內(nèi)所有像素的梯度特征（幅值和幅角），半徑r為： $r = 3\times1.5\sigma$ 其中σ是關(guān)鍵點(diǎn)所在octave的圖像的尺度，可以得到對(duì)應(yīng)的尺度圖像。

梯度的幅值和方向的計(jì)算公式為： $m(x,y)=\sqrt{(L(x+1,y)-L(x-1,y)^2+(L(x,y+1)-L(x,y-1))^2}$

$\theta(x,y) = arctan(\frac{L(x,y+1)-L(x,y-1)}{L(x+1,y)-L(x-1),y})$

鄰域像素梯度的計(jì)算結(jié)果如下圖所示：

完成關(guān)鍵點(diǎn)梯度計(jì)算后，使用直方圖統(tǒng)計(jì)關(guān)鍵點(diǎn)鄰域內(nèi)像素的梯度幅值和方向。具體做法是，將360°分為36柱，每10°為一柱，然后在以r為半徑的區(qū)域內(nèi)，將梯度方向在某一個(gè)柱內(nèi)的像素找出來(lái)，然后將他們的幅值相加在一起作為柱的高度。因?yàn)樵趓為半徑的區(qū)域內(nèi)像素的梯度幅值對(duì)中心像素的貢獻(xiàn)是不同的，因此還需要對(duì)幅值進(jìn)行加權(quán)處理，采用高斯加權(quán)，方差為1.5σ。如下圖所示，為簡(jiǎn)化圖中只畫(huà)了8個(gè)方向的直方圖。

每個(gè)特征點(diǎn)必須分配一個(gè)主方向，還需要一個(gè)或多個(gè)輔方向，增加輔方向的目的是為了增強(qiáng)圖像匹配的魯棒性。輔方向的定義是，當(dāng)一個(gè)柱體的高度大于主方向柱體高度的80%時(shí)，則該柱體所代表的的方向就是給特征點(diǎn)的輔方向。

直方圖的峰值，即最高的柱代表的方向是特征點(diǎn)鄰域范圍內(nèi)圖像梯度的主方向，但該柱體代表的角度是一個(gè)范圍，所以我們還要對(duì)離散的直方圖進(jìn)行插值擬合，以得到更精確的方向角度值。利用拋物線對(duì)離散的直方圖進(jìn)行擬合，如下圖所示：

獲得圖像關(guān)鍵點(diǎn)主方向后，每個(gè)關(guān)鍵點(diǎn)有三個(gè)信息(x,y,σ,θ)：位置、尺度、方向。由此我們可以確定一個(gè)SIFT特征區(qū)域。通常使用一個(gè)帶箭頭的圓或直接使用箭頭表示SIFT區(qū)域的三個(gè)值：中心表示特征點(diǎn)位置，半徑表示關(guān)鍵點(diǎn)尺度，箭頭表示方向。如下圖所示：

1.5 關(guān)鍵點(diǎn)描述

通過(guò)以上步驟，每個(gè)關(guān)鍵點(diǎn)就被分配了位置，尺度和方向信息。接下來(lái)我們?yōu)槊總€(gè)關(guān)鍵點(diǎn)建立一個(gè)描述符，該描述符既具有可區(qū)分性，又具有對(duì)某些變量的不變性，如光照，視角等。而且描述符不僅僅包含關(guān)鍵點(diǎn)，也包括關(guān)鍵點(diǎn)周圍對(duì)其有貢獻(xiàn)的的像素點(diǎn)。主要思路就是通過(guò)將關(guān)鍵點(diǎn)周圍圖像區(qū)域分塊，計(jì)算塊內(nèi)的梯度直方圖，生成具有特征向量，對(duì)圖像信息進(jìn)行抽象。

描述符與特征點(diǎn)所在的尺度有關(guān)，所以我們?cè)陉P(guān)鍵點(diǎn)所在的高斯尺度圖像上生成對(duì)應(yīng)的描述符。以特征點(diǎn)為中心，將其附近鄰域劃分為$d*d$個(gè)子區(qū)域（一般取d=4)，每個(gè)子區(qū)域都是一個(gè)正方形，邊長(zhǎng)為3σ，考慮到實(shí)際計(jì)算時(shí)，需進(jìn)行三次線性插值，所以特征點(diǎn)鄰域的為$3\sigma(d+1)*3\sigma(d+1)$的范圍，如下圖所示：

為了保證特征點(diǎn)的旋轉(zhuǎn)不變性，以特征點(diǎn)為中心，將坐標(biāo)軸旋轉(zhuǎn)為關(guān)鍵點(diǎn)的主方向，如下圖所示：

計(jì)算子區(qū)域內(nèi)的像素的梯度，并按照σ=0.5d進(jìn)行高斯加權(quán)，然后插值計(jì)算得到每個(gè)種子點(diǎn)的八個(gè)方向的梯度，插值方法如下圖所示：

每個(gè)種子點(diǎn)的梯度都是由覆蓋其的4個(gè)子區(qū)域插值而得的。如圖中的紅色點(diǎn)，落在第0行和第1行之間，對(duì)這兩行都有貢獻(xiàn)。對(duì)第0行第3列種子點(diǎn)的貢獻(xiàn)因子為dr，對(duì)第1行第3列的貢獻(xiàn)因子為1-dr，同理，對(duì)鄰近兩列的貢獻(xiàn)因子為dc和1-dc，對(duì)鄰近兩個(gè)方向的貢獻(xiàn)因子為do和1-do。則最終累加在每個(gè)方向上的梯度大小為： $weight = w*dr^k(1-dr)^{(1-k)}dc^m(1-dc)^{1-m}do^n(1-do)^{1-n}$ 其中k，m，n為0或?yàn)?。 如上統(tǒng)計(jì)$4*4*8=128$個(gè)梯度信息即為該關(guān)鍵點(diǎn)的特征向量，按照特征點(diǎn)的對(duì)每個(gè)關(guān)鍵點(diǎn)的特征向量進(jìn)行排序，就得到了SIFT特征描述向量。

1.6 總結(jié)

SIFT在圖像的不變特征提取方面擁有無(wú)與倫比的優(yōu)勢(shì)，但并不完美，仍然存在實(shí)時(shí)性不高，有時(shí)特征點(diǎn)較少，對(duì)邊緣光滑的目標(biāo)無(wú)法準(zhǔn)確提取特征點(diǎn)等缺陷，自SIFT算法問(wèn)世以來(lái)，人們就一直對(duì)其進(jìn)行優(yōu)化和改進(jìn)，其中最著名的就是SURF算法。