一種分類器級聯的手寫相似漢字識別方法

姚 超,盧朝陽,李 靜,姜 維,范志輝

(1.西安電子科技大學通信工程學院,陜西西安 710071; 2.西安電子科技大學綜合業務網理論及關鍵技術國家重點實驗室,陜西西安 710071)

一種分類器級聯的手寫相似漢字識別方法

姚 超1,2,盧朝陽1,2,李 靜1,2,姜 維1,2,范志輝1,2

(1.西安電子科技大學通信工程學院,陜西西安 710071; 2.西安電子科技大學綜合業務網理論及關鍵技術國家重點實驗室,陜西西安 710071)

針對手寫相似漢字識別問題,提出一種新的基于分類器的方法來更全面地利用原始特征中的判別信息.新方法與現有的對相似漢字提取額外特征的方法不同,其在得到特征向量之后,首先利用修正的二次判別函數進行分類,然后用支持向量機對分類結果中的相似漢字的上述特征向量進行再一次的分類,得到最終的識別結果.利用分類混淆矩陣自動得到相似漢字集合,并提出了一種新型的存儲結構用于快速查找支持向量機的訓練字典.在ETL9B手寫漢字數據庫上的實驗表明,所提出的方法可得到相對于提取額外特征方法更好的識別結果,以此證明了原始特征中存在對于相似字的判別信息,提出的基于分類器的方法可更好地利用這些判別信息.

相似漢字識別;手寫漢字識別;修正的二次判別函數;支撐向量機;分類器

文字識別作為模式識別的重要領域,一直得到學者們的廣泛關注,其中手寫漢字識別由于類別數多、個人書寫習慣差異較大等因素,成為文字識別中最困難的領域之一.從20世紀70年代開始,圖像預處理、特征提取以及分類器等技術被越來越多地應用于手寫漢字識別,使其得到了巨大的發展.然而,對于無約束的手寫漢字識別仍然有很大的進步空間[1].

手寫漢字識別的主要難點在于,大量相似漢字的存在以及不規則的書寫變形等,對一些差別極其細微的相似漢字,如“干”和“于”、“汗”和“訐”等,在書寫不規范時,更加難以辨別,因此近年來對于相似字判別成為手寫漢字識別的熱點之一.早期的研究集中在分類器方面,文獻[2]用支持向量機(Support Vector Machine, SVM)對3組相似漢字進行了識別.文獻[3]用小波對相似漢字提取特征,并研究了3種多值SVM結構對相似漢字分類結果的影響.文獻[4]則對相似漢字利用了統計和神經網絡相結合的方法.這幾種方法雖然利用不同的分類器對相似漢字進行識別,但都是對相似漢字提取了特征,并沒有在整個漢字集對如何識別相似漢字進行研究.對于整個漢字集,文獻[5]指出在手寫漢字識別的過程中,由于一般都用線性判別分析(Linear Discriminant Analysis,LDA)[6]對特征進行降維以便于后續的處理,但是當LDA在降維后的維度遠遠小于類別數時,將使原空間中距離較近的類別投影得更緊密,從而使距離較近的類別,即相似漢字,更加難以判別.針對這個問題,文獻[5]對于相似漢字,提出了用LDA對每對相似漢字提取額外的判別特征,并用加權的歐式距離或馬氏距離進行最終的判別.文獻[7]提出了用LDA判別向量來定位相似漢字的鑒別區域,并從這些鑒別區域提取額外的特征以便相似漢字的判別.文獻[8]針對相似漢字,提出了用2DLDA進行手寫漢字特征優化.文獻[9]用LDA為多個相似漢字提取額外的特征,并用級聯的修正的二次判別函數(Modified Quadratic Discriminant Function,MQDF)對多個相似漢字進行判斷.

上述的方法都對相似漢字提取了額外的判別特征,因此都有效地提升了手寫漢字識別系統的整體性能,但是,對于原始的特征向量中判別信息是否足夠判別這些相似漢字,上述方法并沒有研究.針對這個問題,筆者提出了用分類器級聯的方法進一步利用原始特征中的判別信息來識別相似漢字.對于待識別樣本,經過預處理、特征提取、降維等步驟得到特征向量后,首先用MQDF對特征向量進行第1次判別,若第1次的判別結果有可能為相似字時,則用SVM對此特征向量進行再一次的判別,以得到最終識別結果.筆者采用混淆矩陣自動得到相似漢字集合,并提出了一種存儲結構以便于為相似漢字快速查找和讀取SVM的訓練字典.在ETL9B手寫數據庫上的對比實驗結果顯示,所提出方法獲得與提取額外特征方法相近或者更好的結果,這表明在原始特征中包含有對于相似漢字的判別信息,而通過所提出的分類器級聯方法可以更好地利用特征中的判別信息.

