基于詞典優(yōu)化與空間一致性度量的目標檢索

趙永威　周　苑　李弼程

1(武警工程大學電子技術(shù)系　西安　710000)2(河南工程學院計算機學院　鄭州　451191)3(解放軍信息工程大學信息系統(tǒng)工程學院　鄭州　450002)(zhaoyongwei369@163.com)

基于詞典優(yōu)化與空間一致性度量的目標檢索

趙永威1周苑2李弼程3

1(武警工程大學電子技術(shù)系西安710000)2(河南工程學院計算機學院鄭州451191)3(解放軍信息工程大學信息系統(tǒng)工程學院鄭州450002)(zhaoyongwei369@163.com)

摘要基于視覺詞典模型(bag of visual words model, BoVWM)的目標檢索存在時間效率低、詞典區(qū)分性不強的問題，以及由于空間信息的缺失及量化誤差等導致的視覺語義分辨力不強的問題.針對這些問題，提出了基于詞典優(yōu)化與空間一致性度量的目標檢索方法.首先，該方法引入E2LSH(exact Euclidean locality sensitive hashing)過濾圖像中的噪聲和相似關(guān)鍵點，提高詞典生成效率和質(zhì)量；然后，引入卡方模型(chi-square model, CSM)移除詞典中的視覺停用詞增強視覺詞典的區(qū)分性；最后，采用空間一致性度量準則進行目標檢索并對初始結(jié)果進行K-近鄰(K-nearest neighbors, K-NN)重排序.實驗結(jié)果表明：新方法在一定程度上改善了視覺詞典的質(zhì)量，增強了視覺語義分辨能力，進而有效地提高目標檢索性能.

關(guān)鍵詞目標檢索；視覺詞典模型；精確歐氏位置敏感哈希；空間一致性度量；卡方模型

近年來，隨著圖像數(shù)據(jù)規(guī)模的增大，使得圖像處理面臨的環(huán)境更加復雜.雖然SIFT等[1]局部特征在圖像處理領(lǐng)域表現(xiàn)出了良好的性能，但是，其特征維數(shù)較高，若采用VA-File，K-d樹等一些傳統(tǒng)的索引結(jié)構(gòu)進行檢索就會導致“維數(shù)災難”現(xiàn)象.視覺詞典模型(bag of visual words model, BoVWM)[2-3]由于其突出性能，已成為當前圖像標注[4]、圖像檢索與分類[5-8]等領(lǐng)域的主要解決方法.但是，以下3個關(guān)鍵性問題的存在極大地限制了BoVWM模型的性能：1)關(guān)鍵點檢測算子會產(chǎn)生大量的噪聲點無疑會增加計算消耗、降低詞典生成效率；2)當前聚類算法的局限性[9-10]和圖像背景噪聲的存在，使得聚類生成的詞典中包含一些類似于文本信息中的“的”、“和”、“是”等“停用詞”，這里稱其為“視覺停用詞”，嚴重影響了視覺詞典的質(zhì)量；3)傳統(tǒng)的BoVWM模型中視覺單詞間空間信息的缺失和量化誤差嚴重等導致視覺語義表達分辨力不強.

近年來，研究人員針對這些問題做了許多探索性研究，如在過濾噪聲關(guān)鍵點方面：Rudinac等人[11]將相互距離小于1個像素值的特征點看作相似的近鄰點，然后計算其中心值作為代表性特征點，這種方法最大的缺點是計算開銷大，因為它需要遍歷圖像的每個像素點.Jamshy等人[12]通過學習特征點對某一特定應用的先驗知識來過濾大部分特征點，然而這種方法卻降低了圖像分類性能.而針對“視覺停用詞”去除問題，Sivic等人[2]考慮到單詞的信息量大小與其出現(xiàn)的頻率有一定的關(guān)系，從而提出了一種基于詞頻的“停用詞”過濾方法，然而，這種方法卻忽略了視覺單詞和目標語義概念間的相互關(guān)系.Tirilly等人[13]則根據(jù)關(guān)鍵點的幾何性和概率隱語義分析模型淘汰無用的視覺單詞，Yuan等人[14]試圖以統(tǒng)計視覺單詞組合也即“停用詞組”出現(xiàn)的概率來濾除一些無用信息，但是卻忽略視覺詞組內(nèi)部各單詞之間的空間關(guān)系.

