這是第一次寫博客，感覺寫個總結(jié)會有利于自己對算法的理解

首先,，本文參考的博文如下：

1,、https://blog.csdn.net/hit2015spring/article/details/52895367(高斯濾波，有利于對生成高斯差分尺度空間的理解）

2,、https://blog.csdn.net/abcjennifer/article/details/7639681（目前看到的在博客中點贊數(shù)最多的）

3,、https://blog.csdn.net/zddblog/article/details/7521424

4、https://blog.csdn.net/kyu_saku/article/details/52804265（一些基本概念）

5,、https://blog.csdn.net/u011028345/article/details/70829766（幫助對SIFT特征點描述子生成的理解）

6,、https://www.cnblogs.com/JiePro/p/sift_3.html（對理解特征點方向分配很有幫助）

7、https://blog.csdn.net/lingyunxianhe/article/details/79063547（這篇把SIFT算法的整個過程描述的很清楚)

8,、原版的英文文獻：Distinctive Image Features from Scale-Invariate Keypoints

SIFT是特征點鄰域高斯圖像梯度統(tǒng)計結(jié)果的一種表示,，是一種圖像局部特征提取算法。

SIFT對于旋轉(zhuǎn),，尺度縮放,，亮度變化保持不變性

插一句：為什么要提取圖像的局部特征？因為：變量越少,，觀察結(jié)果變化的可能性就越小,。

SIFT算法分為以下五個過程：

一、尺度空間的搭建,；

二,、尺度空間中候選極值點的檢測；

三,、對上一過程中得出的候選極值點進行篩選,，去除低對比度的點和不穩(wěn)定的邊緣響應(yīng)點，得到真正的特征點,；

四,、特征點方向分配；

五,、特征點描述,。

下面對每一個過程進行詳細(xì)的介紹：

一,、尺度空間的搭建

      在圖像處理中引入一個尺度的概念：它可以模擬人在距離目標(biāo)由近到遠(yuǎn)的過程中，目標(biāo)在視網(wǎng)膜當(dāng)中形成圖像的過程,。尺度越大,，表示圖像的概貌，只能看清楚物體的輪廓,，簡單的說就是看起來越模糊,，相當(dāng)于我們觀察遠(yuǎn)處的物體；尺度越小,，表示圖像的細(xì)節(jié),，相當(dāng)于我們觀察近處的物體。如果需要識別出包含不同尺寸的同一物體的兩幅圖像,，隨著物體在圖像中大小發(fā)生變化,，屬于該物體的局部區(qū)域的大小也會發(fā)生變化。SIFT算法中采用圖像金字塔的方法就可以解決這一問題,，首先將兩幅圖像想象成是連續(xù)的,，分別以它們作為底面作四棱椎，就像金字塔一樣,，那么每一個截面都與原圖像相似,，且兩個金字塔中必然會有包含大小一致的物體的截面，但構(gòu)造的金字塔層數(shù)是離散的,，只能構(gòu)造有限層,，所以構(gòu)造層數(shù)越多越好，但處理時間會增加,，層數(shù)太少也不行,，因為向下采樣的截面中可能找不到尺寸大小一致的兩個物體的圖像。

　　在SIFT算法中,，采用的是高斯差分金字塔（DOG）,，具體為什么是高斯差分金字塔不知道，只知道大牛們通過實驗得出：尺度歸一化的高斯拉普拉斯算子能夠得到最穩(wěn)定的圖像特征,，但因為計算量太大,，而高斯差分函數(shù)與高斯拉普拉斯算子很相似，所以通過高斯差分函數(shù)來近似的計算圖像最穩(wěn)定的特征,。

       首先介紹一下高斯金字塔再來理解高斯差分金字塔,，高斯金字塔并不是一個金字塔，而是有很多組（Octave）金字塔構(gòu)成,，并且每組金字塔都包含若干層（Interval），高斯金字塔主要是為了得到不同尺度的圖像來模擬圖像數(shù)據(jù)的多尺度特征,，構(gòu)建主要分兩步：（1）模糊尺度的確定,；（2）降采樣,。大牛們不知道為了什么原因先對原始圖像進行擴大一倍的處理（用雙線性插值），應(yīng)該是為了獲得更多的特征點,，將其作為高斯金字塔的第1組第1層,，將第1組第1層圖像經(jīng)高斯卷積之后作為第1組金子塔的第2層，高斯卷積函數(shù)為（高斯卷積核是實現(xiàn)尺度變換的唯一線性核）：

