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

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

2、讓尺度體現(xiàn)其連續(xù)性，在簡單下采樣的基礎(chǔ)上加上了高斯濾波。一幅圖像可以產(chǎn)生幾組(octave)圖像，一組圖像包括幾層(interval )圖像。高斯圖像金字塔共 o組、s層，則有：(x 汀(yI x, yyj/LOctave 1Octave 5Octave 4Octave 3Octave 2s S. -o1(s)oC2 Sd尺度空間坐標(biāo)；ssub-level層坐標(biāo)；d 0初始尺度；S每組層數(shù)(一般為35)。當(dāng)圖像通過相機(jī)拍攝時(shí)，相機(jī)的鏡頭已經(jīng)對(duì)圖像進(jìn)行了一次初始的模糊，所以根據(jù)高斯模 糊的性質(zhì)：0initinitprepreinit -第0層尺度pre -被相機(jī)鏡頭模糊后的尺度高斯金字塔的組數(shù)：

3、o log2 min M , N 3 M、N分別為圖像的行數(shù)和列數(shù)高斯金字塔的組尺度與組間尺度：組尺度是指同一組(octave)的尺度關(guān)系，組相鄰層尺度化簡為：組間尺度是指不同組直接的尺度關(guān)系，相鄰組的尺度可化為：ss Ss(s)°g2Sod ” 2 o0S最后可將組和組間尺度歸為：2i 1( ,k ,k2 ,L kn 1 )k 2 Si 金字塔組數(shù) n 每組層數(shù)上一組圖像的底層是由前一組圖像的倒數(shù)第二層圖像隔 點(diǎn)采樣生成的。這樣可以保持 尺度的連續(xù)性。差分高斯金字塔Lindeberg 在文獻(xiàn)Scale-space theory: A basic tool for analysing

4、 structures at different scales指出尺度規(guī)化的LoG算子具有真正的尺度不變性。LoG 算子即（Laplacion of Gaussian)，可以由高斯函數(shù)梯度算子 GOG構(gòu)建尺度規(guī)化的GoG算子：2亠2g2g2g2 2x y尺度規(guī)化的LoG算子：2 2GLOG算子與高斯核函數(shù)的關(guān)系2 2 Gauss(x, y, k ) Gauss(x, y,) LOG(x,y, )GG x, y,k G x, y, k 12 2G通過推導(dǎo)可以看出，LOG算子與高斯核函數(shù)的差有直接關(guān)系，由此引入一種新的算子DOG ( Differenee of Gaussians )，即高斯差分算

5、子。DoG ( Differenee of Gaussian )函數(shù)：L x,y, G x, y, * I x, yD x, y, G x, y,k G x, y, * I x, yL x, y,k L x, y,DoG在計(jì)算上只需相鄰尺度高斯平滑后圖像相減，因此簡化了計(jì)算。對(duì)應(yīng)DOG算子，我們要構(gòu)建 DOG金字塔話 n DOG)我們可以通過高斯差分圖像看出圖像上的像素值變化情況。（如果沒有變化，也就沒有特征。特征必須是變化盡可能多的點(diǎn)。）DOG圖像描繪的是目標(biāo)的輪廓。在Lowe的論文中，將第0層的初始尺度定為1.6，圖片的初始尺度定為 0.5,則圖像金 字塔第0層的實(shí)際尺度為1.6 1.6

6、0.5 0.51.521.2 DoG的局部極值點(diǎn)檢測關(guān)鍵點(diǎn)是由DOG空間的局部極值點(diǎn)組成的。為了尋找DoG函數(shù)的極值點(diǎn)，每一個(gè)像素點(diǎn)要和它所有的相鄰點(diǎn)比較，看其是否比它的圖像域和尺度域的相鄰點(diǎn)大或者小。中間的檢測點(diǎn)和它同尺度的8個(gè)相鄰點(diǎn)和上下相鄰尺度對(duì)應(yīng)的9X2個(gè)點(diǎn)共26個(gè)點(diǎn)比較，以確保在尺度空間和二維圖像空間都檢測到極值點(diǎn)。在極值比較的過程中，每一組圖像的首末兩層是無法進(jìn)行極值比較的，為了滿足尺度 變化的連續(xù)性，我們在每一組圖像的頂層繼續(xù)用高斯模糊生成了3幅圖像，高斯金字塔有每組S+3層圖像。DOG金字塔每組有 S+2層圖像。1.3關(guān)鍵點(diǎn)精確定位由于DoG值對(duì)噪聲和邊緣較敏感，因此，在上面D

