趙鵬坤，時愷澤，張素蘭

(1.太原科技大學(xué)計算機科學(xué)與技術(shù)學(xué)院，太原 030024；2.內(nèi)蒙古大學(xué)計算機學(xué)院，呼和浩特 010021)

?

一種基于粗糙集的視覺單詞生成方法

趙鵬坤1，時愷澤2，張素蘭1

(1.太原科技大學(xué)計算機科學(xué)與技術(shù)學(xué)院，太原 030024；2.內(nèi)蒙古大學(xué)計算機學(xué)院，呼和浩特 010021)

摘要：針對傳統(tǒng)BOV(Bag-of-visual words)模型，存在的歧義視覺單詞影響分類精度和效率等問題，采用粗糙集屬性約簡，提出一種視覺單詞生成方法。首先，利用BOV模型，生成訓(xùn)練圖像集和視覺詞典，并將其抽象為決策信息表，其中：決策表中對象按類分別標記作為決策屬性，視覺詞典中的視覺單詞標記為條件屬性；然后根據(jù)決策表中決策屬性的等價集和條件屬性的等價集，建立不相容對象等價集，并對決策表中每一個條件屬性進行啟發(fā)式學(xué)習(xí)，保留能夠引起不相容等價集數(shù)目變化的視覺單詞，形成必要視覺單詞集合；其次，根據(jù)必要視覺單詞集合，結(jié)合相對知識粒度，來衡量決策表中不必要視覺單詞的重要度，保存重要度值高的視覺單詞，消除屬性重要度低的視覺單詞，形成約簡視覺單詞集合，從而有效地消除了視覺詞包中，存在的歧義視覺單詞；最后通過實驗驗證了該方法對視覺單詞約簡是有效的和可行的。

關(guān)鍵詞：視覺單詞；粗糙集；屬性約簡；知識粒度

基于BOV模型[1]的圖像表示方法，因其對圖像放縮、旋轉(zhuǎn)以及仿射變換保持不變性，同時對噪聲、視覺變化保持一定的穩(wěn)定性，能夠有效表達圖像內(nèi)容成為底層視覺特征與高層語義的橋梁，因而在圖像場景分類[2]領(lǐng)域得到廣泛應(yīng)用。典型工作：文獻[3]在建立BOV模型的基礎(chǔ)上，通過融合空間上下文語義關(guān)系和圖像塊特征相似性，給出了圖像場景分類方法，在一定程度上提高了分類精度；文獻[4]針對全局特征對超聲圖像進行描述存在一定局限性，提出了一種利用局部特征描述超聲圖像，并結(jié)合多示例學(xué)習(xí)對超聲圖像進行分類。在一定程度上彌補了語義鴻溝[5]，提高了場景分類精度。但是，視覺詞包中存在有歧義的視覺單詞，使得上述基于BOV模型表示圖像信息的場景分類效果不理想。因此，對BOV模型中的視覺單詞進行約簡，形成一種有效的視覺單詞集，從而提高分類性能，是一個值得研究的主題。

屬性約簡[6]是粗糙集理論的核心內(nèi)容之一，其主要思想是在保持分類能力不變的前提下，消除信息系統(tǒng)(決策表)中不必要的知識。因此該理論在數(shù)據(jù)的決策與分析、模式識別、機器學(xué)習(xí)與知識發(fā)現(xiàn)等領(lǐng)域得到廣泛的應(yīng)用[7]。為了消除視覺詞包中有歧義的視覺單詞，本文采用粗糙集屬性約簡，提出了一種視覺單詞生成方法。實驗驗證了該方法的有效性。

1BOV模型及粗糙集相關(guān)概念

1.1　BOV模型

