張凱兵

(孝感學(xué)院計(jì)算機(jī)與信息科學(xué)學(xué)院,湖北孝感 432000)

通常,描述對(duì)象的元素很多,為了節(jié)省資源,節(jié)約計(jì)算機(jī)存儲(chǔ)空間和提高識(shí)別效率,在保證識(shí)別率的要求下,按某種準(zhǔn)則盡量選擇對(duì)正確分類(lèi)貢獻(xiàn)較大的特征,使得提取的特征具有良好的分類(lèi)性能。為此,很多情況下,需要對(duì)原始特征進(jìn)行某種變換獲得維數(shù)更少、分類(lèi)能力更強(qiáng)的變換特征[1]。在模式識(shí)別系統(tǒng)中,特征的提取與選擇是非常關(guān)鍵的步驟之一,一個(gè)成功的識(shí)別系統(tǒng)很大程度上依賴于特征的提取與選擇[2-4]。特征選擇是通過(guò)消除初始特征中相關(guān)的和冗余的信息,從而選擇維數(shù)較低的并能反映模式分類(lèi)信息的特征子集的過(guò)程。根據(jù)特征選擇過(guò)程中是否使用類(lèi)別信息可分為兩類(lèi):監(jiān)督特征選擇和非監(jiān)督特征選擇。監(jiān)督特征選擇是一種通過(guò)互信息[5]或Fisher標(biāo)準(zhǔn)[6],從原始特征中消除噪聲和不相關(guān)的信息,從而選擇最具可分性特征的方法。而非監(jiān)督特征選擇方法主要度量特征間的相似性或相關(guān)性以消除冗余信息,在保證分類(lèi)正確性的前提下降低特征維數(shù)[7]。特征選擇是眾多研究者一直關(guān)注的問(wèn)題。近年來(lái),同時(shí)考慮模式特征相關(guān)性和冗余性,將非監(jiān)督特征選擇和監(jiān)督特征選擇相結(jié)合的方法得到了廣泛的應(yīng)用[7-8],對(duì)提高識(shí)別率起到了積極的作用。同時(shí),基于數(shù)據(jù)融合技術(shù)的模式識(shí)別技術(shù)能有效改善識(shí)別器的精度。文獻(xiàn)[9]提出了使用主元分析(Principal Components Analysis,PCA)與線性鑒別分析(Linear Discriminant A-nalysis,LDA),獲得 PCA-LDA的融合特征空間進(jìn)行性別鑒別的方法。文獻(xiàn)[10]針對(duì)SVD分類(lèi)信息不足,提出了一種融合SVD和LDA特征進(jìn)行人臉識(shí)別。PCA是一種常見(jiàn)的非監(jiān)督數(shù)據(jù)降維方法,它將維數(shù)較高、彼此間存在一定相關(guān)性的原始特征變換成彼此不相關(guān)的但能反映原特征本質(zhì)信息的低維特征。而LDA是一種監(jiān)督特征選擇方法,它在減低數(shù)據(jù)維數(shù)的同時(shí)還考慮不同類(lèi)別模式間的類(lèi)別信息,使得投影后的特征子空間在同類(lèi)模式間類(lèi)內(nèi)散度最小化,而不同類(lèi)別模式類(lèi)間散度最大化,因此變換后的特征具有很強(qiáng)的可分性,但不能保證消除不同特征間的相關(guān)性和冗余性。本文結(jié)合PCA和LDA各自的優(yōu)點(diǎn),提出一種融合主成分分析(PCA)和線性判別分析(LDA)的手寫(xiě)數(shù)字識(shí)別新方法。該方法采用線性加權(quán)方案融合PCA和LDA特征,分別計(jì)算未知模式的PCA和LDA特征與訓(xùn)練樣本的PCA和LDA特征間的距離,對(duì)兩種距離進(jìn)行加權(quán)平均后,采用最近鄰分類(lèi)器判別測(cè)試樣本類(lèi)別。對(duì)USPS樣本庫(kù)和自備樣本庫(kù)的實(shí)驗(yàn)結(jié)果表明,與單一的 PCA和LDA方法相比,利用 PCA和LDA融合方法能進(jìn)一步提高識(shí)別正確率。

