基于最長公共視覺詞串的圖像檢索方法

苗 軍，崔 嵩，段立娟，張 璇，許少武

1.北京信息科技大學 計算機學院 網絡文化與數字傳播北京市重點實驗室，北京 100101

2.北京工業大學 信息學部，北京 100124

1 引言

基于內容的圖像檢索（Content-Based Image Retrieval，CBIR）是與人類檢索圖像過程更為接近的圖像檢索方式。理想的基于內容的圖像檢索可以跨越語義鴻溝，讓計算機理解圖像的內容，從而根據對于圖像的理解檢索對應的圖像。這個檢索過程通常被建模為圖像特征表達、相似性度量和后處理過程三個部分。其中圖像的特征表達和相似性度量是跨越語意鴻溝，使計算機理解圖像的關鍵，也是影響圖像檢索準確性的最主要問題。

“詞袋”模型（Bag-of-Features，BoF model）借鑒自文本檢索[1]，并在圖像檢索中取得了較好的結果。“詞袋”模型主要分為三個步驟。第一步，提取圖像局部特征（如SIFT特征）；第二步，聚類圖像中的局部特征，構建視覺詞碼本；第三步，將圖像特征映射到視覺詞碼本上，得到該圖像中視覺詞出現的頻率直方圖。這一映射可以看作特征量化的過程。特征量化提高了圖像特征的魯棒性，降低了特征的維度，但損失了視覺詞之間潛在的空間關系，影響對于圖像檢索至關重要的距離的表達。

為進一步提高檢索的性能，需要引入空間信息來減少“詞袋”模型中視覺詞帶來的歧義。一些研究者對于空間信息的引入做了深入研究[1-7]。其中，許多圖像檢索模型在后處理過程中引入空間信息來對“詞袋”模型的結果進行重排序，如RANSAC方法[2]和鄰近特征一致性方法（neighboring feature consistency）[1]。這些方法表明加入空間信息對于檢索質量有提高作用，但其計算復雜度通常較高。另一方面，Passalis等人在他們的工作中將熵優化策略引入詞袋的構建中，提出了熵優化詞袋模型（Entropy Optimized BoW，Eo-BoW）[8]。此外，Mohedano等人嘗試將BoF與CNN結合以提高檢索速度，盡管在實驗數據集上取得了一定成效，但卻存在對干擾圖像敏感的問題[9]。

由于二維圖像是三維場景在一個二維平面上的投影。場景中的不同物體的位置關系在二維圖像中得到了一定程度的保持。通常描述空間關系的方法有兩種：基于目標的描述和基于關系的描述。基于目標的描述方法先提取圖像中目標的坐標，然后通過對坐標進行空間位置劃分來實現對圖像的描述。常用的基于目標的描述方法有網格法、四叉樹[10]、二叉樹、k-d樹等。基于關系的描述是通過分離空間關系和視覺信息，抽象化目標之間的空間位置關系，對抽象的目標關系進行建模分析。本文提出一種基于最長公共視覺詞串的方法引入圖像中目標間的空間位置關系，利用視覺詞來構建視覺詞串，并采用最大似然準則衡量詞串間的相似度。并通過實驗驗證了提出方法對于圖像檢索的有效性。

2 基于最長公共視覺詞串的圖像檢索

目標物體的位置關系是圖像的重要特征之一。空間關系是一種較為模糊的概念，它很難用一個確定的概念來描述清楚，通常這種概念是在一組限定的條件中進行描述的[11]。空間關系通常包括朝向關系和拓撲關系。朝向關系指目標的各部分之間或整體間的朝向。可以使用目標之間的距離或者目標與參照點之間的夾角來衡量。拓撲關系是目標在參照點的平移、旋轉以及尺度變換下不發生變化的關系，強調目標間相對位置關系。為表示圖像中目標的朝向關系和拓撲關系需要獲得圖像的2-D串表達。

2.1 目標位置關系的2-D串表達

