黨宏社，白 梅，張 娜

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

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

黨宏社，白 梅，張 娜

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

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

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

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

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

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

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

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

1.1 ReliefF算法簡介

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

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

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

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

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

(1)

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

(2)

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

(3)

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

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

屬性編號Africabeachbuildingbusdinosaurelephantflowerhorsejokulfood1042790549204328039680638804077008580573006607041802048010457004115043240696704469011380572404652050563052810629206111053690825604984014750703906848059664002190026700243002760026000201001010024300264001925002360032700265002670030000215000610025300285002236002240025700369003030023400221000490031600271002447000800009700081000770011300107000170008900073000818001030117500098001010014901113000130015300092000889000840007800110000760014600084000140009600088000611002662031640224502710032720313500015030770301802640110646006167072840783008817069150901206149065970594812006240063700609006250303900615008410059300658006071306013056260653206900087990620708622056290601505477140361404056028950242803984032050031702872046720346615063100603907179077270855406788088700605606450058711600547005680054300557029970055400758005300059100546170579505440063200675008760060220840205478057630533818028500262602446018840386002343001850245002867032521906447061750726807870085820692108979062060660805925200060100614005960061603013006020082900591006490059321059220562706480069520878506211085930567905994054632203965041310299202638047910322200380030610475103426230631406041071830774208463067980886406058064590586924005490067000546005590298900555007560053300594005462505800054500633306762087410603508407054770577905346

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

2.1 KNN算法

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

(4)

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

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

本文采用ReliefF算法對訓(xùn)練集中各類別圖像進(jìn)行特征加權(quán)，在分類決策的時(shí)候使用距離平方的倒數(shù)對各個(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è)類別，且類別標(biāo)簽class已知。訓(xùn)練樣本Rj=(r1,r2,…,rn)，每個(gè)樣本有n個(gè)特征屬性。待測樣本Xi=(x1,x2,…,xn)，求所屬類別class。本文分類算法具體步驟設(shè)計(jì)如下：

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

(5)

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

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

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

(6)

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

(7)

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

class=argmaxg(class,Xi)

(8)

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

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

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

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

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

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

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

4 結(jié)語

為了對自然圖像進(jìn)行有效準(zhǔn)確地分類，本文提出了一種基于特征和距離加權(quán)的KNN分類方法，利用ReliefF算法進(jìn)行特征加權(quán)，可以分析各個(gè)特征屬性對分類的貢獻(xiàn)程度，并利用距離平方的倒數(shù)對近鄰樣本進(jìn)行距離加權(quán)，最后決定樣本所屬類別。仿真結(jié)果表明，本文提出的方法相比于標(biāo)準(zhǔn)KNN算法和特征加權(quán)KNN算法，具有更高的準(zhǔn)確率，而且可以克服KNN分類算法由于K值取值大小的不同引起的分類誤差。圖像特征內(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] 任建峰，郭雷，李剛.多類支持向量機(jī)的自然圖像分類[J].西北工業(yè)大學(xué)學(xué)報(bào)，2005，23(3)：295-298.

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

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

[6] 鄭潔，秦永彬，許道云.基于Relief的特征加權(quán)殼近鄰分類算法[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] 楊金福，宋敏，李明愛.一種新的基于距離加權(quá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的自然圖像分類方法[J].電視技術(shù),2015，39(19).