基于并行組合分類器的脫機(jī)手寫體數(shù)字識別

楚浩宇，高 萌，劉永生

(東北農(nóng)業(yè)大學(xué) 電氣與信息學(xué)院，黑龍江 哈爾濱 150030)

0 引 言

手寫體數(shù)字識別是光學(xué)字符識別的一個重要分支，分為聯(lián)機(jī)手寫體數(shù)字識別和脫機(jī)手寫體數(shù)字識別。在聯(lián)機(jī)手寫體數(shù)字識別中，計算機(jī)可以通過與之相連的輸入設(shè)備得到關(guān)于筆尖運動軌跡和速度的有效信息，所以識別相對較易[1]。由于數(shù)字圖像的數(shù)據(jù)量龐大且書寫風(fēng)格的迥異等干擾因素對識別會產(chǎn)生很大的影響，因此脫機(jī)手寫體數(shù)字識別難度較大，但其應(yīng)用領(lǐng)域更加寬泛。因此這是一項意義重大的研究課題。

鑒于傳統(tǒng)的單一分類器對數(shù)字之間差異的敏感性不同，許多學(xué)者開始研究組合分類器所產(chǎn)生的效果[2]。文獻(xiàn)[3]使用四種特征和三種傳統(tǒng)分類器構(gòu)造了九種不同的分類器進(jìn)行組合。文獻(xiàn)[4]構(gòu)造了兩級的組合分類器，第一級是最小距離分類器，第二級由三個反向傳播網(wǎng)絡(luò)并聯(lián)而成。文獻(xiàn)[5]提出了一種基于量子神經(jīng)網(wǎng)絡(luò)的二級識別系統(tǒng)。這些方法雖然在一定程度上提高了識別率與可靠性，但分類器的組合結(jié)構(gòu)卻十分復(fù)雜，因此識別速度隨之下降。

文中提出使用一種特征、三種分類器、并行結(jié)構(gòu)組織的組合分類器，與傳統(tǒng)方法相比，在提高識別率與可靠性的同時,極大地減少了算法的時間復(fù)雜度。

1 手寫體數(shù)字識別的基本原理

手寫體數(shù)字識別一般包括圖像預(yù)處理、特征提取、分類識別等模塊[6]，其結(jié)構(gòu)如圖1所示。

圖1 數(shù)字識別的步驟

1.1 圖像的預(yù)處理

預(yù)處理的主要目的是去除字符圖像中的噪聲，并采用灰度化方法處理讀入的圖像，圖像中的每個像素就對應(yīng)唯一一個灰度值,得到規(guī)范化的點陣，為識別做好準(zhǔn)備[7]。

1.2 特征提取

數(shù)字圖像用元素為灰度值的矩陣表示，直接用維數(shù)很高的矩陣進(jìn)行計算無論是時間復(fù)雜度還是空間復(fù)雜度都很大，因此需要進(jìn)行特征提取。一般對預(yù)處理后的圖像進(jìn)行統(tǒng)計特征提取，常用的有主成分分析、獨立成分分析和Fisher線性鑒別分析[8]。

1.3 識別方法

分類器主要分為基于概率分布的分類器，例如邏輯回歸分類器[9]；基于距離的分類器，例如最近鄰分類器[10]; 人工神經(jīng)網(wǎng)絡(luò)分類器，例如BP神經(jīng)網(wǎng)絡(luò)分類器；支持向量機(jī)分類器[11]。 近年來，也有學(xué)者提出應(yīng)用分類識別的伯努利隱馬爾可夫模型與基于活動圖的半監(jiān)督學(xué)習(xí)模型[12-13]。

2 并行結(jié)構(gòu)組合分類器的設(shè)計

為了能夠從不同的角度觀察不同數(shù)字之間變化的規(guī)律，綜合考慮各種單一分類器的優(yōu)缺點，同時不能由于結(jié)構(gòu)太過復(fù)雜化而導(dǎo)致訓(xùn)練分類器的時間和綜合決策時間過長。對此，文中采用K-近鄰算法、廣義回歸神經(jīng)網(wǎng)絡(luò)及支持向量機(jī)，提出一種基于改進(jìn)的投票機(jī)制的并行組合分類器，實現(xiàn)脫機(jī)手寫體數(shù)字的快速、高效識別。

2.1 單一分類器的分類原理

2.1.1 K-近鄰(KNN)分類器

2.1.2 廣義回歸神經(jīng)網(wǎng)絡(luò)(GRNN)分類器

廣義回歸神經(jīng)網(wǎng)絡(luò)是徑向基神經(jīng)網(wǎng)絡(luò)的一種[14]。假設(shè)隨機(jī)變量x和隨機(jī)變量y的聯(lián)合概率密函數(shù)為f(x,y)。設(shè)X是隨機(jī)變量x的測量值，則y在給定X下的條件均值為：

(1)

(2)

其中，n為樣本觀測值的個數(shù)；p為隨機(jī)變量x的維數(shù)；σ為高斯函數(shù)的寬度系數(shù)。

(3)

2.1.3 支持向量機(jī)(SVM)分類器

