基于PCA和LDA融合的手寫數字識別方法

張凱兵

(孝感學院計算機與信息科學學院,湖北孝感 432000)

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

1 基于PCA和LDA的特征選擇

1.1 PCA特征選擇

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

1.2 LDA特征選擇

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

第i類樣本的均值μi估計為:

總體樣本均值估計為:

第i類樣本的協方差Si估計為:

則所有樣本的類內散度矩陣和類間散度矩陣分別估計為:

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

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

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

2 基于PCA和LDA融合策略

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

基于分類器融合主要目標是如何測度兩個模式之間的最終距離。文獻[13]在理論上分析了平均方案和乘積方案適用的條件。本文采用線性加權方案融合PCA和LDA特征,分別計算未知模式的PCA和LDA特征與訓練樣本的 PCA和LDA特征間的距離,然后對兩種距離進行加權平均,采用最近鄰分類器實現最終分類。融合過程如下:

2)計算未知模式與所有訓練模式間的距離:

上式中,w是PCA與LDA之間融合的加權系數,其值是[0,1]之間的某個常數。顯然,當w=0時,加權距離變為LDA分類結果;當w=1時,加權距離變為PCA分類結果。

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

3 實驗結果與分析

采用美國郵政系統數據庫USPS[14]和自備手寫數字樣本數據庫[15]對提出方法進行實驗。如圖1是部分USPS樣本。USPS樣本庫包括7291個訓練樣本和2007個測試樣本,大小均為16×16的灰度圖像。

除USPS樣本庫外,采集不同人和書寫工具書寫的數字樣本構成自備樣本數據庫。如圖2是部分自備樣本。該樣本庫由9000個樣本組成,其中訓練集中有4000個樣本,測試集中有5000個樣本,每個樣本歸一化為48×48大小的二值圖像,訓練集和測試集中每類數字分別有400和500個樣本。

圖1 部分USPS手寫數字樣本

圖2 部分自備手寫數字樣本

對USPS訓練集中的7291個樣本,將灰度數字圖像點陣按行方向構成256維的原始向量,分別進行PCA和LDA的變換矩陣,將訓練集和測試集中的樣本變換到各自的特征子空間進行融合,最后采用最近鄰分類器進行分類識別。

對自備樣本庫,先將規一化大小為48×48的二值圖像進行細化,然后將字符圖像點陣從水平和垂直方向平分為6等份,提取48維的粗外圍特征。使用大小為8×8的網格將字符圖像點陣分割成36等份,取每份中的黑色像素個數對整個字符黑色像素的比率,構成36維粗網格特征。將字符點陣向水平、垂直、45°、135°四個方向投影 ,每個方向取16個投影值,組成64維筆畫密度特征。從水平、垂直、45°、135°四個方向對字符圖像進行投影,構成12維筆畫投影特征。將以上四類特征進行組合,構成160維的統計特征。對高維的統計特征,分別進行PCA和LDA變換,將訓練集和測試集中的樣本變換到特征子空間進行融合,最后采用最近鄰分類器進行分類識別。表1是USPS樣本庫和自備樣本庫分別使用 PCA、LDA和PCA+LDA三種方法得到的識別率對照表。

表1 不同方法識別率對照表

為得到最優融合系數,對公式(11)中的加權系數取[0,1]之間的值,變化步長為0.1,分別得到兩個實驗數據庫在不同融合系數下的識別率,變化曲線如圖3所示。由圖3可以看出,采用PCA+LDA的融合方法比單獨的 PCA和LDA方法獲得的識別率都要高,且當融合系數w=0.8時,獲得最高的識別率。因此,與單獨的 PCA和LDA識別方法相比,PCA+LDA的融合方法能有效性提高手寫數字識別率。

圖3 不同融合系數識別率變化情況

4 結論

針對PCA和LDA特征選擇方法的優點與不足,提出一種在分類器層次上融合 PCA和LDA特征進行手寫字符識別方法。對USPS樣本庫和自備樣本庫的實驗結果表明,與單獨的 PCA和LDA方法相比,本文提出的融合方法能獲得更高的識別正確率。

[1] 模式識別中的特征提取與計算機是絕不變量[M].北京:國防工業出版社,2001.

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

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

[4] 胡中山,婁震,楊靜宇.基于多分類器組合的手寫體數字識別[J].計算機學報,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] 何國輝,甘俊英.PCA-LDA算法在性別鑒別中的應用[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] 張凱兵,宋俊典,鄧立國.手寫字符樣本自動采集研究[J].四川工業學院學報,2004(S1):41-43.