【導(dǎo)讀】速度也隨之加快。從海量數(shù)據(jù)中迅速檢索出有用信息成為人們的迫切需。因此，圖像檢索作為一種能從海量圖像中迅速查找到需要圖像的技術(shù)。很快成為人們研究的熱點(diǎn)。好的獨(dú)特性和魯棒性而受到人們的普遍關(guān)注。本文給出了一種基于SIFT. 其是SIFT算法的基本原理和各自的優(yōu)缺點(diǎn)。算法作為最終的特征提取方案，最后實(shí)現(xiàn)了一個(gè)實(shí)驗(yàn)性的CBIR系統(tǒng)。的魯棒性，提出的基于SIFT算法的CBIR系統(tǒng)方案具有良好的效果。

　　

【正文】 DoG 函數(shù)進(jìn)行曲線擬合。利用 DoG 函數(shù)在尺度空間的 Taylor 展開式： 221() 2T TDDD X D X X XXX??? ? ? (311) 式中 D(X)=D(x,y, ? )， ( , , )TX x y??，對(duì)式 311 求一階導(dǎo)數(shù)，并令倒數(shù)為零，計(jì)算可得特征點(diǎn)的精確位置： 212DDX XX?? ???? (312) 將結(jié)果帶入式 311 只取前兩項(xiàng)得： 1( ) ( , , ) 2 TDD X D x y XX???? ? ? ? (313) 上式去除那些對(duì) 比度較低的不穩(wěn)定極值點(diǎn)。 Lowe 的試驗(yàn)顯示，所有()DX? 取值小于 的極值點(diǎn)均可拋棄（像素灰度值范圍 [0,1]）。 僅僅去除低對(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)相鄰差來估計(jì)： xx xyxy yyDDH DD??????? (316) 式中， xxD 表示 DOG 金字塔中某一尺度的圖像 x 方向求導(dǎo)兩次。 D 的主曲率和 H 的特征值成正比，為了避免直接的計(jì)算這些特征值，只考慮它們的之間的比率。令 ? 為最大特征值， ? 為最小特征值，則有： 2 2 22( ) ( ) ( 1 )()( ) ( )x x y y x x y y x yT r H rrD e t H rT r H D D D e t H D D D? ? ? ?? ? ? ? ???? ? ? ? ? (317) 2( 1) /rr? 在兩特征值相等時(shí)達(dá)最小，隨 r 的增長(zhǎng)而增長(zhǎng)。 Lowe 論文哈爾濱理工大學(xué)學(xué)士學(xué)位論文 21 中建議 r 取 10。如果 22( ) ( 1)()Tr H rD et H r?? (318) 則保留關(guān)鍵點(diǎn)，否則將該關(guān)鍵點(diǎn)剔除。至此， SIFT 算法第二步完成。 特征點(diǎn)方向賦值 通過尺度不變性求極值點(diǎn)，可 以使其具有縮放不變的性質(zhì)，利用關(guān)鍵點(diǎn)鄰域像素的梯度方向分布特性，我們可以為每個(gè)關(guān)鍵點(diǎn)指定方向參數(shù)方向，從而可以使描述子對(duì)圖像旋轉(zhuǎn)具有不變性。 我們使用圖像的梯度直方圖法求關(guān)鍵點(diǎn)局部結(jié)構(gòu)的穩(wěn)定方向。 在前文中，精確定位關(guān)鍵點(diǎn)后也找到改特征點(diǎn)的尺度值 σ，根據(jù)這一尺度值，得到最接近這一尺度值的高斯圖像 。 ( , ) ( , , ) ( , )L x y G x y I x y? ? ? (318) 使用有限差分，計(jì)算以關(guān)鍵點(diǎn)為中心 、 以 3 為半徑的區(qū)域內(nèi)圖像梯度的幅角和幅值，公式如下 。 22( , ) ( ( 1 , ) ( 1 , ) ) ( ( , 1 ) ( , 1 ) )( , 1 ) ( , 1 )( , ) a r c ta n( 1 , ) ( 1 , )m x y L x y L x y L x y L x yL x y L x yxyL x y L x y?? ? ? ? ? ? ? ???? ? ?? ??? ? ??? (320) 在完成關(guān)鍵點(diǎn)鄰域內(nèi)高斯圖像梯度計(jì)算后，使用直方圖統(tǒng)計(jì)鄰域內(nèi)像素對(duì)應(yīng)的梯度方向和幅值。梯度方向直方圖的橫軸是梯度方向角，縱軸是剃度方向角對(duì)應(yīng)的梯度幅值累加值。梯度方向直方圖將 0176。~360176。的范圍分為 36 個(gè)柱，每 10176。為一個(gè)柱。 圖 38 是從高斯圖像上求取梯度，再由梯度得到梯度方向直方圖的例圖。 主 方 向 圖 35 用直方圖統(tǒng)計(jì)像元梯度 在計(jì)算直方圖時(shí)，每個(gè)加入直方 圖的采樣點(diǎn)都使 要 用圓形高斯函數(shù)函數(shù)進(jìn)行加權(quán)處理，也就是進(jìn)行高斯平滑。這主要是因?yàn)?SIFT 算法只考慮了尺度和旋轉(zhuǎn)不變形，沒有考慮仿射不變性。通過高斯平滑，可以使關(guān)鍵哈爾濱理工大學(xué)學(xué)士學(xué)位論文 22 點(diǎn)附近的梯度幅值有較大權(quán)重，從而部分彌補(bǔ)沒考慮仿射不變形產(chǎn)生的特征點(diǎn)不穩(wěn)定。通常離散的梯度直方圖要進(jìn)行插值擬合處理，以求取更精確的方向角度值。 直方圖峰值代表該關(guān)鍵點(diǎn)處鄰域內(nèi)圖像梯度的主方向，也就是該關(guān)鍵點(diǎn)的主方向。在梯度方向直方圖中，當(dāng)存在另一個(gè)相當(dāng)于主峰值 80%能量的峰值時(shí)，則將這個(gè)方向認(rèn)為是該關(guān)鍵點(diǎn)的輔方向 ， 如圖 39 所示 。所以一個(gè)關(guān)鍵點(diǎn)可 能檢測(cè)得到多個(gè)方向，這可以增強(qiáng)匹配的魯棒性。 Lowe 的論文指出大概有 15%關(guān)鍵點(diǎn)具有多方向，但這些點(diǎn)對(duì)匹配的穩(wěn)定性至為關(guān)鍵 。 獲得圖像關(guān)鍵點(diǎn)主方向后，每個(gè)關(guān)鍵點(diǎn)有三個(gè)信息 (x,y,σ,θ)：位置 、尺度、方向。由此我們可以確定一個(gè) SIFT 特征區(qū)域。通常使用一個(gè)帶箭頭的圓或直接使用箭頭表示 SIFT 區(qū)域的三個(gè)值：中心表示特征點(diǎn)位置 ，半徑表示關(guān)鍵點(diǎn)尺度（ r=） ,箭頭表示主方向。具有多個(gè)方向的關(guān)鍵點(diǎn)可以復(fù)制成多份，然后將方向值分別賦給復(fù)制后的關(guān)鍵點(diǎn)。 至此，圖像的關(guān)鍵點(diǎn)已檢測(cè)完畢，每個(gè)關(guān)鍵點(diǎn)有三個(gè)信息：位置、 尺度、方向；同時(shí)也就使關(guān)鍵點(diǎn)具備平移、縮放、和旋轉(zhuǎn)不變性。 關(guān)鍵點(diǎn)描述 關(guān)鍵點(diǎn)描述的目的是在關(guān)鍵點(diǎn)計(jì)算后，用一組向量將這個(gè)關(guān)鍵點(diǎn)描述出來，這個(gè)描述子不但用來描述關(guān)鍵點(diǎn)，也包括關(guān)鍵點(diǎn)周圍對(duì)其有貢獻(xiàn)的像元的信息。描述子除了是進(jìn)行特征匹配的依據(jù)外，還能使使關(guān)鍵點(diǎn)具有更多的不變特性，如光照變化、 3D 視點(diǎn)變化等。 SIFT 特征描述子的生成有四個(gè)步驟，現(xiàn)總結(jié)如下： 特征描述子與關(guān)鍵點(diǎn)所在尺度有關(guān)，因此對(duì)梯度的求取應(yīng)在特征點(diǎn)對(duì)應(yīng)的高斯圖像上進(jìn)行。將關(guān)鍵點(diǎn)附近劃分成 dd 個(gè)子區(qū)域，每個(gè)子 區(qū)域尺寸為 mσ 個(gè)像元（ d=4， m=3， σ 為尺特征點(diǎn)的尺度值）。考慮到實(shí)際計(jì)算時(shí)需要雙線性插值，故計(jì)算的圖像區(qū)域?yàn)?mσ(d+1)，再考慮旋轉(zhuǎn)，則實(shí)際計(jì)算的圖像區(qū)域?yàn)?2 ( 1)md??。 通過對(duì)關(guān)鍵點(diǎn)周圍圖像區(qū)域分塊，計(jì)算塊內(nèi)梯度直方圖，生成具有獨(dú)特的向量，這個(gè)向量是該區(qū)域圖像信息的一種抽象，具有唯一性。 為了保證特征矢量具有旋轉(zhuǎn)不變性， 需 要以特征點(diǎn)為中心， 將坐標(biāo)軸在 附近鄰域內(nèi)旋轉(zhuǎn) θ 角， 使其與特征點(diǎn)主 方向想同，如圖 36 所示 。 旋轉(zhuǎn)后區(qū)域內(nèi)采樣點(diǎn)新的坐標(biāo)為 ： 39。 c os si n39。 si n c osxxyy???? ? ? ? ? ??? ? ? ? ? ?? ? ? ? ? ? (321) 哈爾濱理工大學(xué)學(xué)士學(xué)位論文 23 YXYX 圖 36 將坐標(biāo)變換到特正點(diǎn)的主方向上 將旋轉(zhuǎn)后區(qū)域劃分為 dd 個(gè)子區(qū)域（每個(gè)區(qū)域間隔為 mσ 像元），在子區(qū)域內(nèi)計(jì)算 8 個(gè)方向的梯度直方圖，繪制每個(gè)方向梯度方向的累加值，形成一個(gè)種子點(diǎn)。 與求主方向不同的是，此時(shí)，每個(gè)子區(qū)域梯度方向直方圖將 0176。~360176。劃分為 8 個(gè)方向區(qū)間，每個(gè)區(qū)間為 45176。即每個(gè)種子點(diǎn)有 8 個(gè)方向區(qū)間的梯 度強(qiáng)度信息。 Lowe 實(shí)驗(yàn)結(jié)果表明：描述子采用 4 4 8＝ 128 維向量表征，綜合效果最優(yōu)（不變性與獨(dú)特性）。 圖 37 由特征點(diǎn)鄰域像元梯度求 128 維特征矢量 在生成特正點(diǎn)的描述向量后還要對(duì)描述向量作進(jìn)一步的處理，即門限化和規(guī)范化。描述子向量元素門限化是指方向直方圖每個(gè)方向上梯度幅值限制在一定門限值以下（門限一般取 ）。 設(shè) 1 2 128( , ,..., )W w w w? 為得到的 128 維特征向量， 1 2 128( , ,..., )L l l l? 為規(guī)哈爾濱理工大學(xué)學(xué)士學(xué)位論文 24 范后的特征向量，則描述子向量規(guī)范化的公式為： 1281/ 1 , 2 , . . . , 1 2 8j j iil w w j???? (322) 關(guān)鍵點(diǎn)描述子向量的規(guī)范化正是可去除滿足此模型的光照影響。對(duì)于圖像灰度值整體漂移 ，圖像各點(diǎn)的梯度是鄰域像素相減到，所以也能去除。至此 SIFT 算法所有步驟全部完成，至于它的特征匹配方法在第二章第二節(jié)里已分析完畢，這里不再重復(fù)。 SIFT 算法性能實(shí)驗(yàn) 為了進(jìn)一步驗(yàn)證 SIFT 算法的性能，本文設(shè)計(jì)了一 個(gè) 性能 實(shí)驗(yàn)：使用matlab 編程實(shí)現(xiàn) SIFT 算法，然后對(duì)多組不同類型的圖片進(jìn)行特征提取和匹配， 以 測(cè)試 SIFT 算法對(duì)平移、旋轉(zhuǎn)、遮擋、視角、噪聲和亮度變化的魯棒性，并 統(tǒng)計(jì) SIFT 算法的特征提取及匹配所耗費(fèi)的時(shí)間，實(shí)驗(yàn)結(jié)果如下 。 圖 38 不同尺度下的特征檢測(cè) 圖 311 為不同尺度下同一物體的兩幅圖像，圖像中特征點(diǎn)有綠色箭頭標(biāo)示出來，箭頭的方向?yàn)樘卣c(diǎn)的主方向，箭頭長(zhǎng)度表示特征點(diǎn)的尺度。圖中左邊的圖片尺度較小，圖片攜帶大量的細(xì)節(jié)信息，因此檢測(cè)出更多的特征點(diǎn)，特征點(diǎn)數(shù)量為 1349 個(gè)；而又變得圖像尺度較大，反 映的更多是圖像的整體特征，因此特征點(diǎn)較少，為 395 個(gè)。 哈爾濱理工大學(xué)學(xué)士學(xué)位論文 25 圖 39 不同尺度下的圖像匹配 圖 312 是上述兩幅圖像的特征匹配結(jié)果，相同的特征點(diǎn)被綠色的細(xì)線連接起來。因?yàn)?SIFT 算法是在多尺度空間中進(jìn)行特征提取的， incident 雖然兩幅圖像的尺度不同，但左圖中依然存在與右圖大尺度圖像中相同的特征點(diǎn)，圖中相匹配的特征點(diǎn)數(shù)量為 197 個(gè)。 圖 310 旋轉(zhuǎn)條件下的 SIFT 特征匹配 圖 313 為旋轉(zhuǎn)條件下的 SIFT 特征匹配結(jié)果，再上一章我們已經(jīng)分析過， SIFT 算法在生成特征描述向量前將圖像坐標(biāo)旋轉(zhuǎn)到了特征點(diǎn)的 主方向上，這樣即便圖像發(fā)生旋轉(zhuǎn)，我們依然可以進(jìn)行特征匹配，圖中匹配成功哈爾濱理工大學(xué)學(xué)士學(xué)位論文 26 的特征點(diǎn)數(shù)量為 585 處。 圖 311 視角變化下的 SIFT 特征匹配 圖 312 噪聲條件下的 SIFT 算法特征匹配 圖 314 和 315 分別是 SIFT 算法在視角變化和噪聲條件下的結(jié)果，其中圖 314 中的視角轉(zhuǎn)變超過 60 度，圖 315 中右圖加入了密度為 的椒鹽噪聲。從圖中我們可以看出，雖然 SIFT 算法在這兩種條件下匹配成哈爾濱理工大學(xué)學(xué)士學(xué)位論文 27 功的特征點(diǎn)對(duì)數(shù)有所下降，但途中關(guān)鍵的特征點(diǎn)依然能夠正確匹配，表現(xiàn)出良好的魯棒性。 圖 313 亮度變化下 的 SIFT 特征匹配 圖 314 旋轉(zhuǎn)、遮蓋、平移及尺度變化條件下的 SIFT 算法特征匹配 圖 313 是 SIFT 算法在亮度變化的條件下的特征匹配結(jié)果，因?yàn)?SIFT算法在生成特正點(diǎn)的描述向量后，對(duì)其進(jìn)行了門限化和規(guī)范化，這樣圖像哈爾濱理工大學(xué)學(xué)士學(xué)位論文 28 整灰體度值漂移對(duì)特征匹配的影響幾乎被完全消除了。實(shí)驗(yàn)結(jié)果表明，亮度變化對(duì) SIFT 算法圖像匹配的影響很小，算法在左圖中共檢測(cè)出 1349 個(gè)特征點(diǎn)，右圖檢測(cè)出 1189 個(gè)特征點(diǎn)，成功匹配的特征點(diǎn)對(duì)數(shù)為 1099 對(duì)。而圖 314 則是各種條件綜合作用下 SIFT 算法特征匹配結(jié)果，我們可以看出，在圖像發(fā) 生旋轉(zhuǎn)、平移、尺度變化甚至遮蓋的條件下， SIFT 算法依然能準(zhǔn)確的匹配和定位目標(biāo)。 實(shí)驗(yàn)除了對(duì) SIFT 算法的穩(wěn)定性進(jìn)行驗(yàn)證外，還對(duì)其特征提取及匹配的特性和時(shí)間進(jìn)行了統(tǒng)計(jì)。實(shí)驗(yàn)對(duì)簡(jiǎn)單、中等、復(fù)雜、低對(duì)比度四組紋理圖像進(jìn)行特征提取和匹配，每組 20 張圖片，匹配圖像為每幅圖騙的縮略圖，記錄檢測(cè)出的特征點(diǎn)數(shù)量和程序運(yùn)行時(shí)間。限于篇幅，僅將幾組典型圖像的 實(shí)驗(yàn) 結(jié)果列出，如表 31 所示 。 表 31 各類圖像的 SIFT 特征提取及匹配時(shí)間 圖片編號(hào) L1 S1 S2 M1 M2 M3 F1 F2 圖片類型 低對(duì)比度 簡(jiǎn)單紋理 簡(jiǎn)單紋理 中等紋理 中等紋理 中等紋理 復(fù)雜紋理 復(fù)雜紋理 縮略圖 特征提取時(shí)間/ms 457 457 471 541 562 541 697 963 匹配時(shí)間 /ms 0 1 1 5 7 7 27 277 特征點(diǎn)數(shù)量 /個(gè) 0 20 32 139 173 203 415 1010 從表中數(shù)據(jù)可以看你出， SIFT 算法對(duì)低對(duì)比度圖像的特征提取能力十分有限，如表中圖 L1 的檢索結(jié)果所示。另外，對(duì)比圖 S1（或 S2）與圖F1（或 F2）的檢索結(jié)果， SIFT 算法對(duì)紋理復(fù)雜、細(xì)節(jié)豐富 的圖像具有良好的特征提取能力，如圖 F F2，而對(duì)紋理簡(jiǎn)單、灰度值變化緩慢的圖像則往往不能獲取足夠的特征點(diǎn)，如圖 S S2。并且，對(duì) SIFT 算法耗費(fèi)時(shí)間進(jìn)行成分分析，發(fā)現(xiàn) SIFT 算法在特征提取上耗費(fèi)了大量的時(shí)間，而特征匹配的耗費(fèi)時(shí)間則很少。 SIFT 算法在 CBIR 系統(tǒng)中的應(yīng)用 在上一節(jié)的實(shí)驗(yàn)中我們已經(jīng)驗(yàn)證： SIFT 算法是一種良好的局部特征描述子，對(duì)平移、尺度、旋轉(zhuǎn)、噪聲、視角變化和亮度變化具有良好的不變性，能對(duì)兩幅圖像中的同一對(duì)象進(jìn)行準(zhǔn)確的匹配。這些特點(diǎn)使 SIFT 算法在對(duì)目標(biāo)圖像的準(zhǔn)確查找中具有其他算法所沒 有的優(yōu)勢(shì)。但是， SIFT 算法在對(duì)近似圖像的模糊檢索中則有較大的局限性，如下圖所示： 哈爾濱理工大學(xué)學(xué)士學(xué)位論文 29 (a) (b) 圖 3