轉自：http://www.jellon.cn/index.php/archives/374

?

一、綜述

Scale-invariant feature transform(簡稱SIFT)是一種圖像特征提取與匹配算法。SIFT算法由David.G.Lowe于1999年提出，2004年完善總結，后來Y.Ke(2004)將其描述子部分用PCA代替直方圖的方式，對其進行改進。SIFT算法可以處理兩幅圖像之間發生平移、旋轉、尺度變化、光照變化情況下的特征匹配問題，并能在一定程度上對視角變化、仿射變化也具備較為穩定的特征匹配能力。

二、SIFT特征提取算法

?

SIFT算法首先在尺度空間進行特征檢測，并確定關鍵點的位置和關鍵點所處的尺度，然后使用關鍵點鄰域梯度的主方向作為該點的方向特征，以實現算子對尺度和方向的無關性。

SIFT算法提取的SIFT特征向量具有如下特性：

a) SIFT特征是圖像的局部特征，其對旋轉、尺度縮放、亮度變化保持不變性，對視角變化、仿射變換、噪聲也保持一定程度的穩定性。

b) 獨特性好，信息量豐富，適用于在海量特征數據庫中進行快速、準確的匹配。

c) 多量性，即使少數的幾個物體也可以產生大量SIFT特征向量。

d) 高速性，經優化的SIFT匹配算法甚至可以達到實時的要求。

e) 可擴展性，可以很方便的與其他形式的特征向量進行聯合。

一幅圖像SIFT特征向量的生成算法總共包括4步：尺度空間極值檢測、關鍵點位置及尺度確定、關鍵點方向確定、特征向量生成。最后通過特征向量完成特征點的匹配。

2.1尺度空間極值檢測

機器人在環境中走動時，攝像機和環境中物體的相對位置會發生變化，導致圖像上物體的特征的尺度發生變換。我們希望特征具有尺度不變性，即當特征尺度變化時，特征點檢測器仍然能夠準確的檢測出特征點及其尺度。為滿足以上條件，特征檢測需要在多尺度空間的框架下進行。

尺度空間理論是檢測不變特征的基礎。Witkin(1983)提出了尺度空間理論，他主要討論了一維信號平滑處理的問題。Koenderink(1984)把這種理論擴展到二維圖像，并證明高斯卷積核是實現尺度變換的唯一變換核。

二維高斯函數定義如下：

一幅二維圖像，在不同尺度下的尺度空間表示可由圖像與高斯核卷積得到：

其中(x,y)為圖像點的像素坐標，I(x,y)為圖像數據。σ稱為尺度空間因子，它也是高斯正態分布的方差，其反映了圖像被平滑的程度，其值越小表征圖像被平滑程度越小，相應尺度越小。L代表了圖像的尺度空間。

為高效的在尺度空間內檢測出穩定的特征點，Low使用尺度空間中DoG
(Difference -of-Gaussian)極值作為判斷依據。DoG算子定義為兩個不同尺度的高斯核的差分，是歸一化LoG (Laplacian-of-Gaussian)算子的近似。設k為兩相鄰尺度間的比例因子，則DoG算子定義如下：

選擇DoG算子作為檢測函數有一定的原因。首先，DoG算子計算簡單，只需要將兩個高斯平滑后的圖像L相減即能得到，執行效率較高；其次，DoG算子檢測出的特征點穩定性較好，與LoG檢測效果相近(Mikolajczyk 2002)。

Lowe采用的構造方式如圖1，其建立高斯圖像（圖中左列）與DoG（圖中右列）兩個金字塔。高斯圖像金字塔分為多組，每組間又分為多層。一組中的多層間不同的是尺度，相鄰層間尺度相差一個比例因子k。為在S個尺度間隔內變化尺度因子，如使σ加倍，則k應為。而為了在整個金字塔內獲取DoG極值，應在高斯金字塔中生成S+3層高斯平滑圖像。下一組的圖像的最底層由上一組中尺度為2σ的圖像進行因子為2的降采樣得到，其中σ為上一組中最底層圖像的尺度因子。DoG金字塔由相鄰的高斯圖像金字塔相減得到。

圖1 高斯圖像金字塔（S=2）與DoG金字塔

金字塔中每個高斯圖像的σ為：