BOV模型最初是用來對文本進行分析和檢索，后經(jīng)過長期的研究與發(fā)展研究者將文本處理方法應(yīng)用于圖像識別中?；谝曈X單詞的詞包模型通常表示過程包括局部特征檢測、局部特征描述和直方圖建立。具體過程如下：首先，采用某種局部特征檢測算子確定局部特征的位置、大小和形狀；其次，通過局部特征描述算子(如SIFT)提取圖像局部特征向量，采用K-means算法對局部特征向量進行聚類，每一個聚類中心對應(yīng)于一個視覺單詞，所有視覺單詞集合組成視覺詞典；最后，對給定圖像將其匹配到距離最近的視覺單詞，匯出表示圖像視覺單詞出現(xiàn)頻率的直方圖。

設(shè)C是一個視覺單詞，D1和D2代表兩種不同的圖像場景語義類別，若經(jīng)過某種分類模型使得f∶C→D1，C→D2，則稱視覺單詞C是有歧義的。

1.2　粗糙集相關(guān)概念

定義1一個決策信息系統(tǒng)簡稱決策表T=(U，C，D，V，f)，其中U為一個非空有限對象的集合，論域U={X1，X2…Xn}，其中f∶U×(CUD)→V是一個二元信息決策表，V為屬性值。

定義2設(shè)決策表T=(U，C，D，V，f)，?A?C∪D，則屬性集A 的不可區(qū)分關(guān)系為IND(A)={(x，y)∈U2：?a∈A，f(x，a)=f(y，a)}，其中IND(A)構(gòu)成論域上的一個等價劃分記為U/IND(A).對任意條件屬性C等價劃分，稱為條件屬性等價集U/IND(C)(或條件?？臻g)；稱決策屬性D等價劃分為決策屬性等價集U/IND(D)(或決策?？臻g)[8]。

定義3[9]設(shè)決策表T=(U，C，D，V，f)，c∈C，如果存在xi≠xj且xi，xj∈U對于屬性值使得：f(xi，c)≠f(xj，c)并且f(xi，D)≠f(xj，D)成立，則稱該系統(tǒng)為不相容決策表，xi和xj為不相容對象。不相容對象集合稱為不相容等價集IN(C).

定義5對于給定決策表T=(U，C，D，V，f)若對于條件屬性R集存在任意a∈R使：POSR(D)≠POSR-{a}(D)成立，則稱是必要屬性，否則稱非必要屬性。所有必要屬性的集合稱為核屬性集[11]簡稱CORE(C).

定理2設(shè)決策表T=(U，C，D，V，f)，設(shè)R?C，?a∈R存在R是決策表T的最簡約簡集應(yīng)滿足：1)POSR(D)=POSC(D)，2)POSR(D)≠POSR-{a}(D)

定義6[12]設(shè)決策表T=(U，C，D，V，f)，R?C∪D，屬性集的?？臻g可表示為：U/IND(R)=U={X1，X2…Xi}，U/IND(R)的知識粒度可定義為：

定義7[13]設(shè)決策表T=(U，C，D，V，f)，已知條件粒度空間U/IND(C)，和決策粒度空間U/IND(D)，則條件屬性相對于決策屬性的相對知識粒度可定義為：

