SIFT算法詳解

1、SIFT算法詳解Scale Invariant Feature Transform(SIFT)Just For Funzdd  zddmail對于初學(xué)者，從David G.Lowe的論文到實現(xiàn)，有許多鴻溝，本文幫你跨越。1、SIFT綜述尺度不變特征轉(zhuǎn)換(Scale-invariant feature transform或SIFT)是一種電腦視覺的算法用來偵測與描述影像中的局部性特征，它在空間尺度中尋找極值點，并提取出其位置、尺度、旋轉(zhuǎn)不變量，此算法由 David Lowe在1999年所發(fā)表，2004年完善總結(jié)。其應(yīng)用范圍包含物體辨識、機器人地圖感知與導(dǎo)航、影像縫合、3D模型

2、建立、手勢辨識、影像追蹤和動作比對。此算法有其專利，專利擁有者為英屬哥倫比亞大學(xué)。局部影像特征的描述與偵測可以幫助辨識物體，SIFT 特征是基于物體上的一些局部外觀的興趣點而與影像的大小和旋轉(zhuǎn)無關(guān)。對于光線、噪聲、些微視角改變的容忍度也相當(dāng)高?；谶@些特性，它們是高度顯著而且相對容易擷取，在母數(shù)龐大的特征數(shù)據(jù)庫中，很容易辨識物體而且鮮有誤認。使用 SIFT特征描述對于部分物體遮蔽的偵測率也相當(dāng)高，甚至只需要3個以上的SIFT物體特征就足以計算出位置與方位。在現(xiàn)今的電腦硬件速度下和小型的特征數(shù)據(jù)庫條件下，辨識速度可接近即時運算。SIFT特征的信息量大，適合在海量數(shù)據(jù)庫中快速準

3、確匹配。SIFT算法的特點有：1. SIFT特征是圖像的局部特征，其對旋轉(zhuǎn)、尺度縮放、亮度變化保持不變性，對視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性；2. 獨特性（Distinctiveness）好，信息量豐富，適用于在海量特征數(shù)據(jù)庫中進行快速、準確的匹配；3. 多量性，即使少數(shù)的幾個物體也可以產(chǎn)生大量的SIFT特征向量；4. 高速性，經(jīng)優(yōu)化的SIFT匹配算法甚至可以達到實時的要求；5. 可擴展性，可以很方便的與其他形式的特征向量進行聯(lián)合。SIFT算法可以解決的問題：目標(biāo)的自身狀態(tài)、場景所處的環(huán)境和成像器材的成像特性等因素影響圖像配準/目標(biāo)識別跟蹤的性能。而SIFT算法在一定程度上可解決

4、：1. 目標(biāo)的旋轉(zhuǎn)、縮放、平移（RST）2. 圖像仿射/投影變換（視點viewpoint）3. 光照影響（illumination）4. 目標(biāo)遮擋（occlusion）5. 雜物場景（clutter）6. 噪聲SIFT算法的實質(zhì)是在不同的尺度空間上查找關(guān)鍵點(特征點)，并計算出關(guān)鍵點的方向。SIFT所查找到的關(guān)鍵點是一些十分突出，不會因光照，仿射變換和噪音等因素而變化的點，如角點、邊緣點、暗區(qū)的亮點及亮區(qū)的暗點等。Lowe將SIFT算法分解為如下四步：1. 尺度空間極值檢測：搜索所有尺度上的圖像位置。通過高斯微分函數(shù)來識別潛

5、在的對于尺度和旋轉(zhuǎn)不變的興趣點。2. 關(guān)鍵點定位：在每個候選的位置上，通過一個擬合精細的模型來確定位置和尺度。關(guān)鍵點的選擇依據(jù)于它們的穩(wěn)定程度。3. 方向確定：基于圖像局部的梯度方向，分配給每個關(guān)鍵點位置一個或多個方向。所有后面的對圖像數(shù)據(jù)的操作都相對于關(guān)鍵點的方向、尺度和位置進行變換，從而提供對于這些變換的不變性。4. 關(guān)鍵點描述：在每個關(guān)鍵點周圍的鄰域內(nèi)，在選定的尺度上測量圖像局部的梯度。這些梯度被變換成一種表示，這種表示允許比較大的局部形狀的變形和光照變化。本文沿著Lowe的步驟，參考Rob Hess及Andrea Vedaldi源碼，詳解SIFT算法的實現(xiàn)過程。2、

