一種新的基于頻繁加權(quán)概念格的視覺單詞生成方法

褚 萌，張素蘭，張繼福

(太原科技大學(xué)計算機科學(xué)與技術(shù)學(xué)院，太原 030024)

基于BOV(Bag-of-visual words)模型表示的方法來源文本檢索和自然語言處理，通過一系列視覺單詞的統(tǒng)計直方圖將圖像表示出來，因其簡單直觀的表示方式，BOV(Bag-of-visual words，視覺詞袋)成為圖像表示和場景語義分類的研究熱點之一。近年來，BOV[1]模型廣泛存在于圖像眾多領(lǐng)域當中。

目前，對BOV的研究主要集中在:1)局部基元提取，大部分采用David Lowe提出的SIFT[2](Scale Invariant Feature Transform，尺度不變特征變換)算法，SIFT特征對圖像縮放、旋轉(zhuǎn)以及仿射變換保持不變性，并且對視角變化、噪聲保持一定的穩(wěn)定性，是目前圖像局部特征研究領(lǐng)域取得較成功的一種方法，在目標識別[2]、圖像拼接[3]、圖像匹配[4]等領(lǐng)域應(yīng)用極其廣泛。2)視覺單詞生成，目前主要有兩種視覺單詞方法:一種是Vogel[3]等人所使用的人工標注方法，另一種為無監(jiān)督聚類算法[4]，例如K-means算法。因為手工標注在某些方面存在問題及缺陷，比如工作量巨大、主觀性強，所以當前在生成視覺單詞的方法中，采用無監(jiān)督聚類算法已成為一種最主要的渠道。文獻[5]在普通的視覺單詞基礎(chǔ)上提出了一種新的能夠融合單詞多層上下文的核函數(shù)，提高了圖像識別的準確率。文獻[6]考慮視覺單詞的語義信息，提出了一種基于上下文語義信息的圖像塊視覺單詞生成算法，有效地提高了視覺單詞的語義準確性，改善了場景分類的性能。視覺詞包模型提供的結(jié)構(gòu)化圖像描述框架，在解決類的多樣性、相似性、光照變化、位置差異等一些問題中，優(yōu)點尤為突出，所以，基于視覺詞包模型表示圖像內(nèi)容已成為一種主流方法，并且BOV方法已經(jīng)在圖像分類等領(lǐng)域中得到廣泛應(yīng)用[4-9]。但是由于傳統(tǒng)的視覺單詞生成方法沒有考慮視覺單詞與語義類別，及其視覺單詞本身之間隱含的關(guān)聯(lián)關(guān)系，而且，利用大量高維的視覺單詞進行分類，效率不高。因此，通過分析BOV視覺詞典中視覺單詞，以及視覺單詞之間隱含的關(guān)聯(lián)關(guān)系，對視覺單詞進行約簡，生成一種有效的視覺單詞，提高圖像分類的性能，仍然是個值得研究的主題。

概念格[10-12]，是進行數(shù)據(jù)分析和知識提取的有力工具，具有知識表示的直觀性、完備性和概念層次性，已在信息檢索、數(shù)字圖書館、知識發(fā)現(xiàn)等方面得到廣泛應(yīng)用[10-13]。文獻[14]給出了一種新的概念格結(jié)構(gòu):加權(quán)概念格，彌補了一般概念格假定內(nèi)涵各屬性同等重要的不足。為使得基于加權(quán)概念格上提取的知識更好地滿足用戶需求，并且更加具有實際意義。文獻[15]提出了一種基于信息熵的加權(quán)概念格單屬性權(quán)值獲取方法。由于大量高維的視覺單詞影響圖像語義標注的精度和效率，本文采用頻繁加權(quán)概念格對視覺單詞進行分析與約簡，提出了一種新的視覺單詞生成方法，實驗驗證了該方法的有效性。

1 BOV模型與頻繁加權(quán)概念格

1.1 BOV 模型

基于視覺單詞的詞包模型表示就是在圖像中構(gòu)建與文本單詞相類似的視覺詞匯，首先使用某種算法(例如SIFT算法)提取圖像局部特征，進而描述這些特征區(qū)域，其次通過K-means算法對這些區(qū)域的特征向量進行聚類，以此來構(gòu)建視覺詞典，最后根據(jù)圖像中各個視覺詞匯出現(xiàn)的統(tǒng)計分布，得到表述圖像的視覺單詞統(tǒng)計直方圖。

圖1為我們所選50副場景圖像(Lazebnik[9]場景圖像庫中)中的一幅圖像，假設(shè)視覺詞典的大小為200，圖2是描述該圖像的視覺單詞統(tǒng)計直方圖。

