基于詞頻統(tǒng)計(jì)特征和 GVP 的大規(guī)模圖像檢索算法研究

劉 宇 鄧 亮 郭耕辰 馮良炳

(中國科學(xué)院深圳先進(jìn)技術(shù)研究院 深圳 518055)

基于詞頻統(tǒng)計(jì)特征和 GVP 的大規(guī)模圖像檢索算法研究

劉 宇 鄧 亮 郭耕辰 馮良炳

(中國科學(xué)院深圳先進(jìn)技術(shù)研究院 深圳 518055)

針對(duì)傳統(tǒng)的 GVP(Geometry-Preserving Visual Phrases)圖像檢索算法計(jì)算量大、時(shí)間復(fù)雜度高且不適合處理大規(guī)模圖像檢索等缺點(diǎn)，文章提出了 FSF-GVP(Frequency Statistics Feature-Geometry-Preserving Visual Phrases)算法，該方法將詞頻統(tǒng)計(jì)特征和 GVP 算法相結(jié)合，使用 GVP 排序算法對(duì)詞頻特征統(tǒng)計(jì)后的相似結(jié)果集進(jìn)行排序，忽略不相似結(jié)果集，極大地提高了檢索效率。實(shí)驗(yàn)結(jié)果表明，F(xiàn)SF-GVP 在保證檢索準(zhǔn)確性的前提下，提高了檢索效率，適用于實(shí)時(shí)大規(guī)模圖像檢索。

圖像檢索；詞袋模型

1 引 言

圖像檢索在工業(yè)領(lǐng)域應(yīng)用潛力巨大，近幾年關(guān)于圖像檢索的研究引起了廣泛關(guān)注。在圖像檢索領(lǐng)域，詞袋模型(Bag of Words，BOW)方法被廣泛使用。BOW 算法借鑒了 Web 文本搜索的Bag of Word 思想，將圖像分成一些視覺單詞用于表達(dá)圖像語義。BOW 首先由 Video Google 提出[2]，由 Li 等[3]改進(jìn) BOW 模型，應(yīng)用于單一物體及多類物體的識(shí)別和分類，并創(chuàng)建了統(tǒng)一圖像測(cè)試集 Caltect 101 和 Caltech 256。詞袋模型[4]基于SIFT(Similar Local Features，SIFT)點(diǎn)的描述基礎(chǔ)上計(jì)算得到視覺詞匯表，能夠較好地描述目標(biāo)的統(tǒng)計(jì)信息，也在文本分類領(lǐng)域取得了很好的結(jié)果。但是該特征是一個(gè)亂序的統(tǒng)計(jì)特征，并不能反映目標(biāo)內(nèi)部之間特征所在位置的相互關(guān)系。實(shí)驗(yàn)證明，詞袋模型在目標(biāo)識(shí)別方面有較好的識(shí)別結(jié)果。為了提高檢索精確度、效率和排序結(jié)果，在詞袋模型思想基礎(chǔ)上，有很多的算法被陸續(xù)提出。Vocabulary Tree 數(shù)據(jù)模型[5]和最相似緊鄰算法被有效地用于建立大型詞典，軟匹配(Soft Matching)[6]和漢明切入(Hamming Embedding)[7]被用來解決詞袋模型的硬量化問題。Query expansion[8]作為后期步驟重排序以期獲得高的召回率。除此還有很多改進(jìn)的方法，如減少倒排表使用內(nèi)存等。但是圖像檢索算法因?yàn)槠溆?jì)算量大、時(shí)間復(fù)雜度高而不適合處理大規(guī)模圖像檢索。其中一個(gè)最主要的限制是忽略了視覺單詞的空間幾何信息。

