Algorithm 版 (精华区)

发信人: AA (积极的人生、美好的人生), 信区: Algorithm
标  题: 手写体字符识别的二次串行集成方法(zz)
发信站: 哈工大紫丁香 (2002年05月23日10:23:25 星期四), 站内信件


手写体字符识别的二次串行集成方法
摘要
近年来，手写体字符识别系统的性能的提高不仅仅依赖于某一个识别器，而是靠在系统
中集成多个基于不同特征的识别器。如何充分发挥各识别器的互补性将决定系统的整体
性能。投票法和神经网络方法是常用的集成方法，本文在两者的基础上，提出了二次串
行集成方法，即在投票的基础上有选择的启动特别训练的神经网络作二次识别，从而发
挥投票法误识率低和神经网络集成法能提取复杂分布信息的优点，取得了整体性能的提
高。
关键词
手写体字符识别, 集成，神经网络，投票
一、概  述
近年来计算机字符识别系统层出不穷，性能也不断提高，尤其是统计特征方法的引入，
使得识别速度与性能上了一个台阶[1][2]。在手写体数字识别中，其识别方法大体分为
结构特征方法和统计特征方法[3]。结构特征方法一般是抽取图像中关键点, 如端点、拐
点，组成有序的逻辑规则来判别字符类别，它在印刷字符识别中有较多应用。由于手写
体字符的随意性，和书写环境的多变性，使得字符笔划宽度变化和噪声点常淹没结构特
征点影响识别效果。而统计特征则对字符图像的整体分布状态给出量化特征，它摒弃了
对于某特定点或笔划信息的依赖，具有与生俱来的鲁棒性，从而得到了广泛应用。
统计方法的具体流程如图.1。其中，预处理包括减噪和标准化；特征抽取则是识别的前
提，特征选取的好坏直接影响识别的效果；基于统计特征的识别主要分为基于贝叶斯分
布概率及相应距离的判别函数方法，以及基于神经网络的判别方法，两类方法都会给出
对于识别结果的置信度；而集成则是在系统中有多个识别器时，对各个识别结果进行评
估，得出最终结果，其中主要依据是识别器的置信度[5] [6]。
本文正是基于统计特征方法，在投票法和神经网络识别器的基础上给出一种新的二次串
行集成方法。本文将在第二节分析投票集成的性能，在第三节描述二次串行集成方法中
第二级集成器神经网络的性能，在第三节给出对于整个系统的描述，随后在第五章的实
验中，将给出系统性能实例数据，最后在第六节作出总结。基于本方法的系统在1998年
4月的863数字识别评估中取得优异性能.[8]
二、投票方法性能分析
在字符识别的统计方法中，一个特征总是从一定角度描述了字符图像及其性质。对于N*
N的二值图象,任何特征抽取都是对2N*N种可能的情况进行压缩编码，这必然导致某些信
息的丢失，从而使得本来可区分的图像在特征空间上不可区分；或者由于分布模式复杂
化，在选用一定的分类器之后，对于特定的分类面族成为无法区分的模式，因此统计方
法必然有一个误识问题．为减少误识就必然要拒识一些位于识别界面附近的样本．换言
之，就是误识率低是以拒识率高为代价的。
在大多数成熟的OCR系统中，方向线束及其变形特征都占据主导地位，其性能虽然较其他
统计特征要好，但仍然无法独挡一面，从图.2中可见其误识—正确率曲线。
选用不同的分类器就是选择不同的分类界面。 对于特定的模式集不同的分类界面会有不
同的误识, 因而误识率就会有高低变化。这种变化会随模式集的规模增大而增大。因而
针对不同的特征选用合适的分类器有着一定的讨论价值。另一方面，任一特征都会损失
信息，如果已经损失过度，任何分类器都难以取得合适的结果。这样就必需从多个特征
入手，期望能够用不同特征的相互独立性来彼此补偿，从而合成出优于任一单个特征的
性能。有了多个识别器，一般常用投票法来提高整体性能[4]。
对于k分类问题，定义分类器组N=(N1,N2,...Nn)，Ni输出为(Ci1, Ci2, ..., Cik), Ci
j是可信度输出。令Ai =argmax(Cij)，即最大下标j，这样就可以用专家投票产生侯选的
方法来合成这个n个分类器的结果。
投票法的综合结果是:
对于分类器Ni其正确率为Pci , 误识率Pwj  。
现在让我们分析一下，这样投票的效果。首先假定各个分类器的输出是相互独立的。
即P(Ai=wj,As=wt|x)= P(Ai=wj|x) P(As=wt|x)
因为使各个特定分类器敏感的噪声点或形变是不相同的，因而使多个分类器同时错分为
同一类的的概率较小，故可以设定错误输出均匀分布在另外C-2类上,则有P(wj|wi,i≠j
)=(1-Pc)/(C-1)
对于样本X，设分类器组N输出为矩阵(A1,...,As,Bs+1,...Bn), 其中Ai为正确类别，Bj
是错误分类
P(A1,...,As,Bs+1,...Bn)=P(A1) ...P(Bn) = P(A1) ...P(As)(1-P(As+1))...(1-P(An
))
=Pc1 ...Pcs (1-Pcs+1) ...(1-Pcn)
考虑到同样k票由不同的分类器组合, 相应的投票结果及其概率会有如下几类：
S≥k, 则分类量输出为正确结果, 其概率为:
S<k且
分类输出错误结果,其概率为:
其余情况是拒识, 其概率是1-Pc-Pf
为说明性质，特简化情况.
令Pc1=...=Pcn=Pc, Pw1=...=Pwn=Pw
取典型Pc为90%, 类别C为10, 可得拒识率__正确率的典型分布,
k=3
k=4
k=5
总Pc
0.991
0.919
0.590
总Pe
1.21*10-4
6.79*10-7
1.52*10-9
                 表.1  投票模型的正确率_拒识率分布
