用于圖像搜索和匹配的SIFT算法介紹

SIFT算法由D.G.Lowe 1999年提出，2004年完善總結，論文發表在2004年的IJCV上：

David G. Lowe, "Distinctive image features from scale-invariant keypoints," International Journal of Computer Vision, 60, 2 (2004), pp. 91-110

論文的原文可見：

http://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf

后來Y.Ke將其描述子部分用PCA代替直方圖的方式，對其進行改進。
SIFT方法一經推出就在圖像處理界引起巨大反響，其方法效果良好、實現便捷，很快風靡世界。很多圖像檢測、識別的應用里都能找到sift方法的身影

SIFT算法是一種提取局部特征的算法，在尺度空間尋找極值點，提取位置，尺度，旋轉不變量。算法的主要特點為：

a) SIFT特征是圖像的局部特征，其對旋轉、尺度縮放、亮度變化保持不變性，對視角變化、仿射變換、噪聲也保持一定程度的穩定性。
b) 獨特性(Distinctiveness)好，信息量豐富，適用于在海量特征數據庫中進行快速、準確的匹配[23]。
c) 多量性，即使少數的幾個物體也可以產生大量SIFT特征向量。
d) 高速性，經優化的SIFT匹配算法甚至可以達到實時的要求。
e) 可擴展性，可以很方便的與其他形式的特征向量進行聯合。

SIFT算法主要步驟：
1） 檢測尺度空間極值點
2） 精確定位極值點
3） 為每個關鍵點指定方向參數
4） 關鍵點描述子的生成

SIFT算法詳細

尺度空間理論目的是模擬圖像數據的多尺度特征。  高斯卷積核是實現尺度變換的唯一線性核，于是一副二維圖像的尺度空間定義為：
                     L(x,y,e) = G(x,y,e)*I(x,y)
其中G(x,y,e)是尺度可變高斯函數， 

                     G(x,y,e) = [1/2*pi*e²] * exp[ -(x² + y²)/2e²]

（x，y）是空間坐標， e是尺度坐標。