1 漢字識別

1.1 系統流程

文中所提出的分類器級聯的相似漢字識別系統流程如圖1所示.在預處理過程中,輸入的漢字圖像被歸一化到一個統一的尺寸上,并通過濾波器去除圖像上的噪聲.特征提取過程之后,從漢字圖像中提取的特征向量x=(x1,x2,…,xd)T,被投影到一個低維度的子空間:z=WTx=(z1,z2,…,zl)T,l＜d,其中,W是由子空間的各投影方向組成的轉化矩陣.降維后的特征向量z被送入分類器,通過分類器MQDF[10]得到的相似度來得到判別結果.此時,當MQDF的判別結果為潛在的相似字時,則該特征向量被送入SVM[11]做進一步的判斷,以得到最終的識別結果;反之,MQDF的判別結果即為最終的識別結果.

圖1 系統流程圖

從圖1中可以看出,與近年來出現的相似漢字識別方法[5,7-9]相比,文中所提出的方法沒有為相似字提取額外的特征,而是用了兩級分類器來對其進行判別,這樣做的目的在于,探索已有的特征中是否含有足夠的判別信息以判斷相似漢字.采用MQDF和SVM來構造兩層分類器,是因為MQDF在大類別的問題上有著理論上的優勢,只需要對每個類別建立模型即可,所以,首先用MQDF在整個漢字集合對待識別樣本進行分類;而SVM對小類別小樣本問題解決得很出色,則SVM被用來處理相似字問題.下面簡單介紹MQDF和SVM的相關知識.

1.2 MQDF

MQDF是二次判別函數(Quadratic Discriminant Function,QDF)在小樣本下的改進方法,具體形式如下:

其中,d是輸入向量的維數,μi代表類ωi的均值,pij和λj則是第i類的協方差矩陣Σi的第j個特征向量以及對應的特征值.MQDF假設每個類別的先驗概率都服從高斯分布,在此假設條件下,尋找x∈ωk= arg min g(x,ωi),MQDF可得貝葉斯最優分類結果.為克服樣本量不足帶來的協方差矩陣Σi估計誤差問題,MQDF用h2替代Σi中較小的特征值,當特征值λi從大到小排列時,k為截斷參數,代表了第k個特征值后的所有特征值均被h2替代.在式(1)中,當每一類hi的都取相同值時,稱這種形式的h與類別無關;反之,則稱h與類別相關.在實際應用中,選擇參數h與類別無關的這種形式下時,MQDF的表現往往優于與類別相關的形式[11],所以文中采用與類別無關的形式.

MQDF由于結構簡單、便于多類問題的分類、易于實現且具有很高的準確性等特點,被廣泛應用于手寫文字識別中[5,7,9].

1.3 SVM

SVM是文獻[11]在一種最小化結構風險準則下提出的一種基于統計學習理論的分類器,其主要思想是最優化線性可分情況下的分類平面.對兩類情況,若給定l個訓練數據(xi,yi),i=1,2,…,l,其中,xi∈Rn,yi∈{-1,1},對于待分類樣本x,SVM確定其所屬類別的表達式為

其中,αi為每個樣本所對應的權值,b為偏置,xi·x為向量內積運算.實際中大部分樣本權值均為0,這些權值不為0的樣本稱為支撐向量.對于線性不可分的情況,SVM引入核函數來處理,其具體形式為

其中,K(xi·x)為向量內積的核函數映射.常用的核函數有線性核、多項式核、RBF核和Sigmoid核等.訓練支撐向量機即在給定訓練數據的情況下,通過下面的公式得到αi的過程:

其中,e∈Rl,其元素均為1;Q為半正定的核矩陣,其元素Qij=yiyjK(xi,xj),i,j=1,2,…,l.

2 相似漢字識別

2.1 相似漢字集合和判斷

2.1.1 相似漢字集合