針對視覺單詞間空間信息的缺失和量化誤差嚴重的問題，劉碩研等人[15]采用一種基于上下文語義信息的圖像塊視覺單詞生成算法，利用PLSA模型和Markov隨機場共同挖掘單詞的上下文信息.張瑞杰等人[16]考慮到圖像多尺度空間與單詞上下文語義共生關(guān)系，在不同的圖像尺度空間挖掘單詞的上下文語義信息，進一步彌補了傳統(tǒng)BoVWM模型的空間信息不足問題.Chen等人[10]則提出了一種基于軟分配的視覺詞組(visual phrase)構(gòu)建方法，在彌補視覺單詞空間信息的同時，有效克服了傳統(tǒng)視覺詞組構(gòu)建方法[17]導致的特征信息丟失問題.而為了減小量化誤差，Gemert等人[18]提出了視覺單詞不確定性(visual word uncertainty)模型，該模型同樣是采用軟分配策略對SIFT特征編碼，進一步驗證了軟分配方法對于減弱視覺單詞同義性和歧義性影響的有效性.Otávio等人[19]則提出一種基于視覺單詞空間分布的圖像檢索和分類方法，該方法將視覺單詞的空間信息嵌入到向量空間中，并對單詞在圖像中的相對位置關(guān)系進行編碼，從而得到更為緊致的視覺表達方式.Yang等人[20]則利用視覺語言模型結(jié)合目標區(qū)域周圍的視覺單元構(gòu)建了包含上下文語義信息的目標語言模型，進一步改善了目標檢索性能.此外，文獻[21]在利用上下文近義詞構(gòu)建視覺詞匯直方圖的同時，結(jié)合查詢擴展方法解決目標視角變化較大、目標遮擋嚴重的情況問題.但是，查詢擴展方法都依賴于較高的初始查全率，在初始查全率較低時反而會帶來一些負面影響.

針對上述問題，本文提出一種基于視覺詞典優(yōu)化與空間一致性度量的目標檢索方法.1)引入精確歐氏位置敏感哈希算法[22](exact Euclidean locality sensitive hashing, E2LSH)，利用該算法的位置敏感性和處理高維數(shù)據(jù)的高效性對圖像初始關(guān)鍵點進行過濾，降低噪聲點的影響，降低計算消耗；2)根據(jù)引入卡方模型(chi-square model, CSM)分析視覺單詞與目標類別的相關(guān)性大小并結(jié)合單詞詞頻濾除一定數(shù)量的視覺停用詞，增強視覺詞典的區(qū)分性;3)采用一種包含特征點角度、方向等空間一致性信息的度量方法完成目標檢索，并引入K-近鄰重排序方法，進一步改善目標檢索在復雜環(huán)境下的性能.

1視覺詞典優(yōu)化

1.1關(guān)鍵點過濾

假設(shè)在視覺位置相近的關(guān)鍵點是相似的，將其捆綁在一塊計算其質(zhì)心，并將其作為一個有代表性的關(guān)鍵點.每個關(guān)鍵點pi={ui,si,θi,ri}由4部分組成，分別為：特征點在圖像中的位置坐標ui、特征的尺度si、主方向θi及128維SIFT描述向量ri.為了提高過濾效果，本文選取k(k=6)個位置敏感函數(shù)聯(lián)合起來以拉大關(guān)鍵點碰撞概率之間的差距，定義函數(shù)族：

(1)

其中，g(p)=(h1(p),h2(p),…,hk(p))，可知，經(jīng)函數(shù)g(p)∈G降維映射后，關(guān)鍵點p都會變?yōu)橐粋€k維向量a=(a1,a2,…,ak)，然后，再采用主次Hash函數(shù)h1，h2對向量a進行Hash，構(gòu)建Hash表并存儲關(guān)鍵點.主次Hash函數(shù)的定義如下：

(2)

(3)

Fig. 1　The sketch map of different methods for eliminating key points.圖1　不同方法對關(guān)鍵點過濾的示意圖

