（电路与系统专业论文）印刷体数学表达式识别实现方法研究.pdf

摘要 摘要 数学表达式是大多数科技工程文献的重要组成部分。随着网络技术和计算机 技术的迅速发展，计算机已渗透到社会生活的各个领域，人类社会进入了一个信 息化的时代，通过网络传播和交换信息已经成为一种重要的手段。实现科技工程 文献的数字化对人们的学习和研究有着重要的意义，只有将现有的文献转换成相 应的电子文档，我们已经拥有的大量信息才能够使用计算机处理并使之能够在互 联网上传播。 数学表达式的识别已经成为科技工程文献数字化过程中的难点和关键。本文 针对科技文献中存在的大量数学表达式，首先介绍数学表达式识别的发展历程， 分析它的结构特点，然后详细讨论了数学表达式的识别过程，将这个识别问题分 为三个过程：表达式定位和符号分割、符号识别和结构分析。在数学表达式定位 过程中，通过计算文本行内各符号的纵坐标的平均值和标准差来判断本行是否为 独立的数学表达式，通过对一些特殊数学符号的识别来判断是否存在嵌入式数学 表达式；符号分割采用的是递归的垂直水平轮廓投影分割方法做第一步处理，用 种子填充法对其缺点进行补充，轮廓投影分割法的优点在于用它分割出来的符号 具有结构信息；支持向量机作为统计学习理论的重要应用，我们使用它来进行符 号识别，这是支持向量机方法的一种新应用，但它还是取得了比较好效果；在结 构分析阶段中，树转换的方法被使用来分析数学表达式的结构，引入基线结构树 的概念，将数学表达式中的操作符和操作数分到基线结构树的各个节点上，使用 树结构能简单清晰的反映表达式的结构。 本文在对数学表达式识别各阶段所使用的各种方法进行总结分析的同时，对 使用到的方法编程实现，并给出了实验结果。最后，我们讨论了在数学表达式识 别中所面临的问题以及其今后的发展趋势。 关键词：数学表达式识别符号分割符号识别结构分析 摘要 a b s t r a c t m a t h e m a t i c a le x p r e s s i o n sc o n s t i t u t ea ne s s e n t i a lp a r ti nm o s ts c i e n t i f i ca n d e n g i n e e r i n gd o c u m e n t s w i t hr a p i dd e v e l o p m e n to fm o d e r ni n t e r n e tt e c h n o l o g y a n dc o m p u t e rt e c h n o l o g y , c o m p u t e rh a v ep e n e t r a t e di na uk i n d so fs o c i e t yl i f e d o m a i n s ，a n dh u m a nb e i n gh a v es t e pi n t oi n f o r m a t i o ne r a t h e r ei sak e y v e h i c l eo fd i s s e m i n a t i n ga n de x c h a n g i n gi n f o r m a t i o nv i a t h ei n t e r n e t i ti s i m p o r t a n tt o t h er e s e a r c h i n go fu st r a n s c r i b i n gt h es c i e n t i f i ca n de n g i n e e r i n g d o c u m e n t si n t oe l e c t r o n i cf o r m w h e nw et r a n s c r i b ee x i s t i n gk n o w l e d g ei nt h e f o r mo fp a p e rd o c u m e n t si n t o c o r r e s p o n d i n g e l e c t r o n i c f o r m ，al o to f i n f o r m a t i o nt h a tw eh a v ep o s s e s s e dc a nb ep r o c e s s e db yt o d a y sd i g i t a lc o m p u t e r a n dt r a n s m i t t e dt h r o u g ht h ei n t e r n e t t h er e c o g n i t i o no fm a t h e m a t i c a l e x p r e s s i o n s i s b e c o m i n gak e y i n t r a n s c r i b i n gd o c u m e n t si ns c i e n t i f i ca n de n g i n e e r i n gd i s c i p l i n e si n t oe l e c t r o n i c f o r m i nt h i sp a p e r , w ed i s c u s sr e c o g n i t i o no fm a t h e m a t i c a le x p r e s s i o n si nt h e s c i e n t i f i ca n de n g i n e e r i n gd o c u m e n t s f i r s t ，r e v i e w i n gt h eh i s t o r yo ft h e r e c o g n i t i o n o fm a t h e m a t i c a le x p r e s s i o n sa n da n a l y z i n gt h ep r o p e r t i e so f m a t h e m a t i c a le x p r e s s i o n s t h e nw ec a nd i v i d et h em a t h e m a t i c s - r e c o g n i t i o n p r o b l e mi n t ot h r e ep r o c e s s e s ：p a g es e g m e n t a t i o na n ds y m b o ls e g m e n t a t i o n ， s y m b o lr e c o g n i t i o n s t r u c t u r a la n a l y s i s w e d e t e c t e dt h em a t h e m a t i c a l e x p r e s s i o n sp r i n t e di ns e p a r a t el i n e sb yc a l c u l a t i n gt h eyc o o r d i n a t eo ft h e b o t t o m - m o s tr o wo fs y m b o la n di t ss t a n d a r dd e v i a t i o n f o rd e t e c t i n ge m b e d d e d m a t h e m a t i c a ie x p r e s s i o n s w ec a nc h e c ke a c hi i n et of m do n eo rm o r eo ft h e m a t h e m a t i c a ls y m b o l sw ed e f i n e t h es e g m e n t a t i o no fs y m b o lc a nb ed o n eb y r e c u r s i v eh o r i z o n t a la n dv e r t i c a lp r o j e c t i o np r o f i l e sc u t t i n g w ee m p l o yaf l o o d f i l la l g o r i t h md e a lw i t ht h es u b - e x p r e s s i o nw h i c hc a n n o tb ed e a lw i t hb yt h e p r o j e c t i o np r o f i l ec u t t h es u p p o r tv e c t o rm a c h i n e s ( s v m ) i sai m p o r t a n t a p p l i c a t i o n o ft h es t a t i s t i c a l l e a r n i n gt h e o r y w ea p p l y i tt ot h e s y m b o l r e c o g n i t i o na n di te x p r e s sng o o dp e r f o r m a n c e i nt h ep r o c e s s e so fs t r u c t u r a l a n a l y s i s ，w eu s et r e et r a n s f o r m a t i o nt oa n a l y s i st h es t r u c t u r eo fm a t h e m a t i c a l e x p r e s s i o n s w ei n t r o d u c et h ec o n c e p t i o no fb a s e l i n es t r u c t u r et r e e ( b s t ) ，t h e i n t e r n a lt r e en o d e sa r eo p e r a t o r sa n dl e a fn o d e sa r eo p e r a n d s t h ew a yo ft r e e t r a n s f o r m a t i o n sc a ne x p r e s st h es t r u c t u r eo fm a t h e m a t i c a le x p r e s s i o n si na c o n v e n i e n ta n dc o m p a c tf o r m i nt h i sp a p e r ，w eg i v eas u r v e yo fr e c o g n i t i o no fm a t h e m a t i c a le x p r e s s i o n s ， a n dr e v i e w i n gal o to fw a yi nt h et h r e ep r o c e s s e so fr e c o g n i t i o n w eg i v et h e p r o g r a m sa n dr e s u l t so fr e c o g n i t i o no fm a t h e m a t i c a le x p r e s s i o n si np r i n t d o c u m e n t s f i n a l l y , w ed i s c u s st h ed i 棚c u l t ya b o u tr e c o g n i t i o no fm a t h e m a t i c a l e x p r e s s i o n sa n d i t st r e n di nt h ef u t u r e k e yw o r d s ：r e c o g n i t i o no fm a t h e m a t i c a le x p r e s s i o n ，s e g m e n t a t i o no fs y m b o l ， s y m b o lr e c o g n i t i o n ，s t r u c t u r a la n a l y s i s 2 第一章绪论 第一章绪论 1 1 引言 近年来，随着网络的飞速发展，通过网络传播和交换信息已经成为一种重要 的手段，数字图书馆和远程教育等领域也随之成为研究热点。而要推动这些领域 的发展使之能应用于实际，关键就是开发出一种简单有效的、能将现有的纸张形 式的文档转换成相应的电子文档的方法。只有这样我们现在所拥有的大量信息才 能够使用计算机进行处理并使之能够在互联网上传播。 数学表达式构成了大多数科技工程准则的基本部分。特别是在科技高速发展 的今天，许多科技工程文献中都包含着大量的公式，他们有的和文档中的文字混 杂在一起( 内嵌) ，有的独占一行。目前对于纸张形式的科技工程文献都是通过 扫描将其转换成电子文档的，现在文字识别的方法很多 1 ，也形成了一些比较 成熟的软件( 如清华紫光o c r 、汉王科技等) ，它们对印刷体文字( 包括英文和 汉字) 的识别率最高，对手写体文字的识别率也在逐步提高。但由于数学表达式 中包含了数字、英文字母、希腊字母和一些数学运算符号等，并且这些符号不像 简单文本那样线性排列，而是按一定规则分布在二维结构中，结构比较复杂。目鲋 的o 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 ) 系统还不能正确识别文献中的数学表达 式，这些表达式都是以图像的形式存在的。当人们对科技工程文献进行数字化时， 其中的表达式只能按照图像格式进行保存，而不能加以识别分析。当读者想验证 或重用这些数学表达式时，只能使用专门的数学计算软件或数学排版软件按照其 语法规则重新输入，数学表达式的输入要比纯文本的输入困难，因为数学表达式 除了英文字母、希腊字母和阿拉伯数字外还包括许多特殊的符号，使其输入过程 复杂繁琐，速度慢，并且存在一定的错误率 2 。另外，含有大量数学表达式的 文献在网络中传输时，由于表达式都是以图像格式保存韵，占空间极大，非常影 响传输速率。正是由于上述这些原因使得人们开始着手数学表达式识别的研究。 1 2 数学表达式识别研究现状 l 第一章绪论 数学表达式的识别包括符号识别和结构分析两个阶段。符号识别，文字识别 是符号识别的一个最主要的分支，她作为一个热门的研究领域已经具有三十多年 的历史了 3 ，4 】，这为我们对数学表达式中的特殊符号的识别奠定了坚实的基础； 结构分析，数学表达式的结构比较复杂，她是按照一定规则分布在二维的结构中， 而不是像简单文本那样的线性结构，不过人们对二维模式结构分析的研究也有一 定的历史了 5 。但是，正如 6 ，7 ，8 ，9 中所提到的一样，还很少有人针对数 学表达式识别这一课题进行专门的研究，即把符号识别和结构分析两者结合起来 解决问题。直到近年才有越来越多的人开始把注意力投向这一领域，因此现有的 研究数学表达式的文章比较少。1 9 6 8 年a n d e r s o n 1 0 在其博士论文中首次提出了 公式识别问题，他的用于数学符号识别的方法给出了一个非常好的个案研究。 b e r k e l y 大学的f a t e m a n 从1 9 9 5 年开始研究自动数学公式处理问题。b l o s t e i n 矛h g r b a v e c 1 1 则首次定义了数学表达式的识别问题，将数学表达式的识别分为两 个阶段：符号识别和结构分析，每个阶段又包括三个步骤，它们分别是符号识别 中的预处理、分割和符号识别三个步骤以及结构分析中的符号间的空间关系确 定、逻辑关系确定和意义构造，并根据该问题的主要予部分给出了现存工作的一 个调查。 随着越来越多的人进入到这一领域，近年来对数学表达式识别的研究取得了 很大的进展 1 2 ： b e l a i d 和h a t o n 1 3 为了用更简练的方式分析表达式，使用了两个句法分析， 也就是从上至下和从下至上法。用结构分析法识别出符号后，用从上至下法将表 达式分解成子表达式，而用从下至上法将予结构联合为更大的结构。但他们的实 验仅限于一些简单的数学表达式( 算术和一些三角函数方程) 。 c h e n 和y i n 1 4 提出了一个没有强调结构分析部分的联机手写数学表达式系 统。为了最终显示一个表达式，建立了一个符号关系树来保存符号间所有的空间 关系。因此，该系统不得不执行的主要任务是符号识别。首先，所有的符号根据 传统的统计方法分类( 根据不同的特征查找最近邻的符号) 。然后，如果发生含义 模糊，上下文的信息可以用来决定符号的最后意义。此外，提供了一个用于手动 第一章绪论 改正万一存在模糊或错误分割的符号的联机编辑器。 n a k a y a m a 1 5 设计了一种笔写输入数学公式编辑器，以简化将公式输入到计 算机中的问题。该系统允许用户以任何次序输入字母和符号，他用了一个模板匹 配的算法来识别手写体符号。该系统不需要分割就可实现结构分析。在这种方法 中，所有的字母和符号的信息保存在一张表中，在显示数学表达式时，表达式被 由左至右、由上至下检查后转换成相应的字符串，该系统利用某些限制以确保其 更好的执行。例如，所有的字母应该以小于3 2x3 2 象素的格式写下来，否则， 他们将被作为数学符号或示例来对待。所有的上标中的成分必须在中心线的上 方。此外，在符号的识别阶段，所有的符号将被转化成相应的印刷体。符号问也 将插入一定的空格。 d i i t r i a d i s 和c o r o n a d o 1 6 也设计了一个数学公式编辑器。该系统首先使 用了基于字母和符号识别的a r t ( a d a p t i v er e s o n a n c et h e o r y ) 神经网络法，然 后运用特征法则进行结构分析。尤其在检测和修正错误的时候作了许多额外的努 力，该编辑器另一特殊的特征是可以适合于单个用户的书写习惯。 c h a n f h y e u n g 1 7 设计了运用结构和句法方法的联机数学表达式识别系统。 该系统首先应用了结构法，又称为灵活的结构匹配法来识别符号。然后运用了句 法方法，又称为等级分解分析法，来获得数学表达式的结构。所提出的句法方法 基于三个关键的思想，即左分解、连接符预处理和等级分解以使分解过程更为有 效。 o k a m o t o 和m i a c 1 8 强调大多数的数学表达式的识别可以不通过实际分割它 们的符号而完成结构排列。系统首先运用了递归目标结构分析法来分割字母和符 号，同时建立关系树。然后，使用传统的模板匹配法识别符号。 | j l e e 和m c l e e 1 9 提出了一个识别印刷体数学表达式的系统。首先，系 统运用了一个传统的统计方法来识别单个的字母和符号，然后，运用了面向过程 的方法将二维结构的表达式转换为一维的字符串。 l e e 和w a n g 2 0 提出了既能识别和理解文档中的文本又能识别数学表达式的 系统，在理解表达式的时候，一些特征提取技术和最近邻算法被用于识别字母和 第一章绪论 符号。符号关系树被建立用于描述表达式。此外，还提出了用于纠正识别错误一 些启发式的研究。 f a t e m a n 2 1 ，2 2 设计了一个典型的系统，该系统能成功地将排版好的数学表 达式转换成l i s p 表达式。对符号识别部分而言，运用了不同的方法，如计算用的 h a u s d o r f f 距离和符号灰度值的计算。对结构分析部分而言，运用了一个简单的 递归降序分割法。试验表明最初的由下至上的设计在面临噪声数据时应用很有 限，因此，一个更加结构化的由上至下的方法可以代替它获得更高水平的性能。 1 3 数学表达式识别分类 从识别对象的字体形式来看，数学表达式识别可以划分为印刷体识别和手写 体识别。印刷体公式字体规范、结构整齐，切分和识别都相对容易，印刷体的识 别常见于各种票证收据的自动批量处理应用中的识别阶段。而在手写体公式识别 中，由于用户具有较大的书写自由度，系统因此而面临着各种各样的笔体和参差 不齐的公式结构，这些因素极大地增加了单个字符识别和公式结构切分的难度。 而根据数学表达式输入方式的不同，又可以将数学表达式的识别划分为脱 机( o n l i n e ) 识别和联机( o f f - l i n e ) 识别。因为对印刷体数学表达式的识别都是 脱机进行的，所以联机、脱机的划分对手写体表达式来说才有实际意义。脱机识 别是对用户己经书写完成的数学表达式进行识别，一般是对表达式的图像扫描后 进行识别处理，o c r 是脱机识别领域的一项常用技术：而联机识别则是指在用户 书写数学表达式的时候，识别也同时进行。联机输入能够捕捉手写的动态信息， 如笔划的数量、笔划的顺序和书写速度等。而且联机手写输入还是人机之间的一 种紧密交互，要求系统能够不断地根据用户的输入修正识别结果，并为用户提供 必要的反馈信息，从而联机手写具有实时性的特点。因此就形成了如图l - 1 所示 的数学表达式识别的分类图： 第一章绪论 表 达 式 识 别 印刷体识别 广联机识别 f l 手写体识别一i l 脱机识别 图1 1 本文主要研究印刷体数学表达式的识别。在这里，用于实验的文档是预先排 版的经仔细检查的文档，其识别包含数学表达式的定位、识别和分析。印刷体数 学表达式识别可以用于多种目的，从小的方面来说是在视觉上减少机器阅读、加 快技术文档的网络传输速率。大的方面来说就是用于大量收集的科技工程文档的 扫描、解释和用于数据库的创建，这对于数字图书馆、远程教育系统的建立都很 有意义。 1 5 本文的研究内容与组织 本文首先论述了数学表达式识别对当今社会信息的存储和传播的重要作用， 尤其是对于技术工程文档的数字化、远程教育等有十分重要的意义。然后立足于 印刷体数学表达式识别系统的实现，对数学表达式识别各个阶段的方法进行了总 结和研究，设计了各阶段的实现方案并进行了实验。本文具体结构是： 第一章：介绍了数学表达式识别的发展历史和对当今社会发展的重要意义， 总结了前人对数学表达式识别研究的工作成果，以及今年来的发展现状。对数学 表达式识别进行一个简单分类。 第二章：介绍了印刷体数学表达式识别的困难和意义，根据自己的研究提出 实现印刷体数学表达式识别的总体流程。将印刷体数学表达式的识别问题划分为 三个子问题：表达式定位、符号识别和结构分析。 第三章：介绍了数学表达式前期处理的大致流程以及本文采用的数学表达式 定位方案，同时回顾了前人在符号分割方面所作的工作，提出符号分割方案 递归的垂直水平轮廓投影分割。 第四章：介绍了支持向量机的基本原理、分类性能和实现方法，然后使用前 一章提取出来的特征对符号进行识别，并对两种特征提取方法的识别结果与已有 第一章绪论 文章中的结果进行了对比。 第五章：介绍了数学表达式结构分析中的一些难点，总结了前人在表达式结 构分析中使用过的方法。提出使用树转换方法进行表达式的结构分析，详细阐述 了树转换方法中的三个主要步骤。 第六章：总结与展望，总结本文所做的工作和遇到的困难，展望未来的研究 方向。 第二章e n i d 体数学表达式识别研究 第二章印刷体数学表达式识别研究 2 1印刷体数学表达式识别的意义 几千年以来，人们使用数字、字母以及一些特殊的符号组成各种数学公式，这些 数学公式形象直观的表达了人们的想法和思维，通过这些数学公式人们可以很方便的 进行交流，即使彼此的语言不通。现在，随着网络和计算机的迅速普及，人们很自然 的就会想到将这些由数字、字母和特殊符号组成的数学公式通过计算机来进行交流， 这将给人们的生活和工作带来极大的便利。要实现这个目标，就需要将印刷体的数学 表达式转换成计算机可以识别的形式，虽然在目前的情况下计算机已经可以产生二维 的数学表达式，但是对数学表达式的识别将印刷体的数学表达式转换成计算机可 以识别的形式，却还没有得到广泛的应用。目前这部分的任务还主要依靠人工来完成， 如图2 所示，通过一个人在将印刷体数学表达式转换成计算机可以识别的形式的过程 中所负担的任务，我们可以看到一个数学表达式识别系统能够极大的提高计算机作为 一个文档处理工具的作用。 如图所示，在整个流程图的顶端就是我们要输入的数学表达式，右边的这条数学 公式的自动识别的路径是我们想要走的，但是现在还没有得到广泛的应用，大多数情 况下人们还是通过手工输入数学公式进行人工的转换，也就是左边的这通过键盘输入 数学公式的a s c i i 码格式或者使用数学公式编辑器输入条路径。相比之下，数学公式 的输出技术就比较成熟，应用也比较广泛，如图2 底端所示。 脱机的数学表达式识别主要是指对一份事先准备好的印刷体文档进行扫描转换成 图像格式，然后对文档中所包含的数学表达式定位、识别以及对其结构进行分析。印 刷体数学表达式的识别有很多的用途，其中最主要的一个就是对我们收集到的大量工 程技术文献进行扫描和识别解析，其结果将用于建立大型的数据库。经过识别后的数 学公式还有很大的实际应用价值，根据目前的情况，至少有： 1 转化成l a t e x 格式，用于h t m l 、x m l 的制作。 2 用于机器自动证明。 第一二章印刷体数学表达式识别研究 3 编辑起来比未进行语义处理的公式更加方便。 4 减少文献的存储空间，便于网络上的传输。 数学表达式的人工转换： 人们f 面的方法直接输入数学公式的结构 1 通过键盘输入数学公式的a s c i i 码格式； 2 通过数学公式编辑器输入。 数学表达式的自动转换： 1 计算机识别数学公式中的符号； 2 计算机识别数学公式的二维结构。 。 曰困 图2 数学公式转怎样换成计算机能识别的形式 2 2 数学表达式的特点 在文档中，数学表达式区别于一般文字的一个主要特点是：将大小不一定完全相同 的符号按一定规则排列成一个二维层次结构下面对数学表达式的特点进行阐述。 火 第二章印刷体数学表达式识别研究 2 2 1 数学表达式中的符号 数学表达式中的符号可分为基本符号和特殊符号，如绑定符号、界定符号、运算符 号等，它们有各自的组织准则，如加号必须有2 个操作数等。对于基本符号一般有以 下的形成规则：( 1 ) 大小相同且相邻的数字应该是一个整体，相邻但大小不同就不能作 为一个整体，如4 加就不作一个整体；( 2 ) 几个相邻的字母有可能形成一个整体，如函数 名( 如s i n 、c o s ) 等，但有时也代表2 个变量的乘积，如a b ，它表示a + b ；( 3 ) 除了字母 和数字的其它符号应该独自形成一个整体。 对于特殊的符号，一般有以下3 种情况：( 1 ) 绑定关系符号，如分数线、 兀等，它们同作用域中的表达子式绑定在一起，如f 中的求和符号就绑定了3 个子 1 = 0 表式1 0 0 、i 、i = 1 0 0 ；( 2 ) 界定符号，如括号，它将界定符号间的内容应看成一个完整的 部分，它具有更高的运算优先权；( 3 ) 运算符号，如+ ，+ ，等，它们都约束着各自的 操作数。 2 2 2 数学表达式的运算符号 数学表达式的运算符号包括显式运算符号和隐式运算符号。显式运算符号就是通 常的运算符号，可以根据它们的运算优先权规则来确定运算关系。如果表达式不是线 性的，如爿+ i b ，可以根据运算符号的作用域来确定运算关系。隐式运算符号由相对位 l 置来确定运算关系，而没有明显运算符号，如上标、下标和隐式的乘号。例如，a b 表 示变量a 和变量b 相乘；在2 a 中2 是a 的上标，而在a 。中2 是a 的下标。 2 2 3 含义的不确定性 同样的符号，在不同的位置，其表示的含义可能不相同。例如，圆点可能表示乘， 可能表示小数点，在一些数学表达式图像中还可能是噪声等：还例如d x 在b 出可中 d ( 表示积分变元，而在式c y + d x 中表示d 和x 相乘。 另外在特殊的领域中，数学表达式中的符号有特殊的含义，如物理中的一些常数 符号。所以一个数学表达式识别系统不可能适应于所有的领域，几乎所有的识别系统 第二章印刷体数学表达式识别研究 都只适应于某一个或某几个领域。 2 3印刷体数学表达式识别系统的总体设计 首先，我们来定义这个系统的边界：系统的输入是经过扫描的包含数学表达式的文 档，输出为识别出来的数学公式的排版语言( 比如l a t e x ) 表示。系统的设计问题就是如 何实现从输入到输出的转化问题。 人们解决问题一个重要思路是“化整为零”，即首先把一个复杂的问题分解为几个 相对简单的子问题，把每个子问题解决后再综合为整个问题的解决方案。这种手段不 仅极大地降低了问题的复杂程度，而且允许对每个子问题分别进行优化同时对整个问 题的解决又不产生影响。印刷体数学公式的识别可以切分为三个子问题：表达式定位 在科技文献和工程文献中，很多情况都是文本和数学表达式混合在一起的，所以在识 别之前需要从文档中找出数学表达式。文档中的数学表达式表现为2 种形式：独立的表 达式和嵌入式表达式。独立的表达式是指独占一行的表达式，而那些和文本混合在一 行中的表达式称为嵌入式表达式；符号识别：通过一些符号识别算法对数学表达式中 的符号进行识别，识别算法有模板匹配算法、结构匹算法和统计理论算法等，本文将 使用支持向量机( s v m ) 方法进行符号识别。符号识别阶段分为两个子过程符号分割 和符号识别，因为目前符号识别的方法大多数是基于单个符号的识别，而数学表达式 往往由很多符号组成，所以在符号识别之前，要将数学表达式进行分割，然后再利用 符号识别算法进行识别；表达式结构分析：在符号识别中可以得到数学表达式中每 个符号的固有属性，如大小、位置和相应的符号。结构分析就是要分析这些识别得到 的符号的层次结构，它们的层次结构可以表示成分析树或关系树的形式，经过结构分 析最后可以将得到的符号集合分析为排版语言表示的数学表达式。 因此，整个识别过程可以分为三个阶段：( i ) 系统利用符号分割子系统将数学表达式 中的符号分割出来成为单独的一系列字符；( 2 ) 符号识别子系统利用步骤( 1 ) 的输出结 果，使用支持向量机方法对这一系列的字符进行识别；( 3 ) 利用符号的固有属性，如大 小、位置和相对应的符号，使用基线结构树方法分析这些符号之间的层次结构并建立 一棵关系树。我们可以用如图3 所示的流程图来概括数学表达式识别的过程。 在接下来第三、四、五章，详细介绍了三个子系统的系统功能和实现算法。 第二章印刷体数学表达式识别研究 脱机数据 x 2 2 x + 1 。、。、竺害：、旦+ 、，。这里得到的是一系列的图像块， 竺扯 ( 这早得到的是一个对象序列即识别出来的符号) 结构分析 八+ 入入 x21 入 2x 图3印刷体数学表达式识别过程 2 4 本章小结 本章阐述了印刷体数学表达式识别对现代的学术研究及远程教育的意义，同时分 析了数学表达式的特点，它们是数学表达式识别与普通的文字识别不同的根本原因所 在。最后，设计了具体实现印刷体数学表达式识别系统的流程，在后面的章节中将具 体介绍各个阶段的实现方法。 第三章表达式定位和符号分割 第三章表达式定位和符号分割 在对印刷体数学表达式进行识别之间需要对扫描的文档进行前期处理，因为 扫描得到的文档不可避免的存在噪音、倾斜等干扰，这些干扰不进行处理的话会 给后面的识别过程造成很大的麻烦。本文的前期处理工作主要集中在数学表达式 的定位上，找到表达式的位置后将其提取出来进行识别的第一步符号分割。 3 1 符号识别的前期处理 3 1 1 什么是前期处理 前期处理一般是指在进行文字识别之前的预处理工作。一般说来，前期处理 包括噪音去除、倾斜校正、图文分割、段落和行的划分以及数学表达式的定位等。 但是在前期处理的时候，也许会用到字符的识别。比如对于一个区域，试图确定 它是图还是文的时候，会试探性的进行识别f 】。所以说，前期处理和正式识别不 能完全划分开，往往是一个递推的过程，前期处理的作用是为了后面的识别工作 更加高效、准确。从广义上说，前期处理工作就是所有为了使具体处理更加高效、 准确的工作。 3 1 2 前期处理的大致流程 之所以说是大致流程，是因为前期处理工作并没有一个一成不变的顺序。每 个系统中可能会根据需要进行一些调攘。但是总体来说，大致会遵循以下的流程。 ( 1 ) 得到连通体信息，去除噪音。( 对于基于像素的系统来说，就不查找连通 体了。) ( 2 ) 进行文档的切分在这个过程形成“段落”，把整个文档结构化。 ( 3 ) 进行图文分割，更广义的来说，就是进行段落属性的判别。比如将段落 属性定义为“图”、“文”( 其中包括文本和表达式) 等。 ( 4 ) 对属性为“文”的段落进行“行”切分，分离出“行”的结构来。 ( 5 ) 对行进行属性判别。( 对于一般o c r 系统来说不必如此，对于本文涉及 2 第三章表达式定位和符号分割 的数学表达式识别系统来说是必要的。) 3 1 3 前期处理中各环节的方法 噪音处理：噪音处理有基于版面信息的处理方法，也有基于纹+ 理( t e x t u r e ) 的 处理方法，但是并没有能够满足任意情况下的噪音处理方法。 倾斜校正：有h o u g h 基于变化的倾斜校正，有基于最小二乘法的方法。最 小二乘法的计算量需要小。 段落划分：有两种基本方法( 1 ) 自上而下，k r i s h n a m o o r t h y 等提出了种 利用段落间空白递归地进行横向和纵向切割的算法，p a v l i d i s 和z h o u 则不仅依靠 段落间的空白，还进行了投影轮廓分析。所有类似的这些算法都比较快，但它们 只对所谓m a n h a t t a n 式版面有效，即：图像中各区域之间存在明显的水平和垂直 的空白，区域都可以由互不相交的矩形区域来描述。此外，这类算法易受图像倾 斜的影响。( 2 ) 自底向上，自底向上则不受版面的限制，这种方法一般先进行连 同体分析( c o n n e c t e dc o m p o n e n t sa n a l y s i s ) ，以便减少运算量。有的算法为提高运 算速度，还将原图像缩小一定比例。得到连通体后，通过连通体之间的几何性质 以及一些相应的启发式规则或者应用一砦聚类算法如k - 近邻算法便可以合并出 文字行。另一类不用连通体分析的自底向上方法是由我w o n g 【】等提出的游程 合并算法( r u n - l e n g t h - s m e a r i n g ) ，它对版面简单的图像比较有效。该算法分别在 x 和y 方向上把二值图像模糊化，即把任意两个间距小于某个阈值的黑像素之间 的像素都抹黑，这样就得到两幅图像。把这两幅图像相与，便得到原图像的一个 分割。最后，还得判断各分割区域的属性。自底向上的方法的缺点在于计算量大： 过于依赖域值得选择；容易受噪声干扰。因为这两种方法各有优缺点，所以在这 两种方法的基础上，人们把他们结合起来形成混合方法。 图文分割：图文分割是相当复杂的任务，迄今没有在所有情况下令人十分满 意的结果出现。因为对于任意版面，划分区域本身是和图文分割紧密纠缠的一个 过程。本文对前期处理只是做一个简单的介绍，所以对图文分割的算法就不进行 详细的阐述。 行划分：行的划分和段落划分一样都有两种方法。自底向上：从左到右的扫 第三章表达式定位和符号分割 描连通体。把有重叠的连通体归并为一行。如果两行都有重叠的连通体，就把它 归入重叠较大的一行。这样得来的结果，对倾斜不敏感。但是计算量大，对噪音 比较敏感。自上向下：直接从左到右进行投影，进行行的划分。这种方法对倾斜 特别敏感。 数学表达式的定位：大多数的文献采用根据段落的位置( 居中) ，高度( 比普通 的行高) 来确定是否独立的数学表达式。对于嵌入式的数学表达式，可以根据数 学表达式中的一些特殊符号，如积分号，根号等，用一些统计数据来确定数学表 达式行的位置。 本文主要研究的是数学表达式的识别问题，因此只对文档中的数学表达式的 定位进行了研究，其他的前期处理工作只做一些原理方法上的探讨。 3 2 文档中数学表达式的定位 在科技文献和工程文献中，很多情况都是文本和数学表达式混合在一起的， 所以在识别之前需要从文档中找出数学表达式，即页面分割( p a g e s e g m e n t a t i o n ) 。文档中的数学表达式表现为两种形式：独立的表达式和嵌入式 表达式。独立的表达式是指独占一行的表达式，而那些和文本混合在一行中的表 达式称为嵌入式表达式。 3 2 1 在文档中定位数学表达式的主要方法 要对科技工程文档中的数学表达式进行识别，第一步就是要找出文档中表达 式的位置，尽管数学表达式识别问题越来越吸引了许多研究者的注意，但是关于 表达式定位问题的研究还不是很多，主要的有： l e e 和w a n g 2 3 采用b a y e s 决策规则将文档中的行分为文本行( 标为t e x t ) 和公式行( 标为e x p ) 。在行标定后，独立的数学表达式一定在公式行( e x p ) 中，而 嵌入式数学表达式只在标记为( t e x t ) 的行中。但该方法只适应于一些简单的数学 公式。 f a t e m a n 2 4 提出的方法中定义了文本包( t e x tb a g ) 和公式包( m a t hb a g ) ， 首先将所有的符号初始化分为2 类，分别放在定义好的2 个包中。初始化时，文 4 第三章表达式定位和符号分割 本包中包括罗马字符、斜体数字等，公式包中包括标点符号、特殊符号、斜体字 母、罗马数字以及其它一些标记如水平线和句点等。然后定义一些启发式规则， 并根据这些规则将它们不断调整文本包和公式包中的内容，以保证它们能正确分 类。 用c h a u d h u r t 和g a r a i n 2 f i 的算法定位独立的数学表达式不要用到符号识 别的方法，它通过计算行内各符号的纵坐标的平均值和标准差来判断本行是否为 独立的数学表达式。采用符号识别的方法来检测嵌入式数学表达式，如果存在某 个特殊符号，这里的特殊符号指数学表达式中特有的符号，则说明存在数学表达 式，并采用启发式算法来得到整个数学表达式。 k a c e m 等 2 6 ，2 7 的方法是基于定位查找一些最重要的符号，并从此开始查 找它相邻的符号。该方法主要是基于全局分割和局部分割，全局分割用来定位独 立的数学表达式；而局部分割是用来从普通文本中查找嵌入式数学表达式。在该 方法中用到了基于标签技术的模糊逻辑理论。 3 2 2 本文的数学表达式定位方案 文档中的数学表达式主要有两种形式：独立表达式和嵌入式表达式，我们前 期处理的主要工作就是在待识别文档中将这两种形式的数学表达式找出来，本文 的方案参考了c h a u d h u r i 和o a r a i n 的算法。 首先对整个文档进行一次水平的轮廓投影，通过灰度值的计算可以发现在两 行之间的位置，其轮廓投影的灰度值是最小的，也就是说这里是两个文本行之间 的分界线。经过这一步，文档中的文本行就被分割出来了，当然此时的“文本行” 包括3 种可能的形式：纯文本行、含有嵌入式表达式的文本行、独立的表达式( 因 为此时还不能确定，暂时看作文本行) 。对于一个文本行f ，我们对其中的字符 进行一些简单的分析，取整个文档图像的左上角的像素为原点，令f 为文本行 中字符s ，的最底一行像素值的y 坐标，令n 为文本行r 中字符总数，由此可以计 算出f 的平均值和标准差( s d ) ： 第三章表达式定位和符号分割 i = 吉喜r ，肋= 也( ) 2 因为对于一个纯文本行来说，大多数的字符的最底一行的像素值基本上都是 对齐一条基线的，所以它们的标准差很小。相对的，由于数学表达式( 尤其是独 立的表达式) 它们最底一行的像素值是高低参差不齐的，所以这些符号的标准差 就会比较大。为了计算方便，有时候可以使用平均标准差s s d 来代替标准差s d ： s s d = 去喜弘 1 善n 彬n 曹n 百 要将数学表达式从文本行中分离出来，标准差s d 是一个很好的量度。如图 4 所示的三个文本行，第一个是纯文本行，第二个是有嵌入式表达式的文本行， 第三个是独立的表达式。它们的标准差是( a ) 最小( b ) 稍大( c ) 则要比前两个大很多。 ( a ) 纯文本行 ( b ) 含有嵌入式表达式的文本行 ( c ) 独立的表达式 图4 三种形式的文本行 因此，可以预先设定一个阈值，如果某个文本行的s d 值大于该阈值，就可 以认为该文本行为表达式或者含有表达式，至于是否真的存在数学表达式可以通 过进一步的检测来确定。对于独立表达式可以检测其行间距，因为独立表达式的 行间距一般要大于纯文本行和有嵌入式表达式的文本行，而且多数情况下独立表 达式的s d 值要远大于纯文本行。对于嵌入式表达式采用字符识别的方法来检测， 检奄在每个文本行里是否出现表1 中的数学符号，如果出现则表示该文本行有嵌 入式表达式。为了避免误识别可以采用一些启发式规则，例如符号“( ”和“ ” 有时候会被误识别成c 和“e ”，为了避免出现这种情况，只有在左右两个“f ” 第三章表达式定位和符号分割 “) ”或 “ ”都被发现的时候，才能决定含有圆括号或方括号。对于二元操 作符“= ”、“+ ”、“秽和“ ”等，要确定这些符号是否存在就需要检查它们两 边的操作数，这些操作数包括英文字母、希腊字母和数字等。 一旦确定了某个文本行中含有嵌入式表达式，就需要将其提取出来。首先， 利用垂直轮廓投影将该文本行中的字符分隔开，设该文本行中最左边的数学符号 ( 这里指表l 中所列的数学符号) 为彬，以此为起点按照以下规则向两边扩展得 到整个数学表达式： ( 1 ) 如果彬只包含一个二元操作符，那它两边的字符立刻并入表达式域中； ( 2 ) 如果与左右相邻的字符是下面这些情况，也并入表达式域中：一个或 多个数学符号( 包括括号) ；上标下标：单独的或一系列的点；数字。 3 3 符号分割 目前符号识别的方法有很多，但它们大多数是基于单个符号