一種基于隨機化視覺詞典組和查詢擴展的目標檢索方法

趙永威 李弼程 彭天強 高毫林

(信息工程大學信息工程學院 鄭州 450002)

1 引言

圖像數據的集中和規模的增大給目標檢索帶來機遇的同時也帶來了挑戰，相較于傳統的基于全局的圖像檢索，目標檢索難度更大，面臨的問題也更多，如查詢目標的亮度、光照變化，視角的改變甚至部分目標被遮擋等。近年來，隨著計算機視覺，尤其是圖像局部特征(如 SIFT[1])和視覺詞典法[2,3](Bag of Visual Words,BoVW)的飛速發展及應用，使得目標檢索技術日趨實用化，如文獻[4]就是一種面向網絡的近似重復圖像檢索系統，文獻[5]則允許用戶使用手機拍攝圖片并檢索出與圖片中所包含目標的相關信息。

視覺詞典法最早由文獻[2]提出，由于性能突出，目前已經成為目標檢索領域的主流方法，但是它也存在一些開放性的問題。一是算法時間效率低及內存消耗大。視覺詞典法涉及到大量高維數據的近鄰查找問題，由此導致在數據規模很大的情況下，用于大規模高維近鄰查找的時間將急劇增加，使得算法效率很低。文獻[6]表明K-Means聚類算法只適用于生成較小規模的詞典，當詞典的規模超過510時就比較難以解決，為此，又引入了分層K-Means聚類算法(Hierarchical K-Means,HKM)來提高量化和檢索效率。在此基礎上，文獻[7,8]采用近似 K-means算法(Approximate K-Means,AKM)針對大規模數據庫的目標檢索實現了進一步優化，并引入倒排文檔結構(inverted file)來進一步提高檢索效率。盡管如此，內存消耗依然是其當前面臨的主要問題之一，文獻[7]表明傳統的視覺詞典法處理110萬幅的圖像仍要占用大約4.3 GB的內存。此外，K-Means及其改進算法(HKM,AKM等)不支持動態擴充[9]。二是視覺單詞的同義性和歧義性。由于沒有考慮特征點之間的空間關系，基于K-Means及其改進的聚類算法都會導致以下兩個問題：(1)聚類中心分布的不均勻特性[10]，進而產生由多個視覺單詞描繪同一圖像特征區域的現象，即造成視覺單詞的同義性；(2)偏離聚類中心的數據點會導致聚類中心產生偏移而造成視覺單詞的歧義性，即同一個視覺單詞描述的特征點之間存在很大差異的現象。對此，研究人員進行了諸多嘗試，如文獻[11]提出了一種軟分配方法(Soft-Assignment,SA)來構建視覺詞匯分布直方圖，文獻[12]則進一步驗證了軟分配方法對克服視覺單詞同義性和歧義性問題的有效性，文獻[13]在構建直方圖時引入了一種 QP 分配(Quadratic Programming)的策略提高了特征點與視覺單詞間的匹配精度。較于傳統的硬分配(hard-assignment)，它們都能在一定程度上克服視覺單詞的同義性和歧義性問題，然而，這些方法都是建立在采用K-Means以及其改進的聚類算法生成的視覺詞典基礎上的，都不能有效地解決BoVW方法存在的效率問題。此外，當人工界定的目標區域所包含的信息不能正確或不足以表達用戶檢索意圖時同樣不能得到理想的檢索結果，同時由于對特征點聚類生成視覺詞典時存在量化誤差，會導致原有特征信息的丟失。為此，文獻[14]提出了一種漢明切入(Hamming Embedding,HE)技術，同時證明了幾何驗證(geometric verification)對提高檢索查準率的有效性，但其計算復雜度較高，一般只用作對初始檢索結果的重排序，因而導致在提高查準率的同時也降低了查全率，Hsiao等人[15]則利用相關信息反饋過濾目標區域的噪聲。

