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
論文詳細位址：lowe sift算法
算法主要分為4個步驟：
- scale-space extrema detection--尺度空間上的極值檢測
- keypoint localization--關鍵點的定位
- orientation assignment --為關鍵點标定方向
- keypoint descriptor--提取特征點描述符
$1. 尺度空間上的極值檢測
在介紹這一部分的時候，先引入幾個概念：
- 降采樣：對于一幅圖像而言的降采樣就是每隔幾行、幾列得到取一點，組成一個新的圖像。以比例因子為2的降采樣來說：就是対一幅圖像每隔一行一列取一點。
- 升采樣：其實一種插值，就是在一幅圖像裡利用相關的插值運算得到一幅大的圖像！比如比例因子為2的升采樣就是每個相鄰像素點種插值出一個像素（這裡包括X、Y兩個方向），最常用的插值方法有線性插值等。
- 圖像金字塔：由一個原始圖像經過降采樣得到一幅圖像，再對新的圖像做降采樣，重複多次構成的一組集合。以采樣因子2為例說明，如果形象的把這些圖像摞起來就想一個金字塔，每次之間長和寬大小恰好為2倍關系，故此得名。
- 高斯卷積：就是權函數為高斯函數的模闆進行卷積運算。通常做高斯卷積後的圖像會比原圖像平滑但也會模糊，是以又稱高斯模糊！
- 高斯金字塔：高斯金字塔裡有兩個概念：組（Octave）和層（Level或Interval），每組裡有若幹層！高斯金字塔的構造是這樣的，第一組的第一層為原圖像，然後将圖像做一次高斯平滑（高斯卷積、高斯模糊）高斯平滑裡有一個參數δ,在SIFT裡作者取1.6 。然後将δ乘一個比例系數k作為新的平滑因子來平滑第一組第二層得到第三層，重複若幹次，得到L層（L一般取5）他們分别對應的平滑參數為：0，δ，kδ，k2δ，k3δ。然後将最後一幅圖像做比例因子為2的降采樣得到第二組的第一層，然後對第二組的第一層做參數是δ的高斯平滑，對第二層做kδ的平滑得到第三層.....這裡一定注意：每組對應的平滑因子δ是一樣的,而不是像有的資料上說的持續遞增。這樣反複形成了O組L層的高斯金字塔。一般模糊的高斯模闆長寬都約為6δ（這裡δ為當次的平滑因子，就是可能是kδ，k2δ..）
- DoG（Difference of Gaussian）金字塔：是由高斯金字塔構造出來的，他的第一組第一層是由高斯金字塔的第一組第二層減第一組第一層，他的第一組第二層是由高斯金字塔的第一組第三層減第一組第二層得到。每組都這樣就生成了一個DoG金字塔。順便說一下，DoG金字塔每組圖像幾乎都是一片黑，但仔細看你能看出輪廓的。
圖像比對算法研究之sift算法
最後關于金字塔具體處理的說明：
1）在SIFT裡高斯金字塔的第一組第一層通常是由一個原圖像長寬擴大一倍開始的，這樣做是為了可以得到更多的特征點 ；
2）大家可以發現如果用每組5層的高斯金字塔構造一個DoG金字塔的的話，DoG的每組的層數是4 ；
3）對于DoG金字塔，特征點的搜尋從每組的二層到倒數第二層的（後面說明為什麼），是以如果DoG金字塔有效層數目為n的話，那麼DoG金字塔應該有n+2層，那麼對 應的高斯金字塔應該有n+3層 ；
4）高斯金字塔從第二組開始的每組第一層是由上一組的倒數第二層降采樣得到的，如下所示。
講了這麼多概念，現在正式開始講解如何在尺度空間裡尋找特征點啦。
由于圖像進行伸縮等變換後尺度空間發生變化，是以為了友善找出比對點，需要将圖像在不同的尺度空間裡進行平滑，并相減得到更多的邊緣等高頻資訊（特征點的集中 域）。高斯平滑并計算dog金字塔利用下面的3個計算公式：
至于為什麼用DOG算子來提取額特征點，而不是hessian或者其他角點方法比如Harris，是因為Mikolajczyk (2002)發現通過
計算出來的局部區域極大值和極小值與上述幾種角點相比能産生更加穩定的特征點。
但是上面的公式和DOG又有什麼關系呢？看下面的公式就知道了：
進一步得到=>
兩者之間隻是相差了（k-1）δ2 倍而已，不影響特征點的尋找。
還有一點需要說明的是，這裡不同的δ就是代表不同的尺度，0（本身），δ，kδ,等等... δ的值越大，意味着尺度空間越大。具體該怎麼了解尺度這個概念呢，就是需要描述的像素灰階分布越廣，尺度越廣，也就是說越模糊的圖像尺度也越大。舉個例子，有兩個灰階值分别為0和1，模糊後變為0.4和0.6，要表示這兩個灰階值需要更多的參數，尺度變大。更簡單的說尺度就是頻率，高斯模糊越明顯，尺度越大，因為這時圖像是低頻的。
剩下的隻需要在DOG金字塔裡尋找3X3X3鄰域的極值即為我們所要尋找的feature points.如下圖所示，
$2. 關鍵點的精确定位
通過拟和三維二次函數以精确确定關鍵點的位置和尺度（達到亞像素精度），同時去除低對比度的關鍵點和不穩定的邊緣響應點(因為DoG算子會産生較強的邊緣響應)，以增強
比對穩定性、提高抗噪聲能力。
①空間尺度函數泰勒展開式如（4 ）所示:
對（4）求導,并令其為0,得到精确的位置（5)。
②在已經檢測到的特征點中,要去掉低對比度的特征點和不穩定的邊緣響應點。去除低對比度的點：把公式(5)代入公式(4)，可得（6）。
若（6）的值大于0.03 ，該特征點就保留下來，否則丢棄。
③邊緣響應的去除
一個定義不好的高斯差分算子的極值在橫跨邊緣的地方有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。主曲率通過一個2×2 的Hessian矩陣H求出:
導數由采樣點相鄰差估計得到。D的主曲率和H的特征值成正比，令α為最大特征值，β為最小的特征值，則
令α=rβ 則：
(r + 1)2/r的值在兩個特征值相等的時候最小，随着r的增大而增大，是以，為了檢測主曲率是否在某域值r下，隻需檢測
。
在Lowe的文章中，取r＝10。
$3. 關鍵點方向配置設定
利用關鍵點鄰域像素的梯度方向分布特性為每個關鍵點指定方向參數，使算子具備旋轉不變性。
梯度大小和方向計算公式如下：
（7）
orientation histogram的生成，将0~360度分到36個區間中，每個區間的高度計算如下：∑m(xi,yi)*g(x0,y0,1.5δ) 其中δ為目前的尺度，（x0,y0）為目前特征點的坐标而g(x0,y0,1.5δ)則是高斯濾波系數，計算公式➹（2）。
主方向定義為擁有最高峰hm的那個區間，而其他區間高度為0.8*hm之上的區間方向可以認為是該特征點的輔方向，這樣就增強了比對的魯棒性。
這樣，每個關鍵點key points就有三個資訊：位置（x0,y0）、所處尺度δ、方向。
若表示出來，效果如下：
圖1
$4. 提取特征描述子
圖2
- 首先将坐标軸旋轉為關鍵點的方向，以確定旋轉不變性；
- 為了友善起見，在$3部分利用公式7計算梯度時，應該計算全體像素點的梯度方向及大小；
- lowe建議選取16X16鄰域，然後将這個大區域分為16個4X4區域，再分别對每個區域中16個像素點的梯度大小乘上高斯模闆系數（此時的δ為0.5*4=2）；
- 将16個機關方向向量按照正常的8方向分布，并乘上上一步計算的幅值疊加起來，得到類似圖2右邊的效果。
最後，一共有4X4X8=128維向量來表征這個特征點。
此時SIFT特征向量已經去除了尺度變化、旋轉等幾何變形因素的影響，再繼續将特征向量的長度歸一化，則可以進一步去除光照變化的影響。
$5. 後續比對工作
當兩幅圖像的SIFT特征向量生成後，下一步我們采用關鍵點特征向量的歐式距離來作為兩幅圖像中關鍵點的相似性判定度量。取圖像1中的某個關鍵點，并找出其與圖像2中歐式距離最近的前兩個關鍵點，在這兩個關鍵點中，如果最近的距離除以次近的距離少于某個比例門檻值，則接受這一對比對點。降低這個比例門檻值，SIFT比對點數目會減少，但更加穩定。為了排除因為圖像遮擋和背景混亂而産生的無比對關系的關鍵點。Lowe提出了比較最近鄰距離與次近鄰距離的方法,距離比率ratio小于某個門檻值的認為是正确比對。因為對于錯誤比對,由于特征空間的高維性,相似的距離可能有大量其他的錯誤比對,進而它的ratio值比較高。Lowe推薦ratio的門檻值為0.8。但作者對大量任意存在尺度、旋轉和亮度變化的兩幅圖檔進行比對，結果表明ratio取值在0. 4~0. 6之間最佳，小于0. 4的很少有比對點，大于0. 6的則存在大量錯誤比對點。作者建議ratio的取值原則如下:
ratio=0. 4 對于準确度要求高的比對；
ratio=0. 6 對于比對點數目要求比較多的比對；
ratio=0. 5 一般情況下。
也可按如下原則:當最近鄰距離<200時ratio=0. 6，反之ratio=0. 4。ratio的取值政策能排分錯誤比對點。