支持向量機(jī)是一種建立在統(tǒng)計學(xué)習(xí)理論的VC維理論和結(jié)構(gòu)風(fēng)險最小原理基礎(chǔ)上的模式識別方法。支持向量機(jī)的主要思想是通過某種事先選擇的非線性映射將輸入向量x映射到高維特征空間，在這個空間中構(gòu)造最優(yōu)分類超平面[11]。

對于給定的訓(xùn)練集(x(i),y(i)),為了尋找最優(yōu)分類超平面，支持向量機(jī)需要求解以下二次規(guī)劃問題:

0≤αi≤C,i=1,2,…,m

(4)

其中,m為訓(xùn)練樣本數(shù);αi為拉格朗日乘子；C為懲罰系數(shù)；(x(i),x(j))為核函數(shù)。

給定測試數(shù)據(jù)x,通過式(5)的值來確定標(biāo)簽y。

(5)

2.2 組合分類器的工作原理及流程

2.2.1 改進(jìn)的投票機(jī)制

分類器識別狀況的權(quán)值矩陣為：

(6)

其中，wij為第i+1個分類器在識別數(shù)字j時設(shè)定的權(quán)值。

權(quán)值矩陣中每個元素的取值為：

(7)

其中，ω為該分類器的預(yù)設(shè)定權(quán)值；c為該分類器的識別結(jié)果。

在識別數(shù)字時的判定依據(jù)為：

(8)

給定拒識閾值t,若滿足Rj

2.2.2 工作流程

三個分類器，即KNN分類器、GRNN分類器、SVM分類器分別簡稱為C1、C2、C3。

(1)C1、C2、C3分別在訓(xùn)練集中進(jìn)行學(xué)習(xí)并進(jìn)行參數(shù)尋優(yōu)，得出各分類器的參數(shù)；

(2)將各分類器的識別結(jié)果與測試集中的結(jié)果進(jìn)行比對，根據(jù)正確率排出各分類器的可信度的排名；

(3)收集C1、C2、C3識別數(shù)字的結(jié)果，設(shè)定矩陣中各元素的取值范圍；

(9)

(10)

(11)

(4)列出三行十列的混淆矩陣;

(12)

(5)根據(jù)式(13)計算Rj的值；

(13)

(6)根據(jù)各分類器的可靠性預(yù)設(shè)拒識閾值t=2.5，若滿足Rj<2.5拒絕識別，否則輸出識別的數(shù)字。

3 實 驗

3.1 數(shù)據(jù)來源

文中應(yīng)用的實驗數(shù)據(jù)來源于MNIST數(shù)據(jù)庫，這是一個廣泛使用于各種圖像處理系統(tǒng)和機(jī)器學(xué)習(xí)領(lǐng)域的大型手寫體數(shù)字?jǐn)?shù)據(jù)庫。該數(shù)據(jù)庫包含了6萬組訓(xùn)練圖片和1萬組測試圖片，其中每張圖片已經(jīng)經(jīng)過預(yù)處理壓縮至784(28*28)像素[15]。特征矩陣即是由灰度值作為元素的28*28維矩陣。圖2是MNIST數(shù)據(jù)庫中的部分訓(xùn)練數(shù)據(jù)。

圖2 MNIST訓(xùn)練集的部分?jǐn)?shù)據(jù)

3.2 性能指標(biāo)

分類器的水平由性能指標(biāo)來評價，主要的性能指標(biāo)如下：

(1)識別率(recognition rate)。

Recognition Rate=

100%

(14)

(2)誤識率(false accept rate)。

False Accept Rate=

(15)

(3)可靠性(reliability)。

Reliability=

(16)

(4)拒識率(rejection rate)。

多數(shù)情況下，在輸入待測樣本之后，分類器會給出對應(yīng)數(shù)字的分類結(jié)果。但是對于某些特定領(lǐng)域，分類結(jié)果發(fā)生錯誤可能會帶來極其嚴(yán)重的后果,因此需要對沒有把握的樣本拒絕識別,由此降低誤識率，提高可靠性。

RejectionRate=

100%

(17)

3.3 實驗結(jié)果及分析

評價一個分類器性能的優(yōu)劣主要看其是否具有低誤識率、低拒識率和高識別率、高可靠性。實驗結(jié)果如表1所示。

表1 分類器性能對比實驗結(jié)果 %

比較表1中單一分類器和組合分類器的結(jié)果，單一分類器的拒識率這一指標(biāo)全部為0。組合分類器由于有些數(shù)字樣本因手寫不謹(jǐn)慎而與別的數(shù)字產(chǎn)生混淆的原因，才拒絕識別了這一小部分樣本，所以組合分類器存在單一分類器所沒有的“噪音”過濾功能。從表1中可以看出，并行組合分類器的誤識率要比單一分類器低0.45%～2.38%，而且可靠性要高于單一分類器0.5%～2.43%，所以其魯棒性優(yōu)于單一分類器。