Fig. 2　The map of E2LSH to eliminate the key points.圖2　E2LSH對all_souls81圖片關(guān)鍵點過濾效果圖

由文獻[8]的研究表明，X-means算法是當前關(guān)鍵點過濾方法中較為有效的主流過濾方法，為此，本文分別采用E2LSH和X-means算法對隨機產(chǎn)生的數(shù)據(jù)點進行過濾以驗證E2LSH算法的有效性.如圖1所示.從圖1不難看出，X-means方法過濾得到的代表性關(guān)鍵點較為不均，而由E2LSH過濾得到的代表性關(guān)鍵點更為均勻.因此，基于E2LSH的過濾方法在一定程度上能夠避免關(guān)鍵點密集區(qū)域描述同一語義概念的關(guān)鍵點被分別捆綁到多個類別的現(xiàn)象，同時也能避免關(guān)鍵點稀疏區(qū)域描述不同語義概念的關(guān)鍵點被錯誤地捆綁到一個類別的現(xiàn)象，進而，提高過濾后各關(guān)鍵點的代表性和區(qū)分能力.圖2進一步給出了E2LSH對Oxford5K數(shù)據(jù)庫中all_souls81圖片關(guān)鍵點過濾的效果圖，其中，圓圈代表初始關(guān)鍵點，星形點則表示經(jīng)E2LSH過濾后的關(guān)鍵點.由圖2不難看出，E2LSH算法能有效地對關(guān)鍵點進行過濾，提高關(guān)鍵點的代表性.

1.2“視覺停用詞”去除

卡方模型是一種醫(yī)學上常用的測量2個隨機變量相關(guān)性的方法，受此啟發(fā)，可以采用卡方模型統(tǒng)計視覺單詞與各目標圖像類別之間的相關(guān)性，卡方值越小表示該視覺單詞與各圖像類別的相關(guān)性越小，區(qū)分性也就弱，反之亦然.因此，可以結(jié)合單詞詞頻以更好地濾除“視覺停用詞”.假設(shè)視覺單詞w的出現(xiàn)頻次獨立于目標類別Cj，Cj∈C，1≤j≤k，圖像集C={C1,C2,…,Ck}，而視覺單詞w與圖像集C中目標類別的相互關(guān)系可以由表1來描述.

表1中，n1j表示目標類別Cj包含單詞w的圖像數(shù)目，n2j表示目標類別Cj不包含單詞w的圖像數(shù)目，n+j則表示目標類別Cj中的圖像總數(shù)，并用ni+，i=1,2分別表示圖像集C中包含單詞w的圖像總數(shù)和不包含w的圖像總數(shù).如此，表1中視覺單詞w與各圖像類別的卡方值可計算如下：

Table 1The Relationship Between Visual Word and Object Categories

表1　視覺單詞與各目標類別關(guān)系

(4)

卡方值x2就代表了w與各目標類別間統(tǒng)計相關(guān)性的大小，同時考慮到單詞w詞頻的影響，對卡方值賦予權(quán)重如下：

(5)

其中，tf(w)表示單詞w詞頻.由此，就能夠按照式(5)對每個單詞的卡方值進行排序，然后去除一定數(shù)量S的“視覺停用詞”即可.

Fig. 3　The illustration of spatially-constrained similarity measurement.圖3　空間一致性度量示意圖

2相似性度量準則

2.1空間一致性度量方法

這里，用Q表示查詢圖像，D表示圖像庫中任一幅圖像，其SIFT特征點分別表示為{f1,f2,…,fm}，{g1,g2,…,gn}，那么，2幅圖像之間的空間一致性度量可計算如下：

S(Q,D|T)=

(6)

(7)

故而，就有S*(Q,D)=S(Q,D|T*)可以用來衡量圖像Q和圖像D之間的相似性，且所有的檢索結(jié)果也能以此進行排序.由圖3上面2幅圖不難看出，2幅圖像中只有特征點(fi,gi),i=1,2,3是滿足空間一致性條件的.(f5,g5)是一個錯誤匹配點對，(f4,g4)的取舍則決定于式(6)中參數(shù)ε的大小.