精確歐氏位置敏感哈希[16]是位置敏感哈希LSH(Locality Sensitive Hashing)[17]在歐氏空間的一種實現方案，能夠實現快速的大規模高維數據近似近鄰查找，它能確保原始空間中距離較近的點，經過映射操作后，能夠以較大的概率哈希到同一個桶中，而相距較遠的點哈希到同一個桶的概率很小。因此，借鑒該思想，可以采用精確歐氏位置敏感哈希代替傳統的K-Means及其改進算法對訓練圖像庫的局部特征點進行聚類，生成一組隨機化視覺詞典，進而有效地避免多個單詞描述同一圖像區域和同一單詞描述的特征點之間有很大差異的現象。而查詢擴展[18]是應用在信息檢索中的一種常見技術，其核心思想是指利用計算機語言學、信息學等技術把與原查詢相關的概念添加到原查詢，得到信息量更為豐富、更為準確的查詢模型，它能有效地提高查全率。綜上所述，本文提出一種基于隨機化視覺詞典組和查詢擴展的目標檢索方法。新方法有效地解決了傳統聚類算法帶來的高運算復雜度和視覺單詞同義性及歧義性問題，并較好地增強了目標的區分性。

本文剩余部分組織如下。第 2節簡要介紹了E2LSH的基本定義和哈希原理；第3節給出了基于隨機化視覺詞典組和查詢擴展的目標檢索方法涉及的關鍵技術，其中，著重介紹了基于E2LSH的隨機化視覺詞典組的生成及由 tf-idf算法分配權重的視覺直方圖的構建；第4節對本文方法進行了實驗驗證和性能分析；最后，第5節為結束語。

2 相關知識

2.1 基本定義

LSH作為眾多哈希算法中的一種，是目前解決高維向量近似最近鄰問題的最優算法，在圖像檢索等領域有著廣泛的應用。但初始的LSH只適用于漢明空間，而E2LSH是LSH在歐氏空間的一種隨機化實現方法，增強了LSH的通用性，其位置敏感哈希函數是基于p-穩定分布的，它對高維稀疏數據具有很好的處理效果，特別是當高維向量中非零數據數目一定時，它的查詢時間不變，這個性質是其它算法所沒有的。故本文采用E2LSH對圖像局部特征點進行哈希，位置敏感函數以及p-穩定分布的定義如下：

定義1 給定點集S中任意點q,v∈S，稱函數族H={h:S→U}是位置敏感(locality sensitive)的，其中U為一實數集，如果函數

隨t嚴格遞減，即點q和v碰撞概率隨它們的距離遞減。

定義.2 對于一個實數集R上的分布D，如果存在p≥0，對任意n個實數v1,…,vn和n個服從D分布的隨機變量X1,…,Xn，使得隨機變量 ∑ivi Xi和同分布，則稱D為一個p-穩定分布。且對任何p∈[0,2]都存在穩定分布。

2.2 E2LSH哈希原理

具體地，E2LSH中使用的位置敏感哈希函數具有如下形式：

其中g(v)=(h1(v),…,hk(v))，那么，每個數據點v∈，經函數g(v)∈降維映射后，可以得到一個k維向量a=(a1,a2,…ak)。然后，再利用主哈希函數h1和次哈希函數h2對降維后向量進行哈希，建立哈希表并存儲數據點，h1和h2定義如下：

其中和是隨機整數，s是哈希表的大小，其取值為數據點的總個數，m為一個大的素數，常取值232-5。E2LSH將主哈希值h1和次哈希值h2都相同的數據點存儲在哈希表的同一個桶中，這樣就實現了數據點的空間劃分。

若將哈希表中每個桶的中心看成一個視覺單詞，那么整個哈希表就可看為一個視覺詞典，需要指出的是，由于函數g(v)的選取具有一定的隨機性，因此通過其建立的視覺詞典也帶有隨機性，本文為了降低這種隨機性，從函數族g中選取L個獨立的函數g1,…,gL，建立L個獨立的視覺詞典。

3 基于隨機化視覺詞典組和查詢擴展的目標檢索