比较图.2中DV识别器的分布, 可以发现其性能好于单个网络. 然而在大多数实际应用场
合，不同分类器产生的错误有着相当大的重叠，因而识别结果就不会如上表那样好。
三、二次串行集成方法
投票方法是一种常用的集成方法，从上文分析可知其性能是稳定的，以致人们常常把它
的识别率作为衡量其他集成方法的指标。投票法另一个很大的优点就是它产生的误识率
非常地低。可是，投票法并非完美，它往往对于书写自由的噪声较多的样本产生太多拒
识。如何把低的误识与进一步提高各识别器的识别率相结合是当前集成方法的研究重点
。
神经网络用于多个识别器的集成有着极好的应用前景。我们认为可以把神经网络与投票
法相结合，形成二次串行集成方法，即在投票器产生拒识时,可以用神经网络作二次集成
再识别。
由于大多数基于统计特征的分类器，都可以输出对于聚类值的可信度，这种可信度在一
定程度上反映了该样本特征隶属于所认定类别的概率，因而这种数值实际具有较大的再
分析价值。
在实践中，经常存在1与7的混淆，3与8和2，这种混淆是具有特征性的. 表.2给出了DV方
法的误识矩阵。其中元素aij表示数字i被识别为j的样本数。从中可见1识别为7、 6识别
为0、7识别为2的错误比较突出，共占到总错误的19.3%。而且这种相对集中错误与选取
的特征有密切联系，一种特征中相对集中的地方在其它特征中往往不明显。这种关系不
是简单的几条规则就可以划定的, 但又是客观存在的。由于BP网从理论上可以拟合任何
函数，因而适当选择隐层的节点数，就可以用来提取上述误识矩阵中比较复杂的分布信
息。
为此定义一个三层BP网络作为二次识别器。其中输入层共有N*C个节点，输出为C个节点
分别代表C个类别。当投票器以较高阈值产生拒识时，将N个相互独立的识别器的N*C个可
信度输出送入该二次识别器，从而构成一个与投票串联的集成识别器。训练该二次识别
器时，以对各个识别器输出的求和为初始权值，采取梯度下降总体误差反传方法。当教
师集有代表性时，最终收敛效果必然好于对于N个分类器的平均加权。
由于缺乏手段对BP网最终收敛点作定量分析，我们转而分析BP网初始状态下的集成效果
，并与过半数投票法相比较。
假设有5个互相独立的识别器，各自输出未知样本是0～9的可信度。分类器对于正确类别
的可信度输出Nc(x)，趋近于该模式隶属于正确类别的概率值与噪声的叠加。由于噪声的
平均分布性，可以假定Nc(x)是以该模式隶属于正确类别的概率密度为期望值的区间正态
函数N(μ1 ,σ12)：
由于BP网将模式x识别为其他9类的概率大致相同，可用Nw(y)统一描述其余类别的可信度
输出；由于误识是由训练和识别中的随机噪声引起，故仍然可用区间正态函数N(μ2 ,σ
22)来趋近Nw(y)；由于可信度输出之和为1，即y=(1-x)/(C-1)。故Nw(y)的期望值μ2 =
(1－μ)/9。
这样我们就把问题化为在5个独立的分类器对0～9分别给出可信度输出，正确答案对应的
可信度分布为Nc(x), 其余9项的可信度分布为Nw(y)
因而，集成识别结果正确的概率为
由于上式无法解析表达，故用蒙特卡洛方法给出估计。为增加实际效果，我们用实际方
向线素识别器（DV）来估计其中参数。如图.3为DV对于TsOcr库1的可信度分布。
由实验数值可估计得
μ1=0.7,  σ12=0.0576,
μ2=0.032,  σ22=0.0041,
为验证这样的简化模型的有效性，随机产生5000个服从N(μ1 ,σ12)和N(μ2 ,σ22)的
样本点测试本模型，可得模型识别率为93.5%，而DV对自采样本集1的识别率是92.2% 。
 两者相当接近，可见所定义的模型是有效的。
