黨宏社，白 梅，張 娜

(陜西科技大學(xué) 電氣與信息工程學(xué)院，陜西 西安 710021)

基于ReliefF特征加權(quán)和KNN的自然圖像分類(lèi)方法

黨宏社，白 梅，張 娜

(陜西科技大學(xué) 電氣與信息工程學(xué)院，陜西 西安 710021)

為了對(duì)自然圖像有效準(zhǔn)確地分類(lèi)，提出了一種對(duì)圖像低層特征和KNN分類(lèi)算法中的近鄰樣本分別進(jìn)行加權(quán)的分類(lèi)方法。針對(duì)不同類(lèi)別圖像的視覺(jué)特征的差異，通過(guò)ReliefF算法計(jì)算訓(xùn)練集中每個(gè)類(lèi)別的特征權(quán)值，利用此權(quán)值來(lái)改進(jìn)待測(cè)圖像與訓(xùn)練集中圖像的距離度量；按照不同近鄰到待測(cè)樣本的距離遠(yuǎn)近，為不同近鄰賦予權(quán)值來(lái)改進(jìn)KNN算法在類(lèi)別決策上的不足。實(shí)驗(yàn)結(jié)果表明該方法較傳統(tǒng)KNN和特征加權(quán)KNN方法，準(zhǔn)確性提高且對(duì)不同K值具有良好的魯棒性。

自然圖像；ReliefF；特征加權(quán)；KNN；距離加權(quán)

隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，人們每天獲取的圖像資源也在快速增長(zhǎng)。據(jù)不完全統(tǒng)計(jì)Facebook網(wǎng)站每天新增3億張圖像，互聯(lián)網(wǎng)如何快速地對(duì)海量的圖像資源進(jìn)行處理是迫切需要解決的問(wèn)題，對(duì)圖像進(jìn)行有效分類(lèi)是其中重要的一步。

基于圖像內(nèi)容的分類(lèi)方法通過(guò)提取圖像所包含的視覺(jué)信息從而建立不同特征與圖像類(lèi)別之間的關(guān)系實(shí)現(xiàn)分類(lèi)。通過(guò)提取圖像的顯著圖表征圖像特征信息，利用視覺(jué)注意機(jī)制，選擇顯著目標(biāo)[1]進(jìn)而實(shí)現(xiàn)分類(lèi)，這種方法符合人類(lèi)的生物認(rèn)知能力，但是過(guò)度依賴(lài)前景目標(biāo)的檢測(cè)[2]。文獻(xiàn)[3-4]使用圖像低層的混合特征，即認(rèn)為每個(gè)特征對(duì)于分類(lèi)的權(quán)重是相同的。在進(jìn)行實(shí)際分類(lèi)的樣本中，有的特征對(duì)某個(gè)類(lèi)別的貢獻(xiàn)可能大于對(duì)另一個(gè)類(lèi)別的貢獻(xiàn)，因此，在對(duì)這樣的樣本進(jìn)行分類(lèi)時(shí)，可根據(jù)不同樣本對(duì)不同類(lèi)別的貢獻(xiàn)程度的大小，給圖像不同特征賦予不同的權(quán)重。ReliefF算法在進(jìn)行特征評(píng)估時(shí)，對(duì)數(shù)據(jù)類(lèi)型沒(méi)有限制，效率高，在解決多類(lèi)數(shù)據(jù)分類(lèi)特征選擇的問(wèn)題中取得了較好的效果[5-6]。

KNN分類(lèi)算法是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)領(lǐng)域應(yīng)用最為廣泛的算法之一。算法的基本思想是統(tǒng)計(jì)測(cè)試樣本的K個(gè)近鄰中多數(shù)樣本的類(lèi)別來(lái)決策該樣本的所屬類(lèi)別[7]。K值大小的選取在很大程度上影響了分類(lèi)效果，Gora等人[8]依照尋優(yōu)的思想提出了一種自動(dòng)選擇最優(yōu)K值的方法，取得了良好的分類(lèi)效果。理論上來(lái)說(shuō)，K值越大越好，但是隨著K值的增大，近鄰樣本與測(cè)試樣本距離越近才對(duì)分類(lèi)更有意義。文獻(xiàn)[9-10]也分別通過(guò)對(duì)距離進(jìn)行加權(quán)來(lái)改進(jìn)這一問(wèn)題的不足。