圖1 場景中的一幅圖像Fig.1 An image in the scene

圖2 圖1的視覺單詞統(tǒng)計直方圖表示Fig.2 The visual words histogram representation of Fig.1

1.2 頻繁加權(quán)概念格

在文獻[14]中，針對對象屬性的不同重要性，將權(quán)值引入到概念格的內(nèi)涵中，提出了加權(quán)概念格這一新的格結(jié)構(gòu)。相關(guān)概念如下:

定義1 設(shè)一個形式背景K:=(U，A，R，W)，U表示對象集，A是屬性集，W為屬性的權(quán)值集，R?U × A，其中 U={o1，o2，…，on}，A ={d1，d2，…，dm}，W={w1，w2，…，wm} 且0 ≤wi≤1，wi表示屬性di的重要性，設(shè)h=(O，D，w)為K上任一個三元組，且O?U，D?A，w為屬性集D的權(quán)值，并且關(guān)于R滿足完備性，即

同時成立，則稱h是K上的一個加權(quán)概念，O稱為h的外延，D稱為h的內(nèi)涵。

定義2 設(shè)形式背景K上的加權(quán)概念h1=(O1，D1，W1) 和 h2=(O2，D2，W2) 是兩個不同的結(jié)點，則h1≤h2?D2?D1?O1?O2，≤表示為概念之間的偏序關(guān)系，如果不存在加權(quán)概念h3=(O3，D3，W3)有h1≤h3≤h2成立，則h2稱為h1的父結(jié)點，h1稱為h2的子結(jié)點。形式背景中的所有加權(quán)概念及其之間的這種偏序關(guān)系構(gòu)成的K上的一般加權(quán)概念格，表示為 ＜ LW(U，A，R，W)，≤ ＞，簡記為LW(U，A，R，W).

對于已給定的形式背景，在專家和用戶先驗知識未知的情況下，很難得到形式背景單屬性內(nèi)涵權(quán)值，各屬性特征的重要程度無法確定給出，在文獻[15]中，為標識屬性內(nèi)涵重要性的大小，采用了一個與概率有關(guān)的函數(shù)來測度，即通過信息熵獲得單屬性權(quán)值，見式(1)，這種方法為描述隱含于形式背景各屬性特征重要性上提供了一條新的途徑。

其中任意對象oi∈U(1≤i≤n)具有屬性d的概率為P(d/oi)，H(d)表示屬性d的重要性，即每個對象提供于d的平均信息量。

定義3 形式背景K上屬性集為A={d1，d2，…，dm}，對于任意屬性 di∈ A(1≤ i≤ m)，令Wqz(di)=H(di)=wi，wi稱為單屬性 di的重要性權(quán)值。對于形式背景K上的一個加權(quán)概念h=(O，D，w)，D=dk1∪dk2∪dk3∪…dkm，dk1，dk2，dk3，…，dkm的單屬性重要性權(quán)值分別為 wk1，wk2，wk3，…，wkm.令:

w稱為多屬性內(nèi)涵的權(quán)值。

定義4 依據(jù)用戶對內(nèi)涵感興趣的程度，定義屬性集重要性的最小閾值θmin(1≤θmin≤1)，形式背景K上的任意一個加權(quán)概念h=(O，D，w)，若w≥θmin，h就稱為頻繁加權(quán)概念，則稱 ＜ Lf(U，A，R，W)，≤＞為頻繁加權(quán)概念格，簡記為 Lf(U，A，R，W).

一個形式背景K=(U，A，R，W)，如表1所示，U={o1，o2，o3，o4，o5，o6}，A={d1，d2，d3，d4，d5}，依據(jù)式(1)，得到視覺單詞的權(quán)值，如表2所示，W={0.11，0.19，0.21，0.25，0.24}。設(shè)定內(nèi)涵重要性閾值β=0.16，則對應(yīng)的頻繁加權(quán)概念格如圖3所示。

表1 形式背景Tab.1 A formal context

圖3 頻繁加權(quán)概念格Fig.3 Frequent-weighted concept lattice

表2 單屬性內(nèi)涵權(quán)值獲取方法Tab.2 Acquisition method for single-intent weight value for single attribute

2 基于頻繁加權(quán)概念格視覺單詞生成方法

