王佳欣，彭天強(qiáng)，高毫林

(1.河南工程學(xué)院 計(jì)算機(jī)學(xué)院,河南 鄭州 451191；

2.解放軍信息工程大學(xué) 信息系統(tǒng)工程學(xué)院,河南 鄭州 450002)

?

圖像特征聚類(lèi)優(yōu)先級(jí)判定方法

王佳欣1，彭天強(qiáng)1，高毫林2

(1.河南工程學(xué)院 計(jì)算機(jī)學(xué)院,河南 鄭州 451191；

2.解放軍信息工程大學(xué) 信息系統(tǒng)工程學(xué)院,河南 鄭州 450002)

摘要：由于圖像多種特征的表述能力不同，所以它們?cè)诓煌瑘D像集上的聚類(lèi)效果也不同.為確定在特定圖像集上圖像特征的聚類(lèi)優(yōu)先級(jí)，分析了3種全局特征顏色、紋理和形狀的區(qū)分力，通過(guò)圖像距離曲線(xiàn)說(shuō)明了其區(qū)分力的不同，并通過(guò)檢索結(jié)果驗(yàn)證了不同的區(qū)分力可導(dǎo)致檢索結(jié)果的不同，進(jìn)一步提出了由類(lèi)緊致性和類(lèi)分離性組成的判別指標(biāo)——簡(jiǎn)化全局聚類(lèi)質(zhì)量.實(shí)驗(yàn)證明，區(qū)分性強(qiáng)的特征判別指標(biāo)最好，該指標(biāo)可用于確定圖像聚類(lèi)的優(yōu)先級(jí)，從而決定聚類(lèi)時(shí)選取圖像特征的種類(lèi)和圖像特征選用的順序.

關(guān)鍵詞：圖像聚類(lèi)；聚類(lèi)優(yōu)先級(jí)；簡(jiǎn)化全局聚類(lèi)質(zhì)量

模式識(shí)別中的學(xué)習(xí)問(wèn)題主要包括無(wú)監(jiān)督學(xué)習(xí)(聚類(lèi))、有監(jiān)督學(xué)習(xí)(分類(lèi))和半監(jiān)督學(xué)習(xí)[1]，聚類(lèi)為一組對(duì)象創(chuàng)建分組或類(lèi)使得類(lèi)內(nèi)對(duì)象十分相似而類(lèi)間對(duì)象非常不同.雖然人們已經(jīng)提出了多種聚類(lèi)算法，但聚類(lèi)仍是一個(gè)具有挑戰(zhàn)性的問(wèn)題,一個(gè)聚類(lèi)算法會(huì)因?yàn)閿?shù)據(jù)機(jī)特征的選擇和算法參數(shù)的不同而得出不同的聚類(lèi)結(jié)果.

在圖像處理和計(jì)算機(jī)視覺(jué)中，聚類(lèi)主要是確定相似圖像元素分組的過(guò)程，圖像元素包括像素、圖像分塊、圖像中的物體甚至完整的圖像.其中,對(duì)圖像的聚類(lèi)是數(shù)據(jù)聚類(lèi)的主要應(yīng)用之一，它的目標(biāo)是對(duì)圖像集進(jìn)行分組，使同一類(lèi)的圖像比不同類(lèi)的圖像更相似[2].文獻(xiàn)[3]把圖像聚類(lèi)算法分為兩類(lèi)——有監(jiān)督的和無(wú)監(jiān)督的.有監(jiān)督的聚類(lèi)算法需要人為干預(yù)，也就是聚類(lèi)前對(duì)圖像進(jìn)行標(biāo)注，而這在在線(xiàn)應(yīng)用中幾乎是不可能的.由于不同的圖像特征對(duì)圖像的表述方式不同，所以它們的區(qū)分力會(huì)因圖像內(nèi)容的不同而不同.因此，在圖像內(nèi)容不同的圖像集中，各特征的區(qū)分力也會(huì)不同，這就會(huì)導(dǎo)致聚類(lèi)結(jié)果的不同.為了確定在特定圖像集中聚類(lèi)時(shí)采用特征的種類(lèi)或者特征采用的優(yōu)先級(jí)，需要對(duì)不同特征的優(yōu)先級(jí)進(jìn)行分析.與特征選擇不同，特征選擇主要是從特征中選取一定的維度也就是確定一個(gè)特征的子空間[4]；與特征組合也不同，特征組合通過(guò)對(duì)不同特征組合提高區(qū)分力[5].優(yōu)先級(jí)判定是根據(jù)區(qū)分力對(duì)特征的聚類(lèi)優(yōu)先級(jí)進(jìn)行判定，進(jìn)而確定最適合聚類(lèi)的特征.