文中提出的并行組合分類器在識別率、拒識率、識別算法的時間復(fù)雜度上均優(yōu)于文獻(xiàn)[3-5]中所采用的組合分類器。由于文中選取了識別率較高的單一分類器、改進(jìn)了傳統(tǒng)的投票機(jī)制，這使得只有極少測試樣本會因同時在各種分類器中識別不佳導(dǎo)致權(quán)值之和達(dá)不到預(yù)設(shè)的閾值而被拒識，因此組合分類器具有高識別率、低拒識率。

文獻(xiàn)[3]需要事先訓(xùn)練九種分類器再進(jìn)行組合判斷；文獻(xiàn)[4]中組合分類器第二級采用了三個并聯(lián)BP神經(jīng)網(wǎng)絡(luò)，雖然BP神經(jīng)網(wǎng)絡(luò)在數(shù)學(xué)上已經(jīng)被證明具有實現(xiàn)任何復(fù)雜非線性映射的功能，但收斂速度十分緩慢；文獻(xiàn)[5]使用的QNNs多級分類器包含十四個子網(wǎng)絡(luò)；而文中采用的三個單一分類器均具有較快的訓(xùn)練速度且并行組合分類器的結(jié)構(gòu)簡單，因此在識別算法的時間復(fù)雜度上小于以上文獻(xiàn)的同時，又取得了高識別率、低拒識率。

并行組合分類器在誤識率和可靠性方面高于文獻(xiàn)[4-5]，較之文獻(xiàn)[3]略低?？紤]到文獻(xiàn)[3]中九個組合分類器極大地增加了訓(xùn)練時間和綜合決策時間，而且其較高的拒識率也在一定程度上減少了誤識率、增加了可靠性，而文中提出的并行組合分類器在犧牲較少時間，拒識較少樣本的情況下與其只有不到0.1%的差距，所以并行組合分類器在總體性能上要優(yōu)于其他組合分類器。

4 結(jié)束語

提出了一種并行結(jié)構(gòu)的組合分類器，通過改進(jìn)的投票機(jī)制得出最終的結(jié)果，實驗結(jié)果表明，對單一分類器進(jìn)行組合，在保證了低誤識率、低拒識率、高識別率、高可靠性的前提下，利用簡易結(jié)構(gòu)即可實現(xiàn)脫機(jī)手寫體數(shù)字的快速、高效識別。組合分類器的魯棒性比單一分類器的要強，而且組合分類器有著較強的靈活性和可拓展性，找到更好的組織結(jié)構(gòu)以及判斷機(jī)制將是今后研究的重點。手寫體數(shù)字識別是字符識別中的一個研究方向，提出的組合分類器起到了拋磚引玉的作用，絕不只是應(yīng)用于數(shù)字識別，稍加改變，便可應(yīng)用于其他字符識別。

[1] KHERALLAH M,HADDAD L,ALIMI A M,et al.On-line handwritten digit recognition based on trajectory and velocity modeling[J].Pattern Recognition Letters,2008,29(5):580-594.

[2] 柳回春,馬樹元,吳平東,等.手寫體數(shù)字識別技術(shù)的研究[J].計算機(jī)工程,2003,29(4):24-25.

[3] 胡鐘山,婁 震,楊靜宇,等.基于多分類器組合的手寫體數(shù)字識別[J].計算機(jī)學(xué)報,1999,22(4):369-374.

[4] 傅德勝,謝忠紅,蘇 堅.基于組合分類器的自由手寫體數(shù)字識別方法[J].計算機(jī)工程與設(shè)計,2004,25(10):1713-1715.

[5] 吳茹石,彭 力.基于量子神經(jīng)網(wǎng)絡(luò)的手寫體數(shù)字識別方法研究[J].計算機(jī)工程與設(shè)計,2007,28(18):4462-4465.

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

[7] 張 猛,余仲秋,姚紹文.手寫體數(shù)字識別中圖像預(yù)處理的研究[J].微計算機(jī)信息,2006,22(6-1):256-258.

[8] 楊 健,楊靜宇,葉 暉.Fisher線性鑒別分析的理論研究及其應(yīng)用[J].自動化學(xué)報,2003,29(4):481-493.

[9] BISHOP C M.Pattern recognition and machine learning[M].New York:Springer-Verlag,2006:205-206.

[10] 劉家峰,趙 巍,朱海龍,等.模式識別[M].哈爾濱:哈爾濱工業(yè)大學(xué)出版社,2014:15-17.

[11] VAPNIK V N.The nature of statistical learning theory[M].New York:Springer-Verlag,2000:133-141.

[12] GIMERNEZ A,ANDRES-FERRER J,JUAN A.Discriminative Bernoulli HMMs for isolated handwritten word[J].Pattern Recognition Letters,2014,35:157-168.

[13] CECOTTI H.Active graph based semi-supervised learning using image matching:application to handwritten digit recognition[J].Pattern Recognition Letters,2016,73:76-82.

[14] SPECHT D F.A general regression neural network[J].IEEE Transactions on Neural Networks,1991,2(6):568-576.

[15] LECUN Y,BOTTOU L,BENGIO Y,et al.Gradient-based learning applied to document recognition[J].Proceedings of the IEEE,1998,86(11):2278-2324.