SIFT算法實(shí)現(xiàn)原理步驟

1、SIFT算法實(shí)現(xiàn)步驟 ：1 關(guān)鍵點(diǎn)檢測(cè)、2 關(guān)鍵點(diǎn)描述、3 關(guān)鍵點(diǎn)匹配、4 消除錯(cuò)配點(diǎn)1關(guān)鍵點(diǎn)檢測(cè)1.1 建立尺度空間根據(jù)文獻(xiàn)Scale-space theory: A basic tool for analysing structures at different scales我們可知，高斯核是唯一可以產(chǎn)生多尺度空間的核，一個(gè)圖像的尺度空間，L（x,y,) ,定義為原始圖像I(x,y)與一個(gè)可變尺度的2維高斯函數(shù)G(x,y,) 卷積運(yùn)算。 高斯函數(shù) 高斯金字塔高斯金子塔的構(gòu)建過程可分為兩步：（1）對(duì)圖像做高斯平滑；（2）對(duì)圖像做降采樣。 為了讓尺度體現(xiàn)其連續(xù)性，在簡(jiǎn)單下采樣的基礎(chǔ)上加上了高斯

2、濾波。一幅圖像可以產(chǎn)生幾組（octave）圖像，一組圖像包括幾層（interval）圖像。 高斯圖像金字塔共o組、s層，則有：尺度空間坐標(biāo)；ssub-level層坐標(biāo)；0初始尺度；S每組層數(shù)（一般為35）。當(dāng)圖像通過相機(jī)拍攝時(shí)，相機(jī)的鏡頭已經(jīng)對(duì)圖像進(jìn)行了一次初始的模糊，所以根據(jù)高斯模糊的性質(zhì)：-第0層尺度 -被相機(jī)鏡頭模糊后的尺度高斯金字塔的組數(shù):M、N分別為圖像的行數(shù)和列數(shù)高斯金字塔的組內(nèi)尺度與組間尺度:組內(nèi)尺度是指同一組（octave）內(nèi)的尺度關(guān)系，組內(nèi)相鄰層尺度化簡(jiǎn)為：組間尺度是指不同組直接的尺度關(guān)系，相鄰組的尺度可化為：最后可將組內(nèi)和組間尺度歸為：i金字塔組數(shù) n每組層數(shù)上一組圖像的底

3、層是由前一組圖像的倒數(shù)第二層圖像隔點(diǎn)采樣生成的。這樣可以保持尺度的連續(xù)性。差分高斯金字塔Lindeberg在文獻(xiàn)Scale-space theory: A basic tool for analysing structures at different scales指出尺度規(guī)范化的LoG算子具有真正的尺度不變性。LoG算子即（Laplacion of Gaussian）,可以由高斯函數(shù)梯度算子GOG構(gòu)建尺度規(guī)范化的GoG算子：尺度規(guī)范化的LoG算子：LOG算子與高斯核函數(shù)的關(guān)系通過推導(dǎo)可以看出，LOG算子與高斯核函數(shù)的差有直接關(guān)系，由此引入一種新的算子DOG（Difference of Gau

4、ssians），即高斯差分算子。DoG（Difference of Gaussian）函數(shù)：DoG在計(jì)算上只需相鄰尺度高斯平滑后圖像相減，因此簡(jiǎn)化了計(jì)算。對(duì)應(yīng)DOG算子，我們要構(gòu)建DOG金字塔我們可以通過高斯差分圖像看出圖像上的像素值變化情況。（如果沒有變化，也就沒有特征。特征必須是變化盡可能多的點(diǎn)。）DOG圖像描繪的是目標(biāo)的輪廓。在Lowe的論文中，將第0層的初始尺度定為1.6，圖片的初始尺度定為0.5，則圖像金字塔第0層的實(shí)際尺度為1.2 DoG的局部極值點(diǎn)檢測(cè)關(guān)鍵點(diǎn)是由DOG空間的局部極值點(diǎn)組成的。為了尋找DoG函數(shù)的極值點(diǎn)，每一個(gè)像素點(diǎn)要和它所有的相鄰點(diǎn)比較，看其是否比它的圖像域和尺度