因?yàn)橐曈X單詞本身有多重歧義性，所以空間幾何信息的引入對(duì)于視覺表達(dá)非常重要?？臻g幾何信息通常在后處理中使用，如隨機(jī)抽樣一致(Random Sample Consensus)[9]或者近鄰特征一致(Neighboring Feature Consistency)[2]。因?yàn)閹缀悟?yàn)證方法通常計(jì)算量非常大，所以他們只被安排在了初始排序的前幾個(gè)圖像。金字塔匹配算法(Spatial Pyramid Matching)[10]雖然在空間上有所改進(jìn)[11]，但是缺乏變換的靈活性?？臻g加權(quán)(Spatial-Bag-of-Features)算法通過改變空間直方圖的順序來解決金字塔匹配算法的可變性問題。對(duì)于每個(gè)視覺單詞來說，空間直方圖按照出現(xiàn)次數(shù)最多的方式被重排序，這種思想推進(jìn)了詞袋模型和金字塔匹配算法的發(fā)展。

GVP(Geometry-Preserving Visual Phrases)[1]是基于計(jì)算視覺單詞同時(shí)出現(xiàn)次數(shù)進(jìn)行得分排序的算法。對(duì)于特定空間的幾何信息，一個(gè) GVP是一組視覺單詞。所以，不同的 words 或者不同的空間布局對(duì)應(yīng)不同的 GVP。GVP 被用來編碼空間幾何信息，也可以編碼更多其他種類的信息。Zhang 等[1]發(fā)現(xiàn)將圖像分為 6×7 的大塊，當(dāng)同一塊中兩個(gè)圖像之間出現(xiàn)相同的 SIFT 特征時(shí)，取相同特征數(shù)的組合。當(dāng)組合數(shù)取 2 時(shí)對(duì)于一般結(jié)果來說最好。Wang 等[12]基于 GVP 算法，提出提高組合數(shù)的取值時(shí)檢索效果更好。但是GVP 的性能一直不夠好，且因?yàn)橛?jì)算量大而不適合處理大規(guī)模圖像檢索。為了準(zhǔn)確、高效地處理大規(guī)模圖像檢索，本文提出 FSF-GVP(Frequency Statistics Feature-Geometry-Preserving Visual Phrases)算法。算法首先統(tǒng)計(jì)數(shù)據(jù)庫中圖像與被搜索圖像的詞頻特性，得到相似結(jié)果集和不相似結(jié)果集，再對(duì)相似結(jié)果集使用 GVP 算法進(jìn)行排序，從而得到最終搜索結(jié)果。

本文首先對(duì) FSF-GVP 進(jìn)行具體描述，然后再將該算法與其他算法在時(shí)間和效率上進(jìn)行對(duì)比分析。

2 FSF-GVP 圖像檢索算法

2.1 算法描述

2004 年，Lowe[13]總結(jié)已有的基于不變量技術(shù)的特征檢測(cè)方法，正式提出了一種基于尺度空間，對(duì)圖像平移、旋轉(zhuǎn)和縮放，甚至仿射變換保持不變性的圖像局部特征，即 SIFT 特征。

詞袋模型基于 SIFT 特征，根據(jù)被搜索圖像，在數(shù)據(jù)庫圖像中尋找同一類圖像并返回圖像序列。這種算法首先在文本處理領(lǐng)域獲取了巨大的成功，它使用概率語義分析模型挖掘文檔集中的主題信息，采用非監(jiān)督學(xué)習(xí)方法，從底層的文本特征中獲得語義。BOW 以其快速、高效性在文本分類問題中獲得了巨大的成功[14-17]。關(guān)于分析文本與圖像分類之間的關(guān)系，可以將兩個(gè)問題進(jìn)行類比分析，理解為一副圖像中包含了很多視覺“單詞”。從文本文檔中可以得出詞語—文檔共生矩陣，類似的，從圖像分析中可以得出圖像的詞語—文檔矩陣。所以可以按照不同的視覺主題對(duì)圖像進(jìn)行分類。圖 1 說明了文本分類與圖像分類關(guān)系。

圖 1 文本分類與圖像分類的關(guān)系Fig. 1. Relationship between text classification and image classification

