[机械模具数控自动化专业毕业设计外文文献及翻译]【期刊】概率的数学公式识别使用一个二维的上下文无关文法图-中文翻译

西北工业大学明德学院本科毕业设计论文1 概率的数学公式识别 :使用一个二维的上下文无关文法图 数学表达式的识别问题。发达的系统灵活的，它可以很容易的扩展语法由于它的图形语法，不需要指定规则的优先级。在这个意义上是最佳表达式的所有可能的解释是扩大没有早期的承诺或艰难的决定。在这，我们给出了整个系统的概述和描述详细说明用图的语法和解析过程系统，随着对字符的一些初步结果 ,的结构和表达的识别性能。 关键词在线，手写识别， OCR，数学方程，二维图形语法，图框语法 一、引言 在计算机和其他地方的增长尽管在我们的生活中的数字设备，纸和笔是最传送或记录信息的方便的方法 方法。特别是，数学表达式是最反对 手写输入的应用。计算机理解手写文字（手写或数学公式）是一个正在进行的研究领域。不同的？困难是由于几个因素，包括写作风格的变化较大，其词汇的指示可能的替代品的大小，和一定形状的无语义歧义理解（例如， “O”和“ 0”） 。 数学表达式识别包括两个主要 ubproblems：赛格字符识别的识别化和标记符号（数字，字母，特殊数学符号）和结构分析下 优秀的表达结构的空间字符和字符识别之间的关系定义输出。数学表达式的识别更挑战相比，在识别由于手写文本 O 数学表达式的复杂语义以及汉字的二维布局。 有几种方法在文献结构数学表达式的分析：程序编码规则 1 ； X-Y 削减基于投影亲？ LES 2 ， 3 ；基线树的构建 4 ， 5 ；随机上下文无关语法 6 ；约束属性文法 7 ；分层分解分析 8 ；生成树的生成加权图 9 ；和图形语法 10 13 。在之间这些方法有一定的优势，图语法：为把 14 了，图语法的本质二维表示可以代表一个可能在于有限数量的模式，有限数量的规则，当增强属性。事实上，图语法是公式识别的首选方法之一 ,近年来。在 10 ，图语法添加到现有的系统放松约束的书写顺序的符号。在 11 13 的工作是基于图重写，在一个自底向上使用的语法分析器，折叠节点匹配在每一个规则应用到一个节点。这些系统，的解析过程的输出是一个单节点的含所有输入符号和对应的预期所表达的意思。 西北工业大学明德学院本科毕业设计论文2 我们的系统使用概率上下文无关图指导系统数学有效的解释和关联概率可解释的表达。所提出的系统区别于以往工作的概率算法的方法：先前的基于图文法方法修改初始图的应选择的语法规则是不可逆的，我们的方法娱乐的相邻标记所有可能的解释最终的表达。这可能是由于它的图形语法，可以指定需要规则的优先级，在所有可能的解释为 在迄今为止被保存在一个扩展图。在这框架，所有可能的解释歧义消解的表达是在分析结束，由考虑到由此产生的可能的解释。一种解释的可能性取决于适宜性的符号空间分布的规律和与公认的符号的似然。输出我们的系统是最有可能的解析的输入，随着他们的情况。这是一个重要的优势所提出的系统，为用户可以简单地选择正确解析从名单上，而不是纠正解析结果或重写的表达。 下一节简要描述图克火星，然后我们的方法和实验结果 AR 在随后的章节中描述。在本文的其余部分，使用的术语指的是字符识别的 OCR 不久符号和字符的互换是指 segmente 字符；和节点或令牌是指目前的 O 组符形式的表达式。 二图语法 数学公式精确的语法严格的数学的适当的数学定义是什么性表达和正确解析（含义）一个给定的数学表达。语法包括生产规则说明终端和非 终端定义在语法方面，联合产生作为一个结果的规则应用的非终端。例如我们可以举一个简单的字符串的语法，德？ NES 规则这使得数字和整数如下（这里的 10 数字终端，而数字和点是非 终端）：数学公式精确的语法严格的适当的数学定义是什么性表达和正确解析（含义）一个给定的数学表达。语法包括生产规则终端和非 终端定义语法方面，联合产生作为一个结果的规则应用的非终端。例如我们可以举一个简单的字符串的语法，规则这使得数字和整数如下（这里的 10 数字终端，而数字和整数是非 终端。 数字 =0,1,2,3,4,5,6,7,8,9 整数 =0,1,2,3,4,5,6,7,8,9, 图的语法提供了一个形式主义的语法多维数据不能计算处理通过字符串的语法实现。由于他们的介绍解决图像处理问题，图语法被用来在不同的领域，如并行系统，数据库，编程语言和生物学 15 。在数学表达式的识别，图的语西北工业大学明德学院本科毕业设计论文3 法是 十配合使用图重写的方法初始图形构造标记的表达反复降低到相应的单节点图解析表达式树。在每次迭代中，一个语法规则的选择和应用，当图的电流图的匹配规则的模式图；结果规则的应用，当前图转化为用规则表示。 特别的，规则 R =（ GL； GR； C； EM）由左侧和右侧图图 Gl GR，一个适用性谓词 C，和一个嵌入规则了 Em。适用性谓词 C 是一组约束节点和 /或边缘的属 性值，和不存在一定的边缘，需要满足，以便能应用的语法规则。例如，应用 一个规则谓词表示两个标邻近的标记应具有可接受的大小和位置关系。适用的谓词，应用一个生产规则可以限制即使规则有在输入图的匹配。一个生产应用一个图 G 的规则产生 G0，这是表示 G） R G0。与生产 G） R G0 一个发生图G 是一个图 GL GR 生产取代 G0 按照嵌入规则， EM，如果适用谓词是满意的。嵌入规则规定子图的将子 GR 在图含有原子 GL。在字符串的语法，安置生产是显而易见的，但是在图文法，安置生产图 GR 必须指定通过嵌入规则的 EM，描述如何处理悬边（边缘那个失去一个节点后， GL 是从图）和如何连接到现有生产图 GR 图。一个图 G =（ N； E）被认为是在图语法 GG 的当且仅当 N 2 N（节点）和 E 2 E（边缘）的 GG 和存在的推导，可以生成 G 规则从河从图 G 图 G0推导语法 GG 是德？内德作为一系列产品其中 G） RI1 G1） ri2 G2：）里克G0。图 1 显示了一个例规则从图 G 的导出 G0 在哪儿标记节点 A 和 C 都有替换节点 D 一个有向边从 A 到 C 的嵌入规则表示只有边缘向 C 和边出应保持。虚节点和边在规则说明可能的额外的节点和边，这可能会或可能不会在实际的呈现。 图 1。规则 R 图给图 G0 应用。 三、提出的方法 所提出的系统的概述，如图 2 所示。输入的表达首先分割成孤立的符号 (一个字符或中风的字符） ，每个符号的 OCR 引擎解释部分识别 ii-a.然后初始图的构造，其中的节点 a 认可的符号和边缘代表德 连接符号之间的空间，如 N段 iii-b.解析算法应用文法规则的电流图，添加一个新的节点，在每次迭代中的边缘（参见中间记号在图 2） 。这些新的节点或标记邻近的令牌代表可能的解释。解析过程继续下去，直到没有有效的生产电子资金转账。 我们的语法和解析算法的解释的方向 III-C. III-D。 西北工业大学明德学院本科毕业设计论文4 A. 分割和字符识别（ OCR） 输入的表达首先分割成单独的基于时间维度的特征，即相对两个连续的中风或大之间的时间差特征是用来表示字符边界。然后，在空间上重叠的符号被重新组合（例如两个“ +”符号笔划） 。 OCR 系统是结合支持向量机（ SVM）和人工神经网络（ ANN） ，结合使用。它的输入的分段特征参数和输出三个相关的分数。我们从拉维奥拉数据集选择的一个子集 5 ，附录。 预处理包括大小归一化的事对在线数据以减少工件的坐标每个点被映射到一个固定的坐标范围。然后人物形象是通过插值从这些点的创建。特征提取作为输入的调整大小的图像特征，忽略了时间维度。这样做是为了消除在人物画的时空变化，以及允许用户修改的符号和公式后可以完成了方程。两分类 ,输入功能包括水平，垂直和对角直方图的符号图像的水平，垂直和对角线的深处的黑色像素点符号图像； 8 的 Windows 8 黑色像素数在整个符号和图像的宽度和高度的比率。 在这个数据的支持向量机的系统成功率 92%。虽然有方法生成后从多类支持向量机分类的概率阳离子，我们使用一个神经网络生成的分类，阳离子的选择和获得可靠的识别欺诈证据。人工神经网络的分类，用是一个1-hid 隐藏层前馈神经网络与 30 隐藏神经元。这个分类的性能低相比于SVM，详细的和高识别 88%和 97%的比率，分别为。由于支持向量机在的表演更成功， OCR 系统采用支持向量机的输出作为首选，并获得下一个两个选择和控制从人工神经网络的研究。什么时候精度是低于国家的最先进的 OCR 结果，不在这项工作中的主要焦点。 B. 构造初始图 最初的图是从一个标记列表生成通过分割得到通过 OCR 发动机。在该图中，一个节点对应于一个标记和一个边缘的两个节点之间表明这两个节点在表达的空间布局的邻居。过程可以说正是利用以下定义图形元素： 节点：一个节点是一个元组的 n =（ t； i； c； A) t 是节点类型的； i 是一个独特的识别； c 是相同的的规则，构建了节点属性值。一个节点的类型是词法类型的符号，如数字，字母，算子。每个节点知道哪些规则构建自西北工业大学明德学院本科毕业设计论文5 身，所以如果需要的话，整个历史可以产生。在图 4 中每个方块代表一个图中的节点。 边：边缘是元组 E =（ t； n1； n2） t 是的边缘型， n1 和 n2 是连接节点在一起的边缘。有三种类型的边缘用解析过程： 空间关系的边表示两个节点是否邻居（见定义以下） 。 组件的边缘的非终端节点及其关系组件，用于生成语法树后解析过程。 生产边缘组件边缘反，连接一个终端和非终端节点到非 终端节点，利用它。 初始图形空间关系的边缘，只有他们决定胜负，而其他人（组件生产的边缘）被用来跟踪和加速解析过程。 在此系统中，空间关系的边缘不有任何属性，因为我们不区分不同 邻里关系的不同类型（侧，顶部，底部等） ；不同的社区类型是隐式的决定每个规则的适用性谓词。我们的优势方法是将空间关系的属性适用性词的规则，而不是判定元件全球空间关系的定义，每个规则可以有它自己的空间关系的定义类别。在这种方式中，而不是拘泥于标记这是写的一个与侧弱 y 符号附近的边缘，比如下标规则决定如果这两个符号的相对位置后大的应用规则。街道本身是有一个清晰的线他们的包围盒的中心点之间的视线在小于一个阈值计算的距离从表达式中的符号的平均大小。 通常，一个令牌 3 最佳识别方案与之相关的。然而，如图 2 所示，如果一个角色可能属于一个以上的类型的符号（如“ +”是一个操作数的符号或“ t”） ，然后生成令牌它为了简化解析过程。 C. 语法 我们用一个概率上下文无关文法是二维的基于数学的语法，使用空间布局在本规则的适用性谓词信息。在这个语法，规则是一个元组 R =（ GR； GL； C）在 GL 该模式图， GR 是产品图和 C 的应用 谓词， C：通用能力！ ftrue falseg 通用汽车的地方是一个与 GL 图形。没有嵌入因为所有的规则，规则的遵循相同的嵌入。正常图语法规则表明， GL 被 GR 但西北工业大学明德学院本科毕业设计论文6 在我们的系统中，它表明， GR 被添加到图形（如一个新的节点）和 GL保留它。 左边的图 GL 每个规则是一个星形图（一图有一个中心节点和周围的邻居节点只连接到中央节点） ，和正确的右手边的图的 GR 是一个节点。图 3 GL 和两个简单的语法规则的 GR 图，其中“ +”在 R1 和 R2 的规则的规则算子是中央节点规则。 对申请的决定规则中最重要的部分来自性谓词。对于大多数的规则符号之间的角度和距离的检查，以及它们的大小。一些规则可以对属性有进一步的检查价值观。例如，用于检查分数的规则， GL 具有中心节点代表水平线符号。用性谓词的约束保持宽松，为了保持所有可能的解释数学表达式。例如，上标规则不要求，上标符号较小的尺寸比的基础，但它是不（很）大。 由于匹配节点保持在图中，每个规则也有一个谓语，检查不存在生产的边缘连接到相同的节点 GR 的规则，以防止再次匹配相同的节点产生相同的产品。这有点复杂解析过程和增加了复杂性，但删除需要定义优先规则。 目前有 17 的语法规则，包括对于下标，上标的数学规则，运算符（ +， ，和 ） ，分数，求和，和积分） ，以及至于写在多个非符 号组合的一些规则 重叠笔划（例如 = ， ） 。某些终端与非终端定义语法中给出附录。 所开发的系统主要是将手写数学表达式为乳胶容易进入科学文章；因此，在 LaTeX 代码正确的语法是明确的。然而，系统不了解数学的优先级规则，因此两个或两个以上的可能会产生解析方案对于一个输入，只会得到解决的优先规则（例如， A + B C + D） 。然而，由于该系统提供的所有可能的解释给用户，用户可以选择正确的解释的几种可能的解释之间。 D.解析算法 我们的解析算法是一个相当简单的底部 过程。在每一轮中，算法检查什么规则的语法可以在每个令牌是适用的图。如图 4 所示，最初有 4西北工业大学明德学院本科毕业设计论文7 个代币在初始图 4 节点对应；然后，之后第一轮，两个新的标记（ A2 和a + b）的生成和添加到图。 特别地，两个任务必须由解析器进行：寻找一个相匹配的规则模式图和嵌入产生的产品图。因为任何模式图规则是在我们的系统中的星形图，当处理一个节点，分析器查找匹配的规则具有相同的中心节点；然后检查相邻节点和适用性谓词匹配过程。 一旦找到一个匹配的，一个新的节点根据的规则，然后连接到现有的图组件和生产的边缘。空间关系边缘产生新产生的节点在后没有可能的生产是在现有的图左。每个新的节点继承了它的组件的邻居。空间关系的新生成的节点之间的边分开。 为了处理的解析过程的复杂性在所有可能的地方解释保持，我们使用的（可能性）标记的决定扩展这个令牌（即应用规则） 。理想的应该是做一个 A*搜索，但是目前它是通过一个阈值是动态调整，根据令牌总数和覆盖（如何输入表达式的多标记覆盖）的最好的令牌。 E.消除歧义的解析结果 解析过程的输出是一个图可能的产品是目前。此外，如果输入可以定义的语法，那么至少有一个节点其中包括所有输入符号将在输出图。由于组件的边缘保持产品的历史，一个如果一个表达式树可替代的产生解释节点为根和组件边缘之后，直到达到一个终端节点。 我们计算的可能性，也被称为性，性每一个解析的替代根据预先了解空间布局。 OCR 输出的概率分布。这些分布 问题，例如为基础的相对大小差异下标符号，都学会了在单独的训练数据。总之，所产生的每一个节点可能是产生的空间关系的平均对数似然节点和构件是似然一个符号的发生概率。 举个例子，在图 4 的输入，可能标记的 a+ b 将取决于的可能性的符号“a”的空间布局， “b”和“ +”，就规则添加。我们的每一个空间分布模型 分布统计直方图和计算的可能性在两个符号中的一个给定的距离（例如 X 或 Y 偏移从“ a和 +）相对于该直方图。我们还使用字符识别概率的区别之间的替代分析 a+ b 和 atb 共享相同的布局相似，但不同西北工业大学明德学院本科毕业设计论文8 的可能性字母“ t”。一个更复杂的表达式的可能性（例如（ a + b） 2）是由其平均数对数似然性计算通过在每个组件的数量加权组件组件。可能是在每个规则进行计算应用。 四、实验结果 开发的系统使用的一部分测试在协会收集的数学表达数据库这项工作 16 。完整的数据库包含 57 个方程每次从 15 个不同的用户选择，从常见的表达 结论以匹配由王等人 17 使用的。表达长度范围从 7 到 30 个字符长度。测试集由 20 个方程组成，每个由 5 个不同的用户。 结果是在与表达分析 精度（产生的胶乳的代码方程正确的） ；结构的识别精度（乳胶代码除了 OCR 错误纠正） ；字符识别精度，说明如表IV。 任务准确性计数 正确认识 17% 17 / 100 的表达 正确的结构分析 50% 50 / 100 正确的字符识别 79% 1100 / 1410 表一整体准确度（ 5 用户 20 表达式） 任务准确性比例 表达长度小于等于 1025 / 100 正确认识表达 52%13 / 25 正确的结构分析 88% 22 / 25 表达的长度趋于 11 30 75 / 100 正确认识的表达 5,33 % 4 / 75 正确的结构分析 37,33 % 28 / 75 表二分析表达式的长度方面的结果。 我们看到，方程的识别精度较低（ 17%） ，这是不是很奇怪的 DIF 水平的问题；但结构识别精度也不是很高（ 50%） 。这可以通过事实的解释整体结构误差影响的意义 .明显的 OCR 精度。例