王瑞霞, 彭國華

(西北工業(yè)大學 理學院, 陜西 西安　710129)

子區(qū)域視覺短語稀疏編碼的圖像檢索

王瑞霞, 彭國華

(西北工業(yè)大學 理學院, 陜西 西安710129)

摘要：針對BOVW模型忽略圖像特征空間排列導致量化誤差較大的缺點，利用角點和特征點對圖像進行區(qū)域分割，結合區(qū)域的空間排列信息，提出一種多通道融合的圖像檢索方法。其主要思想是將子區(qū)域編碼和特征空間排列直方圖結合組建視覺短語，這種構造方式在減少編碼誤差的同時還能更好地保留局部空間信息。首先，利用稀疏編碼保留局部信息的高效性對提取的子區(qū)域進行編碼；其次，利用特征的空間位置關系，計算子區(qū)域內的特征空間排列直方圖；利用區(qū)域編碼和特征排列直方圖構建視覺短語；最后，結合BOVW模型的魯棒性，統(tǒng)計視覺短語直方圖用于圖像檢索。實驗結果表明，該檢索方法不僅比BOVW和SPMBOVM有更好的檢索準確率，而且其編碼過程穩(wěn)定，誤差較小。

關鍵詞：角點； BOVW模型；視覺短語；稀疏編碼；圖像檢索；SPM模型

視覺詞袋模型(bag-of-visual-words,簡寫B(tài)OVW是由詞袋(bag-of-words,簡寫B(tài)OW)模型演變而來，圖像的詞袋思想最初是由Zhu Lei等[1]引入計算機視覺。由于其思想簡單，對圖像的目標位置和形變具有魯棒性，近幾年得到了廣泛關注和應用，尤其在圖像檢索、視頻檢索以及多媒體信息檢索方面已經(jīng)取得許多研究成果，具有重要的實用價值。

2003年J.Sivic和A.Zisserman[2]首次提出了BOVW模型在目標檢索中的應用，并獲得良好的效果。該模型采用局部特征直方圖表示圖像，雖然對特征的空間平移不變具有穩(wěn)定性，但直方圖量化過程損失了圖像的空間位置信息，并且忽略了特征的語義理解，檢索結果只針對個別簡單類有效果。針對該缺點，S.Lazebnik等[3]通過研究局部區(qū)域的空間信息，提出了空間金字塔匹配(spatial pyramid match,簡寫SPM)BOVW模型。它不需要考慮復雜的空間幾何關系卻能有效利用圖像的局部空間信息,節(jié)約了計算成本。但SPM的每個塊(block)仍然采用直方圖量化形式,使得圖像表示的空間信息不足，使得圖像視覺描述和語義理解之間還存在很大差距，對于目標和背景界限不清以及背景稍微復雜的圖片分類結果很差。在上述2個模型的基礎上，Yang Jianchao等[4]使用稀疏編碼(sparse code,簡寫SC)進一步改進了模型中的缺點，它將線性支持向量機(support vector machine，簡寫SVM)應用到SPM,并把量化直方圖轉換成稀疏編碼，不僅利用了圖像的空間信息，而且減少了直方圖的量化誤差，同時線性SVM的應用也節(jié)約了計算成本。但它的缺點是相似的block在編碼過程中會得到完全不同的碼，導致編碼過程不穩(wěn)定，而這一點恰恰是直方圖的優(yōu)點。

因此，本文在稀疏編碼模型基礎上，利用局部空間排列信息，結合稀疏編碼算法保留局部信息的高效性和BOVW模型的魯棒性，提出一種基于稀疏編碼的視覺短語(bag-of-visual-phrases, 簡寫B(tài)OVP)模型。該方法包含2個部分：(1)構建視覺短語：第一，利用角點分割圖像為一系列子區(qū)域，利用特征點提取有效子區(qū)域；第二，利用max pooling函數(shù)對子區(qū)域進行稀疏編碼；第三，統(tǒng)計子區(qū)域的特征空間排列直方圖，構建區(qū)域視覺短語。(2)結合BOVW模型，計算圖像視覺短語量化直方圖。與BOVW模型和SPM-BOVW模型比較，實驗結果表明該檢索方法不僅提高了圖像的檢索效率，而且編碼誤差較小，編碼過程比較穩(wěn)定。

1理論知識

1.1BOVW模型

bag-of-visual-words模型是由用在文本分類中的bag-of-words模型擴展而來的。它把1副圖像看成是由許多block組成，1個block就是1個視覺詞，比如1幅人臉圖像，眼睛、鼻子、嘴、人臉、頭發(fā)分別都看成1個block，其主要思想框架如下：

1) 選擇特征提取方法提取圖像的特征，經(jīng)典的BOVW算法采用的是sift特征提取算法；

