趙鵬坤，時(shí)愷澤，張素蘭

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

?

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

趙鵬坤1，時(shí)愷澤2，張素蘭1

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

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

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

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

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

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

1.1　BOV模型

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

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

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

定義1一個(gè)決策信息系統(tǒng)簡(jiǎn)稱(chēng)決策表T=(U，C，D，V，f)，其中U為一個(gè)非空有限對(duì)象的集合，論域U={X1，X2…Xn}，其中f∶U×(CUD)→V是一個(gè)二元信息決策表，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)成論域上的一個(gè)等價(jià)劃分記為U/IND(A).對(duì)任意條件屬性C等價(jià)劃分，稱(chēng)為條件屬性等價(jià)集U/IND(C)(或條件?？臻g)；稱(chēng)決策屬性D等價(jià)劃分為決策屬性等價(jià)集U/IND(D)(或決策?？臻g)[8]。

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

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

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

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

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

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)

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

2基于粗糙集的視覺(jué)單詞生成方法

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

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

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

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

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

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

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

(2)對(duì)每個(gè)視覺(jué)單詞a，對(duì)每個(gè)a∈C-CORE,計(jì)算RG(CORE(C)∪{a}；D)；

(3)選擇視覺(jué)單詞a滿(mǎn)足：

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

Step5：輸出最簡(jiǎn)視覺(jué)單詞集R.

3實(shí)例分析

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

表1　決策表T

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

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為必要視覺(jué)單詞。得到必要視覺(jué)單詞集合CORE(C)={a，e}

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

(3)求最簡(jiǎn)視覺(jué)單詞集合：

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

條件屬性相對(duì)知識(shí)粒度：

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對(duì)于決策表重要度高，因此可得最簡(jiǎn)視覺(jué)單詞集合R={a，b，e，g}.

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

4實(shí)驗(yàn)結(jié)果及分析

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

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

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

圖1　視覺(jué)詞典約簡(jiǎn)前后對(duì)分類(lèi)的影響

初始視覺(jué)單詞容量約簡(jiǎn)后視覺(jué)單詞容量504410086200168300277400365500396

圖2　不同視覺(jué)詞典約簡(jiǎn)后對(duì)分類(lèi)精度的影響

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

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

表3　與其他文獻(xiàn)方法的對(duì)比

5結(jié)論

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

參考文獻(xiàn)：

[1]褚萌，張素蘭，張繼福.一種新的基于頻繁加權(quán)概念格的視覺(jué)單詞生成方法[J].太原科技大學(xué)學(xué)報(bào)，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]劉碩研，須 德，馮松鶴，等.一種基于上下文語(yǔ)義信息的圖像塊視覺(jué)單詞生成算法[J].電子學(xué)報(bào)，2010，38(5)：1156-1161.

[4]丁建睿，黃劍華，劉家鋒，等.局部特征與多實(shí)例學(xué)習(xí)結(jié)合的超聲圖像分類(lèi)方法[J].自動(dòng)化學(xué)報(bào)，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)泉.變精度粗糙集的屬性核和最小屬性約簡(jiǎn)算法[J].計(jì)算機(jī)學(xué)報(bào)，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]苗奪謙，王國(guó)胤，劉清，等.粒計(jì)算：過(guò)去，現(xiàn)在與展望[M].北京：科學(xué)出版社，2007.

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

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

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

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

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

[14]黃國(guó)順，曾凡智，文翰.代數(shù)約簡(jiǎn)的知識(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]鐘利華，張素蘭，胡立華，等.基于概念格層次分析的視覺(jué)詞典生成方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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

中圖分類(lèi)號(hào)：TP391.4

文獻(xiàn)標(biāo)志碼：A

doi：10.3969/j.issn.1673-2057.2016.01.001

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

作者簡(jiǎn)介：趙鵬坤(1988-)，男，碩士，主要研究方向?yàn)閳D像語(yǔ)義標(biāo)注。

基金項(xiàng)目：校博士啟動(dòng)基金(20132005)

收稿日期：2015-03-25