基于內(nèi)容的圖像檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)分析研究 計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)

目錄摘要 1Abstract 2前言 3第1章緒論 41.1基于內(nèi)容的圖像檢索 41.2圖像檢索評價(jià)指標(biāo) 6第2章BoF模型 72.1基于視覺單詞的匹配 72.2投票機(jī)制 92.3倒排索引 10第3章漢明嵌入 123.1原始模型的缺點(diǎn) 123.2基于漢明嵌入的匹配 13第4章幾何重排 164.1弱幾何一致性 164.1.1弱幾何一致性的原理 164.1.2考慮弱幾何一致性的相似度計(jì)算 184.2基于幾何信息的重排 204.2.1隨機(jī)抽樣一致算法 204.2.2錯(cuò)配點(diǎn)剔除 21第5章實(shí)驗(yàn)過程 245.1開發(fā)環(huán)境 245.2框架設(shè)計(jì) 245.3實(shí)現(xiàn) 25第6章結(jié)論 28參考文獻(xiàn) 29致謝 31摘要通常的，圖像檢索可以分為兩大類：基于文本的圖像檢索和基于內(nèi)容的圖像檢索。本文的主要內(nèi)容是設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)基于內(nèi)容的圖像檢索系統(tǒng)?，F(xiàn)在主流的圖像檢索技術(shù)主要是對圖像提取局部特征，并利用特征袋模型對特征進(jìn)行處理，以獲得檢索精度和檢索性能之間的平衡。一個(gè)檢索系統(tǒng)的運(yùn)作主要包括數(shù)據(jù)集預(yù)處理和正式的檢索過程。其中預(yù)處理過程包含：圖像特征提取、視覺詞典構(gòu)建以及圖像特征編碼。檢索過程會(huì)對待檢索的圖像進(jìn)行類似處理，同時(shí)還有對特征的相似度比對，之后返回結(jié)果。本文基于前人的研究成果，做出的主要工作如下：1.搭建一個(gè)基于flask框架的在線檢索系統(tǒng)。2.圖像數(shù)據(jù)集處理階段，對每幅圖像提取RootSIFT特征，并對特征進(jìn)行k-means聚類，用來構(gòu)建特征袋模型。3.利用ukbench數(shù)據(jù)集，比較了基礎(chǔ)特征袋模型，漢明嵌入，弱幾何一致性校驗(yàn)，空間幾何重排等的檢索效果，并對效果進(jìn)行mAP評價(jià)。關(guān)鍵詞：圖像檢索；特征袋模型；漢明嵌入；弱幾何一致性；幾何重排AbstractIngeneral,imageretrievalcanbedividedintotwomajorcategories:text-basedimageretrievalandcontent-basedimageretrieval.Themaincontentofthispaperistodesignandimplementacontentbasedimageretrievalsystem.Currently,themainstreamimageretrievaltechnologymainlyextractslocalfeaturesfromtheimagesandusestheBagofFeature(BoF)modeltoprocessthefeaturestoobtainabalancebetweenretrievalprecisionandretrievalperformance.Theoperationofaretrievalsystemmainlyincludesdatasetpreprocessingandformalretrievalprocess.Thepreprocessingprocessincludes:imagefeatureextraction,visualdictionaryconstruction,andimagefeaturecoding.Theretrievalprocesswillperformsimilarprocessingontheretrievedimages,aswellascomparethesimilaritiesofthefeatures,andthenreturntheresults.Basedonpreviousresearchresults,themainworkofthispaperisasfollows:1.Buildanonlinewebretrievalsystembasedonflaskframework.2.Attheimagedatasetprocessingstage,RootSIFTfeaturesareextractedfromeachimage,andthefeaturesareclusteredusingk-meansalgorithmtoconstructtheBoFmodel.3.Usingukbenchdataset,wecomparethesearchresultsofthebasicBoFmodel,HE,WGC,spatialgeometricre-rankingandsoon,andevaluatetheirefficiencybymAP.Keywords:imageretrieval;bagoffeature;hammingembedding;weakgeometricconsistency;reranking前言隨著諸如智能手機(jī)、數(shù)碼相機(jī)、平板電腦等電子設(shè)備的普及，人們可以用越來越容易的方式創(chuàng)作以及獲取圖片。同時(shí)，社交網(wǎng)站的興起，如國外的Instagram、Facebook和國內(nèi)的QQ等，直接催生了人們分享照片的興趣。這些原因無疑導(dǎo)致了圖像數(shù)據(jù)庫的規(guī)模迅猛增長，例如，flickr作為一個(gè)照片分享網(wǎng)站，單是2017年就有用戶上傳了高達(dá)6億張圖片，中國最大的電商網(wǎng)站淘寶同樣保存著數(shù)十億計(jì)的用戶圖片。海量的圖像規(guī)模不僅在存儲(chǔ)方面增加了難度，同時(shí)在應(yīng)用方面，也對能夠讓用戶精準(zhǔn)、快速的查找感興趣的圖片提出了挑戰(zhàn)。因此，針對大規(guī)模圖像數(shù)據(jù)庫的信息檢索，成為了當(dāng)前數(shù)字圖像處理技術(shù)方向的研究熱點(diǎn)。到目前為止，大規(guī)模圖像檢索的主流是基于內(nèi)容的圖像檢索技術(shù)，主要方式是類似于文本處理方面的詞袋模型，本文下面即對此展開介紹，并解釋其他的擴(kuò)展方法。本文下面的組織如下：第1章介紹基于內(nèi)容的圖像檢索技術(shù)的基本內(nèi)涵，并介紹圖像檢索的評價(jià)指標(biāo)，第2章介紹了利用提取圖像局部特征的基本BoF模型檢索方法，以及相應(yīng)的索引、相似度計(jì)算方式，第3章介紹了對聚類的改進(jìn)，即漢明嵌入，第4章介紹了基于幾何信息的重排，第5章則展示了實(shí)驗(yàn)效果，對所采用的方法進(jìn)行相應(yīng)的實(shí)驗(yàn)，并利用評價(jià)指標(biāo)進(jìn)行效果評價(jià)。緒論本章介紹了傳統(tǒng)圖像檢索方法的缺陷，并展示了基于內(nèi)容的圖像檢索技術(shù)的要點(diǎn)。本章還展示了檢索系統(tǒng)的基本工作流程，以及對檢索結(jié)果的評價(jià)方法?；趦?nèi)容的圖像檢索傳統(tǒng)的圖像檢索方法主要是基于關(guān)鍵字的圖像檢索方法，這種方法主要是通過人工對要處理的圖像進(jìn)行關(guān)鍵字標(biāo)注，讓每幅圖像添加對應(yīng)的關(guān)鍵字，檢索時(shí)就將對圖像內(nèi)容的檢索轉(zhuǎn)化成了對關(guān)鍵字文本的檢索，無疑要容易許多。這種方法有時(shí)候效果可能會(huì)很好，它也曾被百度等搜索引擎采用過，但是它有一些顯著的缺點(diǎn)。首先人工標(biāo)注耗時(shí)耗力，今天的大規(guī)模圖像數(shù)據(jù)庫顯然是無法應(yīng)用的，其次，所謂一圖勝千言，一幅圖像的內(nèi)涵有很多，往往無法用幾個(gè)關(guān)鍵字描述完全，并且每個(gè)人對圖像內(nèi)容的理解也不一樣，因此檢索時(shí)會(huì)導(dǎo)致誤差。這些缺點(diǎn)導(dǎo)致上述技術(shù)無法更廣泛的應(yīng)用。而現(xiàn)在的商用的圖像檢索系統(tǒng)使用的技術(shù)主要是基于內(nèi)容的圖像檢索(ContentBasedImageRetrieval,CBIR)REF_Ref514443249\r\h[1]。圖STYLEREF1\s1SEQ圖\*ARABIC\s11在線CBIR系統(tǒng)的檢索流程基于內(nèi)容的圖像檢索技術(shù)基本不需要人工干預(yù)，并且是對圖像內(nèi)容本身的理解。一個(gè)基本的在線CBIR系統(tǒng)檢索流程如REF_Ref513909754\h圖11所示圖STYLEREF1\s1SEQ圖\*ARABIC\s11在線CBIR系統(tǒng)的檢索流程首先選取初始的圖像數(shù)據(jù)集，需要對它進(jìn)行特征提取，本文這里選取了ukbench/download/ukbench/ukbench.zip，共10200幅圖片，每四幅一組，每組都是類似物體在不同角度和尺度的圖像。下文的內(nèi)容都是基于這一數(shù)據(jù)集的5000幅圖子集來做效果評估。/download/ukbench/ukbench.zip接著是對選取好的數(shù)據(jù)集進(jìn)行圖像特征提取。圖像特征有很多種，常見的包括顏色特征，紋理特征，形狀特征等等，稱為底層特征，以前的CBIR系統(tǒng)主要基于此實(shí)現(xiàn)，綜述性文獻(xiàn)REF_Ref513472251\r\h[3]對此有敘述。這些底層特征都比較易受環(huán)境影響，像是光照、尺度、視角，以及一些背景方面的變化都會(huì)對檢索結(jié)果造成較大的影響，所以圖像檢索時(shí)會(huì)選擇局部特征，這種特征的抗干擾性比較好。Lowe提出的SIFT特征REF_Ref514312382\r\h[4]就是這樣一種在實(shí)踐中被證明效果較好的局部特征，它具有很好的尺度，旋轉(zhuǎn)，和平移不變性，基于Lowe的工作，后人提出了許多的改進(jìn)，其中文獻(xiàn)REF_Ref514251320\r\h[5]提出了RootSIFT特征，它僅僅是對原始SIFT特征的一種代數(shù)擴(kuò)展(對每個(gè)計(jì)算出來的原始SIFT描述子進(jìn)行L1歸一化并取平方根)，但是卻能夠改進(jìn)檢索效果。由于RootSIFT對SIFT特征的兼容性和易于計(jì)算的特點(diǎn)，本文進(jìn)行圖像特征提取時(shí)，對SIFT進(jìn)行處理轉(zhuǎn)換成了RootSIFT特征。SIFT特征和RootSIFT特征一樣，每個(gè)描述子都是128維，每幅圖包含成百上千個(gè)這樣的特征描述子，一個(gè)基本的數(shù)據(jù)集，比如ukbench，包含上千萬維這樣的高維向量，如果查詢圖片依靠暴力匹配每個(gè)向量的距離來計(jì)算相似度，性能上無法接受。為了處理大規(guī)模圖像數(shù)據(jù)集，Sivic等人基于文本處理領(lǐng)域的詞袋模型，提出了特征袋(BagOfFeature,BoF)模型REF_Ref514312395\r\h[6]，利用k-means算法對所有描述子進(jìn)行聚類，聚類之內(nèi)的描述子具有較高的相似度，聚類之間的描述子具有較高的離散度，量化形成k個(gè)視覺單詞。對于一幅包含n個(gè)描述子的圖片，每個(gè)描述子被劃分到最近的視覺單詞，統(tǒng)計(jì)形成視覺單詞的頻率直方圖，用頻率向量來代表這幅圖片，這樣所有n個(gè)圖像特征就被一個(gè)k維向量代替，大大減少了計(jì)算量。圖像查詢時(shí)可以簡單的計(jì)算向量之間的歐幾里得距離或者余弦距離來獲得最終的相似度得分。原始的BoF模型可以獲得比較滿意的檢索精度。一般來說特征聚類過程中，利用k-means算法時(shí)選取的聚類數(shù)k值設(shè)的越高，檢索效果越好，但是由于算法本身是O(k2)這樣一個(gè)比較大的復(fù)雜度，導(dǎo)致大數(shù)據(jù)集聚類時(shí)間較長，針對k-means本身的改進(jìn)有層次k-means和近似k-means等，本文這里介紹的是Jegou等人在文獻(xiàn)REF_Ref514312509\r\h[7]量化描述子形成視覺單詞的過程中，原始圖像本身的視覺幾何信息被丟失掉了，這無疑會(huì)限制檢索的效果。針對這一問題，很多人做出了利用空間幾何信息的改進(jìn)，文獻(xiàn)REF_Ref514312509\r\h[7]提出了弱幾何一致性約束，即簡單的增加了關(guān)鍵點(diǎn)角度和尺度信息的校驗(yàn)，對前面模型得到的結(jié)果進(jìn)行重排。文獻(xiàn)REF_Ref513487820\r\h[8]則提出了對已有結(jié)果的前若干幅圖片增加進(jìn)一步的空間驗(yàn)證過程，重新排序來獲得更高的精度。圖像檢索評價(jià)指標(biāo)對圖像檢索返回的結(jié)果，本文利用的評價(jià)指標(biāo)為平均精度均值指標(biāo)(meanAveragePrecision,mAP)指標(biāo)REF_Ref514251376\r\h[9]。mAP是指的是平均精度(AveragePrecision,AP)的均值：mQ代表查詢次數(shù)。APi則是第i次查詢的平均精度。一般檢索最重要的兩個(gè)指標(biāo)是精度(Precision)和召回率(Recall)，若用x軸表示召回率，y軸表示精度，可得到精度-召回率曲線(Precision-Recallcurve,PRcurveAP實(shí)現(xiàn)中，積分會(huì)被一個(gè)有限和代替：APn表示取回的圖像結(jié)果的個(gè)數(shù)，j是取回圖像的序列，Pj就代表前j個(gè)圖像的精度，?rj則是從第j?1幅圖到第j幅圖召回率的變化值，這代表當(dāng)召回率不變時(shí)相應(yīng)的精度也不計(jì)入。BoF模型BoF模型來自于文本處理領(lǐng)域的詞袋模型，其主要思想是將所有描述子聚類形成視覺詞典，再根據(jù)視覺單詞對描述子進(jìn)行量化，最后根據(jù)量化的特征進(jìn)行檢索。本章展示了如何根據(jù)已有圖像局部特征來進(jìn)行視覺詞典的構(gòu)建，形成頻率直方圖，以及利用倒排索引和投票機(jī)制進(jìn)行特征匹配REF_Ref514250879\r\h[10]。基于視覺單詞的匹配原始的BoF模型的處理流程有下面幾步：首先對于原始圖片，可以先進(jìn)行增強(qiáng)、分割以及統(tǒng)一格式的處理以方便下面的操作。原始圖片處理完成后，對它們提取RootSIFT特征，假設(shè)共m幅圖像，每幅圖則可以獲取n個(gè)RootSIFT的關(guān)鍵點(diǎn)(keypoint)和對應(yīng)的描述子(descriptor)，每個(gè)描述子128維。所有圖片的特征組合作為訓(xùn)練集，對其進(jìn)行k-means聚類，聚類數(shù)k根據(jù)實(shí)際訓(xùn)練效果選取，一般來說k的值越大越好，但也不宜過大，REF_Ref513654072\h表21是對5000幅圖的評估結(jié)果：kmAP20000.68676150000.70617680000.718785100000.730512120000.726284表STYLEREF1\s2SEQ表\*ARABIC\s11對5000幅圖像選取不同k值后的檢索效果評估可以看到對原始的BoF模型來說，k值的增大，對后面的檢索效果提升已經(jīng)不是那么大了，而且大的k值會(huì)顯著的增加聚類時(shí)間。通過聚類可以獲得k個(gè)128維的聚類中心（通常稱為視覺單詞）和量化函數(shù)q：q:q的作用是將一個(gè)特征描述子x映射到距離最近的聚類中心，值qx是聚類中心的索引。量化過程避免了通過計(jì)算向量距離匹配特征的暴力匹配方式，而是通過比較視覺單詞的方式來匹配。直觀的講，如果兩個(gè)描述子x和y在特征空間中距離很近，那么就很有可能滿足qx=fqx,y對一幅圖像n個(gè)描述子進(jìn)行量化可以獲得一個(gè)n維向量，如果再統(tǒng)計(jì)每個(gè)維度的視覺單詞索引，每幅圖就可用一個(gè)k維的頻率向量表征，這里稱為一個(gè)BoF向量。視覺單詞之間的重要性是不一樣的。一般來說一幅圖中出現(xiàn)次數(shù)最多的視覺單詞是重要的，但如果一個(gè)視覺單詞在每幅圖中都會(huì)出現(xiàn)，那它的重要性就會(huì)降低。換句話說，僅在一幅圖中出現(xiàn)多次的視覺單詞更加具有鑒別力，也就可以賦予其更高的權(quán)重。因此，這里對視覺單詞應(yīng)用文本處理中的tf-idf權(quán)重。tf(termfrequency)指的是文檔詞頻，對文檔d中出現(xiàn)的單詞tft,dtft,dft,d為這個(gè)單詞在文檔d中的頻率，t'∈dft',d/stable/modules/generated/sklearn.feature_extraction.text.TfidfTransformer.htmlidfN為文檔總數(shù)，nt是出現(xiàn)過該單詞的文檔數(shù)，越大則說明這個(gè)單詞越常見，相應(yīng)的就會(huì)降低權(quán)重。一個(gè)單詞的tf-idftf添加tf-idf權(quán)重后，匹配函數(shù)2-2可以進(jìn)一步表示為：fidfqy表示如果描述子x和y匹配，匹配函數(shù)等于投票機(jī)制投票機(jī)制應(yīng)用在計(jì)算最終的查詢圖像和已有圖像數(shù)據(jù)集之間的相似度得分上。假設(shè)整個(gè)數(shù)據(jù)集共有m幅圖，相似度得分的計(jì)算方式如下：初始化m幅圖中每幅圖像對應(yīng)的分?jǐn)?shù)si根據(jù)查詢圖像的特征集和每幅圖像的特征集的匹配結(jié)果來更新分?jǐn)?shù)sisi假設(shè)數(shù)據(jù)集每幅圖有ni個(gè)描述子，查詢圖像有n個(gè)描述子，上面的更新方式即表示將每幅圖的描述子xi,j,j∈[0,ni)ssi最后就是匹配函數(shù)值的和s可以進(jìn)一步的對分?jǐn)?shù)si進(jìn)行處理可以得到ssi之所以有這樣的處理是由于匹配函數(shù)只有idf權(quán)重，還沒有考慮到圖像特征個(gè)數(shù)的影響。對此有多種選擇，可以類似式2-3那樣的處理，即si?=si/ni，也可以除以特征個(gè)數(shù)（BoF向量L1范數(shù)）的平方根：si?=si/ns上式實(shí)際上就是經(jīng)過tf-idf加權(quán)后的兩個(gè)BoF向量之間的余弦距離。在實(shí)現(xiàn)中，需要保存每個(gè)BoF向量的L2范數(shù)，最后在計(jì)算si?時(shí)，只需計(jì)算兩個(gè)向量的內(nèi)積倒排索引在計(jì)算相似度得分si?的時(shí)候，通過計(jì)算查詢圖像和參考圖像對應(yīng)的圖STYLEREF1\s2SEQ圖\*ARABIC\s11描述子對應(yīng)視覺單詞的頻率向量直方圖利用倒排索引可以很有效的計(jì)算相似度，這主要是因?yàn)锽oF向量的稀疏性。一幅圖的描述子只會(huì)對應(yīng)很少的聚類，比如ukbench00005.jpg的頻率向量直方圖如圖STYLEREF1\s2SEQ圖\*ARABIC\s11描述子對應(yīng)視覺單詞的頻率向量直方圖統(tǒng)計(jì)前5幅圖的前10個(gè)視覺單詞頻率向量，將是下面的列表形式：[0113031001][1002040001][1202011000][0103101103][1001000000]其中有大量的單元為0，即圖片中沒有這個(gè)視覺單詞對應(yīng)的描述子。在正排表的相似度投票的過程中，對查詢圖像的每一個(gè)描述子，都會(huì)遍歷每幅圖像的所有描述子進(jìn)行匹配，共Om倒排表則是以視覺單詞為基準(zhǔn)遍歷，一個(gè)視覺單詞可以對應(yīng)一個(gè)鏈表，鏈表包含屬于這個(gè)視覺單詞的描述子和所屬的圖片id，遍歷為Om實(shí)現(xiàn)過程中，倒排索引是將視覺單詞和倒排列表分開存儲(chǔ)。倒排列表的索引與視覺單詞是一一對應(yīng)的，一個(gè)列表項(xiàng)包含的是屬于某個(gè)視覺單詞的所有條目組成的鏈表，每個(gè)條目中包含了圖片id以及其他的特征信息。利用結(jié)合倒排索引的投票機(jī)制來計(jì)算相似度，可以比正排表快上百倍。漢明嵌入本章展示了在基于原始的BoF模型，利用倒排索引結(jié)構(gòu)來存儲(chǔ)預(yù)處理的圖像特征信息，利用投票機(jī)制來獲取相似度得分之后，如何通過漢明嵌入來進(jìn)一步的提升圖像檢索的精度，并討論其背后的原理。原始模型的缺點(diǎn)原始BoF模型比較好的利用了圖像局部特征對圖像的區(qū)分能力，同時(shí)利用倒排索引的結(jié)果也能夠有效的檢索圖像，這種方式使得利用原始模型能夠獲得比較好的檢索能力，但是缺點(diǎn)也是明顯的。首先量化會(huì)帶來誤差，不同的描述子可能因?yàn)榫嚯x相近被映射到相同的視覺單詞，這降低了描述子之間的區(qū)分性。聚類數(shù)k是依靠手動(dòng)選取的，REF_Ref513654072\h表21表明一般來說聚類數(shù)設(shè)的越高，精度也會(huì)提升，主要是越多的聚類數(shù)讓量化帶來的誤差越小，要有一個(gè)滿意的效果，BoF向量通常需要達(dá)到上萬維，獲取這么多的視覺單詞十分耗時(shí)，實(shí)驗(yàn)中使用MiniBatchKMeans/stable/modules/generated/sklearn.cluster.MiniBatchKMeans.html對ukbench的5000幅圖像進(jìn)行聚類，耗時(shí)達(dá)到數(shù)十個(gè)小時(shí)。/stable/modules/generated/sklearn.cluster.MiniBatchKMeans.html然而k也不是越高越好，表中可以看到當(dāng)k值繼續(xù)增高后，提升效果越來越差，甚至聚類數(shù)達(dá)到一定程度精度有可能下降，這是由于描述子中含有噪聲，更多的聚類讓噪聲分布越廣泛。一個(gè)合適的聚類數(shù)k的選取應(yīng)該謀求量化誤差和描述子噪聲之間的平衡。量化誤差盡可能的小，不同的描述子不應(yīng)該映射到相同的視覺單詞，描述子噪聲應(yīng)該盡量的分布在同一個(gè)聚類單元中，以避免干擾到正常的描述子。這依靠手動(dòng)選取通常是很困難的，需要遍歷一個(gè)范圍內(nèi)的k值才可以最終選取一個(gè)合適的，十分的耗時(shí)。文獻(xiàn)REF_Ref514312509\r\h[7]提出了漢明嵌入方法，可以很好的解決這個(gè)問題?；跐h明嵌入的匹配漢明嵌入是一種同時(shí)兼顧粗聚類和細(xì)聚類兩方面好處的方法，即更小的量化誤差和更少的噪聲干擾。首先漢明嵌入選取一個(gè)較小的k值，這避免了噪聲干擾，下面的問題是對被分配到同一個(gè)聚類的描述子進(jìn)行進(jìn)一步的細(xì)化。為了達(dá)到這個(gè)目的，可以對同一聚類內(nèi)的描述子進(jìn)行漢明編碼，再比較漢明距離。同一聚類內(nèi)的描述子xi，對應(yīng)的二進(jìn)制漢明編碼bxi是一個(gè)db維向量b0xi?即每維異或之后的值之和。使用漢明距離是為了能讓兩個(gè)描述子對應(yīng)漢明編碼之間的漢明距離能夠反映描述子之間的歐幾里得距離，即保留暴力匹配中描述子強(qiáng)大的區(qū)分性。這種從歐幾里得空間到漢明空間的映射，就稱為漢明嵌入（HammingEmbedding,HE），它保證了在歐幾里得空間內(nèi)距離相近的描述子，對應(yīng)的漢明距離也會(huì)是相近的REF_Ref514250316\r\h[11]。漢明嵌入包含在預(yù)處理和查詢這兩個(gè)階段中，需要獲得每個(gè)描述子的漢明編碼，首先預(yù)處理包含如下過程：生成投影矩陣：生成d,d的隨機(jī)矩陣，矩陣的值符合標(biāo)準(zhǔn)正態(tài)分布，維數(shù)d是描述子維度，一般是128維。對隨機(jī)矩陣進(jìn)行QR分解獲取一個(gè)正交矩陣Q取其前db行，得到了一個(gè)db對描述子投影降維：對所有d維描述子利用投影矩陣P進(jìn)行投影降維，一個(gè)128維的描述子xi降維得到一個(gè)新的db維向量zi=z計(jì)算投影向量的中值：上面的操作使每個(gè)視覺單詞都對應(yīng)若干個(gè)投影向量，對這些投影向量求和并求平均就得到了中值向量τ0,τ本文所有的實(shí)驗(yàn)都對db投影矩陣P和中值矩陣用于計(jì)算描述子的漢明編碼。一個(gè)描述子x，首先得到其量化索引qx和投影向量z=Px=z0b投影向量z的每一維都和x所屬聚類的中值向量比較，如果有zi至此，描述子x不僅可以用量化索引qx來代表，還包含了漢明編碼bx。大大提高了區(qū)分能力。對式f如果描述子x和y的映射到同一視覺單詞，進(jìn)一步比較他們漢明編碼的漢明距離，如果距離小于閾值?t，才認(rèn)為這兩個(gè)描述子真的匹配，否則它們將被拒絕。圖STYLEREF1\s3SEQ圖\*ARABIC\s11不同漢明閾值對檢索精度的影響閾值?t∈[0,db)是一個(gè)固定值，表示對漢明編碼匹配的接受程度，當(dāng)?t圖STYLEREF1\s3SEQ圖\*ARABIC\s11不同漢明閾值對檢索精度的影響REF_Ref514244463\h圖31是對5000幅圖在聚類數(shù)k為5000的時(shí)候，選取不同漢明閾值的檢索評價(jià)。可以看到?t=23時(shí)，效果是最好的。在閾值較小的時(shí)候，比如?t=10時(shí)，實(shí)驗(yàn)的mAP=0.767888，這說明一些正常的匹配被誤過濾了，閾值達(dá)到23時(shí)，mAP為最大值0.877311，此后閾值增大m同時(shí)對比REF_Ref513654072\h表21可以發(fā)現(xiàn)，使用了漢明嵌入方法的粗聚類數(shù)為5000時(shí)的精度水平最好是0.877311，未使用漢明方法的聚類數(shù)為12000時(shí)的精度水平為0.726284，漢明嵌入對檢索效果有極大的提升。本文實(shí)驗(yàn)還發(fā)現(xiàn)，如果一開始就設(shè)一個(gè)很高的聚類數(shù)k，對其應(yīng)用漢明嵌入，其效果不見得比不應(yīng)用好，這符合預(yù)期，因?yàn)闈h明嵌入是對屬于一個(gè)聚類空間的描述子進(jìn)一步的劃分，對于已經(jīng)過聚類的描述子而言，劃分不能夠剔除噪聲的影響?；跐h明嵌入的良好效果，本文下面的實(shí)驗(yàn)將采用這個(gè)方法，并采用?t=23漢明嵌入方法可以很好的和倒排索引結(jié)構(gòu)結(jié)合起來。上文中，倒排列表的索引與視覺單詞是對應(yīng)的，在漢明嵌入中就對應(yīng)一個(gè)中值向量。每個(gè)列表項(xiàng)是一個(gè)鏈表。鏈表中的每個(gè)條目都對應(yīng)某幅圖片中的一個(gè)描述子，因此在條目中可以加入漢明編碼。在實(shí)現(xiàn)過程中，由于漢明編碼是一個(gè)64維的二值向量，可以將這個(gè)向量壓縮為64位整型存儲(chǔ)。在匹配的過程中，利用投票機(jī)制計(jì)算相似度分?jǐn)?shù)，遍歷倒排列表的每一個(gè)條目，需要用到式3-3的匹配函數(shù)?？梢韵扔?jì)算查詢圖像描述子的漢明編碼與遍歷的漢明編碼的距離，一旦漢明距離大小超出了閾值?t實(shí)驗(yàn)中，利用了漢明嵌入的查詢過程甚至比沒有利用的，即單一的倒排索引遍歷查詢的時(shí)間更短。這主要是由于計(jì)算漢明距離僅僅是對兩個(gè)64位整型的漢明編碼進(jìn)行異或操作后再統(tǒng)計(jì)1的個(gè)數(shù)，這里的計(jì)算代價(jià)要小于更新相似度分?jǐn)?shù)的代價(jià)，而利用漢明嵌入，使用一個(gè)較小的閾值，可以顯著過濾大量量化誤差較大的描述子，避免了很多分?jǐn)?shù)更新操作。漢明嵌入也不會(huì)增加多少空間復(fù)雜度，每個(gè)描述子添加一個(gè)8字節(jié)漢明編碼即可，因此值得采用。幾何重排無論是原始BoF模型，還是增加了漢明嵌入了改進(jìn)版模型，盡管圖像檢索效果已經(jīng)不錯(cuò)，但是它們?nèi)匀粵]有利用到圖像的空間幾何特征。如果要進(jìn)一步的改進(jìn)檢索效果，應(yīng)該考慮到圖像幾何信息，因此本章接下來對漢明嵌入之后得到的結(jié)果進(jìn)一步添加了基于圖像空間幾何的重排序階段。弱幾何一致性前面提到過，加入集合信息能夠?qū)z索效果很好的提升，但是卻無法實(shí)際應(yīng)用，因?yàn)楹捅┝ζヅ渌惴ㄒ粯?，幾何匹配算法的?jì)算代價(jià)都很高昂。即使有不少工作都基于對幾何匹配算法的優(yōu)化，但是到目前為止，還是只能應(yīng)用于幾百張規(guī)模的數(shù)據(jù)集，沒有大規(guī)模利用的可能性。為了解決這個(gè)問題，文獻(xiàn)REF_Ref514312509\r\h[7]提出了弱幾何一致性(WeakGeometricConsistancy,WGC)匹配。弱幾何一致性的原理圖STYLEREF1\s4SEQ圖\*ARABIC\s11圖像a和圖STYLEREF1\s4SEQ圖\*ARABIC\s11圖像a和b之間的匹配REF_Ref513831618\h圖41(a)和REF_Ref513831618\h圖41(b)是一對匹配圖像，REF_Ref513831618\h圖41對他們之間的匹配點(diǎn)之間進(jìn)行了連線。圖STYLEREF1\s4SEQ圖\*ARABIC\s12REF_Ref513831618\h圖圖STYLEREF1\s4SEQ圖\*ARABIC\s12REF_Ref513831618\h圖41(a)和REF_Ref513831618\h圖41(b)所有的匹配描述子基于角度差的頻率統(tǒng)計(jì)REF_Ref514244703\h圖42有一個(gè)很明顯的峰值出現(xiàn)，峰值出現(xiàn)在大約?π/4附近，即在角度差大約為?π圖STYLEREF1\s4SEQ圖\*ARABIC\s13圖像a和b之間的匹配對匹配圖像REF_Ref514244782\h圖43(a)和REF_Ref514244782\h圖4圖STYLEREF1\s4SEQ圖\*ARABIC\s13圖像a和b之間的匹配圖STYLEREF1\s4SEQ圖\*ARABIC\s14REF_Ref514244782\h圖圖STYLEREF1\s4SEQ圖\*ARABIC\s14REF_Ref514244782\h圖43(a)和REF_Ref514244782\h圖43(b)所有的匹配描述子基于尺度差的頻率統(tǒng)計(jì)同樣有峰值出現(xiàn)在大約3/4附近，這表示在尺度差（尺度差是關(guān)鍵點(diǎn)半徑的對數(shù)差）3/4附近匹配到的描述子最多，這同樣符合肉眼觀察到的縮放現(xiàn)象?？梢哉J(rèn)為峰值附近的值就是特征尺度和主導(dǎo)方向，如果加入權(quán)重考量，在特征尺度和主導(dǎo)方向的相似度得分就是最高的峰值，其余位置的匹配都是噪聲，將它們都過濾掉，不計(jì)入投票分?jǐn)?shù)?？紤]弱幾何一致性的相似度計(jì)算考慮一對匹配的圖像，它們之間會(huì)有一個(gè)一致性的變化，弱幾何一致性會(huì)過濾掉角度和尺度方面變換不一致的特征，這是通過假設(shè)以下變換分別估計(jì)查詢圖像和參考圖像之間的旋轉(zhuǎn)和縮放參數(shù)來完成的REF_Ref513817036\r\h[13]：xxq,yqT和xt,ytT是查詢圖像和參考圖像的匹配位置，s和θ以及將弱幾何一致性應(yīng)用到倒排索引中，修改式2-7的分?jǐn)?shù)更新函數(shù)，得到：sδa和δs是量化后的角度差和尺度的對數(shù)差，注意這里需要對角度差和尺度差做一些處理。首先是角度差需要限制在?π,π的區(qū)間，那么給定角度差，可以對其正切值反正切，正切值需要對應(yīng)正確的象限，這可以從正弦值和余弦值中得出。其次，對于尺度，保存其對數(shù)，然后再計(jì)算的是對數(shù)差，即兩個(gè)尺度比值的對數(shù)，對數(shù)差限制在?ssi這個(gè)初始分?jǐn)?shù)是一個(gè)二維的直方圖，角度和尺度差量化后的值作為矩陣的索引，確定位置后往該處加上匹配函數(shù)的值，最后取所有位置的分?jǐn)?shù)當(dāng)中的最大值作為最后分?jǐn)?shù)s這么做的動(dòng)機(jī)就是盡量利用角度和尺度信息剔除不屬于一致變換的特征，找到si這個(gè)二維直方圖的分?jǐn)?shù)峰值，并認(rèn)為這個(gè)峰值所在位置的角度差和尺度差就是式2-1所展現(xiàn)的變換的值s和θ在實(shí)驗(yàn)中，角度和尺度信息分別都是獨(dú)立變化的，因此沒有必要在一個(gè)二維的直方圖上投票，可以將它們分開計(jì)算，更新方式如下：ssiδ即分別在角度差和尺度差對應(yīng)的一維直方圖上投票計(jì)算相似度分?jǐn)?shù)，將它們看作是二維的直方圖的邊緣概率。之后將兩者統(tǒng)一起來，得到最后的分?jǐn)?shù)：s角度差對應(yīng)的分?jǐn)?shù)和尺度差對應(yīng)的分?jǐn)?shù)都是取各自直方圖中的最大值，兩者之間再取一個(gè)最小值，就作為最后的分?jǐn)?shù)。二維轉(zhuǎn)化為一維計(jì)算可以降低內(nèi)存和CPU的消耗，上式也是對式4-3的合理估計(jì)。弱幾何一致性方法同樣很好的利用了倒排索引結(jié)構(gòu)，在漢明嵌入的基礎(chǔ)上，繼續(xù)向倒排列表每個(gè)列表項(xiàng)中的每個(gè)條目加上弱幾何信息，即弧度形式的角度和尺度的對數(shù)，并沒有增加多少空間消耗。在查詢時(shí)間方面，弱幾何一致性拖慢了查詢的速度。尤其是對沒有利用到漢明嵌入時(shí)的單一弱幾何一致性的應(yīng)用來說，查詢一幅圖的時(shí)間可以達(dá)到十秒左右，這主要是由于它利用的是式4-4來計(jì)算投票分?jǐn)?shù)，即對兩個(gè)直方圖的更新，而直方圖的更新訪問具有隨機(jī)性，這就無法利用到緩存。沒有經(jīng)過漢明嵌入過濾的原始特征數(shù)量很多，大量的直方圖更新操作增加了運(yùn)行的時(shí)間。而在同時(shí)添加漢明嵌入和弱幾何一致性后，時(shí)間相較于原來BoF模型來說，只是略微有所增加，還可以接受。不同于完整的幾何重排，弱幾何一致性方法能夠被利用到大規(guī)模圖像數(shù)據(jù)集。基于幾何信息的重排幾何匹配算法由于計(jì)算代價(jià)高昂不適用于大規(guī)模圖像檢索，但是它還是能夠應(yīng)用于重排序的過程，也就是對用前面所有的算法檢索得到的結(jié)果，選取前若干幅結(jié)果，然后對它們根據(jù)空間幾何信息進(jìn)行重排序。對幾十幅圖像進(jìn)行空間重排序的過程不會(huì)讓查詢時(shí)間增長多少，但卻是很好的增加檢索精度的方式。下面是詳細(xì)的介紹。隨機(jī)抽樣一致算法RANSAC(RANdomSAmpleConsensus，RANSAC)算法REF_Ref514443872\r\h[15]誕生于1981年，由Fischler和Bolles首次提出，這是一種需要迭代的方法，作用是從一組觀測數(shù)據(jù)中估計(jì)數(shù)學(xué)模型的參數(shù)，觀測數(shù)據(jù)可以包含異常值，并且異常值不會(huì)影響估計(jì)值。RANSAC并不會(huì)產(chǎn)生固定的結(jié)果，它只能是在一定概率的情況下產(chǎn)生相對合理的結(jié)果，但是如果整個(gè)過程包含更多的迭代，產(chǎn)生合理的結(jié)果概率會(huì)增加/wiki/Random_sample_consensus。/wiki/Random_sample_consensus一般要從包含異常值較少的數(shù)據(jù)集當(dāng)中擬合出適當(dāng)?shù)臄?shù)學(xué)模型，可以應(yīng)用最小二乘法，但如果數(shù)據(jù)包含很多的異常值，即噪聲較大，最小二乘法就顯得力不從心，這時(shí)候RANSAC就可以派上用場。RANSAC算法本身就假設(shè)了數(shù)據(jù)集中既包含正常值(inliers)，又包含異常值(outliers)，正常值可以被數(shù)學(xué)模型很好的描述(數(shù)學(xué)模型本身就來自正常值)，而異常值偏離了正常值的范圍很遠(yuǎn)，并且無法適應(yīng)由正常值得到的數(shù)學(xué)模型。如果給定一組可信的觀測數(shù)據(jù)，RANSAC算法假設(shè)存在一個(gè)能夠解釋數(shù)據(jù)的數(shù)學(xué)模型。RANSAC算法基本步驟如下：首先從輸入數(shù)據(jù)集中隨機(jī)的選擇一個(gè)子集，稱之為假設(shè)正常值(hypotheticalinliers)。對在假設(shè)正常值中的元素，擬合出相應(yīng)的數(shù)學(xué)模型，獲取模型參數(shù)，其中假設(shè)正常值中的元素個(gè)數(shù)確保能夠得到一個(gè)確定的模型。對所有其他數(shù)據(jù)針對擬合模型進(jìn)行測試。根據(jù)擬合模型對應(yīng)的損失函數(shù)，適合擬合模型的，就認(rèn)為與假設(shè)正常值是一致的，將其加入到一個(gè)集合中，稱為一致集(consensusset)。如果有足夠多的數(shù)據(jù)都被歸類于一致集，那就說明由假設(shè)正常值估計(jì)得到的模型是適當(dāng)?shù)?。對不在一致集的?shù)據(jù)，可以認(rèn)為它們就是異常值。而對在一致集中的成員，對它們進(jìn)行重新評估來改進(jìn)模型，這里可以利用最小二乘法。對上述的過程進(jìn)行若干次的迭代，每次迭代都會(huì)產(chǎn)生一個(gè)模型，如果沒有足夠多的數(shù)據(jù)都被歸類于一致集，那模型就會(huì)被拒絕，而如果這個(gè)是對上一次產(chǎn)生的模型的改進(jìn)，并且改進(jìn)后一致集的大小比未改進(jìn)的大，那這個(gè)模型會(huì)被保留，并應(yīng)用到下一次迭代。錯(cuò)配點(diǎn)剔除圖STYLEREF1\s4SEQ圖\*ARABIC\s15誤匹配的a和b將RANSAC算法應(yīng)用到重排序中，主要是用它來剔除匹配圖像的錯(cuò)配點(diǎn)，比如誤匹配圖像REF_Ref514244933\h圖45(a)和REF_Ref514244933\h圖45圖STYLEREF1\s4SEQ圖\*ARABIC\s15誤匹配的a和bREF_Ref514244933\h圖45是一對誤匹配的圖，連線的基本是錯(cuò)配點(diǎn)，如果計(jì)算了錯(cuò)配點(diǎn)對應(yīng)的權(quán)重分?jǐn)?shù)，那么顯然誤差會(huì)很大。這個(gè)問題下面應(yīng)用RANSAC算法來解決。首先是獲取兩幅圖像的匹配對。這些匹配對可以通過kNN算法獲取，對于查詢圖像的每個(gè)描述子，從參考圖像中獲得最鄰近的點(diǎn)。這種方法得到的所有匹配已經(jīng)基本沒有錯(cuò)配了，但是還可以進(jìn)一步的提升。首先考慮從參考圖像中獲取兩個(gè)距離最近的鄰居，稱為最鄰近點(diǎn)和次鄰近點(diǎn)，當(dāng)最鄰近點(diǎn)和查詢描述子的距離與次鄰近點(diǎn)和查詢描述子的距離的比值小于一個(gè)比率時(shí)，才認(rèn)為該最鄰近點(diǎn)是真正的匹配點(diǎn)。Lowe對這個(gè)比率做了很多測試REF_Ref513837297\r\h[12]，本文這里取值為0.7。圖STYLEREF1\s4SEQ圖\*ARABIC\s16剔除誤匹配點(diǎn)之后的圖4-5(a圖STYLEREF1\s4SEQ圖\*ARABIC\s16剔除誤匹配點(diǎn)之后的圖4-5(a)和圖4-5(b)可以看到，誤匹配點(diǎn)已經(jīng)基本沒有了，相應(yīng)的，他們經(jīng)過重排階段的得分會(huì)很低。利用RANSAC算法的幾何匹配只是應(yīng)用于最后的top_k幅圖像，因此雖然復(fù)雜度比較大也不會(huì)太過影響匹配時(shí)間，同時(shí)它能夠讓匹配結(jié)果有一個(gè)極好的提升。REF_Ref514414920\h圖47和REF_Ref514414924\h圖48體現(xiàn)了這樣的差異。從REF_Ref514414920\h圖47可以看到，盡管召回率很高，但是精度還很差。圖STYLEREF1\s4圖STYLEREF1\s4SEQ圖\*ARABIC\s17未經(jīng)過幾何重排的檢索結(jié)果圖STYLEREF1\s4SEQ圖\*ARABIC\s18經(jīng)過幾何重排的檢索結(jié)果實(shí)驗(yàn)過程本文實(shí)現(xiàn)的是一個(gè)在線的CBIR系統(tǒng)，下面介紹詳細(xì)的實(shí)現(xiàn)過程。開發(fā)環(huán)境本文基于flask框架搭建了web系統(tǒng)，主要的編程語言是python。圖像處理主要是利用的python版的opencv庫，機(jī)器學(xué)習(xí)算法則主要是利用scikit-learn庫，圖像繪制使用的是matplotlib工具包。其余的圖像檢索算法則自己實(shí)現(xiàn)。本圖像檢索系統(tǒng)的數(shù)據(jù)集可以按照需求指定，常見的有holidays、oxford5k和caltech101等，不同的數(shù)據(jù)集需要實(shí)現(xiàn)相應(yīng)的mAP評價(jià)標(biāo)準(zhǔn)的計(jì)算方法。本文這里選取了ukbench數(shù)據(jù)集的前5000幅圖作為實(shí)驗(yàn)數(shù)據(jù)集。系統(tǒng)開發(fā)環(huán)境的配置如下：操作系統(tǒng)：MicrosoftWindows10版本1709處理器：Intel(R)Core(TM)i5-4210MCPU@2.60GHz內(nèi)存：12.0GB磁盤：1T框架設(shè)計(jì)本圖像檢索系統(tǒng)主要包含web界面處理程序，以及圖像檢索的程序。web界面處理程序主要包含視圖函數(shù)處理，表單處理，以及相關(guān)靜態(tài)文件實(shí)現(xiàn)這些方面。圖像檢索的程序則分為幾大塊，首先是獲取圖像數(shù)據(jù)集和獲取數(shù)據(jù)集以及設(shè)計(jì)該數(shù)據(jù)集的檢索效果評價(jià)程序。其次是實(shí)現(xiàn)SIFT、RootSIFT特征提取，以及相應(yīng)特征匹配程序。漢明嵌入的相關(guān)實(shí)現(xiàn)和倒排索引結(jié)構(gòu)都需要分開實(shí)現(xiàn)。最后則是實(shí)現(xiàn)BoF模型，以及對上述程序的集成。實(shí)現(xiàn)圖STYLEREF1\s5SEQ圖\*ARABIC\s11預(yù)處理流程綜合上面所有的章節(jié)，本文的預(yù)處理流程可以由REF_Ref514442156\h圖STYLEREF1\s5SEQ圖\*ARABIC\s11預(yù)處理流程倒排列表最終是形成REF_Ref514442156\h圖51的結(jié)構(gòu)，其余的結(jié)果，比如視覺單詞，idf權(quán)重等，可以分開存儲(chǔ)。查詢的過程需要載入這些已經(jīng)計(jì)算好的結(jié)果，其中倒排索引比較大，可能會(huì)比較耗時(shí)，因此這里利用了@cached_property裝飾器，僅僅是第一次需要載入，之后直接保存在緩存中，不必再二次載入。圖STYLEREF1\s5SEQ圖\*ARABIC\s12檢索系統(tǒng)界面檢索系統(tǒng)的基本界面如REF_Ref514442287\h圖STYLEREF1\s5SEQ圖\*ARABIC\s12檢索系統(tǒng)界面共支持拖動(dòng)上傳，文件上傳以及粘貼圖片網(wǎng)址上傳這三種文件上傳方式。圖STYLEREF1\s5SEQ圖\*ARABIC\s13檢索效果檢索圖ukbench00060.jpg，檢索效果如REF_Ref514438765\h圖STYLEREF1\s5SEQ圖\*ARABIC\s13檢索效果本實(shí)驗(yàn)設(shè)置檢索結(jié)果一共返回20幅圖片。這里圖ukbench00060.jpg的mAP達(dá)到了100%，效果比較不錯(cuò)。最后對于檢索效果評價(jià)的結(jié)果如REF_Ref514245138\h表51所示。根據(jù)上述章節(jié)的設(shè)置，檢索數(shù)據(jù)集一共5000幅圖，設(shè)置的初始聚類數(shù)為5000，如果加了漢明嵌入，閾值則設(shè)為23。方法mAPbaseline0.706176baseline+HE0.877311baseline+WGC0.784954baseline+Reranking0.775631baseline+HE+WGC0.881024baseline+HE+Reranking0.902593baseline+HE+WGC+Reranking0.918762表STYLEREF1\s5SEQ表\*ARABIC\s11不同檢索方法的效果對比從REF_Ref514245138\h表51中可以看出，在原始BoF模型基礎(chǔ)上，單一增加了漢明嵌入的提升效果最好，加入重排或者弱幾何驗(yàn)證的提升則比較小。如果將這幾種方法都結(jié)合起來，最后的mAP評價(jià)可達(dá)到90%以上。結(jié)論本文介紹了基于內(nèi)容的圖像檢索相關(guān)算法及其基本原理，并設(shè)計(jì)建立了一個(gè)在線CBIR系統(tǒng)，進(jìn)行了實(shí)驗(yàn)驗(yàn)證。本文詳細(xì)介紹了類似于文本詞袋模型的BoF模型，及其背后基于視覺單詞匹配的數(shù)學(xué)原理。介紹了倒排索引相對于傳統(tǒng)正排表的優(yōu)勢，以及投票機(jī)制是如何更新相似度分?jǐn)?shù)的。本文也剖析了BoF的優(yōu)缺點(diǎn)，利用漢明嵌入方法改進(jìn)了原始模型，大大改進(jìn)了檢索系統(tǒng)的精度。本文最后一章講述弱幾何一致性方法，即利用部分幾何信息來作為量化描述子的匹配能力的補(bǔ)充。還有空間重排，通過剔除錯(cuò)配點(diǎn)來提升精度，使用的是RANSAC算法，對前面方法得到的結(jié)果進(jìn)行重排提升精度。除了本文所提到的方法外，還有其他方法提升檢索效果。聚類方面，比如利用層次聚類來減少聚類的時(shí)間。對于弱幾何一致性方法，還可以進(jìn)一步的在尺度和角度信息之外，利用平移信息來保證幾何的一致性，即加強(qiáng)的弱幾何一致性(EnhancedWeakGeometricConsistency,E-WGC)。對于大規(guī)模圖像檢索，可以利用哈希方法來提升檢索速度。近年來，深度學(xué)習(xí)方法被應(yīng)用到圖像檢索領(lǐng)域，這相比于傳統(tǒng)方法，檢索效果得到了進(jìn)一步提高。以上就是未來對圖像檢索系統(tǒng)提升的方向。參考文獻(xiàn)VeltkampRC,TanaseM,SentD.Content-BasedImageRetrievalSystems:ASurvey[J].Rapport,2001,36(03):2649–2661.張峰,鐘寶江.基于興趣目標(biāo)的圖像檢索[J].電子學(xué)報(bào),2018.SmeuldersAWM,WorringM,SantiniS,etal.Content-basedimageretrievalattheendoftheearlyyears[J].IEEETransactionsonpatternanalysisandmachineintelligence,200