用于手写文字识别的MQDF替代参数选择方法_姚超

1、66华中科技大学学报5然科学版）第12卷第42卷笫12期2014 年 12J1Vol. 42 No. 12!>c.2014华中科技大学学报(自然科学版)J. Hunzhong Univ, of Sci. feeh. (Natural Science Edilion)1X)1： 10. 13215/j. hust. 111213用于手写文字识别的MQDF替代参数选择方法姚超卢期阳李静姜维(西安电子科技大学通信工程学院.陕西西安710071)摘要 针対修止二次判別臥数(MQDF的凸代參数的选择何题提出一种选择參数力的方法 ti先通过分析 h在MQDF中的作用将h对判别结枭的影响分为两类情况：

2、燃后对每类情况在训练集上统计办的取值分 布并分析如何选择力可获得戢优的分类结%最后用非参数方法得到这两种情况的概率分布从而得到/!的 最佳取值.在手得数字数据库MN1S1和手码汉字数据库ETL9B ±的实验结果表明了该方法在识别效率以 及时间效率方面的冇效性.关键词 手吗汉孑识别：手写数字识别：修止二次判別函数；参数选择；#参数方法中图分类号 TP391. 13 文献标志码 A 文章编号 1671-1512(201 1)12-0065-05Substitution coefficient selecting method of MQDFfor handwritten characte

3、r recognitionYao Chao Lu Zhaoyang Li J ing J iang Wei(School of relecomniunication Engineering. Xidian University* Xi*an 710071. China)Abstract A method for selecting the substitution coefficient h of modified quadratic discriminant function < MQDF) was proposed. Based on the theoretical analysis

4、* the impact of h to MQDF was dr vided into two groups. The distribution for each group was first learned from the training set and then the best choice of h l)ctwccn the tradc-off was given. The norrparamctric method was used to model the probability density of each distribution so that the best va

5、lue of h could be selected. The experimental results on the handwritten digital character dataset MN 1ST and handwritten Chinese character dataset ETL9B show the effectiveness of the proposed method both in accuracy and time consuming.Key words handwritten C'hinese character recognition； handwri

6、tten digital character recognition； modified quadratic discriminant function； coefficient selection； norrparametric method71994-2018 China Academic Journal Electronic Publishing House. All rights reserved, 66华中科技大学学报5然科学版）第12卷71994-2018 China Academic Journal Electronic Publishing House. All rights

7、reserved, 66华中科技大学学报5然科学版）第12卷收稿日期 2011-05-06.作者简介 姚 超(1985«) 男博士 研究生 E-mail: yaochaofe mail, xidian. edu. cn.基金项目 国家fl然科学曜金资助项Fl ( 60872141):中央岛校垂本科研业务费冬项蔽金资助项目(K50510010007);华为高校创新研究计划资助项目(1RP-2012-03-06).文字识别"是模式识别中的经典问题它对 于模式识别理论研究及苴实际应用都有着很直耍 的意义.对于手写体文字由于字形和个人W写习 惯的影响使得手写文字识另IJ成为模式识别

8、中最 具挑战性的任务之一.近年来支持向畐机 (SVM)、人丁神经网络以及各种基于统计的模式 识别方法都被应用到手写文字识别的研究之 中5.其中基于统计方法的修正二次判别式(MQDF) 简单有效、易于实现且具有很高的准 确性被广泛应用于手写文字识别中.对于与类别相关的替代参数山的选择问题. 文献6根据投影关系和最小化风险函数给出了 一种选取方法文献7给出了另-种与错误率相 关的优化方法但这两种方法针对的参数h都是 与类别相关的然而对于应用更广泛的与类别无 关的参数选择问题仍是靠交义验证的方法來实现而缺乏理论上的分析8 .针对这个问题.木研究 提出了 种新的与类别无关的参数力选择方法. 经过分析参

