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

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

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

為進(jìn)一步提高檢索的性能，需要引入空間信息來(lái)減少“詞袋”模型中視覺(jué)詞帶來(lái)的歧義。一些研究者對(duì)于空間信息的引入做了深入研究[1-7]。其中，許多圖像檢索模型在后處理過(guò)程中引入空間信息來(lái)對(duì)“詞袋”模型的結(jié)果進(jìn)行重排序，如RANSAC方法[2]和鄰近特征一致性方法（neighboring feature consistency）[1]。這些方法表明加入空間信息對(duì)于檢索質(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ù)集上取得了一定成效，但卻存在對(duì)干擾圖像敏感的問(wèn)題[9]。

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

2 基于最長(zhǎng)公共視覺(jué)詞串的圖像檢索

目標(biāo)物體的位置關(guān)系是圖像的重要特征之一?？臻g關(guān)系是一種較為模糊的概念，它很難用一個(gè)確定的概念來(lái)描述清楚，通常這種概念是在一組限定的條件中進(jìn)行描述的[11]?？臻g關(guān)系通常包括朝向關(guān)系和拓?fù)潢P(guān)系。朝向關(guān)系指目標(biāo)的各部分之間或整體間的朝向。可以使用目標(biāo)之間的距離或者目標(biāo)與參照點(diǎn)之間的夾角來(lái)衡量。拓?fù)潢P(guān)系是目標(biāo)在參照點(diǎn)的平移、旋轉(zhuǎn)以及尺度變換下不發(fā)生變化的關(guān)系，強(qiáng)調(diào)目標(biāo)間相對(duì)位置關(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)系。借鑒符號(hào)圖的2-D串表達(dá)[12]，一幅自然圖像也可以表示為視覺(jué)詞的2-D串。首先，將圖像中的物體表示為視覺(jué)詞，將每個(gè)視覺(jué)詞看作一個(gè)符號(hào)向x方向與y方向進(jìn)行投影。其中，“詞袋”模型提取的局部特征即是視覺(jué)詞的一種表示。為表示視覺(jué)詞在兩個(gè)方向上的排序，利用如下符號(hào)表示規(guī)則：“x：”或“y：”表示在X或Y軸上投影得到的視覺(jué)詞串，其中在X軸投影得到的串叫x串，在Y軸投影得到的串叫y串?！?”表示排序關(guān)系，代表視覺(jué)詞的投影沿X軸從左向右排序，沿Y軸從下向上排序。“=”表示重疊關(guān)系，代表兩個(gè)視覺(jué)詞的投影并列排序。則可利用上述規(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

并簡(jiǎn)化為：

x:A＜B＜C＜D

y:D＜BC＜A

圖1 （a） 原始圖

圖1 （b） 符號(hào)圖

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

2.2 構(gòu)建最長(zhǎng)公共視覺(jué)詞串

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

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

具體檢索過(guò)程如下：

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

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

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

步驟3計(jì)算查詢(xún)圖像與數(shù)據(jù)庫(kù)中圖像的最長(zhǎng)公共視覺(jué)詞串。

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

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

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

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

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

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

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

圖4 失配情況示例

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

圖5 抵抗噪聲示意圖

具體檢索過(guò)程如下：

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

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

步驟3計(jì)算查詢(xún)圖像與數(shù)據(jù)庫(kù)中圖像的最長(zhǎng)公共視覺(jué)詞串。

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

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

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

其中，idf(·)表示“詞袋”模型中每個(gè)視覺(jué)詞的權(quán)重，即逆向文件頻率。根據(jù)相似度得分的高低對(duì)數(shù)據(jù)庫(kù)中圖像進(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ù)集是法國(guó)INRIA機(jī)構(gòu)在2008年發(fā)布的。該數(shù)據(jù)集共有500類(lèi)圖像，每類(lèi)圖像有2～6幅不等，共計(jì)1 491幅。數(shù)據(jù)集中圖像的尺寸不一，大部分圖像的分辨率為2 048×1 536，在實(shí)驗(yàn)中統(tǒng)一調(diào)整為1 024×768。Holiday數(shù)據(jù)集中的圖像都是對(duì)同一目標(biāo)或場(chǎng)景進(jìn)行的不同角度的拍攝。INRIA提供了數(shù)據(jù)集每幅圖像的SIFT特征和訓(xùn)練好的字典[13]。字典的維度從100維到200 000維。下面在與“詞袋”模型對(duì)比的實(shí)驗(yàn)中均采用200 000維的字典[14]。按照數(shù)據(jù)集的說(shuō)明，每一類(lèi)的第一幅圖像作為查詢(xún)圖像，在查詢(xún)圖庫(kù)的過(guò)程中要排除自身，在剩余圖像中計(jì)算排名，使用Average Precision（AP）作為衡量系統(tǒng)的指標(biāo)。在500類(lèi)圖像進(jìn)行500次查詢(xún)，然后求其平均值mAP（mean Average Precision），以此作為衡量系統(tǒng)的評(píng)價(jià)指標(biāo)。

3.2 參數(shù)選擇

在實(shí)驗(yàn)中，并不使用每幅圖像的全部SIFT特征，而是選取顯著度最大的t個(gè)作為該圖像的特征。顯著度是由特征點(diǎn)的Hessian矩陣的行列式值和該矩陣的跡共同求得。下面“詞袋”模型縮寫(xiě)為BoF，本文提出方法縮寫(xiě)為L(zhǎng)CVS。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值的增長(zhǎng)放緩，這說(shuō)明當(dāng)描述圖像所需的特征達(dá)到一定數(shù)量之后，過(guò)多的特征引入對(duì)系統(tǒng)起到的作用有限，反而影響特征的魯棒性，出現(xiàn)震蕩或者下降。

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

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

3.3 方法比較與分析

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

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

圖7 部分查詢(xún)結(jié)果對(duì)比

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

圖8 部分查詢(xún)結(jié)果對(duì)比

4 結(jié)論

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

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

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