7、oG尺度空間中檢測到局部極值點(diǎn)還要 經(jīng)過進(jìn)一步的檢驗(yàn)才能精確定位為特征點(diǎn)。去除低對(duì)比度的極值點(diǎn)DoG函數(shù)進(jìn)行曲線擬合。利用DoG函數(shù)為了提高關(guān)鍵點(diǎn)的穩(wěn)定性，需要對(duì)尺度空間在尺度空間的 Taylor展開式:D X D-DX 其極值點(diǎn)：X x, y, T在計(jì)算過程中，分別對(duì)圖像的行、列及尺度三個(gè)量進(jìn)行了修正，其修正結(jié)果如下:£TX求解得x 2XT 2DX為修正值。 將修正后的結(jié)果代入式DTX!xt2dtX2上式去除那些對(duì)比度較低的不穩(wěn)定極值點(diǎn)。Lowe的試驗(yàn)顯示，所有取值小于0.04的極值點(diǎn)均可拋棄（像素灰度值圍0, 1）。去除邊緣響應(yīng)DoG函數(shù)僅僅去除低對(duì)比度的極值點(diǎn)對(duì)于極值點(diǎn)的對(duì)于特

8、征點(diǎn)穩(wěn)定性是遠(yuǎn)遠(yuǎn)不夠的。在圖像邊緣有較強(qiáng)的邊緣響應(yīng)，因此我們還需要排除邊緣響應(yīng)DoG函數(shù)的（欠佳的）峰值點(diǎn)在橫跨邊緣的方向有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。主曲率可以通過計(jì)算在該點(diǎn)位置尺度的2X 2的Hessian矩陣得到，導(dǎo)數(shù)由采樣點(diǎn)相鄰差來估計(jì):DxxDxyDxyDyy表示DOG金字塔中某一尺度的圖像 x方向求導(dǎo)兩次。D的主曲率和H的特征值成正比，為了避免直接的計(jì)算這些特征值，而只是考慮它們 的之間的比率。令為最大特征值，為最小的特征值，則Tr HDxx Dyy2Tr HDet H2Tr HDxxDyy2DxyrDxy21Det H在兩特征值相等時(shí)達(dá)最小，隨rr的增長而增長

9、。Lowe論文中建議r取10。2時(shí)將關(guān)鍵點(diǎn)保留，反之剔除。Det H2關(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)的梯度表示gradl x, y,x y/ 2 2梯度幅值：m x, yL x 1,y Lx 1, yL x, y 1 L x, y 11 L x, y 1 L x, y 1梯度方向：x, y tanLx 1, y L x 1,y方向直方圖的生成確定關(guān)鍵點(diǎn)的方向采用梯度直方圖統(tǒng)計(jì)法，統(tǒng)計(jì)