本文方法在圖像分類(lèi)過(guò)程中，首先提取圖像的顏色矩特征和灰度共生矩陣，利用ReliefF算法評(píng)估不同類(lèi)別圖像特征的重要程度，計(jì)算每個(gè)類(lèi)別的特征權(quán)重，用加權(quán)特征來(lái)學(xué)習(xí)KNN分類(lèi)模型；在選取K個(gè)近鄰時(shí)，按照距離越近對(duì)分類(lèi)貢獻(xiàn)越大的原則，對(duì)不同的近鄰賦予不同權(quán)重，使得KNN分類(lèi)算法對(duì)K值的選取具有良好的魯棒性。

1 基于ReliefF算法的特征加權(quán)

1.1 ReliefF算法簡(jiǎn)介

Relief算法是一種根據(jù)樣本特征對(duì)近距離樣本的區(qū)分能力來(lái)評(píng)估該特征重要程度的權(quán)重選擇算法，最早由Kira提出。Relief算法簡(jiǎn)單，運(yùn)行效率高，但是只能用于處理兩類(lèi)數(shù)據(jù)的分類(lèi)問(wèn)題[11]。因此后來(lái)出現(xiàn)了拓展的ReliefF算法和RRelieF算法，統(tǒng)稱(chēng)為Relief系列算法。其中RReliefF算法用來(lái)解決目標(biāo)屬性為連續(xù)值的回歸問(wèn)題，而本文中用到的ReliefF算法主要針對(duì)多類(lèi)數(shù)據(jù)分類(lèi)問(wèn)題，即對(duì)樣本集中的所有特征進(jìn)行評(píng)估，給每一個(gè)特征賦予一定的權(quán)重。算法首先從訓(xùn)練集中隨機(jī)選擇一個(gè)樣本R，然后從與R同類(lèi)樣本中找出q個(gè)近鄰樣本H，從與不同類(lèi)樣本中找出q個(gè)近鄰樣本M。對(duì)于樣本R中的某維特征rk，如果R與同類(lèi)樣本的距離diff(rk,R,H)小于與不同類(lèi)別樣本的距離diff(rk,R,M)，說(shuō)明特征rk對(duì)區(qū)分類(lèi)別是有益的，則給予該特征較大的權(quán)重；反之如果R與不同類(lèi)別樣本的距離diff(rk,R,M)大于與同類(lèi)樣本的距離diff(rk,R,H)，則說(shuō)明特征rk對(duì)分類(lèi)有著消極的作用，賦之較小的權(quán)重。

1.2 特征權(quán)重的計(jì)算

本文中自然圖像的特征通過(guò)顏色和紋理來(lái)表征。顏色矩利用線(xiàn)性代數(shù)中矩的概念，即圖像中任何的顏色分布都可以用矩來(lái)表示。顏色分布主要集中在低階矩中，將圖像中的顏色分布用顏色一階矩平均值(Average)、顏色二階矩方差(Variance)和顏色三階矩偏斜度(Skewness)來(lái)表示。利用顏色矩對(duì)圖像進(jìn)行描述，無(wú)需量化圖像特征，由于每個(gè)像素具有顏色空間的三個(gè)顏色通道，因此總共用9個(gè)分量來(lái)描述一幅圖像的顏色矩。圖像紋理特征反映了圖像區(qū)域內(nèi)重復(fù)出現(xiàn)的結(jié)構(gòu)變化及其灰度或色彩的排列規(guī)律，是圖像的全局統(tǒng)計(jì)特征。基于Gabor濾波器的紋理特征提取方法利用Gabor小波多方向與多尺度的特點(diǎn)，提取相關(guān)紋理信息，但是算法處理過(guò)程中

計(jì)算數(shù)據(jù)量大。本文采用灰度共生矩陣反映不同圖像在方向、間隔、變化幅度及快慢上的差異。選取corel圖片庫(kù)中的10個(gè)類(lèi)別的500幅自然圖像(每個(gè)類(lèi)別選取50幅)分別提取每幅圖像在0，π/4，π/2，3π/4方向上的4個(gè)特征參數(shù)(慣性矩、相關(guān)性、能量和均勻性)，共16個(gè)紋理特征屬性。

通過(guò)顏色和紋理特征提取算法獲取訓(xùn)練樣本中每幅圖像的特征向量R(r1,r2,…,r25)，為防止大數(shù)據(jù)淹沒(méi)小數(shù)據(jù)，按照式(1)作歸一化處理

(1)

對(duì)于某一類(lèi)別，隨機(jī)選擇其中的一個(gè)樣本，計(jì)算該樣本與所有樣本的距離，對(duì)所有距離值進(jìn)行排序得到同類(lèi)別中的q個(gè)近鄰樣本以及與之不同類(lèi)別中的近鄰樣本，由此根據(jù)reliefF算法計(jì)算樣本與樣本之間的差異并按照式(2)更新該類(lèi)別每個(gè)特征的權(quán)重。重復(fù)進(jìn)行m次，得到每個(gè)類(lèi)別中每個(gè)特征的權(quán)重，m和q是人為設(shè)定的參數(shù)。

