徐 墨，劉福巖，余夢婷

(上海大學 計算機工程與科學學院，上海 200444)

基于自適應希爾伯特掃描和詞袋的圖像檢索

徐 墨，劉福巖，余夢婷

(上海大學 計算機工程與科學學院，上海 200444)

提出一種自適應希爾伯特掃描方法用于解決圖像檢索中使用詞袋模型丟失空間信息的問題。該方法通過分析特征在圖像中的分布來計算在越來越精細的分辨率下每個希爾伯特路徑的權重，從而為每張圖像選擇最優(yōu)的掃描路徑。探討了基于希爾伯特掃描樹的構建過程并對其優(yōu)缺點進行了分析，該方法能夠將圖像特征的空間信息有效地加載到樹的每個節(jié)點上。然后基于局部特征在圖像空間的分布提出一種多層次的自適應希爾伯特掃描策略。得益于此方法，在之后為圖像建立的基于希爾伯特樹形結構上，物體的空間信息將被保存得更加準確，從而有利于快速重建物體輪廓。在Caltech-256數據庫上進行了大量對比實驗，實驗結果表明該方法具有更高的檢索準確率。

希爾伯特掃描；圖像檢索；詞袋；特征表示

1 概 述

近年來，大規(guī)模數據庫中相似圖像檢索受到越來越多的關注。給出一張檢索圖像，目的是從數據庫中檢索出與其包含相同物體或場景的圖像。一個大規(guī)模檢索系統(tǒng)必須考慮三個因素：檢索準確率、內存使用和效率。

目前大部分先進的檢索技術都是基于詞袋模型(Bag-Of-Features,BOF)[1]。BOF模型的基本思想是將圖像表示成一組視覺單詞的直方圖。基于BOF的檢索系統(tǒng)首先需要提取每張圖像的局部特征，例如最流行的SIFT[2]；然后對特征空間聚類生成字典；最終通過特征映射，每張圖像可以用一個直方圖向量來表示。然而BOF忽略了特征的空間信息，不能獲取物體輪廓或者將物體從背景中分離出來。

為了解決這個問題，研究者們提出了一些BOF的衍生模型。例如文獻[3]將圖像分割成不同尺度下2l×2l個小塊，l=0,1,2，再分別計算每個小塊中BOF直方圖向量，最后將21個小塊中的向量連接起來形成最終的圖像描述向量。盡管此方法簡單可行，也取得了不錯的效果，但它必須將圖像分解成固定尺寸，導致其對嚴重混雜現象，幾何變形(如旋轉、尺度變化等)很敏感。文獻[4]提出一種空間權重BOF方法，此方法通過降低背景特征權重，從而突出物體輪廓與位置的重要性。盡管該方法對于混雜背景具有魯棒性，但它只適用于一些特定種類的圖像。文獻[5]將特征從二維空間以不同角度映射到一維空間，然后選取最具代表性的表示方法作為最終的直方圖描述向量。文獻[6]對特征向量重新編碼，將特征的空間信息加入投資向量中。此方法雖然有效，但字典維度太大，不適用于大規(guī)模圖像檢索。受文獻[5]的啟發(fā)，Hao和Kamata[7]將希爾伯特曲線與詞袋模型相結合，為每張圖像建立基于希爾伯特掃描的樹形結構(Hilbert-ScanBasedTree,HSBT)，特征空間信息通過一種聚類與過濾規(guī)則加載到樹的每個節(jié)點，但該方法忽略不同掃描路徑下生成的樹形結構，可能導致空間信息誤加載。