為了計算S*(Q,D)，需要找到最優(yōu)變換T*，這里可將對T進行分解處理，首先將360角度空間劃分nR部分，(一般nR=4或8)，同樣地，尺度空間被劃分為nS部分，通常nS=8，變化范圍為12到2之間.令V(f)表示特征點與查詢圖像中的矩形框中心cQ之間的相對位置關(guān)系向量，那么由匹配的特征點對(f,g)的位置及V(f)就能定位圖像D中的矩形框中心，L(cQ)=L(g)-V(f)，如果w(f)=w(g)=wk，特征點對(f,g)的投票得分為

(8)

Fig. 4　The retrieval result examples of vote map and object location map.圖4　檢索結(jié)果的投票得分圖和目標定位示意圖

不難看出，若相互匹配的特征點對符合空間一致性條件，那么尤其投票得出的矩形框中心位置也是相近的，如圖3所示.每次投票得出的目標位置中心就代表了一個變換T，那么利用式(8)投票所得分數(shù)就等同于利用式(6)進行相似性度量.可以看出，這種機制可以同時進行目標檢索和定位而不需要子圖檢索和后處理，極大地提高了目標檢索系統(tǒng)的實用性和方便性.在實際應用中，可將投票得分圖歸一化為nx×ny個圖像塊大小，同時為了避免投票時的量化誤差及弱化目標遮擋等情況的影響，本文對所估計的中心塊周圍的16×16像素的窗口塊進行投票，而每個塊的得分大小為Score(wk)×e-dσ2，e-dσ2為權(quán)重系數(shù)，由每個塊與中心塊之間的距離d和σ參數(shù)決定，整個過程相當于對投票得分圖進行一次高斯平滑.

圖4給出了對中心塊周圍的像素的窗口塊進行高斯平滑以及對應的目標定位的示例圖，從圖4可以看出，給出一幅查詢圖像就能按照上述方法得到相應檢索圖像的投票得分圖，然后依據(jù)此對目標進行定位，而每個投票得分圖都存在一個極值點，也即是大部分匹配特征點對都將票數(shù)投向的位置.

2.2K-近鄰重排序

根據(jù)上述相似性度量方法對數(shù)據(jù)庫進行檢索，那么結(jié)果可依據(jù)S*(Q,D)值的大小進行排序，記為R(Q,D)，并令Ni表示查詢圖像的第i個檢索結(jié)果，則有R(Q,Ni)=i，用Nq={Ni},i=1,2,…,k表示查詢圖像的K-近鄰.為了有效地利用K-近鄰圖像包含的信息，本文重新利用其中的每一幅圖像作為查詢圖像重新檢索，并分別將排序結(jié)果記為R(Ni,D)，依據(jù)這個排序結(jié)果給圖像庫中的每幅圖像分配一個得分1R(Ni,D)，那么經(jīng)重排序之后的圖像得分可定義為

(9)

(10)

(11)

然后，所有圖像即可按照式(11)進行重排序，完成檢索.

3實驗設(shè)置與性能分析

3.1實驗設(shè)置

本文選取Oxford5K數(shù)據(jù)庫[23]作為實驗數(shù)據(jù)庫，并從每個目標類別中選取50幅圖像，共550幅圖像作為訓練圖像庫來生成視覺詞典，詞典規(guī)模為10 000.此外，引入Flickr1數(shù)據(jù)庫[24]作為干擾數(shù)據(jù)以驗證本文方法在復雜環(huán)境下的實驗性能.實驗硬件配置為Core 2.6 GHz×4、內(nèi)存4 GB的臺式機，軟件環(huán)境為MATLAB2012a,性能評價指標采用查準率均值(average precision,AP)和平均查準率均值(mean average precision,MAP)以及時間效率，相關(guān)定義如下：

(12)

(13)

3.2實驗性能分析