針對傳統聚類算法的效率低及視覺單詞同義性和歧義性問題，本文采用E2LSH對訓練圖像庫的局部特征點聚類，得到一個隨機化的視覺詞典組，并引入查詢擴展策略構建信息量更為豐富、準確目標模型，具體流程如圖1所示。首先，根據文獻[1]的方法提取查詢目標和圖像數據庫中所有圖像的SIFT(Scale Invariant Feature Transform)特征，并對其進行E2LSH映射，實現特征點與視覺單詞的匹配，得到詞頻向量；其次，采用tf-idf算法對詞頻向量重新分配權重，完成視覺詞匯分布直方圖的構建，并針對傳統方法內存消耗大的問題，將圖像庫的直方圖特征存為索引文件，而不再直接對數據進行內存操作；然后，將查詢目標的詞匯直方圖特征與索引文件進行相似性匹配，得到初始結果；最后，綜合利用查詢目標和初始結果中正確匹配圖像的特征信息，并由查詢擴展策略構建信息量更為豐富的目標模型，進行二次或多次檢索，得到最終結果。

圖1 基于本文方法的目標檢索流程圖

3.1 基于E2LSH的隨機化視覺詞典組

對于 2.2節函數族g中的每個函數gi(i=1,…,L)，利用其分別對訓練圖像庫的SIFT點進行哈希聚類，則每個函數gi都能生成一個視覺詞典。那么，利用隨機選取的L個哈希函數g1,…,gL就能夠生成一個隨機化視覺詞典組，具體流程如圖2所示。其中，單個視覺詞典生成的詳細過程可描述如下：

(1)訓練圖像庫的SIFT特征提取。為保證實驗結果的公正性，本文以目標檢索常用的數據庫Oxford5K[19]作為訓練圖像庫，并提取包含K個SIFT特征點的圖像特征庫rK}，其中每個點ri都是一個128維的SIFT特征向量；

(2)E2LSH降維映射。對特征庫R中的每個SIFT點r，利用函數gi對其進行降維映射，得到k維的向量gi(r)；

(3)E2LSH 哈希聚類。按式(4)和式(5)分別計算S I F T 點r的主哈希值h1(gi(r))和次哈希值h2(gi(r))，并將主、次哈希值都相同的點哈希到同一個桶中，生成哈希表，完成特征點的聚類，其中表示哈希表Ti的第k個桶，Ni為哈希表Ti中包含桶的個數。然后計算每個桶的中心即視覺單詞，就能得到視覺詞典其中

圖2 隨機化視覺詞典組的生成示意圖

(4)視覺單詞過濾。對于每個視覺詞典Wi，包含數據點太少或太多的視覺單詞所攜帶信息的區分性往往不大，因此，在信息損失很小的前提下，可以將這些視覺單詞濾除掉，本文為每個視覺詞典都保留M個視覺單詞，即

由上述過程不難看出，隨機化視覺詞典組的構造過程是與數據無關的，為了檢驗E2LSH對數據點的聚類效果，本文將它與 K-Means聚類算法在MATLAB環境下進行仿真對比，結果如圖3(a)和圖3(b)所示。其中，圓點代表初始數據點，星點代表各聚類中心，對比圖3(a)和圖3(b)可以看出，KMeans聚類算法在數據點密集的區域聚類中心很多而在稀疏區域的聚類中心很少，而由E2LSH聚類得到的各個桶的中心分布更為均勻。

3.2 視覺詞匯分布直方圖

對于每幅圖像I，檢測出其所有的 SIFT特征點，并對特征點進行E2LSH映射，完成特征點與視覺單詞的匹配，然后統計其分布情況，則由每個視覺詞典都可生成1個M維的視覺詞匯分布直方圖特征，那么，由文中構造的L個詞典就能得到L個M維視覺詞匯分布直方圖H1,…,HL。其中，單個視覺詞匯分布直方圖構造方法可描述如下。

對于視覺詞典Wi中的任意單詞w，定義函數

其中ri代表圖像I的第i個SIFT點，g(ri)→w表示特征點ri能被哈希到單詞w所在的桶，ω(w,I)表示視覺單詞w在圖像I中所占的權重，其值由 tf-idf算法計算：

其中tf(w,I)表示單詞w在圖像I中的詞頻向量，N為訓練圖像庫的圖像總數，ni為圖像庫中出現單詞w的圖像數目，分母為歸一化因子，那么視覺單詞w在圖像I中的分布就可表示為

