基于二維雙向PCA的手寫數(shù)字識(shí)別算法研究

郭春妮，高瑜翔，黃坤超

(1.成都信息工程大學(xué) 通信工程學(xué)院，四川 成都 610225；2.中國(guó)西南電子技術(shù)研究所，四川 成都 610036)

0 引言

離線手寫數(shù)字識(shí)別是模式識(shí)別應(yīng)用中的重要問(wèn)題之一[1]，它是在沒(méi)有人工交互的情況下從0～9識(shí)別和分類手寫數(shù)字的方法。近年來(lái)，已經(jīng)有很多學(xué)者提出了不同的識(shí)別方法來(lái)解決識(shí)別率和識(shí)別速度的問(wèn)題。數(shù)字識(shí)別主要分為2步：① 特征提取[2]；② 分類識(shí)別。其中，特征提取在數(shù)字識(shí)別系統(tǒng)中有著舉足輕重的地位。主分量分析(PCA)作為一種十分有效的方法，在特征提取中發(fā)揮著重大的作用。

傳統(tǒng)的KNN算法識(shí)別率和識(shí)別速度均不高；學(xué)者胡君萍提出的PCA結(jié)合KNN的識(shí)別算法[3]，其識(shí)別率和識(shí)別速度均有提高，但二者相互矛盾，且需要將二維矩陣轉(zhuǎn)換為一維向量，不能精確計(jì)算協(xié)方差[4]；針對(duì)一維上PCA算法的不足，學(xué)者王軍平提出了2DPCA[5]的特征提取，該方法不需要進(jìn)行二維到一維的轉(zhuǎn)換，而是直接計(jì)算圖像樣本矩陣的協(xié)方差，有效地解決了PCA算法帶來(lái)的問(wèn)題，其識(shí)別速度確有改善，但識(shí)別率仍有待提高。

2DPCA的特征提取中，僅對(duì)樣本的行進(jìn)行了降維，也就是提取的特征矩陣(p×n)行的維度p要小于原矩陣(m×n)行的維度m[6]，但是該特征矩陣還是較大，使得KNN算法中歐式距離的計(jì)算量也較大，為了減少歐式距離的計(jì)算量[7]，提出用更小的矩陣來(lái)代替樣本的特征，因此，本文對(duì)2DPCA算法進(jìn)行了改進(jìn)，提出了二維雙向主分量分析(2DDPCA)算法，并采用MINIST手寫數(shù)據(jù)集[8]，選取了0～9各100張圖像作為訓(xùn)練樣本，各50張作為測(cè)試樣本，訓(xùn)練樣本和測(cè)試樣本彼此獨(dú)立，沒(méi)有交集，對(duì)所提出的算法進(jìn)行了測(cè)試仿真。

1 2DDPCA理論

1.1 算法原理

假設(shè)X是一個(gè)n維的單位列向量，A表示要處理的m×n的樣本矩陣，通過(guò)Y1=AX的線性變換[9]將A投影到X上，得到Y(jié)1，再將Y1通過(guò)Y=Y1Z的線性變換投影到Z上，得到的Y稱為圖像A的特征圖像[10]。

下面以如何確定最佳的投影向量X為例，闡述尋找最佳投影向量[11]的原理：

通過(guò)投影到X上的樣本的整體散度，來(lái)確定最佳的投影向量X，樣本的總體散度[12]為：

J(X)=tr(SX)，

(1)

式中，SX表示樣本的投影特征向量構(gòu)成的協(xié)方差矩陣[13]，表示為：

SX=E(Y1-EY1)(Y1-EY1)T=E[AX-E(AX)][AX-E(AX)]T=E[(A-EA)X][(A-EA)X]T=XT[E(A-EA)T(A-EA)]X。

(2)

因此，

J(X)=XT[E(A-EA)T(A-EA)]X。

(3)

定義矩陣GT為圖像的散度矩陣：

GT=E(A-EA)T(A-EA)。

(4)

可以得到：

J(X)=XTGTX。

(5)

尋找一組最優(yōu)的正交投影向量：X1，X2,…，Xd，使得J(X)最大化。經(jīng)驗(yàn)證，這組最優(yōu)的投影向量，即是由GT的前d個(gè)最大的特征值對(duì)應(yīng)的特征向量組成的。

(6)

(7)

1.2 算法流程

