（计算机软件与理论专业论文）数学公式结构描述与分析.pdf

摘要 摘要 数学公式广泛存在于各类文献之中。毫无疑问，对数学公式图像的自动处理 具有非常的重要性和必要性。同时，数学公式图像处理是一个具有相当难度的 前沿课题，而其中数学公式的分析与理解尤为困难。 本文基于对前人研究成果的总结，首次在模式识别领域提出数学公式语法结 构分析的概念，创造性的提出了数学公式语法结构的描述模型，并建立了数学 公式语法结构与版面结构之问的依赖关系。 本文系统地总结了数学公式的先验知识与语法规则，对其进行了良好的归类 并建立规则库，便于计算机实现与访问。首次建立了语法结构分析与版面结构 分析互动的控制机制，提出“基于语法规则驱动版面结构分析，同时基于版面 分析结果指导语法规则的选择”这样一个自适应的分析机制。 本文基于“以系统优势体现机器智能”的思想，建立了一个流程完整、算法 稳定的处理流程实现对数学公式结构的完整分析的自动处理系统。同时，本文 提供的方法可应用于不同领域的数学公式结构分析，在对数学公式进彳分析的 同时可反向对公式识别结果进行判断与纠错。 关键字 文档图像处理数学公式图像处理数学公式语法描述语法结构分析版面 结构分析 a b s t r a c t a b s t r a c t n u m e r o u sm a t h e m a t i c a le x p r e s s m n se x i s ti na l lk i n d so fd o c u m e n t s t h e r e1 sn o d o u b tt h a tp r o c e s s i n go fm a t h e m a t i c a le x p r e s s i o n si m a g ea r eo ft h em o s ti m p o r t a n c e a n dn e c e s s i t y , b u ti ti sat a s kf a rm o r ed i f f i c u l tt h a no r d i n a r yt e x tr e c o g n i t i o n ， e s p e c i a l l ya n a l y s i sa 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 le x p r e s s i o n s ， f o rt h ef i r s tt i m e ，t h i sp a p e rp r o p o s e st h ec o n c e p to fs y n t a c t i cs t r u c t u r ea n a l y s i s o fm a t h e m a t i c a le x p r e s s i o n si np rf i e l d ，a n dd e s i g n sac r e a t i v em o d e lt od e s c r i b e s y n t a c t i cs 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 s t h i sm o d e lr e f l e c t st h er e l a t i o n s h i p b e t w e e ns y n t a c t i ca n dl a y o u ts 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 s t h i sp a p e rs u m l l l a r i z e sm a t h e m a t i c a lt y p e s e t t i n gr u l e sa n ds y n t a c t i cr u l e sb a s e d o nk n o w l e d g ea n de x p e r i e n c e ，b u i l d su par u l eb a s es ot h a ts y s t e mc a n e a s i i y i m p l e m e n ta n dr e c e s s a n dt h i sp a p e rb u i l d su pa ni n t e r - a c t i v ec o n t r o im e c h a n i s m b e t w e e nl a y o u ta n ds y n t a c t i cs 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 s ，p r o p o s e sa n a u t o a d a p t i v ea n a l y s i sm e c h a n i s mt h a tl a y o u ts t r u c t u r ea n a l y s i si sb a s e do ns y n t a c t i c r u l e sa n ds y n t a c t i cs t r u c t u r ea n a l y s i si sb a s e do i lr e s u l t so fl a y o u ts t r u c t u r ea n a l y s i s t h ea d v a n c eo fm a c h i n ei n t e l l i g e n c ec a nb er e f l e c t e df r o mac o m p l e x ，s t a b l e ， e f f i c i e n tp r o c e s s i n gs y s t e m w eb u i l du pac o m p l e t es t a b l em a t h e m a t i c a le x p r e s s i o n s s t r u c t u r ea n a l y s i sa u t o p r o c e s s i n gs y s t e m t h em e t h o dp r o p o s e db yt h i sp a p e rc a nb e u s e dt oa n a l y s i sa n ym a t h e m a t i c a le x p r e s s i o n si na n yf i e l d b e s i d e so fs t r u c t u r e a 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 s ，t h em e t h o dc a nb eu s e dt od e t e c ta n dc o r r e c t r e c o g n i t i o ne r r o r s k e y w o r d d o c u m e n ti m a g ep r o c e s s i n g ，m a t h e m a t i c a le x p r e s s i o ni m a g ep r o c e s s i n g ， m a t h e m a t i c a le x p r e s s i o ns y n t a c t i cd e s c r i p t i o n ，s y n t a c t i cs t r u c t u r ea n a l y s i s ，l a y o u t s t r u c t u r ea n a l y s i s i i 南开大学学位论文电子版授权使用协议 ( 请将此协议书装订于论文首页) 论文数学纹式豫糊拘述占，相系本人在 南开大学工作和学习期间创作完成的作品，并已通过论文答辩。 本人系本作品的唯一作者( 第作者) ，即著作权人。现本人间意将本作品收 录于“南开大学博硕士学位论文全文数据库”。本人承诺：已提交的学位论文电子 版与印刷版论文的内容一致，如因不同而引起学术声誉上的损失由本人自负。 本人完全了解直五太堂图盘值羞王埕在：焦旦堂焦迨塞的筮堡赴壁! 同意 南开大学图书馆在下述范围内免费使用本人作品的电子版： 本作品呈交当年，在校园网上提供论文目录检索、文摘浏览以及论文全文部分 浏览服务( 论文前1 6 页) 。公开级学位论文全文电子版于提交1 年后，在校园网上允 许读者浏览并下载全文。 注：本协议书对于“非公开学位论文”在保密期限过后同样适用。 院系所名称：机嚷唱敲z 1 芜。 作者签名：露k 矗友 学 “3 - ：以。弓0 0 目期：舻6 门7 日 秉鬟i 墨帮蔼 方f j 毒 天系操作椅s 创 皇i 壶iv 干唪ooo 州则操作符 “ + 一， c o ss i nh o r n s i n ht a n hk e * t a n 二角函数名 d e t i n fc o td i ms u pc s cs e c 特殊操住 穹 e x l o l i r a8 f 8 8 0sa r c s i nl o gl n s x a r g t a na r gr a i nc o s h d e gp rc o t h g e dl g i nl i r ai n fl i r as u pr o o d 第1 2 贞 第二章数学公式语法结构定义与描述 2 2 4 按操作符目类型分类 操作符的目类型可以分为单目、双目和多目，其详细分类列表见表2 6 。 表2 6 按操作符目类型进行操作符分类 ( ) 】10 ) lj ，“ 一，、v 饱h 操作携 h o r ns i n ht a n hk e ri n fd i ms u p e x p a r gc o s hd e gp rc o r kg c dl g i nr f l o d 干+ d a 单般g 操作特 s i nc o sc o tt a nc s cs e ca r c s i nd ，r s o ca f c t a n x牛ooo ，= 墨 付兰兰 目操作犄 b # _ j 抖曹二2 ； d e tl i r a l o g r r l a xr a i nl i m i n fl i r as u p i 一一 多日操作特ff 丌nu 厂 第三节数学公式语法结构描述模型 2 3 1 描述模型设计原则 数学公式语法结构描述模型必须遵循以下原则： 1 必须是可计算、可检索的。 对数学公式语法结构的描述必须在有限的操作步骤中完成，而且描述结构能 够满足可编辑、可检索的要求。 许多现有的研究工作，都直接基于版面结构进行数学公式的分析与理解。其 处理结果大多以l a l r e x 形式输出，而l “t e x 则是基于数学公式的版式结构进行 第1 3 贞 第二章数学公式语法结构定义与描述 排版编辑的。这样的形式无法反应数学公式语法结构的可编辑、可检索特征。 2 必须是可判别的。 文档图像在扫描打印使用过程中，难免产生大量的光噪音热噪音及离散噪 音。尽管在对图像进行分析处理之前进行了噪音处理，但是对于某些结构与数 学符号类似的噪音，如“”、“一”等，如果不依靠语法分析完全依靠版面信息 则无法完全去除。 除此之外，由于字符识别器本身的误差，或由扫描引起的字符粘连而导致的 识别错误等，造成数学公式字符丢失或被误识为其他字符导致语法错误。为了 检查并纠正这些错误，就要求对数学公式语法结构的描述能够实现可判别。 3 必须具有鲁棒性和简洁性 对数学公式语法结构的描述和分析，必须具有精度高、速度快、系统结构简 洁、处理功能完善的特点，能够克服图像质量低下和各种噪音干扰及识别的错 误，保证数学公式语法结构自动处理的精度，便于处理系统的实现、维护与升 级。这样才能满足日常应用中处理大量普通文档中数学公式的应用需求。 2 3 2 语法结构描述模型 根据以上原则，我们建立了四元组形式的数学公式语法结构描述模型。 数学公式语法结构= ( 字符集，子表达式树，语法关系。版面关系) ： 其中： 1 字符集：组成一个数学公式的所有符号，包括所有操作符与操作数。 2 子表达式树：2 1 节中介绍了子表达式的概念，一个数学公式由多个子表 达式组成，而每个子表达式在构成某个子表达式的一部分的同时，又或 者同时由多个子表达式构成。这样，一个数学公式与它的多个子表达式 之间形成一种树状结构，树的根与分支节点正好反映了数学公式及其子 表达式之间的组合与被组合的关系。 3 语法关系：数学公式的编写和排版必须遵循数学领域所规定的一系列规 则，这些规则包括符号间的组合关系、操作符之间的优先级限定、各种 子表达式的阅读顺序等，这些构成了数学公式的“语法关系”。在进行数 第1 4 页 第二章数学公式语法结构定义与描述 学公式语法结构分析时，需要根据统计汇总得到的先验规则，借助版面 结构分析的结果，对数学公式的语法结构进行抽取、分析、验证，籍此 获得完整的数学公式结构。 4 版面关系：即数学公式的版面结构，包括构成公式的所有符号的内容、 字体、字号，以及符号之间的空间位置关系。数学公式图像处理系统中， 经过图像预处理，公式定位，字符识别之后，进行数学公式结构分析。 结构分析的输入为字符识别结果及各符号在公式中的空间位置，要获取 数学公式的语法结构就必须利用数学公式的版面结构。 针对图2 1 中的公式，我们可以利用数学公式语法结构描述模型画出其予表 达式树如下： 口，。黔篓。o 梆潞磊钠鬈豁， l j i | fr 节 谍* j 7 1 川，划节 1 r棋钳血，叫：i 其中： 1 字符集为 图2 2 数学公式语法描述模型示例 第1 5 页 第二章数学公式语法结构定义与描述 表27 示例公式中的字符集 f 厂一= l i r a 一 操作符 十( ) d4 - + 一 操作数甜b3t tt0 lxlx 2 公式语法关系如下： 1 ) 除了d 、( 、) ，其他操作符在公式中的目类型均为二目 2 ) 公式中操作符之间的层次及优先级关系如下表所示： 由于公式中存在很多结构相同，版面位置不同的符号，为了清楚的 区分它们，首先对它们进行编号，如图2 3 ： 下 图2 , 3 示例公式符号编号 根据符号的版面位置及公式的版面结构，可以得到操作符的层次如 装太 害妒 国 陶2 4 示例操作符层次关系 第1 6 贞 第二章数学公式语法结构定义与描述 划分好操作符的层次之后，在语法结构分析中对操作符进行优先级 判断时，只考虑在相同子表达式内同一层次的操作符的优先级。对于某 个子表达式内只含有一个操作符这种情况，就不需要考虑它的操作符优 先级。这样，得到上例操作符优先级表如表2 8 ： 表2 , 8 示例公式操作符优先级表 f 表达式 子彘达式内最高层次操f 1 ：持优丸级k 系 j 孥芋出= 慨孚一“，。卜。= “) “l i r a 。，= 。l i m “ f 粤竽出 “ “d ” l i m 4 1 + x - 1 。 “一 h 0 x l + z l _ - “ 。_ 。 ( a x + b )”( ) 。 “+ “ 3 ) 字符的语法属性如下： 表2 9 示例公式中字符属性列表 f 边式 是行为组 f 无排作 操作符 习类型操作符剃- 类 月i 存恃嚣 操作符 ：，f 限 7 f 、心麓系 番 屯 霉如组舟 是丘 1 i m 卜、靠 特殊操作足 f j 龟、右关系秆凡 埘一 上、卜组台 世 尢 一一 多 卜 绱台 艟止 、 ( ) 鲢 一j s抖定衙j l + + 矗、也 腿剐 行 三 第二章数学公式语法结构定义与描述 2 3 3 语法关系定义与描述 数学公式语法结构描述模型四元组中的语法关系主要包括以下几个方面： ( ) 符号的语法属性 符号根据其操作属性可以分为操作数和操作符两大类。 操作数的语法属性相对简单，作为被操作的对象，在公式中只需要确定其属 于哪个子表达式，在子表达式树的层次等即可。 操作符作为子表达式的核心符号，负责进行操作数之间的操作，其语法属性 包括目类型、所在子表达式的相关特性、是否具有组合功能、其语义类型等等 特性。表2 1 0 给出了操作符在数学公式中的通常的语法属性。 表2 1 0 字符通常语法属性表 h 炎型 币- ，取，多 子表达式 位援 卜“矗卜f 毵n - t 下f 下f j l - f i h - j ri 相关特性 是仃必须 楚，f 符号本身n r 能 出或的位霹 h 氛n l “稿下一f k - 晴i 帽子符骂 定始符 大操作行 第。层分类 天系操作柑 运算操作特 标点符号 衙义炎，删功缱丽数 代数类 几t 4 炎 按照知汉分类 集合类 逻辑类 足僵属l j 组操作符是，代 功隧函数x = 十操 尤卜，f 般 f 】卜下限 作卜，f 限的分类 萌尤皆可 第1 8 页 笫二章数学公式语法结构定义与描述 ( 二) 操作符的优先级 2 1 节中介绍了本文所定义的操作符优先级，特指在数学公式语法结构分析 中，针对已经具备语法属性的操作符的优先顺序。同时，2 1 节中还对操作符按 照其对操作数的不同操作类型进行了分类。这里，给出不同类型操作符之间的 优先级关系如表2 1 1 。 表2 1 】不同类型操作符之间优先级关系 关系操佧符界定擞佧符鼬合 j ! 作倚叫则撵件枸 笑系操作扮 界定操作斡 组含擞伟符 四州擞作符 人的大脑中默认存在操作符优先级，这样在阅读公式的过程中，就限定了人 阅读公式的顺序。同时，操作符的优先级作为公式语法结构的构成依据，也决 定了操作数优先与哪些操作符进行组合构成子表达式。由此，操作符优先级也 限定了子表达式树的树状组织。 2 3 2 节中数学公式语法描述模型事例中，我们给出了操作符优先级在实际公 式分析中的应用。从示例中我们能看出，操作符优先级的比较，只存在于同一 子表达式相同层次上。对于相同子表达式不同层次或不同子表达式内的操作符， 不存在操作符优先级比较的概念。附录a 给出了同一层次可能组合的操作符之 间的优先级对照表。 ( 三) 子表达式树的组成 子表达式树的构成遵循以下几个原则： 1 依据操作符优先级建构子表达式树全局骨架： 2 对所有叶子节点依据其语法属性扩展子树； 3 对2 中每个子树再依据操作符优先级抽取骨架，重复操作l ； 4 依据1 、2 、3 中的操作反复迭代进行，直到所有的叶子节点均为操作数， 则终止，最终生成子表达式树。 第1 9 页 第二章数学公式语法结构定义与描述 2 3 4 小结 本章介绍了建立数学公式语法结构描述模型的原则，并建立了数学公式语法 结构的描述模型，对组成数学公式的所有符号进行了详细分类，并对其语法属 性进行了描述。给出了建立数学公式子表达式树的原则，对图2 - 1 的公式，按照 子表达式树建立原则，其完整分析流程如下： 第一屡次： 第二层次 第三层次 第四层次 第五层次 第六层次 第2 0 贞 第二章数学公式语法结构定义与描述 第七层次 ，p 、 来分斩的操作村，f 豪达式 u 中问节点 厂 操作数 “ir - n t 、 w 选参数 ff ，中问竹点 图2 5 示例公式详细分析流程 通过以上的分析，对于完整的数学公式，我们能在有限固定的步骤内进行拆 解分析，实现对数学公式的检索、计算分析。另外，我们在分析过程中进行了 扩展，对数学公式进行了分层处理，在每一步的分析处理中都借助于先验知识 及语法规则，针对公式中的噪音及识别错误及时地进行了校验及更正。此外， 在系统中，将数据描述、先验规则的描述和分析处理过程进行了划分，对公式 的总体分析处理遵循予表达式树生成原则，这样形成一个鲁棒、简洁的处理系 统。由此可知，该模型能够有效帮助解决数学公式版面结构与语法结构分析的 难题，对数学公式图像处理系统有着基础的重要作用。 第2 1 页 第三章数学公式结构分析的系统架构 第三章数学公式结构分析系统架构 定义了数学公式语法结构的描述模型之后，我们需要在工程上实现数学公式 的语法结构分析。与人相比，机器的本质不同在于“擅长计算而不能思考”。但 具体的思维目的能够通过相互搭配、良好架构的计算来逼近。任何孤立、封闭 的计算都不能称为智能。唯有以系统方式对具体算法进行整合，才能体现出机 器智能。在系统之中现实世界的各种复杂情况被分门别类的转化为具体算法的 解决目标而得到处理。新方法的提出和验证也必须基于成熟、稳定的系统进行。 没有系统支持的研究方法用于实践，而自系统实践中得到的真知使得对具体文 的解决更加合理、有效。 第一节系统处理目标 对数学公式的结构进行自动分析，期望达到如下处理目标： 1 获得完整、详细的公式结构描述。通过结构分析，能够得到数学公式所 有符号的属性、符号之间的组织关系以及数学公式的子表达式组织。数 学公式结构分析的分析结果将直接作为数学公式图像处理系统输出的依 据信息，以方便编辑、检索、计算的格式进行输出。 2 有效去除公式中的噪音。通过结构分析，针对公式中不能通过图像预处 理、符号识别等去除的噪音，能够有效的去除，保证数学公式符号的正 确性。 3 能够有效地检查纠正识别错误。通过结构分析，针对由字符粘连或识别 精度等引起的识别错误及由于特殊操作符与其限定符分离等情况引起的 错误，不仅能够有效地检查，而且能够正确纠正，以保证数学公式的正 确性与完整性。 普通文档图像中包含多种类别的数学公式，其版面结构组合繁多。各种版面 结构组合中，任何偏差、噪音( 图像生成、文档复制、图像采集过程中出现， 第2 2 页 第三章数学公式结构分析的系统架构 其数量和种类同样难以计算) ，加上字符识别器本身所存在的识别误差，都会造 成计算机自动分析的处理错误。我们无法设计一种完美的处理方法以克服所有 偏差、噪音和识别错误的影响。只能基于处理目标和问题描述模型，利用多种 局部、精确的处理方法，搭建合理、鲁棒的处理流程。以最大限度的实现处理 目标并满足应用需要。 第二节系统设计思想 基于以上处理目标，我们在设计数学公式结构分析系统时主要需要考虑以下 几方面的问题。 3 2 1 先验信息的统计与描述 数学公式的先验知识及语法规则作为数学公式语法结构分析的基础及直接 依据，在整个结构分析过程中需要保证随时能够进行访问存取。基于此目的考 虑，本文对数学公式的先验知识及语法规则首先进行了先期的统计归类与描述。 包括操作符与操作数的语法属性表、操作符的优先级定义表、字符之间的组合 关系表，数学公式子表达式的特性表等。 3 2 2 数据结构的设计与实现 在第二章中，本文给出了数学公式语法结构的描述模型，并基于该模型进行 了数学公式示例分析，最终得到数学公式的语法结构子表达式树。根据数学公 式子表达式的树状结构，在系统实现中，可以很方便的采用树形数据结构来表 示子表达式树的这种结构，而且便于检索查找。 3 2 3 “全局一局部”分析流程 根据数学公式语法结构描述模型中子表达式树建立规则，我们在系统实现中 也遵循此规则，对于输入的数学公式，首先进行操作符的抽取，得到子表达式 树的主干，然后根据操作符优先级及符号组合关系，进行操作符操作范围的限 定，得到每个子表达式的范围，再对予表达式依此处理。这样，形成一种自项 第2 3 页 第三章数学公式结构分析的系统架构 向下与自底向上相结合的处理过程，采用全局划分与局部逐层精化的处理方法， 最终得到完整的数学公式结构。 3 2 4 公式版面结构分析技术 进行数学公式的结构分析，就需要对数学公式的版面结构进行分析。数学公 式语法结构描述模型四元组中第四个元素是公式符号之间的版面关系，即公式 的版面结构。从该模型中，我们可以看出数学公式版面结构信息对语法结构分 析的重要辅助作用。在系统实现中，依据此模型，我们建立了以语法结构分析 作为主导，版面结构分析作为辅助手段的处理模型，由版面结构分析提供公式 的版面信息以协助语法结构分析从中获取语法规则并进行子表达式的划分。 基于此设计思想，我们给出这凡方面的关系如图3 1 所示。 图3 i 数学公式结构分析设计思想 第三节数据描述机制 j 1 i 具 数学公式的结构具有多维性，数学公式操作符的语法特征也具有不确定性， 这就导致数学公式的子表达式树结构的不确定性。这种不确定性表现在数据结 构上就是其子表达式树分支的不确定。要使得系统鲁棒、处理流程简洁、易于 扩展，就必须消除解决数学公式的这种不确定性所带来的影响。为此，我们在 设计数学公式子表达式树结构时中采用了伪二叉树这种结构。 伪二又树结构在逻辑意义上与一般的多叉树没有区别，根节点及中间节点表 第2 4 炙 第三章数学公式结构分析的系统架构 示操作符或子表达式，其分支个数由操作符的目类型决定，可以有一个、两个 或多个分支。这样形成逻辑意义上的数学公式子表达式树。 在系统实现中，我们采用父子兄弟链表来实现这种伪二叉树结构。节点间的 父子关系表示根节点或中间节点与其分支节点之间的关系。节点问的兄弟关系 表示同一根节点或中间节点的几个分支节点之间的关系。通过这样一个链表， 在系统实现中我们就可以完整地展现出数学公式的子表达式树结构。 图3 2 和图33 描绘了伪二叉树的逻辑结构及实现结构。 、r1 () 撵作符或r 袭返式 ii 操作数 一，o_一 图3 2 伪二叉树的逻辑结构 。操作符或子表达式口操作数 o一 图3 3 伪二叉树的实现结构 第2 5 页 第三章数学公式结构分析的系统架构 从图3 2 、3 3 中可以看出，不管数学公式子表达式的分支如何变化，这种伪 二叉树结构均能够方便的进行表示实现。这种伪二叉树结构能够表示多元化的 数学公式，涵盖了普通文档图像中常见的数学公式类型。且这种数据结构易于 扩展，便于分析过程中的检索查找，很大程度上提高了分析效率。 第四节核心控制流程 数学公式的结构分析是一个非常复杂的处理过程，其分析过程也是数学公式 子表达式树生成过程。根据子表达式树生成原则，可以看出子表达式的生成过 程为一个迭代过程。这也就意昧着数学公式的结构分析过程为一个迭代过程。 根据这种思想，我们给出了对数学公式结构分析自动处理的完整流程如图3 4 所 不。 析撬处理，去翰帽于符号 生庸杷始节点 生成赫停椅与撮怍赞链 柞符 挎辟拇忭荷弗投舞 而特钲捌分忭蓖圈 f 始怍持骨f 姥抽鞭， 鼙高层故的搬作精划衷 生成疆糠忭椅子表选式树结构 点j 甘 图3 4 数学公式结构分析流程 为了系统的简洁与鲁棒性，也便于进行系统维护调试，我们在实现过程中采 第2 6 页 薏 一 固毛 篁三兰塑兰竺苎箜塑坌塑塑墨竺墨塑 用了循环非递归的形式来实现数学公式的结构分析。图3 - 5 给出了其处理流程。 图3 5 数学公式结构分析实现的详细处理流程 在分析开始之前，首先明确两个概念，操作节点与浯法树节点。操作节点指 在结构分析时，每一步操作过程中根据版面规则划定的一定版面范围内的数学 符号所构成的分析节点。语法树节点则是指数学公式语法结构子表示达式树中 的节点，包括中间节点及叶子节点。 在分析过程的最开始，经过分析预处理后的数学公式，将其作为初始操作悟 点，对其迸行如下操作： 第2 7 页 第三章数学公式结构分析的系统架构 1 )抽取公式骨干操作符 遍历操作节点进行特殊操作符查找，并根据特殊操作符的版面范围 删除在其操作范围下的数学符号，若对剩下的符号进行骨干线抽取，得 到最高层次的操作符列表，生成当前操作节点。 2 )依据操作符优先级生成当前子表达式树 对当前操作节点中的操作符进行优先级查询，得到最高优先级操作 符，根据此操作符的语法属性，得到该操作符的子表达式树结构，若公 式的语法子表达式树为空，则将此操作符作为语法子表达式树的根节点； 若语法子表达式不为空，则将此操作符置于其父节点之厉。 3 ) 依据伪二叉树扩展子表达式树 检查生成的语法子树中是否有操作符存在于当前操作节点中，若存 在，则对此操作符进行第2 ) 步分析。直至当前节点中不再包含此语法 子树中的操作符。 4 ) 依次处理下一级符号 第3 ) 步操作完了以后，检查子表达式树的叶子节点是否含有尚未 分析的操作符，若有，则依此操作符的版面结构创建新的操作节点，对 其再从第1 ) 步操作开始分析。若全部节点分析完毕，则语法结构分析结 束，进行分析后处理及结果输出工作。 笫五节其他重点问题 3 5 1 先验信息的定义与使用 数学公式的先验知识及语法规则是语法结构分析的直接依据，那么其定义与 实现都必须在系统实现之前完成。因而，我们在先期即对数学公式符号的操作 属性、语法属性、组合关系、操作符优先级、目类型等进行了统计分类与描述。 语法规则库是保证数学公式语法结构分析的基础，为了保证在系统中能方便 的对其进行访问，要求其结构定义易于扩充、访问接口易实现。只有这样，才 能将其真正融入复杂的数学公式结构分析系统中，为结构分析提供可靠的核一t l , 支持与分析依据。 第2 8 页 第三章数学公式结构分析的系统架构 本文在系统实现中，考虑到语法结构分析过程中需要随时查询数学公式的语 法规则及操作符优先级，而且为了便于操作，我们将数学公式的符号操作属性 和语法属性、语法规则、操作符优先级、予表达式特性等先验知识及规则采用 二进制文件的格式，将其定义为系统资源供数学公式结构分析使用。部分语法 规则资源文件格式详见附录b 、c 、d 。 对语法规则资源库的访问与调用，采用如下方式： 系统启动时，语法规则资源库跟随系统初始化载入内存 语法规则资源库载入系统后，将以底层应用包的形式，为上层系统提供 调用接口，供系统分析使用 3 5 2 版面结构分析的功能与实现 版面结构分析作为语法结构分析的辅助工具，在系统实现中，其主要作用是 根据语法结构提供的信息进行分析，对符号进行骨干线抽取、子表达式中一级 操作符的选取、操作符版面范围的限定等工作。并能够方便的根据操作符之间 的间距、空隙来实现表达式的拆解。表3 一l 描述了版面结构分析在数学公式结构 分析中的作用。 表3 1 版面结构分析的作用 t 婴上作h 的 操作狩操作 补种特殊操律荷对其摄f 域避行 分析，形成袖号纰戏钓台节点升 范阉的限定 将柠峙纽或铸弁节点佧为整体进行 结构分析，侄】二j 疾环操作处理 骨l ：线分析为方艇的抽取h | 公式 j ：巾f 牾荷0 和川符弓投彩范围茂公a 荷号z 问 投影操作 的卒瞰导_ 柬分析公a 朗符号分ir f j ! f 况，逑l m 为语法结构分析i 蛭 j 公式 类型判断挺供侬概 版而结构 版网结构分析的目锄、以科铸 构采示出凳式的版蕊结构，蹙 树的构建 彖娩器震生成版确搦逆语言 第2 9 页 第三章数学公式结构分析的系统架构 在系统实现中，版面结构的实现采用模块化的机制，为语法结构分析提供功 能函数接口，由语法结构分析来驱动指导版面结构分析的执行这样实现数学 公式结构的完整分析流程。其模块组成列表见表3 - 2 。 表3 2 版面结构分析模块组成表 模块名称模块作用 国扫j 始化搬向站杜j 丹机模块 为h 便城葡精掏分析。楗l 打 颈分析模块 将幅了笱弓从淤剐她粜中删除 特汉剐过r 1 分饿i n 州山r | 、 个，待的雨数名避f r 台抑- 将嵌套：a - 个组卉操作枸中晌 所督符号剥豫，暖赴片干线抽取 功能箱模块 抽取“个语义彳亍的核一t 5 n 用的 绮号的水平中心线，印昔i f 线 枨制数学公式符弓之阎的审徘 艘觊台荚察等进n 版由子袁遮文 的拆分 ( i ) 生成傲学公式版i l j 结构 对 t | 荠处理模块 埘某些特殊粕子符号i ! 成h 版嘶结构子树 第3 0 页 第四章数学公式结构分析方法的性能评价 第四章数学公式结构分析方法性能评价 由于数学公式的结构复杂性和多义性，导致其性能评价极为困难。目前数学 公式图像自动处理的性能评价集中于针对识别结果进行测试评估，而对于数学 公式结构分析基本采用定性分析的方法。 第一节性能评价参数设计 造成数学公式结构分析性能评价困难的原因主要有以下几点： 数学公式符号类型多样、结构多变，造成评测困难 数学公式中包括各种类型的符号，同时由于数学公式的版面结构具有多 维性、语法结构具有不确定性，导致结构分析方法评测困难。 数学公式语法规则庞杂、含义多变，造成评测困难 数学公式的语法规则极为庞杂，并且存在多义性的特点。难以制定完整 确定的评测方法。 数学公式结构难以描述、难以比对，造成评测困难 数学公式蕴涵丰富的语法语义信息，多采用树型结构进行描述。将处理 结果与标准结果进行比对时需要面对“树匹配”这样的软件难题，因此 难以使用自动化方法进行性能评测。而人工评测又存在工作量大、易出 错的缺点，难以满足大批量性能评价的要求。 鉴于以上原因，本文建立了针对数学公式结构分析的定性评价方法体系，从 完整性、精确性、稳定性、容错性四个方面对本文研究内容进行性能评价。 4 1 1 数学公式结构分析的完整性 数学公式结构分析的完整性主要体现在以下几个方面： 符号集完整，即能够分析常规数学公式所使用的所有符号。 语法属性完整，即能够确定各种可能出现的语法属性。 语法关系完整，即能够理解各种语法关系并进行正确描述。 公式类型完整，即能够理解不同类型的数学公式。 第3 1 页 第四章数学公式结构分析方法的性能评价 4 1 2 数学公式结构分析的精确性 在对数学公式进行结构分析的处理过程中，其每一步的处理结果都必须保证 精确，主要体现在以下两个方面： 版面结构提取与分析的精确性 数学公式排版形式多样，受字体、版面风格影响严重。结构分析过程必 须能够精确的提取相关版面信息，同时精确描述公式的版面结构。 语法关系描述与分析的精确性 数学公式由遵循语法规则的子表达式组成，结构分析过程必须能够精确 的描述公式符号的语法关系，同时必须准确的理解不同子表达式之间的 语法层次和优先级关系。 4 1 3 数学公式结构分析的稳定性 数学公式种类繁多，子表达式之间存在复杂的语法嵌套层次，同时又可以采 用不同风格的排版形式。在数学公式结构分析过程中，应保持处理过程的稳定 性，对不同复杂程度的数学公式均能进行有效的处理。 4 1 4 数学公式结构分析的容错性 在实际应用系统中，首先需要进行数学公式符号识别，然后才能够进行数学 公式结构分析，由于识别结果可能包含各种类型的识别错误( 例如字符断裂、 粘连、误识、错识等) ，同时由于数学公式图像可能存在倾斜、扭曲等情况，造 成结构分析时输入信息有误。良好的结构分析方法必须具有容错性，能够接受 错误输入信息，保证处理过程的稳定：同时能够准确的判断出错情况，并保证 公式结构中其他部分的正确和完整。 基于以上四个方面，可对本文提出的数学公式结构分析方法进行定性评价 第3 2 贞 第四章数学公式结构分析方法的性能评价 4 2 1 完整陛评价 第二节本文方法定性评价结果 1 符号覆盖完全、语法属性定义完整 本文建立的数学公式结构分析方法覆盖了2 1 0 个数学公式符号，其中操 作数1 0 2 个，包含英文字母、数字、希腊字符等，操作符1 0 8 个，包含了所 有的公共操作符。 针对操作符，本文分别按照其版面特征、操作类型、目类型、语法组成 对其语法属性进行完整描述。针对操作数，本文按照字符集、合法存在位置 对其语法属性进行了完整描述。 2 先验规则完备、公式结构描述完整 数学公式中可能包含各种类型的子表达式，子表达式之间又存在各种嵌 套或限定关系。本文针对数学公式语法结构特征，定义了完备的先验规则。 本文方法立足于抽取数学公式的语法骨干结构，依靠优先级信息和语法 完整性先验规则将数学公式划分为不同的表达层次，最终将其转化为语法结 构树和版面结构树。这样的处理思想既能够描述版面结构，又能够建立语法 结构，对数学公式结构的理解更加完整。 3 处理机制合理、结构分析过程完整 本文建立了“全局语法指导局部版面分析”的处理流程，同时基于 处理方法正交性原则划分出各个相互独立的分析处理模块。这样的处理机制 既把握住公式结构的语法层次，同时又能够保证各个细节处理的精度。 综上所述，本文建立的数学公式结构分析方法体系能够完整的分析数学公式 版面结构和语法结构，满足各种后续应用的需要。 4 2 2 精确性评价 1 语法规则指导版面分析过程，保证版面结构分析的精确性 数学公式的版面结构表现为图像特征( 如物理位置、大小、版面关系等) ， 单纯利用图像信息或排版规则无法保证公式版面结构分析的精度。各种针对 第3 3 页 第四章数学公式结构分析方法的性能评价 公式版面特征的先验规则或先验阈值通用性差，导致处理精度低下。 本文提出并建立了基于数学公式语法规则指导版面结构分析的方法体 系，选择具有不变性的语法属性作为先验信息，总结具有通用性的语法关系 作为处理规则。从而大大降低了版面结构分析过程中对图像质量的依赖，克 服了排版风格多样化造成的处理困难，保证了版面结构分析的精确性。 2 版面信息校验语法关系描述，保证语法结构分析的精确性 抽取数学公式语法结构是提高计算机对数学公式自动处理智能化程度 的必然选择。由于数学公式所蕴涵的语法关系具有多义性，因此语法结构分 析存在很大的出错概率。 本文遵循“自顶向下一逐层精化”的思想，建立了数学公式的语法结构 层次化分析机制。在分析过程中，依靠版面特征来区分并判定具有多义性的 语法关系。 这样的处理方式，既防止语法关系的多义性破坏公式结构的完整；同时 又在每一个局部处理过程中，依靠版面信息提供更多的参考依据，保证了语 法结构分析的精确性。 综上所述，本文建立的方法能够实现对数学公式结构的高精度分析。 4 2 3 稳定性评价 1 基于符号优先级进行分层处理，保证分析结果的稳定性 本文设计的处理方法，以“操作符、操作数语法属性”、“操作符优先级” 为重要依据，建立层次化的语法结构描述体系。分层处理的思想既能够将复 杂的数学公式拆解为多个层次的简单表达式，同时又能够保证每一个局部处 理的精细程度，从而保证了分析结果的稳定性。 2 采用循环而非递归的控制流程，保证处理过程的稳定性 针对数学公式的结构分析过程往往体现为处理函数的递归性调用，由此 造成处理过程的不稳定、难以维护。 本文设计的处理流程从易用性、易维护的角度出发，采用了“数据循环 取代控制递归”的设计模式，将递归嵌套的控制流程转化为线性循环的控制 流程，这最大限度的保证了处理过程的稳定性和易维护性。 第3 4 页 第四章数学公式结构分析方法的性能评价 3 采用模块化的功能划分与整合，保证系统结构的稳定性 本文建立的数学公式结构分析方法体系包含多种处理技术、利用多种先 验信息。本文遵循模块化的功能划分思想，将系统结构划分为“先验语法属 性与规则”、“局部版面结构分析方法”、“公式结构拆分”、“公式结构描述” 等多个相互独立的处理模块，各模块提供严格定义的内部接口。 在主控结构分析流程中实现对各个独立处理功能的整合，这种系统结构 策略具有易维护、易扩充的特点，保证了系统的稳定性。 4 2 4 容错性评价 1 利用先验语法规则发现各类处理错误 本文总结并定义了完整的先验语法规则，既包括各类语法属性定义，也 包括各种语法关系描述规则。利用这些先验信息，可以非常快速的判断前期 处理结果中的错误位置和错误类型。 公式原形：d 6 双h 沮剐结粱：口；6r 皇塑竺塑鼍尊h 。1 + 一烈h 校验结果： 口占 图4 1 利用先验规则校正识别错误示例 2 伪二叉树描述机制包容各类处理错误 本文采用“伪二叉树”结构描述数学公式的语法结构，这种思想既能够 利用二叉树结构的严密性以保证分析结果的完整，同时又可以非常方便的插 入容错结点，记录各种错误结果的信息。这种描述机制保证了结构分析过程 的完整和稳定，同时又为容错处理提供了良好的数据基础。 第3 5 页 第四章数学公式结构分析方法的性能评价 公式脚口：0 + 6 ) 处州结果：主。+ 厂三二查苎! ! ! ! 墨墅、，一 则蝣粜= “ 二二二习0 i r 饕辜 l 罄； fi 霉釜 u 校蛉结果： 0 + 6 ) 咎篓 图4 2 利用伪二叉树结构校正处理错误示例 站铀肛眦 ! 指汉1 3 广度优先处理过程保证了系统容错性 本文建立的数学公式结构分析方法体系采用“广度优先”的方式进行结 构分析过程，这样就避免了传统的“深度优先”处理流程所造成的错误延续。 在本文设计的控制流程中，对数学公式结构的每一个层次都需要进行全局判 断和校验才能进入下一层次的分析过程。由此使得各种可能的处理错误在更 高的处理层次上被发现，防止后续处理过程被处理错误破坏。 公式哦彤：& 2 + 0 处州绌粜 彗 “，”铺喇 露 嚣 校聆蚺聚： 气2 + 0 图4 3 利用f “度优先方式校正处理错误示例 通过以上定性分析，可以认为本文所建立的数学公式结构分析方法体系具有 良好的容错性和稳定性，能够保证处理结果的完整性和精确性。对建立满足实 际应用要求的数学公式图像识别与理解系统将起到极为重要的推动作用。 第3 6 贞 第五章总结与展望 第五章总结与展望 第一节特殊结构的文档图像处理方法总结 本文详细阐述了针对数学公式图像进行结构分析的方法，数学公式是种特 殊的文档结构，其处理过程极为复杂，这造成了目前的o c r 技术和d i p 技术无 法有效处理这类文档图像。和数学公式类似，化学方程式、文法结构图、范式 等很多具有特殊结构的文档图像也同样无法被计算机精确快速的处理。我们希 望通过对数学公式图像结构分析的方法研究，探索并总结出针对特殊结构文档 图像进行处理的系统方法，提高计算机的智能水平。 5 1 1 处理方法设计总结 综合数学公式图像处理系统的设计经验，本文总结出在进行特殊结构文档图 像自动处理系统设计的时候，需要从以下几个方面进行考虑： 1 特殊结构文档的编写与排版规则总结 针对任何特殊结构的文档图像，在对其进行分析之前，应该首先弄清在该领 域此种结构文档的编写习惯、规则，即这种特殊结构的版面结构和语法结构。 确定如何编排这种特殊结构，就能知道该如何在图像中获取这些特殊结构。了 解了特殊结构的语法结构，即能确定在系统中该以何种方式来表示其含义。因 此，在