本研究分析了不同圖像特征，主要是顏色、紋理和形狀的區(qū)分力，分別是顏色直方圖、Gabor紋理和幾何矩.為了直觀地顯示圖像特征的區(qū)分力，給出了不同特征的圖像距離曲線(xiàn)，不同特征的距離曲線(xiàn)和擬合曲線(xiàn)差異較大.還進(jìn)行了圖像檢索實(shí)驗(yàn)，發(fā)現(xiàn)檢索結(jié)果也有明顯差異.為描述不同圖像特征的區(qū)分力導(dǎo)致的檢索結(jié)果的差異，定義了一個(gè)判別因子——SOCQ(Simplified Overall Cluster Quality)，該因子值的大小能反映對(duì)應(yīng)圖像特征聚類(lèi)結(jié)果的好壞，可用來(lái)判斷哪種特征更適合于聚類(lèi)和各特征聚類(lèi)優(yōu)先級(jí)的高低.

1圖像特征的區(qū)分力

為了便于計(jì)算，主要討論圖像的全局特征，最常用的圖像全局特征是顏色、紋理和形狀，這里分別使用HSV顏色直方圖、Gabor紋理和幾何矩.

1.1特征提取

因?yàn)槊糠N特征都是圖像信息的一種近似，不同特征體現(xiàn)不同的圖像信息，所以對(duì)于同樣的兩幅圖像，其相似程度在不同特征下得出的結(jié)果可能不同.

HSV顏色直方圖是常用的圖像顏色特征之一，它需要把彩色圖像轉(zhuǎn)換到HSV空間并進(jìn)行量化.H，S和V的量化如下：

(1)

這3個(gè)分量的量化結(jié)果可以組合成一個(gè)變量：

x=9H+3S+V，

(2)

這里，x∈[0,71].這樣，圖像就可以用一個(gè)72維的直方圖來(lái)表示.

紋理特征是基于Gabor函數(shù)和小波計(jì)算的.給定一幅圖像I(x, y), 其Gabor小波變換定義如下：

(3)

式中，*表示共軛.假設(shè)局部紋理區(qū)域空間上相似，則可使用變換系數(shù)模值的均值μmn和標(biāo)準(zhǔn)差σmn來(lái)表示這個(gè)區(qū)域：

(4)

這樣，圖像特征就可以根據(jù)這兩個(gè)值構(gòu)造.實(shí)驗(yàn)使用的特征中設(shè)置尺度因子m = 5， n = 4，得出40維特征向量

(5)

形狀特征使用幾何矩進(jìn)行描述，它將圖像函數(shù)f(x,y)映射到xpyq的單項(xiàng)式上，x,y是圖像的坐標(biāo).圖像函數(shù)f(x,y)的(p+q)階幾何矩

(6)

其中，p=0，1，2，…，∞,q=0,1,2,…,∞.

采用對(duì)平移、尺度和旋轉(zhuǎn)具有不變性的7個(gè)不變矩，它們的性能在各種變形的情況下經(jīng)過(guò)了驗(yàn)證,其定義如下：

m1=η20+η02,

m3=(η30-3η12)2+(3η21+η03)2,

m4=(η30+η12)2+(η21+η03)2,

m5= (η30-3η12)(η30+η12)[(η30+3η12)2-3(η03+η21)2]+

(3η21-η03)(η21+η03)[3(η30+η12)2-(η03+η21)2],

m6=(η20-η02)[(η30+η12)2-(η21+η03)2]+4η11(η30-η12)(η21+η03),

