基于2DPCA的手寫數(shù)字識別

王軍平，趙振華

（1.咸陽職業(yè)技術學院 電子信息系，陜西 咸陽 712000；2.蘭州理工大學 電氣工程與信息工程學院，甘肅 蘭州 730050）

手寫數(shù)字識別研究有著廣泛的應用背景和重要的理論意義[1-3]。如今在郵政、財政、稅務等工作中都需要進行手寫數(shù)字的識別，識別結果的好壞直接影響到工作的效率。另外，由于數(shù)字識別的類別較小，有助于作深入分析及驗證一些新的理論。例如支持向量機的提出，就是先在手寫體數(shù)字識別領域里進行驗證，然后推廣到了其他的領域。

目前，對手寫數(shù)字識別的研究依據特征的提取可分為兩大類：基于字符統(tǒng)計規(guī)律和基于字符結構特征。基于統(tǒng)計規(guī)律的方法是利用字符樣本庫，找出0到9中每類字符空間分布的統(tǒng)計規(guī)律，構成分類器進行識別。基于字符結構特征的方法是分析字符筆畫的構造如圈、端點、交叉點、輪廓等來構造分類器進行識別。兩類方法各有優(yōu)勢，總體而言，統(tǒng)計方法能更好地描述一類模式的本質特征，對于與給定訓練集差別不大的字符具有較高的識別率；基于字符結構特征的方法精確地描述了字符的細節(jié)特征，對書寫結構較規(guī)范的字符有較高的識別率。

在字符的特征提取中，主元分析（PCA）是一種十分有效的方法。PCA的思想是將高維樣本空間的樣本投影到某個低維子空間，使得在該子空間中，投影樣本的類間方差最大，類內方差最小。在字符識別中，PCA方法通常是將樣本庫中的每個字符圖像矩陣轉換為一維向量，然后求出樣本總體的協(xié)方差矩陣，計算出該矩陣的特征值及特征向量，根據特征值及對應的特征向量確定子空間的基向量。子空間的這些基向量又稱為字符圖像的特征圖，每個字符圖像都可以由特征圖的不同加權和重構出來，其與原圖的均方誤差是沒有選取的那些特征值之和。由于選取的特征向量是對應于特征值較大的那些向量，一般遠少于特征向量總數(shù)，這樣就實現(xiàn)了對原始樣本空間的降維。

雖然PCA能有效地降低樣本空間的維數(shù)，但在實現(xiàn)過程中2D的圖像矩陣必須首先轉換為1D的圖像向量，其所產生的圖像向量空間的維數(shù)就很高，例如在MINIST字符庫中，每個字符圖像為28×28像素，轉換為一維圖像向量是1×784，這些圖像向量所構成的空間的維數(shù)就為784。這樣就很難精確計算相應的協(xié)方差矩陣。為了克服這一困難，就產生了二維主元分析（2DPCA）方法。相對于PCA，2DPCA是基于二維圖像矩陣而非一維向量，即不需將圖像轉換成一維的向量，取代PCA中樣本總體協(xié)方差矩陣的是圖像協(xié)方差矩陣，它是直接從字符圖像矩陣中構造出來的。這樣得到的圖像協(xié)方差矩陣較PCA要小很多。2DPCA有兩個明顯的優(yōu)點：首先容易精確計算協(xié)方差矩陣，其次確定相應的特征向量所耗的時間要少的多。

文中首先介紹2DPCA的原理及其算法的描述，隨后簡要說明識別過程要用到的一些圖像預處理，第3節(jié)講述兩種分類器的構造，第4節(jié)是實驗及結果分析，最后做出總結。

1 二維主元分析

1.1 原理及算法

用X表示一個歸一化的n維列向量，A為某個m×n的圖像矩陣，通過下面的線性變換將A投影到X：

這樣就得到了一個m維的向量Y，稱之為圖像A的投影特征向量。為了確定最佳的投影向量X，引入投影到X上的樣本的整體散度來度量X的分辨能力。投影樣本的總體散度可以用投影特征向量的協(xié)方差矩陣的跡來確定。由此得到下面的判據：

