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

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

1.北京信息科技大學(xué) 計(jì)算機(jī)學(xué)院 網(wǎng)絡(luò)文化與數(shù)字傳播北京市重點(diǎn)實(shí)驗(yàn)室，北京 100101

2.北京工業(yè)大學(xué) 信息學(xué)部，北京 100124

1 引言

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

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

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

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

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

目標(biāo)物體的位置關(guān)系是圖像的重要特征之一。空間關(guān)系是一種較為模糊的概念，它很難用一個(gè)確定的概念來描述清楚，通常這種概念是在一組限定的條件中進(jìn)行描述的[11]?？臻g關(guān)系通常包括朝向關(guān)系和拓?fù)潢P(guān)系。朝向關(guān)系指目標(biāo)的各部分之間或整體間的朝向?？梢允褂媚繕?biāo)之間的距離或者目標(biāo)與參照點(diǎn)之間的夾角來衡量。拓?fù)潢P(guān)系是目標(biāo)在參照點(diǎn)的平移、旋轉(zhuǎn)以及尺度變換下不發(fā)生變化的關(guān)系，強(qiáng)調(diào)目標(biāo)間相對位置關(guān)系。為表示圖像中目標(biāo)的朝向關(guān)系和拓?fù)潢P(guān)系需要獲得圖像的2-D串表達(dá)。

2.1 目標(biāo)位置關(guān)系的2-D串表達(dá)

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

以一幅圖像包含不同位置的4個(gè)不同目標(biāo)為例，如圖1所示。其在X軸的投影順序?yàn)锳、B、C、D，在Y 軸的投影順序?yàn)镈、B、C、A。應(yīng)用上述規(guī)則可以得到圖像目標(biāo)位置關(guān)系的2-D串表達(dá)：

x:A＜B＜C＜D

y:D＜B=C＜A

并簡化為：

x:A＜B＜C＜D

y:D＜BC＜A

圖1 （a） 原始圖

圖1 （b） 符號圖

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

2.2 構(gòu)建最長公共視覺詞串

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

圖2 圖像A與圖像B構(gòu)成的最長公共視覺詞串示意圖

具體檢索過程如下：

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

圖3 構(gòu)建視覺詞串流程圖

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

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

按如下規(guī)則計(jì)算最長公共視覺詞串

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

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

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

2.3 最長公共視覺詞串魯棒性強(qiáng)化

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

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

圖4 失配情況示例

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

圖5 抵抗噪聲示意圖

具體檢索過程如下：

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

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

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

按如下規(guī)則計(jì)算最長公共視覺詞串

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

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

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

3 實(shí)驗(yàn)結(jié)果

3.1 實(shí)驗(yàn)數(shù)據(jù)集

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

3.2 參數(shù)選擇

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

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

表1 SIFT數(shù)量對的mAP值的影響

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

3.3 方法比較與分析

如上節(jié)所述，LCVS在各不同參數(shù)下的準(zhǔn)確率均高于BoF和Eo-Bow方法，為了進(jìn)一步分析LCVS方法在哪類圖像中更有優(yōu)勢，選取BoF與LCVS的mAP結(jié)果最高的參數(shù)t，在Holiday數(shù)據(jù)集上進(jìn)行了查詢實(shí)驗(yàn)。

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

圖7 部分查詢結(jié)果對比

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

圖8 部分查詢結(jié)果對比

4 結(jié)論

（1）提出了一種基于最長公共視覺詞串的圖像檢索方法，應(yīng)用于自然圖像的檢索中。自然圖像的特征間的距離可以利用最長公共視覺詞串進(jìn)行表達(dá)，這樣的表達(dá)引入了圖像中目標(biāo)間的空間位置關(guān)系，提高了圖像檢索的結(jié)果。

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

（3）與傳統(tǒng)BoF方法和近年提出的改進(jìn)方法Eo-BoW方法進(jìn)行了對比實(shí)驗(yàn)，驗(yàn)證了基于最長公共視覺詞串的方法對于圖像檢索的有效性。實(shí)驗(yàn)結(jié)果表明基于最長公共視覺詞串的距離表達(dá)方式較直接計(jì)算特征距離的表達(dá)方式更能表達(dá)圖像中目標(biāo)間的位置關(guān)系，具有更好的檢索效果。