RG(C；D)=G(U/IND(C))-G(U/IND(C∪D)

定義8設(shè)決策表T=(U，C，D，V，f)，?a∈R，R?C定義a在決策表中的屬性重要度可定義為：

Sgf(a，R，D)=RG(R-{a}；D)-RG(R；D)

對于定義8中屬性重要度定義可知相對知識粒度度量了條件屬性子集粒度空間相對于決策屬性力度空間的粗細程度，當條件屬性減少時，相對知識粒度增大；反之，隨 條件屬性增加，相對知識粒度減小。屬性重要度度量了條件屬性增加或者減少元素前后相對知識粒度變化。

2基于粗糙集的視覺單詞生成方法

基于粗糙集的視覺單詞生成算法的主要思想：(1)生成基于BOV模型的決策表。首先對訓(xùn)練集圖像中局部特征進行描述、提取圖像的局部特征向量，通過K-means算法構(gòu)造初始視覺詞典，并對訓(xùn)練圖像BOV模型0-1歸一化，抽象出決策信息表。其中：圖像集標識為對象集，視覺單詞標識為條件屬性，表中對象按類別標記作為決策屬性。(2)根據(jù)決策表中決策屬性的等價集和條件屬性的等價集，建立不相容對象等價集，并對決策表中每一個條件屬性進行啟發(fā)式學(xué)習(xí)，保留能夠引起不相容等價集數(shù)目變化的視覺單詞，形成必要視覺單詞集合。(3)根據(jù)必要視覺單詞集合，結(jié)合相對知識粒度，來衡量決策表中非必要視覺單詞的重要度，保存重要度值高的視覺單詞，消除屬性重要度低的視覺單詞，形成約簡視覺單詞集合，從而有效地消除了視覺詞包中有歧義的視覺單詞。

根據(jù)上述思想，視覺單詞生成算法如下：

Step1：生成訓(xùn)練圖像基于BOV模型的決策表T=(U，C，D，V，f)，標記訓(xùn)練圖像集為對象集U={X1，X2…Xi}，視覺單詞集合C={c1，c2，c3…cn}為條件屬性集合，標記不同類別對象為決策屬性D={d1，d2，d3…dn}.

Step2：令CORE(C)=Φ，按照定義3得到關(guān)于決策表T的不相容等價集IN(C).

Step3：依據(jù)定理2，如果存在ci∈C，使得，IN(C)≠IN(C-ci)，則ci為必要視覺單詞。

CORE(C)=CORE(C)+{a}

Step4：令R=?(1)根據(jù)定理1，若滿足：1)POSCORE(D)=POSC(D)，2)存在b∈CORE(C)，使POSCORE(D)≠POSCORE-(D)，則R=CORE(C)，跳轉(zhuǎn)至Step5；否則轉(zhuǎn)(2)；

(2)對每個視覺單詞a，對每個a∈C-CORE,計算RG(CORE(C)∪{a}；D)；

(3)選擇視覺單詞a滿足：

(4)R=CORE(C)+{a}

Step5：輸出最簡視覺單詞集R.

3實例分析

為了驗證本文的方法，本文實例選取文獻[14]中的實例進行分析，令文獻中條件屬性a，b，c，e，f，g為BOV模型生成的視覺單詞，視覺單詞容量為6，d為決策屬性，將三類場景圖像決策值分別標記為0、1、2.表1為此類訓(xùn)練圖像BOV模型的決策信息表。

表1　決策表T

(1)計算決策表T中不相容等價集：

U/IND(C)={{X1}，{X2，X10}，{X3}，{X4，X9}，{X5，X8}，{X6，X7}}

U/IND(D)={{X1，X6，X10}，{X3，X5，X7，X8，X9}，{X2，X4}}

f(X2，C)=f(X10，C)∧f(X2，D)≠f(X10，D)

f(X6，C)=f(X7，C)∧f(X6，D)≠f(X7，D)

IN(C)={{X9，X10}，{X4，X9}，{X6，X7}}}

IN(C-a)={{X1，X2，X10}，{X4，X9}，{X6，X7}}}

根據(jù)定理1可知a，e為必要視覺單詞。得到必要視覺單詞集合CORE(C)={a，e}

根據(jù)定理2驗證可知POSCORE(D)≠POSC(D)，得到的CORE(C)非必要視覺單詞集合。

(3)求最簡視覺單詞集合：

由(2)可知C-CORE(C)={b，c，f，g}，根據(jù)定義7，計算必要視覺單詞集合的相對知識粒度RG(R；D)=20/91

條件屬性相對知識粒度：

RG(R+；D)=4/27，RG(R+{c}；D)=19/91

RG(R+{f}；D)=16/91，RG(R+{g}；D)=4/27

依據(jù)定義8判斷在決策表中屬性b,c,f,g重要度：

Sgf(b，R，D)=RG(R-；D)-RG(R；D)=8/91

