SIFT算法原理：SIFT算法詳細介紹

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

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

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

1.1 基本流程

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

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

關鍵點定位：在每個候選的位置上，通過一個擬合精細的模型來確定位置和尺度。關鍵點的選擇依據(jù)于它們的穩(wěn)定程度。

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

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

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

1.2 尺度空間極值檢測

在不同的尺度空間是不能使用相同的窗口檢測極值點，對小的關鍵點使用小的窗口，對大的關鍵點使用大的窗口，為了達到上述目的，我們使用尺度空間濾波器。

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

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

$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)的是圖像的細節(jié)信息。

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

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

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

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

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

在 DoG 搞定之后，就可以在不同的尺度空間中搜索局部最大值了。對于圖像中的一個像素點而言，它需要與自己周圍的 8 鄰域，以及尺度空間中上下兩層中的相鄰的 18（2x9）個點相比。如果是局部最大值，它就可能是一個關鍵點?；旧蟻碚f關鍵點是圖像在相應尺度空間中的最好代表。如下圖所示：

搜索過程從每組的第二層開始，以第二層為當前層，對第二層的DoG圖像中的每個點取一個3×3的立方體，立方體上下層為第一層與第三層。這樣，搜索得到的極值點既有位置坐標（DoG的圖像坐標），又有空間尺度坐標（層坐標）。當?shù)诙铀阉魍瓿珊螅僖缘谌龑幼鳛楫斍皩?，其過程與第二層的搜索類似。當S=3時，每組里面要搜索3層，所以在DOG中就有S+2層，在初使構建的金字塔中每組有S+3層。

1.3 關鍵點定位

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

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

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

將低對比度和邊界的關鍵點去除，得到的就是我們感興趣的關鍵點。

1.4 關鍵點方向確定

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

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

梯度的幅值和方向的計算公式為： $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})$

鄰域像素梯度的計算結果如下圖所示：

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

每個特征點必須分配一個主方向，還需要一個或多個輔方向，增加輔方向的目的是為了增強圖像匹配的魯棒性。輔方向的定義是，當一個柱體的高度大于主方向柱體高度的80%時，則該柱體所代表的的方向就是給特征點的輔方向。

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

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

1.5 關鍵點描述

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

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

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

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

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

1.6 總結

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