m7= (3η21-η03)(η30+η12)[(η30+η12)2-3(η03+η21)2]+

(3η12-η30)(η21+η03)[3(η30+η12)2-(η03+η21)2],

(7)

其中,ηpq=upq/(u00)γ并且p+q=2,3,…,γ=1+(p+q)/2.這7個(gè)矩可以組成一個(gè)特征向量f=(m1,m2,…,m7)來(lái)表征一幅圖像.本實(shí)驗(yàn)使用的是25維向量：

(8)

1.2特征區(qū)分力

為了顯示3種圖像特征的區(qū)分力，從國(guó)際上普遍用于圖像目標(biāo)分類(lèi)的Caltech256圖像庫(kù)中選擇4類(lèi)共100幅圖像，每類(lèi)25幅，記作圖像集1.圖像集1的3種特征的特征分量分布如圖1所示.圖中,橫坐標(biāo)代表的是特征分量，縱坐標(biāo)代表的是特征分量值.可見(jiàn)，不同特征的特征分量分布圖變化趨勢(shì)相似，但近似程度仍有區(qū)別，也就是說(shuō)不同特征的區(qū)分力不同.

圖像距離對(duì)聚類(lèi)算法相當(dāng)重要，許多算法根據(jù)圖像間的歐式距離對(duì)圖像分組.為了便于直觀顯示，以第一幅圖像為基準(zhǔn)，給出了它與其他圖像特征的歐式距離，如圖2所示.

圖1　圖像集1的全局特征分量分布圖Fig.1　The global feature curves for image dataset 1

圖2　圖像集1中第1幅圖像與其他圖像在不同特征下的歐式距離Fig.2　The distance between the first image andother images in image dataset 1 for global feature

由圖可見(jiàn)，由于特征區(qū)分力的不同，3種特征的距離曲線(xiàn)的擬合曲線(xiàn)是不同的，這使得圖像集中同一幅圖像在不同特征情況下對(duì)于基準(zhǔn)圖像的相似度排名不同(距離越小，相似度越高，排名越靠前).為了直觀地顯示相似度排序，圖3給出了以第1幅圖像為檢索圖像的檢索結(jié)果(結(jié)果中的第1幅圖像即為檢索圖像). 圖3(a)用顏色特征進(jìn)行檢索，圖3(b)用紋理特征進(jìn)行檢索，這兩幅圖僅給出前30幅最相似圖像的檢索結(jié)果.可見(jiàn)，檢索結(jié)果是有較大差異的.

圖3　圖像集1在不同特征下的檢索結(jié)果Fig.3　The retrieval results of different feature for image dataset 1

因?yàn)椴煌卣鞯南鄬?duì)相似度可能不同，所以檢索結(jié)果也會(huì)有所不同.為了確定聚類(lèi)使用的最優(yōu)特征或特征使用優(yōu)先順序，借助于聚類(lèi)有效性分析方法進(jìn)行判決.

2聚類(lèi)有效性和OCQ(Overall Cluster Quality)

2.1聚類(lèi)有效性

數(shù)據(jù)集特征選擇和算法參數(shù)值的不同,會(huì)導(dǎo)致聚類(lèi)算法的結(jié)果不同[6].從數(shù)據(jù)分布的觀點(diǎn)看，聚類(lèi)算法難以得出好的結(jié)果的一個(gè)重要原因是沒(méi)有關(guān)于數(shù)據(jù)結(jié)構(gòu)的先驗(yàn)信息.因此，聚類(lèi)的準(zhǔn)確性完全依賴(lài)于數(shù)據(jù)和聚類(lèi)算法獲取數(shù)據(jù)結(jié)構(gòu)信息的程度.為了簡(jiǎn)化聚類(lèi)算法，可以為數(shù)據(jù)集指定某種結(jié)構(gòu).例如，假設(shè)數(shù)據(jù)是高斯分布的合成，這樣就可以通過(guò)EM算法解決問(wèn)題.但是，如果假設(shè)的結(jié)果是錯(cuò)的，聚類(lèi)結(jié)果也會(huì)很差.因此，使用某種目標(biāo)測(cè)度以量化的方式對(duì)聚類(lèi)結(jié)果進(jìn)行評(píng)價(jià)是重要的，這就是聚類(lèi)有效性分析.聚類(lèi)有效性分析在模式識(shí)別中是一個(gè)主要的研究方向，它致力于發(fā)現(xiàn)數(shù)據(jù)集的分布、確定最合適的聚類(lèi)算法和決定某一聚類(lèi)方法的最優(yōu)參數(shù).