文中研究主要基于HSBT[7]結構，因為HSBT能有效地抓取物體輪廓并且壓制背景信息，但其對于特征空間信息的加載可能存在錯誤。使用希爾伯特曲線對圖像進行掃描時，必然導致圖像中相鄰兩塊區(qū)域在希爾伯特序列中分開。對一般圖像而言，由于大量特征提取自圖像中關鍵物體的局部外觀，如果這些特征所處區(qū)域位于希爾伯特掃描的分裂處，必然造成一些空間上相關的特征在映射到一維空間后也被分開，一些融合錯誤必然產生在HSBT建立過程中，導致抓取的物體輪廓失真，或者不能有效地將物體從背景中分離出來，進而影響最終的檢索準確率。于是，文中提出一種全新的自適應希爾伯特掃描策略用于為每張圖像選擇最適合它的希爾伯特掃描路徑。該策略基于兩個因素，第一是統(tǒng)計不同掃描路徑下分裂出兩個方塊中包含的特征總數。由于一般圖像中大部分特征都提取自關鍵物體，如果有一組相鄰方塊包含的特征點總數多于其他三組，這就意味著這兩塊區(qū)域很重要，不應該在一維空間中被分開，因此要避免使用該掃描路徑。然而，如果這兩塊相鄰區(qū)域中的大部分特征集中在其中一塊中，那么經過希爾伯特掃描之后，二維空間中的相關特征在一維空間依舊離得很近，保證了特征的空間位置一致性。為了有效地融合這兩個因素，加入一個權重參數用于控制它們的相對重要性。受希爾伯特掃描生成方法的啟發(fā)，將此方法從特征的全局幾何分布到局部幾何分布進行實施，從而更加有效地運用特征的空間信息。

2 基于自適應希爾伯特掃描的詞袋模型(AHS-BOF)

2.1 基于希爾伯特掃描的樹形結構

假設一張圖像的分辨率是m1×m2，當提取了SIFT特征點之后，用希爾伯特掃描[8]將這些特征點映射到一維空間并將一維序列平均分割成很多子區(qū)域，因為希爾伯特掃描能夠盡可能保存點的鄰域[9]。由于圖像尺寸不一定是正方形，于是提出一種偽希爾伯特掃描[10]，它最重要的優(yōu)點是像希爾伯特掃描一樣能夠盡可能保留每個點的鄰域。因此，該算法有助于文中研究工作。首先用偽希爾伯特曲線掃描整張圖像得到一個一維序列，用{L,F,R}來表示。其中，L表示特征點在圖像中的坐標集;F表示特征集;R表示L分割后所有子區(qū)域的集合。在映射與分割之后，通過對這些子區(qū)域進行聚類操作從而建立HSBT結構。

初始化：首先將線性序列S平均分割成v(1)個子區(qū)域，分解因子為δ，那么，m1×m2大小的圖像就被平均分割成v(1)=m1×m2/δ個不規(guī)則的小塊。由此可以統(tǒng)計每個子區(qū)域中的特征個數并過濾沒有特征的空白區(qū)域，進而可以得到G′，F′，C′。

重要區(qū)域選擇：在區(qū)域融合之前，首先選擇重要的子區(qū)域，具體細節(jié)如下：

其中，M為圖像中特征點的個數；Th為閾值，0

(1)

通過以上三個步驟可以為一幅圖像建立HSBT結構，如圖1所示。

圖1 圖像的HSBT結構

HSBT旨在將二維空間中的特征映射到一維空間，為每張圖像生成一個樹形結構。無需任何標記或手動操作，通過一定的聚類規(guī)則，特征的空間信息都被加載到樹的每個節(jié)點中。

在區(qū)域融合過程中，單一并且固定的掃描路徑可能會產生大量的融合誤差。目標是保證從關鍵物體中提取出來的特征在被映射到一維空間之后盡可能離得很近。在區(qū)域融合過程中，來自關鍵物體的特征會更快被融合到一起，從而有利于快速且準確地恢復關鍵物體輪廓，避免被不必要的噪聲特征干擾。下一節(jié)依據特征在圖像空間中的分布提出一種全新的自適應希爾伯特掃描策略。該策略可以為每張圖像選擇合適的希爾伯特掃描路徑，從而在建立HSBT結構時減少融合誤差并快速重建關鍵物體的輪廓。

2.2 自適應希爾伯特掃描

對于一般圖像，假設對其提取SIFT[2]特征點,那么大部分特征都是從其關鍵物體中提取出來的。在建立HSBT時，包含絕大多數特征的區(qū)域被選為重要區(qū)域，通過多次區(qū)域選擇與融合從而建立樹形結構。目標是確保這些重要區(qū)域在希爾伯特序列中盡可能離得很近，從而有效地減少融合誤差，快速重建重要物體或者場景的輪廓。對于一張圖像存在四種掃描方式(如圖2所示，其中黑色點表示特征點)，也會產生四種不同的線性序列。