圖像中目標間的位置關系可以利用目標物體在兩個正交方向上的投影轉化為兩個1-D的排序表達，這樣的表達可以表示目標間的拓撲關系和朝向關系。借鑒符號圖的2-D串表達[12]，一幅自然圖像也可以表示為視覺詞的2-D串。首先，將圖像中的物體表示為視覺詞，將每個視覺詞看作一個符號向x方向與y方向進行投影。其中，“詞袋”模型提取的局部特征即是視覺詞的一種表示。為表示視覺詞在兩個方向上的排序，利用如下符號表示規則：“x：”或“y：”表示在X或Y軸上投影得到的視覺詞串，其中在X軸投影得到的串叫x串，在Y軸投影得到的串叫y串。“<”表示排序關系，代表視覺詞的投影沿X軸從左向右排序，沿Y軸從下向上排序。“=”表示重疊關系，代表兩個視覺詞的投影并列排序。則可利用上述規則構建圖像目標位置關系的2-D串。

以一幅圖像包含不同位置的4個不同目標為例，如圖1所示。其在X軸的投影順序為A、B、C、D，在Y 軸的投影順序為D、B、C、A。應用上述規則可以得到圖像目標位置關系的2-D串表達：

x:A＜B＜C＜D

y:D＜B=C＜A

并簡化為：

x:A＜B＜C＜D

y:D＜BC＜A

圖1 （a） 原始圖

圖1 （b） 符號圖

這樣圖像的相似度問題可以轉化為字符串的相似度問題。在得到圖像的2-D串的表達后，還需要使用一些策略來計算串與串的相似度。本文采用最大似然準則求解兩個字符串的最長公共子串，并以此衡量圖像間的相似度。

2.2 構建最長公共視覺詞串

為提高檢索的效果，本文在“詞袋”模型中引入表達圖像中物體間空間信息的最長公共視覺詞串（Longest Common Visual Substring，LCVS）。2-D串是圖像中目標物體間的位置關系的一種表達，且需要確定物體的位置及種類。“詞袋”模型將圖像用訓練好的字典進行表達，這樣一幅圖像就可以表示為字典中視覺詞的組合。如圖2所示，通過視覺詞在X軸與Y軸上的投影將圖像表示為視覺詞串，視覺詞串反映了視覺詞之間的拓撲結構，包含很多空間語義信息。在查詢階段，計算待查詢圖像與數據庫中圖像的最長公共視覺詞串。最長公共視覺詞串反映了兩幅圖像的相似程度，公共視覺詞串越長兩幅圖像越相似。構建視覺詞串的流程圖如圖3所示。

圖2 圖像A與圖像B構成的最長公共視覺詞串示意圖

具體檢索過程如下：

步驟1提取查詢圖像特征并進行量化投影，得到查詢圖像中視覺詞串。對于查詢圖像imagequery，提取其SIFT特征F=[f1,f2,…,fl]，并將SIFT特征量化得到視覺詞集合W={w1,w2,…,wm}，其中m為字典中視覺詞的數量。之后，將視覺詞分別向X軸和Y軸投影，得到查詢圖像的視覺詞串xquery和yquery。

圖3 構建視覺詞串流程圖

步驟2提取數據庫中圖像特征并進行量化投影，得到數據庫中圖像的視覺詞串。給定數據庫中圖像imagei，提取其SIFT特征并進行特征量化得到視覺詞串與。

步驟3計算查詢圖像與數據庫中圖像的最長公共視覺詞串。

按如下規則計算最長公共視覺詞串

其中Lcs(String1,String2)表示兩個串的最長公共子串，LCVS_X(i)和LCVS_Y(i)分別是查詢圖像imagequery與數據庫中圖像imagei在X軸和Y軸上的最長公共視覺詞串。Max_LCVS(i)是LCVS_X(i)和LCVS_Y(i)中較大的串作為圖像imagequery與imagei的最長公共視覺詞串。

步驟4根據最長公共視覺詞串計算查詢圖像與數據庫中圖像的相似度得分。

其中，idf(·)表示“詞袋”模型中每個視覺詞的權重，即逆向文件頻率。根據相似度得分的高低對數據庫中圖像進行排序，得到圖像檢索結果。