聚類(lèi)有效性的判定主要有3種方法，第一種方法基于外部準(zhǔn)則，它為數(shù)據(jù)集預(yù)先設(shè)置一種數(shù)據(jù)結(jié)構(gòu)，在此基礎(chǔ)上評(píng)價(jià)聚類(lèi)結(jié)果；第二方法基于內(nèi)部準(zhǔn)則，它在數(shù)據(jù)集自身向量數(shù)量的基礎(chǔ)上對(duì)聚類(lèi)結(jié)果進(jìn)行評(píng)價(jià)；第三種方法基于相關(guān)準(zhǔn)則，也就是在和其他聚類(lèi)方案比較的基礎(chǔ)上進(jìn)行評(píng)估，不同的聚類(lèi)方案可以由同一算法的不同參數(shù)產(chǎn)生，也可以來(lái)自不同的聚類(lèi)算法.前兩種方法是基于統(tǒng)計(jì)檢驗(yàn)的，主要缺點(diǎn)是計(jì)算量較高，而且它們主要衡量數(shù)據(jù)集與預(yù)先設(shè)置方案的吻合程度，但預(yù)先設(shè)置的方案未必是最合適的.

2.2Renyi熵和OCQ

好的聚類(lèi)結(jié)果應(yīng)該最符合數(shù)據(jù)集的分布，也就是說(shuō)數(shù)據(jù)點(diǎn)分給哪個(gè)類(lèi)與數(shù)據(jù)的內(nèi)在結(jié)構(gòu)吻合.這種思想在數(shù)學(xué)上可以用信息論來(lái)實(shí)現(xiàn)，也就是使用熵來(lái)衡量不確定度.常用的是Renyi熵[7]，其定義為

(9)

其中，pk是離散數(shù)據(jù)的概率集合函數(shù).當(dāng)α=2時(shí)，可得二次Renyi熵，也就是香農(nóng)熵.當(dāng)使用Parzen窗方法近似數(shù)據(jù)的概率函數(shù)時(shí)，有

(10)

這里，Gauss(·)是高斯函數(shù)，N是樣本數(shù)量，V(x)是與樣本間平方距離對(duì)應(yīng)的指數(shù)衰減函數(shù).

在相關(guān)準(zhǔn)則的基礎(chǔ)上，He等[8]根據(jù)Renyi熵提出了基于緊致性和分離性的聚類(lèi)評(píng)價(jià)函數(shù).緊致性描述了每個(gè)類(lèi)的成員之間的靠近程度，分離性描述了各個(gè)類(lèi)之間的靠近程度.

類(lèi)緊致性由數(shù)據(jù)集的偏離性定義：

(11)

(12)

這里，k表示數(shù)據(jù)集X產(chǎn)生的類(lèi)的數(shù)目，dev(Ci) 表示類(lèi)Ci的偏差，dev(X)表示數(shù)據(jù)集X的偏差.

類(lèi)分離性借助了文獻(xiàn)[9]的思想和聚類(lèi)評(píng)價(jià)函數(shù)的形式，其定義為

(13)

其中，σ是高斯常量.為簡(jiǎn)化計(jì)算，令2σ2=1，k是類(lèi)數(shù)目，ci是Ci的中心，d(ci,cj)表示ci和cj中心的距離.

He用類(lèi)緊致性和類(lèi)分離性組合成總體聚類(lèi)指標(biāo)來(lái)評(píng)價(jià)聚類(lèi)質(zhì)量，其定義為

Ocq(X)=β·Cmp(X)+(1-β)·Sep(X),

(14)

其中,β∈[0，1]是類(lèi)緊致性和類(lèi)分離性的平衡因子，如Ocq(0.5)給兩部分衡量相同的權(quán)重.