6、高斯模糊SIFT算法是在不同的尺度空間上查找關(guān)鍵點，而尺度空間的獲取需要使用高斯模糊來實現(xiàn)，Lindeberg等人已證明高斯卷積核是實現(xiàn)尺度變換的唯一變換核，并且是唯一的線性核。本節(jié)先介紹高斯模糊算法。2.1二維高斯函數(shù)高斯模糊是一種圖像濾波器，它使用正態(tài)分布(高斯函數(shù))計算模糊模板，并使用該模板與原圖像做卷積運算，達到模糊圖像的目的。N維空間正態(tài)分布方程為：（1-1）其中，是正態(tài)分布的標(biāo)準差，值越大，圖像越模糊(平滑)。r為模糊半徑，模糊半徑是指模板元素到模板中心的距離。如二維模板大小為m*n，則模板上的元素(x,y)對應(yīng)的高斯計算公式為：（1-2）  在二維空間中，這個公式生成的

7、曲面的等高線是從中心開始呈正態(tài)分布的同心圓，如圖2.1所示。分布不為零的像素組成的卷積矩陣與原始圖像做變換。每個像素的值都是周圍相鄰像素值的加權(quán)平均。原始像素的值有最大的高斯分布值，所以有最大的權(quán)重，相鄰像素隨著距離原始像素越來越遠，其權(quán)重也越來越小。這樣進行模糊處理比其它的均衡模糊濾波器更高地保留了邊緣效果。理論上來講，圖像中每點的分布都不為零，這也就是說每個像素的計算都需要包含整幅圖像。在實際應(yīng)用中，在計算高斯函數(shù)的離散近似時，在大概3距離之外的像素都可以看作不起作用，這些像素的計算也就可以忽略。通常，圖像處理程序只需要計算的矩陣就可以保證相關(guān)像素影響。2.2 圖像的二維高斯模糊

8、根據(jù)的值，計算出高斯模板矩陣的大小()，使用公式(1-2)計算高斯模板矩陣的值，與原圖像做卷積，即可獲得原圖像的平滑(高斯模糊)圖像。為了確保模板矩陣中的元素在0,1之間，需將模板矩陣歸一化。5*5的高斯模板如表2.1所示。下圖是5*5的高斯模板卷積計算示意圖。高斯模板是中心對稱的。2.3分離高斯模糊如圖2.3所示，使用二維的高斯模板達到了模糊圖像的目的，但是會因模板矩陣的關(guān)系而造成邊緣圖像缺失(2.3 b,c)，越大，缺失像素越多,丟棄模板會造成黑邊(2.3 d)。更重要的是當(dāng)變大時，高斯模板(高斯核)和卷積運算量將大幅度提高。根據(jù)高斯函數(shù)的可分離性，可對二維高斯模糊函數(shù)進行改進。高斯函數(shù)的

9、可分離性是指使用二維矩陣變換得到的效果也可以通過在水平方向進行一維高斯矩陣變換加上豎直方向的一維高斯矩陣變換得到。從計算的角度來看，這是一項有用的特性，因為這樣只需要次計算，而二維不可分的矩陣則需要次計算，其中，m,n為高斯矩陣的維數(shù)，M,N為二維圖像的維數(shù)。另外，兩次一維的高斯卷積將消除二維高斯矩陣所產(chǎn)生的邊緣。附錄1是用opencv2.2實現(xiàn)的二維高斯模糊和分離高斯模糊。表2.2為上述兩種方法和opencv2.3開源庫實現(xiàn)的高斯模糊程序的比較。3、尺度空間極值檢測尺度空間使用高斯金字塔表示。Tony Lindeberg指出尺度規(guī)范化的LoG(Laplacion of Gaussian)算子

