（计算机应用技术专业论文）印刷体数学公式结构分析与理解的研究.pdf

摘要 摘要 网络与多媒体技术的高速发展带来了对信息的巨大需求。如何将文献信息输入计算 机进行加工、处理已成为信息化建设的重要问题。目前主流o c r ( o p t i c a lc h a r a c t e r s r e c o g n i t i o n ，光学字符识别) 技术虽然能够高速、自动地将印刷体文字信息输入计算机， 但对于结构复杂、符号多变的数学公式仍然无能为力，只能将其按图片形式存储，不能 进行重构和编辑。公式是科技文献的重要组成部分，一个无法处理公式的o c r 系统， 对科技文献的数字化是没有意义的。因此，数学公式识别问题已经成为模式识别领域炙 手可热的课题，具有重要的理论意义和良好的应用前景。 数学公式识别系统包括四个处理模块：公式抽取，公式字符与符号识别，公式结构 分析和公式重构。本文针对公式识别中的关键环节公式结构分析展开研究，设计了 能够分析常见结构类型的包含多层嵌套结构的公式结构分析算法。首先根据字符与符号 属性特征计算外围位置信息；然后运用基线原理递归分析公式中相邻符号的空间关系， 构建结构关系树；之后利用定位符号控制域的方法分析绑定符号，并引入三角区域定位 上下部和动态阈值定位上下标的分析方法，克服了单纯运用基线法的不稳定问题；最后 针对实验中出现的问题，通过建立回溯查漏机制，界限符号的特殊处理方法以及基线阈 值的再修正方法，提高了算法的适应性。对不同类型印刷文档的对比实验表明，本文设 计的结构分析方法能够取得较高的正确率和令人满意的处理速度。 关键词光学字符识别；数学公式识别；结构分析；基线；控制域 a b s t r a c t a b s t r a c t t h eh i g hd e v e l o p m e n to ft h en e t w o r ka n dm u l t i m e d i at e c h n o l o g yc o n t r i b u t e st ot h eg r e a t d e m a n df o ri n f o r m a t i o n t h ec o n v e r s i o no fi n f o r m a t i o nf r o mp r i n t e dt oe l e c t r o n i cf o r m b e c o m e sa ni m p o r t a n ti s s u ei nt h es p r e a do ft h ei n f o r m a t i o n a tp r e s e n t ，t h eo c r s y s t e m sc a n i n p u tt h eo r d i n a r yt e x ti n t oc o m p u t e rq u i c k l ya n da u t o m a t i c a l l y , b u tt h e yc a n n o td e a l 而t h m a t h e m a t i c a le x p r e s s i o n sb e c a u s eo ft h ec o m p l i c a t e ds t r u c t u r e sa n dv a r i o u ss y m b o l s t h e m a t h e m a t i c a le x p r e s s i o n sc a l lo n l yb es t o r e da si m a g e s ，w h i c hc a n n o tb er e c o n s t r u c t e da n d e d i t e d m a t h e m a t i c a le x p r e s s i o n sa r et h ei m p o r t a n tc o m p o n e n to ft h es c i e n t i f i cd o c u m e n t s s o t h eo c r s y s t e mw h i c hc a n n o td e a lw i t hm a t h e m a t i c a le x p r e s s i o n sm a k e sn os e n s et ot h e d i g i t i z a t i o no ft h es c i e n t i f i cd o c u m e n t s t h e r e f o r e ，m a t h e m a t i c a le x p r e s s i o nr e c o g n i t i o nh a s b e c o m eah o t s p o ti nt h ea r e ao fp a t t e r nr e c o g n i t i o nw i t ht h e o r e t i c a li m p o r t a n c ea n dg o o d p r o s p e c t s m a t h e m a t i c a l e x p r e s s i o nr e c o g n i t i o nt y p i c a l l y c o n s i s t so ff o u r m a j o rs t a g e s ： m a t h e m a t i c a l e x p r e s s i o n se x t r a c t i o n ，m a t h e m a t i c a ls y m b o l sr e c o g n i t i o n ，e x p r e s s i o n s s t r u c t u r a la n a l y s i sa n de x p r e s s i o n sr e c o n s t r u c t i o n i nt h i sp a p e r , w ew i l lb e g i nt os t u d y s t r u c t u r a la n a l y s i so fm a t h e m a t i c a le x p r e s s i o n st h a ti sak e ys t e pi nm a t h e m a t i c a le x p r e s s i o n r e c o g n i t i o n ，a n dd e s i g na na l g o r i t h mt h a tc a na n a l y z et h es t r u c t u r eo fv a r i o u st y p e s ，i n c l u d i n g m u l t i - n e s t e ds t r u c t u r e f i r s t l y , t h ep e r i p h e r i e sp o s i t i o ni n f o r m a t i o no fs y m b o l si sc a l c u l a t e d a c c o r d i n gt ot h e i ra t t r i b u t ec h a r a c t e r s s e c o n d l y , t h eb a s e l i n em e t h o di su s e dt oa n a l y z et h e i n t e r a c t i n gs p a t i a lr e l a t i o n s h i p sb e t w e e ns y m b o l sr e c u r s i v e l y f i n a l l y , p o s i t i o n i n gc o n t r o l r e g i o nm e t h o di su s e dt od e a lw i t ht h eb i n d i n gs y m b o l s a n dt h ep o s i t i o n i n go fs c r i p tr e g i o n u s e dt r i a n g l ec o n t r o lr e g i o na n dt h ep o s i t i o n i n go fu pa n dd o w nr e g i o nu s e dd y n a m i c t h r e s h o l di sp r o p o s e d i tc a no v e r c o m et h ei n s t a b i l i t yo ft h em e t h o du s i n gb a s e l i n ep u r e l y a i m i n ga tt h ep r o b l e m si nt h ee x p e r i m e n t ，t h er e c a l ls t r a t e g yf o re r r o rc o r r e c t i o n ，t h es p e c i a l t r e a t m e n to fd e l i m i t a t i o ns y m b o l sa n dt h er e m o d i f i c a t i o no ft h eb a s e l i n et h r e s h o l da r eb u i l tt o i m p r o v et h ea p p l i c a b i l i t yo ft h ea l g o r i t h m t h ee x p e r i m e n t ss h o wt h e s em e t h o d sc a no b t a i n s a t i s f a c t o r ya c c u r a c yw i t hah i g hs p e e d k e yw o r d s ： o c r ；m a t h e m a t i c a le x p r e s s i o nr 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 ；b a s e l i n e ； c o n t r o lr e g i o n 河北大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教育机构的学位或证书 所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了致谢。 作者签名： 焘幽匪 日期：塑2 年丘月上日 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留并向国 家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。学校可以公布 论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 本学位论文属于 1 、保密，在2 嫂仝年月- l 同解密后适用本授权声明。 2 、不保密口。 ( 请在以上相应方格内打“巾) 作者签名：查塑昼 导师签名：旧帕 日期：型立年月l 日 日期：鱼珥年月上日 第1 章引言 1 1 研究背景和意义 第1 章引言 在计算机应用和网络技术飞速发展的今天，资源的共享特别是技术资源的共享越来 越重要，将印刷文献信息输入计算机进行加工、处理已成为信息化社会的必经之路。当 前的o c r ( o p t i c a l c 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 的应用领域，推动信息化建设，具 有重要的理论意义和应用前景。 本课题来源于河北省自然科学基金资助项目印刷文档识别与重构若干核心技术的 新开拓( 编号：f 2 0 0 4 0 0 0 1 3 2 ) 。 1 2 国内外研究现状 公式识别始于二十世纪六十年代末期，发展到现在经历了萌芽期( 1 9 6 8 1 9 9 0 年) ， 积累期( 1 9 9 1 1 9 9 9 年) ，初步应用期( 2 0 0 0 年至今) 三个阶段。 1 9 6 8 年，公式识别问题首次被提出。随后几十年内相关的研究工作进展极其缓慢， 陆续发表了几篇文章。这段时间的工作大部分停留在理论水平上，主要研究思路是试图 构造完备的文法描述数学公式的结构。虽然构造的文法能够描述很复杂的公式，但是实 际系统只能处理包含几个符号的简单公式【2 3 】。a b e l a i d 和j e h a t o n 2 1 使用了两个句法： 自顶向下和自底向上法。在识别出公式各符号后，用自顶向下的方法将表达式分解成子 表达式，而用自底向上的方法将子结构连接成较大的结构。这种方法只适用于分析一些 1 河北人学t 学硕卜学何论文 简单的数学表达式( 如算术表达式和一些三角函数方程) 。f a u r e 和w a n g l 3 】设计了一个 通过奖励关系树来识别手写公式的识别系统，包括两个主要的模块数据驱动模块和 知识驱动模块。该系统的特点是当表达式中的一些符号不能被识别时也能工作。 进入9 0 年代以来，o c r 技术的成熟使得高质量印刷文本的识别率已经超过9 9 ， 在这一阶段，针对数学公式的研究逐渐升温，有超过4 0 篇的论文发表【4 。7 】。但这些工作 只是针对特定类型或者特定环境的表达式处理，不能满足实际应用的要求。o k a m o t o 和 m i y a z a w a 4 】使用递归的投影轮廓切分方法分析数学公式的结构。r j f a t m a n 5 , 6 1 设计了一 种典型的系统，该系统能够成功地将排版好的数学公式转换成l i s p 表达式。在符号识别 中，运用了计算h a u s d o r f f 距离和符号灰度值等方法；在结构分析部分，运用一个简单 的递归降序分割法。该系统的实验结果表明，在面对噪声数据时，最初设计的自底向上 的策略使用效果很有限，此时可采用自顶向下的策略，这种策略可使系统获得更好的性 能。l a v i r o t t e 和p o t t i e r 7 】采用图文法来识别二维数学公式。通过定义精确内容图文法类， 并不断增加上下文文法到这个类中的方法分析数学公式。该方法避免了递归算法的复杂 性，有效地提高了处理速度。但在实验中必须对符号位置和大小信息做出限制性假设。 二十一世纪以来，随着文档图像处理技术的发展，相关技术得到了充分的研究。在 公式处理方面，又有将近2 0 篇论文发表【8 以o 】，但是仍然没有完整的，满足实际需要的产 品出现。c h a n 和y e u n g f 8 】设计了运用结构和句法分析的联机数学表达式识别系统。该方 法首先运用结构法( 又称为灵活的结构匹配法) 来识别符号，然后运用句法分析方法( 又 称为层次分解分析法) 获得数学表达式的结构。他所提出的句法方法基于三个关键思想， 即左分解、连接符预处理和等级分解，从而使分解过程更为有效。 国内对数学公式识别的研究在最近3 ，4 年内才兴起，尚处于起步阶段，相关资料 还很欠缺。主要研究机构有南开大学机器智能研究所和中科院自动化所。南开大学于 2 0 0 1 年至2 0 0 3 年在所承担的国家自然科学基金数学天元基金中进行了相关的研究，在 理论上建立了公式定位、符号识别等的方法体系，为进一步的研究打下了良好的基础。 其中，j i n 等人在l e e 等人所提出方法的基础上，将p a r z e n 窗分类法应用于独立公式的 提取；利用一维分布的普通文本和二维分布的公式符号在基线和均值线上的不同分布特 点，提取嵌入公式】，并给出了一种基于树匹配的公式识别系统自动性能评价方法【12 1 。 江红英等人提出了根据符号的外接矩形和识别结果判别印刷体数学公式上下标关系的 统计方法，提高了判别的准确性。吴微和侯利副1 4 】提出了基于l l ( 1 ) 文法的表达式 2 第1 章引言 构成规则和公式结构分析器的设计，并简略介绍了基于神经网络的数学符号识别方法。 此外，哈尔滨工程大学、广西师范大学、大连理工大学的研究人员也在关注此类研究， 发表了相关的论文【1 5 - 19 1 。总的看来，国内公式识别研究起步较晚，如何超越特定对象， 研究适应我国文献特点的、能够实际应用的公式识别的系统性解决方案，还有很多有待 解决的问题。 1 3 本文的工作 全文的组织结构可以概括如下： 第1 章引言。介绍数学公式识别的研究背景、意义和国内外研究现状。 第2 章印刷体数学公式识别系统概述。介绍数学公式识别系统的组成，并对结构 分析阶段面临的困难进行分析。 第3 章印刷体数学公式结构分析。在分析已有的结构分析方法的基础上，介绍结 构预处理的方法，包括提取符号位置特征，计算符号质心以及提取符号串；然后采用基 线法处理一般公式；最后给出特殊公式( 如根式、积分、求和、极限以及矩阵) 的处理 方法。 第4 章结构分析算法改进。介绍回溯查漏机制，界限符号的特殊处理以及基线阈 值的再修正。 第5 章实验结果分析。对算法改进前后的结构分析方法进行对比，并对实验结果 进行分析。 第6 章结论与展望。对所做的研究工作进行总结，并对今后的研究工作提出建议。 河北大学t 学硕十学位论文 第2 章印刷体数学公式识别系统 2 1i ；p n 体数学公式识别系统的功能与组成 印刷体数学公式识别系统可以完成印刷体文档到电子文档的转变，实现对印刷体数 学公式的自动识别与理解，最终形成可供用户编辑的电子文件。该系统的输入是经过扫 描得到的包含数学表达式的文档图像，输出为识别出来的数学公式的排版语言( 如 l a t e x ) ，系统流程如图2 1 所示。 【- - l 图2 - 1 数学公式识别系统 ( 1 ) 印刷体文档输入：采用光学方法( 光电扫描仪、数码摄像机、c c d 器件) 获得 印刷体文档的二维图像，并输入计算机。 ( 2 ) 预处理：是对公式图像进行的有利于改善识别与分析效果的一系列操作的总称。 包括去除噪声、倾斜校正以及各种滤波处理等。预处理在实用系统中是一个很 重要的阶段，预处理效果的好坏会直接影响到整个系统的正确率。 ( 3 ) 公式抽取：在一般文献中，文本和公式常常混合在一起。要想处理数学公式， 就必须将其从文本中抽取出来。文档中的数学公式分为两种：独立公式和嵌入 公式。独立公式是指独占_ 行的数学公式，而那些和文本混合在一行中的数学 公式称为嵌入公式。 ( 4 ) 公式符号识别：公式符号识别阶段分为两个子过程符号切分【2 0 1 和符号识 第2 章印刷体数学公式识别系统 别。因为目前符号识别的方法大多数是针对单个符号的，而数学表达式往往由 很多符号组成，所以在符号识别之前，首先需要对公式图像进行切割，得到待 识别的单个符号图像；然后提取待识别符号的特征；最后设计分类器将待识别 符号与标准特征库中的符号进行比较，将相似度最高的符号作为符号识别结果。 ( 5 ) 公式结构分析：结构分析就是要利用符号的固有属性，如大小、位置和相应的 代码信息，结合公式结构和语义特征，确定公式符号之间空间关系和逻辑关系， 并以某种形式( 关系树或分析树) 表示出来。 ( 6 ) 公式重构：利用前面的识别、分析结果，生成标准的、反映公式原貌的电子文 档，以便进一步排版、存储等，必要时设计数学公式编辑器，以便用户对公式 进行修改和重用。 结构分析是公式识别系统的关键环节。结构分析阶段产生的结构关系树是重构的主 要依据，直接影响系统的最终输出结果。另外，对于结构分析阶段无法j 下确处理的符号 可以反馈回符号识别阶段重新识别，进一步提高系统的识别率。 由于数学公式的二维嵌套结构，及其复杂的语义信息，使结构分析成为公式识别系 统的难点。 2 2 印刷体数学公式结构分析的难点 数学公式自身的特点和结构决定了公式识别成为模式识别领域有待解决的关键问 题。公式结构分析的难点概括为以下几点： ( 1 ) 公式中的符号并不是简单线性排列的，而是呈二维结构排列分布( 如上下标、 分式等) ，相邻符号间的逻辑关系很大程度上取决于空间位置信息，带有很大 的不确定因素。 ( 2 ) 数学公式类型多样，包含大量的根式、分式、上下标、极限以及矩阵等特殊结 构，空间结构十分复杂。 ( 3 ) 数学公式包含的符号种类很多，如数字、英文字母、希腊字母以及运算符号， 不同类型的符号在公式中充当不同的角色，并且随着公式的不同而变化，不容 易分析。 ( 4 ) 由于数学公式特殊的二维嵌套结构，经常会出现多层嵌套的情况，增加了结构 鎏：i 查兰三茎竺圭兰堡堡三 分析的难度，如图2 - 2 所示的例子。 3 + 图2 - 2 分式多层嵌套的公式 ( 5 ) 数学公式中有很多约定俗成的规范，表示不同的数学含义。如删经常用来表 示一个函数，出用来表示微分号等等，这些语义特征给结构分析带来了不便。 ( 6 ) 一些符号可能和上、下脚标混淆，造成结构分析的错误。例如逗号、引号等通 常都会被分析成上下标。 f 7 ) 目前对数学公式尚没有规范的排版规则，敦科书、报纸、期刊、杂志等不同的 书籍有不同的公式排版规则，这给过度依赖空间关系的结构分析带来了很太难 度。 上述问题如果得不到有效地解挟，就会使结构分析阶段产生很多错误，并且进一步 影响重构结果。 口 第3 章印刷体数学公式结构分析 第3 章印刷体数学公式结构分析 数学公式中存在大量的根式、上下标、极限以及矩阵等特殊结构，这种复杂的二维 嵌套结构使得公式识别不能像识别普通一维文本那样，只按识别结果简单地把数学公式 中符号线性排列，这样做将使识别结果失去纵向的信息，无法重构出原来的数学公式。 所以，必须采用不同于识别文本的方法对数学公式进行结构分析，获取公式符号的二维 结构信息。 根据最终分析程度的不同，数学公式结构分析分为两个层次：版面结构的分析和语 义结构的分析。版面结构分析是利用识别后所得到的符号信息，分析符号间的空间位置 关系，得到公式的空间排列层次。它不需要完全理解整个公式的数学含义，只要求分析 结果足以恢复该公式的排版样式。为了弥补版面结构分析单纯地依赖符号物理属性的弊 端，在版面结构分析之后引入语义分析。语义分析是根据公式逻辑结构的知识建立相应 的启发式规则，纠正版面分析及识别过程中的错误，提取公式中的语义特性。本章提出 基线法和定位符号控制域相结合的版面结构分析方法对一般公式和特殊公式进行分析， 并且根据实验结果对算法进行改进，有效地提高了适用性和准确率，具体算法流程如图 3 1 所示。本章着重介绍版面结构分析，为了简便起见，下面的论述中均简称为结构分 图3 - 1 结构分析流程图 纠 错 返 回 重 新 处 理 河北大学t 学硕十学何论文 析。 3 1 结构分析方法综述 数学公式识别研究至今，大多数公式的结构分析方法事实上都是以一些句法为基础 的。还有一些研究者提出了其它的方法，有些方法只是在理论上被提出来，并未在实验 中进行验证；还有些方法实验的结果不是很理想，像p f e i f f e r f 2 1 1 设计了用普通的二维法 则脱离上下文来分割数学公式二维结构的分析器，但只限于从理论上分解，没有实际的 例子和实验结果。 现有的结构分析方法有以下几种： ( 1 ) 基于几何特征的分析方法。直接根据各个符号的种类、大小、相对位置以及符号 间的空白等几何信息判断出相邻符号的关系，生成符号组，合并子表达式，从而达到分 析数学公式的目的。这种分析方法可以较好地识别公式版式，但语义识别的能力相对较 差。 h a 2 2 】通过建立具有层次结构的表达式树分析数学公式。构造表达式树需要两个步 骤：( i ) 自顶向下。通过x 和y 方向上的反复投影得到初始表达式树。( i i ) 自底向上。 因为第一步投影时没有考虑相邻符号可能具有上下标等关系，所以还要从叶子结点到根 结点，根据位置关系对结点进行分解或合并，以得到最终的表达式树。 t w a a k y o n d o 和o k 锄o t o 【2 3 】采用自上而下和自下而上相结合的方法来决定给定表达 式的输出结构，一是用自下至上法来检查子表达式的局部结构( 特殊的结构处理方法) ， 用来分析上下标以及根式表达式；二是用自上至下法来检查整个表达式的整体结构( 基 本的结构处理方法) ，用来分析子表达式的水平和垂直方向的关系，表达式的结构也是 采用树结构描述的。 0 k 锄o t o 【2 4 】等采用表达式分类解析的方法，将表达式分为两类：一类是含有分式、 根号、括号或数组的子表达式，称为g r o u p a ；另一类是带有上下标或上下限的子表达 厂一 式，称为g r o u p - b 。对于g r o u p a 子表达式定义了一些核符号，如“( ”，“一”，“ ”， “【”，“ ”，“l ”等，然后通过查找这些核符号来分析表达式；g r o u p - b 子表达式则通过 查找上下标和上下限的符号区域来分析表达式。 l e e l z 5 , 2 6 1 使用符号关系树表示公式中各个符号间的关系。首先根据符号的特点，合 一r 第3 章印刷体数学公式结构分析 并邻近符号生成符号组，并使用符号关系树表示每个符号组。根据相邻符号的位置关系 以及上下文信息判断上标和下标。l e e 2 6 】还提到了矩阵分析的方法，并利用4 条启发式 规则改正表达式识别中的错误。 ( 2 ) 基于文法分析的方法。通过定义文法来分析数学公式的含义。文法分析的语义识 别能力较强，但是定义文法是很复杂和困难的。传统的产生式文法可以很好的表示一维 的文本，却不能表示具有二维关系的数学公式。研究人员采用不同的方法扩展传统的产 生式文法，使其具有表达二维数学公式的能力。 a n d e r s o n ! i 】于1 9 6 8 年首次提出纯粹的自上而下的方法。该算法是以一个最根本的 句法规则开始的，试图将问题分割为子目标，直到所有的子目标被满足或无法继续分下 去为止。他的工作( 尤其是指导识别的句法准则的应用) 不仅对数学表达式识别，而且 对一般的句法模式的识别都有指导意义。但句法规则是受限制的，当不满足这一规则时 ( 例如，的限制是式子的宽度要比自身宽) ，数学公式分析被拒绝。 c h a n 和y e u n g t 8 】采用结构和句法的方法开发了一个联机数学表达式识别系统，在 用弹性结构匹配方法识别符号之后，用句法分析的方法( 确定性子句句法，d c g ) 得到 数学表达式的结构。采用d c g 不仅能精确地定义替换规则，而且这些规则能很容易地 被执行，提出了一些用于解决d c g 中回溯问题带来的负面影响的方法，如绑定符号预 处理、层次分解。这种方法对向量和数组的识别很有效。 d i m i t r i a d i s t 2 7 1 除了定义句法规则外，还定义了语义规则。句法规则用来将复杂表达 式分解成简单表达式，而语义规则定义了句法规则各部分在坐标空间的相对位置关系。 t o u m i t t 2 8 】定义了6 级算符优先级，并使用树结构分析公式。分析树的构造过程如下： 首先构造一个只有一个叶结点的树，该结点表示整个数学表达式；然后化简叶结点，直 至不再包含复杂表达式为止。化简过程采用如下递归算法：( i ) 搜索表达式中最高优先 级的算符；( i i ) 根据该算符将复杂表达式拆分成相对简单的表达式；( i i i ) 处理新生成 结点。 g r b a v e c l 2 9 1 构造的系统e x p r e s s o 采用图改写的方法分析表达式。定义了大约6 0 条图改写规则，同时规定了每条规则的使用条件。所有的规则都形如吕：= g ，表示使 用子图g ，代替原图中的子图蜀。e x p r e s s o 目前只能处理包含上标和下标的简单表达 式，但它对公式的排版规式没有严格要求，而且可以检查出某些不合语法的公式。 河北大学t 学硕十学位论文 ( 3 ) 几何特征和文法相结合的分析方法。 c h a u d h u r i 和g a r a i n l 3 0 j 利用空间关系和逻辑关系解析的方法，将数学表达式的解析 过程分为两个阶段，第一阶段定义符号之间的空间关系，第二阶段判断各个符号之间的 逻辑关系。两个或更多符号依照它们之间的逻辑关系组成一些子表达式，由这些子表达 式最终组成整个表达式。 z a i l i b b i f 3 l 】等通过树变换来分析数学表达式的结构。整个过程可以分为3 个阶段。第 一个阶段构建初始基线结构树( b s t ) ，它主要描述输入笔划符号的二维布局，如“芝 就分成两笔输入。第二阶段通过变换将初始的b s t 变换成词法b s t ，在词法b s t 中 合并符号串组，包括十进制数字、函数名、以及多笔划符号如“ ，当然也包括垂直结 构如分式。第三阶段将词法b s t 变换成运算符号树，这个树表示输入表达式的运算顺 序。在每个阶段都是采用树变换来实现的。 综上所述，基于几何特征的分析方法过分依赖符号的空间位置信息，符号排版位置 稍有偏差就容易引起错误，而基于文法的结构分析方法则需要利用公式符号识别结果， 独立性较差。几何特征和文法相结合的方法弥补了两种方法的不足，具有更好的鲁棒性。 3 2 结构分析预处理 在对公式进行结构分析之前，公式符号识别阶段已得到了数学表达式中每个符号的 固有属性，如大小、位置和相应符号的a s c i i 码。而结构分析阶段是要在此基础上分析 得到符号的排列层次，并将其层次结构表示成为结构关系树【3 2 】。 预处理阶段是对识别阶段得到的符号特征进行加工以便顺应结构分析的需要，包括 提取符号的位置特征( 符号的外围坐标，质心坐标等) ，合并函数名和数字串。结构分 析阶段所需要的符号信息不能完整无误的通过识别阶段得到，因此需要先进行结构分析 预处理。 3 2 1 提取符号位置特征 印刷体公式中的符号外围特征的描述常用基于外接矩形的方法。如图3 2 所示，待 判断符号的外接矩形用( l e f t u p x ，l e f l u p y ，r i g h t d o w n x ，r i g h t d o w n y ) 来表示。其中 ( l e f i u p x ，l e r u p 】，) 表示外接矩形的左上角坐标，( r i g h t d o w n x ，r i g h t d o w n y ) 是外接矩形 1 0 - 第3 章印刷体数学公式结构分析 的右下角坐标。h l 和h 2 分别表示两个符号外接矩形的高。通过分析相邻符号外接矩形 的位置得到它们之间的关系。 3 2 2 符号属性 图3 - 2 符号位置特征的定义 数学公式分析相对于普通文本分析最大的不同就是数学公式分析的对象是一个特 殊的符号集，这个符号集包含的符号很多，且字体变化频繁；各个符号大小不一，形状 各异，无论外围特征还是排版规则都有很大的不同，给结构分析带来了诸多的不便。因 此最早由a n d e r s o n 提出了符号质心的概念i lj ，用来检测该符号是否位于某个域内。把符 号看成一个点便于进行几何分析。质心的x 坐标通常位于外接矩形框的中心，而质心 的】，坐标则与符号类别以及该符号是位于水平线的上侧( a s c e n d i n g ) 、下侧 ( d e s c e n d i n g ) ，还是在水平线上( c e n t e r e d ) 有关。 根据符号相对于水平线的偏移不同可把符号分为中心型、下降型、上升型三种，如 图3 3 所示。通常情况下符号的排版遵循三条线原则：顶线、中线和底线，中线的位置 心 型 升 型 心 型 降 型 升 型 顶线 中线基准线 底线 图3 - 3 不同符号的中心类型 一般就是基线的位置。上升型符号的上部超越到顶线的上面；下降型符号的下部跌至底 河北大学t 学硕十学何论文 线的下面；而中心型符号则会均匀分布在这三条线中，要么位于顶线和底线之间( 如x ) ， 要么分别延伸到顶线和底线外面( 如j b ) 。表3 1 统计出不同符号的中心类型。 表3 - 1 符号中心类型 符号类型 0 9 上升型 a z ，r ， ，巨，q b ，d ，l l ，i ，k ，1 ，t 6 ，0 ，入 a ，c ，e ，j ，m ，n ，o ，r ，s ，u ，v ，w ；kz c l ，t 3 ，e ，k ，v ，毛，o ，兀，o ，t ，u ，巾，6 0 兀，八，v ，n ，u ，厂，爹，丝，三， g ，p ，q ，y y ，r 1 1 a 。p 。x 。1 l r 上升型 上升型 上升型 中心型 中心型 中心型 下降型 下降型 数学表达式中的符号分为基本符号和特殊符号两种。基本符号包括英文字母、数字 和希腊字母。特殊符号进一步分为三种：( 1 ) 绑定关系符号( 如分数线、“ 、“兀”等) ， 1 0 它们同作用域中的表达式绑定在一起，如y f 2 中的求和符号就绑定了3 个子表达式 百 f - 1 、1 0 、f 2 ；( 2 ) 界定符号( 如括号) ，界定符号间的内容应看成一个完整的部分，具 有更高的运算优先级；( 3 ) 运算符号( 如“+ ”、“一”、“ 等) ，通常该类又可分为一 元操作符、二元操作符、三元操作符和胛元操作符，它们分别约束着各自的操作数。 为了便于结构分析，根据符号排版规则和类型不同将公式符号分为七类分别计算符 号的质心坐标。 ( 1 ) 英文字母和数字，例如p 、s 、1 、9 等。 ( 2 ) 希腊字母，例如q 、q 、入等。 以上两类符号在印刷体文档中都是按照上升、下降、中心型规范排版的，所以质 心的计算方法比较简单，x 坐标都是： c e n t r o i d x = l e f t u p x - t - ( r i g h t d o w n x l e f t u p x ) 2( 3 - 1 ) 上升型符号的质心y 坐标计算公式为： c e n t r o i d y = l e f i u p y + ( 1 4 ) ( r i g h t d o w n y - l e f l u p y )( 3 - 2 ) - 1 2 第3 章印刷体数学公式结构分析 中心型符号的质心】，坐标计算公式为： c e n t r o i d y = l e f t u p y + ( r i g h t d o w n y - l e f t u p y ) 2 ( 3 3 ) 下降型符号的质心y 坐标计算公式为： c e n t r o i d y = l e f t u p y + ( 3 4 ) ( r i g h t d o w n y - l e f t u p y ) ( 3 - 4 ) ( 3 ) 标点，例如“，、“ 等。标点符号又分为句末标点和其它标点，而句末标点 有时在公式排版中位于所有符号的右下角，结构分析时很容易分析成下标，所以这些符 号的质心坐标在分析时应特殊处理。 ( 4 ) 特殊运算符号，例如“n ”、“”、”、“a ”等。这些符号不管其是什么类型的， 因为是绑定符号，在排版时一般都位于中心位置，所以其质心坐标分别为五】，轴上的 中心坐标，如图3 4 所示。 图3 4 特殊符号的质心 ( 5 ) - - 元关系符，例如“+ ”、“”、“= ”、“s 、“”、“”等。这些符号在排版时一 般都是中心型符号，质心坐标即是符号中心坐标。 ( 6 ) 常用函数名，例如s i n 、c o s 、l i m 、s u p 、i n f 等。通过预处理阶段的合并函数名 操作，在结构分析中通常把函数名看成一个整体处理，其质心坐标一般是函数名中各符 号质心坐标的均值。图3 5 所示为合并后的函数名l o g 的质心坐标，计算公式如下： 1 c e n t r i o d x ( f u n c t i o n n a m e ) = l e f t u p x ( f u n c t i o n l ) + 主宰 r i g m d 。w n x ( 3 - 5 ) ( f u n c t i o n n ) - l e f t u p x ( f u n c t i o n1 ) 】 c e n t r i o d y ( f u n c t i o n n a m e ) = c e n t r i o d y ( f u n c t i o n l ) + c e n t r i o d y ，( 、 f f u n c t i o n 2 ) + + c e n t r i o d y ( f u n c t i o n n ) n 、7 河北人学r 学硕十学位论文 心 上升型中心型 卜降型 图3 - 5 函数名的质心坐标 其中为整个函数名所包含的符号个数，f u n c t i o n l 为函数名中第一个符号， f u n c t i o n 2 为函数名中第二个符号，f u n c t i o n n 为函数名中最后一个符号。 ( 7 ) 帽子修饰符，例如“a b c d ”、“石 、“a 、“石”。帽子修饰符一般都位于嵌套基 线中，和中心符号是上部的关系。这类符号的高度比较低，在处理同一层基线中的符号 时往往会漏掉它们，所以当公式中含有这类符号时相应的基线查找阈值应该大一些或对 这类符号的质心做特殊处理。 3 2 3 提取符号串组 数学公式中可以被看作一个整体独立处理的符号串称为符号串组。这样的符号串组 通常包括两种：复合型符号串组和结构型符号串组。复合型符号串组指处于同一水平线 上的邻近符号集合，它们表示一个独立的数学符号( 比如十进制数字、函数名等) ；结 构型符号串组指处于不同水平线上的通过彼此结构关系表示的数学符号的符号集合( 比 如分号、积分号等) 。由于结构型符号串的处理涉及到符号的二维逻辑结构，比较复杂， 所以在预处理阶段只考虑复合型符号组的合并，而对于结构型符号串的处理留待结构分 析中进行。 复合型符号串组的提取运用最长符号串匹配的方法。 规则3 1 函数名提取。 设：s = 岛s 2 s 。，f = f , f 2 。厶为符号串，其中s ，( o f 投) ，l ( o 歹m ) f f 寸任意符号，且 有f e 一，c 为函数名集合。 i f ( m = f ) a ( v f ) ( ( 0 f f ) a ( s ，= ，) ) t h e n s = f 如图3 - 6 所示为运用规则3 1 提取公式中函数名的语法树。常用的3 3 个函数名和不 誊i 茎：! i ! 堡鍪誊笔墓笔塑坌誊 常用的1 4 个函数名统计如表3 - 2 ，3 - 3 所示。 数学公式切分结果 圜3 击运用函数名提取规则的结构分析结果 表3 - 2 数学公式中常用函数的统计 表3 - 3 数学公式中不常用岖数的统计 e f t ( 概率积分) l i ( 对数积分) d n ( 亚柯比椭圆函数) e i ( 指数积分) s i ( 正旋积分) s n ( 亚纯函数) d i a g ( 对角线矩阵) m o d ( 横) c n ( 椭圆余弦 c a r d 【基数) 河北人学1 i 学硕十学位论文 规贝93 - 2 数字串提取。 设：s 为符号串集合，s 为符号串中的任意符号，c e n t r i o d ( s , ) 、w i d t h ( s , ) 、h i g h ( s , ) 分 别为符号s ，的质心、宽度和高度， d i g i t s 为数字集合，邑为符号串s 的第一个符号，且 有墨 d i g i t s 。 i f s = sj s d i g i t s ( ( c e n t r i o d ( s f ) 一c e n t r i o d ( s , ) ) 见) ( ( w i d t h ( s ) 一w i d t h ( s , ) ) 0 。) ( ( h i g h ( s f ) 一h i g h ( s , ) ) o h ) ) t h e n s d i g i t s ) 式中，眈、瓯和吼为相应的阈值。 公式中处于同一水平线上，大小相等，彼此相连的数字表示一个整体。然而，同一 数字以不同的大小和位置出现，可以代表不同的含义。例如，2 1 0 0 中2 和1 0 0 的大小和 位置不同，构成两个数字串；但在2 1 0 0 中，2 和1 0 0 的大小和位置相同，可被看作成 一个整体，如图3 7 所示。 c e n t r i o d ( s i ) 3 3 结构分析模型 h i g h ( s i ) 拿 f = 1 z 图3 7 数字串提取规则示意图 s 印刷体数学公式结构分析意味着要把一组具有空间位置关系的符号转化成一种可 以描述其逻辑关系的形式化语言。因此首先要建立一个数学模型，从数学公式中抽象出 符号集，然后定义一种形式化语言描述结构分析后的产物。 根据人书写公式的习惯，并参考l a t e x 语言描述公式的方法，定义了1 0 种基本 公式类型例，即分式、根式、定界、矩阵、组、帽子、堆叠、角标、普通单行和基元表 达式，如图3 8 所示。其中基元表达式是公式的最小组成单位，复杂公式都是由上述1 0 种公式类型组合而成的。 1 6 崮d 第3 章印刷体数学公式结构分析 型 分式表达式 ( a + b + + z ) 帽子表达式 r 2 ( f