首先，為了選取合適的Hash函數(shù)個數(shù)值，實驗從550幅訓練圖像庫中提取約1 436 634個特征點，然后利用E2LSH對其過濾，并采用AKM聚類算法對未過濾關(guān)鍵點和不同k值過濾后的特征點進行聚類，生成相同單詞數(shù)目的詞典進行目標檢索分析了參數(shù)k對目標檢索結(jié)果MAP值的影響(此時，令σ2=0)，如圖5所示.從圖5不難看出，隨著參數(shù)k值的變化，目標檢索的MAP值也隨之變化，且在k>3時，經(jīng)E2LSH過濾后的檢索MAP值要高于未過濾的目標檢索.當k=6時，目標檢索MAP值最大，這是因為，當k值較小時會使得過濾后的關(guān)鍵點數(shù)目過少，從而容易丟失圖像包含的細節(jié)信息，而當k值較大時導致過濾后的特征點數(shù)目過多，使得算法過濾效果不明顯，綜合考慮，本文取k=6時剩余代表性關(guān)鍵點數(shù)目為1 002 105個，過濾率為31.3%.然后，實驗又將本文方法與傳統(tǒng)的AKM算法在生成視覺詞典時的時間消耗作了對比，具體如圖6所示.從圖6可以看出，本文方法在經(jīng)E2LSH算法的過濾以后，視覺詞典的生成效率有較為明顯的提升.

Fig. 5　The influence of parameter k on MAP.圖5　參數(shù)k對目標檢索MAP值的影響

Fig. 6　The efficiency comparison of different methods.圖6　不同方法構(gòu)建詞典效率對比

隨后，為了驗證卡方模型對濾除“視覺停用詞”的有效性，實驗在E2LSH函數(shù)個數(shù)k=6的情況下對關(guān)鍵點進行過濾，并生成規(guī)模為10 000的視覺詞典，然后利用卡方模型濾除一定數(shù)量S的視覺停用詞，驗證過濾不同數(shù)目“視覺停用詞”對目標檢索結(jié)果的影響，并與未進行視覺停用詞濾除時的目標檢索結(jié)果進行對比，得其檢索MAP值如圖7所示.從圖7不難看出，采用卡方模型濾除一定數(shù)目的“視覺停用詞”能夠在一定程度上提高目標檢索的MAP值，并且在濾除數(shù)目S=1 000時能夠達到最高的MAP值，即為76.4%.同時，從圖7可以看出,當濾除的單詞數(shù)目過多時，會導致目標檢索性能降低，這是因為濾除過多難免使一些代表性強的單詞也被錯誤地濾除.

Fig. 7　The influence of the number of eliminated visual stop words on MAP.圖7　去除停用詞數(shù)目對目標檢索MAP值的影響

然后，在E2LSH函數(shù)個數(shù)k=6、去除視覺停用詞數(shù)目S=1 000的情況下，實驗以O(shè)xford5K為實驗數(shù)據(jù)庫分析了空間一致性度量準則中參數(shù)σ2對目標檢索MAP值的影響，結(jié)果如圖8所示.其中，當σ2=0時表示不對投票結(jié)果進行高斯平滑，也即是每個匹配特征對都將票數(shù)投向根據(jù)式(8)所估計的一個中心塊，由圖8不難看出，當σ2>0時，也即表示對所估計的中心塊周圍16×16窗口塊進行投票的MAP值明顯優(yōu)于未對投票結(jié)果進行高斯平滑的情況(即σ2=0)，且在σ2=2.5時取得最大的MAP值，因此，本文取σ2=2.5.

Fig. 8　The influence of parameter σ2 on MAP.圖8　參數(shù)σ2對MAP值的影響

其次，由于基于上下文語言模型的目標檢索方法[20](AKM+language model, AKM+LM)能夠很好地記錄視覺單詞間的空間關(guān)系，是當前彌補空間信息不足方面具有代表性的方法，而基于上下文近義詞和查詢擴展目標檢索方法[21](contextual syn-onymous visual words+query expansion, CSVW+QE)在映射視覺詞匯直方圖時，很好地利用了視覺單詞的上下文近義詞，也是當前較為經(jīng)典的利用單詞空間信息的方法，且該方法又引入了查詢擴展策略進一步改善檢索結(jié)果.因此，為了驗證本文方法中空間一致性度量準則以及重排序方法對改善目標檢索結(jié)果的有效性，實驗將本文方法(enhanced visual dictionary and spatially-constrained similarity measure, EVD+SCSM)與AKM+LM方法、CSVW+QE方法以及將優(yōu)化的視覺詞典與語言模型相結(jié)合的方法(enhanced visual dictionary+language model, EVD+LM)在Oxford5K數(shù)據(jù)庫上對11個查詢目標的檢索準確度作了比較，得平均查準率均值MAP如表2所示：