2) 對提取的所有特征用k-means聚類，把相近的特征歸為一類，得到k個聚類中心，這k個聚類中心構成視覺詞典；

3) 計算所有特征與視覺詞典中每個視覺詞的相似度，一般采用歐氏距離計算，找出視覺詞典中與特征距離最近的視覺詞；

4) 統(tǒng)計1幅圖像中視覺詞的個數(shù)，得到圖像的直方圖表示(如圖1所示)。

圖1　BOVW模型示意圖

BOVW模型雖然具有很好的魯棒性，但卻完全忽略特征空間位置信息，大大降低了其性能。

1.2SPMBOVW模型

在SPM模型的啟發(fā)下, S.Lazebnik等提出了SPMBOVW模型。該模型是在BOVW基礎上提出的，如果SPM只有1層，與BOVW一致。SPM把圖像劃分成越來越細的空間子區(qū)域，對每個子區(qū)域統(tǒng)計特征直方圖，典型的3層分解為1×1、2×2、4×4的子區(qū)域，該模型對空間金字塔劃分的各層子區(qū)域分別使用BOVW模型的直方圖量化表示(如圖2所示)。然而, 隨著分級層數(shù)的增加，目標在圖像中的位置、形狀越來越敏感，使得最終圖像的表示形式越來越不穩(wěn)定，該方法相對于BOVW模型的優(yōu)勢便蕩然無存，并且由于對子區(qū)域仍采用直方圖量化形式,使得局部空間信息不足，背景稍復雜的圖片處理結果不理想。

圖2　SPM-BOVW模型示意圖

其中,圖2上部從左到右依次表示空間金字塔第1層、第2層和第3層分割結果圖，下部從左到右依次表示相對應的每層空間金字塔的統(tǒng)計直方圖；3層空間金字塔一共構成了21個子區(qū)域，每一層的權重分別為1/4、1/4、1/2。

1.3稀疏編碼公式

稀疏編碼作為一類有效的技術已經(jīng)被成功應用在許多計算機視覺領域，如圖像分類、圖像識別等[5-6]。設X=[X1,X2,…,XN]∈RD×N是1幅圖像的特征，Xi是局部特征描述子，B=[B1,B2,…,BM]∈RD×M為碼本，是由所有圖像局部描述子通過聚類得到的M個聚類中心組成，Bi是碼本中的第i個碼詞。圖像的每個局部描述子Xi通過碼本B進行編碼生成一個M維的稀疏向量。

稀疏編碼公式定義如下：

滿足條件：‖Bi‖≤1,?i=1,2,…,M。

(1)式中的第1項是重構誤差，第2項是用來控制稀疏碼Ci的稀疏性，λ是用來平衡稀疏性和重構誤差的權衡因子。

通常碼本B是過完備的，這個特性保證了重構系數(shù)的稀疏性。但是，碼本的過完備損失了編碼特征的局部信息，使得相似的特征可能被編碼成完全不同的碼，導致編碼過程的不穩(wěn)定性[4]。

1.4Max pooling函數(shù)

式中：Zi表示第i個block所表示的子區(qū)域編碼，Ci1,Ci2,…,Cin表示系數(shù)矩陣C∈RM×N的i1,i2,…,in列，是第i個block中所包含的ni個局部特征描述子的編碼，其中：N=∑ni。

