基于ocr的数学公式结构的分析

基于ocr的数学公式结构的分析

1印刷体数学公式识别与结构分析随着网络技术的快速发展，将打印文档转换为电子文档是信息交换的重要步骤。借助OCR(OpticalCharactersRecognition，光学字符识别）技术将文档信息输入计算机，是目前公认的信息数字化的高效手段。现有的文档识别与重构系统（OCR软件）对印刷体文字的识别率很高，但由于数学公式的二维嵌套特性、所包含符号的复杂性及数学符号表达含义的多样性，使得数学公式的自动识别成为模式识别中的瓶颈问题。而数学公式是绝大多数科技书刊的重要组成部分，甚至一些文献的核心就是这些公式，失去了公式的文章可能毫无意义。一个无法处理数学公式的识别系统，在应用于富含公式的科技文献时，往往失去其应用价值。因此，研究印刷体数学公式识别与重构技术，具有重要的科学意义和应用前景。数学公式识别通常由三部分组成：数学公式提取；数学公式识别与结构分析；数学公式重构。其中，公式结构分析是一个关键环节。从20世纪的70年代以来，研究人员对数学公式的结构分析做了大量的工作。Anderson采用自顶向下的分析方法，以句法为标准分割识别。Chang提出了利用结构说明方案来分析公式结构的方法。Lavirotte和Pottier采用上下文相关文法分析关键字，以改善分析效果。Grbavec和Blostein利用图来表达公式结构分析的结果，并利用了符号使用的知识。但上述的方法都存在一些缺点。本文提出了一种利用基准线构建初始结构树，并利用语法和语义知识进行树转换。实验证明，这种方法对数学公式的结构分析效果较好。文中第2部分介绍结构分析的预处理；第3部分讨论结构分析的具体步骤；第4部分是实验结果和存在问题的分析。2字符的质心生成为了便于结构分析，需要提取函数名与子表达式字符串，而要完成这些功能，须对字符的大小和中心进行归一化。首先计算字符的外边框（如图1所示），并找出中心，然后把字符中心移动到指定的位置上。根据水平和垂直两个方向字符黑像素的分布进行大小归一化。需要先计算字符的质心GI和GJ:式中c(i,j）为1时表示该像素点为黑像（字符像素），为0时表示该像素点为背景。再计算水平和垂直方向的散度σI和σJ:最后，按比例将字符线性放大或缩小成规定散度的点阵。2.1提取函数名对字符归一化后，运用最长字符串匹配的方法，提取函数型字符（三角函数，绝对值abs（），逻辑符号，等于号等），并把它看作一个整体符号。2.2相邻字符生成满足下列条件的连续字符合并为一个字符：（1）具有相同大小和中心。（2）两相邻字符间的空格小于它们大小。例如2100中1,0,0合并成100。3初始结构树的构建首先利用基准线找到中心点在同一阈值内的字符，根据各个字符之间的位置关系，放在不同的子节点中，构建出初始结构树；然后利用语法和语义知识将结构树转化成以运算符为子节点，操作数为叶子节点的树。3.1确定基准线的算法数学表达式通过数学符号大小和相互之间的位置关系来传递信息，通过对数学公式中基准线上字符的分析，就能揭示数学公式的含义。具体的步骤如下：步骤1记录公式中各个字符的边框线和中心点坐标。对公式中的每一个符号，记录下它们的边框坐标minX(s),maxX(s),minY(s),maxY(s），以及各个字符的中心点坐标CentroidX(s）、CentroidY(s）和高度H（图1):步骤2构建初始结构树。以整个数学表达式（EXPRESSION）作为树的根节点（rnode），将公式所用的字符（已提取的字符串和函数名作为一个字符看）按minX(s）从小到大的顺序存放在列表L(list）中，并作为树的子节点。步骤3确定基准线。对基准线的说明如下：(1）基准线（DL）：对于s1,s2，…，sn∈L，如果CentroidY(s1)-tH≤CentroidY(si）≤CentroidY(s1)+tH成立，那么B=B∪{si}，B集合中字符所在的直线区域成为基准线。其中，s1是首字符，H是首字符的高度，t是阈值（0<t<0.5）。基准线与符合条件的字符集合一一对应，中心点在这个高度范围内的字符在同一条基准线上。例如X2+d+bY=Z中X、+、b、Y、=、Z在同一条基准线上；2、+、d在另一条基准线上，所以在X2+d+bY=Z中有两条基准线。(2）主基准线：对于si∈L，如果（┐SUPER(si,sj））∧（┐SUBSC(si,sj））∧（┐CONTAIN(si,sj))=1成立（其含义见步骤4），并且s1,si∈B，则si所在的基准线称为主基准线。主基准线上对应集合中的字符不被其他字符嵌套。也就是公式中最左边的字符所在的基准线。例如在X2+d+bY=Z中X、+、b、Y、=、Z所在的基准线为主基准线。(3）嵌套基准线：对于sj∈L，当且仅当SUPER(si,sj),SUBSC(si,sj),ABOVE(si,sj),BELOW(si,sj),CONTAIN(si,sj）中有一个为真，sj嵌套si。si所在的基准线为嵌套基准线。其中i≠j。嵌套基准线上的字符，在垂直方向上偏离了某个字符或被别的字符所包围。嵌套常用来表示某种隐式运算。例如在X2+d+bY=Z中2、+、d所在基准线为嵌套基准线，与X之间存在嵌套关系，表明了前者和后者之间的指数运算。确定基准线的算法如下：其中Snode＿list是结点的符号列表；Symbol(rnode）表示根节点的字符；Sstart表示符号列表中的首字符；Hor(Sstart,Snode＿list）是在列表中以Sstart为首字符，从左向右寻找符合条件字符的函数；Collect＿Regine(BaseLine＿symbol）把符合条件的字符放入相应的基准线上；Symbol(Update＿Baseline）表示将基准线上的字符放入子结点；rnode′表示子树的根接点。步骤4分配字符。把同一基准线上的字符s1,s2，…，sn放到同一层子节点中，其他字符放入到其后代子节点。根据从左到右阅读公式的习惯，按下列规则存放字符：嵌套基准线上字符放入到其最左边字符临近字符所在节点的子节点中。可以用最近邻法中Euclidean公式计算距离：同时用标签标注子节点中字符si其父节点中字符sj间的位置关系：SUPER（上标），SUBSC（下标），ABOVE（上部），BELOW（下部）和CONTAIN（包含）。其定义如下：步骤5判断是否结束。判断最下层子节点中字符数是否为1，如果为真，则结束；否则返回到步骤3。3.2公式分析利用数学公式中语法规则和语义知识将原来的结构树，转换以操作符为子节点、操作数为叶子节点的操作符树。3.2.1作用域越小，分级越高根据运算符的优先级和它们之间的相关性，即运算符的作用域，作用域大的主导作用域小的。作用域越小，优先级越高。例如X2+d+bY=Z中，“=”的作用域是整个公式，最大；“+”的作用域是“=”左边的半个公式，但“+”比“=”的优先级高。对公式进行语法分析时，要注意运算符的作用域，最后用TXL语法将初始结构树转换成语法树。3.2.2语义“-”的重构通过分析数学公式的语义，能够识别隐含的运算符（如X2+d+bY=Z中bY之间包含的“*”），分析操作数类型，根据上下文消除运算符的歧义（“-”可以是分数线，还可以是逻辑非），并记录操作数，以便于根据运算的优先级别的同，对公式中运算符排序。语义分析之后，利用树转换规则重构结构树。树转换规则能够搜索结构树，把语法树转换成一种更严格、紧凑的形式。它是以列举方式定义的一组规则，如a*b，转换成[*，a,b]。由于在前面初始结构树中已标明符号的关系，简化了树转换规则。在最后得到的决策树中，包含了隐含的运算符以及操作数。4试验结果与问题分析4.1．不同组数学公式的测试结果实验结果表明，对同一组公式，当时，确定基准线的正确率为75%，识别率为72%；当时，基准线的正确率为79%，识别率为78%;时，基准线的正确率为79%，识别率为78%;时，基准线的正确率为72%，识别率为71%。选取，对不同组数学公式测试结果如表1。这种方法对于公式的结构分析效果理想，可以