9、数h对于MQI）F判别结果的影响将 h的选择问题分为两类悄况：一类悄况须要选择 h人于一个确定的阈值才能保证样本分类的正 确性；另-类情况则须要选抒力小于-个确定的 阈值才可以保证样本被正确分类对于这两种情 况本研究在训练集上得到其各自的分布并分析 选择在这两类慨率相等的点时可保证获得彊优 的分类结果嚴后用非参数方法得到这两种情况 的槪率分布从而得到h的最佳取值.在手写数字 和手写汉字数据库上的实验结果证明了提出方法 的有效性.I 二次判别函数二次判别唄数（Q I）F）具冇如下的形式gqdf（K 妙）=（a -/i ） Z, l（.rIn | Z | =f J £）" 一

10、+丸讥 （1） 式中:d为输入向量的维数屮，和富,分别为S类 的均值向员和协方差矩阵；久和入,则为刀的第j 个特征向帚以及对应的特征值.QDF假设每个类 别的先验概率都服从高斯分布在此假设条件下, 寻找 rwt = arg min g诃<x»o>,） . QDF 可得贝叶 斯最优分类结果.QDF分类器所需的参数祁可从训练数据中 根据最大似然估计得到相比来说训练较为简单 直接并且准确性很高所以在实际中被广泛应 川.但是当输入的特征维数较高而训练数据不足 时会出现维度灾难9现象表现在QDF分类器 中即出现估计误差.从式（1）中可以看出:对于特 征值，同心的估计误差在特征值取值

11、较小时对结 果的影响远大于特征fft取值校人时的影响.针对 这个问题文献3提出了两种MQDF方法苴 形式分别如F：gl(T 仙)=2A In(入,十於)；>=1g2(x,a>.) =) | r fl |k(2)另(1 h;/A,)(*r /t, )> 7 2十 式中Sl（4 S）和/（片5）下而分别被称为 MQDF1和MQDF2.对于MQDF2半特征值人 从大到小排列时M为截断参数表示第k个待征 值后的所右待征值均被於替代.比较式（2）和式（3）可知：对MQDF1.毎个类 别的存储空间为dXd十2d个存储小位而对 MQDF2每个类别的存储空间为d X A十2d个存 储单位在计

12、算过程中，MQDF 1须要计算所有的 d个投影而MQDF2则只须要计算前"个投影 即可.虽然MQDF 1的性能稍优于MQDF2 10 但 由于MQDF2在存储空间和计算时间上所肯有的 优势使得其得到更广泛的应用因此本文只针对 MQDF2进行研究.为了方便起见，下文中分别川 MQDF 和替代 MQDF2 和 g2（zj在式（3）屮.当每一类的h.都取相同值时称 这种形式的人与类别无关反之则称力与类别相 关.与类别相关的参数人选择问题在文献6-7中 已右介绍.然而在实际应用屮选择参数厶与类别 无关这种形式时MQDF的表现往往优于与类别 相关的形式1 但对于这种悄况如何选取参数儿 却较少研

13、究只是从理论上判断人取值与相关. 取值越大时儿应取值越小具体如何取值没有 定论.冃前-般是通过实脸的方法确定力的取伉. 即遍历力以确定其最佳取值为了增加遍历方法 的稳定性也可用交乂验证的方法血选择h.所 以研究种与类别无关的参数选择方法具右 很高的理论价值和应用价值.由于截断参数k的 选取会影响分类器的时间效率和存储效率在应 用过稈中会根抿实际的需求来确定怡的取ffi因 此本文仅号虑在“给定的情况下如何选择t2与类别无关的参数方选择方法2. 1参数力对MQDF判别结果的影响为了分析参数在MQDF判别过程中所起的 作用式（3）被帝写为32=+hU,十£ II r p | 2 耳Cr p