10、以關(guān)鍵點(diǎn)為原點(diǎn)，一定區(qū)域的圖像像 素點(diǎn)對(duì)關(guān)鍵點(diǎn)方向生成所作的貢獻(xiàn)。直方圖以每10度方向?yàn)橐粋€(gè)柱，共 36個(gè)柱，柱所代表的方向?yàn)橄袼攸c(diǎn)梯度方向，柱 的長短代表了梯度幅值。根據(jù)Lowe的建議，直方圖統(tǒng)計(jì)半徑采用3*1.5* d在直方圖統(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%關(guān)鍵點(diǎn)

11、具有多方向，但這些點(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)已檢測完畢，每個(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)周圍對(duì)其有貢獻(xiàn)

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

13、成。關(guān)鍵點(diǎn)描述子斗*斗*斗*Lowe實(shí)驗(yàn)結(jié)果表明：描述子采用4X 4X 8= 128維向量表征，綜合效果最優(yōu)（不變性與獨(dú)特性）。128維關(guān)鍵點(diǎn)描述子（就是特征描述符）生成步驟1.確定計(jì)算描述子所需的圖像區(qū)域描述子梯度方向直方圖由關(guān)鍵點(diǎn)所在尺度的模糊圖像計(jì)算產(chǎn)生。圖像區(qū)域的半徑通過 下式計(jì)算：_3 oct V2 d 11radius2oct是關(guān)鍵點(diǎn)所在組（octave）的組尺度,2.那么旋轉(zhuǎn)角度后新坐標(biāo)為:x>3在圖像半徑區(qū)域?qū)γ總€(gè)像素點(diǎn)求其梯度幅值和方向, 度幅值乘以高斯權(quán)重參數(shù)，生成方向直方圖。cossinsincosy然后對(duì)每個(gè)梯ykexp2 wdr1-dcdc1-drweight

14、grad I x, yxk該點(diǎn)與關(guān)鍵點(diǎn)的列距離 yk該點(diǎn)與關(guān)鍵點(diǎn)的行距離x直方圖列數(shù)（取4）的一半w等于描述子窗口寬度34在窗口寬度為 2X2的區(qū)域計(jì)算8個(gè)方向的梯度方向直方圖，繪制每個(gè)梯度方向的累 加值，即可形成一個(gè)種子點(diǎn)。然后再在下一個(gè)2X2的區(qū)域進(jìn)行直方圖統(tǒng)計(jì)，形成下一個(gè)種子點(diǎn)，共生成16個(gè)種子點(diǎn)。5描述子向量元素門限化及門限化后的描述子向量規(guī)化。描述子向量元素門限化：方向直方圖每個(gè)方向上梯度幅值限制在一定門限值以下（門限一 般取0.2）。描述子向量元素規(guī)化：WLljW,W2丄，呵28丄128為得到的128描述子向量 為規(guī)化后的向量j 1,2 丄 128關(guān)鍵點(diǎn)描述子向量的規(guī)化正是可去除滿

15、足此模型的光照影響。對(duì)于圖像灰度值整體漂 移，圖像各點(diǎn)的梯度是鄰域像素相減得到，所以也能去除。3關(guān)鍵點(diǎn)匹配分別對(duì)模板圖（參考圖， referenee image ）和實(shí)時(shí)圖（觀測圖， observation image ）建 立關(guān)鍵點(diǎn)描述子集合。目標(biāo)的識(shí)別是通過兩點(diǎn)集關(guān)鍵點(diǎn)描述子的比對(duì)來完成。具有128維的關(guān)鍵點(diǎn)描述子的相似性度量采用歐式距離。模板圖中關(guān)鍵點(diǎn)描述子:實(shí)時(shí)圖中關(guān)鍵點(diǎn)描述子：任意兩描述子相似性度量:SiSi1 , Si2 丄,si128d R,S2Sj要得到配對(duì)的關(guān)鍵點(diǎn)描述子，d R,Sj需滿足：Threshold實(shí)時(shí)圖中距離R最近的點(diǎn)S實(shí)時(shí)圖中距離R的次最近點(diǎn)Sp關(guān)鍵點(diǎn)的匹配可以采用窮舉法來完成，但是這樣耗費(fèi)的時(shí)間太多，一般都采用一種叫 k-d樹的數(shù)據(jù)結(jié)構(gòu)來完成搜索。搜索的容是以目標(biāo)圖像的關(guān)鍵點(diǎn)為基準(zhǔn)，搜索與目標(biāo)圖像的特征點(diǎn)最鄰近的原圖像特征點(diǎn)和次鄰近的原圖像特征點(diǎn)。Kd樹是一個(gè)平衡二叉樹X3,1關(guān)鍵點(diǎn)匹配并不能標(biāo)志著算法的結(jié)束，因?yàn)樵谄ヅ涞倪^程中存在著大