2.3 最長公共視覺詞串魯棒性強化

最長公共視覺詞串包含了兩幅圖像的公共隱含模式，但構造的視覺詞串仍不具有旋轉不變性。

如圖4所示，圖像I1和I2相似度較高，且兩者相差90°旋轉。假設兩幅圖像包含的視覺詞構成符號圖Is1和Is2，那么根據2.2節中的方法可以得到兩幅圖像的最長公共視覺詞串為A其長度為1，從最長公共視覺詞串看這兩幅圖像相似度并不高，檢索失配。為了解決這種情況的失配問題，增加方法的旋轉不變性，查詢圖像分別經過0°、90°、180°、270°旋轉，再與數據庫中圖像匹配最長公共視覺詞串，取最長公共視覺詞串中最大的作為結果。這樣的過程提高了最長公共視覺詞串的魯棒性，對噪聲與仿射變換有一定程度的不變性。

圖4 失配情況示例

圖5 展示了匹配對于噪聲影響不敏感。如果有噪聲出現在兩幅相似的圖像的其中一幅中，單詞串的構造仍然不會受到干擾。這種樸素的構造方式是簡單的，易于理解的，在后面的測試中也展現了良好的效果。

圖5 抵抗噪聲示意圖

具體檢索過程如下：

步驟1提取查詢圖像特征并進行量化投影，得到查詢圖像中視覺詞串。對于查詢圖像imagequery，提取其SIFT特征F=[f1,f2,…,fl]，并將SIFT特征量化得到視覺詞集合W={w1,w2,…,wm}，其中m為字典中視覺詞的數量。之后，將視覺詞分別向X軸和Y軸投影，得到查詢圖像的視覺詞串xquery0和yquery0。旋轉查詢圖像重復上述操作得到旋轉不同角度查詢圖像的視覺詞串

步驟2提取數據庫中圖像特征并進行量化投影，得到數據庫中圖像的視覺詞串。給定數據庫中圖像imagei，提取其SIFT特征并進行特征量化得到視覺詞串與。

步驟3計算查詢圖像與數據庫中圖像的最長公共視覺詞串。

按如下規則計算最長公共視覺詞串

其中Lcs(String1,String2)表示兩個串的最長公共子串，patternX(r)和 patternY(r)分別是旋轉r°后的查詢圖像imagequery(r)與數據庫中圖像imagei在X軸和Y軸上的最長公共視覺詞串。 patternMax(r)是 patternX(r)和patternY(r)中較大的串，作為旋轉r°圖像imagequery(r)與imagei的最長公共視覺詞串。 pattern取不同角度旋轉下最大的串，作為最終查詢圖像的最長公共視覺詞串。

步驟4根據最長公共視覺詞串計算查詢圖像與數據庫中圖像的相似度得分。

其中，idf(·)表示“詞袋”模型中每個視覺詞的權重，即逆向文件頻率。根據相似度得分的高低對數據庫中圖像進行排序，得到圖像檢索結果。

3 實驗結果

3.1 實驗數據集

實驗在Holiday數據集上運行，該數據集是法國INRIA機構在2008年發布的。該數據集共有500類圖像，每類圖像有2～6幅不等，共計1 491幅。數據集中圖像的尺寸不一，大部分圖像的分辨率為2 048×1 536，在實驗中統一調整為1 024×768。Holiday數據集中的圖像都是對同一目標或場景進行的不同角度的拍攝。INRIA提供了數據集每幅圖像的SIFT特征和訓練好的字典[13]。字典的維度從100維到200 000維。下面在與“詞袋”模型對比的實驗中均采用200 000維的字典[14]。按照數據集的說明，每一類的第一幅圖像作為查詢圖像，在查詢圖庫的過程中要排除自身，在剩余圖像中計算排名，使用Average Precision（AP）作為衡量系統的指標。在500類圖像進行500次查詢，然后求其平均值mAP（mean Average Precision），以此作為衡量系統的評價指標。