上面的高斯卷積函數(shù)只是一個數(shù)學(xué)表達(dá)式,，根據(jù)數(shù)學(xué)理論知識,，由于數(shù)字圖像是離散的，想求導(dǎo)和求最值這些操作都是使用濾波器,，在圖像處理中通過卷積濾波實現(xiàn)對圖像的平滑,，它使用正態(tài)分布(高斯函數(shù))計算模糊模板，并使用該模板與原圖像做卷積運算,，達(dá)到模糊圖像的目的,。

二維高斯卷積模板如下：

將二維高斯卷積模板與圖像作卷積運算過程如下：

       分布不為0的像素組成的卷積矩陣與原始圖像作變換，每個像素的值都是周圍相鄰像素值的加權(quán)平均,，原始像素的值有最大的高斯分布值,，所以有最大的權(quán)重，相鄰像素隨著距離原始像素越來越遠(yuǎn),，其權(quán)重也越來越小,，這樣進行模糊處理比其他的均衡模糊濾波器更高的保留了邊緣效果，理論上來講,，圖像中每點的分布都不為零,，這也就是說每個像素的計算都需要包含整幅圖像，但在實際應(yīng)用中,，在計算高斯函數(shù)的離散近似時,，在大概3*sigma距離之外的像素都可以看作不起作用，這些像素的計算也就可以忽略不計,，通常,，圖像處理只需要計算（6*sigma+1）*（6*sigma+1）的矩陣就可以保證相關(guān)像素影響。

      但二維矩陣模板會造成邊緣圖像缺失且隨著sigma的變大,，高斯模板和卷積運算量將大大增加,，所以將高斯函數(shù)分離，使用二維矩陣變換得到的效果可以通過在水平方向進行一維高斯矩陣變換加上豎直方向的一維高斯矩陣變換得到,，對用模板矩陣超出邊界的部分——虛線框,，將不做卷積計算。如圖2.4中x方向的第一個模板1*5,，將退化成1*3的模板,，只在圖像之內(nèi)的部分做卷積。

對數(shù)學(xué)公式中高斯卷積方差sigma的選擇：

先要理解幾個概念：

高斯金字塔的模糊尺度：這個尺度是我們產(chǎn)生模板的尺度

攝像頭模糊的尺度：這個尺度是圖像被相機鏡頭模糊后的尺度，一般為固定值,，這里定義0.5

圖像的尺度：這個尺度是攝像頭模糊尺度和高斯金字塔尺度的合作用,，滿足方和根的關(guān)系（對同一張圖片進行連續(xù)多次高斯模糊與只用一次大的高斯模糊，可以達(dá)到一樣的效果,，如兩次的模糊值分別為3和4,，達(dá)到的效果可以只用5就可以）。Lowe定義圖片的尺度為1.6

所以通過計算得到對第1組第1層進行高斯模糊的初始sigma為：

但別忘了前面對原始圖像進行了擴大一倍的處理,，所以真正對第1組第1層進行高斯模糊的初始sigma為：

將sigma1.25乘以一個比例系數(shù)k,，得到一個新的平滑因子，用它來平滑第1組第2層的圖像,，結(jié)果圖像作為第3層,。如此這般重復(fù)，最后得到L層圖像,，在每一組中,，每一層的尺寸都是一樣的，只是平滑系數(shù)不一樣,。將第一組倒數(shù)第三層圖像只作比例因子為2的降采樣,，其他不處理（指不進行高斯模糊）作為第2組的第1層（這樣做的原因：為了保持在極值檢測過程中高斯差分金字塔尺度空間的連續(xù)性，即高斯模糊系數(shù)的連續(xù)性）,，然后對第2組的第1層中的平滑因子通過乘以一個比例系數(shù)k,，得到一個新的平滑因子，用它來平滑第2組第1層的圖像,，結(jié)果圖像作為第2組的第2層,，如此重復(fù)得到第2組的L層圖像，同組內(nèi)它們的尺寸是一樣的,，但是在尺寸方面第2組是第1組圖像的一半,。這樣反復(fù)執(zhí)行，就可以得到一共O組,，每組L層,，共計O*L個圖像，這些圖像一起構(gòu)成高斯金字塔,。

        高斯差分金字塔是在高斯金字塔的基礎(chǔ)上構(gòu)建起來的,，生成高斯金字塔的目的是為了構(gòu)建高斯差分金字塔。高斯差分金字塔的第1組第1層是由高斯金字塔的第1組第2層減第1組第1層得到的,，以此類推,，逐組逐層生成每一個差分圖像，所有差分圖像構(gòu)成差分金字塔,，每一組在層數(shù)上,，高斯差分金字塔比高斯金字塔少一層,。