10、具有真正的尺度不變性，Lowe使用高斯差分金字塔近似LoG算子，在尺度空間檢測穩(wěn)定的關(guān)鍵點。3.1 尺度空間理論尺度空間(scale space)思想最早是由Iijima于1962年提出的，后經(jīng)witkin和Koenderink等人的推廣逐漸得到關(guān)注，在計算機視覺鄰域使用廣泛。尺度空間理論的基本思想是：在圖像信息處理模型中引入一個被視為尺度的參數(shù)，通過連續(xù)變化尺度參數(shù)獲得多尺度下的尺度空間表示序列，對這些序列進行尺度空間主輪廓的提取，并以該主輪廓作為一種特征向量，實現(xiàn)邊緣、角點檢測和不同分辨率上的特征提取等。尺度空間方法將傳統(tǒng)的單尺度圖像信息處理技術(shù)納入尺度不斷變化的動態(tài)分析框架中，

11、更容易獲取圖像的本質(zhì)特征。尺度空間中各尺度圖像的模糊程度逐漸變大，能夠模擬人在距離目標(biāo)由近到遠時目標(biāo)在視網(wǎng)膜上的形成過程。尺度空間滿足視覺不變性。該不變性的視覺解釋如下：當(dāng)我們用眼睛觀察物體時，一方面當(dāng)物體所處背景的光照條件變化時，視網(wǎng)膜感知圖像的亮度水平和對比度是不同的，因此要求尺度空間算子對圖像的分析不受圖像的灰度水平和對比度變化的影響，即滿足灰度不變性和對比度不變性。另一方面，相對于某一固定坐標(biāo)系，當(dāng)觀察者和物體之間的相對位置變化時，視網(wǎng)膜所感知的圖像的位置、大小、角度和形狀是不同的，因此要求尺度空間算子對圖像的分析和圖像的位置、大小、角度以及仿射變換無關(guān)，即滿足平移不變性、尺度不變性、

12、歐幾里德不變性以及仿射不變性。3.2 尺度空間的表示一個圖像的尺度空間，定義為一個變化尺度的高斯函數(shù)與原圖像的卷積。 (3-1)其中，*表示卷積運算， (3-2)與公式(1-2)相同，m，n表示高斯模板的維度(由確定)。(x, y)代表圖像的像素位置。是尺度空間因子，值越小表示圖像被平滑的越少，相應(yīng)的尺度也就越小。大尺度對應(yīng)于圖像的概貌特征，小尺度對應(yīng)于圖像的細節(jié)特征。3.3 高斯金字塔的構(gòu)建尺度空間在實現(xiàn)時使用高斯金字塔表示，高斯金字塔的構(gòu)建分為兩部分：1. 對圖像做不同尺度的高斯模糊；2. 對圖像做降采樣(隔點采樣)。圖像的金字塔

13、模型是指，將原始圖像不斷降階采樣，得到一系列大小不一的圖像，由大到小，從下到上構(gòu)成的塔狀模型。原圖像為金子塔的第一層，每次降采樣所得到的新圖像為金字塔的一層(每層一張圖像)，每個金字塔共n層。金字塔的層數(shù)根據(jù)圖像的原始大小和塔頂圖像的大小共同決定，其計算公式如下：(3-3)其中M，N為原圖像的大小,t為塔頂圖像的最小維數(shù)的對數(shù)值。如，對于大小為512*512的圖像，金字塔上各層圖像的大小如表3.1所示，當(dāng)塔頂圖像為4*4時，n=7，當(dāng)塔頂圖像為2*2時，n=8。為了讓尺度體現(xiàn)其連續(xù)性，高斯金字塔在簡單降采樣的基礎(chǔ)上加上了高斯濾波。如圖3.1所示，將圖像金字塔每層的一張圖像使用不同參數(shù)做高斯模糊

