（计算机软件与理论专业论文）数学公式图像结构分析、理解与重现.pdf

ab s t r a c t ab s t r a c t i n t h e m o v e m e n t o f e l e c t r i z a t i o n , m o re a n d m o re d o c u m e n t s h a v e b e e n s c a n n e d a s d o c u m e n t i m a g e i n t h e c o m p u t e r . s o re s e a c h e r s n e e d t o r e c o 脚z e a n d u n d e r s t a n d d o c u m e n t im a g e a u t o m a t i c a l ly . a l o n g w i t h t h e d e v e l o p m e n t o f o c r t e c h n o lo g y , t h e r e c o g n it io n o f w o r d i n t h e i m a g e h a d b e e n a c h i e v e d . b u t a u t o m a t i c u n d e r s t a n d i n g o f m a t h e m a t i c a l e x p r e s s i o n i m a g e h a s n o t h a v e a e ff e c t u a l m e t h o d a s y e t . t h i s is o n e o f t h e m o s t i m p o r t a n t p ro b l e m in t h e fi e l d o f u n d e r s t a n d i n g o f s p e c ia l d o c u m e n t i m a g e . t h i s p a p e r p r o p o s e d g r a m m a r s t r u c t u r e a n a l y s i s m e t h o d a n d i m p l e m e n t e d t h e m e t h o d w it h c o d e . i n t h i s p a p e r , w e h a d r e s e a r c h e d t h e k e y t e c h n i c a n d m a i n p r o c e s s m e t h o d i n g r a m m a r s t r u c t u re a n a l y s is . t h e m a i n i d e a o f g r a n t tn a r s t r u c t u r e a n a l y s is is t h a t t h e g r a m m a r in f o r m a t io n g u i d e s t h e p r o c e s s o f t h e d e c o m p o s i t i o n a n d c o r r e c t i o n o f m a t h e m a t ic a l e x p r e s s io n i m a g e . f in a l l y , t h e r e s u lt o f a n a l y s i s i s f o m a t t e d a s o t h e r d e s c r i p t i v e l a n g a u g e ( s u c h a s ma t h ml , l a t e x ) f o r a p p l i c a t io n . t h e e v a l u a t i n g o f u n d e r s t a n d 吨 o f s p e c i a l d o c u m e n t i m a g e i s a n i m p o r ta n d a n d d i ff i c u l t p ro b l e m . t h i s p a p e r p r o p o s e d t h e e v a l u a t i n g p a r a m e te r a n d e v a l u a t i n g m e t h o d . a n d t h i s p a p e r a l s o p r o p o s e d t h e q u a l it a t i v e a n a l y s i s o f g r a m m a r s t r u c t u r e a n a l y s i s m e t h o d . t h e s y s te m w h i c h w e h a d i m p l e m e n t e d in t h i s p a p e r i s s e l f - c o n t a i n e d a n d s e l f - c o r r e c t e d . i t c a n b e u s e d f o r r e s e a r c h e r s e s p e c i a l l y f o r m a t h m a t i c r e s e a r c h e r s . t h e a n a l y s i s m e t h o d o f s t r u c t u r e , g r a m m a r s t r u c t u r e a n a l y s i s m e t h o d , ma t h m l , t h e e v a l u a t i n g o f s t r u c t u r e a n a l y s i s , g r a m m a r t r e e 内容目录 图 目 录 机器模拟人理解数学公式图像的 过程， .， . “ :.” . .，. . ” . . . “ . ” . ” 2 展现了 这三个层次之间的依赖关系” :.“ :.“ “ ” ” :.“ ” “ . ，. “ ” 2 数学公式句法结构模型二 ” . ” 二 “ “ . . .” “ . . 一 “ “ . “ ，. “ . ” 一” . “ “ “ . n一，卫 j.几月.月 图 l t 图 1 2 图 2 . 1 图 2 . 2 图 2 . 3 图 2 . 4 图 2 . 5 图 2 . 6 图 2 . 7 图 2 .8 图 2 . 9 句法结构模版及消歧举例 句法结构分析的主要流程 数学公式各类别举例“ . . “ . . . “ . ” “ . ” ” . “ . . . . . . . 一 隐式操作关系举例. “ :.” “ “ . ” ” ，. “ “ . ， . . ” .” “ . . ” 一， . “ . ” ” . “ 二 ，. . 1 2 语法属性判定举例 ，. “ “ . ，. . . . . . . . . . . . . . . - ” “ . . 一” . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 4 x ml格式举例二 “ . ” 二 “ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 6 操作符结合关系举例 “ . 。 :.，. . “ . .“ “ ， ， ” ” . . . . 二 ” . . . . . . . . . 1 9 操作符优先级别判定处理流程. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 9 图 2 . 1 0 图 2 . 1 1 图 2 . 1 2 图 2 . 1 3 图 2 . 1 4 图 2 . 1 5 图 2 . 1 6 图 2 . 1 7 图 3 . 1 图 3 . 2 图 3 . 3 图 3 . 4 图 3 . 5 图 3 . 6 图 3 . 7 图 3 . 8 图 3 . 9 特殊表 达式类别及句法结构模版举例，一 . . . 一， ， . . ” ，” . “ 二 2 0 隐式操作符示例. 一 ” . . .” “ . “ “ ” . . . . .，. ，. ” 二 ” . . . . . . . . . . . . . . .2 2 数学公式中水平中心线的示意图. ， . “ . ” ” . .， 二 ” . . . . . . . . . . . . . . . . . . . 2 3 隐式操作符拆分表达式示例二 “ :. ， 。 . -. ” :.，. . . . . . 一“ . . . . . . . . . . . . . . .2 3 数学公式不同目 类型的句法树形式举例. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 4 句法树的逻辑结构和实现结构. . ， . ” . . . 一 ” . . . . . . . . . . . . . . . . . . . . . . . .2 5 不同重现方式的ma t h ml格式. ” :.“ ” “ :.，. :.“ . “ . 一 “ . . . . . . . . . . 2 7 句法节点与ma t h m l的映射二 ，. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2 7 数学公式图像识别与理解系统框图 :.” “ 一“ . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2 9 句法结构分析主控流程图. .” :. ” . “ . “ .，. 二 ” 二 “ 二 “ 二 ” 二 “ 二 ” . . . . . . 3 0 句法结构分析流程举例 “ .” . ” 二 “ ” “ ” 二 ，. : ，. . . 二” . ” . ” . ，. . ” 3 1 队列结构的使用二 ” ” . . ” ，. ” “ . “ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 4 语法层次提取举例. “ “ :. ” 一 “ . “ . .，. 二 “ . . .” . .，. 二 ” :. “ . ” 一 “ . . . 3 5 子表达式分解搜索区域示意图. “ . “ . 。 . 。 一 ” “ ” . ” 二 . . 一“ . . . . 3 6 知识库的x m l 结构.“ :. ” . ，. :. “ . “ . ” . “ .” . ，. .” “ “ . ，. ， . ” ” 二 ” . . . . . . . . . . . . . . .4 0 句法树的用户界面展示. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4 z 句法树结构与ma t h ml语言格式的对应关系. . . . . . . . . . . . . . . . . . . . . . . . . . .4 3 讥 内容目录 图 3 . 1 0分析结果的输出流程 图4 . 1数学公式水平中心线举例 内容目录 表 目 录 表1 .1 不 同 分 析 层 次 的 重 现 方 式 .“ “ ” . ” 二 “ “ ” . . . ，. 一。 .6 表2 . 1 语 法 规 则 举 例 . ” ” ” . . - ” ” “ “ . 一“ . “ . ” ” ” . ” ” ” “ 一“ ” 二 表 2 .2 知 识 库 中 包 含 的 信 息 内 容 二 ” “ ” . . . “ “ “ 二 “ . “ . . “ 二 “ .1 4 表2 .3 知 识 编 码 举 例二 ” “ . . . ” ” 一 ” . “ “ 二 “ . . . . . . . . . 1 5 表 2 . 4类间操作符优先级别判定表. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 8 表 2 . 5呈现型m an e分类与数学公式分类对应表. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2 8 表 3 . 1典型公式类型句法结构模版. ” “ “ . . . . . .” ” . ” . . “ . .- . “ . . . 一 ， . . . . . . . . . . . . . . . . . . 3 3 表3 .2 知 识 库 结 构 对 照 表 ” .” . . . “ . . 一“ .3 9 表 5 . 1版面分析方法和文法分析方法的优缺点. “ . . - . . . 一 _ . . . . . . . . . . . . . . .4 8 vm 南开大学学位论文版权使用授权书 本人完全了 解南开大学关于收集、保存、使用学位论文的 规定， 同意如下各项内容:按照学校要求提交学位论文的印刷本和电 子版 本;学校有权保存学位论文的印刷本和电子版，并采用影印、 缩印、 扫描、 数字化或其它手段保存论文: 学校有权提供目 录检索以 及提供 本学位论文全文或者部分的阅览服务; 学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电 子版; 在不以赢利为目的的前 提下，学校可以 适当复制论文的部分或全部内容用于学术活动。 学 位 论 文 ” 者 签 “ :血o r 日年jr 月 万 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名:学 位论文作者签名: 解密时间:年月日 各密级的最长保密年限及书写格式规定如下: 内 部5 年( 最 长 5 年 ，一 可 少 于 5 钾 秘 密 * 1 0 年 最 长1 0 年 可 少 于1 0 年 ) 机密2 0 年 ( 最长2 0 年， 可少于2 0 年) 南开大学学位论文原创性声明 本人郑重声明: 所呈交的学位论文，是本人在导师指导下， 进行 研究工作所取得的成果。 除文中已经注明引用的内容外， 本学位论文 的研究成果不包含任何他人创作的、 已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体， 均已 在文中以明确方式标明。 本学位论文原创性声明的法律责任 由本人承担。 学 位 论 文 储 签 名 : 少 叫 d 刁年 ， 月i f 日 第一章 引论 第一章 引论 第一节 致学公式图像结构分析的重要性 文档图像 处 理( d i p : d o c u m e n t i m a g e p ro c e s s ) 的 研究是为了 解决 在将纸质 文档转换为电子文档过程中 所需要的大量人工操作问题o d i p 的研究范畴包括将 文档转化为计算机能处理的形式并从中获 取信息的各种技术与理论。 也即， d i p 就是从文档图像出发，把其中包含的信息转换成符号的形式修改、存储、获取、 重用、传输。 数学公式是数学语言的最主要表现形式，在各类文献中都包含大量数学公 式。这些文献被扫描，作为图像保存入计算机，识别其中的数学公式图像，就 是为了获取公式中包含的信息， 使信息的储存和使用变得容易，实现信息更好 的交流和共享。例如，科技工作者要求能够轻易重用数学公式:数字图书馆要 求能够以 便于编辑、 便于查找的方式储存数学公式;远程教育要求能够以 有效 的方式在网络上传输数学公式。 在文档图像处理中，数学公式图像不能当作普通的文档处理，增加了图像 处理的难度。首先普通文档只是一维结构，而数学公式图像是二维结构:第二， 普通文档只是符号的简单排列。而数学公式图像作为一个整体，反映了特定的 数学含义，只有准确的将符号以 及符号之间的关系进行识别与理解，才能获得 完整的数学公式。 因此， 数学公式图 像结构分析具有重要的现实意义。 第二节 数学公式图像结构分析方法概述 人在阅读数学公式时，首先通过视觉形成公式图像， 而后基于人理解数学 公式的先验规则及数学公式的组成规则， 经过大脑思维的分析与理解最终获得 公式所表达和计算的含义，即经过一个从版面结构到句法结构再到语义含义的 过程。 机器理解数学公式的过程模拟人的阅读过程，见图1 . 1 0 机器理解数学公式是从认识符号、分析公式结构及理解公式语义这三个层 面上进行。认识数学公式符号只需要借助传统的模式识别技术就能很好的实现: 第 t页 第一章 引论 包括一个母字符和若干个子数学元件。 f u k u d a 定义了数学元件之间的九种关系， 根据元件之间的位置关系，计算出每种关系的惩罚值，具有最小惩罚值的关系 就是正确的关系。 上述分析方法都是基于版面信息进行数学公式结构分析。单纯依靠符号之 间的位置信息判定符号之间的关系，必然不能够对具有复杂位置关系的数学公 式进行分析，而且还会容易将符号之间的关系分析错误。 1 . 2 .2基于文法的分析方法 文法分析的方法是通过定义文法实现数学公式分析。文法分析的语义识别 能力较强。 但是因为数学公式的形式是多种多样，并且数学符号具有二义性， 所以单纯依靠文法只能分析有限类型的公式。 b e l a id l rn 定 义了2 1 条 上 下文 无关文 法分析 数学公 式。 b e l a i d 首 先根据字符 的位置以 及算符的 优先级别， 找到一个算符其分析的起点;然后搜索包含该算 符的文法，利用文法分解表达式，然后再针对分解后的子表达式重复上述方法。 如此反复下去， 直到所有区域只包含唯一字符为止。 b e l a i d 定义的产生式文法简 单只能很好的分析一维的数学公式，却没有方法分析具有二维关系的数学公式。 后续的 研究 者 采用不同 的 方 法 1 la u 1 5 h i6 112 0 1 12 1 1 力图 扩展传 统的 产生式文法， 使其具 有表达二维数学公式的能力。 toumitl l s l 定 义了 六级的 算符 优先级， 并使 用树结 构分 析公 式。 分析 树的 构造 过程如下:首先构造一个只有一个叶节点的树，该节点 表示整个数学表达式: 然后化简叶节点，直至不再包含复杂表达式。该方法定义的六级算符优先级别 不能覆盖所有优先级别情况，因此处理的数学公式类型具有局限性. 另一种基于文法的方法是基于图文法进行数学公式分析。 g r b a v e c 1 1 7 1 构造的 系统e x p r e s s o采用改写图的方法分析数学表达式。该系统定义了大约6 0条 图 改 写规则 并 规定了 每 条规则的 使 用条 件， 所有的 规则 都 形如g l :二 1 1 r ， 表示 使 用子图s r 代替 原图中 的9 1 .由 于图 改写 规则 抽象， 简单， 所以 只适用于 简单数 学公 式的结构分析。目 前只能处理包含上标和下标的简单表达式，但它对公式 的排版格式没有严格要求，而且可以检查不合句法的公式。 以上基于文法的分析方法，虽然包含了符号之间的文法关系，但都存在着 文法定义抽象，内容不能授盖各种数学公式类型情况。因此在结构分析中具有 第 a页 第一章 引论 局限性。 1 .2 .3基于句法的分析方法 通过上文对数学公式版面结构分析方法的总结，可以看出，对数学公式版 面结构的处理还只是单纯的依靠传统模式识别技术，对各个符号的大小、字体 和版面位置信息进行分析，其分析结果也只是简单地展示了数学公式的版面结 构， 并不能抽取数学公式的完整信息结构。 而句法结构分析方法就是基于数学公式的 句法结构来实现数学公式图像的 理解与重现。 由图1 .2 ， 句法结构是介乎于图像信息( 版面结构) 和逻辑含义 语 义含义) 之间的描述机制，既体现出公式的计算含义，又直接决定了公式的版 面形式。 数学公式句法结构分析方法在充分利用版面信息的同时，以句法关系为主 导实现对数学公式的拆解。 通过句法关系的合法性检查实现对识别结果的纠错。 本文对该方法进行了更加深入和细致的研究，并将其方法在现实中得到应 用。 第三节 救学公式图像结构的重现 数学公式图像重现是数学公式结构分析的 初级目 的。科技文献中的大量数 学公式图像只有经过结构分析进行重现之后才能得到广泛的应用。这种应用包 括对数学公式的再编辑和重用两种。通过重现数学公式，结构分析才能体现出 其价值。 根据数学公式结构分析方法处理目标和处理层次的不同，重现在不同的阶 段具有不同的含义和表现形式，主要分为三种，见表 1 . 1 0 第 5页 第一章 引论 表 ， . ，不同分析层次的重现方式 分析层次 级别 分析层次分析目标 子七 重现方式 高 甚 低 语义理解实现机器自 动计算c f c + + 或ma t l a b 代码 句法重现实现数学公式的再编辑ma t h ml文档 版面重组实现数学公式图像重组l a t e x . m a t h m l 文档 1 ，重现版面结构 根据版面识别结果中 符号之间的空间位置关系重现版面结构， 使用l a t e x 等排版语言输出.主要应用在版面结构分析方法中。 2 .重现句法结构 在重现版面结构的同时，重现符号之间的句法关系，重点在于重现公式的 句法结构。使用 ma t h ml语言输出，不仅包含了丰富的句法信息，而且利于在 各种应用环境中使用。 3 .重现语义含义 重 现数 学公 式的语 义 含义， 即 公 式的计算内 容， 并使 用l i s p 或m a t l a b 等数 学计算语言输出。实现数学公式的自 动计算就需要分析出公式的语义。 第四节 本文主要内容及结构 本文在前人研究的基础上，对数学公式句法结构分析的概念及其描述模型 进行了深入研究，并在实际系统中实现了公式的句法结构分析方法，并对其性 能进行了定性评价。 下面介绍本文各章的主要内 容: 第一章:概述了数学公式图像结构分析的三个层次以 及目前研究领域中提 到的 结构分析方法。并且根据不同的结构层次提出了相应的数学公式图像重现 方式。 第二章:概述了数学公式图像句法结构分析方法，详细介绍了句法结构分 析方法处理流程的设计，并且着重介绍数学公式句法结构分析方法中几个关键 处理思想的设计。 第 6页 第一章 引论 第三章:着重介绍了数学公式图像句法结构分析方法的实现。详细介绍了 第二章提出的重点处理步骤的实现方法以及经验总结。 第四章:着重介绍了数学公式句法结构分析的评测设计，重点介绍了句法 结构分析系统评测参数的选择和评测方法的设计，并且对句法结构分析方法进 行了客观的定性评价。 第五章:对结构分析从理论、方法以 及重现方法三个方面进行了总结，对 该领域尚未解决的问题进行了分析，并对未来的研究方向进行了展望。 第 7页 第二章 数学公式图像结构分析与重现方法模型 第二章 数学公式图像结构分析与重现方法模型 第一节 致学公式的句法结构模型 本文所研究的结构分析方法是以句法信息为驱动，以版面信息为辅的分析 方法。与该方法相对应的定义了数学公式的句法结构模型作为其分析载体。数 学公式的句法结构模型定义见图2 . 1 . 图像中符号的位 置，字号，字体等 圈 2 . 1数学公式句法结构模型 数学公式句法结构模型采用四 元组g= 仪, s i p , 劝形式描述，即为:数学 公式句法结构=( 版面关系，字符集，句法规则，语法规则) ;如图2 . 1 . 其中版面关系:数学公式的版面结构，包括构成公式的所有符号的内容、 字体、字号，以及符号之间的空间位置关系。数学公式图像处理系统中，经过 图像预处理，公式定位， 字符识别之后， 进行数学公式结构分析。结构分析的 输入为字符识别结果及各符号在公式中的空间位置，要获取数学公式的句法结 构就必须利用数学公式的版面结构。 字符集:组成一个数学公式的所有符号，包括所有操作符与操作数。 语法规则:主要定义了符号所具有的语法信息，包括符号自身的语法属性 和符号 之间的约束关系和组合关系.见表 2 . 1 . 第 9页 第二章 数学公式图像结构分析与重现方法模型 衰 2 . ，语法规则举例 f 操作属性操作符 语法属性大操作符且为多目操作符 判定规则符号的右上方和右下方有表达式 子表达式组合个数 1 特殊组合个数 0 是否可以充当角标是 具有角标的位置右上方、右下方 句法规则:句法规则是为以 后扩展语义所服务的。它定义了所有类型操作 符之间的优先级别、操作符的目 类型 ( 即操作符所拥有的子表达式的个数)和 各种类型子表达式的组合结构。根据处于同一层次操作符之间优先级别的比较 可以确定该数学公式在这个层次上的计算顺序。并且针对不同类型的子表达式 定义了动态的句法结构模版，这种结构模版规定了不同表达式类型下子表达式 的特征，具有消除句法歧义和识别噪音的作用。见图2 .2 . r . 一- 一 l r . - 一 . 一 1 : 右上方1: 右下方; . 1 角标 : 角标 : .1 二 . . . . . . . . . . . . . . . . . . 口 心 . . . 口 . 口 . . . . . 月 . . . 积 分 袭达式 积分 符号 a 句法结构摸版示例 b . 句法结构镇版消歧示例 图 2 .2句法结构模版及消歧举例 第二节 句法驱动结构分析流程 本文所提到的句法结构分析方法是一种以句法信息驱动分析流程的方法， 而版面结构则作为辅助信息划分分析范围.句法结构分析方法的主要流程是首 第 ，页 第二章 数学公式图像结构分析与重现方法模型 先根据符号的版面位置及公式的版面结构，得到操作符的层次。然后在在相同 子表达式内同一层次的操作符的优先级，然后根据最高优先级别的操作符的句 法信息结合版面信息分解子表达式，最后生成句法树。流程图见图 2 . 3 . 圈 2 . 3句法结构分析的主要流程 由上图可以发现在句法结构分析方法中有四个重要的问题需要解决，即为: 1 .版面结构层次的 划分: 在版面结构层次的划分中，提出了水平中心线的概念。 通过对大量数学公 式样张的观察与分析，发现虽然数学公式中的符号由不同的语法信息组合在一 起，但是却在版面结构上呈现出层次性，处于同一层次的操作符具有相同的操 作级别。 使用符号的水平中心线作为版面层次的表现形式，既便于计算， 又可 第 0页 第二章 数学公式图像结构分析与重现方法模型 以直接反映出符号所在的层次。 根据数学公式中水平中心线的不同分布情况，可以将常见的数学公式从版 面结构上分为以下6 类。如图 2 .4 . 基元表 达式( u n i t e x p r e s s i o n ) : 不可分解的 操作数， 普通表达式的 基本 元素。 普通表 达式( c o m m o n e x p r e s s i o n ) : 所有符号 均处 在同 一条水平中 心线上的 简单表达式。 角标表 达式( s c r ip t e x p r e s s i o n ) - 包 含核 心操作符 和角 标子 表达式的复 杂表 达式。 角标子表达式可以 位于核心操作符的左上方、 左下方、 右上方或者右 下方。具有至少2 条水平中 心线。 组表达 式( g r o u p e x p r e s s io n ) : 包含核心 操作符合其 他的具有含义的子表达 式的复杂表达式。具有2 条以上的水平中心线。 矩阵 表 达式( m a t r ix e x p re s s i o n ) : 子表达 式按照行 列排列的复 杂表 达式。 核 心操作符是大定界符。 堆表达 式 ( s t a c k e x p r e s s i o n ) : 描述性符号附 属于 操作符 和操作数的复杂表 达式。 l)2) z =2 a + 3 y 尹 . 葺f辛烤盆权，) 砚 害认式 角标容然大 f f (. )d . 习. “ +习r +z “ 堆表达式 圈 2 .4效学公式各类别举例 2 句法信息的提取与验证: 句法信息必须是完备的:句法信息作为整个分析流程的驱动因素，在分析 过程起着至关重要的作用。句法信息是否完备，直接决定了 句法结构分析的完 备性。因此首先要保证句法信息的完备. 句法信息必须是可用的:句法信息的存储方式应该是可应用的。要能够做 到对符号的句法含义 进行消 歧， 并且提供的信息足以 支撑整个分析流 程。 如何保证句法信息的完备及可用是需要解决的问题。 第 t i页 第二章 数学公式图像结构分析与重现方法模型 3 .句法结构分析处理过程的控制: 在句法结构分析过程中，同一层次的操作符通过优先级别判定获得最高优 先级别的操作符，然后根据操作符的语法信息，按照不同的表达式类型进行子 表达式拆解。这些操作是句法结构分析中的重要环节，充分体现了句法信息驱 动分析流程的意义。 由此可以 发现其中 优先级别判定和特殊表 达式的处理是相当 重要的两个处 理过程。优先级别判定的正确有效以及特殊表达式模版定义的完备性决定了数 学公式结构分析的正确性。 4 .句法结构分析处理过程的细化: 前面三个问题从宏观的角度分析了句法结构分析流程中重要的处理步骤。 但在对样张的实际观察中会发现，并不是所有的操作关系都是以显示操作符的 形式出现的，有些是以隐式操作符的形式出现，例如角标操作符，隐式乘法操 作符见图 2 .5 。 这种隐式操作符由 于在图像中没有具体的符号作为标示， 因此无 法简单的从符号识别结果判定出是否存在隐式操作符。 a b wi a 陇式乘法 b .角标关系 圈2 . 5隐式操作关系 举例 为了能使句法结构分析方法处理各种的公式图像，就需要对句法结构分析 流程从微观的角度来进行细化。隐式操作符需要通过已识别符号的空间位置关 系来判定。 这就需要在句法结构分析流程中充分考虑到隐式操作符的存在， 扩 充句法结构分析流程中的判定步骤，以便数学公式结构关系做出准确地判断。 通过对以上四个分析重点的简要分析，确定了对句法结构分析方法继续深 入研究的主要问题，明确了对句法结构分析方法的研究方向。后面的内容将着 重针对句法关系的提取与验证， 句法结构分析处理过程的控制以 及句法结构分 析处理过程的细化三个方面进行了更加深入的分析研究。 2 .2 . 1句法关系的提取和验证 从前面的分析中，发现句法信息在数学公式句法结构分析过程中占 据着至 第 1 2页 第二章 数学公式图像结构分析与重现方法模型 关重要的地位。与人类相似，如果让机器像人类一样具有先验知识 ( 包括科学 定义的规则以及积累的经验)的思考，就需要让机器也具有一个储存先验知识 的大脑，机器才能不断的从中提取知识作出判断。因此要为机器建立一个完备 而有效的知识库。 知识库是保证数学公式句法结构分析的基础，为了保证在系统中能方便的 对其进行访问，要求其结构定义易于扩充、访问接口易实现。只有这样，才能 将其真正融入复杂的数学公式结构分析系统中， 为结构分析提供可靠的核心支 持与分析依据。 该节的内容即结合句法结构分析的处理过程，对知识库从存储内容、存储 形式以及提取方式进行了分析设计。 2 .2 . 1 . 1知识库的内容 数学公式的先验知识及规则是句法结构分析的直接依据，也是知识库的主 要构成内容。通过前期大量的统计工作，对数学公式符号的操作属性、语法属 性、组合关系、操作符优先级、目 类型等进行了统计分类与描述。 虽然知识库是为句法结构分析处理过程而建立的，但是它不能仅包括符号 的句法信息，还要包括符号的语法信息。通过对知识库使用情况的分析总结， 对前人建立的语法规则库重新进行了构建。根据分析流程中版面分析、句法分 析和语义分析的需要，将知识库中的信息划分为三大部分，即: 1 .符号信息 知识库必须包含所有可识别的符号以及符号的基本信息。其中符号的基本 信息主要指符号的内容和内码。符号的内容是指符号的图像和符号的名称。而 符号的内码是对符号的一种编号，包含了符号的类别及内容信息，在知识库中 作为识别符号的唯一标记，也是系统与知识库交互的唯一途径。 2 .语法信息 语法信息指符号自身所包含的信息。 包括符号的操作属性( 操作符/ 操作数) 、 语法属性 ( 符号的类别) 、 符号具有的组合关系和符号属性的判定规则等信息。 3 .句法信息 句法信息则是介于语法信息和语义信息之间的一个桥梁。句法信息表现出 了 数学公式的运算顺序和运算含义，其专指子表达式之间的组合关系和操作符 的运算顺序，包括子表达式的个数、子表达式之间的组合关系和判定规则以及 第 1 3页 第二章 数学公式图像结构分析与重现方法模型 操作符的优先级别等信息。 衰 2 .2知识库中包含的信息内容 裂 知毖 黔 识; ; 库万 i t i _ 轶 黑 符号信息 符号图像 符号内容 语法信息 符号的操作属性 符号的语法属性 ( 即符号的类别) 符号语法属性的判定规则 符号具有的组合关系 句法信息 符号的目类型 子表达式的组合关系和判定规则 操作符的优先级别 值得注意的是， 在知识库中，判定规则分别出现在了 句法信息和语法信息 中，这在以前的语法规则库概念中是没有的。 判定规则信息充分体现了 句法关系的验证功能。同一个符号可能存在多种 语法属性， 或者同一个子表达式可能存在多种类别，因此判定规则就可以根据 版面信息判断符号的确定语法属性或者子表达式的确定类别。 例如，符号 +， 的语法属性可以是二目 类型充当加号或者单目 类型充当正号，如何判断所要分 析的数学公式图像中的 + 的语法属性，就要由判定规则结合实际的版面信息 来判断，如图 2 .6 . 1 该 操 作 符 为 甲 目 操 作 符 1 圈 2 . 6语法属性判定举例 2 . 2 . 1 .2 知识库的存储形式 在建立知识库时，需要根据知识库的规模、内容的表现形式以及存储形式 第 1 4页 第二章 数学公式图像结构分析与重现方法模型 的通用性来设计知识库的存储形式。 1 .知识库的规模 知识库包括正体英文字母，数字，希腊字母，数学运算符号，三角函数， 箭头符号等常见公式中的符号共 3 3 0个符号。虽然符号数量不多，但是每个符 号均包含了丰富的句法信息和语法信息，需要设计适当的表示形式来展现。 2 .知识库内容的 表示形式 知识库的建立是为计算机进行的句法结构分析所用的，因此知识库的内容 要方便计算机的读取。因此知识库中的信息使用计算机容易理解的编码形式来 表示。 各项的编码形式举例见表 2 .3 ， 具体的知识库内容的编码内容见附录a和 附录b a 裹 2 . 3知识编码举例 戳 默篡 默一知 说 氯赢赢篡 操作属性 操作符 0 操作数 1 语法类型 帽子符号 0 x 0 1 定界符 0 x 0 2 大操作符 0 x 0 4 关系操作符 0 x 0 8 运算操作符 0 x 1 0 标点符号 0 x 2 0 功能函数 0 x 4 0 目 类型 单目 0 x 0 1 双目 0 x 0 2 多目 0 x 0 4 由附录a . b中可以发现与判定规则相关的信息，采用了正则表达式表示。 正则表达式是一种用来操作文本和数据的强大工具，可以将那些原本复杂且繁 琐的文本处理过程变成可自 动处理的工作。而且正则表达式具有易用、灵活、 功能强大的优点，因此使用正则表达式不仅可以表达复杂的句法信息和语法信 息，还便于计算机系统的读取使用。 3 .知识库的存储形式 第 巧 页 第二章 数学公式图像结构分析与重现方法模型 在定义了知识库内容的表示形式之后，就需要从知识库的可扩充性和通用 性设 计 它的 存 储 形 式 ， 在 这 里 选 择x m l ( e x t e n s i b le m a r k u p l a n g u a g e ) 文 档 格 式作为存储形式。 x ml 文档的 特点: 1 )遵循严格的语法要求 x m l要求标记配 对、 嵌套， 而且还要求严格遵守 d t d ( d o c u m n e t t y p e d e f in i t i o n )的规定。 2 )便于不同系统之间信息的 传输 各种不同的系统之间可以采用x m l作为交流媒介。 x ml不但简单易读， 而且可以标注各种文字、图像甚至二进制文件，只要有x ml处理工具， 就可以 轻松地读取并利用这些数据，使得x ml成为一种非常理想的网际语言。 3 )具有较好的保值性 x m l可以长期作为一个通用的标准，而且很容易向其它格式的文件转化， 使得x m l 文档具有较好的保值性， 即使过很多年， 这些文档都是可以再利用的。 从x ml的优点可以发现，知识库所要求的可扩充性和通用性与x ml的特 点相符合。 而且x ml可以使知识库具有较好的保值性，为以后知识库的进一步 应用打下了基础。 根据知识库的内容和组织形式，设计了知识库的x m l 格式。 图 2 . 7 展示了x m l 的格式和实例。 i 0 x 0 0 2 c s t 灿 r 护 加 习. ， 1 嘴 护 . 1 睁二 ff 加 切卜 3 1 n几 丫 t日 , 3 y n g r p n o o / s 目 g 从 p 曰 o p i tm0 / c 甲几 节m o x 2 0 0 2 / s t ni ) i m i ) o x 4 0 , 1 ) 4 1 0 . 0 4 , 1 ) ) / j o d g c 皿 肠卜 1 0 昌 u p ! 名 护城 臼 刀 月 b2 / 5 口 ，! 留 p 目的口， wb i s c r i p t o 二目 运算符 少 功 能 函 数二 口. 习 1口. ， 刁.卜 刁.二 血rov e 户 口卜口 阅m卜 口血m e 曰 闷. 价 b ， . 岭 间 匆 卜x 4比减角， . r ， 如wl i mi t o z )利用 版面 信息抽取当 前 层次的 核 心操 作符: 3 )查询知识库，判断出具有最高 优先级别的核心操作符: 4 )查询知 识 库，以 具有最高优先级别的 操作符的 句法信息生成句法树节 点，并根据句法结构模版扩展句法树结构; 5 )按照该 操作符的 句法结 构 模版， 将剩余 核心操作符填充到相应的 句法 树 节点中; 6 )遍历句法结构树，对待分析节点重复步骤1 . 这样可以发现每通过一遍处理，当前层次的核心操作符已经被放在了正确 的位置，减少了 后面步骤中对其重复的操作.图 3 . 3 举例说明了上述步骤. 圈 3 . 3句法结构分析流程举例 第 3 1页 第三章 数学公式图像结构分析的实 现 3 . 1 . 2数据结构描述 针对上述句法结构分析流程，必须有完备的数据结构来存储处理过程中的 数据，以保证分析过程的正常运行。本文在实现中按照数据结构的用途将其分 为三个层次。下面将一一说明。 3 . 1 .2 . 1符号单元 符号单元概念在本文中首次提出，它是句法结构分析中最小单位，却记录 着最重要的信息。符号单元存储了每个单元的识别结果和语法属性。区别于以 前的符号概念，符号单元既可以存储独立的符号也可以存储合并后的符号，并 将其作为结构分析的基本单位。 例如函数名s i n ， 在经过识别之后分别以s , i , n 三个符号存储，经过合并函数名操作，三个符号被合并为一个符号单元作为分 析数据。 3 . 1 .2 .2句法节点 根据第二章对数据结构的设计，下面