其中Sx表示訓練樣本的投影特征向量所構成的協(xié)方差矩陣，tr（Sx）表示的跡。通過對（2）式的最大化來找出X的某個投影方向，投影到該方向的樣本總體散度最大。協(xié)方差矩陣Sx可表示為

所以有

現(xiàn)在定義下面的矩陣

稱矩陣Gt為圖像協(xié)方差（散度）矩陣。容易驗證Gt為n×n非負定矩陣。Gt可以利用訓練圖像樣本直接計算出來。假定共有 M 個訓練樣本，Aj（j=1，2，…，M）表示第 j個訓練圖像，大小為m×n的矩陣，A表示所有訓練圖像的均值。則Gt為

則判據（2）可表示為

其中X為歸一化的列向量。使這個判據最大化的歸一化向量X被稱為最優(yōu)投影軸。直觀上講，它意謂著在圖像投影到X后，所得的投影樣本的總體散度是最大的。

最優(yōu)投影軸Xopt是最大化J（X）的歸一化向量，即Gt的特征向量中對應于最大特征值的那個特征向量。通常需要選取一組正交的投影軸，X1，…，Xd，來最大化 J（X），即

事實上，最優(yōu)的投影軸，X1，…，Xd，是 Gt的前 d 個最大特征值所對應的正交特征向量。

1.2 特征提取

已經得到了2DPCA的最優(yōu)投影向量X1，…，Xd，就可以用這些向量進行特征提取。對圖像樣本A，定義：

這樣得到一組特征向量Y1，…，Yd，稱之為樣本圖像A的主成分（向量）。注意2DPCA的每個主成分是向量，而PCA的主成分是標量。

用這些主成分向量構成一個m×d矩陣C=[Y1，…，Yd]，稱其為圖像樣本A的特征矩陣或特征圖。

1.3 基于2DPCA的圖像重構

在PCA方法中，重構圖像是用主成分和特征向量（特征圖）結合在一起完成的。2DPCA可以用下面類似的方法實現(xiàn)對圖像的重構。

設圖像的協(xié)方差矩陣為Gt，其前d個最大的特征值所對應的特征向量為X1，…，Xd，這些特征向量是正交的。將圖像樣本投影到這些向量軸上，生成主成分向量，Yk=AXk，（k=1，2，…，d）。 設

因為 X1，…，Xd是正交的，由（8）可以得到樣本 A的重構圖像：

2 字符識別方法

用2DPCA方法對字符圖像進行變換后，就可以利用圖像的主成分向量來構造分類器進行字符的識別。作為研究，文中采用了兩種識別方法。第一種是最鄰近法，另一為重構誤差法，下面分別介紹。

2.1 最鄰近法

其中‖Y（i）k-Y（j）k‖2表示兩個主成分向量Y（i）k和Y（j）k之間的歐氏距離。

現(xiàn)在假定訓練樣本為C1，C2，…，CN（N為訓練樣本的總數(shù)），并且每個樣本都指定了類別γk，對某個測試樣本C，若d（C，Cl）=mind（C，Cj），且 Cl∈γk，則有 C∈γk。

2.2 重構i誤差法

隨后分別計算出測試樣本與每類近似圖像的誤差，

則C應屬于誤差最小的那類字符，即

3 圖像預處理

為了提高字符的識別率，有必要對字符圖像進行一些預處理。預處理的目的是將字符的灰度圖像二值化，并將筆畫粗細統(tǒng)一規(guī)范為2個像素。

文中采用Otsu方法對字符圖像進行二值化。Otsu又稱最大類間方差法，是在最小二乘法原理的基礎上推導得出的。它通過利用直方圖零階、一階累積矩來最大化判別函數(shù)，選擇最佳閾值。