2.3簡(jiǎn)化OCQ(SOCQ)

由前述可見(jiàn)，Cmp(X)的值越小類(lèi)緊致性越強(qiáng)，Sep(X)的值越小類(lèi)分離性越強(qiáng),即OCQ的取值隨著類(lèi)緊致性和類(lèi)分離性的增加而單調(diào)遞減.但是，由于Sep(X)中指數(shù)運(yùn)算的計(jì)算復(fù)雜度較高，它設(shè)計(jì)的目的是反映類(lèi)間距離的影響，同時(shí)與Sep(X)有相同的單調(diào)性.因此，可以設(shè)計(jì)一個(gè)新的簡(jiǎn)化的OCQ，它的Sep(X)不使用指數(shù)函數(shù)，僅保留類(lèi)中心距離d2(ci，cj)，稱(chēng)作Simplified OCQ(即SOCQ).新的Sep(X)定義為

(15)

這時(shí)，Sep(X)隨著類(lèi)中心距離平方和的增加而單調(diào)增加.因此，為了不改變SOCQ的單調(diào)性，使它的兩部分有相同的單調(diào)性，將SOCQ(X) 定義為

Ocq(X)=-β·Cmp(X)+(1-β)·Sep(X),

(16)

其中,β=0.5.因此，SOCQ隨著類(lèi)分離性和類(lèi)緊致性的增加而單調(diào)增加，與OCQ的單調(diào)性相反.

3實(shí)驗(yàn)

從圖3可以看出圖像集1的3種特征區(qū)分性不同，紋理和形狀特征的區(qū)分性不是十分明顯，檢索結(jié)果的準(zhǔn)確率也不高.為構(gòu)建區(qū)分性強(qiáng)的圖像集，從TRECVID選擇4類(lèi)75幅圖像構(gòu)成圖像集2，這4類(lèi)圖像分別來(lái)自于“compere”、“singer”、“rice” 和“sports”.對(duì)圖像集2進(jìn)行檢索，結(jié)果見(jiàn)圖4.查詢(xún)圖像為這兩幅圖中的第1幅圖像.

圖4　圖像集2在不同特征下的檢索結(jié)果Fig.4　The retrieval results of different feature for image dataset 2

從圖4可以看出，顏色特征的檢索結(jié)果要好于紋理特征.這說(shuō)明對(duì)于該查詢(xún)圖像，顏色特征的區(qū)分性要好于紋理特征.同樣，圖5給出了第4類(lèi)第1幅圖像即第56幅圖像與圖像集2中其他圖像的距離和各自的擬合曲線(xiàn).可見(jiàn)，圖中的距離曲線(xiàn)有明顯的階躍.與圖2相比，該圖的階躍更加明顯，這說(shuō)明該圖像集的類(lèi)間距離更大.

圖5　圖像集2中第56幅圖像與其他圖像的距離Fig.5　The distance between the 56th image and other images for image dataset 2

同時(shí)，圖5中3種特征的階躍程度也不同，前兩者高于后者，這說(shuō)明第3種特征的區(qū)分性最弱.為計(jì)算聚類(lèi)結(jié)果的OCQ值，對(duì)圖像集2采用k-means算法進(jìn)行聚類(lèi)并重復(fù)20次，結(jié)果見(jiàn)圖6(a).可見(jiàn)，形狀特征的OCQ因子最大、顏色特征最小，這說(shuō)明顏色特征聚類(lèi)的結(jié)果最好、形狀特征最差.類(lèi)似地，計(jì)算該聚類(lèi)結(jié)果的SOCQ因子值，結(jié)果見(jiàn)圖6(b).3種特征因子值的大小關(guān)系與圖6(a)相比是相反的，但反映的聚類(lèi)效果相同，即顏色特征的聚類(lèi)效果最好、形狀特征的聚類(lèi)效果最差.

圖6　圖像集2的OCQ和SOCQ因子的值Fig.6　The OCQ and SOCQ of image dataset 2

4結(jié)語(yǔ)

