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

王軍平，趙振華

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

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

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

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

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

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

1 二維主元分析

1.1 原理及算法

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

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

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

所以有

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

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

則判據(jù)（2）可表示為

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

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

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

1.2 特征提取

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

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

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

1.3 基于2DPCA的圖像重構(gòu)

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

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

因?yàn)?X1，…，Xd是正交的，由（8）可以得到樣本 A的重構(gòu)圖像：

2 字符識(shí)別方法

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

2.1 最鄰近法

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

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

2.2 重構(gòu)i誤差法

隨后分別計(jì)算出測(cè)試樣本與每類近似圖像的誤差，

則C應(yīng)屬于誤差最小的那類字符，即

3 圖像預(yù)處理

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

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

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

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

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

一個(gè)字符的“骨架”是描述其幾何及拓?fù)湫再|(zhì)的重要特征。本文通過對(duì)經(jīng)過二值化的字符進(jìn)行細(xì)化，提取其骨架特征，然后用包括原點(diǎn)的2×2結(jié)構(gòu)元素對(duì)骨架圖像進(jìn)行一次膨脹。包括原點(diǎn)的2×2結(jié)構(gòu)元素對(duì)圖像的膨脹，相當(dāng)于沿著字符骨架在骨架像素的3鄰域分別“加粗”了一個(gè)像素，這就嚴(yán)格保證了字符所有筆畫均為2個(gè)像素寬度。

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

圖1 字符圖像預(yù)處理Fig.1 Image preprocession of digits

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

本實(shí)驗(yàn)采用的數(shù)據(jù)庫(kù)是MNIST數(shù)據(jù)庫(kù)[4]，此數(shù)據(jù)庫(kù)中含有60 000個(gè)訓(xùn)練樣本和10 000個(gè)測(cè)試樣本，每個(gè)樣本都是28×28個(gè)像素的圖像加上一個(gè)樣本標(biāo)示組成。

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 論

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

[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.