【正文】 但是， SIFT 算法在對近似圖像的模糊檢索中則有較大的局限性，如下圖所示： 哈爾濱理工大學(xué)學(xué)士學(xué)位論文 29 (a) (b) 圖 3。 SIFT 算法在 CBIR 系統(tǒng)中的應(yīng)用 在上一節(jié)的實驗中我們已經(jīng)驗證： SIFT 算法是一種良好的局部特征描述子，對平移、尺度、旋轉(zhuǎn)、噪聲、視角變化和亮度變化具有良好的不變性，能對兩幅圖像中的同一對象進(jìn)行準(zhǔn)確的匹配。另外，對比圖 S1（或 S2）與圖F1（或 F2）的檢索結(jié)果， SIFT 算法對紋理復(fù)雜、細(xì)節(jié)豐富 的圖像具有良好的特征提取能力，如圖 F F2，而對紋理簡單、灰度值變化緩慢的圖像則往往不能獲取足夠的特征點，如圖 S S2。限于篇幅，僅將幾組典型圖像的 實驗 結(jié)果列出，如表 31 所示 。 實驗除了對 SIFT 算法的穩(wěn)定性進(jìn)行驗證外，還對其特征提取及匹配的特性和時間進(jìn)行了統(tǒng)計。實驗結(jié)果表明，亮度變化對 SIFT 算法圖像匹配的影響很小，算法在左圖中共檢測出 1349 個特征點，右圖檢測出 1189 個特征點，成功匹配的特征點對數(shù)為 1099 對。從圖中我們可以看出，雖然 SIFT 算法在這兩種條件下匹配成哈爾濱理工大學(xué)學(xué)士學(xué)位論文 27 功的特征點對數(shù)有所下降，但途中關(guān)鍵的特征點依然能夠正確匹配，表現(xiàn)出良好的魯棒性。 圖 310 旋轉(zhuǎn)條件下的 SIFT 特征匹配 圖 313 為旋轉(zhuǎn)條件下的 SIFT 特征匹配結(jié)果，再上一章我們已經(jīng)分析過， SIFT 算法在生成特征描述向量前將圖像坐標(biāo)旋轉(zhuǎn)到了特征點的 主方向上，這樣即便圖像發(fā)生旋轉(zhuǎn)，我們依然可以進(jìn)行特征匹配，圖中匹配成功哈爾濱理工大學(xué)學(xué)士學(xué)位論文 26 的特征點數(shù)量為 585 處。 哈爾濱理工大學(xué)學(xué)士學(xué)位論文 25 圖 39 不同尺度下的圖像匹配 圖 312 是上述兩幅圖像的特征匹配結(jié)果，相同的特征點被綠色的細(xì)線連接起來。 圖 38 不同尺度下的特征檢測 圖 311 為不同尺度下同一物體的兩幅圖像，圖像中特征點有綠色箭頭標(biāo)示出來，箭頭的方向為特正點的主方向，箭頭長度表示特征點的尺度。至此 SIFT 算法所有步驟全部完成，至于它的特征匹配方法在第二章第二節(jié)里已分析完畢，這里不再重復(fù)。 設(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)鍵點描述子向量的規(guī)范化正是可去除滿足此模型的光照影響。 圖 37 由特征點鄰域像元梯度求 128 維特征矢量 在生成特正點的描述向量后還要對描述向量作進(jìn)一步的處理，即門限化和規(guī)范化。即每個種子點有 8 個方向區(qū)間的梯 度強度信息。~360176。 si n c osxxyy???? ? ? ? ? ??? ? ? ? ? ?? ? ? ? ? ? (321) 哈爾濱理工大學(xué)學(xué)士學(xué)位論文 23 YXYX 圖 36 將坐標(biāo)變換到特正點的主方向上 將旋轉(zhuǎn)后區(qū)域劃分為 dd 個子區(qū)域（每個區(qū)域間隔為 mσ 像元），在子區(qū)域內(nèi)計算 8 個方向的梯度直方圖，繪制每個方向梯度方向的累加值，形成一個種子點。 旋轉(zhuǎn)后區(qū)域內(nèi)采樣點新的坐標(biāo)為 ： 39。 通過對關(guān)鍵點周圍圖像區(qū)域分塊，計算塊內(nèi)梯度直方圖，生成具有獨特的向量，這個向量是該區(qū)域圖像信息的一種抽象，具有唯一性。將關(guān)鍵點附近劃分成 dd 個子區(qū)域，每個子 區(qū)域尺寸為 mσ 個像元（ d=4， m=3， σ 為尺特征點的尺度值）。描述子除了是進(jìn)行特征匹配的依據(jù)外，還能使使關(guān)鍵點具有更多的不變特性，如光照變化、 3D 視點變化等。 至此，圖像的關(guān)鍵點已檢測完畢，每個關(guān)鍵點有三個信息：位置、 尺度、方向；同時也就使關(guān)鍵點具備平移、縮放、和旋轉(zhuǎn)不變性。通常使用一個帶箭頭的圓或直接使用箭頭表示 SIFT 區(qū)域的三個值：中心表示特征點位置 ，半徑表示關(guān)鍵點尺度（ r=） ,箭頭表示主方向。 獲得圖像關(guān)鍵點主方向后，每個關(guān)鍵點有三個信息 (x,y,σ,θ)：位置 、尺度、方向。所以一個關(guān)鍵點可 能檢測得到多個方向，這可以增強匹配的魯棒性。 直方圖峰值代表該關(guān)鍵點處鄰域內(nèi)圖像梯度的主方向，也就是該關(guān)鍵點的主方向。通過高斯平滑，可以使關(guān)鍵哈爾濱理工大學(xué)學(xué)士學(xué)位論文 22 點附近的梯度幅值有較大權(quán)重，從而部分彌補沒考慮仿射不變形產(chǎn)生的特征點不穩(wěn)定。 主 方 向 圖 35 用直方圖統(tǒng)計像元梯度 在計算直方圖時，每個加入直方 圖的采樣點都使 要 用圓形高斯函數(shù)函數(shù)進(jìn)行加權(quán)處理，也就是進(jìn)行高斯平滑。為一個柱。~360176。梯度方向直方圖的橫軸是梯度方向角，縱軸是剃度方向角對應(yīng)的梯度幅值累加值。 ( , ) ( , , ) ( , )L x y G x y I x y? ? ? (318) 使用有限差分，計算以關(guān)鍵點為中心 、 以 3 為半徑的區(qū)域內(nèi)圖像梯度的幅角和幅值，公式如下 。 我們使用圖像的梯度直方圖法求關(guān)鍵點局部結(jié)構(gòu)的穩(wěn)定方向。至此， SIFT 算法第二步完成。 Lowe 論文哈爾濱理工大學(xué)學(xué)士學(xué)位論文 21 中建議 r 取 10。 D 的主曲率和 H 的特征值成正比，為了避免直接的計算這些特征值，只考慮它們的之間的比率。 DoG 函數(shù)的 欠 佳的峰值點在橫跨邊緣的方向有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。 僅僅去除低對比度的極值點對于極值點的對于特征點穩(wěn)定性是遠(yuǎn)遠(yuǎn)不夠的。利用 DoG 函數(shù)在尺度空間的 Taylor 展開式： 221() 2T TDDD X D X X XXX??? ? ? (311) 式中 D(X)=D(x,y, ? )， ( , , )TX x y??，對式 311 求一階導(dǎo)數(shù)，并令倒數(shù)為零，計算可得特征點的精確位置： 212DDX XX?? ???? (312) 將結(jié)果帶入式 311 只取前兩項得： 1( ) ( , , ) 2 TDD X D x y XX???? ? ? ? (313) 上式去除那些對 比度較低的不穩(wěn)定極值點。 由于 DoG 值對噪聲和邊緣較敏感，因此，在上面 DoG 尺度空間中檢測到局部極值點還要經(jīng)過進(jìn)一步的檢驗才能精確定位為特征點。其中 S 為 DoG 空間每組圖像中進(jìn)行極值 點檢測的層數(shù)。 Scale 圖 34 極值點檢測示意圖 在極值比較的過程中，每一組圖像的首末兩層是無法進(jìn)行極值比較的，為了滿足尺度變化的連續(xù)性，我們在每一組圖像的頂層繼續(xù)用高斯模糊生成了 3 幅圖像，高斯金字塔有每組 S+3 層圖像。 哈爾濱理工大學(xué)學(xué)士學(xué)位論文 19 圖 33 不同尺度的高斯差分圖像（左上為原圖） 關(guān)鍵點搜索與定位 在 SIFT 算法中，特正點的確定主要分有以下幾步： 關(guān)鍵點是由 DoG 空間的局部極值點組成的。如果圖像中某像元附近灰度值變化不大，則不同尺度下高斯圖像中相應(yīng)像元的灰度值相差不大，在差分后形成的高斯差分圖像中，相應(yīng)像元的灰度值越?。幌裨浇叶戎底兓酱?，在不同尺度下的高斯圖像相應(yīng)像元的灰度值相差越大，差分后的高斯差分圖相應(yīng)像元 的灰度值也越大。至此， SIFT 算法的第一步就已完成。如前所述， DoG 算子是對 LoG 算子的近似，其公式為： ( , , ) ( , , ) ( , , )D o G x y G x y k G x y? ? ? ? ? (39) 一副圖像在高斯差分尺度空間中的表達(dá) D(x,y,? )可表示為： 哈爾濱理工大學(xué)學(xué)士學(xué)位論文 18 ( , , ) ( , , ) ( , )( , , ) ( , , )D x y D o G x y I x yL x y k L x y? ? ? ?? ? ? ? (310) 所以， DoG 在計算上只需相鄰尺度高斯圖 像相減，從而簡化了計算 ?？傮w上看，設(shè) o 為圖像所在的組數(shù)，則每張圖像的尺度參數(shù)為： 11 2 12 ( , , , , ) , 2n sk k k k? ? ?? ? ? ??? ? ? (37) 當(dāng)圖像通過相機拍攝時，相機的鏡頭已經(jīng)對圖像進(jìn)行了一次初始 的模糊。這里先來分析高斯金子塔中每張圖像尺度參數(shù) ? 的確定方法。 哈爾濱理工大學(xué)學(xué)士學(xué)位論文 17 O c t a v e 1O c t a v e 2O c t a v e 3O c t a v e 4O c t a v e 5Scale 圖 31 高斯金字塔 高斯金子塔的組數(shù)是由原始圖像的分辨率覺定的。所以，高斯金字塔每組圖像的分辨率是上一組圖像的四分之一，而一組圖像中的每一張圖像則是由同一張圖像做不同尺度的高斯模糊獲得的，如圖 31 所示 。為了減少計算量，在高斯濾波的基礎(chǔ)上加上了降采樣，即一幅圖像可以產(chǎn)生幾組（ octave）圖像，一組圖像包括幾層（ interval）圖像。 ? 越大，圖像的尺度越大，所反映的是圖想的整體特征， ? 越小，圖像的初尺度越小，反映的是圖像的細(xì)節(jié)特征。高斯函數(shù)的表達(dá)式及尺度空間的計算公式如式 35 所示。一個圖像在高斯尺度空間的表達(dá) L(x,y,? )，定義為原始圖像 I(x,y)與一個可變尺度的 2 維高斯函數(shù) G(x,y,? )卷積運算。高斯金字塔的構(gòu)建主要分為兩步：對輸入圖像進(jìn)行增量式的高斯卷積和對圖像做降采樣。式 31 為尺度規(guī)范化的 GoG算子： 2222 2 2( , ,G G L o G x yG xy? ? ? ?? ? ? ?? ? ? (31) 哈爾濱理工大學(xué)學(xué)士學(xué)位論文 16 LoG 算子與高斯核函數(shù) ( , , )G x y? 又有如下關(guān)系： 2 ( , , ) ( , , )( 1 )G x y k G x yG k? ? ?? ? ? ?? (32) 2( , , ) ( , , ) ( 1 )G x y k G x y k G? ? ? ? ? ? ? (33) ( , , ) ( , , )( , , ) ( 1 )G x y k G x yL oG x y k? ? ??? ? (34) 式中，通過推導(dǎo)可以看出， LoG 算子與高斯核函數(shù)的差有近似關(guān)系，由此引入一種新的算子 DoG（ Difference of Gaussian），即高斯差分算子作為 LoG 算子的近似。 瑞典皇家理工學(xué)院 的 Tony Lindeberg在他的論文《 Scalespace theory: A basic tool for analysing structures at different scales》 指出尺度規(guī)范化的 LoG( Laplace of Gaussian)算子具有真正的尺度不變性，也就是說圖像經(jīng)過LoG 變換后再檢測出的特征點便具有尺度不變性，這就是 SIFT 算法檢測特征點方法的理論依據(jù)。我們需要同時考慮圖像在多尺度下的描述，獲知感興趣物體的最佳尺度。 尺度越大圖像越模糊。 圖像的尺度空間表達(dá)就是圖像在所有尺度下的描述 ， 即尺度空間是由同一副圖片分別使用不同尺度表示所組成的圖像組。 DoG 尺度空間的構(gòu)造 尺度可以理解為我們觀察自然界物體時使用的單位，如觀察高山時，我們使用 的尺度是米或千米，而觀察細(xì)胞或微生物時，我們使用的尺度是微米或納米。總的來說， SIFT 算法包括兩部分內(nèi)容：一是在尺度空間中進(jìn)行興趣點檢測；二是對檢測出的興趣點用一個 128 維德向量進(jìn)行描述。 SIFT 特征對旋轉(zhuǎn)、尺度縮放、亮度變化等保持不變性，是非常穩(wěn)定的局部特征 。 哈爾濱理工大學(xué)學(xué)士學(xué)位論文 15 第 3章 SIFT 算法原理及性能驗證 SIFT 算法原理 SIFT 算法（ Scale Invariant Feature Transform）是一種 基于尺度空間的、對圖像縮放、旋轉(zhuǎn)甚至仿射變換保持不變性的圖像局部特征描述算子 ，最早是由 British Columbia 大學(xué) 的 大衛(wèi) 而 SIFT 算法原理及實現(xiàn)方法將在下一章做詳細(xì)分析。 本章小結(jié) 本章主要研究了 CBIR 技術(shù)的部分關(guān)鍵環(huán)節(jié)，如最為基礎(chǔ)的特征提取和匹配技術(shù)，這是 CBIR 系統(tǒng)最為重要的一個環(huán)節(jié)，直接決定了整個系統(tǒng)性能的好壞。而由于兩個指標(biāo)相互制約，我們通常也會根據(jù)需要為 “檢索策略 ”選擇一個合適的度，不能太嚴(yán)格也不能太松，尋求在召回率和準(zhǔn)確率中間的一個平衡點。而希望去除檢索結(jié)果中的不相關(guān)文檔時，務(wù)必要將 “檢索策略 ”定的更加嚴(yán)格，這樣也會使有一些相關(guān)的文檔不再能被檢索到，從而 使召回率受到影響。計算公式為： AR ACAAB? ?? ? (214) “召回率 ”與 “準(zhǔn)確率 ”雖然沒有必然的關(guān)系（從上面公式中可以看到），然而在大規(guī)模數(shù)據(jù)集合中，這兩個指標(biāo)卻是相互制約的。該準(zhǔn)則具體的評價方法是：先選擇一副基準(zhǔn)圖像作為 CBIR 系統(tǒng)的查詢，然后根據(jù)查詢結(jié)果與基準(zhǔn)圖像 I 將數(shù)據(jù)庫里的全