(2)

式中：diff(A,R1,R2)表示2個(gè)樣本R1和R2在特征A的差異，Hj表示同類(lèi)樣本中第j個(gè)樣本，Mj(C)表示與R不同類(lèi)別C中的第j個(gè)近鄰樣本。其中

(3)

圖1是將權(quán)重訓(xùn)練主程序運(yùn)行20次得到的每個(gè)類(lèi)別屬性權(quán)重大小的結(jié)果，由圖中可以看出20次的結(jié)果趨勢(shì)相同，將結(jié)果匯總統(tǒng)計(jì)求得每個(gè)類(lèi)別圖像特征屬性權(quán)重的平均值得到表1，其中行為10個(gè)類(lèi)別編號(hào)，列為每個(gè)類(lèi)別的25個(gè)特征屬性的權(quán)值，屬性權(quán)重越大，說(shuō)明該屬性區(qū)分類(lèi)別的貢獻(xiàn)越大，即該類(lèi)別圖像與其他類(lèi)別圖像的差異最先表現(xiàn)在該屬性上。

圖1 各類(lèi)別圖像的特征屬性權(quán)重訓(xùn)練結(jié)果

屬性編號(hào)Africabeachbuildingbusdinosaurelephantflowerhorsejokulfood1042790549204328039680638804077008580573006607041802048010457004115043240696704469011380572404652050563052810629206111053690825604984014750703906848059664002190026700243002760026000201001010024300264001925002360032700265002670030000215000610025300285002236002240025700369003030023400221000490031600271002447000800009700081000770011300107000170008900073000818001030117500098001010014901113000130015300092000889000840007800110000760014600084000140009600088000611002662031640224502710032720313500015030770301802640110646006167072840783008817069150901206149065970594812006240063700609006250303900615008410059300658006071306013056260653206900087990620708622056290601505477140361404056028950242803984032050031702872046720346615063100603907179077270855406788088700605606450058711600547005680054300557029970055400758005300059100546170579505440063200675008760060220840205478057630533818028500262602446018840386002343001850245002867032521906447061750726807870085820692108979062060660805925200060100614005960061603013006020082900591006490059321059220562706480069520878506211085930567905994054632203965041310299202638047910322200380030610475103426230631406041071830774208463067980886406058064590586924005490067000546005590298900555007560053300594005462505800054500633306762087410603508407054770577905346

2 基于特征和距離加權(quán)的KNN圖像分類(lèi)算法

2.1 KNN算法

KNN是一種理論成熟的分類(lèi)算法，最早由Cover和Hart于1968年提出。算法的主要思想是：計(jì)算待測(cè)樣本與已知類(lèi)別的訓(xùn)練樣本的歐氏距離，尋找距離該待測(cè)樣本最近的K個(gè)鄰居，K個(gè)已知類(lèi)別樣本中，多數(shù)樣本所屬的類(lèi)別即為待測(cè)樣本的類(lèi)別。假設(shè)待測(cè)樣本為Xi=(x1,x2,…,xn)，訓(xùn)練集中樣本為Rj=(r1,r2,…,rn)。則二者之間的歐氏距離為

(4)

式中：xk，rk為待測(cè)樣本和訓(xùn)練樣本的特征屬性；n為樣本特征屬性的個(gè)數(shù)。

2.2 基于特征和距離加權(quán)的KNN圖像分類(lèi)

本文采用ReliefF算法對(duì)訓(xùn)練集中各類(lèi)別圖像進(jìn)行特征加權(quán)，在分類(lèi)決策的時(shí)候使用距離平方的倒數(shù)對(duì)各個(gè)近鄰樣本進(jìn)行加權(quán)。假設(shè)訓(xùn)練集L={(class,Rj),class=1,2,…,c;j=1,2,…,l}，共有l(wèi)個(gè)訓(xùn)練樣本，所屬c個(gè)類(lèi)別，且類(lèi)別標(biāo)簽class已知。訓(xùn)練樣本Rj=(r1,r2,…,rn)，每個(gè)樣本有n個(gè)特征屬性。待測(cè)樣本Xi=(x1,x2,…,xn)，求所屬類(lèi)別class。本文分類(lèi)算法具體步驟設(shè)計(jì)如下：

2)用ReliefF算法訓(xùn)練得到的權(quán)值進(jìn)行特征加權(quán)后，待測(cè)樣本與訓(xùn)練樣本的距離為