Sgf(c，R，D)=RG(R-{c}；D)-RG(R；D)=1/91

Sgf(f，R，D)=RG(R-{f}；D)-RG(R；D)=4/91

Sgf(g，R，D)=RG(R-{g}；D)-RG(R；D)=8/91

可知b，g對于決策表重要度高，因此可得最簡視覺單詞集合R={a，b，e，g}.

(4)依據(jù)定理1，可驗證R為最簡屬性集。

4實驗結(jié)果及分析

實驗采用Oliva和Torralba提出的8類自然圖像場景作為數(shù)據(jù)集[15]，該數(shù)據(jù)庫以下簡稱為OT庫。本文選取OT庫中8類每一類100幅圖像，對不同視覺詞典容量分別進行五次實驗驗證其性能。

實驗在pentium(R)D-3.0 GHZ，CPU，512 MB內(nèi)存，Windows XP 系統(tǒng)環(huán)境，在MATLAB平臺下完成實驗。實驗采取6個不同視覺詞典容量{50，100，200，300，400，500}作為數(shù)據(jù)對象，具體的實驗結(jié)果如表2、圖1、圖2所示。

由表2可知，實驗采用本文方法約簡后視覺單詞數(shù)目明顯減少，驗證了本文方法能夠消除詞包中歧義性視覺單詞。同時由圖1(a)、(b)可知，相同初始視覺詞典條件下約簡后比約簡前分類所需時間減少，這是由于初始視覺詞典屬性約簡后視覺單詞數(shù)量減少，使得測試圖像的視覺單詞與訓(xùn)練圖像視覺詞典中視覺單詞之間匹配所需要的時間也將會減少，使得分類的效率比約簡前提高。

圖1　視覺詞典約簡前后對分類的影響

初始視覺單詞容量約簡后視覺單詞容量504410086200168300277400365500396

圖2　不同視覺詞典約簡后對分類精度的影響

由圖2可知，當初始視覺詞典容量較少時，不同的視覺單詞容易被表述為同一類別，造成歧義性現(xiàn)象，使得測試圖像視覺單詞與訓(xùn)練圖像視覺單詞容易出現(xiàn)錯誤識別，導(dǎo)致分類精度降低；隨著視覺詞典容量的逐步增加分類精度逐步最高。但當視覺詞典容量超過200之后分類精度逐漸降低，這主要是視覺詞典增大容易造成詞包中出現(xiàn)冗余問題，使得分類精度會逐漸降低趨于平穩(wěn)。

為了進一步驗證本文方法對圖像分類精度的影響。實驗選取相同的數(shù)據(jù)集，將本文的方法分別與文獻[16]及文獻[17]的方法進行比較。比較結(jié)果從表3中可以看出：本文采用粗糙集屬性約簡，可以更有效的消除視覺詞包中存在歧義性的問題，提高圖像場景分類精度，進而驗證本文方法的有效性。

表3　與其他文獻方法的對比

5結(jié)論

提出一種基于粗糙集的視覺單詞約簡方法，利用該方法生成不同容量大小的約簡視覺單詞，消除存在歧義的視覺單詞，提高了分類精度。實驗表明通過該方法對視覺單詞約簡是有效且可行的。下一步研究工作是將粗糙集分類應(yīng)用在圖像場景分類中。

參考文獻：

[1]褚萌，張素蘭，張繼福.一種新的基于頻繁加權(quán)概念格的視覺單詞生成方法[J].太原科技大學(xué)學(xué)報，2012,33(6)：421-425.

[2]SANCHEZ J，PERRONNIN F，MENSINK T，et al.Image classification with the fisher vector：Theory and practice[J].International journal of computer vision，2013，105(3)：222-245.

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

[4]丁建睿，黃劍華，劉家鋒，等.局部特征與多實例學(xué)習(xí)結(jié)合的超聲圖像分類方法[J].自動化學(xué)報，2013，39(6)：861-867.

