這是第一次寫(xiě)博客，感覺(jué)寫(xiě)個(gè)總結(jié)會(huì)有利于自己對(duì)算法的理解

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

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

2、https://blog.csdn.net/abcjennifer/article/details/7639681（目前看到的在博客中點(diǎn)贊數(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（幫助對(duì)SIFT特征點(diǎn)描述子生成的理解）

6、https://www.cnblogs.com/JiePro/p/sift_3.html（對(duì)理解特征點(diǎn)方向分配很有幫助）

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

8、原版的英文文獻(xiàn)：Distinctive Image Features from Scale-Invariate Keypoints

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

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

插一句：為什么要提取圖像的局部特征？因?yàn)椋鹤兞吭缴?，觀察結(jié)果變化的可能性就越小。

SIFT算法分為以下五個(gè)過(guò)程：

一、尺度空間的搭建；

二、尺度空間中候選極值點(diǎn)的檢測(cè)；

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

四、特征點(diǎn)方向分配；

五、特征點(diǎn)描述。

下面對(duì)每一個(gè)過(guò)程進(jìn)行詳細(xì)的介紹：

一、尺度空間的搭建

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

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

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

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

二維高斯卷積模板如下：

將二維高斯卷積模板與圖像作卷積運(yùn)算過(guò)程如下：

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

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

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

先要理解幾個(gè)概念：

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

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

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

所以通過(guò)計(jì)算得到對(duì)第1組第1層進(jìn)行高斯模糊的初始sigma為：

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

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

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

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

小結(jié)：

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

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

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

（3）每一層尺度的確定

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

二、尺度空間中候選極值點(diǎn)的檢測(cè)

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

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

1、去除低對(duì)比度的點(diǎn)

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

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

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

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

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

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

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

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

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

四、特征點(diǎn)方向分配

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

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

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

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

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

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

拋物線(xiàn)插值的方法如下（i屬于【0，35】）：

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

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

五、特征點(diǎn)描述

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

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

下面兩張圖中的綠色區(qū)域就是用來(lái)描述特征點(diǎn)的16個(gè)鄰域：

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

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