其中為基礎尺度因子；o, s分別為圖像所在的圖像組坐標、組內層坐標，，，（實際應為，為在整個金字塔內獲取DoG極值，有S+3層高斯平滑圖像）；是第一個金字塔組的坐標，通常取0或者-1，當設為-1的時候，則圖像在計算高斯尺度空間前先擴大一倍。在Lowe的算法實現中以上參數分別取值如下：，，。

另外，空間坐標x是組坐標o的函數。設第o組內的空間坐標，則有：

其中是第o組中圖像的分辨率。設為第0組中的圖像分辨率，則其他組的分辨率為：

金字塔構造完后開始檢測DoG局部極值。其中每個像素需要跟同一尺度的周圍鄰域8個像素和相鄰尺度對應位置的周圍鄰域9*2個像素總共26個像素進行比較，如圖2。僅當被檢測點的DoG值大于此26個像素點或小于此26個像素點時才將該點判定為極值點并保存以進行后續計算。

圖2 DoG空間局部極值檢測

2.2關鍵點位置及尺度確定

通過擬和三維二次函數以精確確定關鍵點的位置和尺度（如圖3），同時去除低對比度的關鍵點。其中Lowe使用了DoG函數的泰勒公式展開的方法(Brown and Lowe, 2002)。

圖 3 精確確定關鍵點位置和尺度

去除不穩定的邊緣響應點，以增強匹配穩定性、提高抗噪聲能力。其使用的邊緣相應檢測算子為：

H為Hessian矩陣。Lowe在實現時取r=10。

2.3關鍵點方向確定

通過確定關鍵點的方向，可以使特征描述符以與方向相關的方式構造，從而使算子具有旋轉不變性。關鍵點的方向利用其鄰域像素的梯度分布特性確定。對每個高斯圖像，每個點的梯度的模與方向可以通過如下公式計算得到：

其中L所用尺度為關鍵點所在尺度。

對每個關鍵點，在以其為中心的鄰域窗口內利用直方圖的方式統計鄰域像素的梯度分布。此直方圖有36個柱，每柱10度，共360度。每個加入直方圖的鄰域像素樣本的權重由該像素的梯度模與高斯權重確定。此高斯窗的σ為關鍵點的尺度的1.5倍，加入高斯窗的目的是增強離關鍵點近的鄰域點對關鍵點的影響。

直方圖的峰值反映了關鍵點所處鄰域梯度的主方向。完成直方圖統計后，找到直方圖的最高峰值以確定關鍵點的方向。關鍵點的方向可以由離最高峰值最近的三個柱值通過拋物線插值精確得到。如圖4。

圖4 由梯度方向直方圖確定主梯度方向

在梯度方向直方圖中，當存在一個大于等于主峰值80%能量的峰值時，則添加一個新關鍵點，此關鍵點的坐標、尺度與當前關鍵點相同，但方向為由此峰值確定的方向。因此一個關鍵點可能產生多個坐標、尺度相同，方向不同的關鍵點。這樣做的目的是增強匹配的魯棒性。

至此，特征點檢測完畢，特征描述前的準備工作已經完成。每個關鍵點含有三個信息：坐標、尺度、方向。

2.3特征向量生成

設特征點的方向是θ，則先將特征點的鄰域旋轉-θ角度，這樣保證了旋轉不變性。然后將鄰域劃分為4×4=16塊,對每一塊利用特征點方向確定時采用的方法統計一個梯度直方圖，每個直方圖有8個柱，如圖5。這樣得到一個4×4x8=128維的特征向量。此時SIFT特征向量已經去除了尺度變化、旋轉等幾何變形因素的影響。

圖5 特征點的特征向量構造

最后要對特征向量進行處理以使其適應光照變化。首先要對特征向量進行歸一化。圖像發生對比度變化表現為每個像素點的值以及該點梯度方向的模均變為原來的常數倍，因此對特征向量進行歸一化能消除圖像對比度變化的影響。光照強度變化理論上不會對特征向量產生影響，因為光照強度變化表現為每個像素點的值增加了一個常數，因此像素點間的差值沒有發生改變，梯度值即沒有發生變化。至此特征向量已對光照的仿射變化具有了不變性。然而非線性的光照變化也可能發生，此時對像素點梯度方向產生影響相對較小，而對梯度的模產生較大影響。為了減小值較大的梯度的模的影響，我們可以設定一個閾值，使特征向量中的128項均小于等于該閾值，最后再對特征向量進行一次歸一化即可。Lowe算法中設定此閾值為0.2。

