楚浩宇，高 萌，劉永生

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

0 引 言

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

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

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

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

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

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

1.1 圖像的預處理

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

1.2 特征提取

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

1.3 識別方法

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

2 并行結構組合分類器的設計

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

2.1 單一分類器的分類原理

2.1.1 K-近鄰(KNN)分類器

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

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

(1)

(2)

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

(3)

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

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

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

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

(4)

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

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

(5)

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

2.2.1 改進的投票機制

分類器識別狀況的權值矩陣為：

(6)

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

權值矩陣中每個元素的取值為：

(7)

其中，ω為該分類器的預設定權值；c為該分類器的識別結果。

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

(8)

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

2.2.2 工作流程

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

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

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

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

(9)

(10)

(11)

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

(12)

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

(13)

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

3 實 驗

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

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

圖2 MNIST訓練集的部分數(shù)據(jù)

3.2 性能指標

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

(1)識別率(recognition rate)。

Recognition Rate=

100%

(14)

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

False Accept Rate=

(15)

(3)可靠性(reliability)。

Reliability=

(16)

(4)拒識率(rejection rate)。

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

RejectionRate=

100%

(17)

3.3 實驗結果及分析

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

表1 分類器性能對比實驗結果 %

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

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

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

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

4 結束語

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

[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ù)字識別技術的研究[J].計算機工程,2003,29(4):24-25.

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

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

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

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

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

[8] 楊 健,楊靜宇,葉 暉.Fisher線性鑒別分析的理論研究及其應用[J].自動化學報,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è)大學出版社,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.