對于類別數巨大的漢字識別,人工確定相似漢字基本是不可行的,因為:漢字類別數巨大,人工確定相似漢字需要消耗大量的人力物力;人工與機器判斷相似漢字的準則不同,這將導致人工判斷出的相似漢字集合與機器判斷出的集合有所不同,所以文中利用混淆矩陣來確定相似漢字.混淆矩陣是從訓練集上得到的識別結果確定的,對于C*C的混淆矩陣可表示為

其中,pij代表在特定的分類器下將第j類錯分為第i類的概率.pij的值越大,第j類為第i類的相似漢字的概率越大.當pij大于一個給定的閾值τ時,則第j類為第i類的相似漢字.在實際中,用pij=ni→jni來計算,其中,ni→j代表在給定分類器下將第i類錯分為第j類的樣本個數,ni代表第i類所有樣本的個數.

從上面的定義可知,混淆矩陣M的確定是與分類器相關的,不同的分類器會產生不同的相似字集合.與人工選取相似字集合相比,這種做法的針對性更強.為了使混淆矩陣M的結果更可靠,訓練數據應該與分類數據為不同集合.在文中實驗中,將訓練集隨機分成兩份,其中,3/4的數據用來訓練分類器,剩余的1/4數據用來估計混淆矩陣.實際中,如果數據量較小,則用交叉驗證的方法來提升混淆矩陣的可靠性,文中采用了4組交叉驗證來確定最終的混淆矩陣.在混淆矩陣估計完成后,所有的訓練數據被重新用來訓練分類器.

2.1.2 相似漢字判斷

得到相似字集合后,在識別過程中,用如下的方法判斷當前輸入的漢字圖像是否需要進行相似漢字判斷:

2.2 存儲結構

針對上述MQDF和SVM相似漢字判斷的框架,構造了如圖2所示的快速高效判斷相似漢字的存儲結構.

圖2 存儲結構

圖2中,index是一個長度為漢字類別數的數組,confusion pairs是一個長度為相似字個數的數組,SVM models是一個長度為相似字個數的SVM訓練字典.index中的元素index[i]是第i個類別所對應的相似字在confusion pairs數組中的位置以及第i個類別所對應的相似字的個數,index中的元素NIL代表其對應的類別沒有相似字存在.假定系統中相似字的個數為num,第i個類別所對應的相似字在confusion pairs數組中的位置為index[i]/num,對應的相似字的個數為index[i]%num,其中,/代表取模運算,%代表求余運算.confusion pairs中的元素代表與當前類別構成相似字的對應的類別,SVM models中的結構體元素為對應confusion pairs中兩類相似字的SVM字典.

3 實驗結果

為驗證文中方法的有效性,在手寫漢字數據庫ETL9B上進行了實驗.ETL9B字符數據庫由日本電子工業發展協會、大學和研究機構聯合協助的電工技術實驗室收集.ETL9B數據庫包含了73類日文片假名和2 963類日文漢字,共3 036類文字,每個類別包含200個樣本,其中每個樣本為分辨率64×63的二值圖片.與常用的測試方法相同,文中用200個樣本中的前20個和后20個樣本進行測試,其余的160個樣本進行訓練.文中實驗軟件環境為Visual Studio 2010,硬件環境為Intel i5 3.2 GHz處理器,內存為8 GB.

在預處理中的歸一化操作采用了基于線密度的非線性歸一化方法[12],將漢字圖像歸一化到64×64,然后在歸一化后的圖像上提取八方向的梯度特征[13],得到每個梯度圖像后,經過高斯模糊再進行64個點的采樣,最終得到一個512維的特征向量.用LDA來尋找投影子空間,并設定子空間的維數為180,最終投影后得到180維的特征被送入分類器進行識別.

實驗比較了作為基準的MQDF[10]、基于LDA的合成距離算法[5](LDA compound)、相似模式判別分析(SPDA)[9]以及文中的基于MQDF和SVM級聯(MQDF+SVM)的方法,其中,LDA compound和SPDA是兩種對相似漢字提取額外特征的方法.對于LDA compound,采用了其中效果較好的馬氏距離來判別相似字,為得到LDA compound最優的分類效果,以0.1為步長遍歷了[0,1]內的馬氏距離與MQDF距離的加權系數.對于SPDA,采用了其提出的第2種級聯策略.為了比較各個算法的性能,LDA compound、SPDA以及MQDF+SVM都采用了節2.2中所描述的方法來確定相似字集合以及在分類過程中確定相似字,其中,SVM采用的是臺灣大學公開的LIBSVM[14].

