郭春妮，高瑜翔，黃坤超

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

0 引言

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

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

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

1 2DDPCA理論

1.1 算法原理

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

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

通過投影到X上的樣本的整體散度，來確定最佳的投影向量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ōu)的投影向量，即是由GT的前d個最大的特征值對應(yīng)的特征向量組成的。

(6)

(7)

1.2 算法流程

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

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

(8)

(9)

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

2 識別過程

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

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

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

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

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

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

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

3 實驗仿真與分析

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

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

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

圖1 2DDPCA算法識別率隨2個維度的變化曲線

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

表1 4種算法的識別效果對比

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

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

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

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

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

4 結(jié)束語

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