2.4特征點匹配

當兩幅圖像的SIFT特征向量生成后，下一步將采用關鍵點特征向量的歐式距離來作為兩幅圖像中關鍵點的相似性判定度量。

然而由于遮擋等原因，匹配可能出現錯配的情況，需要采取一些措施降低錯配率。為每對匹配特征點的特征向量歐式距離加閾值的方法并不合適，因為特征點可能有較強的獨特性，其匹配點對特征向量的歐式距離較大是正常的。一種比較有效的方法是在匹配時比較與關鍵點的特征向量最近的和次近的關鍵點。取圖像1中的某個關鍵點，并找出其與圖像2中歐式距離最近的前兩個關鍵點，在這兩個關鍵點中，如果最近的距離除以次近的距離少于某個比例閾值，則接受這一對匹配點，如下式子：

降低這個比例閾值，SIFT匹配點數目會減少，但更加穩定。Lowe在實現過程中取r=0.8，此時雖然會去掉約5%的正確匹配，但同時會去掉約90%的錯誤匹配。

轉自：http://bubblexc.com/y2011/163/

SIFT是我接觸最早的圖像局部特征描述子之一，其實最初，始終覺得局部特征描述子是些非常玄虛的東西。對于SIFT，這種感覺更是尤為強烈，“尺度空間”“拉普拉斯高斯算子（LoG）”“高斯差分金字塔”，一系列讓人頭痛的概念。不過，反反復復看了幾次，漸漸也就有了感覺，在此總結一下。