1 基于PCA和LDA的特征選擇

1.1 PCA特征選擇

主成分分析(principal component analysis)[11]是將分散在一組變量上的信息集中到某幾個(gè)綜合指標(biāo)(主成分)上的統(tǒng)計(jì)分析方法。利用主成分描述數(shù)據(jù)集內(nèi)部結(jié)構(gòu),起著數(shù)據(jù)降維作用,在模式識(shí)別中得到了廣泛應(yīng)用。PCA可將原始高維特征向量投影到一個(gè)低維子空間中,使得在平均誤差最小化情況下能重構(gòu)原向量。通過(guò)估計(jì)訓(xùn)練樣本的協(xié)方差矩陣,計(jì)算其特征向量和特征值,對(duì)特征值進(jìn)行排序,取最大的 k個(gè)特征值對(duì)應(yīng)的特征向量作為子空間的基向量,將 k個(gè)基向量按列排列成變換矩陣W=[w1,w2,…,wk]。設(shè) x是一個(gè) d維向量是所有N個(gè)樣本的均值,由y=WT(x-μ)可將原始d維征特征向量x變換成一個(gè)k維子空間中的向量y,且 k＜ d。

1.2 LDA特征選擇

LDA[12]是一種有效解決模式分類(lèi)問(wèn)題中可分性的方法,通過(guò)將初始特征投影到一組最具可分性的投影軸上,使得分類(lèi)模式在投影特征空間類(lèi)間散度最大,類(lèi)內(nèi)散度最小。

第i類(lèi)樣本的均值μi估計(jì)為:

總體樣本均值估計(jì)為:

第i類(lèi)樣本的協(xié)方差Si估計(jì)為:

則所有樣本的類(lèi)內(nèi)散度矩陣和類(lèi)間散度矩陣分別估計(jì)為:

設(shè)矩陣Wm×n是將原始樣本空間Rn向特征空間 Rm的投影矩陣。由于LDA要求類(lèi)內(nèi)散度最小而類(lèi)間散度最大,則可定義如下成本函數(shù):

最大化J(W)可得最優(yōu)投影矩陣W,即

其中{wi}是Sb和SW的最大的m個(gè)特征值{λi}對(duì)應(yīng)的廣義特征向量。根據(jù)變換矩陣W,所求的特征向量=WT,i=1,…,C,j=1,…,ni。

2 基于PCA和LDA融合策略

考慮到PCA和LDA變換的特點(diǎn),將兩者進(jìn)行融合能有效提高分類(lèi)器的性能。融合的目的主要克服單個(gè)分類(lèi)器或特征向量的不足,利用彼此間的互補(bǔ)性,從而進(jìn)一步提高的識(shí)別系統(tǒng)的識(shí)別正確率。由于PCA能在降低原始特征維數(shù)的同時(shí)保留其本質(zhì)信息,但不能保證變換特征的可分性,而LDA能減低原始特征維數(shù)的同時(shí)在最大限度地保持變換特征的可分性,但不能消除特征冗余信息,因此將兩者融合可以優(yōu)勢(shì)互補(bǔ),在消除冗余信息的同時(shí)能保持良好的可分性。

基于分類(lèi)器融合主要目標(biāo)是如何測(cè)度兩個(gè)模式之間的最終距離。文獻(xiàn)[13]在理論上分析了平均方案和乘積方案適用的條件。本文采用線性加權(quán)方案融合PCA和LDA特征,分別計(jì)算未知模式的PCA和LDA特征與訓(xùn)練樣本的 PCA和LDA特征間的距離,然后對(duì)兩種距離進(jìn)行加權(quán)平均,采用最近鄰分類(lèi)器實(shí)現(xiàn)最終分類(lèi)。融合過(guò)程如下:

2)計(jì)算未知模式與所有訓(xùn)練模式間的距離:

上式中,w是PCA與LDA之間融合的加權(quán)系數(shù),其值是[0,1]之間的某個(gè)常數(shù)。顯然,當(dāng)w=0時(shí),加權(quán)距離變?yōu)長(zhǎng)DA分類(lèi)結(jié)果;當(dāng)w=1時(shí),加權(quán)距離變?yōu)镻CA分類(lèi)結(jié)果。

4)根據(jù)計(jì)算的距離(di1,di2,…,diN)使用最近鄰分類(lèi)器進(jìn)行分類(lèi)決策:

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

采用美國(guó)郵政系統(tǒng)數(shù)據(jù)庫(kù)USPS[14]和自備手寫(xiě)數(shù)字樣本數(shù)據(jù)庫(kù)[15]對(duì)提出方法進(jìn)行實(shí)驗(yàn)。如圖1是部分USPS樣本。USPS樣本庫(kù)包括7291個(gè)訓(xùn)練樣本和2007個(gè)測(cè)試樣本,大小均為16×16的灰度圖像。

除USPS樣本庫(kù)外,采集不同人和書(shū)寫(xiě)工具書(shū)寫(xiě)的數(shù)字樣本構(gòu)成自備樣本數(shù)據(jù)庫(kù)。如圖2是部分自備樣本。該樣本庫(kù)由9000個(gè)樣本組成,其中訓(xùn)練集中有4000個(gè)樣本,測(cè)試集中有5000個(gè)樣本,每個(gè)樣本歸一化為48×48大小的二值圖像,訓(xùn)練集和測(cè)試集中每類(lèi)數(shù)字分別有400和500個(gè)樣本。

圖1 部分USPS手寫(xiě)數(shù)字樣本

圖2 部分自備手寫(xiě)數(shù)字樣本

對(duì)USPS訓(xùn)練集中的7291個(gè)樣本,將灰度數(shù)字圖像點(diǎn)陣按行方向構(gòu)成256維的原始向量,分別進(jìn)行PCA和LDA的變換矩陣,將訓(xùn)練集和測(cè)試集中的樣本變換到各自的特征子空間進(jìn)行融合,最后采用最近鄰分類(lèi)器進(jìn)行分類(lèi)識(shí)別。

對(duì)自備樣本庫(kù),先將規(guī)一化大小為48×48的二值圖像進(jìn)行細(xì)化,然后將字符圖像點(diǎn)陣從水平和垂直方向平分為6等份,提取48維的粗外圍特征。使用大小為8×8的網(wǎng)格將字符圖像點(diǎn)陣分割成36等份,取每份中的黑色像素個(gè)數(shù)對(duì)整個(gè)字符黑色像素的比率,構(gòu)成36維粗網(wǎng)格特征。將字符點(diǎn)陣向水平、垂直、45°、135°四個(gè)方向投影 ,每個(gè)方向取16個(gè)投影值,組成64維筆畫(huà)密度特征。從水平、垂直、45°、135°四個(gè)方向?qū)ψ址麍D像進(jìn)行投影,構(gòu)成12維筆畫(huà)投影特征。將以上四類(lèi)特征進(jìn)行組合,構(gòu)成160維的統(tǒng)計(jì)特征。對(duì)高維的統(tǒng)計(jì)特征,分別進(jìn)行PCA和LDA變換,將訓(xùn)練集和測(cè)試集中的樣本變換到特征子空間進(jìn)行融合,最后采用最近鄰分類(lèi)器進(jìn)行分類(lèi)識(shí)別。表1是USPS樣本庫(kù)和自備樣本庫(kù)分別使用 PCA、LDA和PCA+LDA三種方法得到的識(shí)別率對(duì)照表。

