（模式识别与智能系统专业论文）数学公式识别.pdf

独创性声明 本人声明所成交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确地说明并表示了谢意。 铭蛊一沈 e l 期签名： 丝兰 期 矿6 ，二易 关于论文使用授权的说明 本人完全了解中国科学院自动化研究所有关保留、使用学位论文的规定，即： 中国科学院自动化研究所有权保留送交论文的复印件，允许论文被查阅和借阅： 可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 虢重丝导师签名 同期 妒、易y 第一章绪论 第一章绪论 1 1 结构( 句法) 模式识别 模式识别诞生于2 0 世纪2 0 年代，随着4 0 年代计算机的出现，5 0 年代人 工智能的兴起，模式识别在6 0 年代初迅速发展成一门学科。用来解决模式识别 问题的许多方法，可以一般地概括成两大类：决策理论( 统计方法) 和句法( 结 构) 方法 1 。按照决策理论方法，是要从模式中抽取组特性的测量值( 特征) ， 并常以划分特征空间的办法来识别每一个模式( 将其指定到某个模式类) 。模式 识别在以往几十年饷研究发展，大部分是有关统计方法及其应用。而在一些模 式识别问题中，描述模式的结构信息却具有重要的意义，其识别过程不仅要能 够把模式指定到一个特定类别( 分类) ，而且还要描述那些使模式不致于给误指 到其他类别的特性。这类识别问题的典型例子是图片识别，或者更一般地说， 是景物的分析。如图l l 所示，a 中图片可用b 中的多级结构描述，这之中既 包括子模式a 、b 、c 、d 、e 的分类，也包括对子模式之间的关系的描述。 ( a ) 套心 墙面y 方凳a 桌子b圆凳c 相片d 图画e ( b ) 图卜1 结构模式识别示例 在这类问题中，所研究的模式通常是十分复杂的，需要的特征也很多。所 以，用一些比较简单的子模式组成多级结构来描述一个复杂的模式，就成为非 常具有吸引力的一种想法。此外，假如模式很复杂，而可能有的描述又很多， 对于这种情况，要想把每一种描述都定义为一个类别，就很不实际了。由此可 一 数学公式识别 见，识别的任务并不只是简单的分类，而只有对每个子模式作进一步的描述才 能满足识别的要求，最终的结果也通过一种说明性的语言去描述。 1 1 1 句法模式识别系统组成 一个句法模式识别系统通常包括四个主要部分：即预处理、分割、基元( 及 其关系) 识别和句法分析。系统的一个简单框图如图卜2 所示。 图卜2 句法模式识别系统的框图 述 预处理部分的功能包括以下两个部分：( 1 ) 模式的编码与近似；( 2 ) 过滤、 复原及增强。对于一个输入模式，我们可以首先进行编码，或者以某种方便的 形式加以近似，以便于做更进一步的处理。例如：一个波形可以用它的时间采 样，或傅氏级数展开的前几个有限项来加以近似；一张黑白图片，可以借助0 和l 的网格或一个矩阵来编码( 这就是二值图像的存储格式) 。为使系统以下各 级处理起来更加方便，在这一级往往要采用某种类型的“数据压缩”，这样既可 以减少时间和空间的开销，通过适当的规则又能去除一些无关信息，降低分类 的难度。可以采用过滤、复原以及增强技巧来消除噪声，使缺损复原，以及改 善编码化的模式质量。于是，在预处理部分的输出端，大体可以获得具有合理 的“好的质量”的模式。然后，每一个经过预处理的模式可以用类似语言那样 的结构来表达( 例如一条链) 。 模式表达的过程主要由两部分组成：( 1 ) 模式分割；( 2 ) 基元( 及关系) 识 别。为了借助一个模式的子模式来表示它我们必须分割该模式，并同时辨认 ( 识别) 模式中的基元和关系。换句话说，要以预定的句法或组合运算为基础， 把每一个经过预处理的模式分割为子模式和模式基元，然后再以一组给定的模 第一章绪论 式基元来辨认每一个子模式。在这里，要按指定的句法运算用一组基元来表达 每个模式。例如，通过连接运算，每个模式可表示为基元的一条链( 连接起来 的基元) 。关于表达式及模式在句法上的决策是否正确( 即是否属于由给定的句 法或文法描述的模式类) 的判断，将由“句法分析程序”或“剖析程序”来进 行。在进行句法分析或剖析时，分析程序通常可以用一个剖析或者剖析树的形 式，产生出模式的一个完整的句法描述表明模式在句法上是正确的。另外，模 式或是被拒识，或者是在其他给定的文法基础上得到分析，这里所述的其他文 法，指的是描述考虑之中的其他模式。需要指出的是，模式分割要在所采用的 文法的指导下进行，这样才能使得这两部分有机的结合起来。 要用一个文法来描述所研究的模式类的结构信息，就需要有一个机器，能 根据一个类似语言的表达的模式训练集合把文法推断出来。这个机器的功能类 似于在统计模式识别系统中的“学习”过程。待研究的模式类，是根据该模式 类中的实际样本，通过学习而得到的结构描述。学习得到的描述具有文法的形 式，随后即用于模式描述和句法分析。一种更广泛形式的学习，则可以学习到 有关模式类的最好的基元集合及其结构的描述 2 。 1 1 2 关于句法方法和统计方法的比较 应该说，统计模式识别在近几十年里发展非常迅速，取得很多研究成果。 另一方面，句法方法用于某些方面也得到成功的结果，如字符识别、染色体分 析、泡室图片鉴别、自动检查、二维的数学表达式的识别。然而，把句法分析 和统计分析分为两个分支，这只能说从理论研究的观点看起来是方便的。换句 话说，两种方法有时候并不能分得那么清楚，特别是在实际应用中。许多预处 理和分割的技巧在两种方法中都有用，显而易见的是，因为对于特定的预处理 和分割的技巧的选择，目前主要是取决于所研究的模式类型( 图像或波形，高 噪声的，衰减与否，等等) ，而较少取决于用什么识别方法。统计方法中的特征 选择问题和句法方法中的基元选择问题，性质是相同的，唯一的区别是，句法 方法中的基元表示子模式，而统计方法中的特征可以是从模式中提取出来的某 种数据测量值的的集合。事实上两种方法之间在这一级上看来并没有什么区别， 数学公式识别 因为在选择基元时，本来就不希望基元包 息。例如，在识别二维结构的数学表达式 是字符和数学符号。比较恰当的处理使用 法来识别数学表达式。模式基元的识别， 得到更好的识别结果。 含那些对识别问题具有意义的结构信 时，主要用的是句法方法，模式基元 统计的方法来识别基元，而用句法方 可以用统计的方法更为有效的完成 从前面的讨论可以看出，对于实际的模式识别问题，句法方法与统计方法 在很多情况下是可以相互补充的。如果认为有关模式的明显的结构信息并不重 要，识别问题主要是分类，而不是分类和描述，那么，实际上没有必要采用句 法方法。另一方面，如果模式的结构信息非常丰富，而且识别问题要求分类及 描述，那么采用句法方法就有必要。在模式识别的许多应用中，问题的实质往 往是出于这两种极端情况之间。换句话说，有关模式的有一些类型的结构信息 是重要的，应该利用，但是简单的和概括的模式基元可能不容易提取，特别是 对有噪声和畸变的模式。因为一般来说，模式基元或多或少要用一个模式的局 部特征来定义( 这对于噪声和畸变是敏感的) 且包含较少的句法信息，他们或 许能够更有效地用统计方法来识别。在模式基元被抽取出来以后，可以用句法 方法对整个模式进行识别。这些方法结合起来适当利用，其结果就可能是行之 有效的系统。在较低的级( 指模式的分级结构) ，可用统计方法来识别模式基元。 基于此原则，对于一个给定的识别问题，选定模式基元可以定义为能够用统计 方法来识别的子模式。然后高级模式结构信息将用这些子模式来表示。在这种 情况( 一个二级结构) 下，只要基元可以被识别，并不要求它非常简单和概括。 这样一来，所得到的句法描述可以变得十分简单，识别问题可以有效地利用句 法方法加以解决。 1 2 自动文档处理和录入的发展概况 众所周知，人类的许多知识都是从文档中获得的【2 ，比如书籍，报刊，杂 志，信件，技术报告，政府文件，票据等。这些知识都是以纸张的方式保存在 大小各异的文件箱里面。在信息化的年代里，我们需要将这些知识转变成计算 机能处理甚至理解的电子信息。手工处理的方法已经无法对付这些浩如烟海的 信息，并且简单的手工方法也制约了这些信息的广泛应用，可以说这就是信息 4 第一章绪论 系统的瓶颈【3 】。随着电子技术和计算机技术的发展，从文档中自动获取知识很 早就成为了自动化领域中一个热门的研究方向。 自动文档处理的对象是对扫描的光学图象进行处理，光学字符识别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 。o c r 的研究很早就进入了商业领域，最 早的商业o c r 系统在早在1 9 5 5 年就出现了，只是这个时期的o c r 还只能识别印 刷体字符。到了6 0 年代和7 0 年代，人们在基于光学文字识别( o c r ) 的文档处 理的基础上开始了很多研究工作。由于o c r 商业上的美好前景，很多商家都开 始投资开发o c r 软件，商业市场上开始出现了很多专用的识别软件和相关产品， 在美国市场上曾一度出现过5 0 个o c r 生产厂家并存的局面 4 。由于技术和硬 件的限制，这个时候的o c r 软件还比较简单，尽管有些识别系统可以设定输入 文档的格式，这个时期的o c r 还不能处理复杂格式文档和自由格式文档，例如 t 图文混排，表格，工程图纸等。然而，从7 0 年代开始，人们开始真正认识到 o c r 的巨大市场和研究价值，o c r 的研究方向迅速扩大到手写和各种类型的文档 的识别，比如信函的分类识别。并且这时候文字识别也不再只限于英文和西方 语言的识别，如同文、中文、韩文、阿拉伯文字的识别研究和各种语言混排的 研究也迅速开展起来 61 0 。 到了8 0 年代，大型商业o c r 软件已经曰渐成熟。并且随着个人微机开始普 及，适用于个人微机的o c r 系统也开始出现。o c r 软件也开始小型化，也更加 实用化。这时候单个字的识别研究可以说已经很彻底了，文字的识别率也有了 很大的提高。文字识别的应用方向几乎是无所不包：普通文档，表格 1 1 ，票 据 1 2 ，名片 1 3 ，车牌 1 4 ，身份证 1 5 ，都成了文档识别的研究对象，这些 研究在办公自动化、公安系统、文献情报的计算机化管理、商业和金融业中都 得到了非常广泛的应用。 这个期间，每年的文档分析和识别国际会议( i n t e r n a t i o n a lc o n f e r e n c e s o 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 ( i c d a r ) ) 都会发表几百篇相关论文 1 6 。这段时期文档识别的研究可以说达到了一个全新的高度。 数学公式识别 1 3 数学公式识别的研究 在人机交互时，人类与计算机所处理的对象在许多方面是不同的。人类使 用可视化的语言要比使用串式语言更便捷。例如：用户使用数学符号在二维空 间描述一个复杂的数学表达式要比使用如l a t e x 或者m a p l e 的串式语言要容易 得多，正因如此，在音乐、建筑以及工程等学科中都使用图表形式的可视化语 言来传递信息 4 4 。 通常，一种可视化语言是由一系列符合该语言的句法和语法的表达式组成， 而表达式又由一串字符以二维或三维方式分布组合而成。可视化语言与串式语 言的基本区别在于前者以高维分布，而串式语言是一维分布，因此，对可视化 语言的理解需要理解表达式中终结符与非终结符之间的空间关系，进而理解表 达式的含义。 目前，对可视化语言的研究在于设计和发展一种可编程的可视化语言，包 括各种语言之间的编译，使用可视化编译器能把可视化语言图表转化成一种计 算机可接受的形式，例如电子表格就是最普通、最成功的可视化编程语言的数 据形式。 一些可视化语言，如音乐符号、数学符号、工程图，没有严格的定义，有 方言的差异，我们称之为自然可视化语言。没有具体的规范，这就增加了分析 的难度。 对数学公式而言，有方言差异，例如：西方的阅读顺序是从左至右，而阿 拉伯的习惯是从右至左，方言使得句法和语法定义都复杂化了，使符号的解释 变得多样化：数学符号多种多样，它包括算术、微积分学、逻辑、和一些其他 数学学科中的符号；数学符号的意义多种多样，相同的数学符号可以表达不同 的语义信息。因而，数学中的习惯也分为两类，一种是比较规范的习惯，如从 左至右的解释方向；一种是比较灵活的习惯，如公式的布局模式。 对任何自然可视化语言，由于缺乏正式的定义( 规范) ，不可能产生完全 准确的规则列表，很大程度上依赖于观察和反复推敲才能得出准确含义，因而 需要对语言习惯进行表示以便于更好的理解。 对于数学公式，符号的结构描述可以参考排板的模式、数学符号的历史和 数学的历史，遗憾的是，c a j o r i 对符号的研究仅集中在字符的演化历史，而不 第一章绪论 是字符之间的空间关系的使用。 计算机接受串式语言，它对自然可视化语言的理解必然涉及到语言的识别、 翻译，将自然可视化语言转化为串式语言，这使得我们必然使用编译技术来进 行，这也提供了一个全新的研究领域。 数学公式的识别可以分为两个阶段：字符的识别和结构分析，这也开辟了 两个研究领域，这两个方面的研究已经有几十年的历史，在下面分别进行介绍。 1 3 1 字符的识别 字符识别发展的历史近3 0 年，目前，一些比较成熟的字符识别技术已能得 到满意的结果，但是它们大都是建立在分离字符的基础上，而数学公式是由多 字符排列在一起组成的，因而分割表达式就变得非常重要。一种原始的分割方 法就是把表达式中的所有成分分离开来，一些字符如”i j ，和”j ”是由多个成 分组成，所以分割完以后不得不进行合并，还有一些字符，如根号，它与别的 字符形成包围结构，因而需要特殊处理。下面是公式识别发展过程中所出现的 一些分析方法： o k a m o t o 等人 2 3 ，2 4 提出了印刷体公式的分割方法，通过垂直和水平方向 的递归投影，通过加一些检验步骤来处理特殊情况。这种方法能解决比较简单 的公式布局的分割问题，但对于复杂的结构几乎失效。 f a u r e 和w a n g 2 0 提出一种分割手写体公式的模块化系统，它有两个分割 模块：数据驱动分割模块和知识驱动模块。数据驱动分割模块对表达式建立一 棵关系树，通常，x 轴和y 轴投影可以用来决定分割点，对于根号和分式中的 分数线，在投影前就进行特殊处理，把它们提取出来，然后投影分割；知识驱 动模块通过合并块( 如“i ”，”j ”和”= ”) 更正关系树。 s m i t h i e s 2 5 提出一种分割算法，它产生许多种可能的分割，然后进行识 别，然后选择可信度高的分割，这种方法的缺点在于会产生分割错误，需要人 为更正，但他处理了前面两种方法所不能解决的问题，如印刷体和手写体中都 会出现的粘连情况使两个字符不能分割开( 原因是如果强行把粘连处分丌，有 些字符也会被分开，如：m ，n ) ，这种分割方法常用于联机手写识别中。 总之，对于具有二维结构的数学公式，一个好的分割算法非常重要，才能 f 确而高效的分割出字符用于字符识别。 数学公式识别 对分割后的字符的识别，目前已有很多好的算法可以采用，如模板匹配、 近邻法分类、神经网络等方法，在此不再具体介绍。 1 3 ，2 结构分析 在字符识别以后。可以得到一个字符列表和与之相关的属性，如位置、尺 寸、字符的身份，结构分析的任务是把它们转化为串式语言形式，以分析树或 其它形式表示出来。下面是结构分析方面的一些解决方案： 在进行结构分析之前，有必要作一些预处理，有利于结构分析的进行。在 数学公式分割识别后，公式中存在空间操作码，必须首先找出空间操作码，否 则不能得到正确的公式的含义。f a u r e 和w a n g 2 0 提出一种方法可以自动标记 空间操作码，它使用字符的边框( 位置) 信息，在字符身份确定以前做一些调 整来得到，它的缺点也在此，就是字符身份也可能隐含有空间操作符，如两个 变量的隐式乘法( 不带乘号) ，有时隐含的空间操作符很复杂，需要考虑前后上 下文的信息才能决定。 以下是对结构分析的研究成果，他们是在假定字符识别都正确的情况下进 行的。在结构分析时，a n d e r s o n 1 7 ，1 9 完全采用自上而下的分析方法，以句法 为标准来分割识别问题，但这个算法对公式识别并不是完全有效，因而不能得 到好的识别结果，但他开创了使用句法分析的模式，句法分析的方法也是经典 的模式识别方法。 c h a n g 1 8 提出结构说明方案的方法来进行公式结构分析，这个算法主要利 用操作码的优先级和它的操作数的范围。算法由两步组成：对操作码进行分组 和建立结构树，这个算法考虑到了效率，但只能运用于表达式的结构由操作码 构成的模式，而且，他的算法描述很冗长，难于理解和实现。 p a g a l l o 3 3 ，3 9 应用约束属性文法分析，先标记公式中的重要字符作为关 键字，然后运用关键字的特性进行分析，避免了回溯，但也没有测试结果。其 思想跟c h a n g 1 8 很相似，是一种改进。 l a v i r o t t e 和p o t t i e r 3 5 。3 8 采用了上下文相关文法，对关键字对分析， 加入上下文信息，使得分析更有效，但对字符位置有严格的条件限制，而且它 的适用范围也比较窄。 f a u r e 和w a n g 2 0 采用模块化系统，把一个公式分割成结构比较简单的几 第一章绪论 个部分，分别分析。这种方法用于结构分析中的一个特点是：如果表达式中的 某个字符不能被识别，结构分析仍然可以进行。 p f e i f f e r 2 6 设计的分析器采用了上下文无关文法，提高了结构分析的独 立性和适应性，但是仅仅是讨论，并没有实际的结果。 g r b a v e c 和b l o s t e i n 3 1 使用图来表示公式的结构，通过对图中的节点的 关系进行分析，然后对图的结构进行转换得到公式的结构描述( 图的形式) 。而 且，系统还使用了符号化习惯的知识，例如操作码优先级和操作码的范围，用 来消除算法回溯。这种方法集中了以上的几种理论上的研究成果，并进行了实 现，朝实际应用的方向迈进了一大步。 在公式的分割中，往往会出现过切分问题，必须在结构分析中进行补充， t w a a k y o n d o 和o k a m o t o 3 2 提出一种方法在结构分析中解决过切分问题，采用 两个策略：一个是采用自下而上的方法分析子表达式的局部结构，另一个是自 上而下分析整个公式的整体结构。 z a n i b b i 和b l o s t e i n 2 9 采用了基准线的分析方法来进行结构分析，构建 一棵b s t ( b a s e l i n es t r u c t u r et r e e ) ，得到结构描述，它的优点在于克服了各 种方言的限制，分步的方法使得结构清晰，由于它不能处理表格式结构的公式， 所以，j a m e sr c o r d y 4 7 在后面进行了补充。 由于上面所提出的方案都是在假定字符识别完全正确的情况下进行的，所 以没有进行错误校正，他们共有的缺点在于整体效果不会特别理想。 另外，还有一些研究分别着重于联机公式识别和脱机公式识别，由于篇幅 有限，在此不再一一列举，总之，对于公式识别的研究已经开始发展起来，但 在国内研究才刚刚开始起步，由于课题本身的难度很大，所以需要一段时间的 研究才能有所突破，达到可以完全适用化的效果。 9 第_ _ _ _ = 章数学公式识别系统的构成 第二章数学公式识别系统的构成 2 1 系统一般框架 数学公式识别系统包括两个模块：字符识别和结构分析。一个完整的数学 公式识别系统可细分为六步：a 、预处理：去除噪声，倾斜校正：b 、字符分割： c 、字符识别；d 、字符空间关系确定：e 、逻辑关系确定；f 、公式含义的建立， 如图2 l 所示。在本中我们只研究前四步，也就是说，只完成公式的空间关系 的建立任务。 系统输入 字符识别 联机手写公式或 脱机扫描公式 撬纛正爿竺! 吲竿!去噪、倾斜校正1 一t r 一 结构分析：l 公式含义的建立 系统输出 逻辑关系 的确定 结构分析预 处理模块 字符空间关 系的确定 属性字符串 注：联机手写公式输入接1 3 模式e 3 0 ( 如l a t e x ) l 图2l 数学公式识别过程 2 2 手写体公式识别系统构成 个实用的手写体公式识别系统的构成主要包括用户输入、识别核心和系 数学公式识别 统输出三个部分，如图2 2 所示。通过手写板或其他手写输入工具输入数学公 式到系统，系统完成两个模块的功能：分割公式图像成单一公式字符，然后调 用字符识别模块，返回1 6 个候选给用户，由用户选择，如首选正确，可不做选 择，记录用户选择的结果，即为字符识别结果，同时记录该字符在公式中的位 置，即边框坐标：调用结构分析模块对识别结果和边框坐标进行结构分析，并 通过结构复原模块将分析结果输出到l a t e x 。结构分析包括两步：一次分析得 到初步分析结果，对分析结果进行判定调用二次分析模块对漏识和误识两种情 况加以更正得到最终分析结果。 输入手写公式 公式分割 l 公式字符识别li 字符边框分析l ； 字符识别 !iil ； 结构分析预处理( 公式属性分析) iii 第一次结构分析 b s t 结构分析b s t 结构分析 第二次结构： “：i j j t二灯砖 关键字结构分析关键字结构分析 结构分析 入f f 字符无拒识，岁 i 7 l 0 ， b s t 结构树 h 结构复原 属性( l a t e x ) 字符串r 图2 2 手写体数学公式的结构分析与复原 1 2 第一章数学公式识别系统的构成 2 3 印刷体公式识别系统构成 印刷体公式识别系统主要用于o c r 产品中，作为一个附加功能嵌入到系统 中，完成对文档中的公式块的自动处理与结构复原。系统的输入是：带有数学 公式块的扫描文档图像：系统的输出是：经过分析复原的公式文本，如图2 3 所示。具体的识别过程如下： 由扫描仪扫描的图像经过二值化后，通过版面分析模块分离出公式块进行 分析；对公式块进行一次分割算法，即连通域分析和投影分割，然后经过识别 并分析其识别结果来修正分割结果，最终得到字符块和字符的边框信息；识别 字符模块得到字符的i d e n t i t y ，并纪录边框信息完成字符识别模块功能。字 符识别模块提供给结构分析模块的信息( 字符身份和边框信息) 经过排序即得到 结构分析的输入，通过调用结构分析算法，即b s t 结拘分析算法和基于关键字 ( 括号匹配) 的分析算法的集成分析算法，得到一棵b s t 结构树，实现结构分析 模块功能。通过对b s t 树的遍历即得到属性字符串( l a t e x ) ，完成结构复原功 能。最终实现二维语言向一维语言的转化。 数学公式识别 图2 3 印刷体数学公式的结构分析与复原 4 符 第三章数学公式的切分与字符识别 第三章数学公式的切分与字符识别 3 1 数学公式的分割 数学公式识别的两个应用，即印刷体数学公式识别和手写体公式识别。手 写体公式识别是通过联机信息( 如起笔和抬笔) 来分割公式，相对信息较多， 也比较容易处理。所以在这里我们主要针对印刷体公式的分割进行处理。常用 的字符分割方法很多，如投影分割、连通域分析、基于特征的分类等方法。由 于数学公式的二维分布，我们的分割方法采用多种方法集成，分级进行分割。 如图3 1 所示：t 3 1 1 预处理 图3 一l 印刷体公式分割方案 由于数学公式的字符中存在大量的点号，所以在预处理中去除噪声要特别 谨慎，在这里没有进行这步处理。 在分割中要进行投影，所以必须进行倾斜校正。采用h o u g h 变换 4 8 ，包 括以下三个基本步骤： 几何空涮的每个待处理像素转换成参数空间的参数直线； 在参数空间设置一累加阵列并初始化，每个待处理像素对阵列中处于其 数学公式识别 参数直线上的单元加1 ； 从阵列中选出最大的单元，其对应的参数所决定的直线就是我们在几何 空间上要寻找的直线。然后通过该直线的倾斜角进行反向旋转得到。 3 1 2 连通域分析 连通域分析一般用于版面分析，提取比较大的字符块，用于分割识别。在 这里采用这种算法进行初步字符分割。 连通算法是指从原始图像、图像的线连接图或其他描述方式创建图像的连 通域的过程 4 9 。连通域分析一般采用8 连通，如图3 2 所示： 1 87 206 345 图3 28 连通 考察。点，它和1 、2 、3 、4 、5 、6 、7 、8 点是连通的，其余的点都不连通。 基本算法可参考 4 9 。 快速算法：上面算法在扫描时需要不停的取图像像素点的值，对于二值图 像来说，内存中每个字节存8 个像素点，在取像素点的数值时，必须进行与或 运算，很费时间，因而文 6 提出面向字节的块速算法：对每个字节的2 5 6 种可 能建立游程索引，求游程时，每次读取一个字节。进一步简化运算，假定在每 一行上，相隔一个到三个白点的黑点都是连通的，这样每个字节最多属于两段 游程。以上两种简化大大提高了运算速度( 这样会出现粘连，只适合版面分析) 。 公式图像经过连通域分析，可以使大多数的字符块分割正确。原始算法使 得有些本身不粘连的字符不能分割开，可以通过对原始图像进行横向延伸，使 得原本小的距离放大，得到较为彻底的分割结果，但具有多结构的字符也被分 成几块。连通域的分析结果如图3 3 所示。 、 1 6 第三章数学公式的切分与字符识别 i 圊翻凰凹叩霪 iv 圈 田 图3 - 3 连通域分析a 囵凰 经过连通域分析，每个独立的连通区域都被分割出来，得到一种过分割结 果。但是，只要字符之间有粘连，连通域分析就会失败( 如图3 4 ) 。通过以下 方案解决，我们建立了较完备的公式字符集( 见3 2 ) ，通过一个两类分类器， 可以判定连通区域是否粘连，不粘连的区域被f 确识别，而粘连区域被拒识( 或 被识别成一个特殊类) 。被判定粘连的区域被送到下一个模块( 投影分割) 继续 分割。 昭曩蝴盏 3 1 3 投影分割 图3 4 连通域分析b 投影方式有两种：一种是像素投影，一种是轮廓投影。对数学公式采用递 归像素投影，把扫描图像投影到x 和y 轴上，垂直投影得到子表达式，然后水 平投影得到基准线，再递归投影。投影分割的缺点在于它不能得到上标、下标、 矩阵、求和表达式和根号，这些符号要进行特殊处理，这也是先采用连通域分 割的原因。考虑到连通域分析以后大部分粘连的情形都是上下标的情况，为了 能得到更准确的分割点( 即分割闽值) ，所以在投影时，采用连续两个像素求 数学公式识别 “与”，然后投影( 即连续两个黑点才能被认为是黑点) ，得到投影图，设定阈 值，分割得到结果。如图3 5 所示。 圃虱月嘲盏 3 1 4 字符合并 图3 - 5 投影分割 公式图像经过以上两步的分割，得到一种公式的过分割结果，即多结构字 符( i 、j 、= 等) ，被分成多个小块，所以必须进行字符块的合并。具体 方法是采用位置信息和合并规则进行判断和并，即通过对以上分割结果字符块 进行识别，然后根据规则在其邻域来搜索可能出现的其他部分，合并矩形外框， 并修改其边框信息。如图3 6 所示。 圃虱翔蝴盏 图3 - 6 字符合并 第三章数学公式的切分与字符识别 3 2 数学公式字符识别 目前，一些比较成熟的字符识别技术已能得到满意的结果，但是把它们用 于数学公式的字符识别，识别率一般会有所下降。主要原因有二：一是对多成 分字符，如“i ”和“j ”，分割完以后不得不进行合并；二是字符形成包围结 构( 根号) 以及长的分数线等大字符，需要特殊处理。对于数学公式符号这样 一个新的识别对象我们做了以下两个方面的工作。 3 2 1 数学公式字符集 为了建立比较完备的数学公式字符集，我们参考了o f f i c ex p 的公式编辑 器以及l a t e x 中的公式符号集。建立的字符集分别为：印刷体公式符号2 6 0 个， 由以上的过分割方法，在识别时只需要识别其中的一部分，然后通过合并规则 进行合并，所以只选择多结构字符的部件加入到字符集中；手写体公式符号和 词组3 0 6 个，考虑手写数学公式时用户经常连笔的情况，把一些常用的可能连 笔的词组加入到手写公式符号字典中。训练样本集数量为：印刷体样本1 0 0 0 0 0 个，1 5 0 0 个类；( 联机、脱机) 手写体样本5 0 0 0 0 个，1 4 0 0 个类；测试样本集 数量为：印刷体样本6 0 0 0 0 个，2 6 0 个类；( 联机、脱机) 手写体样本2 5 0 0 0 个， 3 0 6 个类： 3 2 2 识别算法 本文所采用的识别核心算法均为汉王已有的技术，通过对以上的字符集进 行训练和后处理，得到三套识别核心。为了提高手写公式符号的识别率，我们 建立了脱机手写识别核心，即采用脱机特征对手写体公式符号进行分类。印刷 体识别核心的识别率为9 92 6 ；联机手写体公式识别核心识别率为9 8 7 3 ：脱 机手写体公式识别核心识别率为9 8 4 2 。 在手写体公式识别系统中采用的识别核心集成联机手写识别核心和脱机手 写识别核心两个分类器，进一步提高识别率，如下图3 7 所示。在分类器集成 时，我们采用计算每个候选的置信度( 见公式3 1 ) ，两个分类器中相同候选置 1 9 数学公式识别 信度累加，然后根据置信度对2 n 个候选进行排序，取前n 候选作为输出( 识别 结果) 。 置信度1 ，：毒生l z d , j = l 手写输入 ( 3 1 ) 图3 7 分类器集成 总之，经过对数学公式的切分和识别，我们得到两方面的信息，提供给结 构分析模块，即：每个字符的边框信息和字符的身份( 字符识别结果) 。边框信 息在分割模块中得到，字符的身份通过字符识别模块得到。 第四章数学公式的结构分析与复原 第四章数学公式的结构分析和复原 结构分析是本文的主要工作。在字符识别阶段我们得到了公式的的各个字 符的位置信息和身份，通过结构分析预处理可以消除一些不利于结构分析的信 息，也可以得到结构分析所必需的附加属性，便于结构分析的进行。目前的 些结构分析算法都有其局限性，通过改进和多种方法的集成，改进结构分析性 能。结构分析模块的主要功能如图4 1 所示： 系统的输入是：一串字符( 字符身份表示) 和它们的空间位置 系统的输出是：以l a t e x 或操作树 4 5 的形式输出( 我们的最后结果是p s 或d v i 文件) 。 ( a ) 数学公式 0 ) 基准线结：姆科( b a s e l i n es t r u c t w et r e e ) 4 1 结构分析预处理 图4 - j 结构分析过程 为了结构分析的方便，我们在系统中加入了结构分析预处理模块 5 0 。在 这个模块中，我们要实现两个功能：一个是函数型字符的合并，空间操作码的 处理和一些常见语法错误的校正等：另一个是结构属性的提取，得到结构分析 所必需的附加属性。 坐 珑 n 斟 l n l | 一u 数学公式识别 4 1 1 语义信息预处理 语义信息的提取与应用对结构分析既会产生积极的作用，也可能会影响结 构分析，从而得不到正确的结果。因此要做一些预处理，主要有以下几个方面： 函数型字符的合并。如三角函数、数值函数( 绝对值a b s 0 ) 、逻辑符号( i f ， o r ，a n d ，m i n ，m a x ) 等字符，把这些字符合并以后并修改字符属性，字符身份 从语义上更明确，使得结构分析更容易进行，在手写体公式识别系统中，识别 核心加入一些常用的词组在字典中也能起到函数型字符的合并功能。在印刷体 公式中尤其重要，如图4 2 中的“m i n ”的提取：如果不进行合并，单纯的结构 分析会使得下部的符号“l ”被遗漏( 因为普通字符是没有b l e f t 域的) ，得不 到正确的分析结果，从而使分析失败。 墨1 m 始m ( 图4 - 2 印刷体公式样本 一1 ) 空问操作码( 如图43 所示) 的处理主要是找出空间操作码，根据相邻两符 号的身份和位置关系来判断，一旦发现空间操作码，可以通过加入一个确定的 操作符，这样有利于公式逻辑结构的建立和公式含义的理解。 c = a b 图4 - 3 印刷体公式样本 一些常见的错误如缺少一个匹配字符、操作码的误识等。如缺少个匹配 字符，可以加入一个替代符，使结构分析能够顺利进行；操作码的误识可以通 过前后字符的关系来判断，如果能判断操作码字符的真实身份，则正确修改之， 如不能，则加入一个标志符来代替。 。 第四章数学公式的结构分析与复原 4 1 2 结构信息预处理 结构分析的输入为：一串已排序的字符串( i d e n t i t y ) 和它们的空间位置( 用 字符块的边框表示) 。结构信息预处理的任务就是从以上两种输入中提取出以下 两类属性，一是输入属性：包括字符身份和边框属性：二是附加属性：字符类 型、质心类型、质心坐标、w a l l 属性。 字符类型：分为如下6 个类( 原算法分四类，由于有些字符不需要考虑嵌套 基准线，所以把操作符另分类，在求嵌套域时不做处理) 。 l i m i t ss y m b o l s ( 如： 、j 、丌) ： s q r t ( ) ： n o n s c r i p ti o n0 ： o p e r a t i o n s ( 如 、+ ) ： p u n c t u a t i o n ( 如。、；) ： o t h e r s 可以从它们所带的子域来区分它们。l i m i t ss y m b o l s 有6 种域( t o p l e f t ， a b o v e ，s u p e r ，s u b s c r i p t ，b e l o w ，b e l o wl e f t ) ，s q r t 有两种域( c o n t a i n s ， s u p e r ) ，n o n s c r i p t i o n 0 有两种域( a b o v e ，b e l o w ) ，o p e r a t i o n s 无任何操作域， p u n c t u a t i o n 的坐标属性会作适当修改，无任何操作域，o t h e r s 有四种域( a b o v e b e l o w ，s u p e r ，s u b s c r i p t ) 。 域的概念：每个字符的域定义为字符可能跟的嵌套字符所处的位置范围。 在数学公式里，对每个字符可能的域有7 种：c o n t a i n s ( 字符本身所在范围) ， b e l o wl e f t ( 左下区域) ，b e l o w ( 下部区域) ，s u b s c r i p t ( 下标区域) ，t o p l e f t ( 左 上区域) ，a b o v e ( 上部区域) ，s u p e r s c r i p t ( 上标区域) ，具体分布如图4 4 所示。 综上所述，对每个字符，在分析前得到的具体属性有： i d e n t it y ( 字符身 份，识别结果) ，m i n x ，m i n y ，m a x x ，m a x y ( 字符在公式中的边框坐标) ，s t y p e ( 字 符类型属性，用于域分析) ，c t y p e ( 质心类型属性，用于求字符中心坐标) ，x _ e ， y _ c ( 质心坐标) ，m l n x w a l l m i n y w a l l m a x xw a l l ，m a x yw a l1 ( w a l l 属性， 用于结构分析求后续字符的范围界定) ，共1 3 种属性( 如图4 5 所示) 。 数学公式识别 图4 - 4 域的定义 图4 - 5 字符的结构属性 第四章数学公式的结构分析与复原 4 2 结构分析算法 结构分析的任务是对字符识别的结果进行处理，最终得到一棵结构树，然 后通过对结构树的遍历，得到公式结构的属性描述，进一步还原公式的结构。 目前数学公式识别的结构分析算法研究比较多，但经过实现来验证其分析效果 的算法很少，大部分处于理论研究阶段。目前流行并实现的算法可以分为两类： 一类叫做b s t ( b a s e l i n es t r u c t u r et r e e ) 的结构分析算法 4 5 ，通过实际系 统的验证，被广泛关注：另外一类结构分析算法是关键字( 操作码) 结构分析 算法。下面是b s t 算法的描述。算法流程如图4 6 所示。 1 用表达式分割识别而得到的文字构成整个表达式的文字列表； 2 给每个文字分类和求文字的中心，文字类决定与文字相关的嵌套基线的 位置。四个文字类是： l i m i t ：即：对操作数有限制的文字，例如s u m 和i n t e g r a l ； s q r t 根号； n o n s c r i p t e d ：即：不跟上标和下标的文字：一元和二元操作符， 前括号，水平线； p l a i n ：所有其它的文字，包括字母和数字混合的文字和后括号) ； 文字的中心用来测试文字是否属于某个域。中心由边框的坐标来计算， 中心的计算也反映了文字是土二标还是下标、或者两者都不是； 3 树的初始化：开始时，b s t 树只有一个节点e x p r e s s i o n ，r 是包含 整个表达式的图像域，l 是第一步得到的文字的分类列表： 4 计算s l = s t a r t ( l ) 找到文字s i ，s l 是在域r 中的主要基线的起始文字。 s t a r t ( l ) 是用来检验s ，是否是文字列表l 中的最左边的文字，例如： 可以位于的左边； 5 找出以s 丌始的基线中的其他文字。h o r ( ) n 以找到基线中的下一个文 字：它能够处理象上图中的不规则分布。计算s 2 = h o r ( s h l ) ， s 3 = h o r ( s 2 ，l ) 如此下去直至h o r ( ) 函数返回n u l l ； 6 上”步得到的s l ，s 2 ，s n 是域r 的主要基线。把他们添加到b s t 树中：插入n 个文字节点作为描述r 的域节点的子孙； 数学公式识别 7 在主要基线上的文字把域r 分成子域，所有文字都有a b o v e 和 b e l o w 域，( 对于l i m i t 文字，这些域被标志为u p p e r 和l o w e r ，他 们可能扩展为文字的左和右) ，s q n 还有c o n t a i n s 域，类p i n n 和s q a 中的文字还有s u p e r 和s u b s c 域； 每个子域的文字列表为l 中除s i ，s 2 ，s n 以外的文字 8 对每个域节点进行4 到8 步的操作得到非空子树( 循环) ，把这些子树 添加到b s t 树中。 基于关键字的结构分析算法有很多种，我们简单介绍一种基于操作码的结 构分析算法。对一个待识别的公式，通过字符识别，可以对字符进行分类：操 作码和操作数( 操作对象) 。先分析操作码，然后根据操作码分析操作对象，得 到公式的操作码结构。应该说，这种分析方法更接近公式的语义，使得以后的 工作更容易进行，但它也有很致命的缺陷，在第一章中已经总结。 本文采用结合这两种方法各自的优点，并加以改进然后用到应用系统中。 需要说明的是，本文采用的关键字结构分析算法并不是基于操作码的，而是基 于括号匹配的方法，这样，可以使得结构分析的结果更规范，也能提高结构分 析的有效性。 第四章数学公式的结构分析与复原 图4 - 6b s t 算法流程 2 7 数学公式识别 4 3 算法改进 各种结构分析算法都有其优缺点。为了达到更高的识别率，我们集成了两 种结构分析算法：b s t 算法和基于关键字( 括号匹配) 的分析算法，并对它们 加以改进。其过程是，主体分析流程采用b s t 算法，对于具体字符间关系的判 定采用基于语义的方法。基于关键字( 括号匹配) 的分析算法可以在很大程度 上提高分析的准确性，弥补b s t 算法的缺陷，但是它的局限性在于关键字要存 在且匹配，这恰恰是b s t 算法的优点。 4 3 1 手写体公式结构分析 对于手写体公式结构分析，为了提供给用户输入时更多的方便，通过修謦 结构分析算法，可以提高算法的适应性和准确性。所做改进如下： 1 区域重叠。使得字符相邻子区域之间具有部分重叠。在b s t 算法中， 区域之间是严格划分的，没有重叠，但适当的区域重叠使得用户完全 可以根据自己的书写习惯去输入数学公式，可以把字符写于两个邻域 的中间带上，没有必要知道图4 - 4 中的区域划分。在这种情况下，具体 通过以下规则解决： 规则l 每个相邻的区域重叠皮取宽度的2 0 ： s u p e r 和s u b s c r i p t 两个子区域被延伸到字符的中心， 因为h o r 分析在子区域分析前进行，保证了这样的延伸 不会带来额外的分折错误。如下图4 7 所示的有色区域( 积 分号的上下标区域) 与字符本身的区域重叠。 o 鼢睁豳两口8 图4 7 手写体公式识别样本 。 第四章数学公式的结构分析与艇原 2 区域扩展。为了方便实现操作码树向属性字符串转化，我们通过区域 扩展，使得分析按照更符合语义规则的顺序进行，即在实现时每个字 符在上下两个大的区域只产生一颗予树，而不是原算法中产生三颗予 树( 图4 - 4 ) 。但是，扩大区域之间的重叠程度会提高结构分析的错误 率，这可以通过调整子区域分析的顺序来避免分析的重复，具体通过 以下规则实现： 规则2 t l e f t 子区域完全包括a b o v e 和s u p e r 两个子区