GVP 算法補(bǔ)充了 BOW 算法，對(duì) BOW 算法返回的圖像序列進(jìn)行排序，得到搜索數(shù)據(jù)庫圖像后的序列。GVP 算法將圖像分為 M＝A×B 的大塊，計(jì)算每塊中所有視覺單詞同時(shí)出現(xiàn)的概率。當(dāng)數(shù)據(jù)庫圖像某塊中相同的某幾個(gè)視覺單詞同時(shí)出現(xiàn)時(shí)，就給數(shù)據(jù)庫圖像相似度總分加相應(yīng)的權(quán)值分?jǐn)?shù)。

GVP 算法描述如下：

(1)初始化數(shù)據(jù)庫中所有圖像每個(gè)塊(每個(gè)圖像共 M 塊)的分?jǐn)?shù)為 0。每個(gè)塊表達(dá)了視覺單詞的空間幾何信息。

(2)對(duì)于被搜索圖像 m 中的每個(gè)視覺單詞 j，通過倒排表檢索包含視覺單詞 j 的所有圖像 id 和視覺單詞 j 出現(xiàn)的次數(shù)。對(duì)在圖像 i 中出現(xiàn)的每個(gè)視覺單詞 j，將它的空間幾何位置與被搜索圖中 j 的空間幾何位置相減得到每塊的分?jǐn)?shù)。

其中(xd, yd)是圖像 i 中的 j 所處的空間幾何位置，(xj, yj)是被搜索圖像 m 中 j 所處的空間幾何位置。Si是圖像 i 的分?jǐn)?shù)。

(3)遍歷每個(gè)圖像 i 的每塊 m，計(jì)算 length 為k 的 GVP 所得分?jǐn)?shù)。對(duì)上一步算得所有圖像的每塊總分，使用組合方法求得每塊的新分?jǐn)?shù)。并將每塊新分?jǐn)?shù)加和得到一張圖像的總分?jǐn)?shù)。

(4)對(duì)所有圖像分?jǐn)?shù)排序得到所需搜索圖像序列。

GVP 算法還有一些重要的部分，如在上述算法中加入詞頻重要性權(quán)值[1]，加入對(duì)最后總分的規(guī)范化[1]，對(duì) length 取值的選擇[12]，對(duì)詞頻權(quán)值的快速選擇[18]等。

依據(jù)相似圖像的特征總是與幾何位置相關(guān)的特性[12]，F(xiàn)SF-GVP 首先統(tǒng)計(jì)數(shù)據(jù)庫中圖像與被搜索圖像視覺單詞空間的詞頻特性得到相似結(jié)果集和不相似結(jié)果集，再對(duì)相似結(jié)果集使用 GVP算法，利用視覺單詞空間幾何布局，對(duì)圖像進(jìn)行排序。

假設(shè)，有 n 張待搜索圖像，對(duì)所有的圖像的所有 SIFT 特征使用 K-means 方法劃分類別，得到 c 個(gè)類。

FSF-GVP 算法步驟如下：

(1)對(duì)要搜索的圖像，首先求出 SIFT 特征，并根據(jù)之前分類的方法將這些 SIFT 分類。取種類中出現(xiàn)次數(shù)多的前 k 個(gè)類別作為索引。設(shè)索引為 j，正在對(duì)比的圖為 i，i 中 j 出現(xiàn)的次數(shù)為occur，則每個(gè)圖的分?jǐn)?shù)為：

(2)按照桶排序方式，將分?jǐn)?shù)高于設(shè)定閾值的圖像放入相似結(jié)果集列表，其他圖像放入不相似結(jié)果集列表。

(3)對(duì)相似結(jié)果集圖像列表的前 m 個(gè)圖像進(jìn)行 GVP 計(jì)算分?jǐn)?shù)，再進(jìn)行排序并得到最終搜索結(jié)果；

過程解釋如下：首先計(jì)算被搜索圖像出現(xiàn)的次數(shù)，取出視覺單詞數(shù)量最多的 k 個(gè)類別作索引，然后對(duì)所有圖像的視覺單詞相同索引的出現(xiàn)次數(shù)進(jìn)行簡單相加，以相加后的和作為總分，使用桶式排序，把高于設(shè)定閾值的圖像放入相似結(jié)果集列表中，低于設(shè)定閾值的圖像放入不相似結(jié)果集列表中。這樣對(duì)候選集進(jìn)行了預(yù)篩選，極大縮小了搜索空間。對(duì)相似結(jié)果集圖像列表取 m 個(gè)圖像并使用 GVP 進(jìn)行排序，得到最終搜索結(jié)果。