其中n為圖像I中總的SIFT點數目，其它視覺單詞的分布可同樣由上述方法得出，則由視覺詞典Wi就能生成M維的視覺詞匯分布直方圖特征H(H1,H2,…,HM)。

圖3 不同算法的聚類效果對比圖

3.3 相似性度量和平均查詢擴展

由于每個視覺詞匯分布直方圖特征都可看作是M維的空間向量，因此，本文將采用向量的點乘積來度量兩幅圖像的相似性。定義相似性度量函數如下：

查詢擴展作為相關反饋技術的一種，可以有效地豐富原有查詢的信息，構建更為準確的查詢模型。由文獻[11,18]知，查詢擴展有多種方法，綜合考慮性能及效率，本文將采用一種平均查詢擴展(average query expansion)的方法，對初始檢索結果的前N幅相關圖像的詞頻向量作平均，并將其作為查詢目標的新詞頻向量。其定義如下：

其中dq表示初始查詢的詞頻向量即 t f(wj,Q),j=1,…,M,di表示初始檢索結果中第i幅圖像的詞頻向量。

4 實驗結果與性能分析

本文實驗數據采用牛津大學為目標檢索及分類提供的Oxford5K[19]數據庫，共有5062幅圖像。其中，包含55幅標準的查詢圖像，每個目標選取5幅圖像，涵蓋了牛津大學的11處標志性建筑。此外，為了驗證本文方法在大規模數據下的實驗性能，又引入了Flickr1[20]數據庫作為干擾項。實驗硬件配置為Core 2.6 GHz×2，內存2 G的服務器。性能評價指標為平均查準率均值(Mean Average Precision,MAP)和查全率-查準率曲線，相關的定義如下：

AP(Average Precision)為查準率-查全率曲線所包含的面積，而MAP為5幅查詢圖像的平均AP值。

由本文中第2節內容，不難得出，參數L取值越大，算法的隨機性越小，但算法的效率會隨之降低，而參數k則對哈希表中桶的數目具有較大影響。本文以Oxford5K為訓練圖像庫，提取約16334970個特征點，然后采用不同的k,L值的E2LSH對其聚類分別生成不同規模的視覺詞典組，并分析其對目標檢索結果的影響，如圖4所示。其中圖4(a)反映了各查詢目標的MAP值隨哈希表數目的變化情況。圖4(b)反映了哈希表中桶個數與k取值之間的關系。綜合考慮到算法的精度和效率，本文取L=25,

首先，本文對視覺單詞同義性和歧義性問題作簡單說明，如圖5所示，其中w1-w5表示圖像局部特征點的各聚類中心(即視覺單詞)，數字 1-5表示圖像中的局部特征點。由圖5可知，特征點3,4,5在空間上距離很近，故可以認為它們表征圖像的同一區域內容，而特征點1,3在空間上距離很遠，用以表征圖像的不同區域。若采用硬分配方法[7]，則表示同一區域內容的特征點3,4,5將分別被分配到視覺單詞，即產生由多個視覺單詞描述同一特征區域的現象，造成視覺單詞的同義性，而表示不同區域的1,3將同時被分配到單詞w1造成視覺單詞的歧義性，而軟分配方法[11,12]由于同時將一個特征點分配到與之相近的幾個視覺單詞，因此可以在一定程度上克服視覺單詞的同義性和歧義性問題。本文采用的E2LSH算法在聚類時能將空間中相鄰較近點以較大的概率哈希到同一個桶，相距較遠的點則幾乎不被哈希到同一個桶，因此，特征點3,4,5將以較大的概率分配至同一個視覺單詞，而特征點1,3分配至同一單詞的概率極小。此外，本文采用多個哈希表構建視覺詞典組，在降低E2LSH算法隨機性的同時，也能夠實現同一特征點與多個距離相近的視覺單詞之間的匹配，故采用E2LSH構建隨機化視覺詞典組能夠克服視覺單詞的同義性和歧義性問題。

圖4 E2LSH參數的影響

圖5 視覺單詞同義性和歧義性問題示意圖