14、，使得金字塔的每層含有多張高斯模糊圖像，將金字塔每層多張圖像合稱為一組(Octave)，金字塔每層只有一組圖像，組數(shù)和金字塔層數(shù)相等，使用公式(3-3)計算，每組含有多張(也叫層Interval)圖像。另外，降采樣時，高斯金字塔上一組圖像的初始圖像(底層圖像)是由前一組圖像的倒數(shù)第三張圖像隔點采樣得到的。注：由于組內(nèi)的多張圖像按層次疊放，因此組內(nèi)的多張圖像也稱做多層，為避免與金字塔層的概念混淆，本文以下內(nèi)容中，若不特別說明是金字塔層數(shù)，層一般指組內(nèi)各層圖像。注：如3.4節(jié)所示，為了在每組中檢測S個尺度的極值點，則DOG金字塔每組需S+2層圖像，而DOG金字塔由高斯金字塔相鄰兩層相減得到，則高斯

15、金字塔每組需S+3層圖像，實際計算時S在3到5之間。取S=3時，假定高斯金字塔存儲索引如下：第0組(即第-1組)：  0 1  2  3  4   5第1組：            6 7  8  9  10 11第2組：            ？則第2組第一張圖片根據(jù)第一組中索引為9的圖片降采樣得到，其它類似。  3.4 高斯差分金字塔2002年Mikolajczyk在詳細的

16、實驗比較中發(fā)現(xiàn)尺度歸一化的高斯拉普拉斯函數(shù)的極大值和極小值同其它的特征提取函數(shù)，例如：梯度，Hessian或Harris角特征比較，能夠產(chǎn)生最穩(wěn)定的圖像特征。而Lindeberg早在1994年就發(fā)現(xiàn)高斯差分函數(shù)（Difference of Gaussian ，簡稱DOG算子）與尺度歸一化的高斯拉普拉斯函數(shù)非常近似。其中和的關(guān)系可以從如下公式推導(dǎo)得到：利用差分近似代替微分，則有：                 因此有其中k-1是個常數(shù)，并不影響極值點位置的求取。如圖3.2所示，紅色曲線

17、表示的是高斯差分算子，而藍色曲線表示的是高斯拉普拉斯算子。Lowe使用更高效的高斯差分算子代替拉普拉斯算子進行極值檢測，如下：(3-4)在實際計算時，使用高斯金字塔每組中相鄰上下兩層圖像相減，得到高斯差分圖像，如圖3.3所示，進行極值檢測。3.5 空間極值點檢測(關(guān)鍵點的初步探查)關(guān)鍵點是由DOG空間的局部極值點組成的，關(guān)鍵點的初步探查是通過同一組內(nèi)各DoG相鄰兩層圖像之間比較完成的。為了尋找DoG函數(shù)的極值點，每一個像素點要和它所有的相鄰點比較，看其是否比它的圖像域和尺度域的相鄰點大或者小。如圖3.4所示，中間的檢測點和它同尺度的8個相鄰點和上下相鄰尺度對應(yīng)的9×2個點共

18、26個點比較，以確保在尺度空間和二維圖像空間都檢測到極值點。由于要在相鄰尺度進行比較，如圖3.3右側(cè)每組含4層的高斯差分金子塔，只能在中間兩層中進行兩個尺度的極值點檢測，其它尺度則只能在不同組中進行。為了在每組中檢測S個尺度的極值點，則DOG金字塔每組需S+2層圖像，而DOG金字塔由高斯金字塔相鄰兩層相減得到，則高斯金字塔每組需S+3層圖像，實際計算時S在3到5之間。當(dāng)然這樣產(chǎn)生的極值點并不全都是穩(wěn)定的特征點，因為某些極值點響應(yīng)較弱，而且DOG算子會產(chǎn)生較強的邊緣響應(yīng)。3.6 構(gòu)建尺度空間需確定的參數(shù) 尺度空間坐標(biāo)   O組(octave)數(shù) 