字符灰度圖像轉化為二值圖像后，利用數(shù)學形態(tài)學方法進行筆畫粗細的規(guī)范處理。下面簡單介紹一下本文所用到的一些數(shù)學形態(tài)法的原理。

數(shù)學形態(tài)學（Mathematical Morphology）是分析幾何形狀與結構的數(shù)學方法，目前它已成為分析圖像幾何特征的重要工具。它是由一組形態(tài)學的代數(shù)運算子組成，其中最基本的是腐蝕算子和膨脹算子，運用這些算子及其組合可以對圖像結構和形狀進行分析與處理。

對于一個給定的目標圖像X和一個結構元素S，如果S[x]∩X≠Φ，即S[x]與X的交集不為空集，表明它們部分相關，則稱這個點集為結構元素S對X的膨脹，記為X⊕S，用集合表示為X⊕S={x|S[x]∩X≠Φ}，膨脹運算可以看作是將圖像X中的每一個點x擴大為S[x]；與此相反，腐蝕是將X中的每一個與結構元素S全等的子集S[x]收縮為x所構成的集合，記為XΘS，用集合表示為

一個字符的“骨架”是描述其幾何及拓撲性質的重要特征。本文通過對經過二值化的字符進行細化，提取其骨架特征，然后用包括原點的2×2結構元素對骨架圖像進行一次膨脹。包括原點的2×2結構元素對圖像的膨脹，相當于沿著字符骨架在骨架像素的3鄰域分別“加粗”了一個像素，這就嚴格保證了字符所有筆畫均為2個像素寬度。

圖1是MINIST數(shù)據庫中部分樣本的處理結果。圖中第1行是原始樣本的灰度圖，第2行是二值化圖，第3行是骨骼化圖，第4行是筆畫規(guī)范圖。從圖中可以看出，通過上述預處理過程，使所有字符筆畫粗細取得一致，并且通過數(shù)學形態(tài)預處理，使圖像中字符的部分細節(jié)得到改善，從而使同類字符整體形態(tài)的一致性得到改善。

圖1 字符圖像預處理Fig.1 Image preprocession of digits

4 實驗及結果分析

本實驗采用的數(shù)據庫是MNIST數(shù)據庫[4]，此數(shù)據庫中含有60 000個訓練樣本和10 000個測試樣本，每個樣本都是28×28個像素的圖像加上一個樣本標示組成。

圖2 部分子圖Fig.2 Some reconstructed subimages

從圖2可以看到，第一個子圖包含了原始圖像的大部分信息，隨著k的增加，子圖 A?k的信息量逐漸減少，圖3所示的特征值也逐漸收斂到0，這是因為每個子圖對應著某個特征值，而特征值的大小反映了該子圖對重構原圖的貢獻。所以，可以認為原始圖像的大部分信息都集中在前幾個比較大的特征值所對應的子圖中，在識別過程中用這些主成分向量來表示原始圖像是合理的。

現(xiàn)在將這些子圖相加，就可以得到樣本的重構（近似圖，圖4給出了數(shù)字3的5個重構圖，它們是將前d（d=2，4，6，8，10）個子圖相加得到的。 隨著子圖數(shù)量的增加，近似圖越來越清晰。作為比較，同時也給出了用PCA的特征圖進行重構的近似圖，可以看到，2DPCA的效果要好于PCA。

圖3 降序排列的特征值幅度圖Fig.3 Plot of the magnitude of the eigenvalues in decreasing order

圖4 部分基于2DPCA（第一行）和PCA（第二行）重構圖Fig.4 Some reconstructed images based on 2DPCA （upper）and PCA （lower）

完成了字符的特征提取，接下來對測試樣本進行識別實驗。實驗中分類器分別采用最近鄰法 （Nearest Neighbour Method）和重構誤差法（RMEM），識別結果如表1所示。作為比較，表1除了PCA外，還給出了其他常用的分類器的識別結果及計算耗時。

表1 常用方法相比較Tab.1 Contrast with traditional methods