2.2 算法性能分析

GVP 算法首先計(jì)算被搜索圖像的 SIFT 特征，然后對(duì)每個(gè)圖像的所有 SIFT 類進(jìn)行掃描，按照索引號(hào)進(jìn)行加分，時(shí)間復(fù)雜度為 O(c·n)。將所有圖像分成 6×7 的格子，計(jì)算格子內(nèi)符合length 的組合數(shù)記入總分，最后對(duì)所有圖像總分進(jìn)行排序得到搜索結(jié)果，時(shí)間復(fù)雜度為O(c·n)+ O(logn)。總的時(shí)間復(fù)雜度為：

FSF-GVP 算法首先計(jì)算被搜索圖像的所有SIFT 特征，并取前 k 個(gè)分類作為索引，然后對(duì)每個(gè)圖像與索引相同的 SIFT 出現(xiàn)次數(shù)進(jìn)行相加得到初始分?jǐn)?shù)，采用類桶式排序?qū)⒎謹(jǐn)?shù)高于閾值的放入列表中，時(shí)間復(fù)雜度為 O(k·c·n)。對(duì)相似結(jié)果集圖像列表，對(duì)他們進(jìn)行 GVP 排序，時(shí)間復(fù)雜度為 O(c·m·n)+O(c·m·n)+O(log(m·n))?？偟臅r(shí)間復(fù)雜度為

3 實(shí) 驗(yàn)

3.1 數(shù)據(jù)集和評(píng)估標(biāo)準(zhǔn)

Oxford 5K 數(shù)據(jù)集[9]已經(jīng)成為一種評(píng)估標(biāo)準(zhǔn)。它包含了 11 種不同的 Oxford 里程碑和其他的擾亂選項(xiàng)，由 Flickr 提供 5062 圖像分辨率。

本文使用主集合的平均準(zhǔn)確率(Mean Average Precision，MAP)[9]來評(píng)估所有實(shí)驗(yàn)的性能。在相同的實(shí)驗(yàn)環(huán)境下，用執(zhí)行時(shí)間來評(píng)估算法速度。并計(jì)算每個(gè)圖像搜索的精確度求平均值來生成平均準(zhǔn)確率的分?jǐn)?shù)。

3.2 實(shí)驗(yàn)參數(shù)與結(jié)果對(duì)比

本文使用 128 維的 SIFT 描述子進(jìn)行描述，使用 K-means 算法對(duì) SIFT 描述子進(jìn)行聚類，共50000 個(gè)類。一般實(shí)驗(yàn)中，k 取 30%～40%，m取 20%～30%。本文 k 取 30%，m 取 20%。

圖 2 描述了 Oxford 5K 數(shù)據(jù)庫上，GVP 算法在不同字典大小、不同深度 length 下的取值結(jié)果。

圖 2 表明，詞典越大，深度 length 的最佳值越高。因?yàn)樯疃?length 越高，要求在小范圍內(nèi)與原被搜索圖相同的特征越多。而當(dāng) length 過大，篩選條件太過嚴(yán)格，搜索平均準(zhǔn)確率下降。所有圖像無論相似與否得分指標(biāo)都很低，無法區(qū)分圖像誰更相似，所以最后曲線都向下，MAP 降低。

圖 2 GVP 在不同詞典、不同 length 下的性能比較Fig. 2. GVP’s performance under different dictionary sizes and different lengths

圖 3 FSF-GVP 與 GVP 在詞典為 20K 與 50K 和 length 不同下的效果比較Fig. 3. Comparison between FSF-GVP and GVP of different dictionary sizes and lengths

圖 3 比較了 GVP 與 FSF-GVP 排序后前 50個(gè)圖像的平均精確度。

