【文章內(nèi)容簡(jiǎn)介】 見(jiàn)的如下：，其公式如下： (210)，公式為： (211)： (212)將圖像中的特征點(diǎn)提取出來(lái)后，一般用一個(gè)n維向量來(lái)對(duì)圖像的特征點(diǎn)進(jìn)行描述，通過(guò)計(jì)算兩幅圖片相應(yīng)特征點(diǎn)描述向量的相似距離來(lái)確定是否為相似特征。基于相似距離的度量方法具有計(jì)算簡(jiǎn)單，比較有效等優(yōu)點(diǎn)，但和人體視覺(jué)實(shí)際的相似度感知還存在差距。因?yàn)镾IFT算法會(huì)對(duì)檢測(cè)出的特征點(diǎn)生成一個(gè)128維的描述向量，因此在本課題中，采用歐氏距離作為相似性度量的方法。并按并按距離比率(distanceratio)準(zhǔn)則進(jìn)行特征匹配，即對(duì)于某一特征點(diǎn)，設(shè)其描述向量另一圖像中與該特征點(diǎn)最相似的特征點(diǎn)描述向量的歐幾里得距離為，與次相似點(diǎn)描述向量歐幾里得距離為，計(jì)算與的比率ratio = /。則評(píng)判是否與特征點(diǎn)匹配的定義為： (213)其中，為預(yù)先設(shè)定的閾值，Lowe 實(shí)驗(yàn)中采用值為 。也就是說(shuō)當(dāng)距離比率大于某一閾值時(shí)，認(rèn)為特征點(diǎn)成功匹配，相反，則認(rèn)為與特征點(diǎn)不匹配。 CBIR 系統(tǒng)性能評(píng)價(jià)一般情況下，大型數(shù)據(jù)庫(kù)系統(tǒng)采用RecallPrecision準(zhǔn)則來(lái)評(píng)自身的有效性。該準(zhǔn)則具體的評(píng)價(jià)方法是：先選擇一副基準(zhǔn)圖像作為CBIR系統(tǒng)的查詢(xún)，然后根據(jù)查詢(xún)結(jié)果與基準(zhǔn)圖像I將數(shù)據(jù)庫(kù)里的全部圖像分為四類(lèi)：A、檢索到的且與I相似的圖像；B、檢索到的但與I無(wú)關(guān)的圖像；C、未檢索到但與I相似的圖像；D、未檢索到且與I無(wú)關(guān)的圖像。最后統(tǒng)計(jì)各類(lèi)圖像的數(shù)量并計(jì)算查全率R(又叫召回率，Recall)和差準(zhǔn)率P(Precision)。計(jì)算公式為： (214)“召回率”與“準(zhǔn)確率”雖然沒(méi)有必然的關(guān)系（從上面公式中可以看到），然而在大規(guī)模數(shù)據(jù)集合中，這兩個(gè)指標(biāo)卻是相互制約的。由于“檢索策略”并不完美，希望更多相關(guān)的文檔被檢索到時(shí)，放寬“檢索策略”時(shí)，往往也會(huì)伴隨出現(xiàn)一些不相關(guān)的結(jié)果，從而使準(zhǔn)確率受到影響。而希望去除檢索結(jié)果中的不相關(guān)文檔時(shí)，務(wù)必要將“檢索策略”定的更加嚴(yán)格，這樣也會(huì)使有一些相關(guān)的文檔不再能被檢索到，從而使召回率受到影響。凡是設(shè)計(jì)到大規(guī)模數(shù)據(jù)集合的檢索和選取，都涉及到“召回率”和“準(zhǔn)確率”這兩個(gè)指標(biāo)。而由于兩個(gè)指標(biāo)相互制約，我們通常也會(huì)根據(jù)需要為“檢索策略”選擇一個(gè)合適的度，不能太嚴(yán)格也不能太松，尋求在召回率和準(zhǔn)確率中間的一個(gè)平衡點(diǎn)。這個(gè)平衡點(diǎn)由具體需求決定。 本章小結(jié)本章主要研究了CBIR技術(shù)的部分關(guān)鍵環(huán)節(jié)，如最為基礎(chǔ)的特征提取和匹配技術(shù)，這是CBIR系統(tǒng)最為重要的一個(gè)環(huán)節(jié)，直接決定了整個(gè)系統(tǒng)性能的好壞。在本章節(jié)中，我們主要研究了Harris算法、SUSAN算法的基本原理，并設(shè)計(jì)實(shí)驗(yàn)對(duì)其特征檢索特點(diǎn)、能力及穩(wěn)定性進(jìn)行了驗(yàn)證，并與SIFT算法進(jìn)行了對(duì)比分析。而SIFT算法原理及實(shí)現(xiàn)方法將在下一章做詳細(xì)分析。另外本章節(jié)還介紹了常用的特征索引技術(shù)，這一環(huán)節(jié)直接關(guān)系到系統(tǒng)的檢索效率及信息的管理能力。第3章 SIFT算法原理及性能驗(yàn)證 SIFT算法原理SIFT算法（Scale Invariant Feature Transform）是一種基于尺度空間的、對(duì)圖像縮放、旋轉(zhuǎn)甚至仿射變換保持不變性的圖像局部特征描述算子，最早是由British Columbia大學(xué)的大衛(wèi)勞伊（David ）教授于1999年總結(jié)提出的，并于2004年進(jìn)一步完善。SIFT特征對(duì)旋轉(zhuǎn)、尺度縮放、亮度變化等保持不變性，是非常穩(wěn)定的局部特征。并且它將特征點(diǎn)檢測(cè)，特征矢量生成，特征點(diǎn)匹配等步驟結(jié)合在一起，獨(dú)特性好，信息量豐富，現(xiàn)在的應(yīng)用十分廣泛?？偟膩?lái)說(shuō)，SIFT算法包括兩部分內(nèi)容：一是在尺度空間中進(jìn)行興趣點(diǎn)檢測(cè)；二是對(duì)檢測(cè)出的興趣點(diǎn)用一個(gè)128維德向量進(jìn)行描述。具體實(shí)現(xiàn)可以分為四步：構(gòu)造DoG尺度空間、關(guān)鍵點(diǎn)的搜索與定位、特征點(diǎn)方向賦值和關(guān)鍵點(diǎn)描述。 DoG尺度空間的構(gòu)造尺度可以理解為我們觀察自然界物體時(shí)使用的單位，如觀察高山時(shí)，我們使用的尺度是米或千米，而觀察細(xì)胞或微生物時(shí)，我們使用的尺度是微米或納米。更形象的例子是電影中的拉伸鏡頭、查看圖片時(shí)的縮放等等。圖像的尺度空間表達(dá)就是圖像在所有尺度下的描述，即尺度空間是由同一副圖片分別使用不同尺度表示所組成的圖像組。尺度空間中各尺度圖像的模糊程度逐漸變大，能夠模擬人在距離目標(biāo)由近到遠(yuǎn)時(shí)目標(biāo)在視網(wǎng)膜上的形成過(guò)程。尺度越大圖像越模糊。用機(jī)器視覺(jué)系統(tǒng)分析未知場(chǎng)景時(shí)，計(jì)算機(jī)并不預(yù)先知道圖像中物體的尺度。我們需要同時(shí)考慮圖像在多尺度下的描述，獲知感興趣物體的最佳尺度。另外如果不同的尺度下都有同樣的關(guān)鍵點(diǎn)，那么在不同的尺度的輸入圖像下就都可以進(jìn)行匹配，也就是尺度不變性。瑞典皇家理工學(xué)院的Tony Lindeberg在他的論文《Scalespace theory: A basic tool for analysing structures at different scales》指出尺度規(guī)范化的 LoG( Laplace of Gaussian)算子具有真正的尺度不變性，也就是說(shuō)圖像經(jīng)過(guò)LoG變換后再檢測(cè)出的特征點(diǎn)便具有尺度不變性，這就是SIFT算法檢測(cè)特征點(diǎn)方法的理論依據(jù)。LoG算子可由高斯梯度算子GoG構(gòu)建。式31為尺度規(guī)范化的GoG算子： (31)LoG算子與高斯核函數(shù)又有如下關(guān)系： (32) (33) (34)式中，通過(guò)推導(dǎo)可以看出，LoG算子與高斯核函數(shù)的差有近似關(guān)系，由此引入一種新的算子DoG（Difference of Gaussian），即高斯差分算子作為L(zhǎng)oG算子的近似。根據(jù)以上理論，SIFT算法便是在高斯差分尺度空間尋找特征點(diǎn)的，DoG尺度空間的分為以下幾個(gè)步驟: 由上所述，SIFT算法是在高斯差分尺度空間尋找特征點(diǎn)的，而要想獲得圖像在高斯差分尺度空間中的表達(dá)，則首先要獲得圖像的高斯金字塔。高斯金字塔的構(gòu)建主要分為兩步：對(duì)輸入圖像進(jìn)行增量式的高斯卷積和對(duì)圖像做降采樣。Lindeberg在他的論文中證明，高斯尺度核是唯一可以產(chǎn)生多尺度空間的核。一個(gè)圖像在高斯尺度空間的表達(dá)L(x,y,)，定義為原始圖像I(x,y)與一個(gè)可變尺度的2維高斯函數(shù)G(x,y,)卷積運(yùn)算。對(duì)輸入圖像進(jìn)行增量式的高斯卷積過(guò)程又叫做高斯模糊、高斯濾波、高斯變換。高斯函數(shù)的表達(dá)式及尺度空間的計(jì)算公式如式35所示。 (35)式35中的便是圖像的尺度參數(shù)，多幅值不同的高斯模糊圖像組成的圖片集就是圖像在多尺度空間中的表達(dá)。越大，圖像的尺度越大，所反映的是圖想的整體特征，越小，圖像的初尺度越小，反映的是圖像的細(xì)節(jié)特征。由于高斯變換并不改變圖像的分辨率，在大尺度下，圖像的細(xì)節(jié)被忽略，過(guò)高的分辨率只會(huì)產(chǎn)生冗余的計(jì)算量。為了減少計(jì)算量，在高斯濾波的基礎(chǔ)上加上了降采樣，即一幅圖像可以產(chǎn)生幾組（octave）圖像，一組圖像包括幾層（interval）圖像。 為了保持尺度變化的連續(xù)性，每一組圖像的第一張圖像（最底層的一張）是由前一組（金字塔下面一組）圖像的倒數(shù)第三張分別在X軸方向和Y軸方向上隔點(diǎn)采樣得到，如此便構(gòu)成了高斯金字塔。所以，高斯金字塔每組圖像的分辨率是上一組圖像的四分之一，而一組圖像中的每一張圖像則是由同一張圖像做不同尺度的高斯模糊獲得的，如圖31所示。這樣既可以保留圖像不同尺度下的特征點(diǎn)，又減少了信息量和算法的運(yùn)算量。圖31 高斯金字塔高斯金子塔的組數(shù)是由原始圖像的分辨率覺(jué)定的。設(shè)原始圖像大小為mn，則高斯金字塔的組數(shù)o為： (36)每組的層數(shù)N的確定方法由于涉及后續(xù)內(nèi)容將在下一節(jié)進(jìn)行介紹。這里先來(lái)分析高斯金子塔中每張圖像尺度參數(shù)的確定方法。設(shè)高斯金字塔中每組圖像中第一張圖像的尺度參數(shù)為，則該組圖像中任一張圖片的尺度參數(shù)，其中n為圖像的層數(shù)，s為每組圖像中進(jìn)行極值點(diǎn)檢測(cè)的圖像張數(shù)。總體上看，設(shè)o為圖像所在的組數(shù)，則每張圖像的尺度參數(shù)為： (37)當(dāng)圖像通過(guò)相機(jī)拍攝時(shí)，相機(jī)的鏡頭已經(jīng)對(duì)圖像進(jìn)行了一次初始的模糊。所以根據(jù)高斯模糊的性質(zhì)，設(shè)（David ）為第0層尺度，為被相機(jī)鏡頭模糊后的尺度（），則高斯金字塔的初始尺度為： (38) 在獲得圖像的高斯金子塔后，就可以構(gòu)建DoG金字塔了。如前所述，DoG算子是對(duì)LoG算子的近似，其公式為： (39)一副圖像在高斯差分尺度空間中的表達(dá)D(x,y,)可表示為： (310)所以，DoG在計(jì)算上只需相鄰尺度高斯圖像相減，從而簡(jiǎn)化了計(jì)算。高斯差分尺金字塔的構(gòu)建過(guò)程如圖32所示。至此，SIFT算法的第一步就已完成。圖32 高斯差分金子塔的構(gòu)建我們可以通過(guò)高斯差分圖像看出圖像上的像元灰度值情況。如果圖像中某像元附近灰度值變化不大，則不同尺度下高斯圖像中相應(yīng)像元的灰度值相差不大，在差分后形成的高斯差分圖像中，相應(yīng)像元的灰度值越??；像元附近灰度值變化越大，在不同尺度下的高斯圖像相應(yīng)像元的灰度值相差越大，差分后的高斯差分圖相應(yīng)像元的灰度值也越大。圖33是不同尺度的高斯差分圖像。圖33 不同尺度的高斯差分圖像（左上為原圖） 關(guān)鍵點(diǎn)搜索與定位在SIFT算法中，特正點(diǎn)的確定主要分有以下幾步： 關(guān)鍵點(diǎn)是由DoG空間的局部極值點(diǎn)組成的。為了尋找DoG空間的局部極值點(diǎn)，每一個(gè)像元要和它同尺度和相鄰尺度的所有相鄰點(diǎn)比較，如圖34，位于中心的待檢測(cè)點(diǎn)和它同尺度的8個(gè)相鄰點(diǎn)和上下相鄰尺度對(duì)應(yīng)的92個(gè)點(diǎn)共26個(gè)點(diǎn)比較，以確保在尺度空間和二維圖像空間都檢測(cè)到極值點(diǎn)。圖34 極值點(diǎn)檢測(cè)示意圖在極值比較的過(guò)程中，每一組圖像的首末兩層是無(wú)法進(jìn)行極值比較的，為了滿足尺度變化的連續(xù)性，我們?cè)诿恳唤M圖像的頂層繼續(xù)用高斯模糊生成了3幅圖像，高斯金字塔有每組S+3層圖像。DoG金字塔每組有S+2層圖像右圖為不同尺度不同層間極值檢測(cè)示意圖。其中S為DoG空間每組圖像中進(jìn)行極值點(diǎn)檢測(cè)的層數(shù)。也正是這個(gè)原因，每一組圖像的第一張圖像（最底層的一張）是由前一組（金字塔下面一組）圖像的倒數(shù)第三張分別在X軸方向和Y軸方向上隔點(diǎn)采樣得到。由于DoG值對(duì)噪聲和邊緣較敏感，因此，在上面DoG尺度空間中檢測(cè)到局部極值點(diǎn)還要經(jīng)過(guò)進(jìn)一步的檢驗(yàn)才能精確定位為特征點(diǎn)。為了提高關(guān)鍵點(diǎn)的穩(wěn)定性，需要對(duì)尺度空間DoG函數(shù)進(jìn)行曲線擬合。利用DoG函數(shù)在尺度空間的Taylor展開(kāi)式： (311)式中D(X)=D(x,y,)，對(duì)式311求一階導(dǎo)數(shù)，并令倒數(shù)為零，計(jì)算可得特征點(diǎn)的精確位置： (312)將結(jié)果帶入式311只取前兩項(xiàng)得： (313)上式去除那些對(duì)比度較低的不穩(wěn)定極值點(diǎn)。Lowe的試驗(yà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)在橫跨邊緣的方向有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。主曲率可以通過(guò)計(jì)算在該點(diǎn)位置尺度的22的Hessian矩陣得到，導(dǎo)數(shù)由采樣點(diǎn)相鄰差來(lái)估計(jì)： (316)式中，表示DOG金字塔中某一尺度的圖像x方向求導(dǎo)兩次。D的主曲率和H的特征值成正比，為了避免直接的計(jì)算這些特征值，只考慮它們的之間的比率。令為最大特征值，為最小特征值，則有： (317)在兩特征值相等時(shí)達(dá)最小，隨r的增長(zhǎng)而增長(zhǎng)。Lowe論文中建議r取10。如果 (318)則保留關(guān)鍵點(diǎn)，否則將該關(guān)鍵點(diǎn)剔除。至此，SIFT算法第二步完成。 特征點(diǎn)方向賦值通過(guò)尺度不變性求極值點(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ù)這一尺度值，得到最接近這一尺度值的高斯圖像。 (318)使用有限差分，計(jì)算以關(guān)鍵點(diǎn)為中心、以3，公式如下。 (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)镾IFT算法只考慮了尺度和旋轉(zhuǎn)不變形，沒(méi)有考慮仿射不變性。通過(guò)高斯平滑，可以使關(guān)鍵點(diǎn)附近的梯度幅值有較大權(quán)重，從而部分彌補(bǔ)沒(méi)考慮仿射不變形產(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)描述出來(lái)，這個(gè)描述子不但用來(lái)描述關(guān)鍵點(diǎn)，也包括關(guān)鍵點(diǎn)周?chē)鷮?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，σ為尺特征