為了驗證采用E2LSH聚類生成一組隨機化視覺詞典組(Randomized Visual Dictionaries,RVD)并由E2LSH映射完成特征點與視覺單詞間匹配的方法對克服視覺單詞同義性和歧義性問題的有效性，本文將其與傳統的硬分配[7]方法(AKM+HA)和常用的軟分配[11,12]方法(AKM+SA)方法作比較，得查全率-查準率曲線如圖6所示。其中，硬分配和軟分配方法的視覺詞典均由AKM算法[7,8]生成，詞典規模為106。由圖6可知，基于隨機化視覺詞典組的方法相較于硬分配方法和軟分配方法具有更高的檢索精度，并且對于初始查全率低而導致查詢擴展使用受限的情況效果尤為明顯，說明利用E2LSH對特征點聚類能夠比較有效地克服視覺單詞的同義性和歧義性問題。

然后，將本文方法(Randomized Visual Dictionaries+Query Expansion,RVD+QE)與經典的基于AKM和軟分配的方法[11,12](AKM+SA)，軟分配與查詢擴展相結合的的方法(AKM+SA+QE)以及未引入查詢擴展的基于隨機化視覺詞典組(RVD)的方法在 Oxford5K數據庫上對部分目標的檢索精度作比較，總結了平均查詢擴展策略對檢索結果的影響，得MAP值如表1所示。從表1結果可以看出，對不同的查詢目標而言，AKM+SA方法的平均查準率均值(MAP)均低于其他3種方法。由于隨機化視覺詞典組較之AKM+SA更能有效地克服視覺單詞同義性和歧義性問題，因此，RVD方法的MAP值有所提高，但因RVD方法沒有構建信息量更為準確的目標模型，所以與 AKM+SA+QE方法相比略有遜色。而本文方法在隨機化視覺詞典組的基礎上又引入查詢擴展策略構建信息量更為準確、豐富的目標模型，其 MAP值均高于其它幾種方法。因此，采用查詢擴展策略構建目標模型能有效地提高目標檢索精度。

表1 平均查詢擴展策略對MAP值的影響(%)

圖6 不同方法的查準率-查全率曲線對比

此外，為了驗證本文方法在大規模圖像庫下的有效性，圖7給出了本文方法在Oxford5K+Flickr1數據庫上的一些目標檢索結果樣例。其中，上面 5幅 Magdalen圖像可由傳統的 BoVW 方法檢索得到，而下面5幅不易檢索的圖像可采用本文方法檢索得到，可見，采用本文方法能夠得到更多包含查詢目標的圖像。

圖7 基于本文方法的Magdale_2目標檢索結果

最后，將E2LSH和文獻[7,8]的AKM算法在構建視覺詞典及特征點與視覺單詞匹配時的時間消耗作了對比。首先，從訓練圖像庫中選取500幅圖像，提取約 1320000個 SIFT特征點，然后分別采用E2LSH和AKM算法進行聚類生成視覺詞典，并分別采用E2LSH映射與硬比對完成特征點與視覺單詞的匹配，實驗結果如圖8所示。從圖8 (a)可以看出，隨著視覺詞典規模增大，兩種方法的時間消耗都以近乎對數的形式增加，但由文獻[6,16]知，AKM 的時間效率與特征點數的多少成正比，而E2LSH算法則幾乎不受特征點數量的影響。從圖8(b)可以看出，硬比對方法的量化耗時隨著視覺詞典規模增大而線性增加，而 E2LSH方法隨著視覺詞典規模增大，其量化耗時基本保持不變。綜合圖8(a)和8(b)的對比可知，本文方法在圖像規模增大的情況下，依然可以保持較高的時間效率，具有更強的實用性。

5 結束語

本文采用E2LSH算法代替傳統的K-Means聚類及其改進算法對訓練圖像庫的局部特征點聚類，生成了一組支持動態擴充的隨機化視覺詞典組，并在此基礎上，利用E2LSH映射構建表征圖像內容的視覺詞匯直方圖特征，并將圖像庫的特征存為索引文件。此外，為構建信息量更為準確、豐富的目標模型，在初始檢索結果的基礎上，引入一種平均查詢擴展策略完成最終的目標檢索。實驗結果驗證本文方法在一定程度上有效地克服了傳統聚類算法帶來時間效率低、內存消耗大及視覺單詞的同義性和歧義性問題，并較好地增強了目標的區分性，能夠取得更好的檢索性能。需要指出的是，從硬盤中讀取索引文件需要一定的響應時間，而引入的查詢擴展策略有時需要多次迭代才能得到較好的效果，因此，也會帶來額外的時間開銷。所以，研究其它更為高效的目標檢索方法仍十分必要。

