摘 要 在模式识别领域, 投票策略是非常有效的, 而且已被成功应用到人脸检测、识别等领域. 然而, 在手写汉字识别(Handwritten Chi-nese character recognition, HCCR)中, 由于类别集很大、训练样本少等特点, 现有的很多分类器集成方法方法都很难直接应用于此领域. 本文提出一种自产生式投票的方法, 该方法通过事先学习得到的参数集产生一个测试集合, 然后用一个分类器去识别测试集合中的每个样本, 得到属于各个类别的概率, 最后通过加权投票得到识别结果. 实验结果表明,本文提出的方法是实用和有效的.
关键词 手写汉字识别, 自产生投票, 改进二次判别函数, 线密度归一化
Handwritten Chinese CharacterRecognition Based on Self-generationVoting
Abstract Voting strategy is very useful in pattern recognitionand it has been successfully applied in many applications likeface detection and recognition. However, these state-of-the-artmethods are infeasible or unsuitable for handwritten Chinesecharacter recognition (HCCR) because of the problem0s charac-teristics. In this paper, a self-generation voting based methodis proposed for further improving the recognition rate in hand-written Chinese character recognition. This method learns a setof parameters ¯rst for generating a set of samples from the testsample, and then classify these generated samples using a base-line classi¯er. At last, it gives the recognition result by voting.Experimental results on two databases show that the proposedmethod is e®ective and useful in handwritten Chinese characterrecognition systems.
Key words Handwritten Chinese character recognition(HCCR), self-generation voting, modi¯ed quadratic discriminantfunction (MQDF), line density equalization
　　.离线手写汉字识别问题(Handwritten Chinese charac-ter recognition, HCCR) 已经被许多研究人员进行了大量且深入的研究, 并且取得了很多成果[1¡10]. 例如: 1) 在归一化阶段, 基于线密度均衡的非线性归一化方法[1¡2]的提出; 2) 特征提取阶段, 笔画方向特征[3¡5]的提出;3) 特征降维阶段, 线性判别分析(Linear discriminationanalysis, LDA) 的应用; 4) 分类阶段, 改进二次判别函数(Modi¯ed quadratic discriminant function, MQDF)[3]的提出. 本文的基准分类器用到了这几个技术. 由于类别集很大、训练样本少等特性, 很多方法像ANN (Arti¯eial neu-ral network), SVM (Support vector machine), Bagging 或Boosting都很难直接应用到手写汉字识别中. 然而, 这些方法中的一些好的思想对于解决这个问题是非常有启发的. 本文就利用了投票的思想来进一步提升识别性能. 本文提出的自产生式投票方法, 首先根据预先学习得到的一个参数集产生一个虚拟测试集, 然后利用基准分类器识别测试集合中的每个样本, 得到属于各个类别的概率, 最后通过加权投票得到识别结果. 在两个数据集上的实验结果表明, 该方法具有较好的效果. 而且, 由于并行处理技术的快速发展, 该方法具有的并行性将会受到广泛关注.
　　本文的安排如下: 首先, 第1节介绍了自产生投票的框架, 然后, 在第2节介绍了自产生方法和参数学习方法. 第3节给出了实验结果. 第4节是总结.
　　1 自产生投票
　　Bagging或Boosting是两种非常有效的提升分类性能的投票方法. Bagging 是Breiman[11]提出的, 给定一个大小为n的训练集D, Bagging 方法通过从D中有放回的均匀采样得到m个新的大小为np > n的训练样本集Di. 在每个训练集Di 上可以得到一个分类模型mi. 最终通过投票策略给出分类结果. Boosting 则注重分类错误的样本, 将分类错误的训练样本的权重提高, 并依据修改后的样本权重来生成新的训练样本空间, 并用来训练下一个个体分类器. 每个弱分类器的权重是其在训练集上的正确率. 这两个方法的共同点都是通过学习多个弱分类器ht(x)和对应的权重®(Bagging的权重都设为1). 然后通过投票给出最终分类结果.H(x) =T Xt=1®tht(x) (1)给定一个待测试的样本, 每个弱分类器给出一个预测结果,最终的识别结果通过加权投票决定. 本文将这种投票方式称为多分类器投票. 图1是多分类器投票策略的示例图.图1 多分类器投票策略Fig. 1 The multi-classi¯er voting strategy4期 邵允学等: 基于自产生投票的手写汉字识别 451在手写汉字识别中, 由于训练样本少、类别集很大等特点, 类似Bagging或Boosting的多分类器投票策略很难应用到这个问题中. 怎样才能将投票策略应用到手写汉字识别中？假设现在只有一个分类器h(x), 对于一个待测试样本x, 如果能从这个测试样本产生出一个测试样本集fx1;¢ ¢ ¢ ; xTg, 那么可以用分类器h(x) 来分类每一个产生的样本, 最终的分类结果就可以由投票产生. 本文将这种使用一个分类器, 分类每个由原样本产生的样本, 最终通过这些分类结果投票产生最终结果的策略叫做自产生投票. 自产生投票需要根据测试样本产生一个测试集fx1;¢ ¢ ¢ ; xTg并且测试集中每个测试样本的投票权重f®1;¢ ¢ ¢ ; ®Tg也需要事先学习得到.H(x) =T Xt=1®th(xt) (2)图2是自产生投票策略的示例图.图2 自产生投票策略Fig. 2 The self-generation voting strategy
　　2 基于自产生投票的手写汉字识别
　　为了使用自产生投票策略. 首先, 需要确定从一个样本产生一个样本集的方法. 产生的样本需要与原样本属于同一类并且不能太相似; 其次, 需要确定一个能够选择小且完备的产生样本子集和对应权重的参数学习方法. 学习得到的子集冗余度小、互补性强, 这样可以使得投票速度更快, 效果更好; 最后, 采用投票策略给出识别结果.
　　2.1 自产生方法
　　在手写汉字识别中, 文献[12] 提出了一种从一个训练样本产生大量虚拟训练样本的自产生模型. 他们的实验结果表明, 产生的虚拟样本能够有效地解决训练样本不足的问题.本文采用此方法来从测试样本中产生虚拟的测试样本, 这个产生方法能够保证所产生的样本属于同一个类别, 而且可以通过调节参数, 控制产生样本与原始样本的差距.假设f(x; y) 是原始字符图像, g(u; v) 是产生的字符图像. 从原始图像f(x; y) 到产生图像g(u; v) 的映射函数为u=u(x; y) =wn(d1; b1(x)) +k1b2(y) +c1v=v(x; y) =wn(d2; b2(y)) +k2b1(x) +c2(3)其中, k1 和k2 控制修剪坡度, d1 和d2 控制局部缩放的程度,c1 和c2 是为了将映射的中心调节到图像的中心, b1 和b2 将原始坐标线性映射到区间[0;1],wn是非线性扭曲函数, 用来对局部图像进行扭曲变形.实验中, 所有的参数设置都和文献[12] 相同: k1 和k2 分别从区间[¡0:17;0:17]和[¡0:20;0:20]中随机选取, d1 6= 0和d2 6= 0,从区间[¡1:6;1:6]中随机选取, 使用下面两个扭曲函数w1 和w2, 使用w1 和w2 的概率为0.8和0.2,可以产生更多形状的虚拟样本.w1(d; t) =1¡e¡dt1¡e¡d(4)w2(d; t) =(0:5w1(d;2t); 0·t·0:50:5 + 0:5w1(¡d;2(t¡0:5)); 0:5< t·1(5)图3 给出了根据不同d1(d2 = 0:01; k1 = 0; k2 =0; wn =w1) 所产生样本的示例, 中间矩形框内的字符是原始图像. 从左上到右下, d1 的值依次是¡1.6»1.6,间隔0.1. 可以看出jd1j 越大, 字符的形变就越大, 太极端的参数值产生的样本将不利于投票识别, 根据这个准则确定自产生模型中参数范围, 从图3还可以看出, 某个参数的微小变化,对产生样本的形状影响不大.图3 根据不同d1 产生的样本.Fig. 3 Generated samples with di®erentd1图4给出了一些产生样本的例子, 所用参数都是在各个范围内随机选择的. 第一列是原始图像, 其他列是根据不同参数产生的样本. 可以看出产生的样本和原样本属于同一类且形状不同.图4 产生样本实例Fig. 4 Some generated samples
　　2.2 参数学习方法根据第2.1 节描述的产生模型, 一个参数集Pifd1; d2; k1; k2; wng对应一个产生样本gi(u; v).Pi !gi(u; v) (6)不 同 的 参 数 集 集 合 所 对 应 的 投 票 结 果会 有 所 不 同, 本 文 随 机 产 生100 个 参 数 集SpfP1fd1; d12; k1; k12; w1ng; ¢ ¢ ¢ ; P100fd1001; d1002; k1001; k1002,w100ngg用于训练分类器和参数学习.参数学习的目标是从这100个随机产生的集合中, 学习一个子集PfP1;¢ ¢ ¢ ; PTg和对应的投票权重, 使得在验证集452 自 动 化 学 报 39卷上分类结果最好. 算法1给出了本文采用的学习算法, 采用贪心法从候选集合Sp 和S®中依次选取Pi 和®i, S®是投票权重的候选集合.算法1中, T 是要选择的参数集的个数, ;为空集合,CT0f('01);¢ ¢ ¢ ;('0n)g是验证集, '0i 是从样本fi 上提取的特征, 局部变量best p是第t 次循环中得到的最优参数集,best p= ©意味着没有参数集对已学习的集合在验证集上有帮助.算法1.参数集和投票权重学习算法输入. P; ®初始化. P=;; ® =;; best acc= 0for t= 1 :Tdobest p=;;Forp2Sp do1)使用参数集p从样本fi 产生gi;2)从产生的样本gi 上提取特征'ti;3)将特征'ti 放进集合CTt¡1, 得到集合CTt,CTt =f('01;¢ ¢ ¢ ; 't1);¢ ¢ ¢ ;('0n;¢ ¢ ¢ ; 'tn)g;for ®2S®do1)令®t =®, 得到集合®f®1;¢ ¢ ¢ ; ®tg;2)计算在验证集上当前的识别率cur acc, 分类器为H(fj) =h('0j) +Pti=1®th('ij);3)if cur acc > bestaccthenbest acc=cur acc; bestp=p; best®=®;endendendif best p=;thenBreakelse1)使用参数集best p提取特征'ti 且放进集合CTt¡1, 得到集合CTt =f('01;¢ ¢ ¢ ; 't1);¢ ¢ ¢ ;('0n;¢ ¢ ¢ ; 'tn)g;2)令®t =best ®得到集合®f®1;¢ ¢ ¢ ; ®tg;3)令Pt =best p得到集合PfP1;¢ ¢ ¢Ptg;endendend3 实验分析为了验证本文方法的有效性, 在两个常用的数据集CA-SIA和CASIA-HWDB1.1[13]上做了充分的实验. CASIA数据集由中国科学院自动化研究所收集, 包含常用的3 755个汉字, 每个汉字有300个样本. CASIA-HWDB1.1 数据集由中国科学院自动化研究所模式识别实验室收集, 包含3 755个汉字及171个字符, 本文实验只用了3 755个汉字. 在这两个数据集上都是将前250个作为训练数据, 后50个作为测试数据. 图5给出了两个数据集上的样本实例, 前三行是CASIA中的样本, 后三行是CASIA-HWDB1.1数据集上的样本.在参数学习时, 训练样本又被分为训练和验证两个部分,每类中前240个作为参数学习的训练集, 后10个作为验证集.权重的候选集为®f0:1;0:2;0:3;0:4;0:5;0:6;0:7;0:8;0:9;1g;权重的很小变化对投票结果的影响很小, 许多基于复合距离[14]的方法都采用类似的权重候选集.图5 两个数据集上的样本实例Fig. 5 Some samples in the two databases对于每个原始样本和产生的样本, 采用基于线密度均衡化[1]的归一化方法, 将其归一化到64£64, 然后在归一化的图像上, 提取512维的8方向梯度特征[5], 再用LDA将每个特征降到256 维. 实验中用到的分类器是MQDF2[3],MQDF2中主要的参数为使用的特征向量个数Nv. 在算法1的h(x) 分类器中, Nv 设置为50. 对于每个待测试样本x, 根据学习得到的参数PfP1;¢ ¢ ¢ ; PTg, 产生测试样本集fx1;¢ ¢ ¢ ; xTg. 首先用采用粗分类器和MQDF2分类原始样本x, 得到前10个候选, 然后根据x以及fx1;¢ ¢ ¢ ; xTg到候选类别的距离加权和最小的类别作为最终的分类结果.假设产生一个虚拟样本需要时间为T IMEn, 粗分类时间为T IMEc, 最终投票的时间为T IMEv, 则识别一个样本总共的时间为(T £T IMEn +T IMEc +T IMEv).而不采用本文方法需要的时间为(T IMEn+T IMEc). 在一台普配置为双核、4G 内存的PC机上, T IMEn 约为1.4 ms,T IMEc 约为4.8 ms,T IMEv 约为3.7 ms (10个候选且T= 20).可以看出, 最费时的是产生样本阶段, 虽然该方法非常适合并行处理, 但在以后的工作中, 还需要考虑怎样能够快速地产生一个测试样本集.首先, 只用原始的训练样本来训练分类器, 评价在测试集上的结果. 表1给出了不同Nv 对应的识别结果, 在两个数据集上, 最好的识别结果都是当Nv = 50时, 当Nv 变大时,识别率降低, 这是由于训练样本不够.表1 没有使用产生样本时的识别结果(%)Table 1 The recognition rates of the base-line classi¯erwithout using generated samples (%)NvCASIA CASIA-HWDB1.130 97.87 87.2450 97.97 87.4170 97.95 87.0790 97.90 87.07然后, 采用原始样本和产生的样本来训练分类器, 评价在测试集上的结果. 表2给出了不同Nv 对应的识别结果, 当Nv 变大时, 识别率增加, 这表明产生的虚拟样本能够有效缓解训练样本不足的问题.4期 邵允学等: 基于自产生投票的手写汉字识别 453表2 使用产生样本作为训练样本的识别结果(%)Table 2 The recognition rates of the base-line classi¯er usinggenerated samples for training (%)NvCASIA CASIA-HWDB1.130 97.75 87.0450 97.98 87.7470 98.07 88.1390 98.10 88.06最后, 评价本文方法在两个数据集上的性能. 表3和表4给出了不同T和Nv 对应的识别结果, T= 0意味着没有产生样本参与投票. 从表3和表4可以看出, 本文方法比原始不采用投票的方法要好, Nv 增加时, 识别率也增加, 这与表2一致.图6是Nv = 50时, 不同T时的识别率, 左图是CASIA上的结果, 右图是CASIA-HWDB1.1上的结果. 可以看出,当T增加到20左右时, 识别率的增加变得缓慢, 这说明不需要太多的虚拟样本参与投票, 就可以得到较好的结果.表3 本文方法在CASIA上的结果(%)Table 3 The recognition rates of the proposed method ondatabase CASIA (%)Nv T= 0 T= 5 T= 10 T= 15 T= 20 T= 2530 97.75 98.16 98.41 98.56 98.62 98.6450 97.98 98.28 98.48 98.62 98.67 98.6970 98.07 98.31 98.49 98.63 98.68 98.7090 98.10 98.27 98.48 98.61 98.65 98.66表4 本文方法在CASIA-HWDB1.1上的结果(%)Table 4 The recognition rates of the proposed method ondatabase CASIA-HWDB1.1 (%)Nv T= 0 T= 5 T= 10 T= 15 T= 20 T= 2530 87.04 88.47 89.68 90.24 90.38 90.5050 87.74 88.91 89.83 90.36 90.52 90.6570 88.13 88.89 89.83 90.40 90.51 90.5990 88.06 88.95 89.85 90.39 90.49 90.63图6 不同T(Nv= 50)对应的识别结果Fig. 6 The recognition rates with varyingT(Nv= 50) on thetwo databases
　　4 结论
　　本文提出了基于自产生投票的手写汉字识别方法. 该方法通过学习一组产生样本的参数集和对应的投票权重, 对测试样本进行自产生投票. 在两个常用的数据集上的测试结果表明, 该方法是有效的, 且仅需要少于20个样本的投票, 分类性能就可以得到很好的提升.
    References1 Yamada H, Yamamoto K, Saito T. A nonlinear normaliza-tion method for handprinted Kanji character recognition-line density equalization. Pattern Recognition, 1990, 23(9):1023¡10292 Tsukumo J, Tanaka H. Classi¯cation of handprinted Chi-nese characters using nonlinear normalization and corre-lation methods. In: Proceedings of the 9th InternationalConference Pattern Recognition. Rome, Italy: IEEE, 1988.168¡1713 Kimura F, Takashina K, Tsuruoka S, Miyake Y. Modi¯edquadratic discriminant functions and the application to Chi-nese character recognition. IEEE Transactions on PatternAnalysis and Machine Intelligence, 1987, 9(1): 149¡1534 Shi M, Fujisawa Y, Wakabayashi T, Kimura F. Handwrittennumeral recognition using gradient and curvature of grayscale image.Pattern Recognition, 2002, 35(10): 2051¡20595 Liu C L, Nakashima K, Sako H, Fujisawa H. Handwrit-ten digit recognition: investigation of normalization andfeature extraction techniques. Pattern Recognition, 2004,37(2): 265¡2796 Gao T F, Liu C L. High accuracy handwritten Chinesecharacter recognition using LDA-based compound distances.Pattern Recognition, 2008, 41(11): 3442¡34517 Liu C L. High accuracy handwritten Chinese characterrecognition using quadratic classi¯ers with discriminativefeature extraction. In: Proceedings of the 18th InternationalConference on Pattern Recognition. Washington DC: IEEE,2006. 942¡9458 Liu C L, Sako H, Fujisawa H. Handwritten Chinese char-acter recognition: alternatives to nonlinear normalization.In: Proceedings of the 7th International Conference on Doc-ument Analysis and Recognition. Edinburgh, UK: IEEE,2003. 524¡5289 Leung K C, Leung C H. Recognition of handwritten Chinesecharacters by critical region analysis. Pattern Recognition,2010,43(3); 949¡96110 Xu B, Huang K Z, Liu C L. Similar handwritten Chinesecharacters recognition by critical region selection based onaverage symmetric uncertainty. In: Proceedings of the 2010International Conference on Frontiers in Handwriting Recog-nition. Kolkata, India: IEEE, 2010. 527¡53211 Breiman L. Bagging predictors.Machine Learning, 1996,24(2): 123¡140