為判定在特定圖像集上哪種特征更適合于聚類(lèi)，提出了描述特征區(qū)分力的判別因子——SOCQ，用它來(lái)確定圖像特征聚類(lèi)的優(yōu)先級(jí).SOCQ值高的圖像特征聚類(lèi)優(yōu)先級(jí)高，更適合于聚類(lèi)，因?yàn)樵撎卣鞯膮^(qū)分性更強(qiáng).SOCQ與OCQ的不同不僅在于它的計(jì)算復(fù)雜度低，還在于它可以在聚類(lèi)之前進(jìn)行計(jì)算，這也是它與聚類(lèi)有效性分析不同的地方.如果需要使用多種特征進(jìn)行聚類(lèi)，可將SOCQ值高的特征賦予較高的優(yōu)先級(jí).

參考文獻(xiàn)：

[1]ChapelleO,ScholkopfB，ZienA.SemisupervisedLearning[M].Cambridge：MAMITPress，2006.

[2]JainAK,MurtyMN,FlynnPJ.Dataclustering:areview[J].ACMComputingSurveys,1999，31(3):264-323.

[3]KrinidisS,KrinidisM，ChatzisV.AnunsupervisedimageclusteringmethodbasedonEEMDimagehistogram[J].JournalofInformationHidingandMultimediaSignalProcessing，2012，3(2):151-163.

[4]QinBS,JingJN,WangGT.Afastclustering-basedfeaturesubsetselectionalgorithmforhigh-dimensionaldata[J].IEEETransactionsonKnowledgeandDataEngineering,2013，25(1):1-14.

[5]TrungTN,ZhuRL,SilanderT,etal.Onlinefeatureselectionformodel-basedreinforcementlearning[C]∥Proceedingsofthe30thInternationalConferenceonMachineLearning.Atlanta：[s.n.],2013.

[6]苑瑋琦，谷宗輝.全手掌紋5類(lèi)主線(xiàn)特征選擇方法研究[J].儀器儀表學(xué)報(bào),2012,33(4):942-948.

[7]MichaelJA,Berry,LinoffG.DataMiningTechniquesforMarketing,SalesandCustomerSupport[M].NewYork:JohnWiley&Sons,1996.

[8]HeJ,TanAH,ChewLT.Modifiedart2Agrowingnetworkcapableofgeneratingafixednumberofnodes[J].IEEETransactionsonNeuralNetworks,2004(15):728-737.

[9]GokcayE,PrincipeJ.AnewclusteringevaluationfunctionusingRenyi’sinformationpotential[C]∥ProceedingsoftheInternationalConferenceAcoustic,Speech,SignalProcessing.Istanbul:[s.n.],2000.

Cluster priority level decision method for image features

WANG Jiaxin1, PENG Tianqiang1, GAO Haolin2

(1.CollegeofComputerScienceandEngineering,HenanInstituteofEngineering,Zhengzhou451191，China；

(2.InstituteofInformationSystemEngineering,InformationEngineeringUniversity,Zhengzhou450002,China)

Abstract:Because of the different distinguishing ability for different features, the image cluster effects are also different for different image dataset. To decide cluster priority level of different features for one specific image dataset, we analyzed the distinguishing ability of three typical image features color histogram, Gabor texture and geometric moment, and showed the difference of the distinguishing ability among three global image features through their distance curves, and verified the difference of the distinguishing ability among three global image features through their different retrieval results. Based on the analysis, we presented a cluster discriminant index called Simplified Overall Cluster Quality, which is composed of two parts, cluster compaction part and cluster separation part. The experiment results showed that the feature with best distinguishing ability also possesses best discriminant index. So, this index can be used to decide the best feature which can be used to cluster images or the priority of features used for cluster.

Key words:image cluster; cluster priority level; simplified overall cluster quality

作者簡(jiǎn)介：王佳欣(1983-)，男，河南洛陽(yáng)人，講師，主要從事計(jì)算機(jī)應(yīng)用方面的研究.

基金項(xiàng)目：國(guó)家自然科學(xué)基金(61301232);河南省教育廳科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目(14A520066)

收稿日期：2014-11-12

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

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

文章編號(hào)：1674-330X(2015)01-0070-07