圖2 四種希爾伯特掃描

在圖2中不難發(fā)現，第二與第三塊區(qū)域包含圖像中大部分特征，因此這兩塊區(qū)域在建立HSBT時會被選為重要區(qū)域。如果使用圖中第四種掃描路徑，那么塊二與塊三在一維序列中將被分開很遠。因而，很多不相關的特征點(比如從人和道路上提取出來的特征點)會夾雜在塊二與塊三之間，導致很多不相關特征融入塊二與塊三中，產生許多融合誤差，不利于重建重要區(qū)域輪廓。為了避免上述不好的掃描路徑，基于特征的分布情況提出一種全新的自適應希爾伯特路徑選擇策略。

上面提到過，如果某區(qū)域包含了圖像中大部分特征，那么該區(qū)域就是重要區(qū)域，如圖3中的塊二與塊三。因此，影響路徑選擇的第一個因素是在分裂邊緣(圖3中的黃色線條表示分裂邊緣)兩邊的子塊中所包含特征的個數。所以，第一個因素的公式表示為：

w1S=nA+nB/nC

(2)

其中，nA和nB分別表示分裂邊緣兩邊子塊各自包含特征的個數；nC表示整個圖像包含特征的個數；s表示第s個掃描路徑。

如圖2中所示，第三個掃描路徑中分裂邊緣兩邊子塊包含更多特征，那么它們就是重要區(qū)域，不應該被分開。但這時會產生一個問題：如果圖3中A和B兩塊中的特征集中分布在其中一塊中，即使這兩塊在一維序列中被分開，絕大多數特征仍然在一維空間離得很近，因而不會產生很多融合誤差。為了解決這個問題，文中又提出了另一個影響路徑選擇的因素：

w2S=min(nA,nB)/max(nA,nB)

(3)

如果接近1，那么A和B中所包含的特征個數幾乎相同。當特征被映射到一維空間時，大部分特征將被分離得很遠，從而產生大量融合誤差；相反，接近0時，表明大部分特征集中在其中一個方塊中，特征在一維空間中仍然距離很近，降低了融合誤差產生的可能性。此時很難判斷哪個因素對于最后的路徑選擇更重要，為了將這兩個因素有效結合，引入一個權重系數λ來控制兩個因素的相對重要性。公式如下：

WS=(1-λ)·w1S+λ·w2S

(4)

由文獻[7]可知，對于一個矩形空間，一般需要經歷數次分裂才會形成最終的希爾伯特掃描。例如一個大小為4×4的矩形需要兩次分裂才會生成最后的希爾伯特掃描(為基本形，不能再進行分裂，如圖4)。一般的圖像尺寸從幾十乘以幾十到幾千乘以幾千，很顯然僅僅計算一次分裂遠遠不足以評判哪個掃描路徑更好。比如，當和很相近時，宏觀上幾乎無法判斷哪個路徑更好(如圖2中的第二種和第四種)。因此，需要將目光投向特征在每個小塊中的分布，即更細粒度的分布。需要從宏觀和微觀兩個視角分析特征分布狀況。在此基礎上提出了一種多層次方法，見式(5)。

(5)

其中，i表示第i次分裂；j表示在第i次分裂中第j個子塊；k表示分裂次數；l表示每次分裂下子塊的個數；c表示一張圖像中所有特征的個數；cij表示第i次分裂中第j個子塊中特征點的個數；cij/c表示這個小塊相對于整張圖像的權重。

圖3 第一層希爾伯特掃描

圖4 4*4希爾伯特掃描

如果一個子塊包含的特征點多，那么它相對比較重要，它所分配到的權重值也應該越大。

上述方法不僅考慮了特征的全局幾何分布，也考慮了其局部幾何分布情況。由粗到細，從宏觀到微觀，全方位地考慮了特征的空間信息。

2.3 基于自適應希爾伯特掃描的詞袋模型

在為每一張圖像選擇了合適的路徑并建立HSBT之后，將BOF模型與HSBT相結合，這一部分主要有兩個步驟：字典生成和特征編碼。

(1)字典生成。

圖5 多層字典的生成示意圖

(2)特征編碼。

