（计算数学专业论文）印刷体数学公式上下标的一种判别方法.pdf

大连理工大学硕士学位论文 摘要 随着计算机和因特网的发展，人们越来越多地使用计算机处理日常工作和存储信 息。将印刷体文档通过光学字符识另1 ( o p t i c a lc h a r a c t e r sr e c o g n i t i o n ，o c r ) 技术转化为电 子文档进行存储和传输己成为信息交流的重要步骤。现有的主流o c r 软件都能够准确、 高效地识别普通文本，但是对于数学公式，它们的识别结果只不过是一些失去了原来意 义的符号。而数学公式是大部分科技文档的重要组成部分，甚至是一些文献的核心，失 去了公式会使文献的应用价值大为降低。为此研究者们提出了新的数学公式识别系统。 数学公式与普通文本相比有许多不同，其中除了含有字符，还可能包含根式、分式、上 下标、极限、矩阵等特殊结构，其形状和位置也不是固定不变的。此外，公式中有些字 符在不同场合还可能表示不同的意义。这些都使得数学公式成为具有二维特征的复杂结 构体，决定了数学公式识别应该包括符号识别和结构分析两个方面。 本文的结构安排如下：第l 章介绍了模式识别和神经网络方面的知识，概述了数学 公式识别系统的流程。第2 章介绍了文档图像预处理的相关内容，对公式定位的典型方 法及普通符号、处理粘连符号的最短路径和基于自组织特征映射( s o f m ) 网络的分割方 法做了简介。第3 章首先介绍了基于矩特征的字符特征提取，包括几何矩和z e r n i k e 矩。 通过分析比较，发现z e m i k e 矩比几何矩更适合用于符号特征的提取。然后对b p 网络 的分类能力进行了测试，并联合一个s o f m 网络和多个b p 网络，组成多级神经网络模 型作为识别器，对字符图像做了识别试验。第4 章为本文的重点。针对公式结构分析， 特别是上下标这种出现频繁又难于解决的特殊结构，分析和比较了几种上下标关系判别 的方法，并提出了一种基于投影方法和轮廓追踪算法相结合的改进方法。最后进行了数 值实验，表明此方法能较好地适应公式特点，具有较高的正确标记率。 关键词：神经网络；公式识别；上下标；投影；轮廓追踪 印刷体数学公式上下标的一种判别方法 am e t h o df o rd e t e r m i n i n g s u p e r s c r i p t s u b s c r i p t o fp r i n t e dm a t h e m a t i c a lf o r m u l a s a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e r sa n di n t e r n e t ，m o r ea n dm o r ep e o p l eu s ec o m p u t e r s t od e a lw i t hr o u t i n ew o r ka n ds t o r ei n f o r m a t i o n t h e r e f o r e c o n v e r t i n gt h ep r i n t e dd o c u m e n t s t h r o u g ht h eo c r ( o p t i c a lc h a r a c t e rr e c o g n i t i o n ) t e c h n o l o g yi n t ot h er e t r i e v a b l ea n de d i t a b l e e l e c t r o n i cd o c u m e n t sf o rs t o r a g ea n dt r a n s m i s s i o nh a sb e c o m ea ni m p o r t a n tw a y t h e m a i n s t r e a mo c rs o f t w a r e sc a na c c u r a t e l ya n de f b c i e n t l yr e c o g n i z ec o m m o nt e x t s b u tf o r t h em a t h e m a t i c a lf o r m u l a s ，t h er e c o g n i t i o nr e s u l tl o o s e ss o m eo r i g i n a lm e a n i n ga c c o r d i n gt o t h ed o c u m e n t s m a t h e m a t i c a lf o r m u l a sa r ei m p o r t a n tc o m p o n e n t so f m o s ts c i e n c ed o c u m e n t s a n da c ta st h ec o r eo fs o m ei i t e r a t u r e s t h ev a l u eo fal i t e r a t u r ew i l lb eg r e a t l yr e d u c e d w i t h o u tf o r m u l a s a sar e s u l t ，r e s e a r c h e r sb e g i nt os t u d yn e wr e c o g n i t i o ns y g e m sf o r m a t h e m a t i c a lf o r m u l a s c o m p a r e dt oc o m m o nt e x t s , m a t h e m a t i c a lf o r m u l a sh a v em a n y d i f f e r e n tf e a t u r e s ，s u c ha sr a d i c a le x p r e s s i o n ，f r a c t i o n ，s u p e r s c r i p t s u b s c r i p t ，l i m i t ，m a t r i x , e t c t h es h a p ea n dl o c a t i o no ff o r m u l a sa r en o ta l w a y sf i x e d a n ds o m es y m b o l sm a yh a v e d i f f e r e n t m e a n i n g su n d e rd i f f e r e n ts i t u a t i o n s m a k i n g m a t h e m a t i c a lf o r m u l a sb e c o m e c o m p l e xt w o d i m e n s i o n a ls t r u c t u r e s t h u sm a t h e m a t i c a lf o r m u l ar e c o g n i t i o ns h o u l di n c l u d e b o t hs y m b o lr e c o g n i t i o na n ds t r u c t u r ea n a l y s i s t h i st h e s i si so r g a n i z e da s f o l l o w s 。c h a p t e r1p r o v i d e sab r i e fr e v i e wo fp a t t e r n r e c o g n i t i o na n dn e u r a ln e t w o r k s a n di l h s t r a t e st h ew o r kf l o wo fm a t h e m a t i c a lf o r m u l a r e c o g n i t i o ns y s t e m t h er e l a t e dc o n t e n to ni m a g ep r e p r o c e s s i n g ，f o r m u l ae x t r a c t i o na n d c h a r a c t e rs e g m e n t a t i o na r ei n t r o d u c e di nc h a p t e r2 i nc h a p t e r3 c h a r a c t e rf e a t u r ee x t r a c t i o n b a s e do nm o m e n t 佗a m r ei si n t r o d u c e d a n dt h ep e r f o r m a n c eo fb pn e u r a ln e t w o r k s c l a s s i f i c a t i o na b i l i t yi st e s t e d f i n a l l y w ec o m b i n eas o f mn e u r a ln e t w o r kw i t hs e v e r a lb p n e u r a ln e t w o r k st of o r mam u l t i s t a g en e u r a ln e t w o r km o d e la sar e c o g n i z e r , a n dg i v ea c h a r a c t e rr e c o g n i t i o nt e s tf o ri t c h a p t e r4i st h ef o c u so ft h i st h e s i s a f t e rt h ea n a l y s i sa n d c o m p a r i s o no fs e v e r a lm e t h o d sf o rd e t e r m i n i n gs u p e r s c r i p t s u b s c r i p tr e l a t i o n s ，t h i st h e s i s p r e s e n t s a ni m p r o v e dm e t h o db a s e do nt h ep r o j e c t i o nm e t h o da n dt h ec o n t o u rt r a c i n g a l g o r i t h m t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h i sm e t h o dc a na d a p tw e l lt of o r m u l af e a t u r e s a n dh a sag o o dr a t ef o rc o r r e c tl a b e l i n g k e yw o r d s ：n e u r a ln e t w o r k ；f o r m u l ar e c o g n i t i o n ；s u p e r s c r i p t s u b s c r i p t ；p r o j e c t i o n ； c o n t o u rt r a c i n g 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为荻得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：加譬6 i 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名：亟堑鳌： 导师签名：夺至聋 避年4 月止日 大连理工大学硕士学位论文 1 绪论 1 1 模式识别介绍 模式识另 ( p a t t e mr e c o g n i t i o n ) 是人类的一项基本智能活动，它对许多人来说很陌生， 然而实际上人类却在日常生活的每个环节都从事着“模式识别”的活动。模式识别是2 0 世纪6 0 年代初迅速发展起来的一门新学科，它所研究的理论和方法涉及多门学科和技 术领域，推动了人工智能、图像处理、信号处理、计算机视觉及多媒体技术等多种学科 的发展，扩大了计算机应用的领域。 什么是模式和模式识别呢? 广义地说，存在于时间和空间中可观察的事物，如果可 以区别它们是否相同或相似，都可以称之为模式；狭义地说，模式是通过对具体的个别 事物进行观测所得到的具有时间和空间分布的信息：把模式所属的类别或同一类中模式 的总体称为模式类( 或简称为类) 。而“模式识别”则是在某些一定量度或观测基础上把待 识模式划分到各自的模式类中去。 模式识别是一种从大量信息和数据出发，在专家经验和已有认识的基础上，利用计 算机和数学推理的方法对形状、模式、曲线、数字、字符格式和图形自动完成识别的过 程。模式识别包括相互关联的两个阶段，即学习阶段和实现阶段，前者是对样本进行特 征选择，寻找分类的规律，后者是根据分类规律对未知样本集进行分类和识别。广义的 模式识别属计算机科学中智能模拟的研究范畴，内容非常广泛，包括声音和语言识别、 文字识别、指纹识别、声纳信号和地震信号分析、照片图片分析、化学模式识别等等。 计算机模式识别实现了部分脑力劳动自动化。模式还可分成抽象的和具体的两种形式。 前者如意识、思想、议论等，属于概念识别研究的范畴，是人工智能的另一研究分支。我 们所指的模式识别主要是对语音波形、地震波、心电图、脑电图、图片、照片、文字、 符号、生物的传感器等对象进行测量的具体模式进行分类和辨识。 模式识别研究主要集中在两方面，一是研究生物体( 包括人) 是如何感知对象的，属 于认识科学的范畴，二是在给定的任务下，如何用计算机实现模式识别的理论和方法。 前者是生理学家、心理学家、生物学家和神经生理学家的研究内容，后者通过数学家、 信息学专家和计算机科学工作者近几十年来的努力，已经取得了系统的研究成果。 模式识别与统计学、心理学、语言学、计算机科学、生物学、控制论等都有关系。 它与人工智能、图像处理的研究有交叉关系。例如自适应或自组织的模式识别系统包含 了人工智能的学习机制；人工智能研究的景物理解、自然语言理解也包含模式识别问题。 印刷体数学公式上下标的一种判别方法 又如模式识别中的预处理和特征抽取环节应用图像处理的技术；图像处理中的图像分析 也应用模式识别的技术。 一个计算机模式识别系统基本上事有三部分组成的，即数据采集、数据处理和分类 决策或模型匹配。任何一种模式识别方法都首先要通过各种传感器把被研究对象的各种 物理变量转换为计算机可以接受的数值或符号( 串) 集合。习惯上，称这种数值或符号( 串) 所组成的空间为模式空间。为了从这些数字或符号( 串) 中抽取出对识别有效的信息，必 须对它进行处理，其中包括消除噪声，排除不相干的信号以及与对象的性质和采用的识 别方法密切相关的特征的计算( 如表征物体的形状、周长、面积等等) 以及必要的变换( 如 为得到信号功率谱所进行的快速傅里叶变换) 等。然后通过特征选择和提取或基元选择 形成模式的特征空间。以后的模式分类或模型匹配就在特征空间的基础上进行。系统的 输出或者是对象所属的类型或者是模型数据库中与对象最相似的模型编号。针对不同应 用目的，这三部分的内容可以有很大的差别，特别是在数据处理和识别这两部分，为了 提高识别结果的可靠性往往需要加入知识库( 规则) 以对可能产生的错误进行修正，或通 过引入限制条件大大缩小待识别模式在模型库中的搜索空间，以减少匹配计算量。在某 些具体应用中，如机器视觉，除了要给出被识别对象是什么物体外，还要求出该物体所 处的位置和姿态以引导机器人的工作。 1 1 1 模式识别过程 ( 1 ) 模式采集：它相当于对被研究对象的调查和了解，从中得到数据和材料。在物 理上可以觉察到的世界里，适当地选择某些事物和事件，我们把它们称为样本，然后对 它们分别进行观测。每个样本的观测数据的综合都构成模式，所有的样本观测数据则构 成模式空间。显然，模式空间的维数与所选择的样本和测量方法有关，也与特定的应用 有关，一般来说是很大的，但是有限值。在模式空间里，每个模式样本都是一个点，点 的位置由该样本在各维上的测量数据来确定。由物理上可以觉察劭的世界到模式空间所 经历的过程称为模式采集。在模式采集过程中可以细分为图像信息的获取和图像预处 理，预处理的目的是去除噪声、干扰和差异，将原始图像变成适合于计算机进行特征提 取的形式，它包括图像的变换、滤波等。 ( 2 ) 特征提取和选择：它的作用在于把调查了解的数据材料进行加工、整理、分析 和归纳，以去伪存真，能抽取反应事物本质的特征。模式空间的维数虽然是有限的，还 是非常多的，例如一个文字图像可以有几千个数据，一个心电图波形也可能有几千个数 据，一个卫星遥感图像的数据量就更大，其中有些并不能有效地揭示样本的实质。正像 人们对事物进行判断之前要进行综合分析一样，机器在做出判断之前也要对模式空间里 的各坐标元素进行综合分析，获取最能揭示样本属性的观测量作为主要特征，这些主要 大连理工大学硕士学位论文 特征就构成特征空间。显然，特征空间的维数大大地压缩了。特征空间里的每个坐标都 是样本的主要特征，而且，这些主要特征对于通常所遇到的变化和畸变是不变的或不敏 感的。每个样本在特征空间里也是一个点，点的位置由该样本在各维上的测量数据来确 定。由模式空间到特征空间所需要的综合分析，往往包含适当的变换和选择，称为特征 提取或特征选择。特征提取是模式识别中的广泛研究的课题。特征提取可以避免维数灾 难，改进分类器的泛化能力，减少运算次数。 ( 3 ) 分类判决：由某些知识和经验可以确定分类准则，称之为判决准则。根据适当 的判决准则，把特征空间里的样本区分成不同的类型，从而把特征空间塑成了类型空间。 类型空间里不同类型之间的分界面常称为决策面。类型空间的维数与类型的数目相等， 一般地说，小于特征空间的维数。由特征空间到类型空间所需要的操作是分类决策。 从模式识别的技术途径来说，物理上可以觉察到的世界，通过模式空间、特征空间 到类型空间，经历了模式采集、特征提取以及分类决策等操作，是模式识别所经历的完 整过程( 见图1 1 ) 。为了完成上述过程，还需要先对机器进行训练，使机器具有识别的能 力。训练的过程是将人类的识别知识和方法以及分类识别对象的知识输入机器中，产生 分类识别的规则和分析程序，这也相当于机器进行学习。这个过程一般要反复进行多次， 不断地修正错误，改正不足，这包括修正特征提取方法、判决准则参数及方法，最后使 系统正确识别率达到要求。 维数 无限 很大 尺 有限 d 不大 c 图1 1 模式识别过程，其中c d r 无限 f i g 1 1p r o c e s so f p a t t e r nr e c o g n i t i o n ，w h e r ec d 尺 - j 过程：设训练样本为扛7 乞cr 1 ，可通过下述过程来确定网络权值矩阵阢 网络初始化：将训练样本 x ) 么，按出现概率排成序列 x ”) ，随机选取初始权矩 阵矿o ，令k = 0 ； 竞争：对每一个输入，网络中的神经元计算它们各自的输出值，具有最大值的 特定神经元成为竞争的胜利者。具体地，设网络输入= ，# ) ，输出为： 露= k 矗k ，m = l ，m ( 2 6 ) 全体输出单元竞争后，选出唯一的获胜单元羹， 矿= m a 驯x ( 2 7 ) 这表示输入向量x 被分到见所代表的这一类中。可以证明，在权值向量长度固定 i i 既l i = c ( 2 8 ) 的条件下，下式与式( 2 8 ) 等价 lix k - - 嘲= 。r a ；。i ni l 矿一8 ( 2 9 ) 合作：获胜神经元决定兴奋神经元的拓扑邻域的空间位置。可以用各种方式对 输出层的获胜神经元儿定义其，( z = o ，l ，2 ，) 阶邻域彬，如图2 4 所示。设另一个输 出单元虼w ，但萑w 一，定义和儿的距离为 = q ( 2 ，l o ) 图2 4 输出单元的邻域 f i g 2 4n e i 曲b o r h o o do fo u t p u tu n i t s 印刷体数学公式上下标的一种判别方法 权值修改：兴奋神经元通过对它们权值的适当调节以增加它们关于该输入的输 出。利用适当选定的距离函数办( 靠，七) ，按下式修改权值： 嘭+ 1 = 嘭+ 办( “，七) ( x 似一嘭)( 2 11 ) 权值归一化：权值修改后，将各神经元的权值分别乘以适当的常数，使式( 2 8 ) 成 立。 收敛性检测：若按某种准则权值迭代收敛，则停止；否则七增加l ，转到。由 式( 2 1 1 ) ，得 黟葛+ 1 一x 耻= o - h ( d m 。，后”( 纾艺- - x ( ”)( 2 1 2 因此，当i l 一办( ，七) l 0 说明两个神经元之间相互作用。各神经元的 平衡态由于的存在而相互影响，接受域r 也通过朋磕相互影响。 过三 k 呤 7 图2 3 传统学习规则，x ：输入样本， ：神经元 f i g 2 3t r a d i t i o n a lu p d a t i n gr u l ef o r s o f m ，：i n p u t ，：n e u r o n s 图2 4 新的学习规则，工，= 上l + l 2 f i g 2 4n e wu p d a t i n gr u l ef o rs o f m ， 3 = l + 2 3 训练结束后，所有的权值达到一个相对稳定的状态。此时，我们选择第- - y 0 的结点 ( 口点) 作候选分割结点，连接它们( 共有七种组合c ；+ c ；+ c3 ，= 7 ，最上面的和最下面的结 点分别向上、向下作垂线) 作分割路径。分别计算路径长度( 如遇到黑象素，长度加1 0 ； 遇到自像素，长度加1 ) ，选择一条最短路径作分割路径( 见图2 5 ) 。 印刷体数学公式上下标的一种判别方法 图2 5 神经元的分布( 口a n d ) ：口表示候选分割结点，折线表示分割路径 f 谵2 5d i s t r i b u t i o no f n e u r o n s ( 口a n d ) 口r e p r e s e n t sc a n d i d a t es e g m e n t a t i o nn o d e s ， a n dt h ez i g z a gl i n er e p r e s e n t ss e g m e n t a t i o np a t h 2 4 大连理工大学硕士学位论文 3 特征提取与符号识别 3 1基于矩的特征提取 在字符识别过程中，如果将字符图像的像素直接输入送到识别器中，一般来说，会 存在如下一些问题： ( 1 ) 它们的特征空间是非正交的； ( 2 ) 它们不可能表示出被识别模式的显著特征； ( 3 ) 它们是冗长的。多余的大输入矢量会导致需要更大容量的识别器，一般来说， 使其性能下降： ( 4 ) 对于平移、旋转、尺度的交换，它们不是恒定的。 因此，对于给定的模式，我们往往不用原始数据表示，而是在数据预处理及特征提 取阶段采用形状特征提取( 或不变量特征提取) 技术，获得有用的形状特征参数，包括直 接对区域、边缘做出的描述，或者通过数学方法差生的一些特征参数。在神经网络模式 识别系统中通常用矩特征描述方法。 矩特征是利用力学中矩的概念，将区域内部的像素点作为质点，像素的坐标作为力 臂，从而以各阶矩的形式来表示区域形状特征的一种形状描述符。矩和矩的函数在二维 图像的不变量模式识别中具有广泛的应用。美籍华人学者胡名桂教授拉7 】于1 9 6 1 年基于 几何不变量的方法首次提出矩不变量。用规则矩( 这里指几何矩) 的非线性组合，他得到 了图像在平移、旋转、尺度变换下都具有不变性的不变矩描述符。但当时，他只给出低 阶的7 个不变矩。l i t 2 8 1 进行了推广，给出了直到1 2 阶的5 2 个不变矩的统一表达式。 t e a g u e t 2 9 1 基于z e r n i k e 正交多项式给出了z e r n i k e 矩，它也是在实际模式识别应用得最为 普遍的。 3 1 1 几何矩 设i ( x ，y ) 是连续图像函数，它的p + q 阶几何矩定义为： = = 聊阳= iix p y 9 ，( x ，y ) d x d y ( 3 1 ) 几何矩提供图像的丰富信息，并且是模式识别中常用的特征。它们的信息内容来源 于：矩提供了图像的相同表示。在这个意义上，图像能从它的矩( 所有阶) 中重构。因此， 每个矩系数传递一定数量的图像信息。 印刷体数学公式上下标的一种判另l j 方法 模式识别中的理想性质是在几何变换中的不变性，在式( 3 1 ) 中定义的矩取决于图像 中感兴趣对象的坐标。因此，它们没有上述的不变性。这个问题可以通过适当定义矩的 归一化组合来解决。特别地，我们的目标是定义矩的不变性： 平移： x = x + a ，y = y + b( 3 2 ) 缩放： x = 口x ，y = 励 ( 3 3 ) 旋转： ； = 。一c o s s m e 汐c s 。i n s o 秒1 l 。l 少x c 3 4 ， 中心矩： 以g 2 jj ，o ，y ) o x - - ) p 沙一y - ) 9 d x d y ( 3 5 其中，中心矩是平移不变的。 归一化中心矩： 2 等一半+ 6 ， 容易证明，对于平移和缩放，这些矩是不变的。 对于数字图像， _ ) ( f = o ，l ，m 一1 ) ，前面描述的矩可以近似用下式来代替： m p ，= i ( i , j ) i p 9 ( 3 7 ) 为了使矩值对于不同大小的图像的动态范围保持一致，在计算矩之前，对x ? ) ，轴进 行归一化。则矩近似等于 m p ，= i ( x y ) x ? y ?( 3 8 ) 其中的和包含所有的图像像素，( 薯，咒) 是第f 个像素中心点的坐标，并且不再是整数， 而是处于x ，【- 1 ，l 】，乃“一1 ，1 】之间的实数。对于数字图像，已经定义的矩的不变性 只是近似为真。 3 1 2z c m i k e 矩 式( 3 1 ) 中定义的几何矩也可以被视为i ( x ，y ) 单项式x p y 9 在基函数上的投影，这些单 项式不是正交的。因此从信息冗余的观点看，几何矩特征不是最优的。而z e m i k e 矩是 大连理工大学硕士学位论文 基于z e m i k e 正交多项式的一种矩特征，可以减小所要提取的模式特征的信息冗余。 z e m i k e 多项式是定义在单位圆上的一组多项式，通常用极坐标表示，按如下方式定义： z 蛳t = 4 n + lr t ( r ) 4 2c o s m o ，m 0 z 刎，= 、n + l r ? ( ，) 2s i n m 0 , m 0 ( 3 9 ) 乙，= 4 n + l r ：( ，) ，m = 0 其中，嚣、m 为非负整数，满足玎辨，n - i r a l 为偶数，、p 是单位圆上的极坐标。群( r ) 是 关于，的径向多项式，定义如下： 洲= 警s = o 而谛篙赫舻 n 聊 蹦一2 而羽拦赢辆砣” ( 3 1 0 ) 二维平面上单位圆内图像的连续函数厂0 ，y ) 的( 刀，m ) 阶z e m i k e 矩定义为： 么半j f ：+ 内m ，y ) 【匕。( 训) 】饥d y ( 3 11 ) 其中，为复共轭，复值函数。o ，y ) 定义为： 圪。( x ，y ) = k 聊( ，p ) = 尺：驴) e x p ( i m o ) ( 3 1 2 ) 矩特征提取具有抗旋转的性质。设f ( x ，力是图像的分布函数，z e m i k e 矩的极坐标 表示为 a 。= i j f ( r ，o ) g 。( ，) e x p ( i m o ) r d r d o ( 3 1 3 ) 其中，g 。( r ) 是z e r n i k e 多项式当图像旋转角度目时 = 0 9 e x p ( - q o )( 3 1 4 ) 则旋转后的z e r n i k e 矩的模8 f 乙0 = 0 ，0 ，所以是旋转不变的。利用z e m i k e 矩的这些 性质，在字符识别中比较适合用于提取图像特征。 3 2 b p 神经网络 近年来，随着神经网络研究的日益深入及其实现手段的逐渐成熟，神经网络被广泛 用于模式识别问题，特别是用于各种字符的识别，并在一定的字符集上取得了很好的效 果【3 m 3 2 1 。我们采用s o f m 网络和b p 网络组成的二级神经网络模型，对数学符号进行识 别。上一章在字符分割时已经介绍了s o f m 网络的原理和结构，下面先介绍b p 网络的 基本原理和网络的设计问题，然后给出二者组成的二级神经网络进行数学公式识别时的 参数和其它细节。 印刷体数学公式上下标的一种判别方法 3 2 1b p 神经网络概述 b p 神经网络是神经网络分类器中普遍通用的一种形式，广泛用于字符的识别【3 3 】。 b p 网络采用光滑活化函数，具有一个或多个隐层，相邻两层之间通过权值全连接。它 是前传网络，即所处理的信息逐层向前流动。而当学习权值时，却是根据理想输出与实 际输出的误差，由前向后逐层修改权值( 误差的后向传播，即b a c kp r o p a g a t i o n ) 。 图3 1b p 网络结构 f i g 3 1b p n n ss t r u c t u r e ( 1 ) 网络结构：以带一个隐层和一个输出单元的b p 网络为例，网络分为输入层、 隐层和输出层，其拓扑结构如图3 1 。己= l ，) 表示输入单元，r p ( p = l ，尸) 表示 隐单元，厶= l ，m ) 表示输出单元。磊通过权值与隐层的每一个单元0 连接， 通过权值与输出层的每一个单元靠连接。隐层的活化函数为非线性光滑函数 g 。：r 1 一r 1 ，输出层的活化函数为非线性光滑函数g ：尺1 专r 1 ，同层各单元一般不相连 接。输入层和隐层各单元常常排成一维、二维或多维阵列，输出层各单元一般排成一维 阵列。 ( 2 ) 工作流程：对任一输入模式孝= ( 毒，氨) t r ，在训练和分类过程中，对隐单 元p 的输入为： h ，= 孝。 ( 3 1 5 ) n - i 相应的，隐单元p 的输出为： n f ，= g 。( 办，) = g ( w p 。孝。) h = l ( 3 1 6 ) 大连理工大学硕士学位论文 因此对输出单兀彤的输入为： 以= o = g l ( 鼻) ( 3 1 7 ) 最终产生的输出为： 厶= ( 以) = g ：( g ；( 彘) ) ( 3 1 8 ) 现在，假设给定一组输入向量 f 7 ) 二cr 材及相应的理想输出 d 。) 二lc r m ，并记 f 7 ) 乞c r m 为相应的网络实际输出，则误差函数为： e ( 形，w ) 兰吾壹8 0 ，一孝霄= 吾害兰 o l - - 9 2 ( 善p 蜀( 兰幺) ) 】2 ( 3 1 9 ) ，l i of = lm = l p ln = l ( 3 ) 学习过程：权值矩阵和w 的确定应使误差函数e ( w ，w ) 达到极小。一个简单 而又常用的方法是梯度下降法。取当前权值的该变量为： a e 嵋2 叩瓦 = 7 7 ( d 7 一善7 ) g ：( 联) ( 3 2 0 ) = 7 二 二= ( 一孝。) g ：( 层：) ( 3 2 1 ) 其中刁 o 为学习率，而联= 是第川个输出层单元的线性输入。进一步，我们 可以得到当前权值的该变量为： 峨一刁薏一叩丢j 嚣芒峨一刁瓦一叩刍可茁 = 7 7 ( d 一孝) 彰( 职) 硝( 嘭) 影 = 7 7 j 叩孙, j 胁j ( 3 2 2 ) = 刁彰g 印刷体数学公式上下标的一种判别方法 其中 砟= x , w p n 亭n ，6 卜g ：叫) i ( 3 2 3 ) 综合以上讨论可见，应用b p 网络时，所处理的信息( 工作流程) 是前向传播的( 见式 ( 3 1 8 ”；而在网络学习阶段，是用误差的向后( 或称反向) 传播来逐层修改权值( 见式( 3 2 0 ) 和式( 3 2 2 ) ) 。 ( 4 ) 活化函数的选取：活化函数g ( x ) 常选为符号函数的光滑逼近，即s i g m o i d 型函 数，例如： g g ) _ 1 + e x 二p ( 一- 2 f l x ) ( 3 2 4 ) g o ) = t a n h 触( 3 2 5 ) ( 5 ) 初始权值的选择：初始权值w o ，w o 通常选取为接近零的随机数。太大的处置 可能使系统过早的陷入饱和区，不利于进一步学习。例如，对于s i g m o i d 型函数g ( x ) 当 l x i 较大时，g o ) - 0 ，这可能导致网络不可训练。 ( 7 ) 学习速率的选择“在梯度下降法中，学习速率( 或步长) 叩如果太小，则收敛速度 很慢；如果太大，又可能引起迭代解的剧烈振荡。r 的选择并非易事。下面的所谓的自 适应规则是常用的。在每一步( 或若干步) 权值迭代更新后，给当前的叩值一个改变量理： ，7 = l 却a t ，, 矿f 篮a i l ? o ，掣是正的或负的( 表示误差函数随权值分量。的 d w 一 增大而增大或减小) ，则相应地w ，。o ) 减小或增加。a 1 时，式( 3 2 8 ) 容易发散。a 0 时， a w 。可能产生不合理的震荡。总之，通常t 2 取为( o ，1 ) 内f 常数。 大连理j 亡大学硕士学位论文 3 2 2 b p 网络性能试验 在文献f 3 5 1 中，他们用b p 网络做了字符分类性能的试验。试验选用微软w o r d 数学 公式编辑器中的6 4 个常用数学符号，形成6 4 个1 6 x 1 6 x 2 ( 以象素为单位) 的b m p 文件， 对文件中的符号数据部分按行展开形成6 4 个2 5 6 维向量，构成训练样本集c 。在c 上 分别按一定比例随机污染( 原数据1 变为o ，原数据0 变为1 ) ，形成4 个检测样本集 互aa1 , 2 ，3 ，4 ) ，污染率分别为5 ，1 0 ，1 5 和2 0 ，每个检测样本集包含6 4 0 个样本。 试验选取3 层b p 网络，其中输入层为2 5 6 个神经元，输出层为6 4 个神经元，隐层神经 元的数目在实验中进行调整，以考察该变化对网络性能的影响。隐层和输出层活化函数 g ：( ) 和g ：( ) 统一取式( 3 2 4 ) 。定义误差函数 五t w , 功善丢砉1 1 d 一手1 ；云1 刍i 磊m 【0 j - g ( 荟p g ( 薹) ) 】2 ( 3 2 9 ) 记k 为为适当选择的收敛判别标准( 误差界) ，对于输入样本孝，如果 i i o ，一亭刈s 誓，v 一】， ( 3 3 0 ) 则定义该样本收敛。当全部样本都收敛时，网络停止迭代。为降低误识率，引入拒识机 制，设置一个拒识因子0 ，定义拒识标一( 6 1 一) ，b = g l b 2 分别为输出层神经元的最 大输出和次最大输出。当s0 时，该样本被拒。定义网络识别的正确率母，错识率凡， 和拒识率r 一，分别为： 尺，= ( 正确识别样本数样本总数) 1 0 0 ： r 。= ( 错误识别样本数f 4 本总数) 1 0 0 ； ( 3 3 1 ) 也，= ( 拒识样本数样本总数) 1 0 0 。 对参数和r 及隐单元数目取不同数值进行组合，选取网络性能较好的一组参数 ( 卢一0 0 5 ，口t0 6 ，叩l i b0 7 ，k o 1 ) 进行试验，结果见表3 1 。 表3 1b p 网络性能( ) t a b 3 1b pn n sp e r f o r m a n c e ( ) 印刷体数学公式上下标的一种判别方法 可以看出，随着污染率的增大，网络性能急剧下降。原因是用单一的b p 网络进行 6 4 类样本的分类，必然造成网络结构复杂，训练时间过长，也不利于网络中各个参数迅 速有效的调节。 3 3 识别实验 为了提高网络分类性能，我们采用一种多级神经网络模型( m s q 【3 6 1 。实际试验中 采用二级网络，第一级使用s o f m 网络进行数学符号的粗分类，按符号的拓扑特征把它 们先分成若干子类，即实现把大问题化为小问题；第二级使用多个子b p 网络，利用b p 网络较强的分类性能对第一级网络中已分出的各类再进行细致分类，进而完成对数学符 号的识别。 图3 2 多级神经网络进行分类 f i g 3 2c l a s s i f i c a t i o nw i t hm s n n ( 1 ) 实验数据：试验选用l a t e x 中常用的数学符号 3 7 1 ，共1 8 5 个( 见附录a ) ，形成 1 8 5 个6 4 x 6 4 x 2 的b m p 文件，并且每个字符选择1 4 种不同字体，这样总共样本数目为 2 5 9 0 。对文件中的符号数据部分进行预处理，特征提取和选择后得到2 5 9 0 个1 8 维向量 作为识别模块的输入。 ( 2 ) s o f m 网络的粗分类：在s o f m 中，我们设a 是由3 5 个神经元组成网格，所 有神经元排列成环形结构，每个神经元只受前后两个神经元的影响。取距离函数为阶梯 函数( 见图2 5 ( a ) ) ： 慨；三纛舭 其中，7 ) 和( 七) 是与迭代次数k 相关的函数。网络的训练采用两阶段学习方法： 自组织( 粗分类) 阶段。这一阶段一般需要上千次迭代，使训练样本经网络映射后 得到位置大致正确的获胜单元。开始时应该在获胜单元的较大调整邻域( 即使得 大连理i e 大学硕士学位论文 七，k ) 一0 的那些邻点j ) 内修改权值，然后随着迭代步数k 的增加而逐渐收缩调整邻 域。这样，随着学习过程的进行，每个输出单元的“专业化程度越来越高，并呈现出 有序性。我们取初值，7 ( 0 ) = 0 9 ，a ( 0 ) = 1 0 ，最大迭代次数k - 1 0 0 0 0 ，7 ) 一，7 ( 0 ) ( 1 一k k ) 和 ) l i r at , ( o ) o - k k ) 。 收敛( 细化) 阶段。在这一阶段，得到更加精细和准确的分类。在这一阶段 ，7 ) 暑0 0 0 5 ， ) 暑0 。此时 耙，七) 的支集根本不考虑邻域的情况。 经过迭代训练后，将1 8 5 类字符分成3 5 大类，得到的分类结果见附录b 。从表中 可以看出外形相似的字符被分在一类里，如5 、6 、9 总被分在一组，v 、 v 、 么、 人总被分在一组。另一方面，相邻的两个神经元所分到的字符也 有相似性，如l 同时被分到了第1 9 、2 0 、2 1 组。此外，4 被分到第9 组和第3 2 组，这说明第4 个神经元和第3 2 个神经元的空间距离是相近的，可见神经元的分布结 构更适宜采用二维网格结构。 ( 3 ) b p 网络的细分类：s o f m 分类后得到3 5 类，我们相应的定义3 5 个b p 网络， 这样可以降低b p 网络的