5、域的相鄰點(diǎn)大或者小。中間的檢測(cè)點(diǎn)和它同尺度的8個(gè)相鄰點(diǎn)和上下相鄰尺度對(duì)應(yīng)的9×2個(gè)點(diǎn)共26個(gè)點(diǎn)比較，以確保在尺度空間和二維圖像空間都檢測(cè)到極值點(diǎn)。 在極值比較的過程中，每一組圖像的首末兩層是無法進(jìn)行極值比較的，為了滿足尺度變化的連續(xù)性，我們?cè)诿恳唤M圖像的頂層繼續(xù)用高斯模糊生成了3幅圖像，高斯金字塔有每組S+3層圖像。DOG金字塔每組有S+2層圖像。1.3 關(guān)鍵點(diǎn)精確定位由于DoG值對(duì)噪聲和邊緣較敏感,因此,在上面DoG尺度空間中檢測(cè)到局部極值點(diǎn)還要經(jīng)過進(jìn)一步的檢驗(yàn)才能精確定位為特征點(diǎn)。去除低對(duì)比度的極值點(diǎn)為了提高關(guān)鍵點(diǎn)的穩(wěn)定性，需要對(duì)尺度空間DoG函數(shù)進(jìn)行曲線擬合。利用DoG函數(shù)在尺

6、度空間的Taylor展開式：其極值點(diǎn)： 在計(jì)算過程中，分別對(duì)圖像的行、列及尺度三個(gè)量進(jìn)行了修正，其修正結(jié)果如下：求解得為修正值。將修正后的結(jié)果代入式 上式去除那些對(duì)比度較低的不穩(wěn)定極值點(diǎn)。Lowe的試驗(yàn)顯示，所有取值小于0.04的極值點(diǎn)均可拋棄（像素灰度值范圍0，1）。去除邊緣響應(yīng)僅僅去除低對(duì)比度的極值點(diǎn)對(duì)于極值點(diǎn)的對(duì)于特征點(diǎn)穩(wěn)定性是遠(yuǎn)遠(yuǎn)不夠的。DoG函數(shù)在圖像邊緣有較強(qiáng)的邊緣響應(yīng)，因此我們還需要排除邊緣響應(yīng)DoG函數(shù)的（欠佳的）峰值點(diǎn)在橫跨邊緣的方向有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。主曲率可以通過計(jì)算在該點(diǎn)位置尺度的2×2的Hessian矩陣得到，導(dǎo)數(shù)由采樣點(diǎn)相鄰差

7、來估計(jì)： 表示DOG金字塔中某一尺度的圖像x方向求導(dǎo)兩次。D的主曲率和H的特征值成正比，為了避免直接的計(jì)算這些特征值，而只是考慮它們的之間的比率。令 為最大特征值， 為最小的特征值，則 在兩特征值相等時(shí)達(dá)最小，隨r的增長(zhǎng)而增長(zhǎng)。Lowe論文中建議r取10。時(shí)將關(guān)鍵點(diǎn)保留，反之剔除。2 關(guān)鍵點(diǎn)描述2.1 關(guān)鍵點(diǎn)方向分配通過尺度不變性求極值點(diǎn)，可以使其具有縮放不變的性質(zhì)，利用關(guān)鍵點(diǎn)鄰域像素的梯度方向分布特性，我們可以為每個(gè)關(guān)鍵點(diǎn)指定方向參數(shù)方向，從而使描述子對(duì)圖像旋轉(zhuǎn)具有不變性。通過求每個(gè)極值點(diǎn)的梯度來為極值點(diǎn)賦予方向。像素點(diǎn)的梯度表示梯度幅值：梯度方向：方向直方圖的生成 確定關(guān)鍵點(diǎn)的方向采用梯度