基于頻繁加權(quán)概念格的視覺單詞生成算法思想:(1)生成基于BOV模型的形式背景，首先對已構(gòu)造的BOV模型進行0-1歸一化(對BOV模型中的每個值做判斷，如果大于等于定義的某一歸一化閾值α，此時這個值就設(shè)為1，否則為0)，之后將圖像集標識作為對象集，視覺單詞標識作為屬性集，由此生成BOV模型的形式背景。(2)基于BOV模型形式背景單屬性內(nèi)涵權(quán)值的獲取，利用式(1)得到H(di)，獲取單屬性內(nèi)涵di的權(quán)值wi，多屬性內(nèi)涵權(quán)值采用算術(shù)平均值計算。(3)針對某一語義類別，根據(jù)輸入的內(nèi)涵重要性閾值β，按照文獻[14]已給出了頻繁加權(quán)概念的漸進式構(gòu)造方法，構(gòu)造BOV模型的類別頻繁加權(quán)概念格。(4)遍歷類別頻繁加權(quán)概念格結(jié)點，選取大于外延閾值γ的結(jié)點內(nèi)涵所對應(yīng)的屬性集，并求其并集，得到每一特定類別的視覺詞典，進而得到每一類別約簡后的視覺詞典。(5)融合(4)步約簡后的各類別視覺詞典，得到最終表示圖像的全局視覺詞典。

依據(jù)上述思想，視覺單詞生成算法步驟描述如下:

1) 生成訓(xùn)練圖像基于BOV模型的形式背景;

2) VW=?，輸入β和γ;//VW表示某一類別的視覺詞典，β為內(nèi)涵重要性閾值，γ為外延數(shù)閾值;

3) 利用式(1)，計算H(di)并且進行歸一化，獲得單屬性內(nèi)涵di的權(quán)值w;

4) 漸進式新增一個結(jié)點(O，D);

5) 若D由單屬性構(gòu)成，Step7;

6) 否則，利用式(2)計算內(nèi)涵D的權(quán)值w;

7) 如果w＜β，則不生成該結(jié)點，Step4，否則，生成該結(jié)點;

8) 如果 n(0)≥ γ，VW=VW∪{O}，Step4;//n(0)表示結(jié)點(O，D，w)的外延元素個數(shù);

9) 分別求出所有類別的視覺詞典;

10) 對于每一類的視覺詞典，求出Step10中所求出的交集，得到每一類約簡后的視覺單詞;

11) 將每一類約簡后的視覺單詞取并集，此并集即為圖像的全局視覺詞典。

在上述視覺單詞生成過程中，利用生成的BOV模型頻繁加權(quán)概念結(jié)構(gòu)對視覺單詞進行分析，將不滿足外延數(shù)閾值γ的內(nèi)涵屬性(即視覺單詞)舍去，從而生成用戶所需求的并且對圖像語義具有一定貢獻程度的視覺單詞，更加具有實際意義。

圖4 視覺單詞數(shù)目對分類的影響Fig.4 The impact of the number of visual words for classification

3 實驗結(jié)果與分析

為了驗證本文提出算法的有效性，采用Lazebnik的15類自然場景圖像作為數(shù)據(jù)集，其中包含大量類別已標注的圖像，每一類均包括200幅至400幅圖像，總共有4485幅圖像，其中包括bedroom，suburb，industrial，kitchen，livingroom，coast，forest等場景。

每類圖像隨機選擇50幅圖像加入訓(xùn)練集，選取50幅圖像作為測試集，這里采用KNN方法來進行分類，實驗中進行5次隨機劃分得到訓(xùn)練集和測試集圖像，然后分別計算每次劃分的分類精度，最終的分類精度即為5次劃分分類精度的平均值。

首先分析傳統(tǒng)視覺單詞數(shù)目對分類性能的影響，現(xiàn)設(shè)定不同大小的視覺單詞{50，100，200，400，600，900}，實驗結(jié)果如圖4表示。從圖4(a)可以得到，隨著視覺單詞數(shù)目的不斷增多，分類時間逐漸增大。因為視覺單詞數(shù)目變多之后，使用KNN方法進行分類，測試圖像的sift特征向量與訓(xùn)練集視覺單詞之間歐式距離的計算次數(shù)相應(yīng)也會增多，所以，分類的耗時會越多。從圖4(b)可以看出:一方面，較少的視覺單詞判別力不高，可能導(dǎo)致不相似的兩個視覺單詞分配到同一個類別中;另一方面，隨著視覺單詞數(shù)目的不斷增多，分類性能有所提高，但視覺單詞的數(shù)目超過200之后，分類性能不再提升反而呈現(xiàn)下降趨勢，這是因為過多的視覺單詞泛化能力有限，不適應(yīng)計算量及噪聲較大的情況。

實驗采用分類精度較高的視覺單詞數(shù)目為200的情形進行分析。實驗閾值的設(shè)定分別為:內(nèi)涵重要性閾值 β=0.05，外延閾值γ=15，aver為BOV模型概率矩陣中所有概率的平均值，歸一化閾值α分別取 0.3*aver，0.5*aver，0.7*aver，0.9*aver，實驗結(jié)果如表3所示。

