（计算机应用技术专业论文）印刷体数学公式的语法语义分析.pdf

毛；：，c ：l 科技处 学位委 申请日期：工阳矽年6 月f日 明 蚴一h 个 胖 纛黔 凡瑚 一 一一一 孤 蜊 一 一一 一 一 一 ， j ， 、秘- - 河北大学 学位论文独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教育机构的学位或证书 所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了致谢。 作者签名： 王累 日期：二竺l 年上月上e l 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留并向国 家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。学校可以公布 论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 本学位论文属于 l 、保密日，在兰：生年月! 日解密后适用本授权声明。 2 、不保密口。 ( 请在以上相应方格内打“ ) 保护知识产权声明 本人为申请河北大学学位所提交的题目为( 印刷体数学公式的语法语义分析) 的 学位论文，是我个人在导师( 田学东) 指导并与导师合作下取得的研究成果，研究工 作及取得的研究成果是在河北大学所提供的研究经费及导师的研究经费资助下完成的。 本人完全了解并严格遵守中华人民共和国为保护知识产权所制定的各项法律、行政法规 以及河北大学的相关规定。 本人声明如下：本论文的成果归河北大学所有，未经征得指导教师和河北大学的书 面同意和授权，本人保证不以任何形式公开和传播科研成果和科研工作内容。如果违反 本声明，本人愿意承担相应法律责任。 声明人：z 殳 作者签名：呈导 导师签名： 日期：垒：年三月上e t 眵张 日期：垄! 呈年l 月j i = j 日期：堡! 年鱼月l 日 摘要 摘要 目前主流的o c r ( o p t i c a lc h a r a c t e rr e c o g n i t i o n ，光学字符识别) 技术能够将印刷 体文字信息高速、自动地输入计算机，节省了大量的人力资源。然而，对于科技文献中 大量存在的结构复杂、含义丰富的印刷体数学公式，o c r 仍然不能较好地进行识别与 理解。因此，研究印刷体数学公式识别系统具有重要的理论意义和良好的应用前景。 本文针对印刷体数学公式的分析与理解进行了研究，在对公式结构类型进行归纳总 结的基础上，结合数学公式的语法规则和语义知识，对公式结构进行辅助处理，并且设 计了融入检错纠错规则的语法树遍历算法，自动纠正字符识别阶段产生的错误。此外， 本文还引入了一种数学公式的语法语义分析算法，定义了符合l l ( i ) 文法的表达式构成 规则，根据公式上下文情况判别表达式识别的正确性。针对不同类型印刷体文档的对比 实验表明，本文设计的具有检错纠错规则的结构分析方法和语法语义分析算法能够取得 较高的正确率和较好的执行效率。 关键词光学字符识别；数学公式识别；结构分析；语法分析；语义分析 a b s t r a c t a b s t r a c t a tp r e s e n t , t h em a i n s t r e a mt e c h n o l o g yo ft h e o c r ( o p t i c a lc h a r a c t e rr e c o g n i t i o n ) s y s t e mc a ns a v el o t so fm a n p o w e rb e c a u s eo fi t sa b i l i t yo fr e a d i n gp r i n t e dc h a r a c t e r si n t o c o m p u t e ra u t o m a t i c a l l ya n dq u i c k l y h o w e v e r , o c rc a nn o tg e ts a t i s f y i n gr e s u l t si nd e a l i n g 、枷t l lt h em a t h e m a t i c a le x p r e s s i o n st h a te x i s ti ns c i e n t i f i ca n de n g i n e e r i n gd o c u m e n t sb e c a u s e t h e ya l w a y sh a v ec o m p l e xs t r u c t u r e sa n dv a r i o u so fc o n n o t a t i o n s t ot h i sr e g a r d , i tw i l l g e n e r a t ei m p o r t a n t t h e o r e t i c a la n d p r a c t i c a l v a l u e st od or e s e a r c h0 1 1m a t h e m a t i c a l e x p r e s s i o n sr e c o g n i t i o ns y s t e m i nt h i sp a p e r , as t u d yo na n a l y z i n ga 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 sh a s b e e nd o n ea sf o l l o w s f i r s to fa l l ，s t r u c t u r eo fe x p r e s s i o n si s d i s p o s e db a s e do nt h e s u m m a r i z a t i o no fa l ls t r u c t u r et y p e so fe x p r e s s i o n sa n dt h ec o m b i n a t i o no f g r a m m a t i c a la n d s e m a n t i ck n o w l e d g eo fe x p r e s s i o n s a tt h es a m et i m e ，at r a v e r s a la l g o r i t h mf o rs y n t a xt r e ei s d e s i g n e dt oc o m p l yw i t ht h eo r r o l d e t e c t i o na n de r r o rc o r r e c t i o nr u l e s8 0 嬲t oc o r r e c tt h e a t o r so c c u r r e di nt h ep r o c e s so fa u t o m a t i cr e c o g n i t i o n m o r e o v e r , a l la l g o r i t h mu s e dt o a n a l y z et h es y n t a xa n ds e m a n t i ck n o w l e d g eo fm a t h e m a t i c a le x p r e s s i o n si sa l s op r o p o s e d t h i sa l g o r i t h mc h e c kt h ee r r o r so fr e c o g n i t i o na c c o r d i n gt ot h ec o n t e n t - f r e eg r a m m a rw i m e x p r e s s i o n sb yt h r o u g hd e f i n i n gt h er u l e so fe x p r e s s i o n sw h i c hc o m p l yw i ll u1 ) g r a m m a r t h er e s u l t so fe x p e r i m e n t so nv a r i o u st y p e so fd o c u m e n t ss h o wt h a tt h em e t h o d sp r o p o s e di n t h i sp a p e rc a na c h i e v eh i g h e ra c c u r a c ya sw e l la sb e t t e ra p p l i c a t i o ne f f i c i e n c y 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 ；s y n t a xa n a l y s i s ； s e m a n t i ca n a l y s i s i i 目录 i ii i l 目录 第1 章引言1 1 1 研究背景和意义。l 1 2 国内外研究现状1 1 3 本文的工作3 第2 章e p 届l j 体数学公式识别系统4 2 1 印刷体数学公式识别系统的功能与组成4 2 2 印刷体数学公式结构分析与理解的关键问题5 第3 章e p 届l j 体数学公式结构分析7 3 1 结构分析方法综述。7 3 2 结构分析预处理9 3 2 1 符号位置特征提取9 3 2 2 空间关系分层1 0 3 3 结构分析方法一1 l 3 3 1 结构分析模型l l 3 3 2 结构分析算法1 3 第4 章e p 届l j 体数学公式语法语义分析15 4 1 数学公式语法理论15 4 2 基于l l ( 1 ) 文法的语法识别算法1 6 4 3 语法识别文法的应用l9 4 4 语法树检错纠错算法2 3 4 4 1 表达式语义特征提取2 3 4 4 2 语法检错纠错算法2 4 4 4 3 语法检错纠错规则2 5 4 5 绝对值符号的语义分析算法3 l 第5 章实验结果分析。3 4 5 1 评价标准。3 4 5 2 试验结果分析3 4 i i 录 5 2 1 引入l l ( 1 ) 语法语义识别算法的结果分析3 4 5 2 2 融入检错纠错规则的语法树遍历算法的结果分析3 5 第6 章结论与展望。3 6 参考文献3 8 攻读硕士学位期间发表论文情况4 l 致谢4 2 第1 章引言 1 1 研究背景和意义 第1 章引言 近年来，随着网络的飞速发展，网络已经成为信息交换与传播的重要手段。数字图 书馆和远程教育等领域也随之成为研究热点。而要推动这些领域的发展，关键就是开发 出一种简单有效的、能将现有的纸质形式的文档转换成相应的电子文档的方法。只有这 样，现在所拥有的大量信息才能够使用计算机进行处理，并使之能够在互联网上传播。 现在文字识别的方法很多，也形成了一些比较成熟的软件，它们对印刷体文字( 包括英 文和汉字) 的识别率较高，对手写体文字的识别率也在逐步提高，但是在处理数学公式 时却显得稍逊一筹。数学表达式构成了大多数科技工程准则的基本部分，由于印刷体数 学公式结构的二维嵌套特性、所包含符号的复杂性及其数学符号语法、语义的多样性， 现有的o c r 技术还不能有效地处理印刷体数学公式，只能将其以图像形式保存，无法 实现对公式的编辑，而且以图像形式保存的公式占用存储空间较大，不利于科技文献的 网上传输。因此，研究印刷体数学公式识别的自动输入技术对于科技文献的数字化，乃 至社会的信息化建设，具有重要的理论意义和良好的应用前景。 本课题来源于河北省科学技术研究与发展计划项目( n o 0 6 2 1 3 5 9 8 ) 。 1 2 国内外研究现状 国外于2 0 世纪6 0 年代后期开始数学公式识别的研究。进入9 0 年代，这个领域的 研究热度逐渐增加【i j 。 早在1 9 6 8 年，a n d e 渤n 【2 】最先采用了自顶向下的分析方法解析数学表达式。该方法 从最终目标出发，将问题分为许多个子目标，直到所有的子目标都达到或都不能满足为 止。这种目标分割策略的提出为数学表达式识别系统做出了巨大贡献。a b d a i d 和j r h a t o n 3 使用自顶向下和自底向上两种方法。在识别出公式各符号后，用自顶向下的方 法将表达式分解成子表达式，而用自底向上的方法将子结构连接成较大的结构。这种方 法只适用于分析一些简单的数学表达式( 如算术表达式和一些三角函数方程) 。随后这 河北大学下学硕士学位论文 种句法解析方法广泛应用于语音识别及图像处理领域。f a u r e j g l w a n g l 4 】提出了一种采用 各图像基元的边界框直接分析各字符位置关系的方法。这种方法仅用边界框决定符号之 间的位置关系是不充分的，有时会出现一些歧义或误判。 进入9 0 年代，这个领域的研究热度逐渐增加，仅第一届到第五届i c d a r ( i n t e r n a t i o n a lc o n f e r e n c eo nd o c u m e n ta n a l y s i sa n dr e c o g n i t i o n ) 大会上就有1 2 篇与数 学公式识别直接相关的文章。d b l o s t e i n 4 】在识别阶段之前设计了水平切分和垂直切分 的预处理方法，提出了基于随机文法的二维文法来解析数学公式，并结合图改写方法检 测公式分析过程中可能出现的语法错误。j f a t m a n 5 】设计了一种典型的系统，该系统 能够成功地将排版好的数学公式转换成“s p 表达式。在符号识别阶段，采用了计算 h a u s d o r f f 距离和符号灰度值等方法；在结构分析阶段，运用了句法解析的方法来分析 二维的数学公式，通过对操作符的分析提取子表达式。o k a m o t o 和m i y a z a w a 6 】使用递 归的投影轮廓切分方法并结合空白域的属性来分析数学公式的结构。w m k d 7 】等人在识 别手写数学表达式时采用了生成图的方法，利用软决策来处理符号关系的模糊性。 二十一世纪以来，随着文档图像处理技术的发展，相关技术得到了充分的研究。在 公式处理方面，又有将近2 0 篇论文发表，但是仍然没有完整的、满足实际需要的产品 出现i s , 9 】。h u a n g 和k e c h a d i t l 0 】提出了基于基准线和属性串文法相结合的方法，处理联机 手写体数学公式结构分析。算法包括结合特征抽取、解析结构树和表达式结构分析三步。 并且采用了m l p ( m u l t i l a y e rp 盯c c p t r o nn c t u r a ln e t w o r k ) 和s v m ( s u p p o r tv e c t o rm a c h i n e s ) 方法分析判断基线中心字符与其他字符关系，得到较好的效果。l i n gz h a n g 】引入了模 糊逻辑理论来处理上下标，结构分析结果有了较好的改善。 国内对数学公式识别的研究尚处于起步阶段，相关资料还很欠缺。主要研究机构有 南开大学机器智能研究所和中科院自动化所。江红英和靳简明【1 2 】提出了基于统计特征的 印刷体数学公式且下标关系判别方法。该方法将字符识别结果与位置信息相结合，很 好的判断出上下标关系。刘昌平和郭育生【1 3 】提出了一种基于多候选方法的数学公式识 别系统。该系统主要包括公式图像预处理，多候选公式符号分割和多候选公式结构分析 三个部分。在公式符号切分中，使用三次动态规划方法对公式图像进行多候选公式符号 切分。在公式结构分析中，采用层次结构分析方法分析数学公式中的矩阵和子表达式，然 后使厍 l a t e x 格式乘l m a t h t y p e 格式表示数学公式的识别结果。哈尔滨工程大学、广西师 第1 章引言 范大学、大连理工大学的研究人员也在关注此类研究，发表了相关的论文f 1 。1 7 1 。 总的看来，数学公式识别是一个新兴而富有挑战性的研究方向。如何超越特定对象， 研究适应我国文献特点的、能够实际应用的公式识别的系统性解决方案，还有很多有待 解决的问题。 1 3 本文的工作 全文的组织结构可以概括如下： 第l 章引言。介绍数学公式识别的研究背景、意义和国内外研究现状。 第2 章印刷体数学公式识别系统。介绍数学公式识别系统的组成，并对结构分析 阶段的关键问题进行讨论。 第3 章印刷体数学公式结构分析。设计了基于d b s c a n 思想的分层方法，针对公 式特点对印刷体数学公式进行结构分析。 第4 章印刷体数学公式语法语义分析。引入l l ( 1 ) 文法，设计了一种数学公式语 法、语义分析方法，定义了符合l l ( 1 ) 文法的表达式构成规则，根据表达式上下文情况 分析判别表达式识别的正确性。另外，结合数学公式的语法规则和语义知识，设计了融 入检错纠错规则的语法树遍历算法，自动纠正字符识别阶段产生的错误。设计了带有回 溯机制的子表达式提取算法，分析含有绝对值符号的公式的语义。 第5 章实验结果分析。对算法改进前后的结构分析方法进行对比，并对实验结果 进行分析。 第6 章结论与展望。对所做的研究工作进行总结，并对今后的研究工作提出建议。 河北大学工学硕十学位论文 第2 章印刷体数学公式识别系统 2 1 印刷体数学公式识别系统的功能与组成 印刷体数学公式识别系统可以完成印刷体文档到电子文档的转变，并实现对印刷体 数学公式的自动识别与理解，最终形成可供用户编辑的电子文件。该系统的输入是经过 扫描得到的包含数学公式的文档图像，输出为识别出来的数学公式的排版语言( 如 l a t e x ) ，印刷体数学公式识别系统流程，如图2 1 所示。 图2 1 印刷体数学公式识别系统 ( 1 ) 数学公式抽取：该模块完成文档中数学公式的定位，以便对数学公式进行单独 处理。抽取工作可以减少公式对其他文本的影响，而且还可以提高数学公式字符识别的 准确率。公式抽取模块主要分为两部分：对独占一行的孤立公式抽取和混杂在文本行中 的内嵌公式抽取。 ( 2 ) 公式符号识别：对数学公式抽取模块得到的公式图像进行符号切分，得到待识 别单个符号的图像：提取符号特征，在分类器中将提取的特征向量与标准字典中的特征 第2 章印刷体数学公式识别系统 比较，得到符号图像所对应的代码，即识别结果。如果识别阶段不但能够给出符号的识 别结果，还能给出符号的字体、风格、字号等更多信息，将为下一步的结构分析带来更 多的便利。 ( 3 ) 公式结构分析：结构分析包括版面分析和语法语义分析，该阶段主要利用符号 的固有属性，如大小、位置和相应的代码信息，结合公式语法、语义特征，确定公式符 号之间空间关系和逻辑关系，并以关系树或分析树表示出来。 ( 4 ) 公式重构：根据字符识别与结构分析的结果，构造出来能够重现公式原貌的通 用格式文件，并设计实现公式编辑器，方便对公式的编改。 2 2 印刷体数学公式结构分析与理解的关键问题 数学公式的意义是通过公式符号来表达的，数学语言是一种非日常和非自然的语 言，其中一部分是被规定或定义的。公式符号有以下特点： ( 1 ) 数学公式包含的符号种类很多，如数字、英文字母、希腊字母以及运算符号， 不同类型的符号在公式中充当着不同的角色，并且随着公式的不同而变化，不容易分 析。 ( 2 ) 公式符号包含的笔画少，结构简单；符号大小不一、相似性高，不易区分。 ( 3 ) 数学公式中有很多约定俗成的规范，同样的符号在不同的位置表示不同的数 学含义。例如：圆点可能表示乘，也可能表示小数点或者噪声点。又如出可用来表示 微分符号或者d 与x 相乘。 ( 4 ) 公式中包含二维嵌套结构，各符号有着不同的组织规则。对于一些含有特殊 符号的公式如，f、e 厂( x ) e x 中积分符号绑定了不同的符号，具有不同的逻辑关系。 ( 5 ) 一些公式字符出现的位置是随机的，需要依赖上下文来分析判断具体的语法与 意义。比如：l i m ，c o s ，l o g 等组合符号，在英文论文中很难把它们同其他英文字符区 分开。 ( 6 ) 有些书籍印刷质量偏差，有污点或者出现字符粘连现象影响识别效果，导致结 构分析的错误。 ( 7 ) 目前对数学公式尚没有规范的排版规则，教科书、报纸、期刊、杂志等不同的 s 河北大学工学硕士学位论文 书籍有不同的公式排版规则，这给过度依赖空间关系的结构分析带来了很大困难。 上述这些特点，影响了对印刷体数学公式的结构分析与理解。这些问题如果得不 到有效地解决，就会使结构分析阶段产生很多错误，并且进一步影响重构结果。 第3 章印刷体数学公式结构分析 第3 章印刷体数学公式结构分析 3 1 结构分析方法综述 现有的数学公式结构分析方法主要有三种f 1 2 】： 第一种是基于几何特征的分析方法。该方法直接根据字符的内容、大小、相对位置 以及字符间的空白域等属性判断相邻字符的关系、生成符号组、合并子表达式，从而达 到分析数学公式的目的。 h a t l 8 1 提出了解决二维表达式的识别与理解系统，算法有三步：首先提取表达式外接 矩形所提供的字符属性信息，根据位置关系对字符进行分解或合并，建立层次结构的表 达式，构造初始表达式树，然后通过通用的语义规则检测初始表达式，最后修订层次结 构，重构初始表达式树。 t w a a k y o n d o 1 9 】提出了自顶向下和自底向上的结构分析策略。使用较大的字符和空白 域水平或者垂直分割表达式，递归的处理每个子表达式的结构，降低了结构分析的复杂 性。 o k a m o t o 2 0 】等采用根据表达式类型进行结构分析的方法。将表达式分为两类：一类 是含有分式、根号、括号或数组的子表达式，另一类是带有上下标或上下部的子表达式。 广 对于第一类的子表达式定义了一些核心符号，如“( ，“- - p “4 ，“【 ，“ ，“i 等， 然后通过查找这些核心符号来分析表达式；对于第二类子表达式则通过查找上下标和上 下部的符号区域来分析表达式。 l e e 和l e e 2 1 】利用传统的统计方法识别单个字符和数字，然后用程序导向方法把二 维结构的数学公式转化为一维的字符串表示。 l e e 和w a n 一2 2 】采用了启发式规则来检测识别错误，规则如下：( 1 ) 任何一个双目 运算符都必须有两个操作数；( 2 ) 数学函数名的纠错规则；( 3 ) 数字没有下标；( 4 ) 在 同一操作数中的符号具有相同的性质。 f u l ( u d a 【2 3 】提出了“数学元件”的概念。数学元件是一组数学符号，它包括一个母字 符和若干子数学元件。根据元件之间的位置关系，计算出每种关系的惩罚值，具有最小 河北大学t 学硕士学位论文 惩罚值的关系被认为是正确的关系。 第二种是基于文法分析的结构分析方法。通过定义文法来分析数学公式的含义。文 法分析的语义识别能力较强，但定义文法是很复杂和困难的。传统的产生式文法虽然可 以描述一维的文本，但是不能很好地表示具有二维结构的数学公式。研究人员采用不同 的方法扩展传统的产生式文法，使其具有表达二维数学公式的能力。 p f e i f f e r t 9 】设计了采用上下文无关文法的分析器，提高了结构分析的独立性，该分析 器仅仅具有理论意义，没有实际结果。 c h a n 和y e u n g t 8 】提出了公式分析中，常伴随发生的4 类错误：词法错误、句法错误、 语义错误和逻辑错误。词法错误主要由于手写或者排版乱引起，这类错误很难纠正。句 法错误主要是指括号不匹配，缺少操作数等。语义错误是指操作数应用于不合适的操作 域、函数名识别错误。逻辑错误类似于i + 2 f f i 5 ，文中没给出相应的解决方法。 d i m i t r i a d i s 冽除了定义句法规则外，还定义了语义规则。句法规则用来将复杂表达 式分解成简单表达式，而语义规则定义了句法规则各部分在坐标空间的相对位置关系。 t 0 删t 【2 5 1 提出了初始化模型来分析自动识别带有公式的文本，并使用树结构表示抽 取出的数学公式。采用算符优先级规则结合递归算法逐级分析复杂的数学公式，简化了 分析的复杂度。 g r b a v e c i 2 6 】采用图改写的方法分析二维数学表达式。图改写方法依据数学表达式操 作码优先级别和操作码作用域的运算规则来分析表达式，并且能够检查出某些不合语法 的公式，比单纯依靠句法和基于结构的分析方法更加有效。图改写方法对分析二维模式 的图形提供了坚实的理论基础和模型。 第三种是几何特征和文法相结合的结构分析方法。p a g a l l o 2 7 】应用约束属性文法分 析，把重要字符作为关键字，然后运用关键字的特性进行分析，避免了回溯，但没有测 试结果。 c h a u d h u r i 和g a r a i n 2 8 】采用符号识别的方法来检测嵌入式表达式，如果存在某个特 殊符号如、f 、等，则说明存在数学表达式，进而使用启发式算法来分析整个表达 式。 综上所述，基于几何特征的分析方法过分依赖符号的排版信息，而基于文法的结构 分析方法则需要利用公式符号识别结果，文法总结困难。将几何特征和文法相结合的方 第3 章印刷体数学公式结构分析 法弥补了两种方法的不足，具有更好的鲁棒性。 3 2 结构分析预处理 在对公式进行结构分析之前，公式符号识别阶段已得到了数学表达式中每个符号的 固有属性，如大小、位置和相应符号的a s c i i 码。而结构分析阶段是要在此基础上分析 得到符号的排列层次，并将其层次结构表示成为结构关系树。 结构分析阶段所需要的符号信息不能完整无误的通过识别阶段得到，因此需要先进 行结构分析预处理。预处理是对识别阶段得到的符号特征进行加工，以适应结构分析的 需要，包括符号位置特征的提取、字符的水平膨胀处理、空间关系的分层。 3 2 1 符号位置特征提取 印刷体数学公式识别阶段提供每个字符的外接矩形的坐标来描述字符属性信息，结 构分析阶段就是利用这些信息来确定相关字符的位置关系。如图3 1 所示。 图3 - 1 符号位置特征定义 其中，( l e f t u p x ，l e f t u p y ) 表示字符外接矩形的左上角坐标， ( r i g h t d o w n x ，r i g h t d o w n y ) 是字符外接矩形的右下角坐标，j i i l 和j 1 2 分别表示两个符号外 接矩形的高。 河北大学下学硕士学位论文 3 2 2 空间关系分层 数学公式具有二维嵌套结构，相邻符号大小和位置的相关性也不明确。为了获得更 多的公式属性信息，便于高效的进行版面分析，采取以下两步预处理： 第一步：对抽取后的公式进行符号水平膨胀处理【2 9 】。设彳为抽取后得到的二值图像 集合，曰为水平动态因子，彳被曰水平膨胀记为么ob ，则水平膨胀后的二值图像为z ， 贝i j zi ( 曰) zn a ) ，且 zlz = a + b ，a a ，6 曰) 。 第二步：利用基于d b s c a n 聚类思想的方法对图像z 进行分层处理，锁定公式中 处于同一水平层次的符号坐标范围。首先引入d b s c a n 算法的数学建模和相关概念【划： 定义3 1 ( 密度) 空间中任意点的密度是以该点为圆心，以e p s 为半径的圆区域内 包含点数目。 定义3 2 ( 邻域) 空间中任意一点的邻域是以该点为中心、以e p s 为半径的圆区域 内包含的点集合，记作n e p s ( p ) = 碍d ，d i s t ( p ，q ) 跏 。这里d 为数据库。 定义3 3 ( 核心点) 空间中某一点的密度如果大于某一给定阈值m i n p t s ，则称该点 为核心点。 定义3 _ 4 ( 直接密度可达到) 点p 从点g 直接密度可达，若它们满足： ( 1 ) p 处于g 的邻域中，即p n e p s ( q ) ； ( 2 ) g 是核心点，即n e p s ( q ) m i n p t s ，即n e p s ( q ) m i n p t s 。 定义3 5 ( 密度可达到) 点p 从点q 密度可达，若( a ，岛，以) ，其中p ，7 ，胁= g ， 且有a 从p s + i 直接密度可达。 定义3 - 6 ( 密度连接) 点p 和点q 是密度连接的，若对任意的0 ，使p 和g 都从0 密度可达。 定义3 7 ( 基于密度的簇) 是基于密度可达性的最大的密度相连对像的集合。 d b s c a n 算法主要反映数据点集的空间分布以及各数据点之间的关系，从而为聚 类操作提供支持和便利。我们基于d b s c n 聚类算法思想，对膨胀后的公式进行密度可 达簇的合并，得到公式的层次信息，使得公式化繁为简。 算法基本思路如下：对给定图像自上而下，从左向右依次扫描，遇到第一个黑色像 1 0 第3 章印刷体数学公式结构分析 素点就设其为核心点( c o r e p o i n t s ) 或种子点，设c o r e p = l ( 如图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 ) 表示。然后依此过程寻找其他的密度可 达簇，最后剩下的不属于任何簇的点即为噪声点。 图3 - 2 种子点八邻域密度可达示例 该算法只需对整个图像数据扫描一遍就可以得到公式各个层次所包含字符的范围， 为下一步分层处理的结构分析方法奠定了基础。算法的计算时间复杂度为n * i o g ( n ) ， 执行效率较高。分层效果如图3 3 所示。 ( a ) 公式图片( b ) 分层效果 图3 3 基于d b s c a n 思想的子表达式范围锁定 3 3 结构分析方法 各类公式空间位置的复杂程度和嵌套方式各不相同，印刷体数学公式结构分析方法 就是要用形式化语言来描述这些公式符号的空间位置关系。首先建立一个结构分析模 型，抽象出符号各属性特征和逻辑关系，结合语义知识完成公式的结构分析。 3 3 1 结构分析模型 结构分析的输入是符号序列，其中每一个符号都有a s c i i 码值和外接矩形坐标信息 河北大学- t 学硕士学位论文 ( t ，e a u p x ，l e f i u p y ，r i g h t d o w n x ，r i g h t d o w n y ) 。经过预处理，每一个符号的信息位扩展 为七位，其v c + + 描述如下： s t r u c ts y m b o l n o d e m 。t c o d e ；符号的码值 i n t c c n t r o i d x ；中心坐标 i n t c e n t r o i d y ； m t l c f t i 俐符号左上角坐标 m 。t i 上f l u p y ； m r r g h t d o w n x ；右下角坐标 m t r i g h t d o w n y ；) ； 结构分析输出的是一个结构关系树( 以下简称语法树) 。语法树中的每一个节点表 示一个符号，除了符号自身的属性信息外，还包括6 个位置指针，分别代表6 种不同的 空间关系，u p 、s u p e r 、f i g h t 、s u b s c 、d o w n 、i n c l u s i o n 分别表示上部、上标、水平、下 标、下部以及包含关系。如图3 4 所示。 、l c r u p x r i g h t d o w n x ji u p j i a u p e r - 一 t n ， t i j l i l l u p1 _ l h r i n c l u s i o n 上 h o d - 。n ：一l j ， j ”5 1 i t l l d t u i r u1 1rd o w n c r n lr f 叮x s u b s c c e n t e r y 图3 _ 4 空间关系语法树 例如公式瓯：= 刀3 通过结果分析后最终生成的语法树如图3 5 所示。 图3 - 5 公式语法树 1 2 第3 章印刷体数学公式结构分析 语法树中节点结构用v c - h - 语言描述如下： s t r u c ts t r u c t u a l t r e e c o d e i n tc o d e ； l n tc o n t r o i d x ； m tc e n t r o i d y 1 。n tl e f i u 峨； l n tl e f i u p y ： l n tr i g h t d o w n x ； m tr i g h t d o w n n s t r u c t u a l t r e e c o d e * u p ： s t r u c t u a l t r e e c o d e s u p e r s c r i p t ； s t m c t u a l t r e e c o d e * r i g h t ； s t m c t u a l t r e e c o d e * i n c l u s i o n ； s t r u c t u a l t r e e c o d e * s u b s c r i p t ： s t r u c t u a l t r e e c o d e * d o w n ； ) ； 3 3 2 结构分析算法 利用以上预处理过程获得的公式字符属性和层次信息，结构分析算法主要分为五个 步骤： ( 1 ) 根据识别阶段获得的公式所有字符的属性，按照l e f t l i p x ( s , ) 升序排列得到数组 a r r a y ) ，结合空间关系分层处理数学公式中各模块所含的字符，把公式化分为各个子 表达式，分别写入数组 a r r a y l ，a r r a y 2 ，a r r a y ) ； ( 2 ) 通过s t r u c t u r a l a n a l y s i s ( ) i 函数处理包含公式最左侧字符的子表达式 a r r a y j ) 中 各字符位置关系，并令其为整个公式的主导子表达式； ( 3 ) 循环调用处理函数s t r u c t u r a l a n a l y s i s 0 处理其余数组中所含字符的位置关系： 根据子公式模块与主导子表达式模块的位置关系进行匹配，组合完成整体结构分析； ( 4 ) 对公式进行空间关系分层处理后存在的不属于任何子表达式的单个字符，采用 最近邻原则对应到已处理字符的五种位置关系指针中，( 除去水平指针) 最终生成公式 结构语法树。 分析过程说明如图3 - 6 所示，首先处理簇一所包含字符的位置关系，作为公式主导 子表达式，然后分析簇二和簇三与主导子表达式的位置关系，进一步组合完成整体结构 1 3 河北大学t 学硕士学位论文 分析。 ( a ) 原扫描图片 嘞水平膨胀处理效果图 ( c ) 分层处理 图3 石公式分层处理过程 第4 章印刷体数学公式语法语义分析 第4 章印刷体数学公式语法语义分析 4 1 数学公式语法理论 数学语言是表达数学思想的专门语言，具有抽象性、准确性、简约性和形式化等特 点，是一种以符号表达为主的特殊语言。具体可分为符号语言，文字语言和图表语言三 类【3 1 1 。符号语言是数学中通用的、特有的简练语言。按照感知规律，数学符号分为三种： 象形符号、缩写符号和约定符号。象形符号是由数学对象的空间位置结构或数量关系经 抽象概括得到的各种数学图形或图式，再经缩小或改造而形成的一类数学符号，如 么，v ，o 上等都是原形压缩改造，属于象形符号。缩写符号是由数学概念的西文词汇缩写 或加以改造而成的符号，比如函数f ( f u n c t i o n ) 、极限l i m ( 1 i m i o 、最大m a x ( m a x i m a l ) 、 存在了( e x i s t ) 、任意v ( a n y ) 、等符号均为此类。约定符号是数学共同体约定的，具 有数学思维合理性、流畅性的数学符号，如运算符号+ 、， 兰( 全等) 、( 约等) 、 ( 大 于) 、 e t ( 1 ) t - o e t ( 2 ) 丁一 占 ( 3 ) e 一 f m ( 4 ) m o f m ( 5 ) f 一 函数名) ( 6 ) m - s ( 7 ) f - ( d ( 8 ) 0 - 操作符) ( 9 ) m 一 字母i 数字) s 1 1 1f am bm d ( ) 上述文法，终结符圪= s ，e ，t ，o ，f ，m ) ，s 代表表达式初始态，e 代表子表达式， r 代表嵌套子表达式，d 代表操作符，f 代表函数名，肘代表字母或者数字；非终结符 杉= o p e r a t e r ，c o m p a r e ，s y m b o l ，n u m b e r ，( ，) ，【，】，l ，= ) ，其中：o p e r a t e r 代表操作符集 合： 土，t - ，+ ，一) ；s y m b o l 代表字符集合： a ，b 名，a ，b z ) ：c o m p a r e 代表逻 河北大学t 学硕十学位论文 辑操作符集合：倦乏，一，= ，兰，弓令；n u m b e r 代表数字集合： 0 ，1 舛。自顶向下，自左向右判别公式语法的方案【蚓如表化所示。 表牝自顶向下判别公式语法的方案 说明检验某一公式字符串在所定义的语境无关语法中是否合法 背景条件1 一部语境无关语法 2 字符串集合 输入 待分析公式所包含的字符串 工作结构当前位置 输入公式字符串某一符号，初 始时为l 由句法范畴所组成的字符串， 规则串 初始时由本文法起始符号这一 单个字符号组成，即s 算法步骤重复做： 规则串的第一符号是 1 一个终结符，或者 2 一个语法范畴 则 如此符号与当前位置的字符串相匹配，则将规则串的第一字 符消去 如当前位置为输入数学表达式字符串的最终符号， 如规则串为空，则成功：否则，失败。 否则，做 在语法的规则中选择任一其左端为此符号的规则，并构造 余串。 余串由下列两部分组成 1 所选定规则的右端： 2 前一规则串消去第一字符号所剩下的子字符串 中止条件 如果余串为空，而当前位置尚未达到最后，则失败。 设输入的、待识别词串为t ，其当前位置用n 表示，t ( n ) 即为待识别公式字符串中 当前正在加工的字符，公式字符串的长度约定为m a x n 。当自顶向下操作时，规则串一 第4 章印刷体数学公式语法语义分析 般用r ，表示；并以r ，( 1 ) 表示规则串的第一个字符，而r 表示规则串中消去r ，( 1 ) 后 所得的词串。数学公式语法识别的规则集合l 净 r 。，r ：，r 。) 表示，一个规则r 的左、 右两端则分别用l ( r ) 、r ( r ) 来表示。如规则r ，为规则集合中的一条，则用r ，r 来表 示。空字符用占表示，撑分析栈判空标志。语法分析流程f 3 4 】如图4 1 所示。 图4 1 公式语法判别流程图 4 3 语法识别文法的应用 1 合法公式应用举例 检验公式i n a * l n ( 1 n a ) ，分析步骤如下： 河北大学工学硕十学位论文 ( 1 ) 文法g ( s ) - ( o ) s 凹 ( 1 ) 卜 r ( 2 ) n s ( 3 ) e - e m ( 4 ) m 一 洲 ( 5 ) f 一 i n ( 6 ) m g ( 7 ) ，- ( d ( 8 )