SIFT（Scale-invariant feature transform）是一種檢測局部特征的算法，該算法通過求一幅圖中的特征點（interest points,or corner points）及其有關scale 和 orientation 的描述子得到特征并進行圖像特征點比對，獲得了良好效果，詳細解析如下：
一、SIFT算法綜述
特點：
1. SIFT特征是圖像的局部特征，其對旋轉、尺度縮放、亮度變化保持不變性，對視角變化、仿射變換、噪聲也保持一定程度的穩定性；
2. 獨特性（Distinctiveness）好，資訊量豐富，适用于在海量特征資料庫中進行快速、準确的比對；
3. 多量性，即使少數的幾個物體也可以産生大量的SIFT特征向量；
4. 高速性，經優化的SIFT比對算法甚至可以達到實時的要求；
5. 可擴充性，可以很友善的與其他形式的特征向量進行聯合。
應用場景：
目标的自身狀态、場景所處的環境和成像器材的成像特性等因素影響圖像配準/目辨別别跟蹤的性能。而SIFT算法在一定程度上可解決：
1. 目标的旋轉、縮放、平移（RST）
2. 圖像仿射/投影變換（視點viewpoint）
3. 光照影響（illumination）
4. 目标遮擋（occlusion）
5. 雜物場景（clutter）
6. 噪聲
二、SIFT算法實作步驟
2.1 建構尺度空間
要實作圖像比對，我們想在構成圖像的所有點中通過某種方法選取出一些具有代表性的點，重要的是這些特殊點在圖像經過伸縮、旋轉、疊加噪聲和其他一些變化後仍能被提取出來——即具有不變性，這樣我們就可以利用這些具有不變性的特殊點來進行圖像的比對。Lowe提出了一種尋找特殊點的方法，用這種方法找到的點對于圖像的尺度變化具有不變性。
最早的圖像比對使用的是角點檢測（corner detector）。應該說，圖像中物體的邊緣是一個比較好的特征。比較常用的邊緣檢測方法有一階導數邊緣檢測、二階導數邊緣檢測。拉普拉斯邊緣檢測就屬于二階導數邊緣檢測。拉普拉斯算子為
Marr和Hildrith提出了高斯拉普拉斯邊緣檢測算子（LOG算子，表示為
），在拉普拉斯操作之前先進行高斯平滑操作，以抑制高頻噪聲。高斯函數表示為G(x,y,σ)，與原始圖像做卷積後，相當于對圖像進行了低通濾波，且σ越大，則濾波器截止頻率越低，圖像也因失去更多的高頻資訊而更模糊。Lindeberg又提出将上述結果乘以系數
後可獲得尺度不變性，即尺度歸一化的高斯拉普拉斯算子
。
首先是用高斯差分(DOG)來近似
。Lowe說可以參考熱擴散方程得到，這個公式應該比較關鍵，但我尚不清楚為何
左邊的高斯偏導數可以用差分來近似：
其中k趨近于1就可以取等号了。是以：
從中可以看出，高斯差分與尺度歸一化的高斯拉普拉斯算子
僅相差一個比例因子(k-1)。如果我們取k為定值，則在高斯差分中找到的極值點位置大緻相當于在
中的位置。
高斯金字塔有多組，每組又有多層。一組中的多個層之間的尺度是不一樣的（也就是使用的高斯參數σσ是不同的），相鄰兩層之間的尺度相差一個比例因子k。如果每組有S層，則
。上一組圖像的最底層圖像是由下一組中尺度為2σ的圖像進行因子為2的降采樣得到的（高斯金字塔先從底層建立）。高斯金字塔建構完成後，将相鄰的高斯金字塔相減就得到了DoG金字塔。
高斯金字塔的組數一般是:
o表示高斯金字塔的層數，m，n分别是圖像的行和列。減去的系數a可以在0−
之間的任意值，和具體需要的金字塔的頂層圖像的大小有關。
高斯模糊參數σ（尺度空間），可由下面關系式得到:
其中i為所在的組，S為所在的組的層數。
下一個減少計算量的方法是分組（Octave），即通過縮小圖檔尺寸來減少卷積計算。
圖1：分組高斯差分
2.2 DOG極值點檢測
關鍵點是由DOG空間的局部極值點組成的，關鍵點的初步探查是通過同一組内各DoG相鄰兩層圖像之間比較完成的。為了尋找DoG函數的極值點，每一個像素點要和它所有的相鄰共26個點比較，看其是否比它的圖像域和尺度域的相鄰點大或者小。 如果令
中的σ不斷變大（為了計算機實作，隻能取離散的σ值，對應于圖1的Scale），就可以得到很多輸出圖像，這樣局部極值點的尋找就擴充至三維空間(x,y,σ)。正如圖2所示，每個像素點X需要與上下及周圍共26個鄰近點O比較來确定局部最大最小極值。
圖2：極值點檢測
圖3 不同尺度不同層級檢測示意圖
假設s=3，也就是每個塔裡有3層，則
，那麼按照上圖可得Gauss Space和DoG space 分别有3個（s）和2個（s-1）分量，在DoG space中，1st-octave兩項分别是σ,kσ; 2nd-octave兩項分别是2σ,2kσ;由于無法比較極值，我們必須在高斯空間繼續添加高斯模糊項，使得形成σ,kσ,
σ,
σ,
σ這樣就可以選擇DoG space中的中間三項kσ,
σ,
σ（隻有左右都有才能有極值），那麼下一octave中（由上一層降采樣獲得）所得三項即為2kσ,2
σ,2
σ，其首項2kσ=
。剛好與上一octave末項
σ=
尺度變化連續起來，是以每次要在Gaussian space添加3項，每組（塔）共S+3層圖像，相應的DoG金字塔有S+2層圖像。
2.3 關鍵點定位
離散空間的極值點并不是真正的極值點，圖4顯示了二維函數離散空間得到的極值點與連續空間極值點的差别。利用已知的離散空間點插值得到的連續空間極值點的方法叫做子像素插值（Sub-pixel Interpolation）。
圖4 離散空間與連續空間的極值點差異
為了提高關鍵點的穩定性，需要對尺度空間DoG函數進行曲線拟合。利用DoG函數在尺度空間的Taylor展開式(拟合函數)為：
其中，求導并讓方程等于零，可以得到極值點的偏移量為：
對應極值點，方程的值為：
其中,代表相對插值中心的偏移量，當它在任一次元上的偏移量大于0.5時（即x或y或），意味着插值中心已經偏移到它的鄰近點上，是以必須改變目前關鍵點的位置。同時在新的位置上反複插值直到收斂；也有可能超出所設定的疊代次數或者超出圖像邊界的範圍，此時這樣的點應該删除，在Lowe中進行了5次疊代。另外，過小的點易受噪聲的幹擾而變得不穩定，是以将小于某個經驗值(Lowe論文中使用0.03，Rob Hess等人實作時使用0.04/S)的極值點删除。同時，在此過程中擷取特征點的精确位置(原位置加上拟合的偏移量)以及尺度。
2.4 消除邊緣影響
一個定義不好的高斯差分算子的極值在橫跨邊緣的地方有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。
DOG算子會産生較強的邊緣響應，需要剔除不穩定的邊緣響應點。擷取特征點處的Hessian矩陣，主曲率通過一個2x2 的Hessian矩陣H求出：
H的特征值α和β代表x和y方向的梯度，
表示矩陣H對角線元素之和，表示矩陣H的行列式。假設是α較大的特征值，而是β較小的特征值，令
，則
D的主曲率和H的特征值成正比，令為α最大特征值，β為最小的特征值，則公式
的值在兩個特征值相等時最小，随着的增大而增大。值越大，說明兩個特征值的比值越大，即在某一個方向的梯度值越大，而在另一個方向的梯度值越小，而邊緣恰恰就是這種情況。是以為了剔除邊緣響應點，需要讓該比值小于一定的門檻值，是以，為了檢測主曲率是否在某域值r下，隻需檢測如下：
上式成立時将關鍵點保留，反之剔除。
2.5 尋找關鍵點的主方向
經過上面的步驟已經找到了在不同尺度下都存在的特征點，為了實作圖像旋轉不變性，需要給特征點的方向進行指派。利用特征點鄰域像素的梯度分布特性來确定其方向參數，再利用圖像的梯度直方圖求取關鍵點局部結構的穩定方向找到了特征點，也就可以得到該特征點的尺度σ，也就可以得到特征點所在的尺度圖像：
計算以特征點為中心、以3×1.5σ為半徑的區域圖像的幅角和幅值，每個點L(x,y)的梯度的模m(x,y)以及方向θ(x,y)可通過下面公司求得：
計算得到梯度方向後，就要使用直方圖統計特征點鄰域内像素對應的梯度方向和幅值。梯度方向的直方圖的橫軸是梯度方向的角度（梯度方向的範圍是0到360度，直方圖每36度一個柱共10個柱，或者沒45度一個柱共8個柱），縱軸是梯度方向對應梯度幅值的累加，在直方圖的峰值就是特征點的主方向。在Lowe的論文還提到了使用高斯函數對直方圖進行平滑以增強特征點近的鄰域點對關鍵點方向的作用，并減少突變的影響。為了得到更精确的方向，通常還可以對離散的梯度直方圖進行插值拟合。具體而言，關鍵點的方向可以由和主峰值最近的三個柱值通過抛物線插值得到。在梯度直方圖中，當存在一個相當于主峰值80%能量的柱值時，則可以将這個方向認為是該特征點輔助方向。是以，一個特征點可能檢測到多個方向（也可以了解為，一個特征點可能産生多個坐标、尺度相同，但是方向不同的特征點）。Lowe在論文中指出
15%的關鍵點具有多方向，而且這些點對比對的穩定性很關鍵。
得到特征點的主方向後，對于每個特征點可以得到三個資訊(x,y,σ,θ)(x,y,σ,θ)，即位置、尺度和方向。由此可以确定一個SIFT特征區域，一個SIFT特征區域由三個值表示，中心表示特征點位置，半徑表示關鍵點的尺度，箭頭表示主方向。具有多個方向的關鍵點可以被複制成多份，然後将方向值分别賦給複制後的特征點，一個特征點就産生了多個坐标、尺度相等，但是方向不同的特征點。
2.6 生成特征描述
通過以上的步驟已經找到了SIFT特征點位置、尺度和方向資訊，下面就需要使用一組向量來描述關鍵點也就是生成特征點描述子，這個描述符不隻包含特征點，也含有特征點周圍對其有貢獻的像素點。描述子應具有較高的獨立性，以保證比對率。
特征描述符的生成大緻有三個步驟：
- 校正旋轉主方向，確定旋轉不變性。
- 生成描述子，最終形成一個128維的特征向量
- 歸一化處理，将特征向量長度進行歸一化處理，進一步去除光照的影響。
為了保證特征矢量的旋轉不變性，要以特征點為中心，在附近鄰域内将坐标軸旋轉θ（特征點的主方向）角度，即将坐标軸旋轉為特征點的主方向。旋轉後鄰域内像素的新坐标為：
旋轉後以主方向為中心取 8×8的視窗。下圖所示，左圖的中央為目前關鍵點的位置，每個小格代表為關鍵點鄰域所在尺度空間的一個像素，求取每個像素的梯度幅值與梯度方向，箭頭方向代表該像素的梯度方向，長度代表梯度幅值，然後利用高斯視窗對其進行權重運算。最後在每個4×4的小塊上繪制8個方向的梯度直方圖，計算每個梯度方向的累加值，即可形成一個種子點，如右圖所示。每個特征點由4個種子點組成，每個種子點有8個方向的向量資訊。這種鄰域方向性資訊聯合增強了算法的抗噪聲能力，同時對于含有定位誤差的特征比對也提供了比較理性的容錯性。
與求主方向不同，此時每個種子區域的梯度直方圖在0-360之間劃分為8個方向區間，每個區間為45度，即每個種子點有8個方向的梯度強度資訊。在實際的計算過程中，為了增強比對的穩健性，Lowe建議對每個關鍵點使用4×44×4共16個種子點來描述，這樣一個關鍵點就可以産生128維的SIFT特征向量。
通過對特征點周圍的像素進行分塊，計算塊内梯度直方圖，生成具有獨特性的向量，這個向量是該區域圖像資訊的一種抽象，具有唯一性。
參考文獻
1、sift算法詳解及應用（課件）。（本文檔簡明扼要的簡述了SIFT算法和圖像比對以及比對修正。圖文并茂，一覽全貌）
http://wenku.baidu.com/view/87270d2c2af90242a895e52e.html?re=view
2、SIFT算法詳解（sift操作過程理論通俗，尤其是高階泰勒展開式及高階導數分析的很好，對了解亞像素定位拟合中的圖像具體程式設計操作很有用）
http://blog.csdn.net/zddblog/article/details/7521424
3、SIFT特征分析與源碼解讀（1模拟金字塔的過程解釋的很詳細，帶有動畫模拟；2 在尋找特征點進行亞像素定位拟合中的圖像很形象）
http://blog.csdn.net/xw20084898/article/details/16832755
4、【OpenCV】SIFT原理與源碼分析：關鍵點描述（對關鍵點描述子區域的取舍講解的很詳細）
http://blog.csdn.net/xiaowei_cqu/article/details/8113565
5、【OpenCV】SIFT原理與源碼分析（對sift 算法采用分部分叙述且帶有源碼分析說明）
http://blog.csdn.net/xiaowei_cqu/article/details/8069548
6、opencv2.4.9sift源碼分析(1趙春江的這篇文章是我目前看到分析sift算法比較全面的；2尤其給出了使用三維直方圖來分析三線性插值，對了解描述子的生成作用很大；3 給出了源碼分析和示範結果）
http://wenku.baidu.com/view/d7edd2464b73f242336c5ffa.html
http://download.csdn.net/detail/zhaocj/8294793
7、九之再續：教你一步一步用c語言實作sift算法、下
（1算法中尋找主方向使用的抛物線插值拟合方法；2 描述子三次插值）
http://blog.csdn.net/v_JULY_v/article/details/6246213
8、RobHess的SIFT源碼分析：綜述(各個子程式詳解及分析很細緻，一概全貌）
http://blog.csdn.net/masibuaa/article/details/9191309
9、特征點檢測學習_1(sift算法)（1這篇文章沒有太多理論分析，但結合QT和OpenCV做出了生動的sift算法比對示範，有圖很直覺生動呀，用程式配圖一目了然；2 簡述對robhess 的c版本sift代碼在c++中的使用注意問題 ）
http://www.cnblogs.com/tornadomeet/archive/2012/08/16/2643168.html
10、OpenCV 中c版本sift源代碼網址
http://blogs.oregonstate.edu/hess/code/sift/
11、【特征比對】SIFT原理與C源碼剖析（這個也不錯，圖文并茂，還帶有 源碼分析，總體來說是以程式帶動問題分析）
http://blog.csdn.net/luoshixian099/article/details/47377611
12、插值與拟合（對多項式及其插值講解還不錯）
http://wenku.baidu.com/link?url=wWcqLrpokQrjZZKzFbuJ4QDbZXZkMByCu-KaVKrSyGD6fh9Bpk1kZOPitpkFpNBw_no8UoyWY2DGQg9I7aL_tO3oi7z5mUK7cN8Sca6dX-O
13、線性插值與抛物線插值（對這兩種插值講解的很詳細，是目前發現最 好的一版
http://www.docin.com/p-711275966.html
14、奇異值分解（對奇異值怎麼來的講解比較細緻）
http://blog.sina.com.cn/s/blog_53eb0fdf0101sfu1.html
15，SIFT特征點提取 (重點參考)
16、https://zhuanlan.zhihu.com/p/36382429 （重點）