從表3可以看出，通過該算法四種歸一化閾值得到的視覺單詞訓(xùn)練集的個數(shù)依次為2926、2755、2297、1542，與初始的15類3000個(每一類視覺單詞數(shù)目為200，共15類，因此15類有3000個視覺單詞)視覺單詞相比，視覺單詞有所減少，分類所需時間也依次減少，這是因為歸一化閾值增大的同時，基于BOV模型的形式背景就會越來越稀疏，生成的概念格節(jié)點就會相應(yīng)減少，從而分析約簡得到的視覺單詞就會縮減，所以分類耗時就會減少。同時從表3中，還可以看出，分類的性能比較穩(wěn)定，而且在歸一化閾值取0.5*aver時，分類精度為74%，與文獻[7]和文獻[9]的分類精度(分別為72.2%和73.9%)相比，算法的精度有所提高，從而充分地說明所生成的視覺單詞能有效地表示圖像，并用于場景分類。

表3 β=0.05，γ=15時視覺單詞生成和分類的時間和精度Tab.3 The generation of visual words and the time and accuracy of classification when β is 0.05 and γ is 15

4 結(jié)束語

提出了一種新的基于頻繁加權(quán)概念格的視覺單詞生成方法，依照該方法可以得到用戶所需求的并且能夠有效表示圖像集的約簡視覺詞匯，對于BOV理論的研究與加權(quán)概念格的應(yīng)用研究都有一定的研究價值。另外，充分利用概念格表示知識所具有的概念層次特點，得到用戶關(guān)心的，能夠自動標注圖像語義的具有不同層次粒度的場景分類知識是下一步需要研究的工作。

[1]PEDRO QUELHAS，F(xiàn)LORENT MONAY，JEAN-MARC ODOBEZ，et al.A Thousand Words in a Scene[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2007，29(9):1575-1589.

[2]LOWE D.Distinctive image features from scale invariant keypoints[J].International Journal on Computer Vision，2004，60(2):91-110.

[3]VOGEL J，SCHIELE B.Semantic modeling of natural scenes for content based image retrieval[J].International Journal of Computer Vision，2007，72(2):133-157.

[4]NOWAK E，JURIE F，TRIGGS B.Sampling strategies for bag of features image classification[C]//Proc of European Conference on Computer Vision(ECCV’06).Austria:Springer，2006:490-503.

[5]王宇石，高文.用基于視覺單詞上下文的核函數(shù)對圖像分類[J].中國圖象圖形學(xué)報，2010，15(4):607-616.

[6]劉碩研，須德，馮松鶴，等.一種基于上下文語義信息的圖像塊視覺單詞生成算法[J].電子學(xué)報，2010，38(5):1156-1161.

[7]LI F F，PERONA P.A Bayesian Hierarchical Model for Learning Natural Scene Categories[C]//Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition，Washington DC:IEEE Computer Society，2005:524-531.

[8]張素蘭，郭平，張繼福，等.圖像語義自動標注及其粒度分析方法[J].自動化學(xué)報，2012，38(5):688-697.

[9]LAZEBNIK S，SCHMID C，PONCE J.Beyond bags of features:Spatial pyramid matching for recognizing natural scene categories[C]//Proc.of IEEE Int.Conf.on Computer Vision and Pattem Recognition(CVPR’06).USA:IEEE Computer Society，2006:2169-2178.

[10]WILL E R.Restructuring lattice theory:an approach based on hierarchies of concepts[M].Dordrecht Boston，Rival，ed.Reidel:1982:445-470.

[11]王欣欣，張素蘭.基于對象擴展的概念格批處理構(gòu)造算法[J].太原科技大學(xué)學(xué)報，2009，30(5):368-373.

[12]杜秋香，張繼福，張素蘭.基于概念提升的概念格更新構(gòu)造算法[J].太原科技大學(xué)學(xué)報，2009，30(1):1-6.

[13]KWON O，KIM J.Concept lattices for visualizing and generating user profiles for context-aware service recommendations[J].Expert Syetems with Applications.2009，36(2):1893-1902.

[14]張繼福，張素蘭，鄭鏈.加權(quán)概念格及其漸進式構(gòu)造[J].模式識別與人工智能，2005，18(2):171-176.

[15]張素蘭，郭平，張繼福.基于信息熵和偏差的加權(quán)概念格內(nèi)涵權(quán)值獲取[J].北京理工大學(xué)學(xué)報，2011，31(1):59-63.