3.2 參數選擇

在實驗中，并不使用每幅圖像的全部SIFT特征，而是選取顯著度最大的t個作為該圖像的特征。顯著度是由特征點的Hessian矩陣的行列式值和該矩陣的跡共同求得。下面“詞袋”模型縮寫為BoF，本文提出方法縮寫為LCVS。BoF、Eo-BoW與LCVS在參數t的選擇上的最優有一定區別，因此，實驗參數t由500到4 000間隔500進行調整計算在Holiday數據集上的mAP值。

實驗結果如表1與圖6所示。LCVS方法在不同的參數t下的mAP均高于BoF與Eo-BoW。BoF與Eo-BoW模型在t=2 500時最高，前者mAP為0.572 0，后者僅為0.490 0。相比LCVS方法在t=3 000處取得最高的mAP=0.603 6，高于前兩種模型的結果。其中，BoF模型與LCVS模型的SIFT特征數量從2 000后，mAP值的增長放緩，這說明當描述圖像所需的特征達到一定數量之后，過多的特征引入對系統起到的作用有限，反而影響特征的魯棒性，出現震蕩或者下降。

表1 SIFT數量對的mAP值的影響

圖6 在Holiday圖庫上不同SIFT特征數目的mAP曲線比較

3.3 方法比較與分析

如上節所述，LCVS在各不同參數下的準確率均高于BoF和Eo-Bow方法，為了進一步分析LCVS方法在哪類圖像中更有優勢，選取BoF與LCVS的mAP結果最高的參數t，在Holiday數據集上進行了查詢實驗。

選出了LCVS提高了檢索結果的6類典型檢索圖像及結果進行了展示。如圖7所示，第一列圖像為查詢圖像，第二列為同類的待查圖像，第三列為待查圖像用BoF、Eo-Bow和LCVS三種方法檢索的排名。這6類圖像中每類有1～3張同類圖像。其中，LCVS方法對于待檢圖像均成功檢出，BoF方法只有413類的橋正確檢出。

圖7 部分查詢結果對比

通過對于更多圖像的觀察與分析，相比于傳統的BoF方法，LCVS對于明暗變化不敏感；對于旋轉、縮放、平移LCVS方法檢索結果較好；對于細節豐富的場景有不錯的檢索結果。對于細節豐富的場景，LCVS可以充分利用關鍵特征點間的空間位置關系，從而提高了圖像檢索的效果。從實驗對比中發現，LCVS方法在許多BoF和Eo-BoW檢索效果一般的圖像上有了較大的提高，成功檢索出待檢圖像。LCVS檢索結果變差的典型結果如圖8所示，其中，第11類和174類兩種方法均未能正確檢索出同類圖像而LCVS將正確的圖像排在了較后的位置。總結發現主要包括兩類圖像，圖像中缺少有效的細節信息，如大片的沙灘海洋、藍天白云、森林；圖像中細節豐富，且待查圖像有很多新的細節加入，如車等物體遮擋了待檢索的建筑。這樣的結果也較大地受到了SIFT提取到的關鍵點的影響，當提取的關鍵點很少，或缺少待檢索物體的關鍵信息時，LCVS方法將達不到理想的效果。

圖8 部分查詢結果對比

4 結論

（1）提出了一種基于最長公共視覺詞串的圖像檢索方法，應用于自然圖像的檢索中。自然圖像的特征間的距離可以利用最長公共視覺詞串進行表達，這樣的表達引入了圖像中目標間的空間位置關系，提高了圖像檢索的結果。

（2）設計方法提高了檢索的魯棒性，對噪聲與仿射變換有一定程度的不變性，并采用最大似然準則衡量詞串間的相似度。

（3）與傳統BoF方法和近年提出的改進方法Eo-BoW方法進行了對比實驗，驗證了基于最長公共視覺詞串的方法對于圖像檢索的有效性。實驗結果表明基于最長公共視覺詞串的距離表達方式較直接計算特征距離的表達方式更能表達圖像中目標間的位置關系，具有更好的檢索效果。