2子區(qū)域視覺短語稀疏編碼的圖像檢索算法

SPMBOVW模型的優(yōu)點是空間金字塔將圖像劃分為一系列按順序排列的block，每個block看成1個整體，以此來融入圖像的局部空間信息。因此，本文利用角點把圖像分割為若干個子區(qū)域，將每個子區(qū)域看成1個block，提取每個子區(qū)域的特征排列信息。

2.1圖像子區(qū)域的分割

2.1.1角點與特征點的對比

當提取1幅圖像的所有特征時會發(fā)現(xiàn)，1幅圖像有很多特征點，但并不是所有的特征都是圖像目標區(qū)域的特征，有很多是屬于背景區(qū)域的特征，如圖3所示。圖3a)中第1幅圖像提取的sift特征大部分都屬于海洋的信息，而這幅圖片的目標卻是海豚；圖3b)中的第1幅圖像提取的角點雖然較少，但海洋特征減少更多，相對而言信噪比提高了。圖3a)和圖3b)中的第2幅圖像，有背景圖像樹枝的干擾，2幅圖像比較，雖然圖3b)中目標和背景的特征都有所減少，但仍能反映出圖像的基本結構和內容。圖3a)和圖3b)中的第3幅圖像對比，該圖像本身雖然不太受背景的影響，但從圖中可以看出檢測的角點在減少特征數(shù)量的同時，還完全可以表示出蓮花的結構，并且特征的減少提高了編碼的速度，說明損失部分特征點是值得的。

圖3　角點與特征點對比圖

2.1.2子區(qū)域的分割

提取角點的位置，以角點位置為中心，R為半徑，形成1個圓形區(qū)域，整幅圖像將被劃分成若干個子區(qū)域，如圖4所示，圖中每個圓圈表示1個子區(qū)域。將這些圓形區(qū)域中不包含特征點的區(qū)域直接去掉，包含特征點的作為有效區(qū)域，每個有效區(qū)域被記為1個block。

圖4　子區(qū)域分割圖

關于半徑R的選取，R太大的話有效區(qū)域太多，利用角點篩選有效區(qū)域就沒有任何意義，反而會增加計算成本；R太小則會使得包含特征點的有效區(qū)域極其少，無法表示出圖片的主要內容。本文根據(jù)實驗結果最終選取半徑R=15。

2.2基于視覺短語的圖像檢索

視覺短語模型(bag-of-visual-phrase，簡寫B(tài)OVP)是近幾年在BOVW的基礎上針對圖像提出來的[8-9]，通常一個視覺詞有多個語義信息，它能在一定程度上緩解BOVW的語義缺陷，對視覺詞的空間共現(xiàn)模式有一定的意義。

2.2.1構建視覺短語

對提取所有圖像的特征用k-means聚類，得到M個聚類中心，這M個聚類中心就是特征編碼所需的碼本。為了減少編碼的誤差，考慮到特征的多層語義信息，采用KNN法進行編碼，計算視覺詞與碼本的距離，找出最近的K個碼詞表示這個視覺詞。根據(jù)文獻[4], 選取K=5。子區(qū)域視覺短語構建流程圖如圖5所示。

圖5　子區(qū)域視覺短語構建流程圖

子區(qū)域視覺短語構建過程：

1) 提取子區(qū)域的特征，對特征進行編碼。計算每個特征和M個碼本的距離，利用KNN法對特征進行編碼。采用max-pooling函數(shù)融合子區(qū)域所有的特征編碼系數(shù)，最終得到該子區(qū)域的稀疏編碼C；

2) 統(tǒng)計子區(qū)域特征空間排列信息直方圖。將子區(qū)域平均分為16個方向，即[0,360]平均分為16等分，根據(jù)過程(1)中1個特征點對應5個碼詞，按順時針統(tǒng)計每個方向視覺詞出現(xiàn)的個數(shù)，以視覺詞出現(xiàn)最多的方向為主方向，并且該統(tǒng)計方式對旋轉魯棒[10]。得到其特征空間排列直方圖，進行量化，得到其量化直方圖H；