在字典生成之后，所有的局部特征必須映射到字典中的每個視覺單詞上。目前有許多字典映射的方法，例如向量量化(VectorQuantization，VQ)、稀疏編碼[11](SparseCoding,SP)、局部約束線性編碼[12](Locality-constrainedLinerCoding,LLC)和局部軟分配編碼[13](LocalSoft-assignmentCoding,LSC)等。VQ是一對一映射方法，即每一個局部特征映射到離它最近的視覺單詞上。但這沒有考慮到視覺單詞的歧義性，通常會帶來量化誤差。為了解決這一問題，提出了SP、LLC、LSC等方法，這些方法都將局部特征映射到多個視覺單詞上，并在圖像分類上取得了非常好的效果。然而這些方法或多或少都存在一些缺陷，其中最嚴重的缺點就是時間復雜度過大，而大規(guī)模圖像檢索問題對于檢索速度要求很高。為了在檢索準確率與檢索速度尋求一個平衡，最終還是選擇了VQ作為最后的特征編碼方法。

對于一張圖像，其樹形結構的高度為h，如果h大于H，只對其前H層進行量化；如果h小于H，只使用其前h層。最終，一張圖像可以被表示成一個多層次直方圖。編碼規(guī)則如下：

(6)

(7)

每一層的直方圖生成之后，使用最常用的TF-IDF方法對其進行加權。最終，將每一層的直方圖向量連接起來生成圖像特征描述向量。在計算圖像相似度時，采用文獻[7]中的CHI-Square方法。

3 實 驗

在Caltech-256上檢驗此方法。Caltech-256[14]由加州理工學院于2007年建立，其中包含256個類別，每個類別至少包含80張圖像，圖像總數為30 607。每個類別的圖像都是由人工手動挑選出來的。圖像類型涉及不同場景、光照、角度等條件下的自然與人工物體。實驗采用mAP(meanAveragePrecision)作為評價準則。為了訓練字典，隨機從每個類別中選取50張圖像作為訓練集，訓練方法采用K-means。然后再從每個類別中選5張圖像作為測試集。設δ為500，Th為0.8。和文獻[7]一樣，提取樹的前10層，字典大小設置為10k，20k，50k，100k。

圖6顯示了不同λ下幾種方法的對比。很明顯，第二層AHS-BOF的mAP優(yōu)于其他幾種方法。這也證明了文中的設想：多層次能夠有效抓取特征的空間信息。圖中的AHS-BCF-level2幾乎都在HS-BOF之上，這也表明該方法可能不會為圖像選擇最適合它的掃描路徑，但一定不會產生不利影響。在第二層，該方法相比于HS-BOF提高了大概3%的準確率。

圖6 不同λ下的mAP

表1顯示了在不同字典大小下AHS-BOF與其他幾種方法的對比。為了還原前人的結果，所有的實驗參數與文獻[7]一樣。當字典大小為100k時，其大小幾乎等于特征的個數，因而直方圖向量幾乎不具有辨識力，因此，選擇任何掃描路徑對最終的檢索結果都不會產生顯著影響。所以，AHS-BOF與HS-BOF的檢索結果幾乎相同。

表1 不同字典大小下mAP的比較

表2比較了不同分裂層數下mAP的大小。很明顯第二層的結果最好，第三層結果有所下降。這表明，過度重視特征的細節(jié)信息會將一個統(tǒng)一的物體割裂開，從而丟失物體全局外觀。

表2 不同分裂次數下mAP的比較

4 結束語

文中提出的自適應希爾伯特掃描策略能夠為每張圖像選擇合適的掃描路徑，減少了HSBT中的融合誤差，降低了物體重建所需樹的層數，節(jié)省了物體重建時間，有效地解決了BOF模型丟失特征空間信息的缺點。然而該方法對于復雜語義或者場景(臥室、客廳等)的圖像處理能力不夠，并且不同數據庫最優(yōu)的權重參數λ也不同。未來工作中，會嘗試更抽象的特征提取方法，并設計一種動態(tài)參數調節(jié)方法。

[1]SivicJ,ZissermanA.VideoGoogle:atextretrievalapproachtoobjectmatchinginvideos[C]//NinthIEEEinternationalconferenceoncomputervision.[s.l.]:IEEE,2003:1470-1477.

