一种印刷体数学公式优化提取策略.pdf

1 4 62 0 1 0 4 6 1 5 c o 唧妇rE 画 l e e 魄口以A p P 坛m 如瑚计算机工程与应用 一种印刷体数学公式优化提取策略 张灿龙 唐艳平 王强 韦春荣 z H A N Gc a n l o n 9 1 T A N GY a n p i n 酽 w A N GQ i a n 9 1 w E Ic h u n r o n 9 1 1 广西师范大学计算机科学与信息工程学院 广西桂林5 4 1 0 0 4 2 桂林电子科技大学材料科学与工程学院 广西桂林5 4 1 0 0 4 3 上海交通大学航空航天学院 上海2 0 0 2 4 0 1 C o l l e g eo fC o m p u t e rS c i e n c ea n dI n f o 姗a t i o nE n g i n e e T i n g G u 跏鲥N o 瑚a lU n i V e 璐i t y G u i l i n C u 锄g x i5 4 1 0 0 4 C h i 眦 2 s c h o o lo fM a t e r i a lS c i e n c ea I l dE n 舀鹏e r i n g G u i l i nU n i v e 玛竹o fE l e c 呐n i cT e c h n o l o g y G u i l i n G u a n g i5 4 1 0 0 4 C h i m 3 s c h o o lo fA e 啪a u t i c s A s 仃o n 粕t i c s s h a J l g h a jJ i a o t o n gU n i V e r s i t y S h a n 曲a i2 0 0 2 4 0 C h i 腿 E m a i l z c l t y p 1 6 3 c o m Z H A N GC 蛆一I o n g T A N GY 姐一p h l g W A N GQ i a I l g e ta 1 p r i n t e dm m e m a t i c a le x p r e s s i o 璐麟t r a c 伽nm e t h o db a s e d 伽 I C S A S V Ma n dK L 衄l n s f o m C 咖p u t e rE n g i n r i I 嚷a n dA p p 壮 协璐 2 0 l O 4 6 1 5 1 4 6 1 4 9 A b s 竹a c t An e w 印p m a c hf o r8 e p 啪t i n gb o t hi l a t e d 粕de I I l l e d d e de x p r e 昭i o mi np r i n t e dC h i n e t e c h n i c a l 如c u m e n 协i s p r e s e n t e d w h i c hi n c l u d e 8t w os t e p s l i n ec l a s s i f i c a t i o na n 一8 y m b o lr e c o g n m I n 山ea p p r o a c h K L a n s f b 咖i g 印p l i e dt o e l i m i 一 瑚岫i n t e e l a t i o n 枷o I I gl i n ef e a t l l r e s 绷de x t r a c t 呷b o lf e a t u T e s 龃di 咖u 眦c 1 0 n es e l e c t i o na l g 面t h mi 8u s e dt oo p t i m i z ep a 咖e t e r so fl i 耻c l 器8 i f i e r 锄ds y I l l b o lc l a s s m e rb 酗e do ns u p p o r tv e c t o rm a c h i n e T h et e s t i n gr e s u l tt oa b o u t3 0 0p r i n t e dC h i n e 鹋 妣h n i e a d o c u m e n t si n d i c a t e st h a t I l ee x p 孢s s i 伽se x 妇c t i 锄a c c u r a c yi s9 4 a b o v e K e yw o r d s p r i n t e dm a t h e m a t i c a le x p r e 8 s i o n 叫p p o r tv e c t o rm c h i 舱 K L 仃a n s f 0 肌 I 哪u n eC l o n eS e l e c t i o n 摘要 提出了一种先版面行分类后符号识别的印刷体数学公式提取策略 策略中两次应用K L 变换 分别完成版面行特征的降 维和公式符号特征的提取 并采用免疫克隆选择算法优化支持向量机的训练参数 以构建出最优的版面行分类器和公式符号识别 器 通过对3 0 0 多份印刷体中文科技文档进行扫描识别测试 所得结果的公式提取率可达9 4 以上 关键词 印刷体数学公式 支 持向量杌 K L 变换 免疫克隆选择 D o I 1 0 3 7 7 8 j i s s n 1 0 0 2 8 3 3 1 2 0 1 0 1 5 0 4 3文章编号 1 0 0 2 8 3 3 l 2 0 1 0 1 5 一0 1 4 6 0 4文献标识码 A中图分类号 7 n 3 9 1 4 l 数学公式是科技文献中的重要组成部分 因为数学公式中 包含 些特殊的符号如希腊字母 英文字母 运算符和数字 并 具有特殊的结构 它的自动识别或手工输入往往比普通文字要 困难得多 若能将扫描图像中的数学公式自动识别成文本格 式 会对现有印刷体图书资料文献的数字化以及这些资源的网 上交流与共享产生深刻的影响 一般地 印刷体数学公式识别系统包括公式区域提取 公式符号分割与识别 公式结构分析 公式重构与转换等过 程 其中公式区域提取是整个系统的基础环节 现有提取方 法j l q 大多只能处理独立行的公式 简称 独立公式 而有关 内嵌于版面行中公式 简称 内嵌公式 提取的研究还很欠 缺 这主要是因为相对于独立公式具有结构松散 独立成行 区域较大以及汉字出现概率很小等明显特征而言 内嵌公式 往往和汉字混排在一起 且个数和位置的随机性较大 与纯 文本行之l 日 的区别不太明显 对其提取十分困难 国外一些 文献采用符号识别的方法I p 5 实现内嵌公式的提取 但这些方 法需要对文档中所有符号逐一进行匹配 时间开销过大 抽 取结果还受符号识别效果的限制 且不太适合处理符号模式 较多的中文文档 针对以上问题 通过引入K L 变换 支持向量机和免疫克 隆选择等理论 提出了一种先版面行分类后符号识别的公式区 域提取策略 即首先构建 个基于免疫克隆选择型支持向量机 S u p p o nV e c t o rM a c h i n eB a s eo nI 咖u n eC l o 北 S e l e c t i 彻 A l 舯r i t h m 简称I C S A s v M 的行分类器 将版面行分成纯文本 行 只含普通字符 内嵌公式行 普通字符和公式混排 和独立 公式行 只含公式 三类 然后 对归类后的公式行再采用符号 识别的方法进行公式提取 由于只对公式行进行符号识别 所 以这一策略的采用缩小了符号识别的范围 从而提高了公式区 域的提取速度 K L 变换 I c s A s v M 方法的引入 较大地提升 了公式提取的准确度 文章将详细讨论版面行抽取与符号分 割 特征计算与优化 分类器设计 并给出详实的实验数据和结 果分析 基金项日 广西壮族自治区科技厅基金项目 桂科基0 6 4 0 0 6 7 广西师范大学青年骨干教师基金项目 师政科技f 2 0 0 9 p 号 作者简介 张灿龙 1 9 7 5 一 男 博士生 讲师 研究领域为模式识别与智能系统 唐艳平 1 9 7 7 一 女 讲师 研究领域为计算机应用 王强 1 9 5 2 一 男 博士 教授 研究领域为模式 识别与智能系统 韦春荣 1 9 7 5 一 女 讲师 研究领域为图像处理与模式识别 投稿日期 2 0 0 9 一1 2 0 8惨回日期 2 0 l 咖3 一1 7 万方数据 张灿龙 唐艳平 王强 等 一种印刷体数学公式优化提取策略2 0 1 0 4 6 1 5 1 4 7 1 版面行抽取与符号分割 对扫描文档的二值化 去噪 倾斜矫正等处理已有许多成 熟的算法 因此不再详述 以下讨论均假设图像已经过上述 处理 1 1 版面行抽取与合并 版面行抽取的目的是找出图像中所有的版面行 其抽取算 法的好坏直接影响到行特征的计算和公式行的定位 采用水平 投影法f q 对版面行进行了初步抽取 基本思路是首先计算整个 版面水平方向的黑点密度直方图 并根据直方图谷底 实为行 间空白 将版面行抽取出来 再剔除行首和行尾空白 可得到初 步抽取结果 但由于数学公式结构的二维性 会使得某些具有上下结构 的公式被错误地分成两行 因此必须按照某种规则将它们合并 成一行 通过考察行间距发现被错分行之间的距离d 要远小于 整个文档的平均行I 日J 距比 以此为依据 经统计得到一个合并 阈值6 若d 膨 面且两行的行高差大于某阈值 则将这两行进 行合并 合并结果如图l 所示 图中求和号 与其下限 s o 在初步抽取结果中是被错分成了两行 由K a s i 等人楗出的主动轮癣横霉 是由 鲺控 盎v J 一丛螂 H 萱垦相连塑堡静轮嚏堡 枣 戌控瓴意上能量函数 I 一一一一 芦 s 扣x l p I s 6 x s l J 却 暇符予韵第一壤为斧性醒鼍 一第二j 9 蒲 萼曲 1 图1 版面行抽取结果 1 2 符号分割 符号分割是符号特征提取和公式区域定位的重要前提 目 前常用的方法有垂直投影澍6 和连通区域澍1 垂直投影法的基 本思想是对每个版面行计算其垂直方向的黑点密度直方图 并 根据直方图谷底 实为符号间距 将符号分割出来 该方法具有 运算快 符号整体定位性强等优点 特别适合分割汉字 但分割 像 n 一等含有子公式的符号时效果较差 连通区域法 的基本思想是找出整个图像的连通部件 并根据一定准则将各 部件进行组合 以实现符号分割 该方法的优点是能将不相连 的所有基元分离出来 适合处理英文符号 数学符号 但存在运 算慢 噪声敏感等缺点 不太适合处理笔画较多的汉字 将这两 种方法结合起来 扬长避短 经两次分割可将所有符号较好地 分离出来 采用垂直投影法对文档符号分割时 绝大部分汉字可被正 确地分离出来 但也有少数具有左右结构 且笔画分离的汉字 如 能 制 等字会被分成两部分 因此必须将其合并 合并准 则有两条 1 两符号框的I 日J 距z 妇 2 合并后的符号框高宽比 r 俨 其中占为字间距统计值 口为字高宽比统计值 可通过对当前版面行中的所有符号框的间距和高宽比作直方 图分析得到 另外 为了消除标点符号对版面行特征计算的影 响 可根据标点符号区域小 位置低等特点将其剔除 最终的处 理结果如图2 所示 由置 蠼厶睫出吲主勘彩帮模型是由一删 陶啦吣 M 曲 O M 苣屠隧碰城碰墩幽钱 定 g 腔俸嘣E 睦量西魏 矗 目 嘞e p 翻 研币酝 研 f 匕 d 膀圈币霸曛卜啧两弹强髓蛋 薷哿璁自坶朗嘲孺 图2 周投影法分帮符号的结果 图2 中公式区域的某些组成基元并没有被分割出来 因 此 必须采用连通区域法对其进行二次分割 为了避免二次分 割对已分离汉字的影响 在采用连通区域法之前必须根据汉字 的某些特征将其排除在外 1 同一行中大部分汉字的字高与 字宽近似相等 2 同一行中相邻两个汉字的中心距基本相等 3 同一行中大部分汉字的面积值会处在同 特定区间 二次 分割后 公式中的大部分基元已被正确地分离出来了 但还存 在两个问题 1 号一般会被分割成上下两部分 可通过计 算它们的相似度Q k 哪 一h I 哪 I 3 加以合并 其中 茗几埘对应于字符框的左横坐标 高度 宽度 对 号而言 其 Q 值近似为零 2 粘连符号无法分割 当数学符号具有上 下 标时 出现符号粘连的可能性比较大 这个问题目前还无法解 决 图3 是二次分割的最终结果 由K a s s 等人提出的主动轮寰筷犟是由一组控 崩点 钧 目 J 盈 首尾相连构成的轮寮线 定 义控饲点上能量函数 l 口E 鄹咄 习细暂 日 0 l I 田矗x 1 0 西b 积分中魄第一瑷为弹性腿 第二瑷为弯曲能量 图3 用连通区域法分翻符号的结果 2 基于K L 变换的特征计算与优化 个好的分类器是建立在有效特征的基础之上 K L 变换 是一种基于均方误差最小的最优正交变换嘲 被广泛应用于特 征提取与优化 其基本过程是计算由训练样本集构造的产生矩 阵三的本征值和本征向量 并对本征值按降序排列 取前d 个 最大本征值所对应的本征向量构成变换阵对特征向量进行正 交变换 设协l 是带类别标签触 扛l 2 c 的训练样本集 则 二兰 P 埘 研 工1 峨 工叫 7 j 劬 1 l I d 丸 乒 A 1 A 2 A 口 2 丸 I l y 矿工 3 y 工 3 其中 P 蛾 拍分别为第i 类样本集的先验概率和均值向量 f 为信息量 队 u 础 珈 为变换阵 本征值A 对应的本征向 量为巩 y 为变换后的特征向量 不同含义的工可以实现不同 的K L 变换目标 在版面行分类阶段 工 仁D 一 蠢 西 A 表示 个版 面行特征向量 它由行密度幼 字高方差盯 字宽方差t 字 底线高方差蠢 相邻字间的中心距离方差矿以及行规则度A 六部分组成 此时K L 变换用于消除善的各分量之间的相关 性 实现行特征降维 设第i 行 R e c f 耘 以 毗 鬼 第i 行的第 个符号 蝴e c 嘶 其中 R e c f 茗 彬 五 表示左上 角坐标为 z 宽度 高度分别为埘 7 l 的矩形框 则行特征的 计算公式如下 D 厶 堂娶 4 i X n i t t 川 i 他 成 5 t 1 1 研 巩 成 6 z 研 6 嗽 贰 7 万方数据 1 4 8 2 0 1 0 4 6 1 5 c o m p 眦r 西研凇e 矗 l gm dA P p 胁m 函船计算机工程与应用 矿 t 目 c 巩 8 A z 研 地 9 上面的公式中相只为行中黑点个数 撕为水平版面因子 为垂直版面因子锄为均值 研 l 表示求方差 在符号识别阶段 工表示符号的图像向量 此时K L 变换 可用来获得 个特征符号图片 通过对中国期刊全文库中近l 0 0 0 份科技文档进行统计分析 得到 个符号统计表1 表中共 有1 1 5 个符号 主要由大小写字母 阿拉伯数字以及数学符号 组成 它们在数学公式中出现频率较高 对这些符号的各种变 形图像做归一化处理 得到它们的标准图像 以这些标准图像 组成样本集忸 然后采用K L 变换提取各符号的特征 具体步 骤如下 表1 符号统计表 一 肌9 f n H一c p e 一 步骤l 按照公式 1 构造产生矩阵三 并计算其本征值丸 和本征向量毗 l 2 D D 为符号图像大小 步骤2 对A 按降序排列 综合考虑图像信息量f 和维数d 在识别率和识别时间上的平衡 取前d 个 组成正交变换阵 步骤3 按照公式 3 计算J 即为所要提取的符号特征 样本集 3 基于I C S A S v M 的分类器没计 印刷体数学公式提取是 个典型的小样本高维非线性分 类问题 基于结构风险最小化准则的支持向量机 s u p p o r t v e c t o rM a c h i n e 简称s v M 方法能很好地解决此类问题罔 s V M 的基本思想是 采用核运算方式将输入空间变换到高维空间 并在新空间中求取最优线性分类面 下面给出其最优判别函数 形式 髫 s 驴 i 咒K 薯 戈 6 i l 1 0 其中a i 为拉格朗日系数的最优解 6 是分类阈值 孔E 1 一1 l 为类别标号 置为支持向量 工为输入向量 s 为支持向量的总 数 K 魁 茗 为核函数 核函数形式有多种 采用高斯函数e x p 吖k 叫 f 作为核 函数 高斯核s V M 的主要参数有核因子y 与误差惩罚因子c 研究表明y 与c 的取值在很大程度上决定了分类器的性能 为 了得到最优的行分类器和符号识别器 采用免疫克隆选择算法 I m m u n ec l 衄es e l e c t i o nA l g o r i t I l m 简称I c s A 对参数7 与c 值进行优化选择 I C s A 是一种模仿自然免疫系统功能的智能寻优算法即 其 基本过程是将待优化问题看成抗原 问题的解看成抗体一 通过 抗体间的克隆 变异和选择 产生出可以捕获抗原的最佳抗体 使抗体 抗原亲和度 日 达到最大 其中涉及到以下几个主要 操作 设抗体群拈慨 如 鲫 n 为种群规模 克隆操作Z y 屉 贮 倪 i 鼠 矗 口 后 I m 譬盟塑业 i 巧 1 1 毋 后 卢l 其中 正为元素为1 的 维行向量 嘶 i n e x p 1 1 只 后 刮晟 I I 为抗体问的亲和力 变异操作疋 乞 j I y J p 4 1 p 其中 P 为变异概率 1 2 g 后 出I l 磊 i 一匕 纠0 f 为 抗体编码长度 y I 为e 七 的第 个克隆 选择操作Z 馥 后 1 Z 侥 后 日i 七 其中 B 矗 I m a 磊 l 若以只 詹 是当前抗体群 最优 贝0 佛 j 1 佛 否则 若 疋B k 砜最 J 则馥 后 1 鼠 后 否则 只 1 为两者的概率组合 优化问题可描述为在y 与c 的值域内寻找一组值 使得对 同一样本集 版面行样本集或符号样本集 以该组值为参数的 s v M 分类器的识别率最高 因此 抗体p 对应于 y c 亲和度 反口 对应于s v M 分类器的汉别率 最优版面行分类器或符号 识别器的设计步骤如下 s v M 训练机采用L j b s V M 步骤I 设儿c 的值域分别为厂 c 演化代数为后 o 演化 停止准则为7 1 并将特征样本集分成i l J l 练集和测试集两部分 步骤2 在y c 的值域内随机选取忍组值 形成初始解群 口 i 谚 I i M c 魄E 厂 c I E G 持l 2 n 步骤3 以且 后 作为s v M 训练机参数 调用L i b s V M 程序 对特征样本集进行训练和测试 得到识别率厂 最 j 亦即亲和 度值 步骤4 停机判断 若满足r 则输出最优参数对 y c 的 值 终止计算 否则 继续下一步 步骤5 按 1 1 式计算克隆规模口 I 并执行克隆操作贮 和变异操作瓦 得到变异解互 詹 步骤6 以磊 作为s v M 训练机参数 调用b b s V M 程序 对特征样本集进行i f f 练和测试 得到 厂 五 i 步骤7 执行选择操作 得到新的解群口 j 1 步骤8 后 1 返回步骤4 经以上步骤所得到的分类器称为基于I c s A S V M 的分类 器 由于s V M 参数的优化是基于实际样本集的 所以在计算出 最优参数对 7 c 的同时 也得到了最优的版面行分类器或 符号识别器 4 实验与分析 从中国期刊全文库中选取了2 9 0 页典型的文档 共计63 4 0 行 构成版面行分类实验样本集 对表l 中所列出1 1 5 个符号 各采集5 个样本 共5 7 5 张符号图片 作为符号识别实验的训 练样本集 每张图片均归一化为2 8 2 8 而测试集则来源于2 9 0 张文档图片中的数学公式 具体分配情况如表2 所示 表2 实验样奉集与最佳i 只刖率 口鹏 集测试集识别率训练集测试集识别率 纯文本行 2 5 1 6l6 7 89 5 6 数字 5 02 2 49 8 3 内嵌公式行 5 9 l3 9 5 9 5 3 字母2 3 1 59 8 5 独立公式行6 9 64 9 8 4 符号2 6 55 2 I9 7 4 总计38 0 325 3 79 6 1 总计5 7 5l0 6 09 7 9 万方数据 张灿龙 唐艳平 王强 等 一种印刷体数学公式优化提取策略2 0 1 0 4 6 1 5 1 4 9 图4 版面行的亭 町和 随d 变化的关系圈 d 图5 符号的f 刀和 随d 变化的关系图 图6 网格法中行分类器识别率与参数的关系图7网格法中符号分类器识别率与参数的关系 在K L 变换过程中 为了寻找 个合适的d 值 使信息量 f 识别率玑识别时间f 之问达到 个较好的平衡 测量了不同 d 值下的f 叼和t 得到了它们随d 变化的关系图 如图4 5 所 示 从图中可以看出 对分类和识别而言 特征信息量越大 相 应的识别率就越高 但由于原始特征向量的各分量问存在相关 性 使得在去相关的信息量足以完全表征原始特征中的有效信 息后 即使再增加信息量 对识别率的提高也没有多大贡献 并 且冗余的信息量加入反而会增加计算负担 使分类识别时间更 长 所以 从关系图中可以看出 对版面行分类和符号识别而 言 最佳的d 值应分别为4 和1 5 0 相应的信息量 识别率分别 为9 9 8 9 5 和9 2 3 9 3 3 上面的讨论只考虑了特征选取对识别率的影响 实际上 s V M 的参数也同样影响分类器的性能 因此 为了寻找一组最 佳的s V M 参数 使得识别率进一步提高 采用了I c s A 对参数 7 c 进行优化选择 取 2 2 c 2 2 并将其与传统 的网格遍历法进行对比 实验结果如图6 7 8 所示 从实验结 果来看I c s A s V M 能较快地收敛于最优参数 且所获得的识别 率明显高于网格遍历法 这主要归因于I c s A 的记忆寻优特性 即算法一旦发现了一个优良解 就会将其记录下来 并通过克 隆变异操作在该解附近寻找更优的解 同时 变异操作还可以 防止收敛结果陷入局部最优 而网格遍历法受网格密度的影 响 往往会错过最优位置 只得到次优解 版面行和公式符号的 I C s A s v M 最佳参数组合分别是 3 9 7 3 2 9 4 3 8 和 2 4 E 4 1 1 4 6 对应的识别率分别是9 6 4 和9 7 8 系统的总体识别结果如 表2 所示 由于独立公式行与其他两类版面行之间的区别比较 明显 而内嵌公式行与纯文本行之间的区别不大 所以独立公 式行的识别率要高于其他两类 演化代数 图8l c s s v M 识别率的优化过程 5 结论 论文主要讨论了一种对印刷体中文科技文档中的数学公式 进行提取的方法 该方法采用了先对版面行分类 再对归类后的 公式行进行符号识别的策略 从而克眼了对整个文档进行逐字识 别所导致的时间开销过大 识别率较低的缺点 K 乩变换 支持向 量机和免疫克隆选择等优化方法的采用 保证了所设计的版面行 分类器和符号识别器是最优的 实验结果也表明所设计的算法是 高效的 更有效的符号分割 特别是粘连符号分割方法是值得进 步探索的问题 论文的研究具有较强的实际应用价值 并对其 他从事相关领域研究的工作者也具有 定的参考价值 参考文献 1 田学东 郝楠 基于模糊分类的印刷体数学公式抽取方法叨 计算机 应用 2 0 0 7 2 7 8 2 0 3 6 2 0 6 5 2 常新峰 崔键 基于神经网络的印刷体数学公式抽取方法叨 计算机 应甩研究 2 0 0 8 2 5 1 1 3 4 8 3 3 4 8 5 3 C h a u d h u r iBB G a r a i nU A l l 卵p D o 聃hf o rD e c o 印i t i 蚰a n di m e 卜 p r e t a t i o no fm a t h e m a t i c a le 甲r e s s i o mi np r i m e dd o c u m e n t 册 P 8 t t 唧A n a l y 8 i 8 A p p b c 撕 舶2 0 0 0 3 1 2 0 1 3 1 4 G a n i nU C h 叫d h u r iBB C h a I I d h u r iAR I d e n t 洒c a t i o n0 fe m b e d d e dm 日山e r n a t i c B le x p r e 鹤i o 啮i n a e dd o c u m e n t s C T h e1 7 m I m e m a t i o n a lC o n f e