下圖是對高斯金字塔和高斯差分金字塔的一個示意圖，從圖中也可以看出為了在檢測極值過程中能夠在每組圖像中檢測S（S表示層數(shù),，一般取3）個尺度的極值點,，即滿足尺度變化的連續(xù)性,，將第一組倒數(shù)第三層圖像作為第2組的第1層,，且層數(shù)一般取3層，但要在3層的基礎(chǔ)上再加3層變成6層才能滿足要求,。

小結(jié)：

高斯金字塔構(gòu)建過程中的4個關(guān)鍵點：

（1）金字塔組數(shù)的確定,，，M,，N表示圖像的行,，列數(shù)

（2）金字塔層數(shù)的確定,，一般6層（不包括擴大一倍后的原圖像）

（3）每一層尺度的確定

（4）下一組的圖片降采樣母本的確定

二、尺度空間中候選極值點的檢測

       SIFT特征點是由高斯差分空間的局部極值點經(jīng)過篩選組成的，中間的檢測點和它同尺度的8個相鄰點和上下相鄰尺度對應(yīng)的9×2個點共26個點比較,， 一個點如果在DOG尺度空間本層以及上下兩層的26個領(lǐng)域中是最大或最小值時，就認(rèn)為該點是圖像在該尺度下一個候選的特征點,，DoG圖像中的大值和小值出現(xiàn)在圖像區(qū)域發(fā)生較大變化的邊緣處,，沒有變化的區(qū)域響應(yīng)則接近于0，

三,、對上一過程中得出的候選極值點進行篩選,，去除低對比度的點和不穩(wěn)定的邊緣響應(yīng)點，得到真正的特征點

1,、去除低對比度的點

       在SIFT中,，圖像局部塊的對比度是用DOG響應(yīng)的絕對值大小來度量的，因為DOG運算的本質(zhì)是度量一個像素點和其周圍像素的不同,，值越大則對比度越高,。去除小的值的點，保留有較大響應(yīng)的點,。SIFT通過構(gòu)建尺度空間來計算不同尺度下觀察到的特別的局部圖像塊,，由于尺度采樣操作的存在，上面找到的近似極值點落在像素點的位置上,，而實際上如果在像素點附近用空間曲面去擬合的話,，很多情況下極值點都不是恰好在像素點上，而是在附近,，即極值點的位置存在偏移,，為了得到更精確的極值點的位置和其響應(yīng)值，SIFT中,，假定了DOG響應(yīng)局部區(qū)域的連續(xù)性,，用二階泰勒展開式來擬合并估計DOG的響應(yīng)值,，若該特征點的響應(yīng)值的絕對值>=0.03，則保留該特征點,，否則視為低對比度的點丟棄,。

2、去除不穩(wěn)定的邊緣響應(yīng)點

       邊緣的梯度值是朝同一個方向的,，于是會呈現(xiàn)明顯的梯度主方向,，SIFT尋找的局部圖像塊，期望局部塊中的主梯度方向與其他方向的梯度相差不要太大,，通過計算DOG的二階導(dǎo)數(shù)（Hessian矩陣）,，得到主梯度方向和其他方向的比值，保留該比值小于一定數(shù)值的局部特征點,。去除僅落在邊緣上而非角點的點,，這類應(yīng)被舍去的點有一個特征：沿著邊緣切線方向的圖像函數(shù)平緩（曲率小）,。垂直邊緣方向陡峭（曲率大）,。由于Hessian矩陣的兩個特征值是X，Y方向的曲率,，所以求出每個極值點兩個特征值的比例,，設(shè)定一個界限，舍去不合格的點即可,。

        利用Hessian矩陣去除不穩(wěn)定的邊緣響應(yīng)點的算法如下：