從實驗結果可以看出，無論是PCA還是2DPCA，采用最近鄰法 （1-nearest neighbor）識別效果要優(yōu)于重構誤差法（Rmem），但重構誤差法的計算時間要明顯少于最近鄰法，而且2DPCA-Rmem耗時是所有分類器中最少的。

2DPCA優(yōu)于PCA的原因，主要有兩條：1）2DPCA的圖像協(xié)方差矩陣比較小，所以計算精度要高于PCA；2）重構原始樣本時所用的參數(shù)比PCA要少很多。

在和未作“骨架提取”與“膨脹”預處理的字符識別的對比實驗中發(fā)現(xiàn)，通過圖像預處理對字符筆畫粗細進行規(guī)范后，對各字符的識別率平均提高了大約2個百分點。

總體而言，在表1所示的識別方法中，2DPCA的識別率并不是最高的，這是因為2DPCA是基于統(tǒng)計規(guī)律，采用的是單一分類器，要想進一步提高識別精度，就必須利用字符的結構特征來構造分類器，并將兩類分類器結合起來進行識別。不過就計算速度而言，2DPCA具有明顯的優(yōu)勢，比較適用于某些實時性要求較高的場合。

5 結 論

文中提出了一種基于2DPCA的手寫字符識別方法：針對手寫字符書寫隨意，字符筆畫形態(tài)結構不穩(wěn)定的特點，提出首先采用數(shù)學形態(tài)學方法對字符筆畫的粗細特征進行規(guī)范，保證了字符筆畫粗細的一致性，同時也使字符部分細節(jié)的一致性得到改善；在通過圖像預處理得到相對穩(wěn)定的模式后，利用2DPCA抽取字符特征，在相應基向量張成的特征空間里對字符的重建模型進行估計，并利用重建誤差及最近鄰法對字符進行識別。從實驗結果看，該方法在準確率和計算耗時方面有明顯的提高。從理論上講，訓練集的規(guī)模越大越好，但從實驗中發(fā)現(xiàn)訓練集規(guī)模達到一定程度時，本算法的識別率已很高且穩(wěn)定，初步觀察發(fā)現(xiàn)它所要求的訓練集規(guī)模比其他方法相對要小，這樣就會節(jié)省不少訓練時間。在進一步的研究中將考慮結合其它字符形態(tài)矯正預處理方法，使字符模式更加穩(wěn)定，以進一步提高字符識別率。

[1]YousefAO，CherietM.Databasesforrecognitionof handwritten arabic cheques[J].Pattern Recognition，2003（36）:111-121.

[2]Juan A，Vidal E.On the use of Bernoulli mixture models for text classification[J].Pattern Recognition，2002，35 （12）:2705-2710.

[3]Hu J，Yan H.Structural primitive extraction and coding for handwritten numeralrecognition[J].Pattern Recognition，1998，31（5）:493-509.

[4]Hsu Chih-wei，Chang Chih-chung.A practicalguide to support vector classification [EB/OL]（2010-04-15）.http://www.csie.ntu.edu.tw/～cjlin/.

[5]LeCun Y，Jackel L.Learning algorithms for handwritten digitalrecognition [J].Int’L Conf1 ArtificialNeural Networks1 Paris.AI Computer Press，1995（1）:53-60.

[6]Seong-Whan L.Multilayer cluster neural network for totally unconstrained handwritten numeral recognition[J].Neural Networks，1995，8（5）:783-792.

[7]DONG Jian-xiong，Krzy’zakb A，Suen C Y.Local learning framework for handwritten character recognition [J].Engineering Applications of Artificial Intelligence，2002，15（2）:151-159.

[8]ZHANG Bai-ling，F(xiàn)U Min-yue，YAN Hong.Handwritten digit recognition by adaptive-subspace self-organizing map[J].IEEE Trans Neural Network，1999，10（4）:589-603.

[9]Teow L N，Loe K F.Robustvision-basedfeatures and classificationschemes for off-linehandwritten digit recognition[J].Electronic Design Engineering，2002，35（11）:2355-2364.