(5)

式中：λk代表第k個(gè)特征屬性的權(quán)值大小。

3)計(jì)算待測(cè)樣本與所有訓(xùn)練樣本的距離值，找出距離該待測(cè)樣本最近的K個(gè)訓(xùn)練樣本作為新的訓(xùn)練集，則待測(cè)樣本與K個(gè)近鄰樣本的距離依次為dc1,dc2,…,dcK。

5)對(duì)每個(gè)近鄰樣本進(jìn)行距離加權(quán)之后，則判別函數(shù)g定義為

(6)

式中：k_label為近鄰樣本的類(lèi)別標(biāo)簽。

(7)

對(duì)所有的待測(cè)樣本求判別函數(shù)g，則最大的g對(duì)應(yīng)的class值為待測(cè)樣本的類(lèi)別標(biāo)簽，即

class=argmaxg(class,Xi)

(8)

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

為了驗(yàn)證該算法的有效性，本文選取corel圖片庫(kù)中 1 000 幅自然圖像來(lái)做實(shí)驗(yàn)，該1 000幅圖像總共分為10個(gè)類(lèi)別，每個(gè)類(lèi)別100幅。實(shí)驗(yàn)中分別標(biāo)記為Africa(非洲)、beach(海灘)、building(建筑)、bus(公共汽車(chē))、dinosaur(恐龍)、elephant(大象)、flower(花朵)、horse(駿馬)、jokul(雪山)、food(食物)共10個(gè)標(biāo)簽。選擇其中的500幅作為訓(xùn)練樣本，剩下的作為測(cè)試數(shù)據(jù)驗(yàn)證本文算法的有效性。

在MATLAB環(huán)境下，提取訓(xùn)練集中每幅圖像的9維顏色特征和16維紋理特征，根據(jù)ReliefF算法訓(xùn)練得到每個(gè)類(lèi)別中每個(gè)屬性的權(quán)值大小(表1數(shù)據(jù))。利用得到的屬性權(quán)重訓(xùn)練KNN分類(lèi)算法，計(jì)算特征加權(quán)后的待測(cè)樣本與訓(xùn)練樣本之間的距離，尋找K個(gè)近鄰樣本，判斷K個(gè)近鄰樣本對(duì)分類(lèi)的貢獻(xiàn)程度，最終判定待測(cè)樣本所屬的類(lèi)別。圖2～圖4是當(dāng)K取10、20和30時(shí)，用標(biāo)準(zhǔn)KNN算法、ReliefF特征加權(quán)的KNN方法和同時(shí)使用特征加權(quán)和距離加權(quán)對(duì)500幅測(cè)試圖像進(jìn)行分類(lèi)的結(jié)果。

圖2 K=10時(shí)3種方法分類(lèi)準(zhǔn)確率

圖3 K=20時(shí)3種方法分類(lèi)準(zhǔn)確率

圖4 K=30時(shí)3種方法分類(lèi)準(zhǔn)確率

由圖2～圖4的仿真結(jié)果可以看出，隨著K值取值的不同，KNN分類(lèi)算法分類(lèi)準(zhǔn)確率波動(dòng)起伏較大。dinosaur(恐龍)和flower(花朵)兩個(gè)類(lèi)別由于圖像特征鮮明，所以?xún)H采用標(biāo)準(zhǔn)KNN算法就可以將其準(zhǔn)確分開(kāi)，充分說(shuō)明在分類(lèi)過(guò)程中，不同圖像類(lèi)別內(nèi)容對(duì)分類(lèi)的重要性。對(duì)于其他類(lèi)別圖像用ReliefF算法對(duì)KNN分類(lèi)算法進(jìn)行特征加權(quán)后，增加了各自類(lèi)別對(duì)特征區(qū)分能力，分類(lèi)準(zhǔn)確率有了一定的提高；在此基礎(chǔ)上再對(duì)近鄰樣本進(jìn)行距離加權(quán)，分類(lèi)準(zhǔn)確率相對(duì)于特征加權(quán)KNN又有了提高，同時(shí)對(duì)距離加權(quán)后的KNN算法克服了由于K值不同引起的分類(lèi)效果的波動(dòng)，具有一定的魯棒性。

4 結(jié)語(yǔ)