選擇相似漢字的策略與分類器相關,對于不同截斷參數的MQDF,對應著不同的相似漢字集合,表1給出了在不同截斷參數以及不同的閾值下相似字集合的規模.在實驗過程中,對于不同的截斷參數k,選擇了不同的閾值τ,使相似字規模處于100～500之間.這樣做的目的在于,減少訓練時間,因為對用于比較的各算法都采用了同樣的相似字集合以及判別策略,所以對各算法的性能沒有影響.圖3給出了部分相似漢字的示例.

表1 不同參數下相似字集合規模

圖3 相似漢字示例

表2給出了對于不同的截斷參數,對以上提到的各算法在ETL9B上的表現.從表2的實驗結果可以看出,相比于作為基準的MQDF,對相似字進行了進一步處理的方法,在識別的準確率方面均有提升,文中提出的SVM+MQDF方法的效果略優于其他提取額外特征的方法.這說明原始特征中包含有判別相似漢字的信息,文中所提出的分類器級聯策略可以更好地利用這些判別信息.表2同時給出了幾種方法的平均處理時間.從平均識別消耗時間可以看出,LDA compound消耗的額外時間最少,相較于MQDF增加了0.001 52 ms,SPDA與文中提出的MQDF+SVM方法消耗額外時間大體相當,分別為0.010 04 ms和0.009 34 ms,相對于主體的消耗時間,對相似漢字的處理所消耗的時間幾乎可忽略.

進一步分析表2中的實驗結果.MQDF是一種基于高斯分布模型的分類器,其分類僅從概率出發,并沒有考慮各個類別在空間中的相對關系,在LDA降維后對于空間位置較為接近的相似漢字必然難以判別.LDA compound方法在原空間中為相似漢字提取了額外的特征,然后采用馬氏距離和MQDF距離的加權來判斷相似漢字,從而提升了相似漢字的識別效果.但是馬氏距離本質上依然是高斯分布模型的分類器,所以仍然有提高的空間.SPDA方法則是對于相似漢字提取額外特征后,用MQDF的級聯來得到最終識別結果,由于相對LDA compound方法,SPDA提取的特征維度更高,而MQDF分類器較馬氏距離能更好地判別相似模式,所以取得了較LDA compound更好的結果.文中提出的MQDF+SVM方法,其中,SVM考慮如何最好判別兩類并獲得最佳推廣能力這樣的特性,彌補了基于概率模型MQDF的不足,從而對相似字進行了較好的判斷.相對其他為相似漢字提取額外特征的方法,文中所提出的MQDF+SVM是利用不同分類器的特性以更全面地利用已有特征中的判別信息,該方法對采用方向線素[13]、四方向梯度特征[13]等也具有適應性.

表2 不同截斷參數下的識別結果

4 結束語

針對手寫漢字識別中相似字識別問題,提出一種分類器級聯的方法,以更全面地利用原始特征中的判別信息.與現有的為相似漢字提取額外特征的方法不同,該方法在得到特征向量之后,首先利用修正的二次判別函數進行分類,然后用支持向量機對分類結果中的相似漢字的上述特征向量進行再一次的分類,得到最終的識別結果.通過實驗結果可以看出,原始特征中存在對于相似字的判別信息,提出的分類器級聯方法可更好地利用這些判別信息來判別相似漢字.

[1]Liu C L,Yin F,Wang D H,et al.Online and Offline Handwritten Chinese Character Recognition:Benchmarking on New Databases[J].Pattern Recognition,2013,46(1):155-162.

[2]田盛豐,黃厚寬.基于支持向量機的手寫體相似字識別[J].中文信息學報,2000,14(3):37-41. Tian Shengfeng,Huang Houkuan.Recognition of Similar Chinese Handwriting by Support Vector Machine[J].Journal of Chinese Information Processing,2000,14(3):37-41.

[3]封筠,王彥芳,楊揚,等.SVM多值分類器在脫機手寫體相似漢字識別中的應用[J].計算機工程與應用,2004,40 (27):200-202. Feng Jun,Wang Yanfang,Yang Yang,et al.Recognition of Off-line Similar Handwritten Chinese Characters Based on Multi-class Support Vector Machines Classifier[J].Computer Engineering and Applications,2004,40(27):200-202.