① 通過(guò)式(6)列出樣本A的散度矩陣GT，計(jì)算其特征值及特征向量，選出前p(p

② 將Y1作為第二次特征提取的樣本，令Y1=Ok∈Rm×p,計(jì)算Y1也就是Ok的散度矩陣G：

(8)

(9)

通過(guò)散度矩陣計(jì)算其特征值及特征向量，選出其q(q

2 識(shí)別過(guò)程

本實(shí)驗(yàn)主要對(duì)手寫數(shù)字識(shí)別系統(tǒng)進(jìn)行了設(shè)計(jì)分析，采用2DDPCA特征提取和KNN分類算法相結(jié)合的方法進(jìn)行識(shí)別，同時(shí)對(duì)比了3種特征提取方法(PCA，2DPCA，2DDPCA)在識(shí)別中的效果。本實(shí)驗(yàn)在MATLAB平臺(tái)下進(jìn)行，具體實(shí)現(xiàn)流程如下：

(1)實(shí)驗(yàn)準(zhǔn)備：選取MINIST數(shù)據(jù)庫(kù)中的1 500張圖像進(jìn)行編號(hào)和分類，新建2個(gè)文件夾，分別為訓(xùn)練集和測(cè)試集。其中，訓(xùn)練集包含0～9共十類樣本，每一類樣本組成一個(gè)文件夾單獨(dú)存放，且每類中包含100張樣本圖像；測(cè)試集也同樣操作，每類中包含50張樣本圖像。

(2)樣本預(yù)處理：由于MINIST數(shù)據(jù)庫(kù)的圖像是統(tǒng)一大小的，因此不需要對(duì)樣本圖像的大小進(jìn)行處理。只需要將樣本圖像轉(zhuǎn)化二值圖像[14]，即針對(duì)每一個(gè)像素點(diǎn)，將圖像處理成只用0和1表示的矩陣[15]。

(3)特征提?。悍謩e使用PCA，2DPCA，2DDPCA三種算法，通過(guò)訓(xùn)練樣本[16]，求取特征矩陣X。

將訓(xùn)練樣本組成的矩陣train轉(zhuǎn)化為一維向量train_data，求train_data協(xié)方差的特征值及對(duì)應(yīng)的特征向量，取前dim個(gè)最大的特征值對(duì)應(yīng)的特征向量組成特征矩陣X。將訓(xùn)練樣本train_data投影到X上，得到訓(xùn)練的特征圖像train_Y，再將某一張測(cè)試樣本圖像轉(zhuǎn)換為一維向量test_data，以同樣的方式將test_data投影到X上，得到測(cè)試的特征圖像test_Y。

按照2.2小節(jié)所述的算法流程進(jìn)行兩次特征提取，得到行和列都進(jìn)行降維的特征圖像。

(4)分類識(shí)別：運(yùn)用KNN算法[17]，計(jì)算train_Y和test_Y之間的歐式距離[18]，將距離從小到大排序，并保存對(duì)應(yīng)的編號(hào)，選取其中K個(gè)最小的距離，即測(cè)試對(duì)象的近鄰，尋找每個(gè)距離對(duì)應(yīng)的訓(xùn)練樣本圖像，記錄每個(gè)圖像對(duì)應(yīng)的編號(hào)，根據(jù)這K個(gè)編號(hào)所屬的類別，取其中占數(shù)最多的類別作為識(shí)別結(jié)果。

3 實(shí)驗(yàn)仿真與分析

本實(shí)驗(yàn)采用了MINIST數(shù)據(jù)庫(kù)中的1 500個(gè)樣本，其中訓(xùn)練樣本1 000個(gè)，測(cè)試樣本500個(gè)。訓(xùn)練樣本和測(cè)試樣本各10類，分別是0～9的樣本，樣本為28×28像素大小的圖像。通過(guò)特征提取和KNN算法分類識(shí)別，在MATLAB平臺(tái)上實(shí)現(xiàn)仿真，對(duì)仿真結(jié)果進(jìn)行如下分析：

使用2DDPCA進(jìn)行特征提取，然后使用KNN算法進(jìn)行數(shù)字分類識(shí)別。按照需求從命令行窗口輸入KNN算法中的參數(shù)K，以及2DDPCA算法中矩陣行和列分別需要降低的維度dim1，dim2。遍歷所有的測(cè)試樣本，每一次循環(huán)都會(huì)顯示識(shí)別結(jié)果，待所有樣本都被識(shí)別完后，還會(huì)顯示識(shí)別成功和失敗的樣本個(gè)數(shù)，同時(shí)顯示識(shí)別率。

由于在選定K值時(shí)，該算法的識(shí)別率隨dim1，dim2變化的數(shù)據(jù)量太大，這里將其繪制成如圖1所示的曲線圖，可以看出該算法的識(shí)別率和dim1，dim2的選取息息相關(guān)，dim1達(dá)到7時(shí)，識(shí)別率隨dim2的波動(dòng)趨于平穩(wěn)，當(dāng)dim2達(dá)到4時(shí)，識(shí)別率隨dim1的波動(dòng)也趨于平穩(wěn)，因此選取適當(dāng)?shù)膁im1和dim2的值即可，其對(duì)應(yīng)的主分量矩陣幾乎已經(jīng)能夠代替整個(gè)圖像的特征，因此不論dim1，dim2如何變化，其識(shí)別率不會(huì)有很大的波動(dòng)。

圖1 2DDPCA算法識(shí)別率隨2個(gè)維度的變化曲線

將該算法和其他算法進(jìn)行對(duì)比，通過(guò)大量的仿真，得到相同條件下幾種不同算法的識(shí)別率以及所用時(shí)長(zhǎng)，具體數(shù)據(jù)如表1所示。

表1 4種算法的識(shí)別效果對(duì)比

算法類型K的取值345KNN識(shí)別率/%所用時(shí)長(zhǎng)/s86.035.5286.227.7285.227.86PCA+KNN識(shí)別率/%所用時(shí)長(zhǎng)/s87.010.6886.410.7287.010.912DPCA+KNN識(shí)別率/%所用時(shí)長(zhǎng)/s88.410.3288.610.3387.610.212DDPCA+KNN識(shí)別率/%所用時(shí)長(zhǎng)/s89.410.3190.410.1390.210.19

根據(jù)上表，可以得出結(jié)論：使用PCA及KNN的聯(lián)合識(shí)別算法時(shí)，選取一定的dim值，其識(shí)別率比單獨(dú)使用KNN算法的識(shí)別率要高，且識(shí)別速度更快；當(dāng)使用2DPCA及KNN的聯(lián)合算法，其識(shí)別率比使用PCA算法和單獨(dú)使用KNN算法都要高，而其識(shí)別速度與使用PCA算法相差不大；當(dāng)使用2DDPCA及KNN的聯(lián)合算法，選取合適的dim1和dim2，其識(shí)別率比前3種算法都高，而識(shí)別速度和2DPCA幾乎沒(méi)有差別。在PCA算法中，需要將二維矩陣變換成一維向量，如果要達(dá)到更高的識(shí)別率，則主分量的維度會(huì)相應(yīng)增大，此時(shí)的識(shí)別速度會(huì)減慢，因此，對(duì)于PCA算法來(lái)說(shuō)，要想得到較高的識(shí)別率，需要犧牲識(shí)別速度。2DDPCA相對(duì)于2DPCA算法來(lái)說(shuō)，多一次特征提取的過(guò)程，因此在特征提取過(guò)程中耗費(fèi)的時(shí)間會(huì)相對(duì)多一些，但在識(shí)別過(guò)程中，由于2DDPCA的特征矩陣比2DPCA的特征矩陣小，在識(shí)別過(guò)程中，歐式距離的計(jì)算量也就相對(duì)較小，所以這2種算法的識(shí)別速度幾乎沒(méi)有差別。

在相同的維度下，分別對(duì)3種算法進(jìn)行仿真，多次仿真后得到的識(shí)別率變化曲線如圖2所示。

圖2 3種不同PCA算法在相同dim下的識(shí)別率

從實(shí)驗(yàn)數(shù)據(jù)分析折線圖可以看出，在相同的維度下，2DDPCA及KNN聯(lián)合的識(shí)別算法在不同K值下識(shí)別的效果最好。2DDPCA相比于2DPCA，多進(jìn)行了一次特征提取，因此其提取的特征更能準(zhǔn)確表征原圖像，從而使得識(shí)別效果更佳。

4 結(jié)束語(yǔ)

本文提出了基于2DDPCA結(jié)合KNN的手寫數(shù)字識(shí)別算法，并分析仿真比較了與其他3種算法在識(shí)別速率與識(shí)別率方面的優(yōu)劣性。從理論上來(lái)說(shuō)，2DDPCA算法不僅是直接對(duì)矩陣進(jìn)行處理，還對(duì)行和列都進(jìn)行了降維，實(shí)現(xiàn)了2次特征提取的同時(shí)，更進(jìn)一步降低了特征矩陣的大小。因此，圖像的特征信息更加準(zhǔn)確，從而能夠在不犧牲識(shí)別速度的同時(shí)，識(shí)別率得到一定提高。