（计算机软件与理论专业论文）数学公式图像理解的性能评测与分析.pdf

ab s tr a c t ab s t r a c t a s a s c i e n t i fi c l a n g u a g e o f a ll m a n k i n 氏m a t h e m a t i c a l e x p r e s s i o n s h a v e v e ry w i d e a n d i m p o r ta n t a p p l i c a t i o n s i n t h e g l o b a l a c a d e m i c r e s e a r c h . t h e e v a l u a t i o n o f m a t h e m a t i c a l e x p r e s s i o n s n o t o n l y p r o v i d e s d e ta i l e d t e s t i n g r e s u l t s f o r a l g o r i t h m d e v e l o p e r s t o g u i d e t h e m t o i m p ro v e t h e a l g o r i t h m , b u t a l s o p r o v i d e s q u a l i t y a s s u r a n c e f o r e n d u s e r s o f p r o d u c t - l e v e l m a t h e m a t i c a l e x p r e s s i o n p r o c e s s i n g s y s te m s . a s a t y p i c a l t w o - d i m e n s i o n a l s t r u c t u r e , t h e r e a r e m a n y d i ff i c u l ti e s a n d p r o b l e m s i n t h e e v a l u a ti o n o f m a t h e m a ti c a l e x p r e s s i o n i m a g e u n d e r s t a n d i n g . t h e r e i s n o i n t e g r a t e d e v a l u a t i o n m e t h o d o l o g y , a n d t h e s i t u a t i o n h a s h i n d e r e d t h e f u r t h e r re s e a r c h d e v e l o p m e n t a n d i t s f u r t h e r p r o d u c t w o r k . t h i s p a p e r d e s i g n s t h e s y n t a c t i c s t r u c t u r e m o d e l o f e x p re s s i o n s , a n d f o c u s e s o n t h e e v a l u a t i o n m e t h o d f o r l a y o u t s t r u c t u r e a n a l y s i s u n d e r t h e 加 d a n c e o f t h e s y n t a c t i c s t r u c t u re a n a l y s i s . t h e m e th o d g i v e s q u a n t i t a t i v e a s s e s s m e n t f o r t h e v a r i o u s e r r o r s a p p e a r i n g i n t h e l a y o u t s tr u c t u re a n a l y s i s fr o m b o t h o f t h e m a c r o s c o p i c a l a n d m i c r o c o s m i c a s p e c ts , a n d i d e n ti fi e s t h e p r e c is e l o c a t i o n a n d p o s s i b l e c a u s e s o f e rr o r s . t h i s p a p e r p r o p o s e s t h e p e r f o r m a n c e e v a l u a t i o n m o d e l o f t h e e x p r e s s i o n i m a g e u n d e r s t a n d i n g . t h i s p a p e r g i v e s a d e t a i l e d i n s t r u c t i o n f o r t h e p r e p a r a t i o n a n d d e s c r i p t io n o f t e s t i n g d a t a , a n d d e s i g n s g o o d t e s t i n g o b j e c t i v e s a n d a c c u r a t e t e s t i n g p a r a m e t e r s . f in a l l y t h e i n t e g r a t e d p e r f o r m a n c e e v a l u a t i o n e n v i r o n m e n t i s b u i l t u p . t o v a l i d a t e t h e c o rr e c t n e s s a n d e ff e c t i v e n e s s o f t h e m e t h o d a n d m o d e l , t h e s t a n d a r d t e s t i n g d a t a b a s e i s b u i l t u p . b a s e d o n t h e d a t a b a s e , t h i s p a p e r s u m m a r i z e s a n d d e s c r i b e s e r r o r s f o u n d i n t h e e v a l u a ti o n a n d g i v e s s p e c i fi c q u a n t i t a t i v e r e s u l t s . i n a w o r d , t h i s p a p e r e s t a b l i s h e s t h e m o s t c o m p l e t e a n d e ff e c t i v e e v a l u a ti o n m e t h o d s o f a r f o r e x p re s s i o n i m a g e u n d e r s ta n d i n g , w h i c h i s p r o v e d 勿t h e p r a c ti c e . k e y w o r d 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 u n d e r s t a n d i n g , p e r f o r m a n c e e v a l u a ti o n , l a y o u t s t r u c t u r e , s y n t a c t i c s t r uc t u r e , t r e e p a t t e rn ma t c h i n g 目 录 图 目 录 图 1 . 1数学公式图像处理的核心流程 图 2 . 1数学公式图像理解三个层次之间的 依赖关系.“ . 一 . . . . 9 图 2 .2数学公式句法结构描述模型 .“ ” . _ 二 ” . ; . . . 1 0 图 2 . 3数学公式句法结构分析结果的描述示例 _ 二 _ . . . . . . . . . . . . . . . . . . . 1 3 图 2 . 4数学公式版面复杂度计算示例二 ” . ” . “ . “ “ _ 一一 . . . . . . . . . . . . . . 1 5 图 2 .5版面信息中水平中 心线的 级别划分示例” . ; . . . . . . . . 1 6 图 2 .6多种公 式类型的 子表达式示例一” ” . ” “ . . “ 一一一. . .; . . 1 7 图 2 . 7版面结构评测算法的整体流程图. . ， 一 一 一 _ . . . . . . . 一. . . 2 2 图 2 .8树型模式匹配的 详细流 程图. “ “ . ” .” 二 “ . 一. . . . . . . 2 4 图 2 .9隐 式操作符节点比对流 程图二 ” .” .“ . 二 ” . . .; .; .; . . . 2 6 图 2 .1 0数学公式图像理解的 性能评测模型.“ . ” 一 “ . . . . . . . 2 9 图 3 . 1性能评测方法的应用实例1 “ 二 ” . ” . ” . ” ” ” . . 一 。. . . 3 9 图 3 . 2性能评测方法的应用实例2 . . . . . . . . . .; . . . .; ; . . .4 1 图 3 . 3性能评测环境模型 . ” ” _ . . . . “ ” 二 ” . . . . 一_. . . . . 4 3 图 3 . 4性能评测环境模型的架构体系. . . . . . . . . ; . . . . . . . . . . . . . . . . . ; . . . . . . . . . . . . . . . . . 4 4 目录 图 3 . 5评测环境数据管理组织结构图. . 一:._一. 一 ” . . . . . . . . . . . . . . . . 4 6 图 3 . 6具体实现的目 录结构 ” . . 一. . . . . .- .一 . _一 .; . 4 7 图 4 . 1标准数据库分类统计表图例 一 - - - - - - - 一 _ _ _ _ _ _ _ _ _ . _ . 一. . . 一. . 4 9 图 4 . 2不同版面复杂度的公式举例 . “ . 二 “ . 一. . . . . ; . . ; . . . . . . . . . 5 1 图 4 . 3实验结果数据统计表图例. .; . .; . .; .; . ; . ; . .; . . . . . 5 2 图 4 . 4节点内容与公式类型错误的数学公式举例 . ” 二 ” 二 . . ; . . 5 5 图 4 . 5其他类型错误的数学公式举例” . ” . “ . . . - - - - 一- 一 ” . ; ; . ; . . . . 5 7 目录 表 目 录 表 2 . 1按照语法类型分类的 操作符举例._一:. “ ” “ .” . “ “ . 二 1 1 表 2 . 2版面结 构分析的 级别与权重计算. ” . “ . _ . . . . . . 一 “ . . 1 6 表 3 . 1数学公 式图像理解性能评测环 境的 评测规范. 一 ; . . . . 4 5 表 4 . 1侧试样本集按照公式类型分类统计结果. . - - . . 一 ” 。 . “ :i.“ 50 表 4 .2测试样 本集按照版面复杂度分类统计结果. ” _ 一 :. ” 一5 0 表 4 .3按照版面复杂度分类的公式级别评测结果统计. . . .一 . .5 3 表 4 .4按照编 辑操作分类的评测结果统计.” “ .” ” 二 ” . ” . . ” . _ . .夕 表 4 . 5节点级别的评测结果统计 . . “ . . . . 一二 “ . . . . . . . . . . . . . . . . . . ; . . . . . 5 3 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容:按照学校要求提交学位论文的印刷本和电子版 本;学校有权保存学位论文的印刷本和电 子版，并采用影印、缩印、 扫描、 数字化或其它手段保存论文; 学校有权提供目 录检索以及提供 本学位论文全文或者部分的阅览服务; 学校有权按有关规定向国 家有 关部门或者机构送交论文的复印件和电子版; 在不以 赢利为目 的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 ，学位论文作者签名: 1 10 07 年犷月 丫日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 : 指导教师签名:学位论文作者签名 解密时间:年月日 各密级的最长保密年限及书写格式规定如下 南开大学学位论文原创性声明 本人郑重声明: 所呈交的学位论文， 是本人在导师指导下， 进行 研究工作所取得的成果。 除文中已经注明引用的内容外， 本学位论文 的研究成果不包含任何他人创作的、 己公开发表或者没有公开发表的 作品的内容。 对本论文所涉及的研究工作做出贡献的其他个人和集 体， 均己 在文中以明确方式标明。 本学位论文原创性声明的法律责任 由一本人承担。 学位论文作者签名: 年月日 第一章 绪论 第一章 绪论 第一节 数学公式图像处理及其性能评测概述 数学公式作为自然科学领域应用极其广泛的一种表达式，是通用的国际语 言，不受到种族、国家、文化和任何方言的限制。不同国籍的科学人员都可以 通过这种共通的符号沟通。将数学公式从文档图像中识别出来并进行正确的理 解也是当今时代科技文档电子化中的一项重要课题。 数学 公式图 像处理系统是一种 特殊的 文档图 像分析系统。 图1 . 1 说明了 一 般 数学公式图像处理系统的核心流程及其与性能评测的关系。 、几 一一一 一履一 一翼一一 .uwssere fra comem i ,was;e ertsau ! en 一-一 j 图 ， . ，数学公式图 像处理的核心流程 第 1页 第一章 绪论 在大多数情况下，数学表达式具有二维的特殊结构，并且包含了除英文字 母和数字之外的很多特殊字符，字体、字号变化频繁;对其进行识别、分析与 理解时会存在诸多问题与困难.从数学公式图像的处理流程可以看出，数学公 式图像处理本身已 经是一个具有相当难度的前沿课题了，许多方法还在探索与 试验阶段:正因为该领域的研究还处于这样一个阶段，因此对各种研究手段进 行评测以检验方法的有效性、正确性和准确性就显得尤为迫切和重要。 所谓评测，即测试评估的简称。这里所说的测试可以视为定性地判断 对 还是 错 ，而评估是要指出哪里 对哪里 错 ，甚至定量地指出 对或 错的程度。所谓性能是一种指标，表明软件系统对于其正确性，准确性， 完整 性， 及时 性等要 求的 符合 程度。 无论是公式的 识别， 还是公式 的分析理解都需要进行 测试和性能 评估。只 有这样才能为数学公式图 像处理结果的 好坏提供一个统一 完善和公认的 标准， 为相关研究人员提供完整详细的评测结果，以指导其对相关课题的进一步研究 与改善，为应用系统的用 户提供详 细的 质量保证和信心说明。 为了 对相关 研究 与算法的优劣进行比较，推动相关研究的不断发展，就必须在大规模集合上进 行测试，此时就需要引进相应的评测方法与技术。 同时数学公式图像处理要想广泛应用，就必须是产品级的，而不是简单的 存在于理论研究中的，对应的评测难度也会上升。这不同于一般的面向普通项 目 的测试，因 为普通项目 有 特定 的范围和评测案例集， 有一定的 约束条件和规 范;这也不同于简单的中间件测试，中间件一般没有用户界面，同样有特定范 围。 产品级的 数学公式评测是 针对全 人类数学公式的， 要求通 用性必须强大， 同时能够应对处理目标的急剧膨胀，应用范围广大等问题。 第二节 数学公式图像理解性能评测的难点 由图1 . 1 可知， 数学公式图 像 理解位于数学公式图 像处理的中间 步骤， 前面 的定位切分与识别等功能模块可能对其产生影响，使得其自身的输入数据就是 不正确的;而且作为一种二维结构，从数学定义和计算机处理的角度讲也是困 难的。所以针对大千世界中纷繁复杂的数学公式定义统一的结构描述模型是必 要的，只要这样，才能进一步针对不同的数学公式进行图像理解的研究和评测 工作。 第z 页 第一章 绪论 而在实际的科研工作中，缺乏对数学公式图像理解的处理结果的性能评测 工具，这也严重约 束与阻碍了 针对该模块的研究 进展; 科研人员针对某个模 块 进行一个很小的改 动，往往就会影响系统方方面面的 性能，即使花费很多时间 对系统性能进行评测仍然可能不够准确。 数学公式图像处理属于特殊的人工智能领域，而数学公式图像理解又是其 中的重要组成部分;由于种种原因，对其进行评测面临着众多难点。 1 ) 数学公式的自身特性造成性能评测比对困难。 . 公式符 号类型多 样、结构多 变， 造成标准 结果的选 择与 制定困 难 经统计分 类，数学公式中的 符号种 类多 达3 6 9 个，其中操作 数有包 括英文 大小写 字母、数字、希 腊字母等 共 1 3 6 个; 而2 3 3 个操作 符按照 其语法类型划分成七大类。 这些符号中如 。 与 a ,。与 w , y 与 r 等，即使是人肉眼观察，有 时候也 是难以区 分清楚的，这就 造成了 评测 标准结果的选择与制作 很困 难。 . 公式语法规则庞杂、含义多变， 造成比对对象和比对顺序的选择困难 数学公式的语法规则极为庞杂，语法结构具有不确定性和多义性， 造成待比对对象和比对的先后顺序的选择是困难的。 常见的如隐式操作符的问题，表达式 “ a b + c ”可以理解成变量 a 6 和变量c 相加，也可以理解成变量a 乘以变量 b 之后再加上变量 c :这 里的 就要 选择比对 对象是a b 和c 还是a , b 和c 。 又例如表达式“ a , b ) , 根据正确的语法规则可以理解为一个半开半闭的区间，同时也可以理解 为 表达式 “ ( a , b ) ” 的误识，前者 在比 对顺 序上是顺序判断的， 而后者则 是先判断定 界操作符 “ 0 ”的正 确性， 再判断 其中的内 容。 2 )数学公式图像理解的性能评测数据描述机制难以建立 . 如何表示数学公式图像理解的处理结果 用户最终 得到的数 学公式处 理结 果可以 是线性的字符串，也可以 是 固定的l a t e x 或m a t h m l 格式， 但这些都不 能直接应用于图像理解的 性 能评测， 不能 作为评测的 输入数 据:由 此带 来对应的基准数据的表示也 存在困 难。因 此需要定义 适用于数 学公式图 像理解评测用的数据描述， 同时要 有一定 的格式转换准则，并 保证输入 数据与基准数据之间 表示的 一致性。 第 3页 第一章 绪论 . 如何 选择有 代表性且规模 适度的 样本 集 要完整全面的测试数学公式图像理解的性能，主要通过有大量图像 样张的测试来完 成， 这些 作为 评测数据的图 像样张的管理 及其与具体测 试案例的结合也是一项繁重的工作。测试案例要具有代表性，不能只挑 选那些对算法设 计者而言 测试效 果好的 测试案例， 要保证覆盖 面;同 时 规模也要控制适度， 不能一味的求大求全， 这样会影响最终的评测效率。 . 如何制定评测指 标与如何表示和分 析最终的 评测结果 由于评测内容的繁杂，使得评测指标体系的建立也变得困难，进而 不能保证评测结果的完整有效。同时评测结果的表示格式没有统一的标 准，使得其也不够准确直观。 3 ) 数学公 式图 像理解的评测体 系难以 建立 . 数学公式图像的结构描述方式复杂，造成评测比对算法的设计困难 数学公式蕴涵丰富的语法语义信息，多采用树型结构进行描述。将 处理结果与标准结果进行比对时需要面对 “ 树匹配”这样的软件难题， 因 此难以 使用自 动化方 法进行性能评测。 而人工评测又存在 工作量大、 易出 错的 缺点， 难以 满 足大批量性能评 价的要求。 . 如何建立集成化的性能评测环境并进行良好管理 如何 使用良 好的 评测规范 建立集成 化的 性能评测环境，该 评测环境 中必须有良好的评测规范，对评测环境中的包括评测对象， 基准集，结 果集， 评 测报告 等在内 的诸项内 容进行 有效管 理。同 时， 评测 对象、 评 测目标、评测样本，评测场景和评测参数等诸多因素构成了测试环境的 复杂性和不 稳定 性， 这些也是评 测体系建立中需要解决的 难题之一。 . 如何保证评 测方 法和评测系统的可 移植性与适应 性 任何系统的评估测试都应该考虑到系统如何识别简单的表达式，然 后去检测系统对复杂 度增长情况下的 响应情况。针对 庞大的 数学公式图 像处理系统，这点也是必须考虑到的。 通过以 上分析可以看出:针对数学公式图 像理解的处理结果进行评测是极 具挑战性的，此方面的研究也是必要和重要的。 第a 页 第一章 绪论 第三节 数学公式图 像理解性能评测的现状与 概述 目 前有关数学公式图像的性能评测主要集中于针对结果的评测，而且基本 采用定性分析的方法.有关数学公式处理结果的定量分析是一项十分困难的工 作， 该评 测分析过程主要包括了 两个阶段:一 个是符号内容的识别，另一个 是 图像内容的理解。本文的研究重点是针对图像理解部分的性能评测，但如果一 个阶段的评测是独立于另一个阶段的，或许不能真实反映系统的性能;因此在 针对图像理解的性能评测过程中会涉及到有关符号识别内容的评测，但在微观 上会要求把两者的评测效果分离，宏观上形成集成化的评测方法体系。 自从二十世纪六十年代末提出数学公式的处理问题以来，有关数学公式处 理的各个方面问 题都有或多 或少的 研究。由 于早期的研究人员主要致力于理论 方面的研究， 而没有实验结果，因 此很长一段时间并没有提出 如何评价一个数 学公式处 理系统的 性能好坏的问 题。 在2 0 0 0 年 之前针 对数学公式图 像的 评测主 要 还 是 借 鉴 一 般的 文 档图 像 处 理 系 统 的 评 测 方 法 1 9.2 0 ,2 1,9 ， 大 致 可 以 分 成 三 类 : 1 ) 注 重 公 式 的 结 构， 通 过 测 试 只 给出 两 种 结 果 : 正 确 或 者 错 课 。 2 ) 只考虑数学公 式中的 符号的 识别 率情况: 3 )只 对少数非 常典 型的 数学公式 进行评测， 这些公式由 少数固定 人员 整齐 编写，结果常 常都能正确识别，目的 仅仅是证明 使用的方 法至少对这些公式是 适用的。 这些评测方法都是最基本的，同时也是片面的，性能指标也过于笼统，测 试样本集规模也过小。进入二十一 世纪以 来， 有关数学公式评 测方面的 研究逐 渐增多。 k a m - f a i c h a n 等在【 1 中 提到了 把数 学公式处理中 的错误 类型分成了 两种: 公式中的符号的错误识别和公式本身的错误，并给出了两种错误率的计算公式， 即用错误个数除以公式总数，但并没有说明如何找到这些错误，也没有提出有 效的评测步骤和流程。 不 久 以 后 ， m .o k a m o to 等 人 在 2 中 提出 了 一 种 基 于m a th m l 格 式 的 ， 针 对 数学 公式结构分析进行评估的方法。他们 将数学公式的标准分析结果和实际的 分析 结构都用 m a t h n e 格式表示， 然后 在此基础上进行比 较， 来评测那些典型 的数学公式类型 ( 主要包括角标，分式，根式，矩阵，极限等)的结构分析结 果是否正确。这一方法，针对简单的非常典型的数学公式结构比较理想，但复 第 5页 第一章 绪论 杂一些的结构，则比较结果不甚理想，同时该方法没有针对 ma t h n f 的特点进 行有效的改进，因而缺乏通用性。另一个缺点是把简单结构的错误的权重与复 杂嵌套结构的错误的权重设计成了相同值，这样无法区分具体的错误原因和错 误性质，也不满足性能评测是为了给系统研发指出问题和改进方向的目的。 z a n i b b i 等人在【 3 中提出了 一 种通过计算出 现在数 学公式的 不同 基线上的 符 号集合的 方法来对公式进行自 动 化评测的 方法。该方 法从微观上深入了 对识别 结果的 评测， 本质上还是针对识 别结果进行评测，同时 其在宏 观上不能很好的 评测整个数学公式处理系统的性能。 近 年 来 ， u tp a l g a ra in 等 人 在 4 , 6 中 提出 了 针 对 数 学 公 式 识 别 研 究 的 数 据 仓库的组织 和数 据格式的 描述等问 题; 但仍没有就产品 级数学公式图 像处理 系 统的评测研究提出一个完整有效的评测体系;无法从宏观上指导针对数学公式 图 像处理的 完整的评 测管理与 评测步 骤流程. k a z u k i a s h i d a 等 人在 习 中论述了 应用大规模印 刷体 数学公 式样张集 合作为 评测样本的数 学公式识别系 统的性能 评测问题，并 创建了自 己 的数据库 集合; 但其中的主要 工作也更加偏重于符号 识别的性能评测。 鉴于目前的实际需要和研究现状，研究并实现数学公式图像理解的性能评 测是必要的也是艰巨的。 第四节 本文的主要内容与结构 数学公式图像理解需要有效的性能评测与分析，针对该领域，目前尚没有 完整有效的 评测方法和评测 体系 模型。本文在前人研究的基础上，首先分析了 数学公式图 像理解的句法结构 描述模型:然后基于 此描述模型，建立了 基于句 法结构分析指导的版面结构树型 模式匹配的 性能 评测方法:进而以 该评测方法 为核心建立了 完整全面的数学公 式图 像理解的性能评 测模型，论述了 包括评测 目 标、评测参数和评测结果等在内的 性能评测体系; 最终实现评测方法、 评测 流程与评测环境的 集成， 并 给出 了具 体的 评测实 例和实验 结果。 下面分别介绍各章的主要内容。 第一章: 本文的引言章节。 提出 本文研究的问题 一数学 公式图 像理 解的 性 能评测与分析，指出其在数学公式图像处理中的地位，阐述了对该问题进行研 究的 价值和难点， 并对前人的 研究 状况 进行了概 述. 集 6页 第一章 绪论 第二章:本文的核心章节。首先给出数学公式图像理解的句法结构描述模 型;然后提出针对版面结构分析结果的基于树型模式匹配和不同权重指标的先 自 底向上再自 顶向 下的评测比 对方 法;最 后建立了完整的针对数学公式图 像理 解的性能评测模型。 第三章: 本文的 展开章节。首 先说明了 评测数据的获取准备与格式描述， 然后 通过评测目 标、 评测参 数的设计与具 体方法实现的结果实 例给出了 完整的 评测流程;最后说明了性能评测环境模型及其具体的组织搭建结构. 第四章:本文的实验章节。为验证以上评测方法和体系的正确性及有效性， 首 先给出了 实 际应用的 样本 集介绍，其中包 括了 详细的统计分类情况; 然后 介 绍了具体评测结果的分类统计与分析情况，给出了定量分析结果。 第五章:本文的总结展望章节。对全文内容进行回顾，并指出下一步的改 进和发展方向。 第 7页 第二章 数学公式图像理解的性能评测模型 第二章 数学公式图像理解的性能评测模型 上 一章介绍了 针对数学公 式图 像理解的性能 评测的难点与现状，为 解决以 上提出的问题，本文建立了针对它的性能评测模型，本章将对此评测模型和具 体的评测方法进行详细完整的论述。 第一节 数学公式图像理解的句法结构描述模型 z . i . i数学公式图像理解的相关背景知识 为方便后面的理解，本小节介绍数学公式图像理解相关的背景知识。 数学公式是一种形式化语言，蕴含着丰富的结构信息和知识信息，数学公 式图像理解就是了解数学公式中各个子表达式的内容组成，并将其表达的相关 知识以合理的方式进行重现和重用。 机器理解数学公式主要是从认识符号、分析公式结构及理解公式语义这三 个层面上进行。认识数学公式符号只需要借助传统的模式识别技术就能很好的 实现;在公式结构分析理解阶段，数学公式的表达形式被划分为三个层次，即 数学公式符号之间形成的版式结构，依据数学公式各个符号之间的组织关系形 成的句 法结构， 以及数学公式的 语义含 义。 图2 . 1 展现了这三 个层次之间的 依赖 关系。 承法进 期 、 .、 端 /口 从 句法结构 至 .- .一.， 计抹含义 图 2 . 1数学公式图像 理解三个 层次 之间的 依赖关 系 数学公式的结构分析方法根据其处理目 标和层次的不同，分为三类1川: 版式结构分析要求识别数学公式的排版结构，分析结果足以原样恢复 第 ，页 第二章 数学公 式图 像理解的 性能 评测模型 公 式版式。科技文献数字化 过程中， 为了 保留原 文版面结构， 就需要对公式版 式 进行分析。 句法结构分析句法结构是介乎于图像版式结构和语义含义之间的描述 机制，既体现出公式的计算 含义， 又直接决定了 公式的版式形式。 句法结构分 析要求识别出数学公式中的句法结构，基于先验规则和句法规则抽取数学公式 的句法信息，在此基础上依据运算符的优先级及操作符与操作数之间的操作关 系抽出符合数学公式表达的各级子表达式，形成数学公式完整的结构。 语义结构分析准确理解整个数学公式的数学含义，明确公式的运算顺 序和计算方法，从而实现数学公式的自动计算。 2 . 1 . 2数学公式图像理解的句法结构描述模型 文档图像处理的目的之一便是对文档图像的表面和深层次的结构的理解 11 6 1 。 本 文 设 计 的 数 学 公 式图 像 理 解 句 法 结 构 描 述 模 型 是以 句 法 驱 动 为 核 心 的 ， 版面信息作为辅助的分析描述模型。它采用四元组方式进行表述即: 句法结构 描述模型 声厦 版面关 系， 符号集，语 法规则， 句法规则 - - - - - 一:孚 i i 功能函数 s i n c o n s i n k i n f l o g i n 1 g l i m m a x m i x m o d c o t h d i m d e t e x p d e g 3 )语法规则: 语法规则定义了所有符号具有的语法信息， 包括符号类型、 语法属性和 符号之间的约束关系和组合关系。 4 )句法规则: 句法规则定 义了 所有 类型 操作符之间的优先 级别、 操作符的目 类型 ( 即 操 作符所拥有的 子表达式的 个数) 和各种类型子 表达式的 组合结构。 根据处 于同一层次操作符之间的优先级别比较可以确定该数学公式在这个层次上 的计算顺序. 并且针对不同类型的子表达式定义了动态的结构模版， 这种结 构模版规定了不同表达式类型下子表达式的特征， 具有消除句法歧义和识别 第 页 第二章 数学公式图像理解的性能评测模型 噪音的作用。 此外，整个数学公式图像理解的句法描述描述模型需要底层知识库的支持， 所有有关符号集合，语法规则，句法规则的基础信息都存储在知识库中。该知 识库对与数学公式图像理解相关的知识和经验进行编码，并制定一套通用规则， 以辅助实现对数学公式表达式中所蕴含的知识的推理、演绎、判断和决策。 2 . 1 . 3 数学公式图像理解的句法结构描述模型的处理结果 一个数学 公式由多个子表达式组成， 而每个子表达式在构成某个子表达 式 的一部分的同时，又可能同时由多个子表达式构成;这样，一个数学公式与它 的多个子表 达式之间形成一种树状结构， 树的 根与分支节点正 好反映了 数学 公 式及其子表达式之间的组合与被组合的关系。本文使用句法结构树来表示数学 公式图像理解的处理结果。 从逻辑实 现上讲，该树是一种带标记的 有序多叉树， 操作符一定是树的 根 或者中间节点，其孩子个数由操作符的目 类型决定，操作数则一定是树的叶子 节点。树中的 每一个节点都会存储从数学公 式定 位、识别、切分一直到结构 分 析理解所获的各种信息数据。 从实际 物理存储实现讲，为了 便于后 续处 理， 按照孩子兄弟转换法将多 叉 树转换成标准的二叉树结构。节点间的父子关系表示了逻辑实现中根节点或中 间节点与其第一个孩子节点之间的关系，而节点间的兄弟关系则表示了具有同 一个父节点的几个孩子节点之间的关系。 针对图2 .3 ( a ) 中所示的公式， 对应画出 其逻辑意 义上的 句法结构树 如图2 . 3 伪 ) 所示， 为了 方便表 示， 树节点中 包含的具 体的 版面关系和 句法规则没 有显示: 图2 . 3 ( c ) 中 表示了 在 句法结构分析中 抽取 操作符的 先后层次 顺序，而图2 .3 ( d ) 表示了转换后的物理存储结构。 第 1 2页 第二章 数学公式图像理解的性能评测模型 即- 肠 z +扩t l e t d s .八1 二门 2 加 ) 盆学公式 示例 当酮抽取的场作箱抽取层饮 .匕 + -0 j ac n e 1 . 目2 o 勿作位 叶了节 直口 件作 材 .节 口 嘴 闷节 直 向 致学公式句毯绪构分析的逻辑实砚闭 橄作符的抽取层次 但) 掀学公式句法结构分析的物理实砚 图 2 . 3数学公式句法结构分析结果的描述示例 第 1 3页 第二章 数学公式图像理解的性能评测模型 第二节 数学公式图像理解的性能评测方法研究 根据本章第一节中对数学公式图像理解层次的划分，针对其的性能评测可 以对应划分成三个层次:版面结构的性能评测，句法结构的性能评测和语义结 构的性能评测。同时 可以 看到， 在高一级的 数学公式图 像理解层次的基础上， 进行对 应的 性能评测: 才可以高 屋建 瓶，获 得全面 丰富 的处理 模型 与描述信息， 得到相关的指导。因 此在己 经提出 句法结 构描述模型的基础上， 本文主要针对 图像理解中版面结构分析的处理结果提出针对性的性能评测方法;首先分别从 宏观和微观两个角度介绍具体的性能评测方法。 2 . 2 . 1基于宏观版面级别的性能评测方法 符号 位置 ( p o s i t i o n o f a s y m b o l ) : 对于 任意一 个数 学符号s y m b ， 使用包围 它 的 最 小 外 接 矩 形 框r e c t(s y m b ) 的 位 置 来 描 述 它 的 空 间 位 置。 定 义四 元 组 (xi. x r , y t , y b ) 。 其中: x 1 表示r e c t ( s y m b ) 的左 上角的x 坐标值; x r 表示r e c t ( s y m b ) 的 右下角的x 坐标 值; y t 表示r e c t ( s y m b ) 的左 上角的y 坐标值; 沙表示r e c t ( s y m b ) 的 右下角的y 坐标值: 水 平中 心线 ( h o r i z o n t a l ce n t e r l i n e ) : 简称h c l ，穿过一 个数学 符号的中 心 位置的 水平直线. 对符号s y m b ，它的中心位 置c e n t e r ( s y m b ) ( x , y ) 计算如 下: c e n t e r ( s y m b ) x =r e c t ( s y m b ) x l + r e c t ( 匀叨 b ) . x r 2 r e c t ( s y m b ) .y l 十 r e c t ( s y m b ) . y r 2 ( 2 - 1 ) c e n t e r ( s y m b ) .y = -1 cxcy !1，est 对 于同 一 个 数 学 公 式 e 中 的 符 号 s y m b (i) ， 令 d i是点 (c x ,乌)到 直 线 l 的 距 离， 则满足 m in y d i s o曲of ( 2 - 2 ) 的 直线l 就是数学公 式e 的一 条h c l .实际水平中 心线用平 行于 x 轴的直线 y = k i rr 似， k 取c y 的平均 值. 第 1 4页 第二 章 数学公 式图像理 解的 性能评测模型 不同数学 公式的 版面结 构具有 不同的 复杂度，在给出了以 上两个概念后， 给出针对数学公式图像理解的 “ 版面复杂度”的概念。 版面复 杂 度 ( g e o m e t r i c c o m p l e x i ty) : 简称g c ， 通过计算一个数学 公式中 的水平中心线的数量描述了公式版面结构的多样性，层次性与复杂程度。由于 版面结构在一 定程度上决定了句法结 构，因 此该概念也可以 在一定程度上描述 公式句 法结构的复 杂度。图2 . 4 中， 数学 公式a 的所有符 号都 排列在一条h c l 上， 则 该数学公 式的版 面复 杂度g c ( a ) = 1 0 数学公式b 中 操作数a , b , c , 2 和 a 以 及 操作符中的 ，和 + ， 都处于同 一条h c l 上， 而a 的 上标2 和a 的下 标1 又处于两条 不同的h c l 上， 因此g c ( b 目 .同 样道理， 数学公 式c 和数学公 式 d 的版面复 杂度g c ( c ) = 5 , g c ( d ) ， 8 . a + b + c = 2 + a- - - - - - - - 一(.)a 2 + b + c = 2 + a , - - - - - - - - - 一 (b ) a + b r + c i 二 2 + a , - - - - - - - - 一 :0 :, 1 1 + 0 + r 二 里 + a , _ _ _ _ _ _ _ _ _ 一 。 声 图 2 .4数学公式版面复杂度计算示例 数学公式中所有符号的地位是不同的，这也是由不同地位的水平中心线决 定的;将那些句法结构分析 中产生的核心操作符和操作数称为基准符号 ( b a s e - le v e l s y m b o l ) ， 在 结 构 分 析 中 如 果 这 些 符 号 识 别 错 误、 版 面 关 系 或 者 句 法 关系判断错误， 则产生的影响更大，因为周围的非基准符号 ( n o n e b a s e - l e v e l s y m b o l ) 都是围绕 在它的周围， 依附在 基准符 号上的， 从而将产生一系列 连锁的 错误反应.而数学公式整体版面复杂度的大小往往是由那些非基准符号的数量 和位置所决定的。 任何系统的评估测 试都 应该考 虑到简 单与复杂 度增长 等多 种 情况下的响应情况。因此对数学公式版面结构分析的结果进行评测，必须考虑 公式的版面复杂 度， 结合不同复杂度和不同层次上发生的错误，来分析 评价最 终的处理结 果.因 此必须考虑 针对不同位置的 符号设计不同的权重。 根 据j o y d ip m itra 和u tp a l g a r a in 等 人 的 工 作 181 ， 用 字 母l 来 表 示 符 号 在 数 学公式中 所处的级别， 也就是水 平中心线的级别。 其中 ，基准符号的 l定义 为 零; 然后按照数学 公式中 符号的版面关系，基准符号向下的符号所处的级别 依 次递减为 一 1 ， 一 ， ; 基准符号向 上的符号所处的 级别依次递增为1 , 2 , 。 第 1 5页 第二章 数学公式图像理解的性能评测模型 赋 予 在 第 k 级( 即 l = k ) 发 生 的 错 误 以 权 重 兴 ， 然 后 分 别 定 义 : st 是 ix l + t 整体识别理 解的字符 个数: s 。 是发生 错误的字符 个数: 民是级别为i 的字 符个数; e ; 是级别为i 的发生 错误的 字符个数。 最后定义 版面级别的性能评测系 数丫 的计 算公式为: s + 2 : ,e , x 7 6 c = 1 一 s , + y尺 x ( 2 - 3 ) 1-罕一111+1 这样， l值越小的符号 ( 即权重越高)发生错误的影响也越大，造成最后的 指标系数越小。图2 .5中示例的g c =5 。每个节点的级别与权重如表 2 .2 所示。 3210-i 图 2 .5版面信息中水平中心线的级别划分示例 表 2 . 2版面结构分析的级别与权重计算 数学符号版面级别 权重 y =1 n x 十- 01 a r c t a n x- 11 / 2 c1 1 / 2 f s i nxdx21 / 3 d31 / 4 2 . 2 . 2 基于微观树型模式匹配的性能评测方法 数