（1）對每個候選的極值點計算圖像在X方向和Y方向的二階偏導(dǎo)數(shù)以及圖像XY方向的導(dǎo)數(shù),；

（2）根據(jù)第一步的結(jié)果，得到該候選極值點的Hessian矩陣：

Ixx表示X方向的二階偏導(dǎo)數(shù),；Iyy表示Y方向的二階偏導(dǎo)數(shù),；Ixy表XY方向的二階導(dǎo)數(shù)

（3）求出該Hessian矩陣的兩個特征值，那么矩陣的兩個特征值之和就是矩陣的跡,，兩個特征值之積就是矩陣的行列式,；

（4）將矩陣跡的平方與矩陣行列式的平方之比作為判斷條件（這里假設(shè)兩個特征值成比例關(guān)系，不一定是整數(shù)比例進行計算）,，若該“比”小于一定的閾值（閾值一般取10）,，則是真正的極值點。

四,、特征點方向分配

       對上面的每個特征點,，圍繞該點選擇一個窗口（圓形區(qū)域，以該特征點為中心,，半徑為3*sigma作一個圓域）,，窗口內(nèi)各采樣點的梯度方向構(gòu)成一個直方圖，根據(jù)直方圖的峰值確定特征點的主方向,，  直方圖的峰值確定以后,，任何大于峰值80%的方向（柱）創(chuàng)建一個具有該方向的特征點,，這個方向認(rèn)為是特征點的輔方向，因此,，對于多峰值的情況,，在同一位置和尺度就會產(chǎn)生多個具有不同方向的關(guān)鍵點，就是將該特征點復(fù)制成多份特征點（除了方向θ不同外,，x,y,σ都相同）,。  注意：特征點的尺度用來選擇哪個高斯濾波圖像參與計算，還用來決定窗口的大?。榱吮ＷC不同尺度下的同一特征點都包含相同的信息量,，那么窗口的大小必須不一樣：同一個原始圖像,，尺度越大,，窗口應(yīng)該越大；反之,，如果窗口大小不變,，尺度越大的圖像包含的信息量越少。

窗口內(nèi)各采樣點的梯度方向和梯度幅值計算公式如下:

L為特征點所在的尺度空間值,，大牛們計算模值是通過對高斯函數(shù)的sigma取1.5sigma的高斯分布加成的,，高斯函數(shù)如下：

按尺度采樣的3*sigma原則，鄰域窗口半徑為3*1.5sigma,，分配給特征點的方向并不直接是特征點的梯度方向,，且梯度幅值也不是直接累加到直方圖中去的，每個累加到梯度方向直方圖的采樣點的幅值都要進行權(quán)重處理,，加權(quán)采用圓形高斯加權(quán)函數(shù),，對于已經(jīng)檢測到的特征點，我們知道該特征點的尺度值sigma,，因此根據(jù)這一尺度值,，得到高斯函數(shù)方差為該特征點尺度sigma的1.5倍，形式為：

其中（i,j）為該點距離特征點的相對位置,，左上角點像素距離特征點（0,0）（即中心點）的相對位置坐標(biāo)為（-4,-4）,，同理，右下角像素為（4,4）,。遍歷鄰域（綠色）中每個點,，判斷其梯度方向，將其加入相應(yīng)的梯度方向直方圖中,，加入量為其梯度幅值 * wi,j ,，例如左上角(-4,-4)的點，其梯度為方向為25°,，梯度幅值為m,，我們將其加入到hist[2]中（假設(shè)hist[0]為0°~10°的直方柱,，hist[1]為10°~20°的直方柱，以此類推至hist[35]為350°~360°）,加入的量為m* w(-4,-4),，即hist[2] = hist[2] + mag* w(-4,-4),。直至遍歷整個鄰域，統(tǒng)計出該特征點出的梯度方向直方圖,。