圖 3 的實(shí)驗(yàn)結(jié)果與圖 2 比較相似。性能上幾乎無變化。當(dāng) length 相對(duì)較大時(shí)，圖中 FSF-GVP算法的變化比 GVP 相對(duì)遲鈍，即對(duì) length 變化的耐受性更好。這是因?yàn)?FSF-GVP 的排序所用總分包含了兩部分，一部分是數(shù)據(jù)庫圖像與被搜索圖出現(xiàn)相同 SIFT 類別的次數(shù)作為分?jǐn)?shù)，另一部分是 GVP 計(jì)算排序所用的分?jǐn)?shù)。Length 只影響 GVP 計(jì)算排序所用的分?jǐn)?shù)而不影響前一部分的分?jǐn)?shù)，所以 FSF-GVP 對(duì) length 的變化相對(duì)遲鈍，即當(dāng) length 相對(duì)較大時(shí)平均搜索準(zhǔn)確率下降速度較 GVP 更小。

文中 GVP 和 FSF-GVP 圖像排序前 10 名平均精度結(jié)果表明，GVP 算法與 FSF-GVP 算法在圖像排序前 10 名的平均精度上幾乎無差別，其中，GVP 平均準(zhǔn)確率為 0.870，而 FSF-GVP 為0.868。因?yàn)閷?duì)于排名非常靠前的圖像，他們與被搜索圖非常相似。對(duì)于 FSF-GVP 算法而言，越相似的圖像，分?jǐn)?shù)第一部分即相同 SIFT 類別的出現(xiàn)次數(shù)越高，并且第二部分 GVP 的分?jǐn)?shù)也會(huì)越高。所以 FSF-GVP 與 GVP 的前 10 張圖像搜索平均準(zhǔn)確率基本相同。

圖 4 為 GVP 和 FSF-GVP 的搜索結(jié)果。使用圖 4 兩幅圖像各自的第一個(gè)圖像作為被搜索圖像，數(shù)據(jù)庫圖像中包含原圖。實(shí)驗(yàn)中，GVP 與FSF-GVP 都能在將原圖排在第一位，并且前 10的搜索精度無差別。

圖 4 GVP 和 FSF-GVP 的搜索結(jié)果Fig. 4. The search results of GVP and FSF-GVP

4 結(jié) 論

為準(zhǔn)確、高效的處理大規(guī)模圖像檢索，本文在 GVP 算法的基礎(chǔ)上，提出了 FSF-GVP 算法。首先統(tǒng)計(jì)數(shù)據(jù)庫中圖像與被搜索圖像的詞頻特性得到相似結(jié)果集和不相似結(jié)果集，極大縮小了搜索空間，再對(duì)相似結(jié)果集使用 GVP 算法進(jìn)行排序。Oxford 5K 數(shù)據(jù)庫上的實(shí)驗(yàn)表明排序后前10 張圖像的檢索精度與 GVP 算法無差別。FSFGVP 對(duì)于 length 能接受的波動(dòng)范圍比 GVP 要大很多。FSF-GVP 較 GVP 更快速，更適合于大規(guī)模的圖像檢索。

[1] Zhang YM, Jia Z, Chen T. Image retrieval with geometry-preserving visual phrases [C] // IEEE Conference on Computer Vision and Pattern Recognition, 2011: 809-816.

[2] Sivic J, Zisserman A. Video google: a text retrieval approach to object matching in videos [C] // International Conference on Computer Vision, 2003: 1470-1477.

[3] Li FF, Fergus R, Perona P. Learning generative visual models from few training examples: an incremental Bayesian approach tested on 101 object categories [C] // Conference on Computer Vision and Pattern Recognition Workshop, 2004: 178.

[4] He X, Zemel RS. Learning and Incorporating Topdown Cues in Image Segmentation [M]. Springer Berlin Heidelberg, 2006: 338-351.

[5] Nister D, Stewenius H. Scalable recognition with a vocabulary tree [C] // IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2006: 2161-2168.

