SIFT特征提取算法詳解

轉載自：https://www.cnblogs.com/wangguchangqing/p/4853263.html

1.SIFT概述

SIFT的全稱是Scale Invariant Feature Transform，尺度不變特征變換，由加拿大教授David G.Lowe提出的。SIFT特征對旋轉、尺度縮放、亮度變化等保持不變性，是一種非常穩定的局部特征。

1.1 SIFT算法具的特點

1. 圖像的局部特征，對旋轉、尺度縮放、亮度變化保持不變，對視角變化、仿射變換、噪聲也保持一定程度的穩定性。
2. 獨特性好，資訊量豐富，适用于海量特征庫進行快速、準确的比對。
3. 多量性，即使是很少幾個物體也可以産生大量的SIFT特征
4. 高速性，經優化的SIFT比對算法甚至可以達到實時性
5. 擴招性，可以很友善的與其他的特征向量進行聯合。

1.2 SIFT特征檢測的步驟

有4個主要步驟

1. 尺度空間的極值檢測 搜尋所有尺度空間上的圖像，通過高斯微分函數來識别潛在的對尺度和選擇不變的興趣點。
2. 特征點定位 在每個候選的位置上，通過一個拟合精細模型來确定位置尺度，關鍵點的選取依據他們的穩定程度。
3. 特征方向指派 基于圖像局部的梯度方向，配置設定給每個關鍵點位置一個或多個方向，後續的所有操作都是對于關鍵點的方向、尺度和位置進行變換，進而提供這些特征的不變性。
4. 特征點描述 在每個特征點周圍的鄰域内，在標明的尺度上測量圖像的局部梯度，這些梯度被變換成一種表示，這種表示允許比較大的局部形狀的變形和光照變換。

2. 尺度空間

在一定的範圍内，無論物體是大還是小，人眼都可以分辨出來。然而計算機要有相同的能力卻不是那麼的容易，在未知的場景中，計算機視覺并不能提供物體的尺度大小，其中的一種方法是把物體不同尺度下的圖像都提供給機器，讓機器能夠對物體在不同的尺度下有一個統一的認知。在建立統一認知的過程中，要考慮的就是在圖像在不同的尺度下都存在的特征點。

2.1 多分辨率圖像金字塔

在早期圖像的多尺度通常使用圖像金字塔表示形式。圖像金字塔是同一圖像在不同的分辨率下得到的一組結果，其生成過程一般包括兩個步驟：

1. 對原始圖像進行平滑