從上面可以看到做一個梯度方向的直方圖,，梯度方向直方圖的橫軸是梯度方向角，縱軸是梯度方向角對應(yīng)的（帶高斯權(quán)重）梯度幅值累加值,，范圍是0~360度,，其中每10度一個柱，總共36個柱,。直方圖的一個柱表示一個角度范圍,，如10°~20°，這樣得到的主方向或者輔方向是一個角度區(qū)間,，需要進行拋物線插值來求出主方向和輔方向的角度,，這樣計算出來的主方向或者輔方向才是一個值。

拋物線插值的方法如下（i屬于【0,，35】）：

由于角度是循環(huán)的,，即0度=360度，如果出現(xiàn)h(j)超出了（0,，……,，35）的范圍，那么可以通過圓周循環(huán)的方法找到它所對應(yīng)的在0度到360度之間的值,。如h(-1)=h(35),。

得到特征點的主方向后，對于每個特征點可以得到三個信息(x,y,σ,θ),，即位置,、尺度和方向。由此可以確定一個SIFT特征區(qū)域,，一個SIFT特征區(qū)域由三個值表示,，中心表示特征點位置，半徑表示關(guān)鍵點的尺度,，箭頭表示主方向,。具有多個方向的關(guān)鍵點可以被復(fù)制成多份，然后將方向值分別賦給復(fù)制后的特征點,，一個特征點就產(chǎn)生了多個坐標(biāo),、尺度相等，但是方向不同的特征點,。為了確保旋轉(zhuǎn)不變性,，將圖像旋轉(zhuǎn)至特征點主方向與X軸方向重合,。

五、特征點描述

       首先需要確定計算特征描述符的鄰域范圍,，將特征點附近的鄰域劃分成4*4個子區(qū)域,，每個子區(qū)域作為一個種子點，每個種子點有8個方向,，這里與求特征點主方向時有所不同,，此時每個子區(qū)域的梯度方向直方圖將0度到360度劃分為8個方向范圍，每個范圍為45度,，這樣每個種子點共有8個方向的梯度強度信息,。

       理論上來說，每個子區(qū)域的矩形邊長為3*sigma,，即一個子區(qū)域中包含（3*sigma）*（3*sigma）個像素,，16個子區(qū)域的像素個數(shù)為4*4*（3*sigma）*（3*sigma）。但在實際中,，由于如果鄰域中像素的梯度方向為33度時,，不能直接把它當(dāng)作30度進行處理，應(yīng)該要把它按照相鄰的梯度方向30度到40度的距離切分成兩份分給它們,，所以就需要進行三線性插值的處理，所以將描述該特征點的窗口邊長從3*sigma*d擴增至3*sigma*（d+1）,，這樣整個區(qū)域的像素數(shù)就變成了【3*sigma*（d+1）】*【3*sigma*（d+1）】,，但由于圖像要旋轉(zhuǎn)，所以整個區(qū)域的像素數(shù)又變成了【3*sigma*（d+1）*根號2】*【3*sigma*（d+1）*根號2】,。雖然現(xiàn)在窗口的邊長變成了3*sigma*（d+1）,，但最后用來描述特征點的區(qū)域邊長還是3*sigma*d，所以實際得到的16個子區(qū)域的描述是通過窗口邊長為3*sigma*（d+1）的區(qū)域經(jīng)過計算得到的,，即下圖第二張圖中綠色區(qū)域是由外面的藍(lán)色區(qū)域計算得到,，一個綠色區(qū)域由包含它的外面4個藍(lán)色區(qū)域計算得到，至于具體怎么計算,，見如下第二張圖和第三張圖,。

下面兩張圖中的綠色區(qū)域就是用來描述特征點的16個鄰域：

如上統(tǒng)計的4*4*8=128個梯度信息即為該特征點的特征向量。特征向量形成后,，為了去除光照變化的影響,，需要對它們進行歸一化處理，公式如下：

當(dāng)兩幅圖像的SIFT特征向量生成后,，下一步采用特征點向量的歐式距離作為兩幅圖像中的特征點相似性判定度量,，取圖像1中的某個特征點，找出圖像2中與其歐式距離最近的前兩個特征點,，在這兩個特征點中,，如果最近的距離與次近的距離比值小于某個閾值,，則接受這一對匹配點，降低這個比例閾值,，SIFT匹配點數(shù)量會減少,，但更加穩(wěn)定。