Table 2　The Comparison of Object Retrieval MAP Values of Different Methods

從表2可知，對不同的查詢目標而言，采用AKM+LM方法的MAP值均低于其他3種方法；而EVD+LM方法的MAP值相較于AKM+LM方法有一定的改善，足以說明本文提出的詞典優(yōu)化方法能有效降低圖像背景噪聲點和停用詞的影響，提高視覺詞典的區(qū)分性；同時CSVW+QE方法的性能要略好于EVD+LM方法，這是因為CSVW+QE方法在利用空間信息的基礎(chǔ)上又結(jié)合查詢擴展策略，得到了更多與查詢目標相關(guān)的圖像.但是，本文方法的檢索MAP值要遠高于上述3類方法，與EVD+LM方法對比可以看出，本文中的空間一致性度量準則對單詞空間信息的利用優(yōu)于視覺語言模型.由此也說明改善視覺詞典質(zhì)量能提高視覺詞典對圖像內(nèi)容的語義表達能力，而更加準確的度量方法則能更加精確地對圖像內(nèi)容的表達形式進行度量，二者都能在一定程度上提高目標檢索精度.與CSVW+QE方法相比，可知本文方法在詞典優(yōu)化的基礎(chǔ)上，結(jié)合空間一致性度量準則和重排序，使得本文方法綜合性能優(yōu)于CSVW+QE方法.

Fig. 9　The AP of different methods on Oxford5K.圖9　在Oxford5K數(shù)據(jù)庫上的目標檢索AP值

Fig. 10　The AP of different methods on Oxford5K+Flickr1.圖10　在Oxford5K+Flickr1數(shù)據(jù)庫上的目標檢索AP值

然后，又引入Flickr1數(shù)據(jù)庫作為干擾數(shù)據(jù)驗證本文方法在復雜數(shù)據(jù)環(huán)境下的性能.實驗結(jié)果如圖9和圖10所示.對比圖9和圖10可知，采用本文方法(EVD+SCSM)進行檢索較之其他3種方法有更好的表現(xiàn)，且在加入干擾項數(shù)據(jù)庫之后，AKM+LM方法、EVD+LM方法因沒有對查詢目標的信息進行有效擴展，因此其檢索性能都有明顯的下降.CSVW+QE方法及本文方法卻下降不明顯；但是，當加入大規(guī)模干擾數(shù)據(jù)之后，由于CSVW+QE方法中的查詢擴展策略依賴于較高的初始查全率，所以對于初始查全率較低的Cornmarket，Magdalen等目標而言，其檢索AP值反而低于AKM+LM方法和EVD+LM方法.而本文方法采用的K-近鄰重排序方法是在空間一致性度量準則下進行的，能夠自動地舍棄那些不滿足空間一致性條件的特征點信息，所以其檢索AP值不受初始查全率影響，由此說明本文方法在大規(guī)模干擾數(shù)據(jù)情況下仍能取得較好的檢索結(jié)果，實用性更強.

Fig. 11　Example of K-NN re-ranking result.圖11　K-近鄰重排序結(jié)果示意圖

最后，圖11給出了K-近鄰重排序方法的效果示例圖.從圖11可以看出，第1行圖像中的第5幅最近鄰圖像與查詢目標圖像無關(guān)，但是由其檢索得到的虛線框中的任何一幅圖像的最終檢索得分不會改變，因為它們與其他的最近鄰圖像不相關(guān).而用實線框框標識的圖像會得到較高的檢索得分，因為它們與K-近鄰中的多數(shù)圖像相關(guān).不難看出，采用K-近鄰重排序方法之后可以得到更多包含查詢目標的圖像.

4結(jié)語