用5个同样的简化模型作为第一级识别器，分别把识别结果和可信度送入二次识别器和过
半数投票器，用蒙特卡罗方法来比较两者性能。5000次随机实验可得：
过半数投票器识别率：99.84％
平均加权识别率： 99.98%
可见平均加权的识别率优于过半数投票。由于实际系统中各识别器的输出并非相互独立
，因而实际识别率低于上述指标。但以上模拟实验中，过半数投票器与BP网的初态（平
均加权）的相对优劣是有实际指导意义的。
四、系统架构
本文选择三类特征，分别是方向线素，灰度，轮廓数。由于方向线素的性能优异，故引
入方向线素的两个变形，不对称方向线素1和2，这样形成5个独立的识别器。下面分别详
述各特征的定义。
1． 分类器N1基于方向线素：对于标准化的二值图象，划分为16个方格，按照水平，垂
直，主对角，次对角四个方向提取64维特征，作为BP网的输入。所有识别器均采用三层
结构,输出共10个节点,分别对应0~9,不再另设拒识输出节点。输入层由各特征维数决定
。
2． 分类器N2和N3基于方向线素的变形,将标准化的二值图象不对称划分为16个矩形格,
按照水平，垂直，主对角，次对角方向分别提取方向向量,得到64维特征输入。
3． 分类器N4基于灰度特征：标准化的二值图象，划分为64个方格,累计其中的黑象素点
的个数，得到64维特征输入。
4． 分类器N5基于轮廓特征：取8个X坐标，分别延Y方向扫描标准化后的二值图象，得到
第一左轮廓和第二左轮廓的X坐标值；同理得到第一右轮廓和第二右轮廓的X坐标值，第
一上轮廓和第二上轮廓的Y坐标值，第一下轮廓和第二下轮廓的Y坐标值，从而形成64维
输入。
五个识别器的输出是对于各个类别的近似隶属度，经取大得到该识别器的最佳候选，五
个候选输入投票器产生投票结果，作为第一次集成。从上文分析可知，投票可以将误识
压得很低。在本系统中，利用这一点，先选用较高票数，保证第一级输出误识极低。若
投票器输出为拒识，则把五个识别器输出的对于0～9的隶属度作为50维向量输入集成BP
网N6，完成二次集成。整体系统架构如图.4所示。
五、实验结果及分析
本系统以自己收集较清晰的书写较规范的TsOcr库3 （40000样张幅）作为有教师学习集
; 选用Nist库中近6万样张作为测试集。由于Nist库中的样本比较规范，与许多人龙飞凤
舞的风格有一定的差距，故另用图象质量较好但书写较自由的TsOcr库1（10000样张）和
图象质量较差的TsOcr库2（10000样张）构成测试集。测试集中典型样本如图.5,6,7。测
试结果如下：
首先，各个识别器在没有设置拒识的条件下对于测试集的识别率都低于99％(表.3)。用
投票法仅能用票数来改变拒识率的高低，其拒识－正确率是孤立的点,如图.8 。基于同
样的识别器，使用本二次集成器，通过简单的阈值调整可以得到拒识－正确曲线如图.9
。使用投票法和二次串行集成的方法在最大识别率情况下,虽然都比任一个子识别器的识
别率要高,但使用投票作集成，最大可将正确率提高1.95%(TsOcr库2),最少可将正确率提
高0.55%(Nist库);而用本文提出的二次串行集成方法可将正确率最大提高5.30%(TsOcr库
2),最少也可将识别率提高0.56%(Nist库).由此可见本文提出的二次串行集成方法比投票
方法更能提取各个识别器的输出分布,更能提高系统的整体正确率.另外需要指出的一点
是,在图象较规范的情况下,本方法与投票法相差无几,仅有0.01%也就是仅有4个样本识别
不同,可见这时各识别器的可信度输出分布的规律性较差,而当样本书写质量较差时, 本
方法与投票法有3.35%的差别,如此大的差距正说明,书写质量差是由一种有倾向性的噪声
引起的, 比如断线和边框的残留,这种有倾向性的噪声在识别器的可信度输出上也有规律
可循,这种规律性正适于用被本文提出的二次串行集成方法来提取.
六、结论
由于手写体的千变万化，单一的基于统计特征的识别器无法取得满意的识别结果。不同
的统计特征之间的互补性产生了多识别器集成的问题。投票的方法是一个较通用的方法
，本文通过概率理论分析肯定了其可行性，由于投票的方法即使加上不同权值，也只是
简单线性再划分，而基于统计特征的识别器产生的可信度分布是复杂非线性的，因而其
性能必然受到影响，如何才能继承投票的低误识率并进一步利用可信度分布呢？针对这
个问题本文把投票和神经网络结合起来，提出了二次串行集成方法。实验表明其性能优
于投票方法，而且对于无约束过于自由的字体有着更大容错性。
包括本系统在内的决大多数系统都采用开环的识别模式，这是不符合人的识别方式的。
如果能够把识别粗略结果反馈到前一级，形成一个闭环的集成方法将是一个有潜力的方
向。
参考文献
[1]Michael D Garris,Charles L Wilson, "neural network-based systems for hand
printed OCR applications", IEEE Tran. Image Processing, Vol. 7,No8, p1097-11
12,1998
[2] Paul D.Fader, Mohemed Ali Khabou, "automatic feature generation for hand
written digit recognition", IEEE Tran. Patt.Anal.Mach.Intell., Vo18, No12, 1
996
[3] John t.Favata, Sargur N.Sarihari "Offline Recognition of Handwritten Cur
sive words", SPIE Vol 1661, p224-234,1992
[4] Roberto Battiti,annamaria Colla, "Democracy in Neural Nets Voting Scheme
s for Classification" Neural Networks, Vol7,No4,p691-707,1994
[5] Song Wang, Xiaoyan Zhu, Yijiang Jin "Multiple experts Recognition System
 Based on Neural Network", Proceedings of ICPR'96, Vienna, Austria
[6] 郝红卫，戴汝为 “人机结合的集成方法及其在字符识别中的应用”， 模式识别与
人工智能， Vol9,No.1,p10-20
[7]马少平，夏莹，朱小燕 “基于模糊方向线素特征的手写体汉字识别”，清华大学学
报 Vol37, no 3,p42-45, 1997
[5] "第五界全国汉字识别、语音识别与合成系统及自然语言处理系统评测结果", 智能
机研究动态，No4, p9-19,1998
手写体字符识别的二次串行集成方法
第   1   页
手写体字符识别的二次串行集成方法
第   8   页 
--
                人世间的事谁也无法掌握
                  该执著的  永不怨悔
                  改舍去的  不在牵挂
                  改珍惜的  好好把握

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: NLPCenter.hit.edu.cn]