為了有效的在尺度空間檢測到穩定的關鍵點，提出了高斯差分尺度空間（DOG scale-space）。利用不同尺度的高斯差分核與圖像卷積生成。
                     D(x,y,e) = ((G(x,y,ke) - G(x,y,e)) * I(x,y) = L(x,y,ke) - L(x,y,e)
DOG算子計算簡單，是尺度歸一化的LoG算子的近似。

Gaussian卷積是有尺寸大小的，使用同一尺寸的濾波器對兩幅包含有不同尺寸的同一物體的圖像求局部最值將有可能出現一方求得最值而另一方卻沒有的情況，但是容易知道假如物體的尺寸都一致的話它們的局部最值將會相 同。SIFT的精妙之處在于采用圖像金字塔的方法解決這一問題，我們可以把兩幅圖像想象成是連續的，分別以它們作為底面作四棱錐，就像金字塔，那么每一個 截面與原圖像相似，那么兩個金字塔中必然會有包含大小一致的物體的無窮個截面，但應用只能是離散的，所以我們只能構造有限層，層數越多當然越好，但處理時 間會相應增加，層數太少不行，因為向下采樣的截面中可能找不到尺寸大小一致的兩個物體的圖像。有了圖像金字塔就可以對每一層求出局部最值，但是這樣的穩定 點數目將會十分可觀，所以需要使用某種方法抑制去除一部分點，但又使得同一尺度下的穩定點得以保存
圖像金字塔的構建：圖像金字塔共O組，每組有S層，下一組的圖像由上一組圖像降采樣得到。
 
圖1 Two octaves of a Gaussian scale-space image pyramid with s =2 intervals. The first image in the second octave is created by down sampling the second to last image in the previous
 
圖2 The difference of two adjacent intervals in the Gaussian scale-space pyramid create an interval in the difference-of-Gaussian pyramid (shown in green).

空間極值點檢測
為了尋找尺度空間的極值點，每一個采樣點要和它所有的相鄰點比較，看其是否比它的圖像域和尺度域的相鄰點大或者小。如圖3所示，中間的檢測點和它同尺度的8個相鄰點和上下相鄰尺度對應的9×2個點共26個點比較，以確保在尺度空間和二維圖像空間都檢測到極值點。

構建尺度空間需確定的參數
   e －尺度空間坐標
   O －octave坐標
   S － sub-level 坐標
注：octaves 的索引可能是負的。第一組索引常常設為0或者-1,當設為-1的時候，圖像在計算高斯尺度空間前先擴大一倍。
空間坐標x是組octave的函數，設 是0組的空間坐標，注：在Lowe的文章中，Lowe使用了如下的參數：
在組o=-1，圖像用雙線性插值擴大一倍（對于擴大的圖像 ）。

精確確定極值點位置
   通過擬和三維二次函數以精確確定關鍵點的位置和尺度（達到亞像素精度），同時去除低對比度的關鍵點和不穩定的邊緣響應點(因為DoG算子會產生較強的邊緣響應)，以增強匹配穩定性、提高抗噪聲能力。
 
邊緣響應的去除
一個定義不好的高斯差分算子的極值在橫跨邊緣的地方有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。主曲率通過一個2x2 的Hessian矩陣H求出:
導數由采樣點相鄰差估計得到。
D的主曲率和H的特征值成正比，令為最大特征值

關鍵點方向分配
   利用關鍵點鄰域像素的梯度方向分布特性為每個關鍵點指定方向參數，使算子具備旋轉不變性。
在實際計算時，我們在以關鍵點為中心的鄰域窗口內采樣，并用直方圖統計鄰域像素的梯度方向。梯度直方圖的范圍是0～360度，其中每10度一個柱，總共36個柱。直方圖的峰值則代表了該關鍵點處鄰域梯度的主方向，即作為該關鍵點的方向。圖4是采用7個柱時使用梯度直方圖為關鍵點確定主方向的示例。 
 
圖4 由梯度方向直方圖確定主梯度方向
在梯度方向直方圖中，當存在另一個相當于主峰值80%能量的峰值時，則將這個方向認為是該關鍵點的輔方向。一個關鍵點可能會被指定具有多個方向（一個主方向，一個以上輔方向），這可以增強匹配的魯棒性[53]。
至此，圖像的關鍵點已檢測完畢，每個關鍵點有三個信息：位置、所處尺度、方向。由此可以確定一個SIFT特征區域（在實驗章節用橢圓或箭頭表示）。 陳運文

特征點描述子生成
 
由關鍵點鄰域梯度信息生成特征向量
接下來以關鍵點為中心取8×8的窗口。圖5-4左部分的中央黑點為當前關鍵點的位置，每個小格代表關鍵點鄰域所在尺度空間的一個像素，箭頭方向代表該像素的梯度方向，箭頭長度代表梯度模值，圖中藍色的圈代表高斯加權的范圍（越靠近關鍵點的像素梯度方向信息貢獻越大）。然后在每4×4的小塊上計算8個方向的梯度方向直方圖，繪制每個梯度方向的累加值，即可形成一個種子點，如圖5右部分所示。此圖中一個關鍵點由2×2共4個種子點組成，每個種子點有8個方向向量信息。這種鄰域方向性信息聯合的思想增強了算法抗噪聲的能力，同時對于含有定位誤差的特征匹配也提供了較好的容錯性。
實際計算過程中，為了增強匹配的穩健性，Lowe建議對每個關鍵點使用4×4共16個種子點來描述，這樣對于一個關鍵點就可以產生128個數據，即最終形成128維的SIFT特征向量。此時SIFT特征向量已經去除了尺度變化、旋轉等幾何變形因素的影響，再繼續將特征向量的長度歸一化，則可以進一步去除光照變化的影響。
當兩幅圖像的SIFT特征向量生成后，下一步我們采用關鍵點特征向量的歐式距離來作為兩幅圖像中關鍵點的相似性判定度量。取圖像1中的某個關鍵點，并找出其與圖像2中歐式距離最近的前兩個關鍵點，在這兩個關鍵點中，如果最近的距離除以次近的距離少于某個比例閾值，則接受這一對匹配點。降低這個比例閾值，SIFT匹配點數目會減少，但更加穩定。

SIFT算法的實際匹配效果如下：

轉自：http://blog.csdn.net/cserchen/article/details/5606859