3) 構建視覺短語。合并子區(qū)域的稀疏編碼C和特征空間排列直方圖H，構建視覺短語P=[C;H]，由于是2種不同方式的結合，因此需要對其進行歸一化。

2.2.2統(tǒng)計視覺短語直方圖

結合BOVW模型的魯棒性，對提取的所有視覺短語構建視覺短語模型,其步驟如下：

1) 建立視覺短語詞典。用k-means對所有視覺短語聚類，得到K個聚類中心，組成視覺短語詞典，本文設置K=1 000。

2) 統(tǒng)計視覺短語直方圖。根據(jù)視覺短語詞典統(tǒng)計視覺短語頻數(shù)，得到視覺短語直方圖。

3各類算法實驗結果比較

本文使用Caltech101數(shù)據(jù)庫，該數(shù)據(jù)庫包含101類和1個背景類，一共是102類，9 144幅圖片，圖片大小不一。在圖像檢索時，相似度的計算方法通常也會影響檢索結果的準確度，用任何一種方法計算相似度都會有其弊端，因此，本文采用歐氏距離和余弦定理2種方式結合來計算相似度。對于評價準則，計算查全率和查準率得到綜合評價指標F1-measure值。圖6是BOVW模型、SPMBOVW模型以及本文算法的F1-measure指標對比圖，給出了25類查詢圖像的檢索結果。從圖中可以看出本文提出的算法(為方便簡寫為RVPBOVW)雖然在個別類中檢索精度有所下降，但大部分的檢索結果都得到很大的提高。

圖6　各類算法F1-measure指標對比圖

其中：縱坐標是各類算法的F1-measure指標值，橫坐標相對應的25類圖像分別表示：1(airplanes)、2(accordion)、3(brain)、4(car-side)、5(butterfly)、6(dollar bill)、7(faces-easy)、8(grand piano)、9(ketch)、10(mandolin)、11(motorbikes)、12(pigeon)、13(revolver)、14(rooster)、15(schooner)、16(scissors)、17(snoopy)、18(starfish)、19(stop-sign)、20(strawberry)、21(watch)、22(water-lilly)、23(windsor-chair)、24(yin-yang)和25(wrench)。

表1　各類算法平均準確率

表1給出了各類算法檢索的平均準確率，可以看出本文提出的RVPBOVW算法檢索平均準確率提高了24%，而且其誤差也相對減少了一半，說明該方法有效地保留了特征局部空間信息，而且計算方法比較穩(wěn)定。

圖7　本文算法部分檢索結果示例

圖7列出了Caltech101數(shù)據(jù)庫的部分檢索結果，返回的是前30幅檢索結果圖，每一類圖像的第1張圖像為查詢圖像。圖7說明本文方法不僅提高了每類圖像的檢索準確率，而且返回的相似圖像排在前面的結果基本都是正確的結果圖，檢索排序也是檢索效率的另一評判標準。

4結論

視覺短語是根據(jù)圖像本身帶有一定的語義信息而提出的，是對視覺詞的一個擴展。利用稀疏編碼保留局部信息的高效性將稀疏編碼應用到視覺短語的構建中，能更好地描述圖片所要表達的內容，減弱了圖片描述和語義理解之間難以逾越的鴻溝。本文提出的視覺短語稀疏編碼的圖像檢索算法不僅能夠很好保留圖像局部空間信息，而且減弱了編碼誤差引起的檢索的不準確性，同時該方法有很好地魯棒性。但編碼和構建視覺短語的過程都比較花費時間，將兩者結合，增加了時間計算成本，因此，如何更好的將兩者結合，減少后臺計算時間，提高前臺檢索速度，這也是進一步要考慮的問題。

參考文獻：

[1]Zhu Lei, Rao Aibing, Zhang Aidong. Theory of Keyblock-Based Image Retrieval[J]. ACM Trans on Information Systems, 2002, 20(2): 224-257