為了改善生成視覺詞典的質(zhì)量、提高視覺單詞對圖像內(nèi)容的表達能力，本文首先利用E2LSH算法對圖像初始關(guān)鍵點進行過濾，降低噪聲點的影響；然后，引入卡方模型統(tǒng)計各視覺單詞與目標類別的相關(guān)性，并結(jié)合單詞詞頻信息移除詞典中的視覺停用詞；最后，為了確保度量的準確性，采用空間一致性度量準則進行相似性度量以彌補傳統(tǒng)視覺詞典模型中單詞空間關(guān)系缺失降低量化誤差并對初始檢索結(jié)果進行K-近鄰重排序.實驗結(jié)果有效地驗證了本文方法的有效性.

需要注意的是，在今后需要研究如何降低E2LSH算法的隨機性問題來提高過濾效果的魯棒性.此外，如何通過距離度量的學習使得特征空間的距離更加接近真實的語義距離也是今后亟待解決的問題.

參考文獻

[1]Lowe D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110

[2]Sivic J, Zisserman A. Video Google: A text retrieval approach to object matching in videos[C]Proc of the 9th IEEE Int Conf on Computer Vision. Piscataway, NJ: IEEE, 2003: 1470-1477

[3]Jégou H, Douze M, Schmid C. Improving bag-of-features for large scale image search[J]. Computer Vision, 2010, 87(3): 316-336

[4]Ji Chuanjun, Liu Zuotao, Chan Wen, et al. Context modeling based automatic image annotation system[J]. Journal of Computer Research and Development, 2011, 48(1): 441-445 (in Chinese)(紀傳俊, 劉作濤, 產(chǎn)文, 等. 一個基于語義上下文建模的圖像自動標注系統(tǒng)[J]. 計算機研究與發(fā)展, 2011, 48(1): 441-445)

[5]Chen Y Z, Dick A, Li X, et al. Spatially aware feature selection and weighting for object retrieval[J]. Image and Vision Computing, 2013, 31(12): 935-948

[6]Wang J Y, Bensmail H, Gao X. Joint learning and weighting of visual vocabulary for bag-of-feature based tissue classification[J]. Pattern Recognition, 2013, 46(12): 3249-3255

[7]Cao Y, Chang H W, Zhiwei L, et al. Spatial-bag-of-features[C]Proc of the 23rd IEEE Conf on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2010: 3352-3359

[8]Zhu Jun, Zhao Jieyu, Dong Zhenyu. Image classification using hierarchical feature learing method combined with image silency[J]. Journal of Computer Research and Development, 2014, 51(9): 1919-1928 (in Chinese)(祝軍, 趙杰煜, 董振宇. 融合顯著信息的層次特征學習圖像分類[J]. 計算機研究與發(fā)展, 2014, 51(9): 1919-1928)

[9]Li Dai, Sun Xiaoyan, Wu Feng, et al. Large scale image retrieval with visual groups[C]Proc of the 20th IEEE Conf on Image Processing. Piscataway, NJ: IEEE, 2013: 2582-2586

[10]Chen Tao, Yap K H, Zhang Dajiang. Discriminative soft bag-of-visual phrase for mobile landmark recognition[J]. IEEE Trans on Multimedia, 2014, 16(3): 612-622

[11]Rudinac M, Lenseigne B, Jonker P. Keypoint extraction and selection for object recognition[C]Proc of the 8th IEEE Conf on Machine Vision Applications. Piscataway, NJ: IEEE, 2009: 191-194

[12]Jamshy S, Krupka E, Yeshurun Y. Reducing keypoint database size[C]Proc of the 15th Int Conf on Image Analysis and Processing. Berlin: Springer, 2009: 113-122

[13]Tirilly P, Claveau V, Gros P. Language modeling for bag of visual words image categorization[C]Proc of the 2008 Int Conf on Content-based Image and Video Retrieval. New York: ACM, 2008: 249-258

[14]Yuan J, Wu Y, Yang M. Discovery of collocation patterns: From visual words to visual phrases[C]Proc of the 20th IEEE Conf on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2007: 1-8

[15]Liu Shuoyan, Xu De, Feng Songhe, et al. A novel visual words definition algorithm of image patch based on contextual semantic information[J]. Acta Electronica Sinica, 2010, 38(5): 1156-1161 (in Chinese)(劉碩研，須德，馮松鶴, 等. 一種基于上下文語義信息的圖像視覺單詞生成算法[J]. 電子學報, 2010, 38(5): 1156-1161)