19、  S 組內(nèi)層數(shù)在上述尺度空間中，O和S，的關(guān)系如下： (3-5)其中是基準層尺度，o為組octave的索引，s為組內(nèi)層的索引。關(guān)鍵點的尺度坐標(biāo)就是按關(guān)鍵點所在的組和組內(nèi)的層，利用公式(3-5)計算而來。在最開始建立高斯金字塔時，要預(yù)先模糊輸入圖像來作為第0個組的第0層的圖像，這時相當(dāng)于丟棄了最高的空域的采樣率。因此通常的做法是先將圖像的尺度擴大一倍來生成第-1組。我們假定初始的輸入圖像為了抗擊混淆現(xiàn)象，已經(jīng)對其進行的高斯模糊，如果輸入圖像的尺寸用雙線性插值擴大一倍，那么相當(dāng)于。取式(3-4)中的k為組內(nèi)總層數(shù)的倒數(shù)，即  (3-6)在構(gòu)建高斯金字塔時，

20、組內(nèi)每層的尺度坐標(biāo)按如下公式計算：(3-7)其中初始尺度，lowe取，s為組內(nèi)的層索引，不同組相同層的組內(nèi)尺度坐標(biāo)相同。組內(nèi)下一層圖像是由前一層圖像按進行高斯模糊所得。式(3-7)用于一次生成組內(nèi)不同尺度的高斯圖像，而在計算組內(nèi)某一層圖像的尺度時，直接使用如下公式進行計算：(3-8)該組內(nèi)尺度在方向分配和特征描述時確定采樣窗口的大小。由上，式(3-4)可記為(3-9)圖3.5為構(gòu)建DOG金字塔的示意圖，原圖采用128*128的jobs圖像，擴大一倍后構(gòu)建金字塔。4、關(guān)鍵點定位以上方法檢測到的極值點是離散空間的極值點，以下通過擬合三維二次函數(shù)來精確確定關(guān)鍵點的位置和尺度，同時去除低對比度的關(guān)鍵點

21、和不穩(wěn)定的邊緣響應(yīng)點(因為DoG算子會產(chǎn)生較強的邊緣響應(yīng))，以增強匹配穩(wěn)定性、提高抗噪聲能力。4.1關(guān)鍵點的精確定位離散空間的極值點并不是真正的極值點，圖4.1顯示了二維函數(shù)離散空間得到的極值點與連續(xù)空間極值點的差別。利用已知的離散空間點插值得到的連續(xù)空間極值點的方法叫做子像素插值（Sub-pixel Interpolation）。為了提高關(guān)鍵點的穩(wěn)定性，需要對尺度空間DoG函數(shù)進行曲線擬合。利用DoG函數(shù)在尺度空間的Taylor展開式(擬合函數(shù))為：(4-1)其中，。求導(dǎo)并讓方程等于零，可以得到極值點的偏移量為：(4-2)對應(yīng)極值點，方程的值為：(4-3)其中,代表相對插值中心的偏移量，當(dāng)它

22、在任一維度上的偏移量大于0.5時（即x或y或），意味著插值中心已經(jīng)偏移到它的鄰近點上，所以必須改變當(dāng)前關(guān)鍵點的位置。同時在新的位置上反復(fù)插值直到收斂；也有可能超出所設(shè)定的迭代次數(shù)或者超出圖像邊界的范圍，此時這樣的點應(yīng)該刪除，在Lowe中進行了5次迭代。另外，過小的點易受噪聲的干擾而變得不穩(wěn)定，所以將小于某個經(jīng)驗值(Lowe論文中使用0.03，Rob Hess等人實現(xiàn)時使用0.04/S)的極值點刪除。同時，在此過程中獲取特征點的精確位置(原位置加上擬合的偏移量)以及尺度()。4.2消除邊緣響應(yīng)一個定義不好的高斯差分算子的極值在橫跨邊緣的地方有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。DOG

