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

褚 萌，張素蘭，張繼福

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

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

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

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

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

1.1 BOV 模型

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

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

圖1 場(chǎng)景中的一幅圖像Fig.1 An image in the scene

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

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

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

定義1 設(shè)一個(gè)形式背景K:=(U，A，R，W)，U表示對(duì)象集，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上任一個(gè)三元組，且O?U，D?A，w為屬性集D的權(quán)值，并且關(guān)于R滿足完備性，即

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

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

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

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

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

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

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

一個(gè)形式背景K=(U，A，R，W)，如表1所示，U={o1，o2，o3，o4，o5，o6}，A={d1，d2，d3，d4，d5}，依據(jù)式(1)，得到視覺(jué)單詞的權(quán)值，如表2所示，W={0.11，0.19，0.21，0.25，0.24}。設(shè)定內(nèi)涵重要性閾值β=0.16，則對(duì)應(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)概念格視覺(jué)單詞生成方法

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

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

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

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

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

4) 漸進(jìn)式新增一個(gè)結(jié)點(diǎn)(O，D);

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

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

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

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

9) 分別求出所有類(lèi)別的視覺(jué)詞典;

10) 對(duì)于每一類(lèi)的視覺(jué)詞典，求出Step10中所求出的交集，得到每一類(lèi)約簡(jiǎn)后的視覺(jué)單詞;

11) 將每一類(lèi)約簡(jiǎn)后的視覺(jué)單詞取并集，此并集即為圖像的全局視覺(jué)詞典。

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

[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]王宇石，高文.用基于視覺(jué)單詞上下文的核函數(shù)對(duì)圖像分類(lèi)[J].中國(guó)圖象圖形學(xué)報(bào)，2010，15(4):607-616.

[6]劉碩研，須德，馮松鶴，等.一種基于上下文語(yǔ)義信息的圖像塊視覺(jué)單詞生成算法[J].電子學(xué)報(bào)，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]張素蘭，郭平，張繼福，等.圖像語(yǔ)義自動(dòng)標(biāo)注及其粒度分析方法[J].自動(dòng)化學(xué)報(bào)，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]王欣欣，張素蘭.基于對(duì)象擴(kuò)展的概念格批處理構(gòu)造算法[J].太原科技大學(xué)學(xué)報(bào)，2009，30(5):368-373.

[12]杜秋香，張繼福，張素蘭.基于概念提升的概念格更新構(gòu)造算法[J].太原科技大學(xué)學(xué)報(bào)，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)概念格及其漸進(jìn)式構(gòu)造[J].模式識(shí)別與人工智能，2005，18(2):171-176.

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