14、jp,卜（4）(3)对于样本Q,叫）其所属类别由x 6 s = arg min g（x,<o.）得到.当3、=物时.该样本分类 正确反之则分类错误.所以对（rs ）定义小（文） 为样本到其真实类别的MQDF距离幻（工）为该 样本列苴他任类别的MQDF距离公式如下：71994-2018 China Academic Journal Electronic Publishing House. All rights reserved, 第12期姚超等：用TTi文7识别的MQDE 代参数选抒方法 67 入：gc3 = 2(十InG +C2/i2；(5)”3 =£"："

15、 +呵+ 君 | j- /r |2 2(工一丹)7丿：尊= K 十R,/h2.(6)根据式(5)和式(6)可知：当(C.-R, )(C2- K >) 20时,h的取值不会影响MQDF的判别结 果，所以应重点考虑(G & ) (C厂R2) <0时参 数厶对结果的影响.当样本.r判别正确时即当gc (才Vgr (才)时(1 ,(：2，RlR*和h有如下两种 关系：G 鼻 &，C? M &，/r M (G 乩)/(乩一G)；(7) G < R C2 > R> h2 > (C2 -R2)/(R, -G).如式(7)所示力的取值对MQDF的刿别

16、结 果的两种影响为:a.当GV&G>&时於的 取值须要大于个门限值儿心此时即可保证分 类有可能正确;b.当C,>R(.('2<K2时.於的取 值须要小于一个门限值h“此时即可保iiE分类 有可能正确.因此选择参数“时.须要在楼个数 据集上综合占虑九s和儿s这两类情况才能保证 得到较好的分类效果.2.2 参数方的选择方法对于参数h对MQQF的两种影响悄况本研 究在训练集上分别统计其分布然后根据分布情 况来确定参数力的最佳取值.2.2. 1九命和九和的统计方法假设已他任一类别。的均值向绪卩以及待 征值A,和特征向量p,八則根据下面的步骤来统 计帑个训练集上

17、的儿叭和九4步骤1对于样本(gs)根据式(5)和式 (6)确定QCi和Rf；步骤2根据式(7)确定当用MQDF分类该 样本正确时统计参数h对所右类别须要满足的 关系集合Hi.H*2.步骤 3 取 = inf Ht n Ha n 仃 H“ , /»Lx=sup H->nH,2n-nHr»步骤J , = i十1 币复步骤13直至遍历完 所有样本.在步骤3中如果nH*2n-nHx=0* 那么无论办如何取值.该样木$都分类不正确， 如果门丹2门门屮=(08.那么I,取任 何实数该样本都可以被正确分类.这两种情 况所得的 心.和 心不计入最终的统计.如果 H“n H'2

18、 CI仃H ' = (0匚)，那么此时得到的 心十入统计而心“则不考虑；同理如果Ha n H切n Hr = (r.,oo).那么此时仅将心列入 统计中.2. 2.2利用/心和心*分布的参数h选择方法 统计到心和心在训练集上的取值之 后如果取h=h0 那么对于hnM>hQ的样本可 保证直分类正确；同理“；“ V儿可保证其中另一 部分的样本被正确分类.用槪率来表达上述的描 述为 Pc ( X,) = j '人皿(.r) d.r 十 J * P z( r)山这 恰好辱价T贝«t斯最小错误概率丸的形式此B寸 最优的h应选择在几")=”5(於)处.2.2.3非参

19、数方法估计 g和心的分布由于“叭和h “的分布形式未対，因此采用非 参数方法的Parzen窗皿方法來估计其分布具 体方法为式中:以为核函数；九为平滑因子且匕=疋 将会影响/>-(» )的结果较大的九意昧着较大的 平滑度而较小的九则意味着较小的平滑度.本研究中固定核函数的形式为护(戶)= cxp( p 2)用 Parzen 窗的方法对 /imU4 和儿分别进行估计，图1是该方法在MNIST手写 数字数据库上取A = 5时估计的h叭和儿杠的分布3实验结果为了验证提岀的方法的有效性本研究在手71994-2018 China Academic Journal Electronic Pu

20、blishing House. All rights reserved, 68华中科技大学学报5然科学版)第12卷71994-2018 China Academic Journal Electronic Publishing House. All rights reserved, 68华中科技大学学报5然科学版)第12卷丐数字数据库MNIST和手丐汉字数据库 ETL9B上分别进行了实验比较常用的交乂验证 h的选择方法与本文方法的优劣.传统方法一般 在训练集上首先用一个较大的步K来确宦出最优 h的范围然后在这个范围内用另一个较小的步 氏來确定h的最终取值.本研究屮实验软件环境 为 Visual

21、Studio 2010.硬件环境为 Intel i5 3. 2 GHz处理器8 GB内存.3. 1用MNIST数据库的测试结果MNIST数据库包含09的7X 2 张手 写数字的图像数据苴中6X10*张图像作为训练 数据，采集自250个不同的节写者另外1 X 10* 张图像作为测试数据來I不同于训练数据的其 他W写者.MXIST数据库中的样本是28X28的 灰度图像由原始20X2()图像经过缩放抗锯齿等 操作得到图2(a)为MNIST数据库中部分样本.vTw44u4My44le移槽4w乙乙*SJZti'乙乙L'z乙z乙(a) MMST部分样本(b) ETL9B部分样本图2部分手丐

22、样本示盘图在实脸小将图像线件归化到20X20后提 取图像的八方向梯度特征川然后将图像分成 5 X 5的均匀网格统计每个网格中各梯度方向的 累计值作为待征这样每个图像可得到200维的 待征向量之后LDA方法Z被用于实验中之前 的200维的持征向就被降至9维然后降维后的 待征被用来计算各个类别的均值以及协方差矩 阵，协方并矩阵通过Karhuncn-Locve变换fn 得到MQDF分类器所需的特征值和待征向fi.为了证明所提方法的冇效性对于不同的截 断参数H本研究在训练集上计算出本文所提方 法所对应的人卄同时比较r在训练集上遍历得 到的最佳的htrn.表1中是不同的截断参数k下 所对应的hJi g以

23、及它们各口所对应的识别率« I MNIST数据库的实验结果沧冲和y.ra. n «1计算心呻消耗的平均时间为 1.451 s而计算儿»消耗的平均时间为100. 340 s可以看出本文所提出的方法节省r选择参数h 所消耗的时间.从实验结果可以看到：当”=16时本文所 提的方法在效果I：优于通过实脸方法确定h所取 得的识别率.当A = 78时本文方法所得到的结 果较通过实验确定的方法得到的结果差这是因 为此时人在总维度中的比例太大在实际情况中 一般不会如此选择k.比较两种方法的平均消耗 时间.nf以看出本文所提出的方法远远优于传统 的遇历方法所以总体來说本文所提出的方

24、法是 有效的.3. 2用ETL9B数据库的测试结果ETL9B数据库包含了 73类日文片假名和 2 963类U文汉字共3 036类文字毎个类别包 含了 200个样本其中每个样本为分辨率64X63 的二值图片图2(b)为ETL9B数据库中的部分 训练样本和测试样本.在此用200个样本中的前 20个利后20个样本进行测试用其余160个样 本进行训练.在实验中首先将每个样本剪裁到苴最小外接 矩形；然后通过非线性归一化小得到64 X 64的 图像，计算图像中每个像素点的梯度待征再将图 像分成8X8的网格用高斯采样统计每个网格中 的梯度值作为特征这样汉字图像被转化为512 维的特征向量，最后用线性判别分析

25、方法将这 512维的原始特征向呈降维到作为最终的特 征进(f训练和测试.在测试阶段采用两级分类的 策略:首先采用一个简总的最近中心分类器得到 洌10个候选测试样本；然后用MQI)F在这此候 选测试样本中得到最终的识别结果.表2为不同 的截断参数“下所对应的h屮,h “以及它们各自 所对应的识别率.khvz/iL亦/%11.5797.031.6097. OS90. 9997. IS0.8197. 1730. 7397.310.7197.3110. 6197. 410. 7097. 3150. 5297. 400. 7097. 3160. 1897. 390. 6997. 3470. 2697.0

26、60, 6297.3680. 1297.030. 6097. 38k/ifrnXm/%51.08497.911. 68197. 59100. 70998. 101. 20098. 13130. 58098. 530. 93993. 36200.52098. 590. 76893. *9250. 19598.620. 61593. 55300. 43097. 630. 55593. 60100.31598.670, 40398. 66500. 28398. 680. 30198. 67« 2 ETL9B数据库的实验结果本研究比较了 A = 5,10,15.20,25.30,40,50

27、这几个参数下的h取值情况以及其对应的识别71994-2018 China Academic Journal Electronic Publishing House. All rights reserved, 第12期姚趙等：用TTi文7 i只别的MQDF W代参数选择方法69率，其中计算平均消耗时间为1 248. 117叭 而计算儿m平均消耗时间为18 144.806 S之所以 没有给出史奇的"是因为相对于特征维数d = 180,实际中很少取到更高的k.从表2的实验结 果可以看出：本文所提出的方法在优于传统的遍 历方法的同时还减少了选抒h所消耗的时间这 证明了本文所提出算法的有效性.

28、从表1和表2可以看出：随着k的增大M的 值在减小这与理论上的分析泉-致的.从表1可 以看出随荐k的増大识别率在&>3之后提升效 果并不明显表2中的识别率则在Zr>30后提升 较小.这是因为A代表的是高斯分布中的主要方 向，当取值到一定大小时高斯分布中的大部分 信息已经被包會在内.所以实际屮应该选择合适 的k来平衡分类器的时间效率、存储效率与识别 效率之间的关系.本文所提出的方法在时间效率上相比于传统 的方法右很k的提升这是因为传统的方法是遍 历形式的即在可能存在的区域内以一定的步 长去搜索其最优取值而本文所提出的方法则只 须要遍历一次即可得到< h爲和心,所以在时 间

29、效率上可以得到很大的提升.参 考 文 献1 Zamort-Mnrtincz E. Frinken V Espana-Boqucra S et al. Neural network language models for off-line handwriting recognition |. Pattern Recognition 2014. 47(4)： 1642-1652.2 Impedcvo S. More than twenty years of advancements on frontiers in handwriting recognition J . PniiiTn Recogn

30、ition 2014. 47(3)： 916-928,3 Kimura F fakashina K Tsuruoka S. el al. Modified c|ua(lrntic discriminant functions and the application to Chinese character recognition J . IEEE Transnctions on Pattern Analysis and Machine Intelligence 1987, 9(1)： 119-153.4 何强丁晓青刘长松.用于手写汉字识别的级联 MQDF分类器J浦华大学学报：fl然科学版. 2

31、008. 18(10)： 1609-1612.5 Zhu B. Shivrnm A. Sctlur S. ct al. Online handwritten piirfnivp wore! rcoognition using segmentntion-free MKF in combination with P2DBMN-MQDK C' / 1 document Analysis and Recognition ( ICDAK ). Washington； IEEE. 2013s 34353.Moghaddam Pent land A. Probabilistic visual lea

32、rning for object rej)rcscntationJ. IEEE rrnnsne- tions on Pattern Analysis and Machine Intelligencet 1997, 19(7)： 696-710.7 Liul八 Sako H Fujisawa H. Dizcriminnlive lenm-ii:g quadratic discriminant function for handwriting recognition J . IEEE Transactions on Neural Networks. 2004 15(2)： 430-444.8 Liu C Lt Yin F Wang I) H ct al. Online and offline handwritten Chinese character recognition： benchmarking on new databasesQJ . Patlern Recognition* 2叽3. 46(1)： 155-162.9 Pes