圖8 算法時間復雜度對比

[1]Lowe D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision,2004,60(2): 91-110.

[2]Sivic J and Zisserman A.Video Google: a text retrieval approach to object matching in videos[C].Proceedings of 9th IEEE International Conference on Computer Vision,Nice,2003: 1470-1477.

[3]Jurie F and Triggs B.Creating efficient codebooks for visual recognition[C].Proceedings of International Conference on Computer Vision,Beijing,2005: 604-610.

[4]Canada Idée Inc.Reverse image search system.http://www.tineye.com[2011-03].

[5]Google Company.Google goggles.http://www.google.com/mobile/goggles/[2011-03].

[6]Nister D and Stewenius H.Scalable recognition with a vocabulary tree[C].Proceedings of IEEE Conference on Computer Vision and Pattern Recognition,New York,2006:2161-2168.

[7]Philbin J,Chum O,Isard M,et al..Object retrieval with large vocabularies and fast spatial matching[C].IEEE Conference on Computer Vision and Pattern Recognition.Minneapolis,June 17-22,2007: 1-8.

[8]Cao Yang,Wang Chang-hu,Li Zhi-wei,et al..Spatialbag-of-features[C].IEEE Conference on Computer Vision and Pattern Recognition,San Francisco,USA,2010:3352-3359.

[9]Marée R,Denis P,Wehenkel L,et al..Incremental indexing and distributed image search using shared randomized vocabularies[C].Proceedings of MIR’10,Philadelphia,USA,2010: 91-100.

[10]Van Gemert J C,Snoek M,et al..Comparing compact codebooks for visual categorization[J].Computer Vision and Image Understanding,2010,114(4): 450-462.

[11]Philbin J,Chum O,Isard M,et al..Lost in quantization:improving particular object retrieval in large scale image databases[C].IEEE,Conference on Computer Vision and Pattern Recognition,Anchorage,Alaska,USA,June 2009:278-286.

[12]Van Gemert J C,Veenman C J,Smeulders A W M,et al..Visual word ambiguity[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(7): 1271-1283.

[13]Wang Jing-yan,Li Yong-ping,Zhang Ying,et al..Bag-offeatures based medical image retrieval via multiple assignment and visual words weighting[J].IEEE Transactions on Medical Imaging,2011,30(11): 1996-2011.

[14]Jegou H,Douze M,and Schmid C.Hamming embedding and weak geometric consistency for large scale image search[C].IEEE Conference on European Conference on Computer Vision,Heidelberg,2008: 1-29.

[15]Hsiao J H and Chang H.Topic-sensitive interactive image object retrieval with noise-proof relevance feedback[C].IEEE International Conference on Acoustics,Speech,and Signal Processing,Prague Congress Center,2011: 869-873.

[16]Datar M,Immorlica N,Indyk P,et al..Locality-sensitive hashing scheme based on p-stable distributions[C].Proceedings of the Twentieth Annual Symposium on Computational Geometry,Brooklyn,New York,2004:253-262.

[17]Gionis A,Indyk P,and Motwani R.Similarity search in high dimensions via hashing[C].Proceedings of the 25th International Conference on Very Large Data Bases (VLDB),Edinburgh,Scotland,1999: 518-529.

[18]Sajina R,Aghila G,and Saruladha K.A survey of semantic similarity methods for ontology based information retrieval[C].IEEE Second International Conference on Machine Learning and Computing,Bangalore,India,February,2010: 297-302.

[19]Robotics Research Group.Oxford5K dataset.http://www.robots.ox.ac.uk/_vgg/data/oxbuildings/.[2011-03].

[20]Yahoo Company.Flickr1 dataset.http://www.flickr.com/[2011-03].