為了對(duì)自然圖像進(jìn)行有效準(zhǔn)確地分類(lèi)，本文提出了一種基于特征和距離加權(quán)的KNN分類(lèi)方法，利用ReliefF算法進(jìn)行特征加權(quán)，可以分析各個(gè)特征屬性對(duì)分類(lèi)的貢獻(xiàn)程度，并利用距離平方的倒數(shù)對(duì)近鄰樣本進(jìn)行距離加權(quán)，最后決定樣本所屬類(lèi)別。仿真結(jié)果表明，本文提出的方法相比于標(biāo)準(zhǔn)KNN算法和特征加權(quán)KNN算法，具有更高的準(zhǔn)確率，而且可以克服KNN分類(lèi)算法由于K值取值大小的不同引起的分類(lèi)誤差。圖像特征內(nèi)容豐富，如何選用最具有代表圖像內(nèi)容的特征是下一步研究的主要工作內(nèi)容。

[1] MARISA C.Visual attention：the past 25 years[J].Visio Research，2011，51(13)：1484-1525.

[2] TEOFILO DE C，GABRIELA C，F(xiàn)LORENT P.Images as sets of locally weighted features[J].Computer Vision and Image Understanding，2012，116(1)：68-85.

[3] 任建峰，郭雷，李剛.多類(lèi)支持向量機(jī)的自然圖像分類(lèi)[J].西北工業(yè)大學(xué)學(xué)報(bào)，2005，23(3)：295-298.

[4] 謝文蘭，石躍祥，肖平.應(yīng)用BP神經(jīng)網(wǎng)絡(luò)對(duì)自然圖像分類(lèi)[J].計(jì)算機(jī)工程與應(yīng)用，2010，46(2)：163-166.

[5] 李潔，高新波，焦李成.基于特征加權(quán)的模糊聚類(lèi)新算法[J].電子學(xué)報(bào)，2006，34(1)：89-92.

[6] 鄭潔，秦永彬，許道云.基于Relief的特征加權(quán)殼近鄰分類(lèi)算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2013，34(3)：951-954.

[7] HE J，TAN A H，TAN C L.A comparative study on chinese text categorization methods[C]//Proc. PRICAI’ 2000 Internantionnal Workshop on Text and Web Mining.Melbourne，Australia：[s.n.]，2000：24-35.

[8] GORA G，WOJNA A.A classifier combining rule induction and K-NN method with automated selection of optimal neighborhood[C]//Proc. 13th European Conference on Machine Learning. Berlin：[s.n.]，2002：111-123.

[9] 楊金福，宋敏，李明愛(ài).一種新的基于距離加權(quán)的模板約簡(jiǎn)K近

鄰算法[J].電子與信息學(xué)報(bào)，2011，33(10)：2378-2383.

[10] 肖輝輝，段艷明.基于屬性值相關(guān)距離的KNN算法的改進(jìn)研究[J].計(jì)算機(jī)科學(xué)，2013，40(11)：157-159.

[11] MALGORZATA W，PIOTR M.Automatic relief classification versusexpert and field based landform classification for the medium-altitude mountain range，the Sudetes，SW Poland[J].Geomorphology，2014(1)：133-146.

黨宏社(1962— )，博士，教授，主要從事計(jì)算機(jī)控制、多源信息融合、數(shù)字圖像處理等方面的研究；

白 梅(1990— )，女，碩士生，主研數(shù)字圖像處理、圖像檢索，為本文通訊作者；

張 娜(1989— )，女，碩士生，主研壓縮感知、圖像處理。

責(zé)任編輯：時(shí) 雯

Classification Method of Feature Weighted for Natural Images Based on ReliefF and K-nearest Neighbors

DANG Hongshe，BAI Mei，ZHANG Na

(SchoolofElectricalandInformationEngineering，ShaanxiUniversityofScienceandTechnology，Xi’an710021，China)

In order to classify the natural images more effectively and accurately，a classification method weigh images feature and the nearest neighbors of KNN is proposed.Since diverse categories images have different visual features，ReliefF is used to obtain the feature weight vector of each category in training set for weighing the distance between test images and training images；different weights are given for the K-nearest neighbors according to the distance to training images，so that the weakness of traditional KNN at the classification decisions is overcome effectively.Compared with the traditional KNN and feature-weighted KNN，the experimental result shows that this method has more accuracy and strong robustness for the number of the nearest neighbors.

natural images；ReliefF；feature-weighed；KNN；distance-weighed

陜西省科技廳社會(huì)發(fā)展科技攻關(guān)計(jì)劃項(xiàng)目(2015K18-05)

TP391

A

10.16280/j.videoe.2015.19.003

2015-02-13

【本文獻(xiàn)信息】黨宏社，白梅，張娜.基于ReliefF特征加權(quán)和KNN的自然圖像分類(lèi)方法[J].電視技術(shù),2015，39(19).