8、直方圖統(tǒng)計(jì)法，統(tǒng)計(jì)以關(guān)鍵點(diǎn)為原點(diǎn)，一定區(qū)域內(nèi)的圖像像素點(diǎn)對(duì)關(guān)鍵點(diǎn)方向生成所作的貢獻(xiàn)。直方圖以每10度方向?yàn)橐粋€(gè)柱，共36個(gè)柱，柱所代表的方向?yàn)橄袼攸c(diǎn)梯度方向，柱的長(zhǎng)短代表了梯度幅值。根據(jù)Lowe的建議，直方圖統(tǒng)計(jì)半徑采用3*1.5*在直方圖統(tǒng)計(jì)時(shí)，每相鄰三個(gè)像素點(diǎn)采用高斯加權(quán)，根據(jù)Lowe的建議，模板采用0.25,0.5,0.25，并連續(xù)加權(quán)兩次。關(guān)鍵點(diǎn)的主方向與輔方向關(guān)鍵點(diǎn)主方向：極值點(diǎn)周圍區(qū)域梯度直方圖的主峰值,也是特征點(diǎn)方向關(guān)鍵點(diǎn)輔方向：在梯度方向直方圖中，當(dāng)存在另一個(gè)相當(dāng)于主峰值80%能量的峰值時(shí)，則將這個(gè)方向認(rèn)為是該關(guān)鍵點(diǎn)的輔方向。這可以增強(qiáng)匹配的魯棒性，Lowe的論文指出大概有15

9、%關(guān)鍵點(diǎn)具有多方向，但這些點(diǎn)對(duì)匹配的穩(wěn)定性至為關(guān)鍵。方向分配實(shí)現(xiàn)步驟1. 確定計(jì)算關(guān)鍵點(diǎn)直方圖的高斯函數(shù)權(quán)重函數(shù)參數(shù) ；2. 生成含有36柱的方向直方圖，梯度直方圖范圍0360度，其中每10度一個(gè)柱。由半徑為圖像區(qū)域生成；3. 對(duì)方向直方圖進(jìn)行兩次平滑；4. 求取關(guān)鍵點(diǎn)方向（可能是多個(gè)方向）；5. 對(duì)方向直方圖的Taylor展開式進(jìn)行二次曲線擬合，精確關(guān)鍵點(diǎn)方向；圖像的關(guān)鍵點(diǎn)已檢測(cè)完畢，每個(gè)關(guān)鍵點(diǎn)有三個(gè)信息：位置、尺度、方向；同時(shí)也就使關(guān)鍵點(diǎn)具備平移、縮放、和旋轉(zhuǎn)不變性。2.2 生成特征描述符描述的目的是在關(guān)鍵點(diǎn)計(jì)算后，用一組向量將這個(gè)關(guān)鍵點(diǎn)描述出來，這個(gè)描述子不但包括關(guān)鍵點(diǎn)，也包括關(guān)鍵點(diǎn)周圍

10、對(duì)其有貢獻(xiàn)的像素點(diǎn)。用來作為目標(biāo)匹配的依據(jù)，也可使關(guān)鍵點(diǎn)具有更多的不變特性，如光照變化、3D視點(diǎn)變化等。通過對(duì)關(guān)鍵點(diǎn)周圍圖像區(qū)域分塊，計(jì)算塊內(nèi)梯度直方圖，生成具有獨(dú)特性的向量，這個(gè)向量是該區(qū)域圖像信息的一種抽象，具有唯一性。下圖是一個(gè)SIFT描述子事例。其中描述子由2×2×8維向量表征，也即是2×2個(gè)8方向的方向直方圖組成。左圖的種子點(diǎn)由8×8單元組成。每一個(gè)小格都代表了特征點(diǎn)鄰域所在的尺度空間的一個(gè)像素，箭頭方向代表了像素梯度方向，箭頭長(zhǎng)度代表該像素的幅值。然后在4×4的窗口內(nèi)計(jì)算8個(gè)方向的梯度方向直方圖。繪制每個(gè)梯度方向的累加可形成一個(gè)種子

