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

楚浩宇，高 萌，劉永生

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

0 引 言

手寫體數(shù)字識別是光學(xué)字符識別的一個重要分支，分為聯(lián)機手寫體數(shù)字識別和脫機手寫體數(shù)字識別。在聯(lián)機手寫體數(shù)字識別中，計算機可以通過與之相連的輸入設(shè)備得到關(guān)于筆尖運動軌跡和速度的有效信息，所以識別相對較易[1]。由于數(shù)字圖像的數(shù)據(jù)量龐大且書寫風(fēng)格的迥異等干擾因素對識別會產(chǎn)生很大的影響，因此脫機手寫體數(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ò)分類器；支持向量機分類器[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ìn)的投票機制的并行組合分類器，實現(xiàn)脫機手寫體數(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è)隨機變量x和隨機變量y的聯(lián)合概率密函數(shù)為f(x,y)。設(shè)X是隨機變量x的測量值，則y在給定X下的條件均值為：

(1)

(2)

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

(3)

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

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

對于給定的訓(xùn)練集(x(i),y(i)),為了尋找最優(yōu)分類超平面，支持向量機需要求解以下二次規(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)的投票機制

分類器識別狀況的權(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)和機器學(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)的投票機制，這使得只有極少測試樣本會因同時在各種分類器中識別不佳導(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)的投票機制得出最終的結(jié)果，實驗結(jié)果表明，對單一分類器進(jìn)行組合，在保證了低誤識率、低拒識率、高識別率、高可靠性的前提下，利用簡易結(jié)構(gòu)即可實現(xiàn)脫機手寫體數(shù)字的快速、高效識別。組合分類器的魯棒性比單一分類器的要強，而且組合分類器有著較強的靈活性和可拓展性，找到更好的組織結(jié)構(gòu)以及判斷機制將是今后研究的重點。手寫體數(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].計算機工程,2003,29(4):24-25.

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

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

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

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

[7] 張 猛,余仲秋,姚紹文.手寫體數(shù)字識別中圖像預(yù)處理的研究[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.