23、算子會產(chǎn)生較強的邊緣響應(yīng)，需要剔除不穩(wěn)定的邊緣響應(yīng)點。獲取特征點處的Hessian矩陣，主曲率通過一個2x2 的Hessian矩陣H求出： (4-4)H的特征值和代表x和y方向的梯度， (4-5)表示矩陣H對角線元素之和，表示矩陣H的行列式。假設(shè)是較大的特征值，而是較小的特征值，令，則(4-6)                導(dǎo)數(shù)由采樣點相鄰差估計得到,在下一節(jié)中說明。D的主曲率和H的特征值成正比，令為最大特征值，為最小的特征值，則公式的值在兩個特征值相等時最小，隨著的增大而增大。值越

24、大，說明兩個特征值的比值越大，即在某一個方向的梯度值越大，而在另一個方向的梯度值越小，而邊緣恰恰就是這種情況。所以為了剔除邊緣響應(yīng)點，需要讓該比值小于一定的閾值，因此，為了檢測主曲率是否在某域值r下，只需檢測(4-7)式(4-7)成立時將關(guān)鍵點保留，反之剔除。在Lowe的文章中，取r10。圖4.2右側(cè)為消除邊緣響應(yīng)后的關(guān)鍵點分布圖。 4.3有限差分法求導(dǎo)有限差分法以變量離散取值后對應(yīng)的函數(shù)值來近似微分方程中獨立變量的連續(xù)取值。在有限差分方法中，我們放棄了微分方程中獨立變量可以取連續(xù)值的特征，而關(guān)注獨立變量離散取值后對應(yīng)的函數(shù)值。但是從原則上說，這種方法仍然可以達到任意滿意的計算精度。

25、因為方程的連續(xù)數(shù)值解可以通過減小獨立變量離散取值的間格，或者通過離散點上的函數(shù)值插值計算來近似得到。這種方法是隨著計算機的誕生和應(yīng)用而發(fā)展起來的。其計算格式和程序的設(shè)計都比較直觀和簡單，因而，它在計算數(shù)學(xué)中使用廣泛。有限差分法的具體操作分為兩個部分：1. 用差分代替微分方程中的微分，將連續(xù)變化的變量離散化，從而得到差分方程組的數(shù)學(xué)形式；2. 求解差分方程組。一個函數(shù)在x點上的一階和二階微商，可以近似地用它所臨近的兩點上的函數(shù)值的差分來表示。如對一個單變量函數(shù)f(x)，x為定義在區(qū)間a,b上的連續(xù)變量，以步長將區(qū)間a,b離散化，我們會得到一系列節(jié)點，然后求出f(x)在這些點上

26、的近似值。顯然步長h越小，近似解的精度就越好。與節(jié)點相鄰的節(jié)點有和，所以在節(jié)點處可構(gòu)造如下形式的差值： 節(jié)點的一階向前差分節(jié)點的一階向后差分節(jié)點的一階中心差分本文使用中心差分法利用泰勒展開式求解第四節(jié)所使用的導(dǎo)數(shù)，現(xiàn)做如下推導(dǎo)。函數(shù)f(x)在處的泰勒展開式為：(4-8)則，(4-9)(4-10)忽略h平方之后的項，聯(lián)立式(4-9)，(4-10)解方程組得：(4-11) (4-12)二元函數(shù)的泰勒展開式如下：將展開后忽略次要項聯(lián)立解方程得二維混合偏導(dǎo)如下：(4-13)綜上，推導(dǎo)了4.1,4.2遇到的所有導(dǎo)數(shù)計算。同理，利用多元泰勒展開式，可得任意偏導(dǎo)的近似差分表示。在圖像處理