[16]Zhang Ruijie, Li Bicheng, Wei Fushan. Image scene classification based on multi-scale and contextual semantic information[J]. Acta Electronica Sinica, 2014, 42(4): 646-652 (in Chinese)(張瑞杰, 李弼程, 魏福山. 基于多尺度上下文語義信息的圖像場景分類算法[J]. 電子學報, 2014, 42(4): 646-652)

[17]Yeh J B, Wu C H. Extraction of robust visual phrases using graph mining for image retrieval[C]Proc of 2010 IEEE Int Conf on Multimedia and Expo (ICME 2010). Piscataway, NJ: IEEE, 2010: 3681-3684

[18]Van Gemert J C, Veenman C J, Smeulders A W M, et al. Visual word ambiguity[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2010, 7(32): 1271-1283

[19]Otávio A B P, Fernanda B S, Eduardo V, et al. Visual word spatial arrangement for image retrieval and classification[J]. Pattern Recognition, 2014, 47(1): 705-720

[20]Yang Linjun, Geng Bo, Cai Yang, et al. Object retrieval using visual query context[J]. IEEE Trans on Multimedia, 2012, 13(6): 1295-1307

[21]Xie Hongtao, Zhang Yongdong, Tan Jianlong, et al. Contextual query expansion for image retrieval[J]. IEEE Trans on Multimedia, 2014, 56(99): 1-32

[22]Slaney M, Casey M. Locality-sensitive hashing for finding nearest neighbors[J]. IEEE Signal Processing Magazine, 2008, 8(3): 128-131

[23]Robotics Research Group. Oxford5K dataset[DBOL]. [2014-03-26]. http:www.robots.ox.ac.uk_vggdataoxbuildings

[24]Yahoo Company. Flickr1 dataset[DBOL]. [2014-03-24]. http:www.flickr.com

Zhao Yongwei, born in 1988. PhD, lecturer. His research interests include image analysis and processing.

Zhou Yuan, born in 1978. Master, lecturer. Her research interests include image processing and multimedia technology.

Li Bicheng, born in 1970. PhD, professor. His research interests include data mining and artificial intelligence processing.

Object Retrieval Based on Enhanced Dictionary and Spatially-Constrained Similarity Measurement

Zhao Yongwei1, Zhou Yuan2, and Li Bicheng3

1(DepartmentofElectronicTechnology,CAPFEngineeringUniversity,Xi’an710000)2(SchoolofComputerScience,HenanUniversityofEngineering,Zhengzhou451191)3(InstituteofInformationSystemEngineering,PLAInformationEngineeringUniversity,Zhengzhou450002)

AbstractBag of visual words model based object retrieval methods have several problems, such as low time efficiency, the low distinction of visual words and the weakly visual semantic resolution because of missing spatial information and quantization error. In this article, an object retrieval method based on enhanced dictionary and spatially-constrained similarity measurement is proposed aiming at the above problems. Firstly, E2LSH (exact Euclidean locality sensitive hashing) is used to identify and eliminate the noise key points and similar key points, consequently, the efficiency and quality of visual words are improved; Then, the stop words of dictionary are eliminated by chi-square model (CSM) to improve the distinguish ability of visual dictionary; Finally, the spatially-constrained similarity measurement is introduced to accomplish object retrieval, furthermore, a robust re-ranking method with the K-nearest neighbors of the query for automatically refining the initial search results is introduced. Experimental results indicate that the quality of visual dictionary is enhanced, and the distinguish ability of visual semantic expression is effectively improved and the object retrieval performance is substantially boosted compared with the traditional methods.

Key wordsobject retrieval; bag of visual words model; exact Euclidean locality sensitive hashing(E2LSH); spatially-constrained similarity measure; chi-square model (CSM)

收稿日期：2015-01-20；修回日期：2015-07-07

基金項目：國家自然科學基金項目(60872142，61301232)

中圖法分類號TP391

This work was supported by the National Natural Science Foundation of China (60872142，61301232).