[2]Sivic J, Zisserman A. Video Google: a Text Retrieval Approach to Object Matching in Videos[C]//Proceedings of the Ninth IEEE International Conference on Computer Vision. Nice, France: IEEE, 2003: 1470-1477

[3]Lazebnik S, Schmid C, Ponce J. Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories[C]//Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition. New York, USA: IEEE, 2006: 2169-2178

[4]Yang Jianchao, Yu Kai, Gong Yihong, Huang Thomas. Linear Spatial Pyramid Matching Using Sparse Coding for Image Classification[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, Miami, Florida, USA: IEEE, 2009: 1794-1801

[5]Zhang Lihe, Ma Chen. Low-Rank Decomposition and Laplacian Group Sparse Coding for Image Classification[J]. Neurocomputing, 2014, 135(7): 339-347

[6]Liu Huaping, Liu Yulong, Sun Fuchun. Traffic Sign Recognition Using Group Sparse Coding[J]. Information Sciences, 2014, 266(5): 75 - 89

[7]Wang Jinjun, Yang Jianchao, Yu Kai, et al. Locality -Constrained Linear Coding for Image Classification[C]//IEEE Conference on Computer Vision and Pattern Recognition, 2010：3360-3367

[8]Zhang Shiliang, Tian Qi, Hua Gang, et al. Generating Descriptive Visual Words and Visual Phrases for Large-Scale Image Applications[J]. IEEE Trans on Image Process, 2011, 20(9): 2664-2677

[9]Chen Tao, Yap Kimhui, Zhang Dajiang. Discriminative Bag-of-Visual Phrase Learning for Landmark Recognition[C]//Proceedings of the 2012 IEEE International Conference on Acoustics, Speech and Signal Processing. Kyoto, Japan, 2012: 893-896

[10] 張琳波,王春恒,肖柏華,邵允學. 基于Bag-of-phrases的圖像表示方法[J]. 自動化學報,2012,38(1):46-54

Zhang Linbo, Wang Chunheng, Xiao Baihua, Shao Yunxue. Image Representation Using Bag-of-Phrases[J]. Acta Automatica Sinica, 2012, 38(1):46-54 (in Chinese)

Image Retrieval of Sub-Region Visual Phrases

with Sparse Coding

Wang Ruixia, Peng Guohua

(Department of Applied Mathemetics, Northwestern Polytechnical University, Xi′an, 710129, China)

Abstract:The BOVW model ignores the image feature spatial arrangement, thus causing quantization error. Considering this shortcoming, we divided an image into a series of sub-regions according to corners and features. Combining spatial arrangement information of the sub-regions, we, using multimodal fusion, proposed a new image retrieval method. The main idea is to construct visual phrases through sub-region encoding and feature spatial arrangement histograms. By this combination, it not only reduces the encoding error but also better preserves the local spatial information. First, using the advantages of sparse coding, we encoded the sub-regions; second, according to the feature spatial location relations, sub-region feature spatial arrangement histograms were calculated; third, visual phrases were composed of sub-region encoding and feature spatial arrangement histograms; at last, incorporating the robustness of BOVW model, we calculated the visual phrase histograms for image retrieval. The results and their analysis show preliminarily that the proposed retrieval method not only has better retrieval accuracy than BOVW and SPMBOVW but also its encoding is more stable and the error is smaller.

Key words:calculations, clustering algorithms, combinatorial optimization, data fusion, errors, flowcharting, functions, image coding, image retrieval, image segmentation, mathematical operators, MATLAB, mean square error, pixels, robust control, schematic diagrams, stability; corner, BOVW(bag-of-visual-words) model, visual phrase, sparse code, spatial pyramid match model

中圖分類號：TP391

文獻標志碼：A

文章編號:1000-2758(2015)05-0721-06

作者簡介：王瑞霞(1984—)，女，西北工業(yè)大學博士研究生，主要從事基于內容的圖像檢索研究。

基金項目：國家自然科學基金(61201323)資助

收稿日期：2015-01-18