物體識別的核心問題是將同一目標在不同時間、不同分辨率、不同光照、不同位姿情況下所成的像相相匹配。而為了進行匹配，我們首先要合理的表示圖像。由于目標的自身狀態、場景所處的環境的影響，同一類物體在不同的圖像中所成的像往往會差別很大，但即使這樣，人們所能通過同一物體的一些局部共性來識別出物體（正如我們能將不同國家民族的人區分出來）。所謂局部特征描述子就是用來刻畫圖像中的這些局部共性的，而我們也可以將一幅圖像映射（變換）為一個局部特征的集合。理想的局部特征應具有平移、縮放、旋轉不變性，同時對光照變化、仿射及投影影響也應有很好的魯棒性。傳統的局部特征往往是直接提取角點或邊緣，對環境的適應能力較差。1999年British Columbia大學?David G.Lowe(http://www.cs.ubc.ca/~lowe/)?教授總結了現有的基于不變量技術的特征檢測方法，并正式提出了一種基于尺度空間的、對圖像縮放、旋轉甚至仿射變換保持不變性的圖像局部特征描述算子－SIFT（尺度不變特征變換），這種算法在2004年被加以完善。

SIFT算法的實質可以歸為在不同尺度空間上查找關鍵點（特征點）的問題。所謂關鍵點，就是一些十分突出的點，這些點不會因光照條件的改變而消失，比如角點、邊緣點、暗區域的亮點以及亮區域的暗點，既然兩幅圖像中有相同的景物，那么使用某種方法分別提取各自的穩定點，這些點之間就會有相互對應的匹配點。而在SIFT中，關鍵點是在不同尺度空間的圖像下檢測出的具有方向信息的局部極值點。涉及到的最重要的兩步是：1.構建尺度空間 2.關鍵點檢測

·??????構建尺度空間

先來談談尺度的問題。我們要精確表示的物體都是通過一定的尺度來反映的。現實世界的物體也總是通過不同尺度的觀察而得到不同的變化。比如說，對同一物體拍照，我們拍攝了一副近景，一副遠景，雖然兩幅圖片中都有這個物體，但這個物體確是處于兩個不同的尺度。SIFT特征具有尺度不變性，就是說即使同一物體處于兩個不同的尺度的圖像中，我們仍可以通過提取圖像的SIFT特征匹配成功。

圖像的尺度有多種表示方法（金字塔、八叉樹等等），在SIFT中Lowe教授采用了尺度空間理論。其主要思想是通過對原始圖像進行尺度變換，獲得圖像多尺度下的尺度空間表示序列，并檢測這個序列中的關鍵點。這樣圖片就被映射為多個尺度上的關鍵點信息，盡管兩幅圖片是處于不同的尺度，但卻可以提取出在尺度變換中沒有改變的關鍵點，從而進行關鍵點匹配，進而識別出物體。

實際上，在尺度空間理論中，是通過對圖像進行模糊來模擬多尺度下的圖像。直觀上，圖像的模糊程度逐漸變大，模擬了人在距離目標由近到遠時目標在視網膜上的形成過程。文獻《Scale-space theory: A basic tool for analysing structures at differentscales》(http://www.csc.kth.se/~tony/abstracts/Lin94-SI-abstract.html)證明，高斯核是唯一可以產生多尺度空間的核（其它核會對圖像造成模糊之外的其它影響）。一個圖像的尺度空間，?L(x,y,σ)?（σ?可以代表尺度的大小），定義為原始圖像?I(x,y)?與一個可變尺度的2維高斯函數?G(x,y,σ)? 卷積運算。高斯函數：

G(x,y,σ)=

1/2πσ2e[?(x2+y2)/(2σ2)]

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

需要的注意的是，圖像的尺度是自然存在的，不是人為創造的！高斯卷積只是表現尺度空間的一種形式。（在SIFT的代碼中，進行高斯模糊時，用到了高斯模糊的“勾股定理”：例如，使用半徑分別為 6 和 8 的兩次高斯模糊變換得到的效果等同于一次半徑為 10 的高斯模糊效果）。

在SIFT中，構建了高斯金字塔（如圖1所示），即分為兩步：1）對圖像做高斯平滑 2）對圖像做降采樣（減小計算量）。一幅圖像可以產生幾組（octave）圖像，一組圖像包括幾層（interval）圖像。為了讓尺度體現出連續性，相鄰兩層圖像間的尺度為k倍的關系，同時相鄰兩組的同一層尺度為2倍的關系（在SIFT算法中，Lowe教授假設初始圖片已經是以一定?σ?模糊過得了）。

·??????關鍵點檢測

文獻《Scale-spacetheory: A basic tool for analysing structures at different scales》(http://www.csc.kth.se/~tony/abstracts/Lin94-SI-abstract.html)指出尺度規范化的LoG算子具有真正的尺度不變性。即我們可以在不同尺度的圖像（已經經過高斯卷積）上進行拉普拉斯運算（二階導數），并求極值點，從而求出關鍵點。但這樣做的運算量很大，于是SIFT中進行了近似處理：

?2G=?2G?x2+?2G?y2

LOG(x,y,σ)=σ2?2G≈Gauss(x,y,kσ)?Gauss(x,y,σ)σ2(k?1)

G(x,y,kσ)?G(x,y,σ)≈(k?1)σ2?2G

通過推導可以看出，LoG算子與高斯核函數的差有直接關系，由此引入一種新的算子DoG（Difference of Gaussians），即高斯差分算子：

D(x,y,σ)=[

G(x,y,kσ)?G(x,y,σ)]?I(x,y)=L(x,y,kσ)–L(x,y,σ)

???? 可以看出，LoG算子和DoG算子指相差常數系數，而這并不會改變極值點的位置。因此我們在DoG算子中求得極值點就是LoG算子的極值點，也正是我們需要的關鍵點。而DoG在計算上只需相鄰尺度高斯平滑后圖像相減，因此簡化了計算！

???? 對應DOG算子，我們要構建DOG金字塔

如下圖，我們可以通過高斯差分圖像看出圖像上的像素值變化情況。如果沒有變化，也就沒有特征。特征必須是變化盡可能多的點。本質上，DOG圖像描繪的是目標的輪廓。

??? 關鍵點是由DOG空間的局部極值點組成的。為了尋找DoG函數的極值點，每一個像素點要和它所有的相鄰點比較，看其是否比它的圖像域和尺度域的相鄰點大或者小。具體來說，中間的檢測點和它同尺度的8個相鄰點和上下相鄰尺度對應的9×2個點共26個點比較，以確保在尺度空間和二維圖像空間都檢測到極值點。

??? 至此就可以檢測出圖像中尺度不變的關鍵點，然后我們為關鍵點賦予梯度方向，并利用關鍵點的周圍的像素梯度方向直方圖生成SIFT特征描述子。具體過程可以參考以下資料

1、SIFT的matlab程序，非常詳細?http://www.vlfeat.org/~vedaldi/code/sift.html

2、SIFT tutorial?http://www.aishack.in/2010/05/sift-scale-invariant-feature-transform/

3、一個非常詳細ppt教程，可用作教學http://wenku.baidu.com/view/53021cf24693daef5ef73daf.html