[2]LoweDG.Objectrecognitionfromlocalscale-invariantfeatures[C]//ProceedingsoftheseventhIEEEinternationalconferenceoncomputervision.[s.l.]:IEEE,1999:1150-1157.

[3]LazebnikS,SchmidC,PonceJ.Beyondbagsoffeatures:spatialpyramidmatchingforrecognizingnaturalscenecategories[C]//IEEEcomputersocietyconferenceoncomputervisionandpatternrecognition.[s.l.]:IEEE,2006:2169-2178.

[4]MarszaekM,SchmidC.Spatialweightingforbag-of-features[C]//IEEEcomputersocietyconferenceoncomputervisionandpatternrecognition.[s.l.]:IEEE,2006:2118-2125.

[5]CaoY,WangC,LiZ,etal.Spatial-bag-of-features[C]//IEEEconferenceoncomputervisionandpatternrecognition.[s.l.]:IEEE,2010:3352-3359.

[6]McCannS,LoweDG.Spatiallylocalcodingforobjectrecognition[M]//ACCV2012.Berlin:Springer,2012:204-217.

[7]HaoPengyi,KamataS.Hilbertscanbasedbag-of-featuresforimageretrieval[J].IEICETransactionsonInformationandSystems,2011,94(6):1260-1268.

[8]HilbertD.überdiestetigeAbbildungeinerLinieaufeinFl?chenstück[J].MathematischeAnnalen,1891,38:459-460.

[9]JagadishH,FaloutsosC,SaltzH.AnalysisoftheclusteringpropertiesoftheHilbertspace-fillingcurve[J].IEEETransactionsonKnowledgeandDataEngineering,2011,13(1):124-141.

[10]ZhangJ,KamataS,UeshigeY.Apseudo-Hilbertscanforarbitrarily-sizedarrays[J].IEICETransactionsonFundamentals,2007,90(3):682-690.

[11]YangJ,YuK,GongY,etal.Linearspatialpyramidmatchingusingsparsecodingforimageclassification[C]//IEEEconferenceoncomputervisionandpatternrecognition.[s.l.]:IEEE,2009:1794-1801.

[12]WangJ,YangJ,YuK,etal.Locality-constrainedlinearcodingforimageclassification[C]//IEEEconferenceoncomputervisionandpatternrecognition.[s.l.]:IEEE,2010:3360-3367.

[13]LiuL,WangL,LiuX.Indefenseofsoft-assignmentcoding[C]//IEEEinternationalconferenceoncomputervision.[s.l.]:IEEE,2011:2486-2493.

[14]GriffinG,HolubA,PeronaP.Caltech-256objectcategorydataset[R].California:CaliforniaInstituteofTechnology,2007.

Image Retrieval Based on Adaptive Hilbert Scan and Bag of Features

XU Mo,LIU Fu-yan,YU Meng-ting

(School of Computer Engineering and Science,Shanghai University,Shanghai 200444,China)

One fundamental problem in large scale image retrieval with the bag-of-features is its lack of spatial information.An approach called adaptive Hilbert-scan depended on distribution of features in an image is proposed.This method computes weight of each Hilbert-scan at increasingly fine resolutions by analysis of feature distribution in the image,which is able to assign a suitable scanning path for each image.Hilbert-scan based tree structure is studied and its advantage ad disadvantage is analyzed.The method adds the spatial information of local features into each node of tree,furthermore a novel adaptive Hilbert-scan strategy with multi-level is designed,which is built on the distribution of features in image.Owing to merits of this method,spatial information of features will be preserved more precisely in Hilbert-scan based tree structures.Extensive experiments on Caltech-256 show the effectiveness of the method.

Hilbert-scan;image retrieval;bag-of-features;feature representation

2016-02-22

2016-06-09

時間：2016-11-22

國家自然科學基金面上項目(61471232)

徐 墨(1989-)，男，碩士，研究方向為圖像處理與計算機圖形學；劉福巖，副教授，研究方向為計算機圖形學等。

http://www.cnki.net/kcms/detail/61.1450.TP.20161122.1227.028.html

TP301

A

1673-629X(2016)12-0017-05

10.3969/j.issn.1673-629X.2016.12.004