·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卷