27、中，取h=1，在圖4.2所示的圖像中，將像素0的基本中點導(dǎo)數(shù)公式整理如下：4.4 三階矩陣求逆公式高階矩陣的求逆算法主要有歸一法和消元法兩種，現(xiàn)將三階矩陣求逆公式總結(jié)如下：若矩陣可逆，即時，(4-14)5、關(guān)鍵點方向分配為了使描述符具有旋轉(zhuǎn)不變性，需要利用圖像的局部特征為給每一個關(guān)鍵點分配一個基準方向。使用圖像梯度的方法求取局部結(jié)構(gòu)的穩(wěn)定方向。對于在DOG金字塔中檢測出的關(guān)鍵點點，采集其所在高斯金字塔圖像3鄰域窗口內(nèi)像素的梯度和方向分布特征。梯度的模值和方向如下：(5-1)L為關(guān)鍵點所在的尺度空間值，按Lowe的建議，梯度的模值m(x,y)按的高斯分布加成，按尺度采樣的3原則，鄰域窗

28、口半徑為。在完成關(guān)鍵點的梯度計算后，使用直方圖統(tǒng)計鄰域內(nèi)像素的梯度和方向。梯度直方圖將0360度的方向范圍分為36個柱(bins)，其中每柱10度。如圖5.1所示，直方圖的峰值方向代表了關(guān)鍵點的主方向，(為簡化，圖中只畫了八個方向的直方圖)。方向直方圖的峰值則代表了該特征點處鄰域梯度的方向，以直方圖中最大值作為該關(guān)鍵點的主方向。為了增強匹配的魯棒性，只保留峰值大于主方向峰值80的方向作為該關(guān)鍵點的輔方向。因此，對于同一梯度值的多個峰值的關(guān)鍵點位置，在相同位置和尺度將會有多個關(guān)鍵點被創(chuàng)建但方向不同。僅有15的關(guān)鍵點被賦予多個方向，但可以明顯的提高關(guān)鍵點匹配的穩(wěn)定性。實際編程實現(xiàn)中，就是把該關(guān)鍵點

29、復(fù)制成多份關(guān)鍵點，并將方向值分別賦給這些復(fù)制后的關(guān)鍵點，并且，離散的梯度方向直方圖要進行插值擬合處理，來求得更精確的方向角度值，檢測結(jié)果如圖5.2所示。至此，將檢測出的含有位置、尺度和方向的關(guān)鍵點即是該圖像的SIFT特征點。6、關(guān)鍵點特征描述通過以上步驟，對于每一個關(guān)鍵點，擁有三個信息：位置、尺度以及方向。接下來就是為每個關(guān)鍵點建立一個描述符，用一組向量將這個關(guān)鍵點描述出來，使其不隨各種變化而改變，比如光照變化、視角變化等等。這個描述子不但包括關(guān)鍵點，也包含關(guān)鍵點周圍對其有貢獻的像素點，并且描述符應(yīng)該有較高的獨特性，以便于提高特征點正確匹配的概率。SIFT描述子是關(guān)鍵點鄰域高斯圖像梯度統(tǒng)計結(jié)果

30、的一種表示。通過對關(guān)鍵點周圍圖像區(qū)域分塊，計算塊內(nèi)梯度直方圖，生成具有獨特性的向量，這個向量是該區(qū)域圖像信息的一種抽象，具有唯一性。Lowe建議描述子使用在關(guān)鍵點尺度空間內(nèi)4*4的窗口中計算的8個方向的梯度信息，共4*4*8=128維向量表征。表示步驟如下：1. 確定計算描述子所需的圖像區(qū)域特征描述子與特征點所在的尺度有關(guān)，因此，對梯度的求取應(yīng)在特征點對應(yīng)的高斯圖像上進行。將關(guān)鍵點附近的鄰域劃分為d*d(Lowe建議d=4)個子區(qū)域，每個子區(qū)域做為一個種子點，每個種子點有8個方向。每個子區(qū)域的大小與關(guān)鍵點方向分配時相同，即每個區(qū)域有個子像素，為每個子區(qū)域分配邊長為的矩形區(qū)域進行采樣(個子像素實

31、際用邊長為的矩形區(qū)域即可包含，但由式(3-8)，不大，為了簡化計算取其邊長為，并且采樣點宜多不宜少)?？紤]到實際計算時，需要采用雙線性插值，所需圖像窗口邊長為。在考慮到旋轉(zhuǎn)因素(方便下一步將坐標(biāo)軸旋轉(zhuǎn)到關(guān)鍵點的方向)，如下圖6.1所示，實際計算所需的圖像區(qū)域半徑為：   (6-1)計算結(jié)果四舍五入取整。2. 將坐標(biāo)軸旋轉(zhuǎn)為關(guān)鍵點的方向，以確保旋轉(zhuǎn)不變性，如6.2所示。 旋轉(zhuǎn)后鄰域內(nèi)采樣點的新坐標(biāo)為： (6-2)3. 將鄰域內(nèi)的采樣點分配到對應(yīng)的子區(qū)域內(nèi)，將子區(qū)域內(nèi)的梯度值分配到8個方向上，計算其權(quán)值。旋轉(zhuǎn)后的采樣點坐標(biāo)在半徑為radius的圓內(nèi)

