（课程与教学论专业论文）联机手写数学公式识别系统的研究与实现.pdf

摘要 摘要 随着计算机信息技术地飞速发展 现代信息技术运用于教育越来越受到人们的关注 近年来手写识别技术与产品广泛应用于教育教学领域之中 其中 数学公式识别成为近 年来兴起的研究热点 但是公式的识别比文字段落的识别困难 其原因在于数学公式具 有复杂的二维嵌套结构 并且公式符号含义具有多样性 这使得数学公式在结构分析方 面存在很多困难 联机数学公式识别系统主要包括三个组成部分 字符识别 公式结构分析 公式输 出 其中 结构分析的准确性直接影响公式输出的质量 是整个联机数学公式识别系统 的关键 本文第一章介绍了数学公式识别研究的背景 总结了数学公式识别的分类 介绍了 联机手写数学公式研究的现状和有关的产品 第二章中 作者重点介绍了模式识别技术 单个字符识别部分的主要算法 第三章中 阐述了公式识别的结构分析算法 错误纠正 最后 介绍了数学公式编 辑工具m a t h p l a y e r 第四章中 介绍自己怎么设计并实现联机手写数学公式识别系统 对一些关键技术 还提出了自己的见解并编写程序在p c 机上实现 在字符识别中 使用统计识别方法和神 经网络相结合的方法 建立分类器 大大节省了字符识别的时间 还加入了学习的功能 以便以后识别能力的扩展 在结构分析中 采用树转换的方法来分析数学公式的结构 实验表明 这种策略具有较好的适用性 在输出阶段 采用在应用程序中嵌套i e 控件 使用m a t h p l a y e r 实现公式的输出 这种方法有利于实现公式的再利用 在文章的末尾 阐述使用自己设计的联机手写数学公式识别系统时的实验结果 以及 自己设计的系统中存在的问题 作者对本文进行总结 并根据系统中存在的问题 提出 下一步的工作情况 关键词 联机手写数学公式识别 模式识别 字符识别 结构分析 a b s tr a c t w i t hr a p i dd e v e l o p m e n to fc o m p u t e ri n f o r m a t i o nt e c h n o l o g y p e o p l eb e g i nt o a p p l y t h e mt ot h ef i e l do fe d u c a t i o n s p e c i f i c a l l y h a n d w r i t i n gt e c h n o l o g ya n di t sp r o d u c t sa r e w i d e l yu s e di ne d u c a t i o n a lf i e l dd u r i n gt h el a s tf e wy e a r s r e c e n t l y t h er e s e a r c ht o w a r d st o a c c u r a t e r e c o g n i t i o no fh a n d w r i t t e nm a t h e m a t i c a le x p r e s s i o n sd r a w sm u c ha t t e n t i o n h o w e v e r t h er e c o g n i t i o no fh a n d w r i t t e nm a t h e m a t i c a le x p r e s s i o n si s g e n e r a l l ym o r e d i f f i c u l tw h e nc o m p a r e dt ot h er e c o g n i t i o no fh a n d w r i t t e nw o r d s s i n c em a t h e m a t i c a l e x p r e s s i o n so f t e nc h a r a c t e r i z e sw i t hc o m p l e xt w od i m e n s i o n a ll i n k i n gs t r u c t u r e s a n dm a n y m a t h e m a t i c a le x p r e s s i o n sc a nb eu n d e r s t o o di nm u l t i p l ew a y s t h e s em a k et h er e c o g n i t i o no f h a n d w r i t t e nm a t h e m a t i c a le x p r e s s i o n s e s p e c i a l l yd i f f i c u l t r e c o g n i t i o no fo n l i n eh a n d w r i t t e nm a t h e m a t i c a lf o r m u l ai sac o m p l e xp r o c e s s t h i s p r o c e s sc a nb ed i v i d e di n t ot h r e es t e p s s y m b o lr e c o g n i t i o n s t r u c t u r a l a n a l y s i s a n d e x p r e s s i o no u t p u t v e r a c i t yo fs t r u c t u r a la n a l y s i sh a sa ni m p o r t a n te f f e c to ne x p r e s s i o no u t p u t i ti sak e ys t e pi no n l i n eh a n d w r i t t e nm a t h e m a t i c a lf o r m u l ar e c o g n i t i o n c h a p t e r1i n t r o d u c e st h eb a c k g r o u n do ft h er e s e a r c h s u m m a r i z e st h ec l a s s i f i c a t i o no f m a t h e m a t i c a lf o r m u l ar e c o g n i t i o n a n dr a i s e ss o m et e c h n i c a ld i f f i c u l t i e s i ta l s oi n t r o d u c e s c u r r e n tr e s e a r c ha n dp r o d u c t st h a ta r er e l a t e dt ot h i st o p i c i nc h a p t e rt w o t e c h n o l o g yo fp a t t e r nr e c o g n i t i o nt e c h n o l o g ya n dt h em a i na l g o r i t h mo f s y m b o lr e c o g n i t i o na r ee x p a t i a t e dc a r e f u l l y i nc h a p t e rt h r e e t h ea u t h o rf o c u s e so ns t r u c t u r a la n a l y s i sa l g o r i t h ma n de r r o rc o r r e c t i o n a tl a s to ft h i sc h a p t e r t h ea u t h o ri n t r o d u c e st h em a t h e m a t i ce d i t o rm a t h p l a y e r i n t h ef o u r t h c h a p t e r t h ea u t h o rd e s c r i b e sh o wt od e s i g n a n di m p l e m e n to n l i n e h a n d w r i t t e nm a t h e m a t i c a lf o r m u l as y s t e m t h ea u t h o ra d v a n c e sh e ro p i n i o na b o u tk e y t e c h n o l o g i e sa n dr e a l i z e do np cb yp r o g r a m m i n g s y m b o lr e c o g n i t i o nb a s e do ns t a t i s t i c a l m e t h o da n dn e u r a ln e t w o r k i tc o n s t r u c t sm u l t i c l a s s i f i e rf o rs a v i n gt h et i m eo fs y m b o l r e c o g n i t i o n t h es y s t e mh a sl e a r n i n gf u n c t i o ni no r d e rt oe x t e n dt h er e c o g n i t i o na b i l i t y i nt h e p r o c e s s i n g o fs t r u c t u r a l a n a l y s i s i t u s e st r e es t r u c t u r e st o a n a l y z et h e s t r u c t u r eo f m a t h e m a t i c a le x p r e s s i o n s e x p e r i m e n t a lr e s u l ti n d i c a t e st h em e t h o dh a sb e t t e ra p p l i c a b i l i t y a p p l i c a t i o ne m b e d d e di ec o m p o n e n t a n dt h em a t h e m a t i ce d i t o rm a t h p l a y e rr e a l i z ef o r m u l a n o u t p u t t h em e t h o di sp r o p i t i o u st of o r m u l ar e c y c l e t h ee n do ft h i sp a p e ri st h er e s u l ta n dt h ed i s c u s s i o n t h i sp a r tp e r f o r m sad i s c u s s i o n a b o u tt h i sa r t i c l e a n dt a k e st h er e s u l ti n t oa p p l i c a t i o n f i n a l l y t h ef u t u r ew o r ki sp r o p o s e d b a s e do np r o b l e m si nt h es y s t e m k e y w o r d s r e c o g n i t i o no fo n l i n eh a n d w r i t t e nm a t h e m a t i c a lf o r m u l a p a t t e mr e c o g n i t i o n s y m b o lr e c o g n i t i o n s t r u c t u r a la n a l y s i s h i 广州大学学位论文原创性声明 本人郑重声明 所呈交的学位论文 是本人在导师的指 导下 独立进行研究工作所取得的成果 除文中已经注明引 用的内容外 本论文不含任何其他个人或集体已经发表或撰 写过的作品成果 对本文的研究做出重要贡献的个人和集体 均已在文中以明确方式标明 本人完全意识到本声明的法律 后果由本人承担 学位论文作者签名 也k 芬 日期 o 唧年多月 7 日 广州大学学位论文版权使用授权书 本人授权广州大学有权保留并向国家有关部门或机构送 交论文的复印件和磁盘 允许论文被查阅和借阅 本人授权 广州大学可以将学位论文的全部或部分内容编入有关数据库 进行检索 可以采用影印 缩印或扫描等复制手段保存 汇 编学位论文 保密的学位论文在解密后适用本授权书 学位论文作者签名 制婚 聊獬 锡 日期 1 年f 肜1e 1 日期 易汐7 钳别日 第一章绪论 第一章绪论 联机手写数学公式识别或称为在线手写数学公式识别 是一种重要的人机交 互技术 它给用户提供了一种自然的进行数学公式输入的方法 用户利用某种设 备直接书写数学公式 经过系统识别处理后 转换为统一的表示 实现数学公式 输入 联机手写数学公式识别技术的发展具有重要的现实意义 具有非常广泛的 应用领域 有助于教育事业的发展 在计算机的日常使用过程中 用户特别是学 生 教师 工程师和科研人员 经常会有将数学公式输入计算机的需求 现行的 两种输入方法 特殊语言法和图形界面法 1 1 都不及手写数学公式自然 简便 手写数学公式识别系统可以方便的将计算机辅助教学应用于各学科课堂教学中 用户可以像完成文字处理一样轻松的完成数学 物理 化学等各种复杂公式的输 入 另一方面 对手写数学公式识别的研究基本上与文化背景无关 这样就为各 国 各地区的研究工作者提供了一个施展才智的大舞台 在这一领域大家可以探 讨 比较各种研究方法 1 1 研究背景 数学符号和数学公式识别开始于上世纪6 0 年代 是字符识别领域的一个较 古老又特别的分支 随着科学技术和计算机技术的飞速发展 需要处理的含有数 学公式或数学方程的自然科学方面的材料也在快速增多 人类与计算机所处理的 对象在许多方面是不同的 人机交互系统就是要在计算机用户与计算机之问建立 一种交互式的对话方式 在计算机处理数学公式的早期 人们使用一类专用的一维结构文本语言来表 示二维的数学公式 识别是对这些经过一维转化后的公式进行的 这种方法极大 地降低了公式的识别难度 2 j 目前 经常使用的这种方法表示数学公式的描述语 言的一个例子是l a t e x 3 1 但使用这种方式输入比较适合于有一定经验的专家用 户 而对大多数的普通用户来说 学习l a t e x 语言的语法的任务太过繁重 因此 不利于这项应用的大众化推广 从人性化的角度出发 人们使用可视化的语言t 4 要比使用串式语言更便捷更 第一章绪论 直观 通常 一种可视化语言是由一系列符合该语言的句法和语法的表达式组成 而表达式又由一串字符以二维或三维方式分布组合而成 可视化语言与串式语言 的基本区别在于前者以高维分布 而串式语言是一维分布 因此 对可视化语言 的理解需要理解表达式中终结符与非终结符之间的空间关系 进而理解表达式的 含义 计算机接受串式语言 它对自然可视化语言的理解必然涉及到语言的识别 翻译 将自然可视化语言转化为串式语言 这使得我们必然使用编译技术来进行 这也提供了一个全新的研究领域 数学公式输入计算机通常比纯字符难 因为数学公式由英文字符 数字 希 腊字母以及其他特殊字符组成 数学公式相对其他手写识别系统而言 更为复杂 数学符号种类繁多 它包括算术 微积分 逻辑和一些其他的数学学科中的符号 数学符号的意义多种多样 相同的数学符号可以表达不同的语义信息 数学符号 之间空间关系的错综复杂 相同的符号在空间位置上不同时 表达的意义是截然 不同的 数学公式识别 5 可以划分为印刷体识别和手写体识别 如图卜1 所示 从手写 与识别时间的关联上考虑 又可以进一步将数学公式的手写体识别划分为脱机识 别和联机识别 脱机识别是用户写完数学公式后进行识别 而联机识别则是指在 用户书写数学公式的时候 识别也同时进行 联机输入能够捕捉手写的动态信息 如笔划的数量 笔划的顺序和书写速度等 而且 联机手写输入还是人机之间的 一种紧密交互 要求系统能够不断的根据用户的输入修正识别结果 并为用户提 供必要的反馈信息 从而联机手写具有实时性的特点 本文研究的是联机手写数 学公式识别 2 第一章绪论 1 2 联机手写数学公式识别的难点 日常学习和工作中 用笔在纸上书写数学公式是最平常而又简单的事情了 不同的人写的数学公式 我们总是能够看懂它的意思 但就是这样一件普通的事 情 对于功能强大的计算机而言却是有很大的难度进行处理的 把公式输入计算 机和计算机进行自动识别这两项任务把手写数学公式的识别变得复杂了 数学公 式中包括了 些数字 英文字符 希腊字母和一些特殊的字符等 并且这些符号 不像简单文本那样线性排列 而是按一定规则分布在二维结构中 结构比较复杂 计算机对它的自动识别是富有挑战性的 另一方面 由于书写数学公式时 界面 和书写工具的非精确性 数学公式结构的复杂多变性 数学符号的二义性嘲 以 及泛化计算理论的要求等原因 使得手写数学公式的识别和编辑成为一个难点 因此 解决这些技术问题 用更加自然 简便 高效的方法来完成手写数学公式 的输入 编辑和计算闯题 一方面要求硬件输入工具提高精确性 更重要的一方 面是要对识别算法进行研究和改进 1 2 1 输入设备的非精确 输入设备以某一特定的频率进行采样 将物理信息数字化并且传入计算机这 个过程存在着离散设备对连续数据采样所引起的设备误差 此外 用户的手写也 会因为一些不可避免因素而引入噪音 如手腕的抖动 书写环境的变化等 另一 方面 模式识别作为一种由非精确空间向精确空间映射的技术 其识别结果以概 率形式表示 本身也是非精确的 此外 不同的用户都有着不同的书写习惯 各 种手写体在外形上具有较大的差异 所有的这些因素 导致界面的非精确性是与 生俱来的 它使得用户界面下的意图提取和分析成为一个不可回避的问题 1 2 2 相似字符多 数学公式中的字符不同于汉字识别 构成数学公式的字符大多数是英文字 符 数字和运算符 它们的特点是书写简单 语义清晰 表达的意义变化多样 也正是因为数学公式中字符的书写简单 造成了另外一个突出问题是数学公式中 的二义性 二义性是指某对象具有不止一个正确的解释 数学公式的二义性体现 3 第一章绪论 在其数学符号本身的二义性 例如减号和分数线 在手写公式时都是横线 但意 义却大不相同 如何判断书写的是减号还是分数线呢 再如数字 0 和字母 o 其形状十分相似 如下图1 2 所示 连人的肉眼有时候都比较难区分 何况是机 器了 o 1 2 3 数学公式的复杂结构 图1 2 是0 还是0 f i g u r e l 2 i s o o r 0 7 判断数学公式的复杂结构是识别数学公式的重点和难点 线性结构的文本比 较容易进行切分 数学公式不同于线性结构的普通文本 数学公式二维的复杂结 构具有很多变化 使得切分的难度大大增加 在最基本的数学公式中具有分式 根式 上标 下标等复杂的结构以及它们的相互嵌套 见下图1 3 所示 对这些 结构的识别具有相当的难度 这就引出了数学公式识别的一系列的研究 包括了 公式的定位 公式的结构分析 理解公式含义和最后显示出识别后的公式等许多 方面相当复杂而又环环相扣的问题了 x 图1 3 手写公式举例 f i g u r e l 3h a n d w r i t t e nf o r m u l ae x a m p l e 1 3 联机手写数学公式研究的现状与成果 近年来 随着手写识别技术和笔式界面交互技术的不断发展 联机手写数学 公式识别作为笔式界面环境下的一项重要应用 也越来越多地吸引了众多专家学 4 三池 卜 第一章绪论 者的注意 很多大学的相关院系都开展了这方面的研究工作 主要有德国的 u n i v e r s i t yo f t e c h n o l o g y m u n i c h 7 s l 美国麻省理工学院 m 9 1 0 1 加拿大 o u e e n su n i v e r s i t y 1 2 切 香港科技大学1 1 4 1 5 1 6 等 不仅在识别研究的理论上进行了比较深入的研究 不少商业公司也推出了手 写数学公式识别的产品 也形成了一些比较成熟的软件 例如 t h en a t u r a ll o g s y s t e m l l 7 1 是比较早推出的能够联机识别字符和公式的系统 这个系统是用j a v a 语言实现的 只能在网络上在线使用 t h e f r e e h a n d f o r m u l a e n t r y s y s t e m 1 8 l 是一 个笔式等式编辑器 它运行于i j n 慨和m a c o sx 平台下 i n f t ye d i t o r 1 9 是一个数 学公式可视编辑器 作者将m a l h 锄a t i c a 和m a t h l i n l 组合在一起 形成新的套装 它可以改造成为能处理l a t e x 的系统 如下图1 4 所示 微软亚洲研究院基于模 式识别技术的 手写数学公式识别器 为用户提供了全新的手写输入功能 当 用户在平板电脑上手写数学公式之后 手写数学公式识别器就可以自动识别出用 户所写的公式 手写数学公式识别器作为m i c r o s o f te d u c a t i o np a c k 的应用之一 已经于2 0 0 5 年7 月发布 最新推出手写公式识别产品是2 0 0 6 年7 月 汉王科技率先 推出具有手写公式识别功能的产品 e 粉笔 它的优点是在普通电脑上就可以 使用 而且能识别比较复杂的数学公式 识别率也比较高 汉王手写公式识别界 面如下图1 5 所示 这些研究的内容都是对用户直接用鼠标或者手写笔输入的二 维结构的数学公式进行识别 图1 4i n f t ye d i t o r f i g u r e l 4i n f t ye d i t o r 5 第一章绪论 1 4 本文的工作 图1 5 汉王e 粉笔 f i g u r e l 5h a n gw a n ge c h a l k 基于对现有相关软件的研究和分析 再结合自己所做的工作 现将笔者设计 的系统与相关软件的某些功能做一些比较 列表如下 表1 1 各种手写公式识别软件的比较 t a b l e l 1c o m p a r i s o no fv a r i o u sh a n d w r i t t e nf o r m u l ar e c o g n i t i o ns o f t w a r e 软件本系统 m i c r o s o f le d u c a t i o np a c k i n f t ye d i t o r汉王e 粉笔 功能 用于p c 机是否是是 显示一维表达式有无有有 简单表达式计算有无无有 学习新字符有无无无 本文首先论述了数学公式识别研究的背景 并且逐渐过渡到手写数学公式的 研究 然后立足于联机手写数学公式识别的具体应用 对其识别的难点和识别算 法和主要技术进行研究 并且自己设计了一个简单的联机手写数学公式识别系 统 其中包括英文字符的识别 简易数学符号识别 公式结构分析包括四则运算 字符上下标 简单分式和简单根式的表示 本文具体的结构是 第一章中介绍了数学公式识别研究的背景 总结了数学公式识别的分类 提 出联机手写公式识别的难点 介绍了联机手写数学公式研究的现状和有关的产 品 并且在最后给出了论文的思路和组织结构 第二章中 作者介绍联机手写数学公式识别主要技术 总结了现今比较完善 6 第一章绪论 的模式识别技术的主要步骤 单个字符识别部分的主要算法 第三章中 介绍公式识别的结构分析算法 错误纠正 最后 使用数学公式 编辑工具m a t h p l a y e r 实现公式输出 第四章中 介绍自己设计的识别系统的功能 并详细描述如何实现联机手写 数学公式识别系统 主要采用树转换的方法来分析数学公式的结构 在文章的末尾 给出使用自己设计的联机手写数学公式识别系统时的实验结 果 并针对实验结果思考自己设计的系统中存在的若干问题 最后 作者对本文 进行总结 并根据系统中存在的问题和手写数学公式识别的发展趋势 提出下一 步的工作 7 第二章联机手写数学公式的字符识别 第二章联机手写数学公式的字符识别 2 1 模式识别概述 模式识别诞生于2 0 世纪2 0 年代 随着4 0 年代计算机的出现 5 0 年代人工 智能的兴起 模式识别在2 0 世纪6 0 年代迅速发展成为一门学科 它所研究的 理论和方法在很多科学和技术领域中得到了广泛的重视 推动了人工智能系统 的发展 扩大了计算机应用的可能性 冽 几十年来 模式识别研究取得了大量 的成果 也实现了很多成功的应用 但由于实际系统中涉及到很多复杂的问题 还有待解决 模式实际上可以说是存在有某种基本结构组织的排列或有序化 我们可以 把整个世界看作是由模式构成的 w a t a n a b 2 1 把模式定义成一个能够给出名字 但不能明确定义的一个实体 模式也可称为对某一事物或其他一些感兴趣项目 的定量或结构上的描述 一组具有公共特性的模式可以看作为一个模式类 通 过机器进行模式识别的主要问题 就是如何采用更好的处理技术自动地 尽可 能少由人介入地把模式分到各自的类中 对于一个典型的模式识别系统 类的判别仅仅是整个系统任务的一个方面 可以或不可以必须确定的属性之一 属性可以是离散的值 布尔实体 按句法 规则的句子或模拟值 在模式识别中 学习就相当于模式特征和属性之间相互 关系规则的判定 图2 1 中给出了一个典型模式识别任务的所有方面 2 2 l 它包括 图2 1 模式识别系统的构成 f i g n r e 2 1c o m p o s i n go fp a t t e r nr e c o g n i t i o ns y s t e m 预处理 把图像划分成独立的识别对象 此外 它还能按比例变换图像以便对 识别对象的处理 8 第二章联机手写数学公式的字符识别 特征提取 提取各个模式的高层信息使其容易识别 分类器 分类器识别出模式所属的类别或者大体上确定给定模式的属性 相关处理 相关处理器通过提供关于识别对象周围环境的相关信息来提高识别 精度 2 1 1 数据采集 数据采集是模式识别过程必不可少的第一步 主要是使用一些如传感器等的 设备对对象进行数字化处理 例如 在图像分析和符号识别的应用中使用的主要 设备有摄像机和扫描仪等 在语音识别应用中使用的设备有麦克风等 这些设备 以一定的时间频率和 或者 空间频率进行采样 并把观测值数字化为预置的一些 比特信息 考虑到噪音的损害 采样设备必须具有足够的精度 合理的代价和一 定的健壮性 数据采集阶段往往需要辅助存储器保存搜集的数据 如果识别不能够在数据 采集的同时进行 那么就需要临时存储所采集的数据 当构造一个模式识别系统 的时候 需要大量的存储空间来保存训练数据 减小存储资源占用的方法就是对 数据压缩 负面影响是会导致数据精度的遗失 这一矛盾成为了某些联机识别的 瓶颈l 矧 2 1 2 预处理 预处理是识别处理的第一步 占有十分重要的地位 预处理的好坏将直接影 响识别方法的难易及识别结果的好坏 预处理的目的是去噪声 加强有用的信息 并对输入测量仪器或其他因素所造成的退化现象进行复原 噪音是指任何对模式 识别系统正确分类产生阻碍的因素 现实系统中的噪音是不可避免的 需要特定 的预处理技术来减低噪音的影响 此外 预处理模块还负责对有用信息进行加强 或者加入某些新的 有效的特征 预处理内容是与识别对象和识别方法密切相关 的 不同的识别对象决定了不同的识别方法 也决定了不同的预处理内容 9 第二章联机手写数学公式的字符识别 2 1 2 1 平滑 经过平滑处理 能去掉孤立噪声 干扰 矧 平滑笔划边沿 对于手写体来 说 一般需要经过平滑处理 排除识别时的干扰 处理的方法有很多 原始数 据的滤波处理分为两步 第一步是对原始点坐标的滤波 第二步是对这些点坐 标所计算出的笔划方向码的滤波 1 原始坐标数据的滤波 由于同一笔划中相邻点具有一定相关关系 不可能出现距离较大的相邻点 这里可以采用一种平滑处理方法 如下式所示 x p l a x 一 0 一a x 工曲 a 工瑚 k 一口 1 一a 誓l b a l 冗余点为 a l m 其中 x k 是笔划在t 时刻的坐标 下标p 表示经过平滑后的数据 是 平滑系数 0 互a5 1 8 越大 平滑后两点相关性越大 反之a 为0 不进行平 滑处理 三 秕一是判别冗余点和噪声点的距离阈值 2 笔划方向码的滤波处理 由于在实际书写过程中 输入的笔划并不是很标准 在方向码序列中 还 含有大量的噪声和人为的错笔 这就需要套对方向码进行滤波 2 1 2 2 归一化处理 归一化包括位置归一化 大小归一化以及笔画粗细归一化 2 5 1 本系统是联 机手写公式识别只简单介绍前两类 1 位置归一化 在图像处理中 为了消除字符点阵位置上的偏差 需要把整 个字符点阵图形移动到规定的位置上 这个过程被称为位置归一化 有两 种位置归一化方法 一种是基于质心的位置归一化方法 另一种是基于字 符外边框的位置归一化 基于质心的位置归一化方法首先计算字符的质心 第二章联机手写数学公式的字符识别 然后再把质心移动到指定的位置上来 基于文字外边框的位置归一化需要 首先计算文字的外边框 并找出中心 然后把文字中心移动到指定的位置 上来 相对而一言 质心的计算是全局性的 基于质心的归一化方法抗干 扰能力强 大小归一化 由于字符字形繁多 同一字符的特征也因此而不同 为了便 于统一描述 对不同字形的字符均能识别 所谓大小归一化就是指对不同 大小的字符图像做变换 使之成为同一尺寸大小的字符 从图形学的角度 看 大小归一化处理的实质是对二维图形的缩放 即先求出原图像与标准 尺寸的缩放系数 然后对图像的离散坐标点作逐点缩放 2 1 3 特征提取和选择 特征提取和选择是模式识别中的一个关键问题 它的基本任务是研究如何从 众多特征中求出那些对分类识别最有效的特征 从而实现特征空间维数的压缩 由于在很多实际问题中常常不容易找到那些最重要的特征 或受条件限制不能对 它们进行测量 为了有效的实现分类识别 就要对原始数据进行交换 得到最能 反映分类本质的特征 这就是特征提取和选择的过程 一般我们把原始数据组成 的空间叫测量空间 把分类识别赖以进行的空间叫特征空间 通过变换 可把在 维数较高的测量空间中表示的模式变为在维数较低的特征空间中表示的模式 在 特征空间中的一个模式通常也叫做一个样本 它往往可以表示为一个向量 即特 征空间中的一个点 原始特征的数量可能很大 或者说样本是处于一个高维空间中 通过映射 或 变换 的方法可以用低维空问来表示样本 这个过程叫特征提取瞄1 映射后的特 征叫二次特征 它们是原始特征的某种组合 通常是线性组合 所谓特征提取 在广义上就是指一种变换 若y 是测量空间 x 是特征空间 则变换 a y 一 x 就叫做特征提取器 从一组特征中挑选出一些最有效的特征以达到降低特征空间维数的目的 这 个过程叫特征选择 特征选择的任务是从一组数量为d 的特征中选择出数量为 d d d 的一组最优特征来 在具体实施特征提取与选择时有如下两个基本途径 1 当实际用于分类识别的特征数目d 给定后 直接从已获得的n 个原始特征中选 1 1 第二章联机手写数学公式的字符识别 出d 个特征 x 勤 使可分性判据j 的值满足下式 i 瓴 工2 乃 一m a v l x i 2 妇 式中 t t j 0 是n 个原始特征中的任意d 个特征 此即直接寻找n 维特征空间 中的d 维子空间 这类方法称为直接选择法 其主要有 分支定界法 用回归建 模技术确定相关特征等方法 2 在使判据j 取最大的目标下 对n 个原始特征进行变换降维 即对原n 维特征空 间进行坐标变换 再取子空间 这类方法称为变换法 其主要有 基于可分性判 据的特征提取选择 基于误判概率的特征提取选择 离散k l 变换法 基于决策 界的特征提取选择等方法 设 口 口 口 是n 维特征空间e 的一个基底 矢量x 是对象在e 中关于 n j 的一个观测 则x 可表示为 牡艺叩t 在此基底 q 上x 的各分量 q 称为对象的特征值a 特征提取与选择实质是在e 中找出一个子空间w 对象新的特征是通过x 向 子空间投影得到的 令w 是m 维子空间 是由m 个线性无关的矢量晟 芦 卢 张成 的 b p w s p a n 局 芦2 成 m 一0 l l a t z 五肇 玩 坟 一 式中 s 是笔道特征向量 a k b k 是字符中k 条笔道的傅利叶系数 2 p 维 2 2 3 判别方法 将输入字符的特征向量与字典的特征向量相比较 设图象特征向量 l 的 分布是多元正态分布 3 3 1 则判别函数的形式如下 g 仁 口 赢 x p 卜i l m o 一m 口 r 式中 m 和 是从样本中经学习后求得的类别口的平均图象向量和协方差矩 阵 如果g 仁 氏 一脚香 g 仁 疗 则可判定字符l 属于吼类 计算时 在对 规定几项限制和情况下 可采用以下两个判别条件 1 9 第二章联机手写数学公式的字符识别 判别条件1 假设构成字符的各笔道之间并无相互关系 而表示傅利叶系数的各分量之 间有相互关系 这个条件等价于下列方程式 一 足 一s 一 式中 s k 是属于类别口的笔道k 的协方差矩阵 判别函数g l 一 由下式表示 g l 0 mg s i g s t 一 吼 一 式中 s 是字符l 的笔道k 的输入特征向量 o s 是属于类别0 中笔道k 的字 典特征向量 如果g l 靠 m a x x g l 8 则被识别为靠类 判别条件2 在使用判别条件2 时 特征向量的分量方差应予考虑 但各分量间的协方 差则忽略不计 换句话说 在判别时只使用 的对角线分量 判别函数占 口 由下式表示 g 三 o i l m 1 l m 猡 t 护 1 三一m 谬 三一m 2 3 多分类器设计 我们知道有许多不同种类的模式识别分类器 每种都有其自己的许多优点和 缺点 一个性能很好的分类器也必然会存在对某些模式的误识 而这些被误识的 模式往往又可以通过应用另一种不同的分类方法和分类特征的分类器得到正确 的识别 这是因为能够从有限的训练样本集中得到完全解决方案的学习算法是不 存在的 特定的学习方法都有其侧重性 适用于不同的应用环境 因此 将许多 不同的分类器以某种方式进行组合 以便在总体上能取得比单一分类器更好的效 果 3 4 1 下图2 5 所示 给出了应用于模式识别问题的多识别器系统的概念 2 0 第二章联帆手写数学公式的字符识别 图2 5 多分类器的应用 f i g u r e2 5t h ea p p l i c a t i o no fm u l t i c l a s s i f i e r 目前 多分类器集成是模式识别领域中的一项重要研究内容 人们对此已经 进行了很多研究工作 将问题以更数学化的方式进行讨论 考虑一个具有m 个互 不相交集合的判定空问 v i e a 一岱2 膨 每个集合q 代表模式所需分组 或分类成的一类或一组 判定空间可写为 p q u c u u c 因此 判定空间是所有类中所有可能模式的集合 现在定义一系列相应的整 数标记a 一仉2 m 因此 集合a 对于已定义的类提供了所有可能的整数标 记 判决空间集合p 扩展为包括a u m 1 m i 表示一个摒弃类 此类是根据 已有的标准识别器识别不出的模式 下面用l 表示在组合系统中识别器的总共数 量 系统中的每个识别器都用e 表示 因此系统中识别器为q p 气 将模式x 输入到识别器c 中识别器e 的输出是一整数标号j a u m 1 此标号指明x 属于 类c 或者可能为摒弃类 这可表示成e x 习 注意到不管识别器是什么类型 识别器都被看成是一函数黑盒 此函数黑盒输入一模式样本x 然后输出一分类 第一二章联机手写数学公式的字符识别 标号j 现在我们已建立了大部分所需的符号表示 尽管由标号j 指定的分类是任意给定的识别器e 的最后输出 但是许多现在的 分类系统还能在中间阶段提供其它的有用信息 譬如 贝叶斯分类器提供m 个后 验概率p i x i 1 m 也就是说 矢量x 分类为c 的概率 在这种分类器中 标号就被简单当作这些概率中最大的一个概率 一旦分类完成 可能就不被保留 这些概率 然而 这些摒弃的信息在多分类器中可能非常有用 不同的识别器所 能提供的信息种类是不同的 基于不同方式组合起来的混合系统 具有相当多的优点 并已应用于商业产 品中 在模式识别可能应用的许多不同问题中 统计方法 句法方法和神经网络 方法都有自己相应的作用 2 4 本章小结 本章介绍了模式识别的基本原理 识别过程和实现方法 然后总结了在字 符识别中所使用三种识别方法 它们分别是统计模式识别方法 句法模式识别 方法和神经网络识别方法三类 并分别加以说明和相互比较 在字符识别过程 最重要的两个步骤是特征描述和判别方法 本章说明了针对数学符号所进行的 特征描述和判别方法 并详细说明了实际系统中使用的特征提取方法 最后讨 论了多分类器的集成 以及实际系统中所使用的集成方法 第三章结构分析 第三章结构分析 结构分析是公式识别的主要工作 对公式识别的准确性起到至关重要的作 用 在字符识别阶段运用已有的字符识别算法 并加以改进得到公式的各个字符 的位置信息和类别 构成树来表示各个字符和数学公式之间的关系 通过结构分 析预处理可以消除一些不利于结构分析的信息 也可以得到结构分析所需的附加 属性 便于结构分析的进行 树上的节点信息包括字符的级别和其他许多参数 比如说大小和位置 结构分析模块主要包括两方面工作 系统的输入和系统的输 出 系统的输入是 字符内容和它们的空间位置 系统的输出是 以m a t h p l a y e r 的形式输出 3 1 结构分析算法 结构分析的任务是对字符识别的结构进行处理 最终得到一颗结构树 然后 通过对结构树的游历 得到公式结构的属性描述 进一步还原公式的结构 结构 分析算法理论研究比较丰富 各种结构分析算法都有其优缺点 f a t e m a n 等人彤j 提出的方法中定义了文本包f r e x tb a g 和公式包 m a t hb a g 首先将所有的符号初始化分为2 类 分别放在定义好的2 个包中 初始化时 文本 包中包括罗马字符 斜体数字等 公式包中包括标点符号 特殊符号 斜体字母 罗马数字以及其它一些标记如水平线和句点等 然后定义一些启发式规则 并根 据这些规则将它们不断调整文本包和公式包中的内容 以保证它们能正确分类 l a v i r o t t e 和p o t t i e r p 6 提出采用图文法来识别二维数学公式 这种方法是多维 的模糊性和图的构造 在理论上采用精确定义的方法来解决图文法之间的模糊 性 他们定义了一系列的规则来描述数学关系 采用自底而上的算法来解析数据 获得最终结果 如果我们要识别公式 e 1 它首先识别字符c 和x 并判 断他们的位置关系 这时他们成为一个单独的标记 最后将 e 和 1 构成 最后的结果 w i n k l e r 等p 首先为手写体符号的输入产生一个符号假设网 s h n 然后使用 第三章结构分析 h m m 从s h n 中查找一个或多个符号序列 并根据可能性最大的符号序列来决定 最终的符号分类 这种方法也称为软决策方法 s a t a m o t o 等 3 8 l 也用h m m 方法来 识别数学表达式中的符号 l e e 和w 柚一3 9 采用b a y 豁决策规则将文档中的行分为文本行 标为t e x t 和公式行 标为e i 在行标定后 独立的数学表达式一定在公式行 e x p 中 而 嵌入式数学表达式只在标记为 t e x t 的行中 但该方法只适应于一些简单的数 学公式 c h a u d h u r i 和g a r a i n l 4 0 3 的算法定位独立的数学表达式不要用到符号识别的方 法 它通过计算行内各符号的纵坐标的平均值和标准差来判断本行是否为独立 的数学表达式 采用符号识别的方法来检测嵌入式数学表达式 如果存在某个特 殊符号 这里的特殊符号指数学表达式中特有的符号 则说明存在数学表达式 并采用启发式算法来得到整个数学表达 c h a n 和y e u n g 4 l j 采用结构和句法的方法开发了一个联机数学表达式识别系 统 用弹性结构匹配方法识别符号之后 用句法的方法 确定性子句语法 d c g 得到数学表达式的结构 采用d c g 不仅能精确地定义替换规则 而且这些规则能 很容易地被执行 它提出了一些用于解决d c g 中的回溯带来的负面影响的方法 如绑定符号预处理 层次分解 据说这种方法对向量和数组的识别很有效 z a n i b b i 等 4 2 1 通过基线来判断结构 树变换来分析数学表达式的结构 所以叫 做基准结构树 b a s e l i n es t r u c t u r et r e 订 第一个阶段构建初始基线结构树 b s t 它 主要描述输入笔划符号的二维布局 如 就分成两笔输入 第二阶段将词法 b s t 3 e 换成运算符号树 这个树表示输入表达式的运算顺序 在每个阶段都是采 用树变换来实现的 使用t x l i 吾言来转换树 在词法b s t 中包括十进制数字 函 数名 以及多笔划符号如 一 当然也包括竖直结构如分式 3 2 错误纠正 在数学表达式识别的时候经常会出现错误 识别中错误的检测和纠正也是数 学表达式识别系统中一个重要的组成部分 错误的字符识别和分类在结构分析中 能导致错误的结果 l e e 暑1 w a n g l 4 3 采用一些启发式规则来检测错误 他们考虑了四种启发式的规 第三章结构分析 则 其中一条是 任何一个双目运算符都必须有两个操作数 例如 若有表达 式 t i 打 被纠正成 1 i 1 n u m l 第几条线 f o r t i m e l o j o s t o r e n u m l t h n e l x 一1 t i m e l i f t i m e l 0 q u e u e j t h n e l j i f t i m e l 0 s t o r e n u m l t i m e l 1 x 一1 1 q u e u e j t m a e l j i f t i m e l 0 s t o r e n u m l t i m e l 1 x 1 1 i f s t