[5]ZHANG D，ISLAM M M，LU G.A review on automatic image annotation techniques[J].Pattern Recognition，2012，45(1)：346-362.

[6]陳昊，楊俊安，莊鎮(zhèn)泉.變精度粗糙集的屬性核和最小屬性約簡算法[J].計算機學(xué)報，2012(5)：1011-1017.

[7]WANG C，HE Q，CHEN D，et al.A novel method for attribute reduction of covering decision systems[J].Information Sciences，2014，254：181-196.

[8]苗奪謙，王國胤，劉清，等.粒計算：過去，現(xiàn)在與展望[M].北京：科學(xué)出版社，2007.

[9]苗奪謙，徐菲菲，姚一豫，等.粒計算的集合論描述[J].計算機學(xué)報，2012，35(2)：351-363.

[10]王國胤，張清華.不同知識粒度下粗糙集的不確定性研究[J].計算機學(xué)報，2008，31(9)：1588-1598.

[11]張清華，王國胤，劉顯全.基于最大粒的規(guī)則獲取算法[J].模式識別與人工智能，2012，25(3)：388-396.

[12]張明，唐振民，徐維艷，等.可變多粒度粗糙集模型[J].模式識別與人工智能，2012，25(4)：709-720.

[13]桑妍麗，錢宇華.一種悲觀多粒度粗糙集中的粒度約簡算法[J].模式識別與人工智能，2012，25(3)： 361-336.

[14]黃國順，曾凡智，文翰.代數(shù)約簡的知識粒度表示及其高效算法[J].控制與決策，2014，29(8)：1354-1362.

[15]OLIVA A，TORRALBA A.Modeling the shape of the scene：a holistic representation of the spatial envelope[J].International Journal of Computer Vision，2001，42(3)：145-175.

[16]EMRAH E，NAFIZA A.Scene classification using spatial pyramid of latent topics∥Pattern Recognition (ICPR)，2010 20th International Conference on.Istanbul，Turkey：IEEE Computer Society，2010：3603-3606.

[17]鐘利華，張素蘭，胡立華，等.基于概念格層次分析的視覺詞典生成方法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2015(1)：136-141.

A Generation Method of Visual Words Based on Rough Set

ZHAO Peng-kun1，SHI Kai-ze2，ZHANG Su-lan1

(1.School of Computer Science and Technology，Taiyuan University of Science and Technology，Taiyuan 030024，

China；2.School of Computer Science and Technology，Inner Mongolia University，Huhehaote 010021，China)

Abstract：A method of generative visual words based on rough set attribute reduction was proposed for solving the problem that visual word ambiguity affects accuracy and efficiency of classification in the traditional BOV Bag-of-visual words model.First of all，the training image set and visual dictionary were generated by using BOV model，and were abstracted as decision information table.Besides objects in the decision table was labeled as decision attribute separately according to the class，visual words in the dictionary was labeled as condition attribute.Then incompatible object equivalence sets were established according to decision attribute in decision table of equivalent set and equivalent condition attribute set，and the necessary visual words collection were generated by using heuristic learning for each condition attribute of decision table and keeping the vision of the change of incompatible equivalent set number words.Secondly，ambiguous visual words in the visual words package were eliminated effectively by measuring the importance degree of decision making unnecessary visual words in the table so as to save high importance value of visual words according to the necessary visual words collection and relative knowledge granularity，thus eliminating the low visual word of attribute importance，forming the reduction of visual word set.In the end，experimental results validate the effectiveness and feasibility of the method.

Key words：visual words，rough set，attribute reduction，knowledge granularity

中圖分類號：TP391.4

文獻標志碼：A

doi：10.3969/j.issn.1673-2057.2016.01.001

文章編號：1673-2057(2016)01-0001-05

作者簡介：趙鵬坤(1988-)，男，碩士，主要研究方向為圖像語義標注。

基金項目：校博士啟動基金(20132005)

收稿日期：2015-03-25