SIFT算法詳解

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

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

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

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

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

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

7、曲面的等高線是從中心開(kāi)始呈正態(tài)分布的同心圓，如圖2.1所示。分布不為零的像素組成的卷積矩陣與原始圖像做變換。每個(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距離之外的像素都可以看作不起作用，這些像素的計(jì)算也就可以忽略。通常，圖像處理程序只需要計(jì)算的矩陣就可以保證相關(guān)像素影響。2.2 圖像的二維高斯模糊

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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