11、點(diǎn)，如右圖所示：一個(gè)特征點(diǎn)由4個(gè)種子點(diǎn)的信息所組成。Lowe實(shí)驗(yàn)結(jié)果表明：描述子采用4×4×8128維向量表征，綜合效果最優(yōu)（不變性與獨(dú)特性）。128維關(guān)鍵點(diǎn)描述子（就是特征描述符）生成步驟1. 確定計(jì)算描述子所需的圖像區(qū)域描述子梯度方向直方圖由關(guān)鍵點(diǎn)所在尺度的模糊圖像計(jì)算產(chǎn)生。圖像區(qū)域的半徑通過下式計(jì)算： 是關(guān)鍵點(diǎn)所在組（octave）的組內(nèi)尺度，2. 將坐標(biāo)移至關(guān)鍵點(diǎn)主方向那么旋轉(zhuǎn)角度后新坐標(biāo)為： 3.在圖像半徑區(qū)域內(nèi)對(duì)每個(gè)像素點(diǎn)求其梯度幅值和方向，然后對(duì)每個(gè)梯度幅值乘以高斯權(quán)重參數(shù)，生成方向直方圖。 該點(diǎn)與關(guān)鍵點(diǎn)的列距離 該點(diǎn)與關(guān)鍵點(diǎn)的行距離 等于描述子窗口寬度 &#

12、215;直方圖列數(shù)（取4）的一半4.在窗口寬度為2X2的區(qū)域內(nèi)計(jì)算8個(gè)方向的梯度方向直方圖，繪制每個(gè)梯度方向的累加值，即可形成一個(gè)種子點(diǎn)。然后再在下一個(gè)2X2的區(qū)域內(nèi)進(jìn)行直方圖統(tǒng)計(jì)，形成下一個(gè)種子點(diǎn)，共生成16個(gè)種子點(diǎn)。5.描述子向量元素門限化及門限化后的描述子向量規(guī)范化。描述子向量元素門限化：方向直方圖每個(gè)方向上梯度幅值限制在一定門限值以下（門限一般取0.2）。描述子向量元素規(guī)范化：為得到的128描述子向量 為規(guī)范化后的向量關(guān)鍵點(diǎn)描述子向量的規(guī)范化正是可去除滿足此模型的光照影響。對(duì)于圖像灰度值整體漂移 ，圖像各點(diǎn)的梯度是鄰域像素相減得到，所以也能去除。3 關(guān)鍵點(diǎn)匹配分別對(duì)模板圖（參考圖，re

13、ference image）和實(shí)時(shí)圖（觀測(cè)圖，observation image）建立關(guān)鍵點(diǎn)描述子集合。目標(biāo)的識(shí)別是通過兩點(diǎn)集內(nèi)關(guān)鍵點(diǎn)描述子的比對(duì)來完成。具有128維的關(guān)鍵點(diǎn)描述子的相似性度量采用歐式距離。模板圖中關(guān)鍵點(diǎn)描述子：實(shí)時(shí)圖中關(guān)鍵點(diǎn)描述子：任意兩描述子相似性度量：要得到配對(duì)的關(guān)鍵點(diǎn)描述子，需滿足：關(guān)鍵點(diǎn)的匹配可以采用窮舉法來完成，但是這樣耗費(fèi)的時(shí)間太多，一般都采用一種叫k-d樹的數(shù)據(jù)結(jié)構(gòu)來完成搜索。搜索的內(nèi)容是以目標(biāo)圖像的關(guān)鍵點(diǎn)為基準(zhǔn)，搜索與目標(biāo)圖像的特征點(diǎn)最鄰近的原圖像特征點(diǎn)和次鄰近的原圖像特征點(diǎn)。Kd樹是一個(gè)平衡二叉樹關(guān)鍵點(diǎn)匹配并不能標(biāo)志著算法的結(jié)束，因?yàn)樵谄ヅ涞倪^程中存在著大量的錯(cuò)配點(diǎn)。圖中交叉的綠線為錯(cuò)配點(diǎn)4 消除錯(cuò)配點(diǎn)RANSAC（Random Sample Consensus，