[6] Philbin J, Chum O, Isard M , et al. Lost in quantization: improving particular object retrieval in large scale image databases [C] // Conference on Computer Vision and Pattern Recognition, 2008: 1-8.

[7] Jegou H, Douze M, Schmid C. Hamming embedding and weak geometric consistency for large scale image search [C] // Proceedings of the 10th European Conference on Computer Vision: Part I, 2008: 304-317.

[8] Chum O, Philbin J, Isard M, et al. Total recall: automatic query expansion with a generative feature model for object retrieval [C] // Proceedings of the IEEE International Conference on Computer Vision, 2007: 1-8.

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

[10] Lazebnik S, Schmid C, Ponce J. Beyond bags of features: spatial pyramid matching for recognizing natural scene categories [C] // IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2006: 2169-2178.

[11] Weiss Y, Torralba A, Reigus R. Spectral hashing [C] // Advances in Neural Information Processing Systems, 2008: 2169-2178.

[12] Wang FY, Zhang SW, Li HP, et al. Image retrieval using multiple orders of Geometry-preserving Visual Phrases [C] // International Conference on Image Analysis and Signal Processing, 2012: 1-5.

[13] Lowe DG. Distinctive image features from scaleinvariant keypoints [J]. International Journal of Computer Vision, 2004. 60(2): 91-110.

[14] Grosky WI, Zhao R. Negotiating the semantic gap: from feature maps to semantic landscapes [C] // Theory and Practice of Informatics Lecture Notes in Computer Science, 2001: 33-52.

[15] Hare JS, Sinclair PAS, Lewis PH, et al. Bridging the semantic gap in multimedia information retrieval: top-down and bottom-up approaches [C] // Mastering the Gap: from Information Extraction to Semantic Representation, European Semantic Web Conference, 2006: 6894624.

[16] Zhang YJ. Visual Informsfen Retrieval Based on Content [M]. Science Press, 2003.

[17] Zhao R, Grosky WI. Narrowing the semantic gap-improved text-based web document retrieval using visual features [J]. IEEE Transactions on Multimedia, 2002, 4(2): 189-200.

[18] Wang FY, Zhang SW. Image retrieval using accurate approximatedinverse document frequency of geometry-preserving visual phrases [C] // International Conference on Audio, Language and Image Processing, 2012: 914-918.

Image Retrieval Using Feature Word Frequency Statistics of Geometry-Preserving Visual Phrases

LIU Yu DENG Liang GUO Gengchen FENG Liangbing
( Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen 518055, China )

Traditional GVP (geometry-preserving visual phrases) image retrieval algorithm is not suitable for handling the large-scale image retrieval because of its high time complexity. In this paper, FSF-GVP (frequency statistics featuregeometry-preserving visual phrases) algorithm, which combined word frequency statistic characteristics and GVP algorithm, was proposed. FSF-GVP algorithm counts visual word frequency characteristics of an image to be searched and image database to get similar result set and dissimilar result set. Then FSF-GVP algorithm uses the GVP algorithm to sort the similar result set, which improves the retrieval efficiency. The experiment results on Oxford 5K dataset show that FSFGVP is suitable for the large-scale real-time image retrieval on the premise of ensuring the accuracy of retrieving result and improving the retrieval efficiency.

geometry-preserving visual phrases; bag of words

TP 751

A

2013-12-29

國家自然科學(xué)基金項(xiàng)目(61070147)，深圳市科技研發(fā)資金基礎(chǔ)研究計(jì)劃(JC201105190951A)。

劉宇，碩士研究生，研究方向?yàn)閳D像檢索和軟件架構(gòu)；鄧亮，碩士研究生，研究方向?yàn)槟Ｊ阶R(shí)別和圖像處理；郭耕辰，碩士研究生，研究方向?yàn)檐浖軜?gòu)；馮良炳(通訊作者)，博士，研究方向?yàn)橹悄苡?jì)算與智能控制、多視角三維重建、網(wǎng)絡(luò)服務(wù)組合和增強(qiáng)現(xiàn)實(shí)，E-mail：lb.feng@siat.ac.cn。