（计算机软件与理论专业论文）数学公式结构分析系统设计与关键方法研究.pdf

摘要 摘要 数学公式图像的自动识别与理解，是文档图像处理与模式识别领域的世界级 难题。数学公式是非常复杂的一种文档结构，难以被计算机进行自动处理。对 数学公式文档图像进行精确地识别和理解的方法研究，具有广泛的应用价值和 学术价值。这也是文档图像识别理解领域的一个重点和难点问题。 随着数学公式图像识别领域研究的不断深入，结构分析系统的模型已经基本 成熟。目前，以句法分析为驱动、结合版面和语法分析的结构分析流程正在被 广泛的研究和使用。 本文就是在此基础之上，在研究和改进结构分析系统的同时，提出了基于多 层次基准线的结构分析方法，极大地减少了结构分析过程中搜索和判定的次数， 优化了分析系统流程和效率。 同时，本文重点着眼于结构分析子模块的关键技术的研究和评测，首次完整 的研究和描述了版面结构分析、语法结构分析、和句法结构分析模块中的一系 列关键技术和处理方法。 特殊文档图像理解的评测是一个重要且困难的问题。本文给出了数学公式图 像结构分析的评测参数和评测方法，并对本文所提出的系统进行了定性分析。 本文中实现的系统具有完备性和容错性，可以适应科研人员( 特别是数学领 域的科研人员) 对数学公式图像的处理要求，具有很高的应用价值。 关键词：数学公式句法结构分析语法结构分析版面结构分析句法结构树结 构分析评测 a b s t r a c t a b s t r a c t t h er e c o g n i t i o na n du n d e r s t a n d i n go fm a t h e m a t i c a lf o r m u l ai m a g e si saw o r l d c l a s s p r o b l e mi nt h e f i e l do fd o c u m e n ti m a g ep r o c e s s i n ga n dp a t t e r nr e c o g n i t i o n m a t h e m a t i c a lf o r m u l ad o c u m e n th a sv e r yc o m p l e xs t r u c t u r et h a tc a n n o tb eh a n d l e d a u t o m a t i c a l l yb yt h ec o m p u t e r t h er e s e a r c h e si nr e c o g n i z i n ga n du n d e r s t a n d i n g m a t h e m a t i c a lf o r m u l ad o c u m e n ti m a g e sh a v eg r e a te f f e c t si nb o t ha p p l i c a t i o n sa n d a c a d e m i cl e v e l t h es t r u c t u r ea n a l y z i n gs y s t e mm o d e li sg e t t i n gb a s i c a l l ym a t u r ed u r i n gt h el o n gt i m e r e s e a r c ho nm a t h e m a t i c a lf o r m u l ai m a g er e c o g n i t i o n a tp r e s e n t ，s y n t a x - m o t i v a t e d a n a l y s i s ，c o m b i n e dw i t ht h el a y o u ta n dg r a m m a t i c a la n a l y s i si sb e i n ge x t e n s i v e l y s t u d i e da n du s e di nt h es t r u c t u r ea n a l y s i sp r o c e s s t h i sa r t i c l ep r e s e n t sam u l t i - l e v e lb a s e l i n es y n t a c t i cs t r u c t u r ea n a l y s i sm e t h o dw h i c h i m p r o v e st h eo r i g i n a ls t r u c t u r ea n a l y s i sm e t h o do nr e d u c i n gt h en u m b e ro fs e a r c h i n g a n dd e t e r m i n i n gd u r i n gt h es t r u c t u r ea n a l y s i sp r o c e s s ，m e a n w h i l et h es y s t e ma n a l y s i s p r o c e s sa n de f f i c i e n c yi so p t i m i z e d t h i sa r t i c l ei sf o c u s e do nt h er e s e a r c ha n de v a l u a t i o no fs t r u c t u r a la n a l y s i sm o d u l e a tt h es a m et i m e ，as e r i e so fk e yt e c h n o l o g i e sa n dm e t h o d si nl a y o u ts t r u c t u r e a n a l y s i s ，g r a m m a t i c a ls t r u c t u r ea n a l y s i s ，a n ds y n t a c t i cs t r u c t u r ea n a l y s i sa r er a i s e d a n dd e s c r i b e dc o m p l e t e l y t h e e v a l u a t i n go fs p e c i a ld o c u m e n ti m a g ei sa ni m p o r t a n tp r o b l e m i nt h i sp a p e r , t h e e v a l u a t i o nm e t h o d sa n dp a r a m e t e r si nm a t h e m a t i c a lf o r m u l ai m a g es t r u c t u r ea n a l y s i s i sp r e s e n t e d ，a n daq u a l i t a t i v ea n a l y s i si sg i v e na tt h es a m et i m e t h es y s t e mp r e s e n t e di nt h i sa r t i c l ei sp r o v e dar o b u s ta n de f f i c i e n tm a t h e m a t i c a l f o r m u l ai m a g ed o c u m e n ta n a l y s i ss y s t e mw h i c hc a nm e e tt h en e e d sf o rr e s e a r c h e r s ( e s p e c i a l l yf o rm a t h e m a t i c a lr e s e a r c h e r s ) i nm a t h e m a t i c a lf o r m u l ai m a g ep r o c e s s i n g k e yw o r d s ：m a t h e m a t i c a lf o r m u l al a y o u ts t r u c t u r ea n a l y s i s g r a m m a t i c a ls t r u c t u r e a n a l y s i ss y n t a c t i cs t r u c t u r ea n a l y s i ss y n t a c t i cs t r u c t u r et r e e s t r u c t u r ea n a l y s i s e v a l u a t i o n i i 图目录 图目录 图1 1 数学公式图像自动处理过程2 图1 2 数学公式图像处理三个层次的关系3 图2 1 基准线与核心骨干线1 0 图2 2a 类表达式版面范围11 图2 3 数学公式句法结构模型组成1 3 图2 4 利用语法规则确定字符属性1 6 图2 5 语法规则确定操作符的作用域和组合关系1 6 图2 6 利用句法规则进行优先级结构比较1 7 图2 7 数学知识库结构模型18 图2 8 公式结构行与语义行19 图2 9 基于多基准线的句法结构分析过程描述2 1 图2 1o 数学公式结构分析工作模型2 3 图2 11 对树结构进行分析的主控流程2 4 图2 1 2 结构分析系统架构图2 5 图3 1 西文字体结构及术语示例2 7 图3 2 符号中心线调整前后位置对比2 8 图3 3 数学公式骨干区域示意图2 9 图3 4 不平衡分式表达式示例2 9 图3 5 包含复杂下标表达式示例一3 0 图3 6 复杂指数表达式示例3 0 图3 7 骨干线提取流程设计3 0 图3 8 根式外接矩形位置调整。3 4 图3 9 定界子表达式合并示例3 5 v 图目录 图3 1 0 定积分表达式的组合关系示例3 8 图3 11 语法规则指导的表达式处理方法一3 9 图3 1 2 子表达式区域示意4 0 图3 1 3 角标关系类型示例4 2 图3 1 4 角标关系判定和分析流程图4 3 图3 15 角标区域划分示意图4 4 图3 16 函数名搜索算法4 6 图3 17 句法结构树的逻辑结构及实现结构4 7 图3 1 8 操作符目类型确定子表达式域示例4 8 图3 1 9 子表达式句法树结构示例4 8 图3 2 0 公式骨干层次结构示意图4 9 图3 2 1 句法结构树的详细扩展过程5 1 图3 2 2 语法规则对字符识别错误的校验5 4 图3 2 3 语法规则对子表达式树结构的校验5 5 图4 1 数学公式版面复杂度计算示例一5 7 图5 1 不同重现方式的m a t h m l 形式6 5 图5 2 句法树结构与呈现型m a t h m l 的映射关系6 6 v i 表目录 表目录 表1 1 数学公式文档的层次结构8 表2 1 子表达式分类示例1 2 表2 2 数学公式版面类型示例15 表3 1 定界表达式组合关系类型3 5 表3 2b 类表达式操作符的组合方式3 8 表3 3 操作节点中间状态及处理方法4 8 表4 1 样本集符号统计情况6 l 表4 2 实验样本集评测结果6 1 v i i 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 珈7 年多 日 南开大学学位论文版权使用授权书 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 供本学位论文全文或者部分的阅览服务；学校有权按有关规定向国 的的前提下，学校可以适当复制论文的部分或全部内容用于学术活 学位论文作者签名：暂葬 抄7 年占月1 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： 第一章前言 第一章前言 第一节数学公式图像自动处理 数学公式图像的自动识别与理解，是文档图像处理( d o c u m e n ti m a g e p r o c e s s ，d i p ) 与模式识别( p a t t e r nr e c o g n i t i o n ，p r ) 领域的世界级难题。数学 公式是非常复杂的一种文档结构，广泛存在于各类文献书籍与技术资料中。由 于数学符号的多义性和数学公式结构的多变性，使得数学公式难以被计算机进 行自动处理，难于在i n t e m e t 上进行广泛传播，大量的数学公式依然以图像的方 式进行保存，这大大降低了数学领域知识共享与信息检索的效率，也给教育、 科研、工程技术等领域的信息化工作制造了巨大的障碍。因此，对数学公式文 档图像进行精确地识别和理解的方法研究，具有广泛的应用价值和学术价值。 数学公式图像的自动识别( o p t i c a lf o r m u l ar e c o g n i t i o n ，o f r ) 是能够根据 数学公式中字符之间的关系获得其结构信息的技术。一般来讲，自动识别过程 可以被划分为四个部分：公式定位、字符识别、结构分析和结果重现，如图1 1 所示。可见，数学公式文档图像处理方法的发展主要受到以下几类技术的影响 和制约： 1 文档图像处理技术。 通常，普通文档图像中不仅包含数学公式，还包含普通文本以及图表等版 面元素。因此，需要首先对文档图像版面结构和逻辑结构进行分析和理解，然 后从文档图像中确定数学公式的位置，从而将公式图像提取出来。 目前，o c r 技术已经非常成熟，通用文档图像处理系统能够较好的完成一 般文档图像从版面分解到最终版面恢复输出的全过程。但不同于普通文本图像， 由于数学公式复杂的版面及语义特征，到目前为止，仍然没有完整、实用的数 学公式图像自动处理方法和系统出现。 2 字符切分及识别技术。 数学公式符号识别技术就是在数学公式定位以后，切割并识别出数学公式 中的所有数学符号。 目前，商业o c r 系统能很好地处理1 一d 文本，能够将文本图像切分并识别 转化为与之相对应的字符。但数学公式通常不是1 d 的，且字符大小不一，符 第一章前言 3 9 目分* 1 2 从女# 目镕中自位m 育 ，： ! v = c l o g ，。d + l “i ) 2 ：一”j 图1j 数学公式图像自动处理过程 l a t e x m a t l a b m a t h m l 号出现的频率也不同于普通义本，而且公式中经常会出现希腊宁母、运算符号 等一般o c r 识别引擎不能识别的符号。许多针对普通文本的方法用于数学公式 符号识别时往往会适得其反，使得一般o c r 系统对数学公式无能为力，公式符 号识别率往往降到1 0 左右，甚至更低。 霉 躲 第一章前言 3 表达式结构描述及分析方法。 要实现对数学公式结构的正确识别和理解，首先就需要建立数学公式结构 描述模型，准确地反映出公式图像和语义之间的关系。并在此基础上，设计分 析流程，完成对数学公式图像结构的识别和理解。 数学公式文档图像处理的过程极其复杂，目前还没有一个现实的系统能达 到令人满意的效果。所有关于数学公式图像自动识别的理论和技术还都处于试 验阶段。本文所研究和描述的就是这个分析系统的一个核心部分一“结构理 解与重现 ( s t r u c t u r eu n d e r s t a n d i n ga n dr e p r e s e n t a t i o n ) 的系统设计和关键处理 方法。 第二节数学公式结构分析概述 1 - 2 1 数学公式结构分析的重要性 数学公式，是由数字、代数符号、运算符号等符号构成，表示数量、变量、 运算、或数学规律的一个或一组符号【l 】。 任何一个具体的数学公式，都是由一系列符号组成的。这些符号之间的相 对空间位置决定了公式的版式结构，其相互之间的组合关系展示了数学公式的 语法意义，而它们之间的运算关系则决定了数学公式的语义含义。因此，机器 理解数学公式，同样需要从认识符号、分析公式结构及理解公式语义这三个层 面上进行。图1 2 展示了这三个方面的依赖关系。 图1 2 数学公式图像处理三个层次的关系 在早前的研究工作中网，针对数学公式图像的识别与理解还集中在识别符号 到结构理解的地步。对公式版式结构的理解也大多单纯基于公式符号的大小、 字体、版面位置等信息来进行，并未考虑到公式符号之间的组合关系及公式的 语法规则。这样的数学公式文档处理方法存在这很大的缺陷：首先，单纯依靠 版面信息无法有效消除数学符号的歧义性，这会极大的降低识别结果的正确性， 3 第一章前言 无法满足基本的应用需求；其次，版面分析不能准确理解数学公式的计算含义， 这就无法对识别结果进行校验，也无法应用于更高级的语义理解研究方向。无 法保证识别稳定性的同时，也限制了数学公式文档识别与理解研究的发展。 因此，为了更准确地了解公式2 d 版式结构，同时为了更进一步的进行公 式语义含义的理解，设计一个完整、实用的结构分析方法是至关重要的。 1 2 2 数学公式结构分析方法 1 2 2 1 数学公式结构分析方法历史和分类 数学公式的结构分析方法根据其处理目标和处理层次的不同，可以分为三 类： 1 基于版面的分析方法 基于版面的分析方法就是直接根据各个符号的内容、大小、相对位置以及 符号间的空白等结构信息判断出相邻符号的关系，生成符号组，合并子表达式， 从而实现数学公式分析的方法。 l e e 等人3 】 4 11 5 最早使用符号关系树( s y m b o lr e l a t i o nt r e e ) 表示公式中各 个符号之间的关系，关系共有6 种，分别是：上，下，右，上标，下标以及子 表达式。以特殊符号为中心搜索临近符号，生成符号组，并生成每个符号组的 符号关系树。该方法可以处理简单公式，但不能处理多行以及复杂的单行数学 公式，而且时间开销大1 6 j 。 o k a m o t o 等人【7 】【8 1 采用自底向上和自顶向下相结合的方法识别数学公式的 版面结构。自顶向下的方法用来分析表达式在水平方向和竖直方向上的关系。 自底向上的方法用来处理对于上标、下标或者包含的关系。在一定程度上节省 了计算开销，但是仅仅根据版面信息分解表达式，不可能处理的完全正确。在 上下标和矩阵处理上还不是很完善，而且不能处理含有帽子符号的，即一个符 号在多个符号上方的公式。 h a 等人 9 】通过建立具有层次结构的表达式树分析数学公式。该方法将公式 中的每个符号都看作一个简单对象。若干个组合在一起并具有数学含义的简单 对象构成一个复合对象。表达式树的每个节点都代表一个简单或复合对象；根 节点表示整个数学公式；内部节点代表复合对象；叶子节点代表简单对象；每 个内部节点指向一个或多个子节点，表示该节点代表的对象可以分解成由子节 点表示的子对象。并通过自顶向下和自底向上两个步骤来构造表达式树。该方 4 第一章前言 法的分析过程过于简单，因此稍微复杂一些的公式就无法分析。 f u k u d a t l o 】提出的数学元件( ) 的概念，数学元件就是一组数学符号，它 包括一个母字符和若干个子数学元件。f u k u d a 定义了数学元件之间的九种关系， 根据元件之间的位置关系，计算出每种关系的惩罚值，具有最小惩罚值的关系 就是正确的关系。 上述分析方法都是基于版面信息进行数学公式结构分析。单纯依靠符号之 间的位置信息判定符号之间的关系，必然不能够对具有复杂位置关系的数学公 式进行分析，而且还会容易将符号之间的关系分析错误。 2 基于文法的分析方法 文法分析的方法是通过定义文法实现数学公式分析。文法分析的语义识别 能力较强。但是因为数学公式的形式是多种多样，并且数学符号具有二义性， 所以单纯依靠文法只能分析有限类型的公式。 b e l a i d t i l l 定义了2 1 条上下文无关文法分析数学公式。b e l a i d 首先根据字符 的位置以及算符的优先级别，找到一个算符其分析的起点；然后搜索包含该算 符的文法，利用文法分解表达式，然后再针对分解后的子表达式重复上述方法。 如此反复下去，直到所有区域只包含唯一字符为止。b e l a i d 定义的产生式文法简 单只能很好的分析一维的数学公式，却没有方法分析具有二维关系的数学公式。 后续的研究者采用不同的方法【1 2 1 1 3 1 1 4 1 1 5 1 1 6 1 力图扩展传统的产生式文法，使其 具有表达二维数学公式的能力。 t o u m i t b 3 1 定义了六级的算符优先级，并使用树结构分析公式。分析树的构造 过程如下：首先构造一个只有一个叶节点的树，该节点表示整个数学表达式； 然后化简叶节点，直至不再包含复杂表达式。该方法定义的六级算符优先级别 不能覆盖所有优先级别情况，因此处理的数学公式类型具有局限性。 另一种基于文法的方法是基于图文法进行数学公式分析。g r b a v e c 1 7 】构造的 系统e x p r e s s o 采用改写图的方法分析数学表达式。该系统定义了大约6 0 条 图改写规则并规定了每条规则的使用条件，所有的规则都形如g l ：= g r ，表示使 用子图g r 代替原图中的9 1 。由于图改写规则抽象，简单，所以只适用于简单数 学公式的结构分析。目前只能处理包含上标和下标的简单表达式，但它对公式 的排版格式没有严格要求，而且可以检查不合句法的公式。 以上基于文法的分析方法，虽然包含了符号之间的文法关系，但都存在着 文法定义抽象，内容不能覆盖各种数学公式类型情况。因此在结构分析中具有 5 第一章前言 局限性。 3 基于语法的分析方法 通过上文对数学公式版面结构分析方法的总结，可以看出，对数学公式版 面结构的处理还只是单纯的依靠传统模式识别技术，对各个符号的大小、字体 和版面位置信息进行分析，其分析结果也只是简单地展示了数学公式的版面结 构，并不能抽取数学公式的完整信息结构。 而语法结构分析方法就是基于数学公式的语法规则来实现对数学字符之间 相互关系的判定和重组。语法结构是介乎于图像信息( 版面结构) 和逻辑含义 ( 语义含义) 之间的描述机制，既体现出公式的语法规则、指导公式版面形式， 又能对识别和结构分析结果进行有效地校验。 1 2 2 2 基于多基准线的结构分析方法 从2 0 世纪6 0 年代末，a n d e r s o n 【1 1 】意识到数学公式的语法指导对数学公式图 像结构分析的重要性以来，语法信息和规则在公式结构分析过程中扮演着越来 越重要的角色。但随着研究和应用的不断深入，单纯依靠版面关系，无法理解 公式结构的逻辑含义，无法满足更高级的语义结构分析的需求。这就需要对公 式进行更高层次的句法结构分析。 综上，可以看出不同的结构分析方法具有各自的优势： 版面分析能够精确获取符号的版面位置、大小、相对位置、符号间空 白等版面信息，为更高级的分析提供最基础的判断和依据； 语法分析能够指导和约束符号间的相对位置和组合关系，有效消除符 号的歧义性。同时对识别结果和结构分析结果有很好的校验功能； 句法分析能够理解公式的逻辑含义，保证结构分析的准确性。 本文提出了一种基于多层次基准线的数学公式结构分析方法。它综合了上 述三种分析方法：以句法结构分析为主导，版面分析和语法分析为辅助和校验。 这种方法既可以实现对数学公式结构的重现，同时又可准确的理解数学公式所 表达的计算含义，为数学公式的语义分析和高级应用提供帮助。 1 2 - 3 结构分析中的关键技术 以上在宏观方面，可以将结构分析划分为版面分析、语法分析、句法分析 三大类。但由于数学符号的特殊性和符号间二维相对位置的复杂性，就需要对 6 第一章前言 结构分析流程从微观的角度来进行细化，从而提出了多个关键的细节处理技术。 主要包括以下几个方面： 1 公式核心骨干层次的提取方法 一个具体的数学公式中，往往包含多个结构行和一个或多个语义行( 定义 见2 1 节) 。准确的提取出公式的核心骨干层次( 语义行) ，并明确语义行和结构 行之间的对应关系，是进行句法结构分析的基础。 2 子表达式的合并分解 子表达式包含定界子表达式、分式子表达式、根式子表达式等多个类型， 每一个不同类型都包含各自的版面和语法规则信息。因此，针对每一个特殊类 型，都要设计具体的处理方法，才能保证子表达式被正确的合并分解。同时， 子表达式之间还有着复杂的相对位置关系，对于相互关联的子表达式，还需要 设计特别的处理算法。 3 角标的判定 正是由于角标这种特殊结构的存在，使得数学公式在结构上具有区别与普 通文本的维数特征。角标关系貌似简单，但是符号间的相对尺寸或空间位置的 微小变化以及符号的错误识别结果，都可能造成相邻符号之间关系判断的错误， 最终造成对整个数学公式的错误理解。设计一种针对角标关系的结构分析机制 是实现一个完整可靠的数学公式图像识别与理解系统的必要环节。 4 字符合并 通过对大量样张的观察分析，有很多情况是不能只考虑独立的符号的，组 合之后的符号可能会具有新的含义。因此，需要对数学公式中的符号进行细节 分析和合并，使之成为基本语义符号( 定义见2 1 节) 。符号合并主要包括函数 名合并、变量名合并和数字合并。 5 句法树的生成和扩展方法 句法树是结构分析流程的最终结果，它本身的结构反映了数学公式的版面 结构。同时，句法树的扩展过程，又反映了公式的计算顺序和语义含义。因此， 设计一个好的句法树结构模型和扩展方法，能够极大的提高结构分析的准确性 和系统分析效率。 6 结构分析结果的校验 由于数学公式符号和结构的复杂性，识别结果的错误以及结构分析中微小 的判定失误都可能造成分析结果错误。因此，在结构分析之后，需要设计有效 7 第一章前言 地校验机制，对分析结果进行验证，保证结果的正确性和唯一性，提高系统容 错性。 本文的第三章，对以上关键技术进行了详细的设计和描述。 第三节数学公式图像的重现 科技文献中的大量数学公式图像只有经过结构分析进行重现之后才能得到 广泛的应用。这种应用包括对数学公式的再编辑和重用两种。通过重现数学公 式，结构分析才能体现出其价值。根据数学公式文档结构层次的不同，重现在 不同的层次具有不同的含义和表现形式，主要分为三种，见表1 1 。 表1 1 数学公式文档的层次结构 分析 分析层次分析目标重现目标 级别 实现机器c c + + 或 il 语义理解 自动计算 m a t l a b 代码 一l 实现公式 句法重现m a t h m l 文档 的再编辑 1 ： 版式重现 实现公式 l a t e x 、 0 m a t h m l 文档 的图像重现 1 重现版面结构 根据版面识别结果中符号之间的空间位置关系重现版面结构，使用l a t e x 等排版语言输出。主要应用在版面结构分析方法中。 2 重现句法结构 在重现版面结构的同时，重现符号之间的句法关系，重点在于重现公式的 句法结构。使用m a t h m l 语言输出，不仅包含了丰富的句法信息，而且利于在 各种应用环境中使用。 3 重现语义含义 重现数学公式的语义含义，即公式的计算内容，并使用l i s p 或m a t l a b 等数 学计算语言输出。实现数学公式的自动计算就需要分析出公式的语义。 8 第一章前言 第四节本文研究范围及内容组织 1 4 1 本文研究工作重点 前人关于结构分析的论文多是分析和建立结构分析的理论模型，然后根据 模型提出一个较完整的结构分析整体流程，并对其进行系统级的评测。鉴于基 于句法和语法结构分析的模型已经日趋成熟。本文在此基础上，改进并完善数 学公式结构分析流程，创新性的提出“基于多基准线的数学公式结构分析模 型 。并对在此模型基础上的结构分析系统进行设计和实现。 同时，本文重点对数学公式结构分析流程中的关键处理方法进行研究和描 述。首次完整的提出了版面结构分析、语法结构分析、和句法结构分析模块中 的一系列关键问题的处理方法，并对其进行性能评价。 1 4 2 内容组织 下面介绍本文各章的主要内容： 第一章，概述数学公式文档图像自动处理的意义；介绍数学公式结构分析 的方法，以及对应不同结构层次的重现方法；明确结构分析过程中的核心关键 技术和处理目标。 第二章，定义和说明结构分析中的术语；介绍数学公式句法结构描述模型 和底层知识库模型；提出基于多基准线的结构分析方法和系统设计方法；介绍 数学公式结构重现方法。 第三章，重点研究结构分析系统中预处理、版面结构分析、语法结构分析、 句法结构分、后处理五个核心模块的功能和实现方法；详细介绍各个模块中的 关键处理技术。 第四章，介绍了结构分析系统评测参数的选择方法和评测方法设计；针对 不同的功能模块进行具体功能评测；并对数学公式结构分析系统的完整性、精 确性、稳定性方面给出详细评价。 第五章，对本文研究工作进行总结；提出尚待解决的问题；对未来数学公 式及其他特殊文档的结构分析技术发展进行展望。 9 第二章数学公式结构分析系统设计 第二章数学公式结构分析核心方法 第一节全文术语定义和说明 数学公式中经过识别后得到的不可分割的最小符号单位。例如英文字母、 数字、希腊字母、运算符等。 一操作符和操作数 在本文数学公式所包含的所有符号被分为操作符和操作数两大类。 操作符：包括运算符、函数名及某些特殊符号，在数学公式中表示对一个 或多个操作数的某种操作关系，或某种特殊数学规律。 操作数：由数字、英文字母、希腊字母等代数符号构成，在数学公式中表 特殊操作符就是在版面上能够表现出二维结构特征或具有组合关系的操作 符。例如、兀、_ r 、爹以及分数线、定界符等都是特殊操作符；而像+ 、一、 x 等就是普通操作符。 操作符作用域 作用域是指所有参加当前操作符控制的运算的符号所在的区域的并集。例 如分数线的作用域就是它的分子和分母和它本身所占区域的并集。 _ 基准线与核心骨干线 基准线，是指将公式中所有符号按照其中心线位置进行聚类，形成一个或 多个结构行，基准线是公式结构行位置的标识。 步号乏二磊一一 - i - - ! j i p 隹i 4 1 0 第二章数学公式结构分析系统设计 核心骨干线，是公式当前所有基准线中，具有分析优先级最高的一条，通 常是反映公式核心结构的结构行所在的位置。 _ 语义单位和基本语义单位( u n i t ) 语义单位，是指在当前的语义行中可以表现语义的最小单位。即它在当前 语义行中，在保持行意义信息的前提下不可再分解。语义单位只是相对于某个 语义行的概念，如果换一个环境，原来的语义单位就可能成为一个语义行而被 继续分解。例如被合并的分式表达式、图2 1 中的i = l 等。 基本语义单位，是指在语义上不可以再分的语义单位，通常有一个或多个 符号组成。例如单个符号、函数名、变量名和数字。 _ 操作符的优先级 本文中所提到的操作符优先级不同于实际数学公式运算中的操作符优先级 概念，本文自定义了一套操作符优先级，作为数学公式句法结构分析的主要控 制参数。 子表达式 子表达式是构成数学公式的逻辑元素，一个数学公式可由一个子表达式或 多个子表达式组合而成。它是表达某种运算关系或者某种特殊数学规律的组合。 本文根据公式的版面特征及子表达式自身的语法属性，定义以下规则： 1 字符或子表达式在数学公式中以版面从左至右的顺序排列； 2 如果子表达式的版面位置范围可以完全由该子表达式的核心字符决定， 则定义其为“a - 类子表达式 【l 引。例如，单个字符组成的表达式，分 式表达式、根式表达式、定界表达式等； 囵团固团烈j幽 图2 2a 类表达式版面范围 3 如果子表达式的版面位置范围需要由它包含的所有字符共同决定，则定 义该子表达式为“b 类子表达式 。例如，函数表达式、积分表达式、 第二章数学公式结构分析系统设计 连加连乘表达式等。 根据以上规则，可以将常见子表达式分类如表2 1 所示： 表2 1 子表达式分类示例 ? 子表达式类型核心操作符子表达式示例 单个或多个连续 字符 字符本身 x ，靠，e ，a ，1 ，2 3 6 a a x 2 + 2 b i 分式表达式 类 3 x 3 一口 子 根式表达式r 4 2 a 2 4 a b 2 n + 呵s i n x c o s ( 2 x ) 表 v 达 定界表达式 ( ) ， ，2 ( a + b ) q l q 2f x , x 0 式 一口2 1a 2 2 一户t o ，x o 推导表达式 一4 _ 忍 积分表达式 s ，弧，r 2 x d x ( f a c o s x t a n x d x b l 连加连乘 ，兀a i兀( 葺+ 吒一。) f 曩lf = 1 类 子 并集交集 n ，u n 互u 二4 表 f 皇l 达 函数表达式 s i n ，m a x , l i m l i m 半m a x ( 口一c ) 式 x - - + o t 7 普通表达式 + ，一， a x + y m n 第二节数学公式结构分析模型 随着数学公式结构分析领域研究的不断发展和深入，基于语法和句法结构 分析的模型【1 9 】已经日趋成熟，并被越来越多的学者研究和使用。在进行流程和 系统的设计之前，有两个重要的问题需要重视和解决：建立数学公式句法结构 描述模型；提取数学公式语法规则、句法规则，并对其进行有效地存储和管理。 本节将对这两个问题进行分析和描述。 1 2 第二章数学公式结构分析系统设计 2 2 1 数学公式句法结构描述模型 本文使用四元组结构【2 0 】描述数学公式的句法结构，如图2 3 所示。 s y n t a c t i cs t r u c t u r e = ( l a y o u ti n f o r m a t i o n ，s y m b o ls e t , g r a m m a rr u l e s ， s y n t a c t i cr u l e s ) ； 其中： 一l a y o u ti n f o r m a t i o n ：版面结构，数学公式中所有符号和公式结构的版面位置 信息。版面信息可用于判断作用范围、提取不同层次的子表达式，是重要的 辅助信息； - s y m b o ls e t ：符号集，数学公式中所有出现的操作符和操作数。根据符号内 容可调用相应的语法规则，确定符号之间的组合关系，检查符号出现的合法 性； _ g r a m m a rr u l e s ：语法规则，不同符号之间的语法约束与组合关系。它用于 确定操作符的作用域和子表达式内容，同时检查发现识别结果中存在的错 误，保证子表达式提取的完备性和正确性； _ s y n t a c t i cr u l e s ：句法规则，子表达式的分解与约束关系。此类规则主要负 责分析不同运算符之间的优先级顺序，消除数学公式符号的多义性，并可被 快速解析转换为其他的数学公式描述形式。 句法属性 ( 数学公式) r j _ l 一 语法属性 ( 子表达式) r j _ _ 字符集 ( 识别结果) 弋 j _ l 。一 版面信息 ( 文档图像) 子表达式之间的 组合和约束关系 符号之间的组合 和约束关系 符号识别结果 图像中符号的位 置坐标、字号、字体等 图2 3 数学公式句法结构模型组成 2 2 1 1 数学公式的基本版面结构 版面结构包括公式中字符的版面信息和公式结构版面信息两部分内容。 1 3 第二章数学公式结构分析系统设计 字符的版面信息，包括字符的外界矩形位置坐标、字符中心线、字体、字 号等信息。 公式结构版面信息，包括公式的版面类型、基准线位置以及多条基准线间 的相互关系等。数学公式中的符号根据其语法属性不同体现出不同的排版风格。 根据公式符号的水平中心线( h c l ) 排列情况，可对数学公式的类型进行如下 划分： 1 基元表达式( u n i te x p r e s s i o n ) 数学公式中的独立符号，不可再分，主要是指不具有运算功能的运算数或 基本语义单位； 2 普通表达式( c o m m o ne x p r e s s i o n ) 绝大部分符号排列在相同的h c l 上，呈现一维版式结构； 3 角标表达式( s c r i p te x p r e s s i o n ) 角标是一种特殊的语法约束关系，角标符号的h c l 位于其描述符号的左上、 左下、右上、右下四个方向上； 4 组表达式( g r o u pe x p r e s s i o n ) 一些特殊的运算符会与其他符号组合成2 d 结构的版面形式，如根式、求和、 积分、分式等； 5 矩阵表达式( m a t r i xe x p r e s s i o n ) 由特殊定界符包含多行多列符号组成的表达式，如行列式、矩阵等； 6 堆叠表达式( s t a c ke x p r e s s i o n ) 描述说明符号在数学公式中常以堆叠的形式出现，它们不是具有固定语法 规则的组表达式，如帽子符号等。 表2 2 描述了不同版面类型的基础数学公式。对基础类型进行准确的划分和 分析，有助于对公式整体结构的分解和重构。 1 4 第二章数学公式结构分析系统设计 表2 2 数学公式版面类型示例 版面类型公式示饲 a 基元表达式以 b 普通表达式y = 2 x + 7 z c 角标表达式 f d 组表达式 f 厂( x ) 出 u h 。五：1 e 矩阵表达式 i 恐。场h l y 一2 一i f 堆表达式 a + x y + z 2 2 1 2 数学公式符号集的组成和类别 数学公式的符号可分为操作符和操作数两类。操作符：包括运算符、函数 名及某些特殊符号，在数学公式中表示对一个或多个操作数的某种操作关系， 或某种特殊数学规律；操作数：是指由数字、英文字母、希腊字母等代数符号 构成，在数学公式中表示数量、变量等含义。根据符号的类型可选用对应的语 法规则进行深入的子表达式分析。 本文研究工作针对正体斜体英文字字母、数字、标点、希腊字母、数学符 号、三角函数共计3 6 9 个符号，覆盖了科技文献中所有数学公式的常用字符。 2 2 1 3 数学公式的语法规则 语法规则，规定了数学公式中字符的语法属性，以及不同符号间的语法约 束与组合关系。对数学公式的分析过程中，语法规则具有如下作用： 字符语法属性分类。语法规则可以通过对字符间空间关系的判断，确定字 符的唯一语法属性。图2 4 描述了对“+ ”进行语法判断的过程。 组合和分解“子表达式( 定义见2 1 节) 。语法规则可以通过作用域信息， 将具有组合规则的运算符与其附属字符合并，成为一个子表达式，如图2 5 。 15 第二章数学公式结构分析系统设计 语法规则验证。结合识别结果和版面信息，语法规则还可以用来纠正识别 错误、消除多语义字符的语法歧义、实现对句法树结构的校验和修改。( 详见3 4 节) 勖+ 口 ，一一一一一一一一一一一一、 ir i g h t ( + ) 2 0 p e r a n d & & 1 v l 、l e f t ( + ) = o p e r a n d! r i g h t ( + ) 2o p e r a n d & & l e i t ( + ) 2 n u l l 凸 厂、 l 该字符表示字符属性l 、 图2 4 利用语法规则确定字符属性 j 。 t o p 黜g h t ：积分上限 b o u o m r i g h t = 积分下限 * r i g h t = 积分函数 * s i g h t e n d = 微分符号 语法规则( 为必要条件) 图2 5 语法规则确定操作符的作用域和组合关系 2 2 1 4 数学公式的句法规则 不同类型表达式的组合形成了多重层次的数学公式结构，同层次操作符之 间的优先级关系决定了数学公式的计算顺序。 句法规则描述每个操作符的子表达式形成规则，每一个操作符都有一个固 定的树型结构模板，其中子节点的个数和属性均根据语法规则预先填充。图2 6 描述了根据句法规则中不同的优先级关系生成的不同子表达式结构。 句法规则同时负责判断操作符之间的优先级，我们采用“相对优先级 的 形式设计了包含所有操作符的矩阵结构，任意两个操作符均可通过查找矩阵以 确定哪个操作符的优先级更高。 1 6 一 咖 哟 +脯 l n = ) 第二章数学公式结构分析系统