32、被分配到的子區(qū)域，計算影響子區(qū)域的采樣點的梯度和方向，分配到8個方向上。旋轉(zhuǎn)后的采樣點落在子區(qū)域的下標(biāo)為   (6-3)Lowe建議子區(qū)域的像素的梯度大小按的高斯加權(quán)計算，即(6-4)其中a，b為關(guān)鍵點在高斯金字塔圖像中的位置坐標(biāo)。4. 插值計算每個種子點八個方向的梯度。如圖6.3所示，將由式(6-3)所得采樣點在子區(qū)域中的下標(biāo)(圖中藍色窗口內(nèi)紅色點)線性插值，計算其對每個種子點的貢獻。如圖中的紅色點，落在第0行和第1行之間，對這兩行都有貢獻。對第0行第3列種子點的貢獻因子為dr，對第1行第3列的貢獻因子為1-dr，同理，對鄰近兩列的貢獻因子為dc和1-dc，對鄰

33、近兩個方向的貢獻因子為do和1-do。則最終累加在每個方向上的梯度大小為：(6-5)其中k，m，n為0或為1。5. 如上統(tǒng)計的4*4*8=128個梯度信息即為該關(guān)鍵點的特征向量。特征向量形成后，為了去除光照變化的影響，需要對它們進行歸一化處理，對于圖像灰度值整體漂移，圖像各點的梯度是鄰域像素相減得到，所以也能去除。得到的描述子向量為，歸一化后的特征向量為則 (6-7)6. 描述子向量門限。非線性光照，相機飽和度變化對造成某些方向的梯度值過大，而對方向的影響微弱。因此設(shè)置門限值(向量歸一化后，一般取0.2)截斷較大的梯度值。然后，再進行一次歸一化處理，提高特征的鑒別性。7. 按特征點的

34、尺度對特征描述向量進行排序。至此，SIFT特征描述向量生成。 描述向量這塊不好理解，我畫了個草圖，供參考：7、SIFT的缺點SIFT在圖像的不變特征提取方面擁有無與倫比的優(yōu)勢，但并不完美，仍然存在：1. 實時性不高。2. 有時特征點較少。3. 對邊緣光滑的目標(biāo)無法準確提取特征點。等缺點，如下圖7.1所示，對模糊的圖像和邊緣平滑的圖像，檢測出的特征點過少，對圓更是無能為力。近來不斷有人改進，其中最著名的有SURF和CSIFT。8、總結(jié)本人研究SIFT算法一月有余，鑒于相關(guān)知識的缺失，尺度空間技術(shù)和差分近似求導(dǎo)曾困我良久。Lowe在論文中對細節(jié)提之甚少，甚至只字未提，給實現(xiàn)帶來了很大困難。經(jīng)過多方查閱，實現(xiàn)，總結(jié)成此文。自認為是到目前為止，關(guān)于SIFT算法最為詳盡的資料，現(xiàn)分享給你，望批評指正。一同分享給你的還有同時實現(xiàn)的高斯模糊源碼，sift算法源碼，見附錄1，2。源碼使用vs2010+opencv2.2實現(xiàn)。zdd2012年4月28日 于北師大2012年5月17日15:33:23第一次修正修正