（计算数学专业论文）英文科技文档中粘连下标的一种判定方法.pdf

大连理工大学硕士学位论文 摘要 随着计算机的普及，使用计算机处理日常工作和存储信息成为人们更多的选 择对图像格式文档文件的识别与检索引起了广泛的关注适用于普通印刷体文 档图像的o c r 系统已经比较成熟，对粘连字符的处理成为其识别正确率的主要影 响因素之一，科技文档中存在较多的数学表达式，它们是由特殊符号及字符组成 的比较复杂的结构体数学表达式中字符之间存在着二维关系，这使得粘连字符 的处理成为正确识别数学表达式的一个重要部分为此，本文作了一些尝试，给出 了一种粘连下标的判定方法本文主要包括以下内容： 本文第1 章简单介绍了神经网络方面的一些知识，概述了数学表达式识别系 统的一些流程，包括数学表达式的定位，识别，重组并且列出了粘连字符检测，分 割方面的主要方法 在第2 章。分析了粘连下标的主要特征，给出了一种新的投影方法基于此，总 结出了一种粘连下标的判定方法：首先，通过上述投影方法获取字符或者符号的 轮廓信息。然后通过粘连下标特殊的轮廓特征迸行判别最后，给出了数值实验。 表明该方法能够在不同类型字符中能够很好的检测出粘连下标 针对粘连下标判定方法中参数选取的问题，第3 章中给出了一种模糊神经网 络方法该方法将第2 章方法的参数作为权值，通过学习来获得比较合适的数值 当然这种模糊神经网络方法也可以直接用来判定粘连下标 第4 章考虑到粘连字符出现的概率问题，针对实际科技文档图像作了数值实 验主要是在数学表达式定位的过程中，运用粘连下标判定方法，检测文档中的粘 连字符并标记出来 关键词：粘连下标；轮廓投影；模糊神经网络；数学公式定位；粘连字符分割 大连理工大学硕士学位论文 am e t h o df o rd e t e c t i n gm e r g e ds u b s c r i p t si ne n g l i s h s c i e n t i f i cd o c u m e n t a b s t r a c t c o m p u t e r - a i d e dd o c u m e n t - h a n d l i n gs y s t e m sh a v eb e e nw i d e l yu s e d t h e r eh a s b 嘲g r o w i n gi n t e r e s tt or e c o g n i z ea n d r e u s e v ed o c u m e n ti m a g e s o p t i c a lc h a r a c t e r r e c o g n i t i o n ( o c r ) c o m e si n t ob e i n gt od ot h i s j o b a tp r e s e n t , t h er e c o g n i t i o nr a t i oo f p r i n t e dd o c u m e n ti m a g e sh a sa c h i e v e dah i g hl e v e l t h es e g m e n t a t i o no f t o u c h i n gc h a r - a c t a r si sb e c o m i n ga ni m p o r t a n tf a c t o rt oi m p r o v et h er a t i o i ns c i e n t i f i cd o c u m e n t s ， t h e r ea r em a n ym a t h e m a t i c a le x p r e s s i o n sa n dt h e s ee x p r e s s i o n sc o n s i s to fs p e c i a lc h a r - a c t e r sw i t hc o m p l i c a t e ds t r u c t u r e t h e r ea r et w o - d i m e n s i o n a lp o s i t i o nr e l a t i o n s h i p s a m o n gs y m b o l so ft h e s ee x p r e s s i o n s t h er e c o g n i t i o no fm e r g e dc h a r a c t e r sb e c o m e s a l li m p o r t a n tp a r ti nx e c o g n i z i n gt h e s ee x p r e s s i o n s t ot h i se n d ，t h i st h e s i sp r e s e n t sa m e t h o dt od e t e c tm e r g e ds u b s c r i p t s t h et h e s i si so r g a n i z e da sf 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 fn e u r a ln e t w o r k s ，a n di l l u s t r a t e st h ew o r k f l o wo f m a t h e m a t i c a le x p r e s s i o n sr e c o g n i t i o ns y s t e m ，w h i c hc o n t a i n st h ee x p r e s s i o n s e x t r a c t i o n ，r e c o g n i t i o na n d r e c o n s t r u c t i o n t h e m e t h o d s o f m e r g e d c h a r a c t e r s d e t e c t i o n a n ds e g m e n t a t i o na a l s or e v i e w e d c h a p t e r 2 a n a l y z e ss o m e f e a t m e s o f m e r g e ds u b s c r i p t s a n d p r e s e n t s a n e w p r o j e c - t i o nm e t h o d b a s e do nt h i s ，ad e t e c t i o nm e t h o di sg i v e n h r s f l y , t h ef r i n g ep r o j e c t i o n o fc h a r a c t e ri m a g ei sf e t c h e d s e c o n d l y , t h em e r g e ds u b s c r i p t sa r cd e t e c t e db a s e do n t h es p e c i a lp r o j e c t i o ni n f o r m a t i o n f i n a l l y , as i m u l a t i o ni sp r e s e n t e dw h i c h s h o w st h a t t h ed e t e c t i o nm e t h o dw o r k se f f e c t i v e l y f o rt h es e l e c t i o no fp a r a m e t e r si nt h ed e t e c t i n gm e t h o d ah n do ff u z z yn e u r a l n e t w o r k sm e t h o di sd i s c u s s e di nc h a p t e r3 t h i sm e t h o dc a n b eu s e dn o to n l yt oc h o o s e p r o p e rv a l u eo ft h e s ep a r a m e t e r sb ys e t t i n gt h e ma sw e i g h t so fn e t w o r k s ，b u ta l s ot o d e t e c tm e r g e ds u b s c r i p t si n d e p o n d e n f l y , c h a p t e r4c o n s i d e r st h ep r o b a b i l i t yo fa p p e a r a n c eo fm e r g e ds u b s c r i p t si n s c i e n t i f i cd o c u m e n t , a n ds h o w st h es i m u l a t i o nr e s u l t sf o rs o m er e a ld o c u m e n ti m a g e s 一一 英文科技文档中粘连下标的一种判定方法 t h es i m u l a t i o ni sb a s e do nm a t h e m a t i ce x p r e s s i o n se x t r a c t i o na n dm a r k u p st h em e r g e d s u b s c r i p t si nt h es o u r c 七i m a g e s k e y w o r d s ：m e r g e ds u b s c r i p t ；f r i n g ep r o j e c t i o n ；f u z z yn e u r a ln e t w o r k s ；f o r - m u l ae x t r a c t i o n ；m e r g e dc h a r a c t e r ss e g m e n t a t i o n 一一 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的 研究工作及取得研究成果。尽我所知，除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也 不包含为获得大连理工大学或者其他单位的学位或证书所使用过的 材料。与我一同工作的同志对本研究所做的贡献均已在论文中做了 明确的说明并表示了谢意。 作者签名 衅 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文 版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅本人授权大连理工大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印 或扫描等复制手段保存s n # e 编学位论文 作者签名：逸至翊臣 导师签名：羝导师签名：望逖 2 - - 口7m 上月丛日 一3 9 大连理工大学硕士学位论文 第一章绪论 1 1 人工神经网络概述 人工神经网络( a r d f i c i a ln e u r a ln e t w o r k s ，简写为a n n s ) ，简称神经网络，是对 人脑或自然神经网络( n a t u r a ln e t w o r k ) 某些基本特性的抽象和模拟，用于模拟大 脑的若干机理与机制，实现某个方面的功能神经网络由大量的处理单元( 称神经 元) 通过广泛地相互连结而成，具有高度的并行性和高速的信息处理能力 人工神经网络的研究始于4 0 年代初w s m c c u l l o c h 和w p i t t s 于1 9 4 3 年提 出了m - p 模型，第一次建立用数理语言描述来脑信息处理过程的模型5 0 年代 末期，r o s e n b l a t t 提出著名的感知器模型同时神经网络研究进入了首个高潮期 然而，1 9 6 9 年m m i n s k y 和s p a p e r t 编写的 p e r c e p t r o n 从理论上证明了单层 感知器能力的有限性，诸如不能解决异或问题，使得神经网络研究为很少人关 注幸运的是j j h o p f i e l d 于1 9 8 2 年引入能量函数。来理解一种带有对称突触联 接的反馈网络的动力学计算特性【l 】这种网络因此得名h o p f i e l d 网络，引起了研 究神经网络的又一次热潮接着，1 9 8 6 年r u m e 蝴m c c l e i l a n d 合著的 p a r a l l d d i s t r i b u t e dp r o c e s s i n g ：e x p l o r a t i o ni nt h em i c r o s t r u c t u r e so fc o g n i t i o n 两卷书出 版，对神经网络的进展起了极大的推动作用尤其是，r u m e l h a r t 提出了多层网 络b a c k p r o p a g a t i o n 法或称e r r o r p r o p a g a t i o n 法【2 】，成为当今应用最广泛的前向神 经网络的学习方法之一 1 。1 1 神经网络的结构 神经网络的结构主要包括神经元的排列方式。神经元间的连接方式，神经元 的输入和输出，网络权值的学习规则一般来说，神经网络中的神经元捧列为输入 层，输出层及若干中间层( 或称为隐层) 输入层的神经元主要是接收外界输入的 信号；隐层的神经元被封装在网络内部。主要用于增加网络的能力；输出层的神经 元负责向网络外输出信号 神经网络中的神经元通过权值互连，这种连接具有方向性，但一条连接不能 是双向的一个神经元的输入由所有输入连接累加获得；一个神经元的输出经过 与权值的某种处理来作为后续神经元的输入分量神经网络的连接可分有如下分 类： 英文科技文档中粘连下标的一种判定方法 按照层关系来分 层间连接( i n t c r - l a y e rc o n n e c t i o n s ) 只有神经网络不同层之间的神经元之间 存在连接： 层内连接( i n t r a - l a y e r c o n n e c t i o n s ) 神经网络同一层内部的神经元之间存在 连接 按照连接程度来分 全连接( f u l l yc o n n e c t e d ) 神经网络所有神经元之间都存在连接： 部分连接( p a r t i a l l yc o n n e c t e d ) 神经网络只有部分神经元之间存在连接 按网络中信息流动的方向来分 前馈连接( f e e df o r w a r dc o n n e c t e d ) 用于层间连接，第i 层神经元的输出与权 值处理后作为第j 层神经元的输入，但躺层神经元的输出不做为第i 层的输 入： 双向连接( b i - d i r e 斌i o n a lc o n n e c t e d ) 用于层间连接，第i 层神经元的输出与 权值处理后作为第j 层神经元的输入，同时第j 层神经元的输出也做为第i 层 的输入； 层级连接( h i e r a r c h i c a lc o n n o t e ) 用于层间连接，神经元的连接只发生在网 络的第i 层和第i + 1 层之间，不存在跨层连接； 共振连接( r e s o n a n c ec o n n e c t e d ) 用于层间连接，网络中的神经元之间全连 接，而且信息在层闻反复传递，直到满足某些条件后才输出； 递归连接( r e c u r r e n tc o n n e c t e d ) 用于层内连接，同层神经元之间全连接或部 分连接，同层神经元的输入和输出不断互相影响，直到满足某些条件后才输 入到下一层： o n c e n t e r o f f - s u r r o u n d 连接用于层内连接，某个神经元与同一层与其相邻 的神经元之间有兴奋性连接( 例如连接的权值为正数) ，而与同层的其他神经 元之间有抑制性连接( 例如连接的权值为负数) 一2 一 大连理工大学硕士学位论文 神经网络的学习过程是神经网络的一大特点，它是按照某种规则，逐步调整 网络神经元间权值，以满足输入输出之间关系要求的过程一般来说，神经网络的 学习过程可以分为以下三种： 有教师学( s u p e r v i s e dl e a r n i n g ) 给定一族成对的输入和理想输出作为样 本集，网络根据理想输出与实际输出之间的误差来不断调整权值，直到实 际输出与理想输出之间的误差减小到满足要求为止； 无教师学习( u n s u p e r v i s e dl e a r n i n g ) 不给定网络的理想输出，网络按照输入 数据的某些统计意义上的规律不断调整权值甚至网络结构，最终体现出输 入数据的某些统计意义上的特征。这种方法有自组织性； 强化学( u n s u p e r v i s e dl e a r n i n g ) 同样不给定网络的理想输出，但对网络的 输出做出评价，如奖或惩网络通过不断强化受奖励的权值更新模式调整权 值，直到实际输出满足要求为止 神经网络按照上述的学习方式，存在着以下几种主要学习规则： 丑e 6 6 s r u e d o n a l do l d i n gh e b b 在 t h eo r g a n i z a t i o no f b e h a v i o r ) 【3 】中提出了神经元 之间连接强度变化的规则，主要可以描述为：如果两个神经元都处于兴奋状态，那 么它们之间的突触连接强度将会得到增强，即后来的h c b b 学习法则： t 协= , 7 0 j 翰 t h ed e l t ar u l e d e l t a 规则源自是h e b b 学习规则，是连续地更改网络权值，使网络对输入模 式的输出尽可能地接近其期望输出主要运用最小化实际输出与期望输出的均方 误差来调整权值也称最小均方学习规则( l e a s tm e a ns q u a r el e a r n i n gr u l e ) ： 嘶 = 7 ( d 一o j ) 戤 ( 1 2 ) k o h o n e n jl e a r n i n gl a w t e u v ok o h o n e n 提出的模仿大脑皮层活动的拓扑网络结构，其中的神经元之 间相互竞争，胜者获得学习机会获胜的神经元在更新自己权值的同时，抑止其它 一3 一 英文科技文档中粘连下标的一种判定方法 神经元的活动： i l ，m + 1 ) = 九( d 0 。，女) g “) 一i - ，m ) ) ( 1 - 3 ) h o p f i e l dl a w 1 9 8 2 年j j h o p f i e l d 提出了由非线性元件构成的全连接型单层反馈系统 的h o p f i e l d 神经网络，引入了能量函数方法，具体的学习规则是通过能量函 数e ( w ) 在网络迭代运行过程中不断地降低能量，最后趋于平衡状态，以达到学 习的目的： 掣；瑚) + 差嘶删卅m ( 1 4 ) 1 1 2 神经网络的特性与应用 神经网络是由简单的神经元组成的复杂体系，它具有存储和应用经验知识的 自然特性它更有其突出的优点： 1 强大的自适应学习能力 神经网络具有调整权值以适应外界变化的能力当它在一个时变环境中运行 时，网络可以设计随时间变化的权值用于模式识别，信号处理和控制的神经网络 与它的自适应能力耦合，就可以变成能进行自适应模式识别，自适应信号处理和 自适应控制的有效工具； 2 分布存储和容错性 当一个神经网络输入一个激励时。它要在已存的知识中寻找与该输入匹配最 好的存储知识为其解当然在信息输出时，也还要经过一种处理，而不是直接从记 忆中取出这种存储方式在部分信息不完全，或者说丢失或损坏甚至有错误的信 息时。仍能恢复出原来正确的完整信息。具有一定的鲁棒性 3 高度的非线性全局能力 神经网络的神经元可以是线性或非线性的非线性神经元相互连接组成的神 经网络具有非线性性，而且这种非线性分散在神经网络的各处，可以用来解决许 多非线性问题 4 高度的并行性 神经网络的并行处理能力是通由不同个数的神经元以及它们之间的连接形 式和方法来表现的它有较好的耐故障能力和较快的总体处理能力，这特别适于 一4 一 大连理工大学硕士学位论文 实时控制和动态控制 5 可以硬件实现 神经网络不仅能够通过软件而且可借助硬件实现并行处理这使得神经网络 具有快速和大规模处理能力的实现网络由于学习和适应，自组织，函数逼近和大 规模并行处理等能力，神经网络具有用于智能控制系统的潜力 神经网络具有其它方法所不具有的性能，能成功地解决其它一些方法解决不 了的问题，已经被用来解决各种复杂的，模糊的，不完备模式问题最常见的有下 面几类： 预测通过学习现有过去的样本资料，建立对应关系。由输入值获得输出来 预测未来或者可能结果。如股市预测，天气预报，疾病诊断； 分类判断输入的模式，如字符识别，语音识别等模式识别； 数据处理联想：从受损模式中恢复出原始数据，如图像恢复；过滤：平滑输 入信号，如图像或语音信号的去噪；概念化：通过分析输入模式，推理数据之 间的关系，如数据挖掘； 智能控制神经网络具有非线性映射能力，可以对不确定系统自适应和自学 习： 优化计算与决策由目标函数和约束条件建立网络的能量函数，用网络状态 的动态方程驱动网络运行，当系统稳定时获得最优值 1 2 数学表达式识别系统 1 2 1 数学表达式识别系统概述 光学字符识别( o c r ) 是对使用光学方法得到的文字或字符图像进行分析。识 别，最后转换成计算机内码的技术它融合了图像处理，识别，文本理解与还原，表 格，票据处理等技术于一体，涉及到模式识别，人工智能，模糊数学，组合论，信息 论，计算机，语言文字学，心理学等多个学科o c r 系统可以克服人工输入费时费 力的缺点，当前的o c r 系统对手写【5 】，印刷体文本【6 i 7 】都有很高的识别率，已经 广泛应用于办公自动化，快速录入等领域 一5 一 英文科技文档中粘连下标的一种判定方法 数学表达式广泛地存在于大量的科技文档中，是科技文档的重要组成部分 很多文档一旦失去了数学表达式，将变得难于理解，甚至毫无意义数学表达式一 般由特殊符号，希腊字母，英文字符和数字组成，这些符号通常通过特定的格式输 入到计算机，输入复杂度远远大于普通的文本输入a n d e r s o n 8 1 在1 9 6 8 年提出了 印刷体数学表达式识别的问题近年来，对数学表达式的识别问题的研究逐渐升 温 9 - 1 6 数学表达式的识别系统一般包括数学表达式的定位。数学表达式中字 符符号的识别，数学表达式的结构重组三个部分 1 2 2 数学表达式的定位 数学表达式的定位就是在科技文档图像里面准确地提取数学表达式。以期后 续识别与重组，是数学表达式识别与结构重组的必要步骤。也是科技文档图像实 现全自动识别的一个关键步骤目前。数学表达式定位方面的文献还不多 在科技文档图像中，数学表达式可以分为独立行表达式和内嵌行表达式两种 类型独立行表达式是数学表达式单独成行。行内没有其他的普通文本；内嵌行表 达式是指文本行内出现的数学表达式一般的数学表达式定位方法都将两者分开 来考虑l 船等人【9 】针对独立行表达式利用行间距，行高，字符密度等信息进行提 取；针对内嵌行表达式，采取先搜索重点数学符号，然后将这些符号合并组合用于 提取表达式的方法f a t e m a n 等人 1 7 】将独立行表达式和内嵌行表达式统一起来 考虑，将存在于文档图像中的所有符号分成数学符号和文本两类，搜索文档图像 中的数学符号，然后通过一定的手段将所有的数学符号适当组合以得到数学表 达式基于大量符号的统计数据，k a c e m 等人【1 8 】提出了一种有效的定位方法这 种方法将出现在文档图像中的连通成分分为数学符号和非数学符号两类。合并适 当的连通成分成行依据一些特征提取出独立行表达式然后对剩余的含有数学 符号的行，以数学符号为中心扩展出内嵌行表达式 以上方法大多考虑的只是数学表达式和纯文本行并存的情况，而很多科技文 档中，并存着数学表达式。文本，表格以及图片等多种对象而且，利用文档中数学 符号统计数据的某些方法对中文文档无效李峰等人 1 9 1 给出了一种能够处理这 些问题的数学表达式定位方法。这种方法统一考虑独立行表达式和内嵌行表达 式该种方法首先依据连通成分确定文档行信息，然后找出由尽可能多的文字组 成的行( 即密度最大的行) 作为基准行，获得基准字符高度；然后根据基准字符高 度合并非正常行，排除具有封闭边界的表格和图片：接着获取行垂直连通成分个 数投影，连通字符间距等特征，获取行内的数学符号和字符。组合扩展成数学表达 一6 一 大连理工大学硕士学位论文 式，以期提取出数学表达式这种方法没有外在统计数据的要求，也无需建立单独 的数学符号库，但是这种方法对图片和表格的排除还不够完善 1 2 3 数学表达式的识别和重组 数学表达式的识别是将数学表达式中的字符及特殊符号识别出来；数学表达 式的重组就是将识别出来的字符及特殊符号依据数学表达式的二维结构组织起 来，使其成为具有具体含义的可以正确编辑的表达式 豳 甄 惑 随爨黼 澜国隧滋渊 觜缝謦可爱戮微分数线翟擞蛩 图1 1上标域和下标域的分类 f i g 1 1c l a s s i f i c a t i o no fs u b s c r i p ta n ds u p e r s c r i p td o m a i n s 作者所在的教研室在符号识别方面采用自组织特征映射( s o f m ) 神经网络 与b p 神经网络组合构成的符号识别嚣首先通过s o f m 网络将1 8 5 个常用数学符 号及字符分成3 5 类( 见附录c ) 然后在具体的每一种类中用b p 网络【2 3 】来确定识 别到具体的字符上面其中s o f m 网络分类包括两个阶段：自适应阶段和细化阶 段自适应阶段是网络通过自适应学习使得输入模式映射到大体正确的输出模 式所以这一步又称为粗分类阶段细化阶段是进一步的更加准确地使得输入模 式正确的收敛到输出模式，又称为收敛阶段 数学表达式的符号与字符经过神经网络的识别，得出的是一组毫无意义的 符号与字符序列，必须通过重组才能成为意义的数学表达式针对印刷体数学表 达式的重组问题，候利昌【6 】提出了一种基于l l ( t ) 文法【2 6 1 的结构分析法这种结 构分析方法首先根据上下标位置的位置关系，利用域的概念将数学结构体分成五 类( 见图1 i ) ，并且分别给出了上下标域的确定方法：然后定义了符合u 1 ) 文法的 表达式构成规则，并构造了预测分析表：接着，给出了结构分析算法，这个结构分 析算法以预测分析表为核心，特别构造了一个符号栈，用来存放搜索到的待分析 的数学字符与符号：最后将其转换成可编辑的l a t e x 文本格式。 一1 一 英文科技文档中粘连下标的一种判定方法 表1 1 从吼到以+ l 的代价规则 c o s t ( a l ，吼+ 1 )a i + l 在a 。正下方啦+ i 在a d t _ ；5 下方 i0 4 + l 为白像素 ol i 啦+ 1 为黑像素 1 01 0 j 1 3 粘连字符分割与检测 1 3 1 粘连字符分割方法 印刷体文档图像文本的o c r 识别率已经达到很高的水平，使得粘连字符的 正确识别与否成为影响识别率的个重要因素粘连字符分割成为近些年研究 比较活跃的课题 2 7 - 3 1 研究者尝试用各种方法分割粘连字符，其中最短路径方 法( s p m ) 2 7 应用广泛侯【6 】，朱1 2 5 1 给出了新的基于s o f m 神经网络的分割方法 下面将对这两种方法进行简单的介绍： 最短路径分割方法 最短路径分割方法的思想是在一定规则下的路径集合里选取一条代价 最小的路径，将其作为粘连字符分割线的方法设最短路径方法考虑的路径 为p = a l a 2 ，则p 需满足下面的规则： 路径尸的起始点a 1 在图像的第一行，终点在图像的最后一行 路径p 中节点a f 必须在其前一节点啦一1 所在行的下一行，并且它们邻接( 这里 的邻接为8 邻接) 其中0 i n 文献1 2 7 1 中给出的路径代价可用表达式( 1 5 ) 来表示 n l f ( p ) = c o s t ( a , ，叭1 ) ( 1 5 ) t ；1 其中，两邻接点之间的代价值见表1 3 1 那么，最短路径分割方法寻找路径可以总 结如下： 求取路径p ，s t f ( p 。) = m i 礼f ( p ) ( 1 6 ) 一8 一 大连理工大学硕士学位论文 其中，p 在满足上述规则的路径集合里面取 关于路径代价的算法在这里给出一个例子，图1 2 中显示一条符合规则的路 径只；12 一8 ，运用( 1 5 ) 可计算路径的代价为 j# 1 ；罐 。5 2 ： * 3 二驾 ，。_ 4 擎。 # 5 嚣 6 # 、 曩 ，。蒜 竣 8 豁 图1 2 一个路径例子 f i g 1 2o n ep a t hf o re x a m p l e f ( p 1 ) = 1 0 + l + 1 0 以+ l + o + 1 0 扼+ l = 1 3 + 2 0 v 5 ( 1 7 ) 最短路径方法可以根据不同的文档粘连情况选择定义比较合适的代价方案， 算法比较简洁，能够在一定程度上调节切割路径的选择，但计算切割代价的方式 具有局部性 s o 孽m 网络分割方法 s o f m 网络也称自组织映射网络，可以自适应地以拓扑有序的方式建立一种 输入到输出的离散映射。这种映射是将任意维的输入模式转换成一维或者二维的 输出模式s o f m 网络的输出单元是相互独立的输出模式，它们通过竞争以求被 激活这种激活的排他性的s o f m 网络保持输入模式之间的相似关系 s o f m 的网络结构见图1 3 ，设网络的权值矩阵为w 网络的输出单元 为，m = 1 ，2 ，一，m ，网络输入为z = ( z l ，z 2 ，z n ) ，网络的权值矩阵 为w = w 赢) m x n ，网络的输入输出关系为 舻t 辫n ( 1 8 ) 、 j o ， l = w 赢，m = 1 ，2 ，m l n = 1 英文科技文档中粘连下标的一种判定方法 图1 3 $ o f m 网络结构 f i g 1 3s t r u c t u r eo fs o f m 其中乳为获胜单元 权值修改规则为： 嘴1 = w 嚷+ ( d ，加，j c ) ( z ( 姊一像) ( 1 9 ) 其中d 。为单元d ， l 与获胜单元d 。的距离， ( 的为距离函数，具体可参考【6 】 网络的学习过程如下： s t e p l 初始化网络安排输入样本顺序，初始化权值矩阵： s t e p 2 检测相似性根据式( 1 8 ) 计算输入样本的获胜单元； s t e p 3 更新权值根据式( 1 9 ) 修改权值，并归一化权值矩阵的每一行； s t e p 4 检测收敛性根据某种准则判断迭代是否收敛，若是。则学习停止；否 则跳转s t e p 2 基于s o f m 的字符分割方法是通过学习，聚类白像素，获取白像素的聚类 点，通过聚类点找出一条合适的分割路径为了避免聚类点之阃的相互吸弓i ，文 献【6 依据f i s h e r m a n sr u l e 3 2 ，更改权值修改规则为： 姚( 1 ) 刮砷啦，喇n 吲d ) ( 1 1 0 ) i w 0 ( + 1 ) = 西。w ： + 1 ) ，m c 其中，表示获胜单元北对输出单元的影响因子，7 ( 七) 为步长函数，f 扯) 是输入 样本矢量 一l o 大连理工大学硕士学位论文 基于s o f m 的方法能够在全局上寻找最佳的分割路径，但是分割方法速度比 较慢结合最短路径分割方法与s o f m 分割方法的优点，陈 3 3 1 提出了一种新的方 法，对印刷质量较差，粘连较严重的样本效果较好，但同样也有速度上的问题 1 3 2 粘连字符的检测 一般的识别系统对粘连字符的处理见图1 4 先对其进行识别，如果识别器无 法识别，则认为其为粘连字符，对其进行分割，然后重新识别这样做有一定的道 理，因为正常的字符占需识别字符的绝大部分，是识别系统的重心但是这样做会 使得一部分粘连字符被误识，并且在字符分割的时候不清楚粘连字符的具体粘连 情况，譬如是多字符粘连还是双字符粘连，影响到分割的效果特别是在科技文档 图1 4字符识别流程图 f i g 1 4f l o wc h a r to f c h a r a c t e rr e c o g n i t i o n 数学表达式的识别中，由于数学符号与字符及其自身之间存在着二维关系，不正 确的识别轻则只是本身字符的错误，重则使整个数学表达式的结构变得混乱并 且数学表达式本身由于结构的原因，时常会出现粘连的情况，这使得对粘连字符 的处理成为数学表达式识别的一个重要部分 为避免粘连字符被误识，【3 4 提出了数学表达式中粘连字符的一种检测方法 这种检测方法是基于识别的检测方法，它是先将待识字符连通体初步识别到某 一字符种类a ，然后比较该连通体的特征集与种类a 的标准特征集对比，如果某些 特性不一致，则认为待识字符连通体为粘连字符例如，如果一个粘连字符连通 体丁2 ”被识别成了“r ，而它的一些特征，如纵横比，轮廓特性，与种类r ”的这些 方面的标准对比，如果出现不同，则将“，2 ”作为候选粘连字符体同时【3 4 】给出了 英文科技文档中粘连下标的一种判定方法 一种数学表达式中粘连字符的分割方法。 针对数学表达式中粘连字符的处理，基于识别的检测方法能够在一定程度上 减少粘连字符对数学表达式的影响但是无法检测出粘连字符的种类，无法预知 粘连字符的二维特征如果先将粘连字符检测出来，并且能够判断粘连字符的二 维结构，将有利于选择合适的分割方法以达到最佳的分割效果。同时也有利于识 别数学表达式的结构就此方面，本文作了些尝试，给出了粘连下标的一种判定方 法当然这种方法也可以扩展到其他方面粘连的判定。如粘连上标 1 4 本文的主要工作 本文首先简单地介绍了数学表达式识别系统的一些知识和现状：接着，针对 英文科技文档中数学表达式粘连检测的问题，本文提出了一种粘连下标的判定方 法该方法依据一种新的投影方法，根据粘连下标的轮廓特征来判定一个字符连 通体是不是粘连下标；并且。由该判定方法建立了一个模糊神经网络模型，这个神 经网络除了能够很好的处理判定方法的参数选取问题，本身也可以用来判定连通 体是否是粘连下标；最后，基于数学表达式的定位，运用实际文档图像。对判定方 法进行了数值实验。 一1 2 一 大连理工大学硕士学位论文 第二章粘连下标判定方法 带下标的数学字符作为数学表达式的重要组成部分。能否被正确地判定直接 影响到数学表达式的定位和识别在英文科技文档图像里面，数学字符与其下标 由于位置关系常常会出现粘连的情况这给数学表达式，特别是文本行公式的定 位，带来比较大的遗漏问题；同时，由于数学表达式是二维结构，而带下标的数学 字符又是多数数学表达式重要的组成体，粘连将会造成数学表达式识别时二维结 构的误识由此，如果有一种简洁的方法能够在数学表达式的定位或者识别中先 对字符进行预判，将会减轻这些影响在这里我们给出了一种判定方法 本章的第1 节概括了粘连下标的一些特征以及判定方法的基本原理据此，在 第2 节我们得到了具体的判定方法最后，第3 节应用判定方法进行了粘连下标判 定的数值实验 2 1 1 基本原理 2 1 基本原理及投影方法 在英文科技文档图像里面，粘连下标，除了与其他英文字符及数学符号有共 同的连通等特性外，本身拥有一些独特的特征图2 1 中粘连字符九显示出粘连下 标的一般特征： 粘连下标一般由双字符相互粘连组成，左边字符占主体部分可称其为主体 字符，右边部分为附属部分，可称其为下标字符； 与主体字符相比，下标字符上空一般有较大的空白区域，可称其为高度的不 对等性： 与主体字符相比，下标字符所占的宽度一般比较窄，可称其为宽度的不对等 性； 粘连下标作为一类数学公式字符，拥有数学公式字符所拥有的一般特征，如 数学公式内的字符间距大于正常文本单词中字符间的间距，数学公式与同 行i 临近的文本单词字符之间的间距大于文本单词之间的间距等 一1 3 英文科技文档中粘连下标的一种判定方法 图2 1 粘连下标示例：九 f i g 2 1s a m p l eo fm e r g e ds u b s c r i p t s ：九 鉴于粘连下标字符拥有上述独特特征我们可以运用一种新的投影方法将粘连下 标字符从其他字符中检测出来下面将介绍新的投影方法 2 1 2 投影方法 投影方法是图像处理中常用的一种图像分析方法。它通过对已知数据信息降 维或提取来获得可用的局部数据信息针对二维黑白像素图，黑像素的垂直或者 水平累加投影常常用来分析问题，而对于粘连下标的图像，这种通常情况下的投 影无法获得粘连下标不同于其他英文字符或数学符号的独特特征在这里我们提 出了一种新的投影方法，这种方法能够获得图像中连通体的轮廓特征首先，我们 给出新投影方法确切的定义。 定义2 1 ：假设图像的左下角为图像原点，若黑白矩形图像为i ( x ，) ， r c $ ，们= 1 l 篙：襄篡凳詈嚣蓁： q 舢 其中，0 z x ，0 y y 则称 o m ”a x ，i ( 。，可) 白+ 1 ) 一1 4 大连理工大学硕士学位论文 为图像j ( 。，) 的上轮廓投影，简记为r ( z ) ；称 o m 口a x y 堆，剪) ( y 一) 为图像，( z ，”) 的下轮廓投影，简记为r ( o ) 上述定义能够很好地描述一个连通体图像的上下轮廓特征直观上讲，上轮 廓投影就是图像x c = ，) 的上轮廓黑像素距底端的距离；而下轮廓投影就是图像下 轮廓黑像素距图像顶端的距离 图2 2 给出了粘连下标如的粘连原图像以及其传统投影和上下轮廓投影图 从中可以看出上下轮廓投影给出了字符图像的轮廓特征，但是这种投影方法也存 图2 2上下轮廓投影示例 f i g 2 2s a m p l eo fe d g e - b a s e dp r o j e c t i o n 在缺点，对污染比较严重的图像，这种方法获得的轮廓将与待检字符的真实轮廓 特征有出入当然这可以通过图像的预处理来加以矫正和控制图像的预处理不 是我们的研究重点，在此不再赘述针对数学粘连下标字符，给出图像j ( z ，) 的前 提条件如下： 为保证图像为单一连通字符体( 小写i ，j 的上端圆点除外) ，图像的黑像素 在z 方向上不能出现断裂，即r ( 。) o ，妇f 0 ，x ) ； 一1 5 一 英文科技文档中粘连下标的一种判定方法 为保证图像高度即字符高度，图像顶端行必须存在黑像素，即m a xr ( z ) = u s z y ： 为保证图像高度即字符高度，图像底端行必须存在黑像素，即m a xp b ( o ) = 0 x y 2 2 基于上下轮廓投影的判定方法 2 2 1 判定方法的概要流程 根据粘连下标与其他字符或数学符号体不同的轮廓特征以及上述新的上下 轮廓投影方法，我们给出判定方法的简单流程如下： ( 1 ) 获取输入字符图像的上下轮廓投影； ( 2 ) 根据上轮廓投影情况，预先判断，排除非文字字符： ( 3 ) 获取上轮廓投影最大值集合的最大位置x m a x 和下轮廓投影最大值集合的 最小位置x m i 。； ( 4 ) 判断上述两个位置间的点的上轮廓投影值与字符高度的关系，以及其右 侧上轮廓投影最大值与字符高度的关系满足一定的条件，则判定其为粘连下标 下面我们将给出判定方法的具体表达 2 2 2 判定方法的具体描述 为了更清楚地描述判定方法，我们首先引入如下概念及标记 上轮廓极小值的位置集合为 l ( ，) = 扣 r ( 功 兄 一1 ) ，r ( z ) 只扛+ 1 ) ，0 z x 1 ) ( 2 4 ) 上轮廓最右边的最大值位置为 弼= m a x x 。ir ( 黝) 。娶熬r ) ) 下轮廓最左边的最大值位置为 瑶= m i n z 。i 昂( 知) 2 峰m a 。x 。p b ( 。) ) ( 2 6 ) 一1 6 一 大连理工大学硕士学位论文 z 右侧上轮廓投影的最大值为 耽( 茁) - 婶m a 。x 。p ( x o ) ( 2 7 ) 于是我们可以给出判别准则如下： f1 玩( j ) o 并且j 知( 弼，弼) ， o ( x ，口，展，y ) = 8 t r ) a y , f l y 毛( z o ) 7 y ； ( 2 8 ) 10 其他 其中，0 口，屈，y 1 ，准则输出为l 时表明图像字符是粘连下标。 2 3 数值实验 2 3 1 样本构成 由于样本选取的困难性，我们选取一些字符元，将它们组合并经由c t e x 生 成p d f 文档，然后转换成字符图像作为输入具体