表1 不同方法識(shí)別率對(duì)照表

為得到最優(yōu)融合系數(shù),對(duì)公式(11)中的加權(quán)系數(shù)取[0,1]之間的值,變化步長(zhǎng)為0.1,分別得到兩個(gè)實(shí)驗(yàn)數(shù)據(jù)庫(kù)在不同融合系數(shù)下的識(shí)別率,變化曲線如圖3所示。由圖3可以看出,采用PCA+LDA的融合方法比單獨(dú)的 PCA和LDA方法獲得的識(shí)別率都要高,且當(dāng)融合系數(shù)w=0.8時(shí),獲得最高的識(shí)別率。因此,與單獨(dú)的 PCA和LDA識(shí)別方法相比,PCA+LDA的融合方法能有效性提高手寫(xiě)數(shù)字識(shí)別率。

圖3 不同融合系數(shù)識(shí)別率變化情況

4 結(jié)論

針對(duì)PCA和LDA特征選擇方法的優(yōu)點(diǎn)與不足,提出一種在分類(lèi)器層次上融合 PCA和LDA特征進(jìn)行手寫(xiě)字符識(shí)別方法。對(duì)USPS樣本庫(kù)和自備樣本庫(kù)的實(shí)驗(yàn)結(jié)果表明,與單獨(dú)的 PCA和LDA方法相比,本文提出的融合方法能獲得更高的識(shí)別正確率。

[1] 模式識(shí)別中的特征提取與計(jì)算機(jī)是絕不變量[M].北京:國(guó)防工業(yè)出版社,2001.

[2] 朱小燕,史一凡,馬少平.手寫(xiě)字符識(shí)別研究[J].模式識(shí)別與人工智能,2000(6):174-180.

[3] 馬少平,周瑩,朱小燕.基于模糊方向線索特征的手寫(xiě)體漢字識(shí)別 [J].清華大學(xué)學(xué)報(bào):自然學(xué)科版,1997(3):42-45.

[4] 胡中山,婁震,楊靜宇.基于多分類(lèi)器組合的手寫(xiě)體數(shù)字識(shí)別[J].計(jì)算機(jī)學(xué)報(bào),1999(4):369-374.

[5] Kwak N,Choi C.Input feature selection by mutual information based on Parzen window[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2002(12):1667-1671.

[6] Duda R,Hart P,Stork D.Pattern recognition[M].California:John Wiley&Sons,2000.

[7] Mitra P,Murthy C,Pal S.Unsupervised feature selection using feature similarity[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2002(3):301-312.

[8] Peng H,Long F,Ding C.Feature selection based on mutual information criterion of max-dependency,max-relevance,and min-redundancy[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(8):1226-1238.

[9] 何國(guó)輝,甘俊英.PCA-LDA算法在性別鑒別中的應(yīng)用[J].計(jì)算機(jī)工程,2006(19):208-210,213.

[10] Pang Yanwei,Yu Nenghai,Zhang Rong et al.Fusion of svd and lda for face recognition[C].International Conference on Image Processing,2004,2:1417-1420.

[11] Jolliffe I.Principal Component Analysis[M].Newyork:Springer-Verlag,1986.

[12] Belhumeur P,Hespanha J,and Kriegman D.Eigenfaces vs.fisherfaces:recognition using class specific linear projection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1997(7):711-720.

[13] Tax M,Breukelen M,Duin R,Josef K.Combining Multiple Classifiers By Averaging Or By Multiplying[J].Pattern recognition,2000,33:1475-1485.

[14] USPS Handwritten Digit Database[OL].http://www.cs.toronto.edu/roweis/data.html.

[15] 張凱兵,宋俊典,鄧立國(guó).手寫(xiě)字符樣本自動(dòng)采集研究[J].四川工業(yè)學(xué)院學(xué)報(bào),2004(S1):41-43.