[4]張德喜,馬少平.基于統計與神經元方法相結合的手寫體相似字識別[J].中文信息學報,1999,13(3):33-39. Zhang Dexi,Ma Shaoping.Handwritten Similar Chinese Characters Recognition Based on Combining Statistics with Neural Networks Method[J].Journal of Chinese Information Processing,1999,13(3):33-39.

[5]Gao T F,Liu C L.High Accuracy Handwritten Chinese Character Recognition Using LDA-based Compound Distances [J].Pattern Recognition,2008,41(11):3442-3451.

[6]Izenman A J.Linear Discriminant Analysis[M].New York:Springer,2008:237-280.

[7]Leung K C,Leung C H.Recognition of Handwritten Chinese Characters by Critical Region Analysis[J].Pattern Recognition,2010,43(3):949-961.

[8]高學,溫文歡,金連文.用于相似字識別的手寫漢字特征優化方法[J].哈爾濱工程大學學報,2012,33(7):887-893. Gao Xue,Wen Wenhuan,Jin Lianwen.A Feature Optimization Method for Similar Handwritten Chinese Character Recognition[J].Journal of Harbin Engineering University,2012,33(7):887-893.

[9]Wang Y,Liu C,Ding X.Similar Pattern Discriminant Analysis for Improving Chinese Character Recognition Accuracy [C]//Proceedings of 12th International Conference on Analysis and Recognition.Washington:IEEE Computer Society, 2013:1056-1060.

[10]Kimura F,Takashina K,Tsuruoka S,et al.Modified Quadratic Discriminant Functions and the Application to Chinese Character Recognition[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1987(1):149-153.

[11]Vapnik V.The Nature of Statistical Learning Theory[M].New York:Springer-Verlag,2000.

[12]Liu C L,Sako H,Fujisawa H.Handwritten Chinese Character Recognition:Alternatives to Nonlinear Normalization [C]//Proceedings of 7th International Conference on Document Analysis and Recognition.Los Alamitos:IEEE Computer Society,2003:524-528.

[13]Liu C L.Handwritten Chinese Character Recognition:Effects of Shape Normalization and Feature Extraction[C]// Lecture Notes in Computed Science:4768.Heidelberg:Springer Verlag,2008:104-128.

[14]Chang C C,Lin C J.LIBSVM:a Library for Support Vector Machines[J].ACM Transactions on Intelligent Systems and Technology,2011,2(3):1-27.

(編輯:齊淑娟)

Hybrid classifier based method for similar handwritten Chinese character recognition

YAO Chao1,2,LU Zhaoyang1,2,LI Jing1,2,JIANG Wei1,2,FAN Zhihui1,2
(1.School of Telecommunication Engineering,Xidian Univ.,Xi’an 710071,China; 2.State Key Lab.of Integrated Service Networks,Xidian Univ.,Xi’an 710071,China)

To solve the similar handwritten character recognition problem,a novel scheme is proposed to make better use of the feature's discriminative information.Different from the methods for extracting the extra feature for the similar characters,the Modified Quadratic Discriminant Function(MQDF)is first adopted to classify the feature,then the Support Vector Machine(SVM)is used to discriminate the similar characters without the extra feature.To collect the subset of similar characters,the confusion matrix is employed.A new structure for storing the dictionary of the SVM is also proposed for quickly searching. Experimental results on ETL9B show the superior performance of the proposed scheme to the methods for extracting the extra feature,which proves that the feature contains discriminative information for the similar characters and that the proposed scheme can utilize this information very effectively.

similar character recognition;handwritten Chinese character recognition;modified quadratic discriminant function(MQDF);support vector machine(SVM);classifier

TP391.43

A

1001-2400(2015)05-0026-07

2014-05-26< class="emphasis_bold">網絡出版時間:

時間:2014-12-23

國家自然科學基金資助項目(60872141);中央高校基本科研業務費專項資金資助項目(K50510010007);華為高校創新研究計劃資助項目(IRP-2012-03-06)

姚 超(1985-),男,西安電子科技大學博士研究生,E-mail:yaochao@mail.xidian.edu.cn.

http://www.cnki.net/kcms/detail/61.1076.TN.20141223.0946.005.html

10.3969/j.issn.1001-2400.2015.05.005