2. 對處理後的圖像進行降采樣（通常是水準、垂直方向的1/2）

   降采樣後得到一系列不斷尺寸縮小的圖像。顯然，一個傳統的金字塔中，每一層的圖像是其上一層圖像長、高的各一半。多分辨率的圖像金字塔雖然生成簡單，但其本質是降采樣，圖像的局部特征則難以保持，也就是無法保持特征的尺度不變性。

   2.2 高斯尺度空間

   我們還可以通過圖像的模糊程度來模拟人在距離物體由遠到近時物體在視網膜上成像過程，距離物體越近其尺寸越大圖像也越模糊，這就是高斯尺度空間，使用不同的參數模糊圖像（分辨率不變），是尺度空間的另一種表現形式。

   我們知道圖像和高斯函數進行卷積運算能夠對圖像進行模糊，使用不同的“高斯核”可得到不同模糊程度的圖像。一副圖像其高斯尺度空間可由其和不同的高斯卷積得到：

   L(x,y,σ)=G(x,y,σ)∗I(x,y)L(x,y,σ)=G(x,y,σ)∗I(x,y)

   其中，G(x,y,σ)是高斯核函數。G(x,y,σ)是高斯核函數。

   G(x,y,σ)=12πσ2ex2+y22σ2G(x,y,σ)=12πσ2ex2+y22σ2

   σσ稱為尺度空間因子，它是高斯正态分布的标準差，反映了圖像被模糊的程度，其值越大圖像越模糊，對應的尺度也就越大。L(x,y,σ)L(x,y,σ)代表着圖像的高斯尺度空間。

   建構尺度空間的目的是為了檢測出在不同的尺度下都存在的特征點，而檢測特征點較好的算子是Δ2GΔ2G(高斯拉普拉斯,LoG）,

   Δ2=∂2∂x2+∂2∂y2Δ2=∂2∂x2+∂2∂y2

   使用LoG雖然能較好的檢測到圖像中的特征點，但是其運算量過大，通常可使用DoG（差分高斯，Difference of Gaussina）來近似計算LoG[Marr and Hidreth]。

   設kk為相鄰兩個高斯尺度空間的比例因子，則DoG的定義：

   D(x,y,σ)=[G(x,y,kσ)−G(x,y,σ)]∗I(x,y)=L(x,y,kσ)−L(x,y,σ)D(x,y,σ)=[G(x,y,kσ)−G(x,y,σ)]∗I(x,y)=L(x,y,kσ)−L(x,y,σ)

   其中，L(x,y,σ)L(x,y,σ)是圖像的高斯尺度空間。

   從上式可以知道，将相鄰的兩個高斯空間的圖像相減就得到了DoG的響應圖像。為了得到DoG圖像，先要建構高斯尺度空間，而高斯的尺度空間可以在圖像金字塔降采樣的基礎上加上高斯濾波得到，也就是對圖像金字塔的每層圖像使用不同的參數σσ進行高斯模糊，使每層金字塔有多張高斯模糊過的圖像。降采樣時，金字塔上邊一組圖像的第一張是由其下面一組圖像倒數第三張降采樣得到。

   易知，高斯金字塔有多組，每組又有多層。一組中的多個層之間的尺度是不一樣的（也就是使用的高斯參數σσ是不同的），相鄰兩層之間的尺度相差一個比例因子kk。如果每組有SS層，則k=21Sk=21S。上一組圖像的最底層圖像是由下一組中尺度為2σ2σ的圖像進行因子為2的降采樣得到的（高斯金字塔先從底層建立）。高斯金字塔建構完成後，将相鄰的高斯金字塔相減就得到了DoG金字塔。

   高斯金字塔的組數一般是

   o=[log2min(m,n)]−ao=[log2⁡min(m,n)]−a

   oo表示高斯金字塔的層數，m，n分别是圖像的行和列。減去的系數aa可以在0−log2min(m,n)0−log2⁡min(m,n)之間的任意值，和具體需要的金字塔的頂層圖像的大小有關。

   高斯模糊參數σσ（尺度空間），可由下面關系式得到

   σ(o,s)=σ0⋅2o+sSσ(o,s)=σ0⋅2o+sS

   其中oo為所在的組，ss為所在的層，σ0σ0為初始的尺度，SS為每組的層數。

   在Lowe的算法實作中σ0=1.6,omin=−1,S=3σ0=1.6,omin=−1,S=3，omin=−1omin=−1就是首先将原圖像的長和寬各擴充一倍。

   從上面可以得知同一組内相鄰層的圖像尺度關系

   σs+1=k⋅σs=21S⋅σsσs+1=k⋅σs=21S⋅σs

   相鄰組之間的尺度關系

   σo+1=2σoσo+1=2σo

   2.3 高斯金字塔建構示例

   以一個512×512512×512的圖像I為例，建構高斯金字塔步驟：(從0開始計數，倒立的金字塔）
3. 金字塔的組數，log2512=9log2⁡512=9，減去因子3，建構的金字塔的組數為6。取每組的層數為3。
4. 建構第0組，将圖像的寬和高都增加一倍，變成1024×10241024×1024（I0I0）。第0層I0∗G(x,y,σ0)I0∗G(x,y,σ0)，第1層I0∗G(x,y,kσ0)I0∗G(x,y,kσ0)，第2層I0∗G(x,y,k2σ0)I0∗G(x,y,k2σ0)
5. 建構第1組，對I0I0降采樣變成512×512512×512（I1I1）。第0層I1∗G(x,y,2σ0)I1∗G(x,y,2σ0)，第1層I1∗G(x,y,2kσ0)I1∗G(x,y,2kσ0)I1∗G(x,y,2k2σ0)I1∗G(x,y,2k2σ0)
6. ⋮⋮
7. 建構第o組，第s層 Io∗G(x,y,2oksσ0)Io∗G(x,y,2oksσ0)

高斯金字塔建構成功後，将每一組相鄰的兩層相減就可以得到DoG金字塔.

3. DoG空間極值檢測

為了尋找尺度空間的極值點，每個像素點要和其圖像域（同一尺度空間）和尺度域（相鄰的尺度空間）的所有相鄰點進行比較，當其大于（或者小于）所有相鄰點時，改點就是極值點。如圖所示，中間的檢測點要和其所在圖像的3×33×3鄰域8個像素點，以及其相鄰的上下兩層的3×33×3領域18個像素點，共26個像素點進行比較。

從上面的描述中可以知道，每組圖像的第一層和最後一層是無法進行比較取得極值的。為了滿足尺度變換的連續性，在每一組圖像的頂層繼續使用高斯模糊生成3幅圖像，高斯金字塔每組有S+3S+3層圖像，DoG金字塔的每組有S+2S+2組圖像。

3.1 尺度變化的連續性

設S=3S=3，也就是每組有3層，則k=21S=213k=21S=213，也就是有高斯金字塔每組有(S−1)3層圖像，DoG金字塔每組有(S−1)3層圖像，DoG金字塔每組有(S-2)2層圖像。在DoG金字塔的第一組有兩層尺度分别是σ,kσσ,kσ，第二組有兩層的尺度分别是2σ,2kσ2σ,2kσ，由于隻有兩項是無法比較取得極值的（隻有左右兩邊都有值才能有極值）。由于無法比較取得極值，那麼我們就需要繼續對每組的圖像進行高斯模糊，使得尺度形成σ,kσ,k2σ,k3σ,k4σσ,kσ,k2σ,k3σ,k4σ，這樣就可以選擇中間的三項kσ,k2σ,k3σkσ,k2σ,k3σ。對應的下一組由上一組降采樣得到的三項是2kσ,2k2σ,2k3σ2kσ,2k2σ,2k3σ，其首項2kσ=2⋅213σ=243σ2kσ=2⋅213σ=243σ，剛好與上一組的最後一項k3σ=233σk3σ=233σ的尺度連續起來。

4. 删除不好的極值點（特征點）

通過比較檢測得到的DoG的局部極值點實在離散的空間搜尋得到的，由于離散空間是對連續空間采樣得到的結果，是以在離散空間找到的極值點不一定是真正意義上的極值點，是以要設法将不滿足條件的點剔除掉。可以通過尺度空間DoG函數進行曲線拟合尋找極值點，這一步的本質是去掉DoG局部曲率非常不對稱的點。

要剔除掉的不符合要求的點主要有兩種：

1. 低對比度的特征點
2. 不穩定的邊緣響應點

   4.1 剔除低對比度的特征點

   候選特征點x，其偏移量定義為ΔxΔx，其對比度為D(x)D(x)的絕對值∣D(x)∣∣D(x)∣，對D(x)D(x)應用泰勒展開式

   D(x)=D+∂DT∂xΔx+12ΔxT∂2D∂x2ΔxD(x)=D+∂DT∂xΔx+12ΔxT∂2D∂x2Δx

   由于x是D(x)的極值點，是以對上式求導并令其為0，得到

   Δx=−∂2D−1∂x2∂D(x)∂xΔx=−∂2D−1∂x2∂D(x)∂x

   然後再把求得的ΔxΔx代入到D(x)的泰勒展開式中

   D(x^)=D+12∂DT∂xx^D(x^)=D+12∂DT∂xx^

   設對比度的門檻值為T，若∣D(x^)∣≥T∣D(x^)∣≥T，則該特征點保留，否則剔除掉。

4.2 剔除不穩定的邊緣響應點

在邊緣梯度的方向上主曲率值比較大，而沿着邊緣方向則主曲率值較小。候選特征點的DoG函數D(x)的主曲率與2×22×2Hessian矩陣HH的特征值成正比。

H=[DxxDyxDxyDyy]H=[DxxDyxDxyDyy]

其中，Dxx,Dxy,DyyDxx,Dxy,Dyy是候選點鄰域對應位置的差分求得的。

為了避免求具體的值，可以使用HH特征值得比例。設α=λmaxα=λmax為H的最大特征值，β=λminβ=λmin為H的最小特征值，則

Tr(H)=Dxx+Dyy=α+βDet(H)=Dxx+Dyy−D2xy=α⋅βTr(H)=Dxx+Dyy=α+βDet(H)=Dxx+Dyy−Dxy2=α⋅β

其中，Tr(H)Tr(H)為矩陣H的迹，Det(H)Det(H)為矩陣H的行列式。

設γ=αβγ=αβ 表示最大特征值和最小特征值的比值，則

Tr(H)2Det(H)=(α+β)2αβ=(γβ+β)2γβ2=(γ+1)2γTr(H)2Det(H)=(α+β)2αβ=(γβ+β)2γβ2=(γ+1)2γ

上式的結果與兩個特征值的比例有關，和具體的大小無關，當兩個特征值想等時其值最小，并且随着γγ的增大而增大。是以為了檢測主曲率是否在某個門檻值TγTγ下，隻需檢測

Tr(H)2Det(H)>(Tγ+1)2TγTr(H)2Det(H)>(Tγ+1)2Tγ

如果上式成立，則剔除該特征點，否則保留。（Lowe論文中取Tγ=10Tγ=10)

5. 求取特征點的主方向

經過上面的步驟已經找到了在不同尺度下都存在的特征點，為了實作圖像旋轉不變性，需要給特征點的方向進行指派。利用特征點鄰域像素的梯度分布特性來确定其方向參數，再利用圖像的梯度直方圖求取關鍵點局部結構的穩定方向。

找到了特征點，也就可以得到該特征點的尺度σσ，也就可以得到特征點所在的尺度圖像

L(x,y)=G(x,y,σ)∗I(x,y)L(x,y)=G(x,y,σ)∗I(x,y)

計算以特征點為中心、以3×1.5σ3×1.5σ為半徑的區域圖像的幅角和幅值，每個點L(x,y)的梯度的模m(x,y)m(x,y)以及方向θ(x,y)θ(x,y)可通過下面公司求得

m(x,y)=[L(x+1,y)−L(x−1,y)]2+[L(x,y+1)−L(x,y−1)]2−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−√m(x,y)=[L(x+1,y)−L(x−1,y)]2+[L(x,y+1)−L(x,y−1)]2

θ(x,y)=arctanL(x,y+1)−L(x,y−1)L(x+1,y)−L(x−1,y)θ(x,y)=arctan⁡L(x,y+1)−L(x,y−1)L(x+1,y)−L(x−1,y)

計算得到梯度方向後，就要使用直方圖統計特征點鄰域内像素對應的梯度方向和幅值。梯度方向的直方圖的橫軸是梯度方向的角度（梯度方向的範圍是0到360度，直方圖每36度一個柱共10個柱，或者沒45度一個柱共8個柱），縱軸是梯度方向對應梯度幅值的累加，在直方圖的峰值就是特征點的主方向。在Lowe的論文還提到了使用高斯函數對直方圖進行平滑以增強特征點近的鄰域點對關鍵點方向的作用，并減少突變的影響。為了得到更精确的方向，通常還可以對離散的梯度直方圖進行插值拟合。具體而言，關鍵點的方向可以由和主峰值最近的三個柱值通過抛物線插值得到。在梯度直方圖中，當存在一個相當于主峰值80%能量的柱值時，則可以将這個方向認為是該特征點輔助方向。是以，一個特征點可能檢測到多個方向（也可以了解為，一個特征點可能産生多個坐标、尺度相同，但是方向不同的特征點）。Lowe在論文中指出

15%的關鍵點具有多方向，而且這些點對比對的穩定性很關鍵。

得到特征點的主方向後，對于每個特征點可以得到三個資訊(x,y,σ,θ)(x,y,σ,θ)，即位置、尺度和方向。由此可以确定一個SIFT特征區域，一個SIFT特征區域由三個值表示，中心表示特征點位置，半徑表示關鍵點的尺度，箭頭表示主方向。具有多個方向的關鍵點可以被複制成多份，然後将方向值分别賦給複制後的特征點，一個特征點就産生了多個坐标、尺度相等，但是方向不同的特征點。

6. 生成特征描述

通過以上的步驟已經找到了SIFT特征點位置、尺度和方向資訊，下面就需要使用一組向量來描述關鍵點也就是生成特征點描述子，這個描述符不隻包含特征點，也含有特征點周圍對其有貢獻的像素點。描述子應具有較高的獨立性，以保證比對率。

特征描述符的生成大緻有三個步驟：

1. 校正旋轉主方向，確定旋轉不變性。
2. 生成描述子，最終形成一個128維的特征向量
3. 歸一化處理，将特征向量長度進行歸一化處理，進一步去除光照的影響。

為了保證特征矢量的旋轉不變性，要以特征點為中心，在附近鄰域内将坐标軸旋轉θθ（特征點的主方向）角度，即将坐标軸旋轉為特征點的主方向。旋轉後鄰域内像素的新坐标為：

[x′y′]=[cosθ−sinθsinθcosθ][xy][x′y′]=[cos⁡θ−sin⁡θsin⁡θcos⁡θ][xy]

旋轉後以主方向為中心取 8×88×8的視窗。下圖所示，左圖的中央為目前關鍵點的位置，每個小格代表為關鍵點鄰域所在尺度空間的一個像素，求取每個像素的梯度幅值與梯度方向，箭頭方向代表該像素的梯度方向，長度代表梯度幅值，然後利用高斯視窗對其進行權重運算。最後在每個4×44×4的小塊上繪制8個方向的梯度直方圖，計算每個梯度方向的累加值，即可形成一個種子點，如右圖所示。每個特征點由4個種子點組成，每個種子點有8個方向的向量資訊。這種鄰域方向性資訊聯合增強了算法的抗噪聲能力，同時對于含有定位誤差的特征比對也提供了比較理性的容錯性。

與求主方向不同，此時每個種子區域的梯度直方圖在0-360之間劃分為8個方向區間，每個區間為45度，即每個種子點有8個方向的梯度強度資訊。

在實際的計算過程中，為了增強比對的穩健性，Lowe建議

對每個關鍵點使用4×44×4共16個種子點來描述，這樣一個關鍵點就可以産生128維的SIFT特征向量。

通過對特征點周圍的像素進行分塊，計算塊内梯度直方圖，生成具有獨特性的向量，這個向量是該區域圖像資訊的一種抽象，具有唯一性。

7. 總結

SIFT特征以其對旋轉、尺度縮放、亮度等保持不變性，是一種非常穩定的局部特征，在圖像處理和計算機視覺領域有着很重要的作用，其本身也是非常複雜的，下面對其計算過程做一個粗略總結。

1. DoG尺度空間的極值檢測。 首先是構造DoG尺度空間，在SIFT中使用不同參數的高斯模糊來表示不同的尺度空間。而構造尺度空間是為了檢測在不同尺度下都存在的特征點，特征點的檢測比較常用的方法是Δ2GΔ2G（高斯拉普拉斯LoG），但是LoG的運算量是比較大的，Marr和Hidreth曾指出，可以使用DoG（差分高斯）來近似計算LoG，是以在DoG的尺度空間下檢測極值點。
2. 删除不穩定的極值點。主要删除兩類：低對比度的極值點以及不穩定的邊緣響應點。
3. ** 确定特征點的主方向**。以特征點的為中心、以3×1.5σ3×1.5σ為半徑的領域内計算各個像素點的梯度的幅角和幅值，然後使用直方圖對梯度的幅角進行統計。直方圖的橫軸是梯度的方向，縱軸為梯度方向對應梯度幅值的累加值，直方圖中最高峰所對應的方向即為特征點的方向。
4. 生成特征點的描述子。 首先将坐标軸旋轉為特征點的方向，以特征點為中心的16×1616×16的視窗的像素的梯度幅值和方向，将視窗内的像素分成16塊，每塊是其像素内8個方向的直方圖統計，共可形成128維的特征向量。