第3卷第5期 智能系统学报 Vol 3 Na 5 2008年10月 CAA I Transactions on Intelligent Systems 0ct2008 数学公式图像的结构理解与重现 史广顺，肖萃，王庆人 南开大学机器智能研究所.天津300071)】 摘要：数学公式图像识别与理解是文档图像处理领域的重要组成部分，目前尚无满足一般应用的处理方法.提出 了一种鲁棒的数学公式结构理解方法，使用公式图像识别结果、语法规则和句法规则分析数学公式结构，对数学公 式的类型进行了完整的划分，对识别结果的错误进行自动的检查和纠正，能够自动分析数学公式符号的优先级和计 算顺序既可以应用于数学公式图像的识别与格式转换，也可应用于对数学公式的检索和辅助编辑.基于1000个真 实公式图像的实验结果证明了分析方法的有效性和稳定性. 关键词：数学公式识别：版面结构分析：语法结构分析：数学公式结构理解 中图分类号：TP391文献标识码：A文章编号：1673-4785(2008)05040107 Recon structing ma thema tical expressions from mage da ta SH I Guang-shun,XO Cui,WANG Q ing-ren (Institute ofMachine Intelligence,NankaiUniversity,Tianjin 300071,China) Abstract:Mathematical exp ressions appear in many kinds of scientific documents and technical reports Under- standing and reconstructing mathematical expressions has become an mportant problem in the domain of document mage analysis The authors developed a robust method for the analysis of structure in mathematical expressions After mages are processed,generating recognition results,this method analyzes the structure of mathematical ex- pressions according to syntax rules and syntactic rules Classification into different types of mathematical exp res- sions is then made Syntax errors in the recognition process are checked and corrected automatically The preferen- tial level and the computing sequences of arithmetical operation signs in mathematical expressions are also automati- cally analyzed This method can be applied to the recognition of mages containing mathematical expressions and transom ing beteen fomats,and is useful in retrieval and editing of mathematical expressions About 1000 ma- ges ofmathematical expressions fiom real documents were used for perfomance evaluation The test results proved the stability and efficiency of this method Keywords:mathematical expression recognition;layout analysis syntactic analysis mathematical expression un- derstanding 数学公式存在于各类文档之中，对其进行精确对数学公式进行结构拆解的方法，也包括使用语法 的识别和理解是文档图像处理领域的重要问题.由 规则对数学公式结构进行理解和描述的方法」 于数学公式的二维空间结构以及数学符号语义的多 Tian提出了利用基准线构建初始结构树，并利用 义性，使得对数学公式结构的描述与理解变得非常 语法和语义知识进行树转换的方法.U.Garain'采 复杂和困难，所以对其的研究具有很高的科研价值 用词法分析与句法分析相结合的方法，来提高树结 和挑战性.近20年来，研究者们提出了多种数学公 构的准确度. 式结构分析的处理方法.既包括利用版面信息】 在上述的各种方法中，单纯依靠版面信息无法 消除数学符号的歧义性，不能理解数学公式的计算 收稿日期：200804-16 含义.近年来的一些新方法中，虽然加入了语义语法 基金项目：天津市自然科学基金资助项目(05Y℉MJC01500). 规则，可只是作为辅助信息，无法有效检查并纠正数 通信作者：史广顺.Emai让gsshi@nankai edu cn 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 3卷第 5期 智 能 系 统 学 报 Vol. 3 №. 5 2008年 10月 CAA I Transactions on Intelligent System s Oct. 2008 数学公式图像的结构理解与重现 史广顺 , 肖 萃 , 王庆人 (南开大学 机器智能研究所 ,天津 300071) 摘 要 :数学公式图像识别与理解是文档图像处理领域的重要组成部分 ,目前尚无满足一般应用的处理方法. 提出 了一种鲁棒的数学公式结构理解方法 ,使用公式图像识别结果、语法规则和句法规则分析数学公式结构 ,对数学公 式的类型进行了完整的划分 ,对识别结果的错误进行自动的检查和纠正 ,能够自动分析数学公式符号的优先级和计 算顺序. 既可以应用于数学公式图像的识别与格式转换 ,也可应用于对数学公式的检索和辅助编辑. 基于 1 000个真 实公式图像的实验结果证明了分析方法的有效性和稳定性. 关键词 :数学公式识别 ;版面结构分析 ;语法结构分析 ;数学公式结构理解 中图分类号 : TP391 文献标识码 : A 文章编号 : 167324785 (2008) 0520401207 Reconstructing mathematical expressions from image data SH I Guang2shun, X IAO Cui, WANG Q ing2ren ( Institute ofMachine Intelligence,Nankai University, Tianjin 300071, China) Abstract:Mathematical exp ressions appear in many kinds of scientific documents and technical reports. Under2 standing and reconstructing mathematical exp ressions has become an important p roblem in the domain of document image analysis. The authors developed a robust method for the analysis of structure in mathematical exp ressions. After images are p rocessed, generating recognition results, this method analyzes the structure of mathematical ex2 p ressions according to syntax rules and syntactic rules. Classification into different types of mathematical exp res2 sions is then made. Syntax errors in the recognition p rocess are checked and corrected automatically. The p referen2 tial level and the computing sequences of arithmetical operation signs in mathematical exp ressions are also automati2 cally analyzed. This method can be app lied to the recognition of images containing mathematical exp ressions and transform ing between formats, and is useful in retrieval and editing of mathematical exp ressions. About 1000 ima2 ges of mathematical exp ressions from real documents were used for performance evaluation. The test results p roved the stability and efficiency of this method. Keywords:mathematical exp ression recognition; layout analysis; syntactic analysis; mathematical exp ression un2 derstanding 收稿日期 : 2008204216. 基金项目 :天津市自然科学基金资助项目 (05YFJMJC01500). 通信作者 :史广顺. E2mail: gsshi@nankai. edu. cn. 数学公式存在于各类文档之中 ,对其进行精确 的识别和理解是文档图像处理领域的重要问题. 由 于数学公式的二维空间结构以及数学符号语义的多 义性 ,使得对数学公式结构的描述与理解变得非常 复杂和困难 ,所以对其的研究具有很高的科研价值 和挑战性. 近 20年来 ,研究者们提出了多种数学公 式结构分析的处理方法. 既包括利用版面信息 [ 122 ] 对数学公式进行结构拆解的方法 ,也包括使用语法 规则 [ 325 ]对数学公式结构进行理解和描述的方法. Tian [ 6 ]提出了利用基准线构建初始结构树 ,并利用 语法和语义知识进行树转换的方法. U. Garain [ 7 ]采 用词法分析与句法分析相结合的方法 ,来提高树结 构的准确度. 在上述的各种方法中 ,单纯依靠版面信息无法 消除数学符号的歧义性 ,不能理解数学公式的计算 含义. 近年来的一些新方法中 ,虽然加入了语义语法 规则 ,可只是作为辅助信息 ,无法有效检查并纠正数
·402· 智能系统学报 第3卷 学公式图像识别结果中的错误，鲁棒性不足.本文提 构，如图2所示」 出了一个句法规则驱动的、对数学公式进行结构分 syntactic structure =layout infomation, 析的方法，将版面结构信息、符号语法规则、公式句 sym bol set,grammar rules,syntactic rules); 法规则相互结合，对数学公式图像的识别结果进行 式中：layout infomation为版面结构，数学公式中所 分析.这种方法既可以实现对数学公式结构的重现， 有符号和公式结构的版面位置信息.版面信息可用 同时又可准确的理解数学公式所表达的计算含义， 于判断作用范围、提取不同层次的子表达式，是重要 为数学公式的语义分析和高级应用提供帮助 的辅助信息，symbol set为符号集，数学公式中所有 本文的研究重点在于如何建立一种介于图像和 出现的操作符和操作数.根据符号内容可调用相应 语义之间的描述结构，对数学公式的版面形式、符号 的语法规则，确定符号之间的组合关系，检查符号出 内容、语法关系、句法结构进行完整的描述，实现不 现的合法性；grammar rules为语法规则，不同符号之 同类型信息之间的统一，从而为更加精确地理解数 间的语法约束与组合关系.它用于确定操作符的作 学公式结构奠定坚实的基础 用域和子表达式内容，同时检查发现识别结果中存 在的错误，保证子表达式提取的完备性和正确性： 1数学公式句法结构描述模型 syntactic rules为句法规则，子表达式的分解与约束 1.1数学公式的结构组成 关系.此类规则主要负责分析不同运算符之间的优 文档图像处理的目标在于获取文档的表面结构 先级顺序，消除数学公式符号的多义性，并可被快速 或深层结构.对数学公式而言，其文档结构层次如 解析转换为其他的数学公式描述形式」 图所示 子表达式之间的 分析 法属性 组合和约束关系 级别 分析层次 分析甘标 重现甘标 (数学公式) 实现机器 C/C++或 符号之问的组合 高 语义理解 自动计算 Matlab代码 语法属性 和约束关系 (子表达式) 实现公式 法重现 的再编辑 MathML文档 符号识别结果 字符集 (识别结果) 实现公式 版式重现 Latex、 图像中符号的位 的图像重现 MathML文档 置坐标、字号、 版面信息 字体等 文档图像) 图1数学公式文档结构层次 Fig 1 Overview of expressions structures 图2数学公式句法结构模型组成 对印刷体数学公式图像的识别和理解包含3个 Fig 2 Syntactic structure model of expressions 处理目标：1)数学公式版面结构重现，使其能够转 121数学公式的版面结构 换为Latex或MaML格式的电子文档，2)数学公式 版面结构包括公式中字符的版面信息和公式结 重新编辑，使其能够导入到类似于MathTypel的编辑 构版面信息两部分内容 器中，3)数学公式重新计算，分析其计算含义并进 字符的版面信息包括字符的外界矩形位置坐 行自动求解或计算 标、字符中心线、字体、字号等信息 由于数学公式的结构复杂性和符号多义性，以 公式结构版面信息包括公式的版面类型、基准 及图像质量低下和识别错误造成的信息失真.只利 线位置以及多条基准线间的相互关系等.数学公式 用版面结构信息无法深入理解数学公式的语义含 中的符号根据其语法属性不同体现出不同的排版风 义，而只利用语义规则无法有效克服各种前期处理 格.根据公式符号的水平中心线(HCL)排列情况， 的结果错误，只有将版面信息、字符内容、语法规则、 可对数学公式的类型进行如下划分 句法规则相互结合，才能实现鲁棒准确的数学公式 I)基元表达式(unit exp ression) 结构分析 数学公式中的独立符号，不可再分，主要是指不 12数学公式句法结构描述模型 具有运算功能的运算数； 本文使用四元组结构描述数学公式的句法结 2)普通表达式(common exp ression) 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
学公式图像识别结果中的错误 ,鲁棒性不足. 本文提 出了一个句法规则驱动的、对数学公式进行结构分 析的方法 ,将版面结构信息、符号语法规则、公式句 法规则相互结合 ,对数学公式图像的识别结果进行 分析. 这种方法既可以实现对数学公式结构的重现 , 同时又可准确的理解数学公式所表达的计算含义 , 为数学公式的语义分析和高级应用提供帮助. 本文的研究重点在于如何建立一种介于图像和 语义之间的描述结构 ,对数学公式的版面形式、符号 内容、语法关系、句法结构进行完整的描述 ,实现不 同类型信息之间的统一 ,从而为更加精确地理解数 学公式结构奠定坚实的基础. 1 数学公式句法结构描述模型 1. 1 数学公式的结构组成 文档图像处理的目标在于获取文档的表面结构 或深层结构. 对数学公式而言 ,其文档结构层次如 图 1所示. 图 1 数学公式文档结构层次 Fig. 1 Overview of exp ressions structures 对印刷体数学公式图像的识别和理解包含 3个 处理目标 : 1)数学公式版面结构重现 ,使其能够转 换为 Latex或 MathML格式的电子文档 ; 2)数学公式 重新编辑 ,使其能够导入到类似于 MathType的编辑 器中 ; 3)数学公式重新计算 ,分析其计算含义并进 行自动求解或计算. 由于数学公式的结构复杂性和符号多义性 ,以 及图像质量低下和识别错误造成的信息失真. 只利 用版面结构信息无法深入理解数学公式的语义含 义 ,而只利用语义规则无法有效克服各种前期处理 的结果错误 ,只有将版面信息、字符内容、语法规则、 句法规则相互结合 ,才能实现鲁棒准确的数学公式 结构分析. 1. 2 数学公式句法结构描述模型 本文使用四元组结构描述数学公式的句法结 构 ,如图 2所示. syntactic structure = ( layout information, symbol set, grammar rules, syntactic rules) ; 式中 : layout information为版面结构 ,数学公式中所 有符号和公式结构的版面位置信息. 版面信息可用 于判断作用范围、提取不同层次的子表达式 ,是重要 的辅助信息 ; symbol set为符号集 ,数学公式中所有 出现的操作符和操作数. 根据符号内容可调用相应 的语法规则 ,确定符号之间的组合关系 ,检查符号出 现的合法性 ; grammar rules为语法规则 ,不同符号之 间的语法约束与组合关系. 它用于确定操作符的作 用域和子表达式内容 ,同时检查发现识别结果中存 在的错误 ,保证子表达式提取的完备性和正确性 ; syntactic rules为句法规则 ,子表达式的分解与约束 关系. 此类规则主要负责分析不同运算符之间的优 先级顺序 ,消除数学公式符号的多义性 ,并可被快速 解析转换为其他的数学公式描述形式. 图 2 数学公式句法结构模型组成 Fig. 2 Syntactic structure model of exp ressions 1. 2. 1 数学公式的版面结构 版面结构包括公式中字符的版面信息和公式结 构版面信息两部分内容. 字符的版面信息包括字符的外界矩形位置坐 标、字符中心线、字体、字号等信息. 公式结构版面信息包括公式的版面类型、基准 线位置以及多条基准线间的相互关系等. 数学公式 中的符号根据其语法属性不同体现出不同的排版风 格. 根据公式符号的水平中心线 (HCL )排列情况 , 可对数学公式的类型进行如下划分. 1)基元表达式 ( unit exp ression) 数学公式中的独立符号 ,不可再分 ,主要是指不 具有运算功能的运算数 ; 2)普通表达式 ( common exp ression) ·402· 智 能 系 统 学 报 第 3卷
第5期 史广顺，等：数学公式图像的结构理解与重现 ·403· 绝大部分符号排列在相同的HCL上，呈现一维 字符语法属性分类.语法规则可以通过对字符 版式结构； 间空间关系的判断，确定字符的惟一语法属性.图4 3)角标表达式(script exp ression) 描述了对“+进行语法判断的过程 角标是一种特殊的语法约束关系，角标符号的 组合“子表达式”定义见23节).语法规则可 HCL位于其描述符号的左上、左下、右上、右下4个 以通过作用域信息，将具有组合规则的运算符与其 方向； 附属字符合并，成为一个子表达式 4)组表达式(group exp ression) 语法规则验证.结合识别结果和版面信息，语法 一些特殊的运算符会与其他符号组合成2D结 规则还可以用来纠正识别错误、消除多语义字符的 构的版面形式，如根式、求和、积分、分式等 语法歧义、实现对树结构的校验和修改.（详见 5)矩阵表达式(matrix exp ression) 25节) 由特殊定界符包含多行多列符号组成的表达 田b+a 式，如行列式矩阵等； 6)堆叠表达式(stack expression) Right(+)-Operand & 二日操作符 Left(+)=Operand 表示加法 描述说明符号在数学公式中常以堆叠的形式出 判定规则 现，它们不是具有固定语法规则的组表达式，如帽子 Right(+)=Operand & 字符属性 Left(+)=Null 表示正号 符号等； 图3描述了不同版面类型的基础数学公式.对 该字符表示字符病性 基础类型进行准确的划分和分析，有助于对公式整 图4利用语法规则确定字符属性 体结构的分解和重构 Fig 4 Check the grammar attributes by grammar rules a z=2a+3y 1.24数学公式的句法规则 (a)基元表达式 (b)普通表达式 不同类型表达式的组合形成了多重层次的数学 (©)角标表达式 公式结构，同层次操作符之间的优先级关系决定了 数学公式的计算顺序 [fex)d女 a+xy+z 句法规则描述每个操作符的子表达式形成规 则，每一个操作符都有一个固定的树型结构模板，其 (d)组表达式 (e)矩阵表达式 (f)堆叠表达式 中子结点的个数和属性均根据语法规则预先填充， 图5描述了根据句法规则中不同的优先级关系生成 图3数学公式版面类型示例 的不同子表达式结构。 Fig 3 Visual samples of layout structures 句法规则同时负责判断操作符之间的优先级 122数学公式符号集的组成和类别 采用相对优先级的形式设计了包含所有操作符 数学公式的符号可分为操作符和操作数2类。 的矩阵结构，任意2个操作符均可通过查找矩阵以 操作符：包括运算符、函数名及某些特殊符号，在数 确定哪个操作符的优先级更高 学公式中表示对一个或多个操作数的某种操作关 公式图像：a×b-G 错误 系，或某种特殊数学规律；操作数：是指由数字、英文 正确 字母、希腊字母等代数符号构成，在数学公式中表示 数量、变量等含义.根据符号的类型可选用对应的语 法规则进行深入的子表达式分析 本文研究工作针对正体斜体英文字字母、数 字、标点、希腊字母、数学符号、三角函数共计220个 字符，覆盖了科技文献中所有数学公式的常用字符 图5优先级比较示例 1.23数学公式的语法规则 Fig 5 Sample of priority comparison 语法规则规定了数学公式中字符的语法属性， 13结构分析底层知识库 以及不同符号间的语法约束与组合关系.对数学公 以上提到的四元组是结构分析的直接依据.通 式的分析过程中，语法规则具有如下作用： 过前期大量的统计工作，对数学公式符号的操作属 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
绝大部分符号排列在相同的 HCL上 ,呈现一维 版式结构 ; 3)角标表达式 ( scrip t exp ression) 角标是一种特殊的语法约束关系 ,角标符号的 HCL位于其描述符号的左上、左下、右上、右下 4个 方向 ; 4)组表达式 ( group exp ression) 一些特殊的运算符会与其他符号组合成 2D结 构的版面形式 ,如根式、求和、积分、分式等. 5)矩阵表达式 (matrix exp ression) 由特殊定界符包含多行多列符号组成的表达 式 ,如行列式、矩阵等 ; 6)堆叠表达式 ( stack exp ression) 描述说明符号在数学公式中常以堆叠的形式出 现 ,它们不是具有固定语法规则的组表达式 ,如帽子 符号等 ; 图 3描述了不同版面类型的基础数学公式. 对 基础类型进行准确的划分和分析 ,有助于对公式整 体结构的分解和重构. 图 3 数学公式版面类型示例 Fig. 3 V isual samp les of layout structures 1. 2. 2 数学公式符号集的组成和类别 数学公式的符号可分为操作符和操作数 2类. 操作符 :包括运算符、函数名及某些特殊符号 ,在数 学公式中表示对一个或多个操作数的某种操作关 系 ,或某种特殊数学规律 ;操作数 :是指由数字、英文 字母、希腊字母等代数符号构成 ,在数学公式中表示 数量、变量等含义. 根据符号的类型可选用对应的语 法规则进行深入的子表达式分析. 本文研究工作针对正体 /斜体英文字字母、数 字、标点、希腊字母、数学符号、三角函数共计 220个 字符 ,覆盖了科技文献中所有数学公式的常用字符. 1. 2. 3 数学公式的语法规则 语法规则规定了数学公式中字符的语法属性 , 以及不同符号间的语法约束与组合关系. 对数学公 式的分析过程中 ,语法规则具有如下作用 : 字符语法属性分类. 语法规则可以通过对字符 间空间关系的判断 ,确定字符的惟一语法属性. 图 4 描述了对“ + ”进行语法判断的过程. 组合“子表达式 ”(定义见 2. 3节 ). 语法规则可 以通过作用域信息 ,将具有组合规则的运算符与其 附属字符合并 ,成为一个子表达式. 语法规则验证. 结合识别结果和版面信息 ,语法 规则还可以用来纠正识别错误、消除多语义字符的 语法歧义、实现对树结构的校验和修改. (详见 2. 5节 ) 图 4 利用语法规则确定字符属性 Fig. 4 Check the grammar attributes by grammar rules 1. 2. 4 数学公式的句法规则 不同类型表达式的组合形成了多重层次的数学 公式结构 ,同层次操作符之间的优先级关系决定了 数学公式的计算顺序. 句法规则描述每个操作符的子表达式形成规 则 ,每一个操作符都有一个固定的树型结构模板 ,其 中子结点的个数和属性均根据语法规则预先填充. 图 5描述了根据句法规则中不同的优先级关系生成 的不同子表达式结构. 句法规则同时负责判断操作符之间的优先级 , 采用“相对优先级 ”的形式设计了包含所有操作符 的矩阵结构 ,任意 2个操作符均可通过查找矩阵以 确定哪个操作符的优先级更高. 图 5 优先级比较示例 Fig. 5 Samp le of p riority comparison 1. 3 结构分析底层知识库 以上提到的四元组是结构分析的直接依据. 通 过前期大量的统计工作 ,对数学公式符号的操作属 第 5期 史广顺 ,等 :数学公式图像的结构理解与重现 ·403·
·404· 智能系统学报 第3卷 性、语法属性、组合关系、操作符优先级、目类型等进 个处理对象，跳至1)，循环重复，直至结构分析完 行了统计分类与描述.同时，定义了底层知识库，用 成 于以上各类规则和信息的存储.知识库的内容如图 采用以上算法，数学公式图像的识别结果可以 6所示。 被组织成遵循计算顺序的树型结构 符号 22版面分析技术的应用 符号图像 符号内容 算法1的1)需要通过版面分析以确定属于第1 信总 层次的操作符.可利用的版面信息包括：操作符的 知 符号的操作属性 HCL、符号的大小、表达式图像外接矩形的水平中心 语法 符号的语法属性（即符号的类别） 识 坐标等」 规则 符号语法屈性的判定规则 符号具有的组合关系 首先，将所有字符按照HCL的值进行聚类，得 库 到公式中所有骨干线信息；然后，挑选出具有最高优 句法 符号的目类型 子表达式的组合关系和判定规则 先级的骨干线作为当前分析层次对象 规则 操作符的优先级别 图7描述了提取公式y-。mxd.最高级 2a 图6底层知识库构成 别骨干层次的处理过程」 Fig 6 Structure ofmathematical knowledge database 公式图像：y sin.xdx Inx 知识库是为语法结构分析处理过程而建立的， 2a 版面信息分析 为结构分析提供重要的信息.同时，这种知识统一存 储与管理的方式，大大的增强了系统的可扩充性和 n 灵活性。 2a 2算法与关键技术 first level second level 基于数学公式结构描述规则库，可采用“自顶 :当前层次最小分析单元 一：骨干区域 向下的处理流程对数学公式的结构进行迭代式的 分析.首先通过版面信息找到公式的核心骨干层次， 图7版面结构分析 Fig 7 Layout structure analysis 然后利用语法和句法规则将该层次转换为一棵能反 映公式正确计算顺序和结构的句法树.当该层次全 23子表达式提取 部分析完成，再从公式中找到次级核心骨干层次，对 定义子表达式：由一个或多个当前层次运算符 句法树进行扩充.不断重复这一过程，直到公式结构 与其附属字符组合而成，例如图6公式中的 分析全部完成： 。xd和，分别是以积分号和分数线为核心 21数据结构设计与核心处理算法 2a 本文采用树型结构描述数学公式，每一个操作 操作符的子表达式.组合后的子表达式在当前的运 符的树型结构都是与其对应的句法规则的一个 算层次的属性为操作数.因此，在句法结构分析之 实例 前，根据语法规则提取子表达式，可以有效筛选出公 式核心操作符，避免附属操作符对公式计算顺序的 本文方法的处理流程描述如下： 影响，保证公式结构的准确性.根据数学公式的阅读 算法1： 初始状态：处理对象为公式中所有符号.创建空 顺序（从左至右），对所有当前层次的操作符应用语 的根结点 法规则，执行以下算法： 1)进行版面分析，提取第1层次的所有字符： 算法2： 2)应用语法规则，确定核心操作符集； 输入：核心骨干层次字符集(L0S),包含公式 经版面信息分析提取出的所有处于第1层次的 3)应用句法规则，判断操作符的优先级，按优 字符 先级将核心操作符的子表达式结构填充到结构树 中 1)依据字符左边界X坐标值，从左至右排列所 4)选择公式中次高级别的骨干层次作为下一 有字符； 1994-2009 China Academic Journal Electronie Publishing House.All rights reserved.http://www.cnki.net
性、语法属性、组合关系、操作符优先级、目类型等进 行了统计分类与描述. 同时 ,定义了底层知识库 ,用 于以上各类规则和信息的存储. 知识库的内容如图 6所示. 图 6 底层知识库构成 Fig. 6 Structure of mathematical knowledge database 知识库是为语法结构分析处理过程而建立的 , 为结构分析提供重要的信息. 同时 ,这种知识统一存 储与管理的方式 ,大大的增强了系统的可扩充性和 灵活性. 2 算法与关键技术 基于数学公式结构描述规则库 ,可采用“自顶 向下 ”的处理流程对数学公式的结构进行迭代式的 分析. 首先通过版面信息找到公式的核心骨干层次 , 然后利用语法和句法规则将该层次转换为一棵能反 映公式正确计算顺序和结构的句法树. 当该层次全 部分析完成 ,再从公式中找到次级核心骨干层次 ,对 句法树进行扩充. 不断重复这一过程 ,直到公式结构 分析全部完成. 2. 1 数据结构设计与核心处理算法 本文采用树型结构描述数学公式 ,每一个操作 符的树型结构都是与其对应的句法规则的一个 实例. 本文方法的处理流程描述如下 : 算法 1: 初始状态 :处理对象为公式中所有符号. 创建空 的根结点. 1)进行版面分析 ,提取第 1层次的所有字符 ; 2)应用语法规则 ,确定核心操作符集 ; 3)应用句法规则 ,判断操作符的优先级 ,按优 先级将核心操作符的子表达式结构填充到结构树 中 ; 4)选择公式中次高级别的骨干层次作为下一 个处理对象 ,跳至 1) ,循环重复 ,直至结构分析完 成. 采用以上算法 ,数学公式图像的识别结果可以 被组织成遵循计算顺序的树型结构. 2. 2 版面分析技术的应用 算法 1的 1)需要通过版面分析以确定属于第 1 层次的操作符. 可利用的版面信息包括 :操作符的 HCL、符号的大小、表达式图像外接矩形的水平中心 坐标等. 首先 ,将所有字符按照 HCL的值进行聚类 ,得 到公式中所有骨干线信息 ;然后 ,挑选出具有最高优 先级的骨干线作为当前分析层次对象. 图 7描述了提取公式 y = ∫ d 0 sinxdx - lnx 2a 最高级 别骨干层次的处理过程. 图 7 版面结构分析 Fig. 7 Layout structure analysis 2. 3 子表达式提取 定义子表达式 :由一个或多个当前层次运算符 与其 附 属 字 符 组 合 而 成 , 例 如 图 6 公 式 中 的 ∫ d 0 sin xdx和 lnx 2a ,分别是以积分号和分数线为核心 操作符的子表达式. 组合后的子表达式在当前的运 算层次的属性为操作数. 因此 ,在句法结构分析之 前 ,根据语法规则提取子表达式 ,可以有效筛选出公 式核心操作符 ,避免附属操作符对公式计算顺序的 影响 ,保证公式结构的准确性. 根据数学公式的阅读 顺序 (从左至右 ) ,对所有当前层次的操作符应用语 法规则 ,执行以下算法 : 算法 2: 输入 : 核心骨干层次字符集 (FLOS) ,包含公式 经版面信息分析提取出的所有处于第 1 层次的 字符. 1)依据字符左边界 X 坐标值 ,从左至右排列所 有字符 ; ·404· 智 能 系 统 学 报 第 3卷
第5期 史广顺，等：数学公式图像的结构理解与重现 ·405· 2)从LOS中提取第1个操作符，定义为A; 特殊的编译器将其转换为可直接运行的计算代码， 3)在知识库中查询A的语法规则： 将在后续的论文中描述这种方法 4)若A有多个语法属性，则结合版面信息判 定，得到A的惟一语法属性； 3语法规则对结果的校验 5)若A具有组合规则，则根据作用域，将所有 3.1识别结果校验 附属于A的字符合并，形成以A为核心运算符的子 在数学公式的符号识别结果中可能包含识别错 表达式；否则，跳至7)； 误，利用语法规则中的约束条件，可以发现并消除部 6)将被组合的操作符从HLOS中删除，子表达 分识别错误，本文设计了以下几类容错处理： 式作为新的操作数； 1)字母和数字的拼写检查：‘0'和‘o’,‘1'和 7)在LOS中提取下一个操作符，跳至3)， ‘1'非常容易混淆.但是如果出现‘c0s’,则根据函数 经过以上处理步骤，在OS中留下的操作符 名拼写规则应将其改为‘c0s';在数字串中如果出现 就是第1层次的核心操作符，可根据它们进一步建 字母，也可以将其改为形式相似的数字.图9(a). 立数学公式的句法结构框架 公式原形：cosx 24句法结构树的生成 函数名合并 得到核心操作符集(Coe-L0S)之后，首先，利 识别结果：)=C0sx Jy=Co图x 用知识库中的句法规则，对第1层次核心操作符进 语法规则对字符识 上下标语法规则匹 行优先级比较、公式结构拆分、子表达式拆解等句法 别结果进行校验 配不一致！错误！ 结构分析，得到当前层次的句法树；然后，提取公式 校险结果：一C0s 的下一层次字符，重复算法1，直到生成一棵完整的 公式结构树 (a)利州语法规则纠正字符识别错误 图8完整描述了图7中公式的结构分析过程， 处理结果被保存在结构树之中 公式原形：∑a+b) Σ子表达式树结构 层次核心运算符集 法结构树 分析结果：∑a+b) n 语法规则对公式 结构进行校验 上下标语法规则匹 配不一致！错误！ 校验结果：∑（a+b) 1 (b)语法规则对子表达式树结构的校验 sin.d 图9语法规则的验证功能 Fig 9 Grammar ambiguity elm inate ⑧ In,X 2)约束条件的错误修正.对定界符‘('和‘)' 包回 而言，识别结果可能是‘['或‘]’，根据符号的组合 规则与约束条件，可以利用上下文信息进行可信度 图8句法结构分析过程示例 验证，从而修正其识别错误 Fig 8 Sample of syntactic analysis 32语法消歧 在数学公式中存在很多有歧义的运算符，消除 25结构重现与格式转换 歧义是分析数学公式结构的重要技术.本文设计的 在获得如图8所示的数学公式结构树之后，可 语法规则中包含一项约束条件，其用途就是消除运 以非常容易的将其转换为Latex格式或MaML格 算符的语法歧义 式 约束条件包含以下几项内容： 本文方法不仅可以实现版面结构的重现，同时 1)运算数的个数与位置.如123节中图4所 可以快速的将数学公式结构导入到各种编辑器之 示，以“+为例，当其左右两侧均出现运算数或其 中，结构树中蕴涵的语法信息和句法信息均可通过 他子表达式时，说明它是四则运算符.当只有其右侧 1994-2009 China Academie Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
2)从 FLOS中提取第 1个操作符 ,定义为 A; 3)在知识库中查询 A的语法规则 ; 4)若 A 有多个语法属性 ,则结合版面信息判 定 ,得到 A的惟一语法属性 ; 5)若 A 具有组合规则 ,则根据作用域 ,将所有 附属于 A的字符合并 ,形成以 A 为核心运算符的子 表达式 ;否则 ,跳至 7) ; 6)将被组合的操作符从 FLOS中删除 ,子表达 式作为新的操作数 ; 7)在 FLOS中提取下一个操作符 ,跳至 3). 经过以上处理步骤 ,在 FLOS中留下的操作符 就是第 1层次的核心操作符 ,可根据它们进一步建 立数学公式的句法结构框架. 2. 4 句法结构树的生成 得到核心操作符集 (Core2FLOS)之后 ,首先 ,利 用知识库中的句法规则 ,对第 1层次核心操作符进 行优先级比较、公式结构拆分、子表达式拆解等句法 结构分析 ,得到当前层次的句法树 ;然后 ,提取公式 的下一层次字符 ,重复算法 1,直到生成一棵完整的 公式结构树. 图 8完整描述了图 7中公式的结构分析过程 , 处理结果被保存在结构树之中. 图 8 句法结构分析过程示例 Fig. 8 Samp le of syntactic analysis 2. 5 结构重现与格式转换 在获得如图 8所示的数学公式结构树之后 ,可 以非常容易的将其转换为 Latex格式或 MathML格 式. 本文方法不仅可以实现版面结构的重现 ,同时 可以快速的将数学公式结构导入到各种编辑器之 中 ,结构树中蕴涵的语法信息和句法信息均可通过 特殊的编译器将其转换为可直接运行的计算代码. 将在后续的论文中描述这种方法. 3 语法规则对结果的校验 3. 1 识别结果校验 在数学公式的符号识别结果中可能包含识别错 误 ,利用语法规则中的约束条件 ,可以发现并消除部 分识别错误 ,本文设计了以下几类容错处理 : 1)字母和数字的拼写检查 :‘0’和‘o’,‘1’和 ‘l’非常容易混淆. 但是如果出现‘c0 s’,则根据函数 名拼写规则应将其改为‘cos’;在数字串中如果出现 字母 ,也可以将其改为形式相似的数字. 图 9 ( a). 图 9 语法规则的验证功能 Fig. 9 Grammar ambiguity elim inate 2)约束条件的错误修正. 对定界符‘( ’和‘) ’ 而言 ,识别结果可能是‘[ ’或‘]’,根据符号的组合 规则与约束条件 ,可以利用上下文信息进行可信度 验证 ,从而修正其识别错误. 3. 2 语法消歧 在数学公式中存在很多有歧义的运算符 ,消除 歧义是分析数学公式结构的重要技术. 本文设计的 语法规则中包含一项约束条件 ,其用途就是消除运 算符的语法歧义. 约束条件包含以下几项内容 : 1)运算数的个数与位置. 如 1. 2. 3节中图 4所 示 ,以“ + ”为例 ,当其左右两侧均出现运算数或其 他子表达式时 ,说明它是四则运算符. 当只有其右侧 第 5期 史广顺 ,等 :数学公式图像的结构理解与重现 ·405·
·406- 智能系统学报 第3卷 存在操作数和子表达式时，说明它是符号运算符」 除此之外，为了验证系统的容错性，对200个数 2)与其他运算符的组合关系.以“（为例，当其 学公式图像的识别结果进行了人工修改，得到带有 右侧出现“]”咀两者之间存在“，时，说明它是一个 噪音和误差的评测样张集，进行系统容错性测试.测 区间描述符“(，]”：当不存在“，时，它应该被理 试结果如表2所示.综合2类测试结果，应用本文提 解为一个定界运算符 出的结构分析方法，可以有效提高结构分析的正确 通过定义一系列的约束条件，可以准确地分析 性和稳定性，更好的满足各类应用的需求 每个符号的语法属性，并根据约束条件和组合关系 提取子表达式 表1结构分析测试结果 3.3句法树结构校验 Table 1 The results of syntactic ana lysis 子表达式树反映了对应公式的句法结构.由于 公式 样张 子表达 结构 平均准确率 识别及版面结构分析的误差，有可能使树结构变形， 复杂度 ●数量 式完整 正确 1 从而无法正确表达公式的信息.应用语法规则，可以 150 150 150 1.000 400 399 398 0996 通过必要条件是否存在，来判断拆分的正确性，对错 276 269 253 0946 误情况依据语法规则进行修正，得到准确的子表达 6 89 8 79 0910 式结构.图9(b)描述了对子表达式结构树的校验 7-12 85 75 64 0817 过程 Total 1000 976 944 0960 4实验 表2容错性测试结果 Table 2 The results of fault-tolerant 为验证本文研究工作的有效性，共选择使用了 500个公式样本作为训练样本.从EEE Transactions 错误类型 样张数量 纠正数量 平均纠正率 识别错误 100 82 0820 及其他学术期刊中扫描制作了500页文档图像，并 结构错误 100 85 0850 将这些图像中包含的7610个数学公式作为评测样 Total 200 167 0835 本.在评测样本中，包含90913个公式符号，覆盖了 本文使用字符集中的所有符号.由于尚无有效的数 5 学公式结构分析自动评测工具，因此采用人工观察 结论 的方法对1000个评测样本进行了性能评价.结构分 本文的研究工作，将句法结构、语法规则、版面 析的评测参数设计如下： 分析相互结合，更加完整的理解数学公式.与目前同 1)子表达式内容完整性.子表达式（一级核心 类方法相比，主要有以下方面的优点： 运算符)是否能够正确提取，语法约束元素是否能 1)定义了完整的数学公式句法结构模型，明确 够正确提取； 定义了语法规则和句法规则，可以更加准确地对数 2)句法结构正确性.公式的计算顺序是否描述 学公式进行描述和分类； 正确，子表达式的句法结构是否正确有效； 2)首次提出底层知识库概念，系统地总结、归 3)系统容错性.对于图像噪音造成的误识结果 纳并分类存储了大量先验数学属性和规则，为公式 是否能够删除，对于符号误识结果是否能够修正」 结构分析提供直接依据； 采用IMit提出的方法，以句法层次数目作 3)采用HCL聚类的骨干线提取方法，通过多参 为评价公式复杂性的标准.并按照版面结构复杂度 数确定骨干区域，提高了骨干层次划分的稳定性； 对测试公式进行分类，进行测试.测试结果如表1所 4)采用句法规则驱动的结构分析方法，从结构 示.测试结果表明，本文介绍的句法结构分析方法适 分析的最初，加入验证信息，保证了公式结构分析的 用于多种类型的公式.特别的，对于占数学公式主体 正确性.同时该结构分析过程又可准确的理解数学 的中等复杂度公式，结构分析准确率得到了非常大 公式所表达的计算含义，为语义计算等高级应用提 的提升，平均准确率达到968%，高于目前同类系 供基础信息； 统平均水平(85%~92%).而对于复杂度较高的公 5)使用语法规则进行结果验证，极大地增强了 式，结构分析的准确率也得到了相应的提高，平均准 数学公式理解系统消除符号歧义校验错误的能力， 确率为817%，达到预期的目标 提高了分析的准确率与稳定性」 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.ne
存在操作数和子表达式时 ,说明它是符号运算符. 2)与其他运算符的组合关系. 以“(”为例 ,当其 右侧出现“]”且两者之间存在“, ”时 ,说明它是一个 区间描述符“( , ]”;当不存在“, ”时 ,它应该被理 解为一个定界运算符. 通过定义一系列的约束条件 ,可以准确地分析 每个符号的语法属性 ,并根据约束条件和组合关系 提取子表达式. 3. 3 句法树结构校验 子表达式树反映了对应公式的句法结构. 由于 识别及版面结构分析的误差 ,有可能使树结构变形 , 从而无法正确表达公式的信息. 应用语法规则 ,可以 通过必要条件是否存在 ,来判断拆分的正确性 ,对错 误情况依据语法规则进行修正 ,得到准确的子表达 式结构. 图 9 ( b)描述了对子表达式结构树的校验 过程. 4 实 验 为验证本文研究工作的有效性 ,共选择使用了 500个公式样本作为训练样本. 从 IEEE Transactions 及其他学术期刊中扫描制作了 500页文档图像 ,并 将这些图像中包含的 7 610个数学公式作为评测样 本. 在评测样本中 ,包含 90 913个公式符号 ,覆盖了 本文使用字符集中的所有符号. 由于尚无有效的数 学公式结构分析自动评测工具 ,因此采用人工观察 的方法对 1 000个评测样本进行了性能评价. 结构分 析的评测参数设计如下 : 1)子表达式内容完整性. 子表达式 (一级核心 运算符 )是否能够正确提取 ,语法约束元素是否能 够正确提取 ; 2)句法结构正确性. 公式的计算顺序是否描述 正确 ,子表达式的句法结构是否正确有效 ; 3)系统容错性. 对于图像噪音造成的误识结果 是否能够删除 ,对于符号误识结果是否能够修正. 采用 J. M itra [ 8 ]提出的方法 ,以句法层次数目作 为评价公式复杂性的标准. 并按照版面结构复杂度 对测试公式进行分类 ,进行测试. 测试结果如表 1所 示. 测试结果表明 ,本文介绍的句法结构分析方法适 用于多种类型的公式. 特别的 ,对于占数学公式主体 的中等复杂度公式 ,结构分析准确率得到了非常大 的提升 ,平均准确率达到 96. 8% ,高于目前同类系 统平均水平 (85% ～92% ). 而对于复杂度较高的公 式 ,结构分析的准确率也得到了相应的提高 ,平均准 确率为 81. 7% ,达到预期的目标. 除此之外 ,为了验证系统的容错性 ,对 200个数 学公式图像的识别结果进行了人工修改 ,得到带有 噪音和误差的评测样张集 ,进行系统容错性测试. 测 试结果如表 2所示. 综合 2类测试结果 ,应用本文提 出的结构分析方法 ,可以有效提高结构分析的正确 性和稳定性 ,更好的满足各类应用的需求. 表 1 结构分析测试结果 Table 1 The results of syn tactic ana lysis 公式 复杂度 样张 数量 子表达 式完整 结构 正确 平均准确率 1 150 150 150 1. 000 2～4 400 399 398 0. 996 5 276 269 253 0. 946 6 89 83 79 0. 910 7～12 85 75 64 0. 817 Total 1 000 976 944 0. 960 表 2 容错性测试结果 Table 2 The results of fault2toleran t 错误类型 样张数量 纠正数量 平均纠正率 识别错误 100 82 0. 820 结构错误 100 85 0. 850 Total 200 167 0. 835 5 结 论 本文的研究工作 ,将句法结构、语法规则、版面 分析相互结合 ,更加完整的理解数学公式. 与目前同 类方法相比 ,主要有以下方面的优点 : 1)定义了完整的数学公式句法结构模型 ,明确 定义了语法规则和句法规则 ,可以更加准确地对数 学公式进行描述和分类 ; 2)首次提出底层知识库概念 ,系统地总结、归 纳并分类存储了大量先验数学属性和规则 ,为公式 结构分析提供直接依据 ; 3)采用 HCL聚类的骨干线提取方法 ,通过多参 数确定骨干区域 ,提高了骨干层次划分的稳定性 ; 4)采用句法规则驱动的结构分析方法 ,从结构 分析的最初 ,加入验证信息 ,保证了公式结构分析的 正确性. 同时该结构分析过程又可准确的理解数学 公式所表达的计算含义 ,为语义计算等高级应用提 供基础信息 ; 5)使用语法规则进行结果验证 ,极大地增强了 数学公式理解系统消除符号歧义、校验错误的能力 , 提高了分析的准确率与稳定性. ·406· 智 能 系 统 学 报 第 3卷
第5期 史广顺，等：数学公式图像的结构理解与重现 ·407· 在今后的工作中，还要进一步研究如何分析并 [J].Computer Engineering.2006,32(23):202-204 提取数学公式的计算含义，同时对数学公式结构分 [7]GARA N U,CHAUDHUR IB B.A syntactic approach or 析方法的评价也将是重要的问题： processing mathematical expressions in printed documents [C]//Proceedings of 15th Intematonal Conference on Pat- 参考文献： tem Recognition Barcelona,Spain,2000:523-526 [8 M IIRA J,GARA N U,CHAUDHUR IB B.Automatic un- [1 ]CHEN Y,SHM I T,OKADA M.Fundamental study on derstanding of structures in printed mathematical expressions structural understanding of mathematical exp ressions[C]// [C ]//Proceedings of Seventh Intemational Conference on Proceedings of IEEE SMC 99 Conference Tokyo,Japan, Document Analysis and Recognition Edinburgh,Scotland, 1999:153-158 2003:540-544 [2靳简明.数学公式图像处理研究[D]天津：南开大学， 作者简介： 2003 史广顺，男，1978年生，副教授，硕 JN Jianming Research on typesetmathematical expression- 士生导师，先后负责省部级科研项目4 mage processing[D]Tianjin:NankaiUniversity,2003. 项，参与省部级与国家级科研项目10 余项.主要研究方向为模式识别与机器 [3 ]GUO Yusheng.HUANG Lei,LU Changping A new ap- 智能、数字图像处理、自然语言理解、软 proach or understanding of structure of printed mathemati- 件开发技术 cal expression[C]//Proceedings of the 6th Intemational Conference on Machine Leaming and Cybemetics HongKong,China,2007:19-22 肖萃，女，1984年生，硕士研究 [4 ]LAV ROTTE S,POTTIER L Mathematical fomula recogni- 生，主要研究方向为文档图像处理、模 tion using graph grammar[J]Document Recognition V, 式识别 1998,3305:44-52 [5田学东，王文姣.基于综合纠错的印刷体数学公式识别 后处理[J1计算机工程与设计，2007,28(20)：5039- 5041 王庆人，男，1965年生，教授，博士 TAN Xuedong,WANG Wenjiaa Postprocessing for prin- 生导师.1989年创造性的实现基于熵分 ted omula based on synthetic eror correction[J].Comput- 类的0CR引擎，并于1992~1994连续 er Engineering and Design,2007,28(20):5039-5041. 3年获得美国UNLV全球析与OCR评 [6田学东，李娜，徐丽娟.印刷体数学公式结构分析方 比冠军.先后承担国家级、省部级项目 法的研究[J].计算机工程，2006,32(23)：202-204 20余项，主要研究方向为模式识别与机 TAN Xuedong.LINa,XU Lijuan Research on structural 器智能.发表EEE期刊论文10余篇， analysis ofmathematical exp ressions in printed documents 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
在今后的工作中 ,还要进一步研究如何分析并 提取数学公式的计算含义 ,同时对数学公式结构分 析方法的评价也将是重要的问题. 参考文献 : [ 1 ]CHEN Y, SH IM IZU T, OKADA M. Fundamental study on structural understanding of mathematical exp ressions[ C ] / / Proceedings of IEEE SMC ’99 Conference. Tokyo, Japan, 1999: 1532158. [ 2 ]靳简明. 数学公式图像处理研究 [D ]. 天津 : 南开大学 , 2003. J IN Jianm ing. Research on typesetmathematical exp ression2 image p rocessing[D ]. Tianjin: Nankai University, 2003. [ 3 ] GUO Yusheng, HUANG Lei, L IU Changp ing. A new ap2 p roach for understanding of structure of p rinted mathemati2 cal exp ression [ C ] / / Proceedings of the 6 th International Conference on Machine Learning and Cybernetics. HongKong, China, 2007: 19222. [ 4 ]LAV IROTTE S, POTTIER L. Mathematical formula recogni2 tion using graph grammar [ J ]. Document Recognition V, 1998, 3305: 44252. [ 5 ]田学东 , 王文姣. 基于综合纠错的印刷体数学公式识别 后处理 [J ]. 计算机工程与设计 , 2007, 28 ( 20) : 50392 5041. TIAN Xuedong, WANG W enjiao. Post2p rocessing for p rin2 ted formula based on synthetic error correction[J ]. Comput2 er Engineering and Design, 2007, 28 (20) : 503925041. [ 6 ]田学东 , 李 娜 , 徐丽娟. 印刷体数学公式结构分析方 法的研究 [J ]. 计算机工程 , 2006, 32 (23) : 2022204. TIAN Xuedong, L INa, XU L ijuan. Research on structural analysis of mathematical exp ressions in p rinted documents [J ]. Computer Engineering, 2006, 32 (23) : 2022204. [ 7 ] GARA IN U, CHAUDHUR I B B. A syntactic app roach for p rocessing mathematical exp ressions in p rinted documents [C ] / / Proceedings of 15 th International Conference on Pat2 tern Recognition. Barcelona, Spain, 2000: 5232526. [ 8 ]M ITRA J, GARA IN U, CHAUDHUR IB B. Automatic un2 derstanding of structures in p rinted mathematical exp ressions [C ] / /Proceedings of Seventh International Conference on Document Analysis and Recognition. Edinburgh, Scotland, 2003: 5402544. 作者简介 : 史广顺 ,男 , 1978年生 ,副教授 ,硕 士生导师 ,先后负责省部级科研项目 4 项 ,参与省部级与国家级科研项目 10 余项. 主要研究方向为模式识别与机器 智能、数字图像处理、自然语言理解、软 件开发技术. 肖 萃 ,女 , 1984年生 ,硕士研究 生 ,主要研究方向为文档图像处理、模 式识别. 王庆人 ,男 , 1965年生 ,教授 ,博士 生导师. 1989年创造性的实现基于熵分 类的 OCR引擎 ,并于 1992～1994连续 3年获得美国 UNLV全球析与 OCR评 比冠军. 先后承担国家级、省部级项目 20余项 ,主要研究方向为模式识别与机 器智能. 发表 IEEE期刊论文 10余篇. 第 5期 史广顺 ,等 :数学公式图像的结构理解与重现 ·407·