（计算机应用技术专业论文）印刷体数学公式符号识别技术的研究.pdf

摘要 摘要 将文献信息输入计算机进行处理是信息化社会的必由之路。目前广泛应用的o c r ( o p t i c a lc h a r a c t e rr e c o g n i t i o n ，光学字符识别) 系统对印刷体文字已取得很高的识别率， 克服了人工输入费时费力的缺点，但是还不能处理数学公式，只能将其按图片存储，不 但占用大量空间，而且不能对其进行编辑和检索。因此，数学公式自动识别在将含有大 量公式的科技文献转化为电子文档的过程中具有重要的意义，是当前识别领域的一个研 究热点。 数学公式识别系统分为数学公式抽取，公式符号识别，公式结构分析和公式重构四 个模块。公式符号识别模块的功能是将公式中的符号图像转换成相应的代码，是公式识 别系统的核心部分，包括符号切分和符号识别两个阶段。本文针对印刷体数学公式符号 切分和识别展开研究，设计了能够适应公式符号二维分布、大小不一、多交叠、多字体 等特点的切分和识别算法。首先采用投影和基于连通特征的切分方法对公式符号进行切 分，为符号识别提供正确的符号位置信息，然后对符号进行预处理，提取符号的轮廓特 征和方向线素特征，利用一个两级分类器对符号进行识别，并通过建立切分与识别之间 的反馈机制，提高了识别模块的准确率。针对不同印刷质量文档的对比实验表明，本文 设计的符号切分和识别方法能够取得较高的识别率和令人满意的处理速度。 关键词光学字符识别数学公式识别字符切分轮廓特征方向线素特征 a b s t r a c t a b s t r a c t w i t ht h ep o p u l a r i z a t i o no fc o m p u t e r , t h ec o n v e r s i o no fi n f o r m a t i o nf r o mp r i n t e dt o e l e c t r o n i cf o r mb e c a m e 锄i m p o r t a n ti s s u e a tp r e s e n t ，t h eo c rs y s t e m st h a th a v eb e e n w i d e l yu s e dc a l lr e c o g n i z et h ep l a i nt e x tw i t hh i g ha c c u r a t er a t e ，b u tt h e yc a n n o td e a lw i 廿i m a t h e m a t i c a lf o r m u l a s t h ef o r m u l a sa r es t o r e da si m a g e s ，w h i c hn o to n l yt a k eal o to f s t o r a g es p a c e ，b u ta l s o c a n n o tb ee d i t e do rs e a r c h e d t h u s ，a u t o m a t i cr e c o g n i t i o no f m a t h e m a t i c a le x p r e s s i o n si so n eo ft h ek e yv e h i c l e si nt h ed r i v et o w a r d st r a n s c r i b i n g d o c u m e n t si ns c i e n t i f i ca n de n g i n e e r i n gd i s c i p l i n e si n t oe l e c t r o n i cf o r m a tp r e s e n t ，t h e r e s e a r c ho ni ti sah o t s p o tb u tn o tm a t u r e t h i ss y s t e mc a l lb ed i v i d e di n t of o u rs t a g e s ：m a t h e m a t i c a lf o r m u l a se x t r a c t i o n ，f o r m u l a s y m b o l sr 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 sa n df o r m u l a sr e c o n s t r u c t i o n t h ef o r m u l as y m b o l s r e c o g n i t i o ni sa ni m p o r t a n ts t a g ei nt h em a t h e m a t i c a le x p r e s s i o nr e c o g n i t i o ns y s t e m i t c o n s i s t so ft w os t e p s ：s y m b o l ss e g m e n t a t i o na n ds y m b o l sr e c o g n i t i o n a i m i n ga tt h ef a c tt h a t t h ec o m m e r c i a lo c rs y s t e m sc a n n o tr e c o g n i z ee x p r e s s i o ns y m b o l sc o r r e c t l yb e c a u s eo ft h e d i f f e r e n c e sb e t w e e nm a t h e m a t i c a ls y m b o l sa n do r d i n a r yc h a r a c t e r s ，w ed ol o t so fr e s e a r c h w o r ko nt h er e c o g n i t i o no fp r i n t e de x p r e s s i o n s a na p p r o a c ht h a tc o n t a i n s 诧e d b a c k m e c h a n i s mi sp r o p o s e df o rs y m b o l ss e g m e n t a t i o na n dr e c o g n i t i o n f i r s t l y , p r o j e c t i v ef e a t u r e s a n dc o n n e c t e dc o m p o n e n t sl a b e l i n gm e t h o da r eu s e dt os e g m e n ts y m b o l si ne x p r e s s i o n s s e c o n d l y , t h ec o n t o u rf e a t u r e sa n dd i r e c t i o n a l l i n ee l e m e n tf e a t u r e sa r e e x t r a c t e df r o m s y m b o l s f i n a l l y , ac o a r s e - t o - f i n ec l a s s i f i c a t i o ns t r a t e g yi se m p l o y e dt or e c o g n i z es y m b o l s w i t l lt h e s ef e a t u r e s t h ee x p e r i m e n t ss h o wt h a tt h e s em e t h o d sc a l lo b t a i ns a t i s f a c t o r y r e c o g n i t i o na c c u r a c yw i t hah i 曲s p e e d k e yw o r d s ：o c r ；m a t h e m a t i c a l f o r m u l ar e c o g n i t i o n ；s y m b o l ss e g m e n t a t i o n ； c o n t o u rf e a t u r e ；d i r e c t i o n a ll i n ee l e m e n tf e a t u r e s 河北大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教育机构的学位或证书 所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了致谢。 作者签名：毖叠日期：丝丛年j _ _ 月二兰日 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留并向国 家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。学校可以公布 论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 本学位论文属于 l 、保密1 ：3 ，在年月日解密后适用本授权声明。 2 、不保密留。 ( 请在以上相应方格内打“”) 作者签名： 堑叠 导师签名： 日期：塑堕年上月皇互e t 日期：龇年月立日 第1 章引言 1 1 研究背景 第l 章引言 随着人类社会信息化程度的日益提高，将印刷文档转化成相应的电子文档成为一个 亟待解决的问题。利用o c r ( o p t i c a lc h a r a c t e rr e c o g n i t i o n ，光学字符识别) 技术将印 刷文档输入计算机，是目前公认的信息数字化的高效手段。经过几十年的发展，o c r 技术已经进入了实用阶段，而且其速度和准确率都达到了令人满意的程度。近年来，在 o c r 技术基础上，结合字体识别、表格识别技术，已经初步实现了原文版面的重构与 再现，这样就可以方便地进行编辑和排版。但目前这类文档识别系统( o c r 软件) 对 数学公式束手无策，只能按照图像进行保存，这样就不能对文章中的公式进行编辑，也 不能依据公式内容对文章进行检索。绝大多数科技文献的核心内容就是数学公式，失去 了公式的文章可能毫无意义：而且以图像形式保存公式占用存储空间比较大，不利于科 技文献的网上传输。文档处理的目标是获取文档信息，使信息的存储和获取变的相对容 易。所以印刷文档中数学公式的处理在o c r 系统中占有举足轻重的地位。 综上所述，研究数学公式识别可以拓宽o c r 技术的应用领域，提高科技文献数字 化的效率。因此，针对公式识别技术展开研究具有重要的理论意义和良好的应用前景， 对我国信息化建设具有重要意义。 本课题来源于河北省自然科学基金资助项目印刷文档识别与重构若干核心技术的 新开拓( 基金编号：f 2 0 0 4 0 0 0 1 3 2 ) 。 1 2 国内外研究现状 公式识别问题于1 9 6 8 年由a n d e r s o n 在他的博士论文中首次提出【1 1 。但直到9 0 年 代，才成为研究的热点。公式识别技术发展如此缓慢，与数学公式自身特点给公式识别 所带来的困难是分不开的。首先，数学公式中所包含的符号种类较多，如英文字母、希 腊字母、运算符号等；而且根据这些符号所起作用的不同，在尺寸、位置、形态上有很 大差异，例如上下标的尺寸远小于一般符号，而功能符号( 如，兀等) 尺寸会比一 洞北大学t 学硕士学位论文 暑暑皇富鼍詈皇詈皇鲁鼍置皇鼍皇皇! 詈詈詈詈詈曼! 曼! 暑曼詈詈詈詈詈! 鼍詈詈曼曼皇皇皇鼍皇曼暑置量! ! 詈曼皇鼍詈詈! 喜詈皇皇詈置i 皇曼鲁葛暑! 鼍詈皇詈鼍詈詈皇晕量_ 般符号大很多；构成函数的字母多为正体，而表示变量的字母多为斜体。另外公式符号 笔画少、相似性高、不易区分。因此，公式符号的切分与识别远比简单一维分布的普通 文本复杂的多。 到目前为止，已有一些文章专门探讨数学公式处理某一方面的基本方法，如：公式 含义的分析，公式的定位，符号的切分识别等。也有一些文章不但提出了基本处理方法， 还构造了比较完整的实验系统或针对特定情况处理的实际系统，但还没有成形的产品问 世l z 刮。多数论文在讨论中沿用了传统的切分和识别方法，没有考虑到公式的特殊情况。 在为数不多的涉及公式符号切分和识别的方法中，切分环节多是利用投影或间隙特性， 而识别方法仍然采用传统的模板匹配法、结构分析法和神经网络法等。o k a m o t o 和m i a c s 提出的系统首先运用了递归目标结构分析法来分割字母和符号，同时建立关系树，然后 用传统的模板匹配法识别符号。l e e 6 】提出了一个识别印刷体数学公式的系统。首先运 用传统的统计方法来识别单个字母和符号，然后用面向过程的方法将二维结构的公式转 换为一维结构的字符串。l e e 和w a n g 7 】提出了既能识别文本又能识别数学公式的系统， 在理解公式的同时应用特征提取技术和最近邻算法来识别字符，建立符号关系树来描述 表达式。此外还提出了用于纠正识别错误的一些启发式规则。f a t e m a n 8 】设计了一个典 型的系统，该系统能成功地将排好版的数学公式转换成l i s p 表达式。对识别部分采用 了不同的方法，如计算h a u s d o r f f 距离和符号灰度值等。对结构分析部分采用了简单的 递归降序分割法。l e e t 7 】介绍的系统将连通域搜索的结果作为待识别符号，利用统计方 法设计了一个能处理整个文档内容的识别器。m s u z u k i 【9 j 等人介绍的英文文献识别系 统i n f t y 由两个独立的识别引擎组成，分别针对普通文本和数学符号进行识别。 o k a m o t o t l 0 1 1 1 1 1 等人采用递归的水平和垂直投影切割方法对符号进行切分，符号识别利用 的是模板匹配法。h a 1 2 】利用x y 切分方法得到公式中的符号，然后采用神经网络方法进 行符号识别。u g a r a i n 1 3 】等人设计了多分类器结构的多层次符号识别引擎，提高了公式 符号识别的鲁棒性。实验表明，粘连字符仍是造成公式识别率低的主要原因，但是目前 处理粘连字符的论文很少。其中w a n g 1 4 采用曲线最短路径分割方法处理粘连字符。a n o m u r a 1 5 】等人设计了在粘连字符的四角寻找独立字符，确定分割线位置的切分方法。 国内对数学公式识别的研究尚处于起步阶段，目前还没有成形的印刷体公式识别的 系统问世，主要的研究机构有南开大学机器智能研究所【1 6 】，哈尔滨工程大学自动化学院 第1 章引言 【17 1 ，沈阳工业大学和大连理工大学等，已有4 0 多篇相关的论文发表。 综上所述，印刷体数学公式的识别是当前o c r 识别技术研究的难点，距离实用还 有很大的距离。 1 3 文章组织 全文的组织结构可以概括如下： 第l 章绪论。简要叙述课题研究背景，数学公式识别的国内外研究现状。 第2 章数学公式识别系统概述。介绍了印刷体数学公式识别系统的组成。 第3 章数学公式字符的定位。介绍已有字符切分方法及其优缺点，指出所存在的 问题，在此基础上，采用基于连通特征的切分算法对公式符号进行切分，引入识别反馈 机制处理切分错误。 第4 章公式字符识别器的研究与设计。介绍字符识别预处理过程、特征抽取的方 法和识别器的设计过程。采用了带阈值的两级组合特征分类器，提高公式字符的识别率。 第5 章实验过程及结果分析。对新旧方法的识别结果进行对比，并对实验结果进 行分析。 第6 章总结和展望。对所做的研究工作进行总结，并对今后的研究工作提出建议。 河北大学工学硕七学位论文 皇! 皇皇皇皇曼置曼詈皇皇薯e 皇i nn u 晕詈量罾毫詈皇詈詈詈皇 第2 章数学公式识别系统概述 数学公式是绝大多数科技书刊的重要组成部分，它包含许多键盘无法直接输入的特 殊符号，手工输入十分繁琐。一个无法处理数学公式的识别系统，在应用于富含公式的 科技书刊时，往往会失去应用价值。而数学公式的二维嵌套特性、所包含符号的复杂性 及其数学符号表达含义的多样性，使得印刷体数学公式识别系统的开发成为模式识别领 域中一个具有挑战性的课题。 2 1 数学公式识别系统的组成 数学公式识别系统分为四个模块：公式抽取，公式识别，公式结构分析和公式重构。 系统框图如图2 1 所示。 图2 1 数学公式识别系统框图 公式抽取模块将独立公式( 独占一行的公式) 和嵌入公式( 混杂在文字中的公式) 抽取出来，以便进一步的切分与识别；公式识别模块分为切分和识别两个步骤，首先定 4 第2 章数学公式识别系统概述 位公式中的字符得到各个符号的位置坐标，再将进行预处理后的单个字符送入识别器得 到字符的编码，切分和识别结果存放在预先定义好的一个结构体中，以便为结构分析模 块提供信息；在公式结构分析模块，根据已经得到的公式字符的关联属性，如位置、尺 寸、字体等，借助已有知识确定符号之间的空间和逻辑关系，构造公式关系树，以便于 公式的重构；公式重构模块利用符号识别与结构分析的结果，构造出能够重现公式原貌 的通用格式文件( 如m a t h m l 、l a t e x 、p d f 等) 。 公式识别模块是整个数学公式识别系统的关键环节。由于公式中包括数字、英文字 母、希腊字母、运算符号等多种类型的字符和符号，大小不一，正斜体变化频繁，且在 空间上呈二维嵌套分布，使得传统的、比较成熟的o c r 核心对公式符号的切分准确率 和识别率都很低【1 8 】【19 1 。因此，有必要针对公式的特点，研究专门的公式符号切分和识 别算法。公式符号的识别性能直接影响结构分析和重构等环节的正常进行，并最终影响 公式识别系统的整体指标，鉴于公式符号的独特之处，研究准确性高，适应公式特点的 字符切分与识别方法，是十分重要的。因此，它是数学公式识别系统的核心。 2 2 数学公式识别的难点 数学公式识别技术发展如此缓慢，是与数学公式自身的特点分不开的。在数学公式 中，字符和符号是按二维嵌套结构分布的，并且字符大小不一，这使得公式字符定位和 识别相当困难。总的来说，数学公式识别存在着以下几个难点： 公式中字符的出现位置是随机的，没有一定规律，有时只能根据上下文来判断 一个字符是否为公式字符的一部分，这就给公式中字符定位带来很大的困难。 字符的大小随着字符位置和内容的不同而改变。例如，数学公式中的上标、下 标、积分号。这就使得公式的结构更加复杂，增加了字符定位的负担。 一些公式中的字符存在粘连现象，严重影响了切分和识别。 公式中一些字符由许多部件组成，宽窄不一，给切分造成了不便。 公式中的字符结构简单，受噪声影响较为严重，包含的分类信息少，相似字符 比较多，相似程度极高，给识别造成了不便。 一些符号虽然互不粘连，但是在投影上不可分，如x 2 + y 2 ，虽然采用基于连 通特征的切分方法可以将它们切开，但是会增加处理时间。 5 河北人学丁学硕十学位论文 公式中的字符虽然只有2 0 0 多个，但是这些符号字体多变，大小不一，变量一 般都用斜体书写，而函数名( 如表2 1 所示) 、数字和符号等则用正体书写( 如 图2 2 所示) ，某些字符笔画不够规范，接近于手写，增加了识别的难度。 表2 1 数学公式中常见函数名统计 s i n ( 正弦)a r c s g c ( 反正割)l i m ( 极限) c o s ( 余弦)a r c c s c ( 反余割) l o g ( 对数) t a n ( 正切)a r c t a n ( 反正切)r o t ( 旋度) c t g ( 余切)a r c c t g ( 反余切)e x p ( 指数) s e c ( 正割)a r c c o s ( 反余弦)a b s ( 绝对值) c s c ( 余割)a r c s i n ( 反正弦) l g ( 常用对数) g r a d ( 梯度) d i v ( 散度)i n ( 自然对数) 图2 2 公式中字符正斜体示意图 第3 章公式字符切分 第3 章公式字符切分 字符识别器的辨识对象，应当是规范化了的单个字符图像。而公式抽取模块得到的 结果是待识别公式块的位置坐标。因此，需要对公式块中的字符进行切分、平滑去噪、 归一化后送识别器进行识别。正确的识别往往依赖于正确的切分，因此字符切分是本系 统关键的一步。 3 1 公式字符切分方法综述 3 1 1 间隙切分 间隙切分是利用字符间隙和字符间距进行字符切分，是最早使用的一种方法【2 0 】。这 种方法非常简单，利用基本相同的字符宽度和相近的字符间隙，通过搜索字符间隙进行 切分。但是该方法要求字符宽度和字符间隙基本相同，对输入图像的质量的依赖性很大， 对于印刷质量很好的纯中文文本这种方法能够取得很好的效果，但是对于数学公式图 像，这种切分方法效果很不理想，比如根号表达式中的公式符号就不能正确切分。 3 1 2 投影切分 投影切分是利用水平和垂直投影特征来进行字符切分【2 1 2 2 1 。由于投影特征易于计 算，因此该方法容易实现并且速度较快。但是对于二维分布并且多有字符包围和相互粘 连的数学公式图像，由于缺乏清晰的投影特征，投影法也很容易失败。 3 1 3 反馈切分 反馈切分是通过识别效果的反馈信息来判断切分的正确性，这种方法的基本原理是 以识别信度作为切分标准。该算法一般由两个步骤组成：首先是寻找并生成切分假设， 即先利用文本图像的投影特征或者字宽、字高、字距等参数，找到可能的切分位置集； 然后根据识别结果选择最佳切分假设，即每一个可能的切分位置，由识别模块进行验证， 河北大学工学硕十学位论文 用动态规划算法找到最佳切分位置。文献【2 3 】中有一个这种方法的例子。它由一个切分 算法得到大量的候选切分点，然后将相邻的候选切分点进行组合送到识别器识别，如果 识别结果得到较高的可信度，就将组合后的切分点作为切分结果。这种方法是在近几年 识别算法完善的基础上发展起来的，由于它可以利用大量的先验知识来进行切分的指导 和判断，所以它在具有一定先验知识的领域应用前景很广。 3 1 4 染色切分 在染色切分过程中，对图上的点进行处理都是基于该点的八邻域的。点的八邻域是 一个以该点为中心的3 3 窗口。其步骤是：首先确定最左边缘的点，以这个点为起点， 实施染色法，对遇到的每一黑点，先把它染为一种特殊的( 黑色、白色以外的) 颜色， 然后再检查它周围的8 个点，如果这8 个点中有黑点存在，就接着分别以这些新的黑点 为中心，染上特殊的颜色，再检查。如此循环递归，当这个循环过程停下来的时候，所 有与最开始的起始点在同一个连通区域内的黑点都被染上了这种特殊的颜色。这个算法 按深度优先的顺序执行，将纠缠在一起的符号中最左面的像素染成特殊颜色。这时程序 再次扫描这个整体，就可以把标记了特殊颜色的像素点从整体中分离。从最左面一层层 地剥离了原来纠缠在一起的符号，实现了符号的切分。这种方法虽然能处理投影法无法 切分出来的交叠字符的情况，但它运算量大，速度慢。 3 2 影响数学公式切分的因素 字符切分是数学公式识别的难点之一，如前所述，数学公式结构复杂，相邻字符的 大小和位置的关系也不明确，所以想通过某种规律来快速、准确地定位字符十分困难。 影响数学公式切分的因素主要有以下几个方面： 1 )在数学公式中，字符和符号是按二维的复杂结构排列的，并且公式中的字符 大小不一、位置不定、形成二维嵌套结构( 如图3 1 ( a ) 所示) ，而普通文本都是 呈一维分布的，只需对文本域进行简单的行字切分就可以将文本域中的字符切分开 来。因此对数学公式中符号的切分比普通文本困难得多。 2 )由于印刷、扫描等诸多因素，数学公式中的字符之间有明显的粘连现象( 如 图3 1 ( b ) 所示) ，这些粘连的字符给字符的切分带来了不便。 8 - 第3 章公式字符切分 3 )数学公式中有许多符号是由多个部件组成的( 如图3 1 ( a ) 中的= 和) ， 在进行切分的时候并不能够确定该部件是一个符号还是一个符号的一部分，仅仅按 照部件之间的距离将其进行合并，容易将两个邻近字符合并到一起送识别器进行识 别，造成字符的识别错误。 ( a ) 带有极限和分数的二维公式 3 3 字符切分方法 ( b ) 带有粘连字符的公式 图3 1 待处理的数学公式图像 对于以上几种数学公式的情况，通过对相关知识的学习和研究，本文采用了带有识 别反馈机制的投影法和基于连通特征的切分方法对公式字符进行切分，首先采用投影法 将不存在包含关系和交叠关系的数学公式字符进行切分，然后将切分所得的字符块送到 公式字符识别器进行处理，对于识别距离大于一定阈值的字符，采用基于连通特征的切 分方法来定位，这样就可以正确切分交叠或包围结构的字符。具体切分过程如图3 2 所 示。 河北大学工学硕十学位论文 3 3 1 基于连通特征的切分 图3 - 2 数学公式切分流程图 连通区搜索的目的是找出图像中所有连通的部件。本文设计了一种可以一次搜索到 所有连通区部件的搜索算法。对于图像页，自左向右，自上而下扫描，点p 所属的连通 区只与点o 、1 、2 、3 有关，与点p 相关的点的位置如图3 3 所示。 图3 - 3 点的位置关系图 基于连通特征的切分算法描述如下： 设标志缓冲区全为o ； w h i l e ( 未读到文件尾) 第3 章公式字符切分 读取f 位置像素点值赋给v a l u e ； i f ( v a l u p = = 1 ) 将o 位置的像素点值赋给b i t s o ； 将1 位置的像素点值赋给b i t s 1 ； 将2 位置的像素点值赋给b i t s 2 ； 将3 位置的像素点值赋给b i t s 3 ； i f i 只有0 位置是黑点) k = - o ： i f i 只有1 位置是黑点) k = l ； 坂只有2 位置是黑点) k = - 2 ； i 坟只有3 位置是黑点) k = - 3 ： 敢只有0 ，1 位置是黑点) k = - i ；与情况1 相同 珉只有0 ，2 位置是黑点) k - - 4 ； i f i 只有0 ，3 位置是黑点)k = - 3 ：与情况3 相同 坂只有l ，2 位置是黑点) k = - i ； i f i 只有l ，3 位置是黑点) k = - 5 ； 诋只有2 ，3 位置是黑点)肛6 ； i f ( 只有0 ，1 ，2 位置是黑点) k = - i ；与情况1 相同 i f i 只有0 ，l ，3 位置是黑点) k = - 3 ；与情况3 相同 i f 【只有o ，2 ，3 位置是黑点) k - - 4 ；与情况4 相同 i f i 只有1 ，2 ，3 位置是黑点) k = - 5 ；与情况5 相同 i f ( o ，l ，2 ，3 位置都是黑点) k = - 5 ；与情况5 相同 i f ( o ，l ，2 ，3 位置都是自点) 扣7 ； s w i t c h( 七) c a s eo ：令l a b e l i 等于0 位置像素点的l a b e l 值，更新该连通区的坐标； c a s el ：令l a b e l i 等于1 位置像素点的l a b e l 值，更新该连通区的坐标： c a s e2 ：令l a b e l i 等于2 位置像素点的l a b e l 值，更新该连通区的坐标； 河北大学工学硕十学位论文 c a s e3 ：令l a b e l i 等于3 位置像素点的l a b e l 值，更新该连通区的坐标； c a s e4 ：令l a b e l i 等于o ，2 位置像素点的l a b e l 值小的那个值合并 o ，2 所在的连通区，更新该连通区的坐标； c a s e5 - 令l a b e l i 等于l ，3 位置像素点的l a b e l 值小的那个值，合并 1 ，3 所在的连通区： c a s e6 ：令l a b e l i 等于2 ，3 位置像素点的l a b e l 值小的那个值，合并 2 ，3 所在的连通区； c a s e7 ：分配新的缓冲区纪录新的连通区，并用l a b e l i g e 录f 位置像 素点所属的连通区； s w i t c h ( 七) i f w h i l e ) 结束 在算法执行过程中只需扫描图像一次，而且只需为l a b e l 数组开辟图像行宽大小的 缓冲区，因此本算法具有速度快，占用内存少的优点。 3 3 2 公式字符切分的实现 对于普通的不存在包含关系和交叠关系的数学公式采用投影法就可以将公式中的 符号进行定位，将那些独立的字符块送到公式字符识别器进行处理，对于那些用投影法 不能切分的字符将其送入识别器后，识别距离大于一定阈值，对于识别距离大于一定阈 值的字符系统认为它是交叠字符或是有包围结构的字符，对这些字符采用基于连通特征 的切分方法将其切分，然后再送到识别器进行识别，公式块切分过程如图3 4 所示： ( a ) 原始公式图像 第3 章公式字符切分 ( b ) 垂直投影切分结果 ( c ) 水平投影切分结果 ( d ) 基于连通特征的切分结果 图3 - 4 数学公式块切分过程 图3 - 4 所示公式中有些字符被切分成多个部件，每个部件被单独送到识别器进行识 别，识别后还需要按照相应的规则将这些字符进行合并处理。由两个或两个以上连通区 部件组成的公式符号归纳如图3 5 所示，第一行是由两个连通区部件组成的公式符号集 合，第二行是由三个连通区部件组成的公式符号集合。 图3 5 由多个部件组成的字符 通过对这些字符观察，发现由多个连通体组成的字符分为以下四类： 河北大学工学硕十学位论文 ( 1 ) 字符在竖直方向可以分为多个连通体的情况，包括：、；、= 、? 、! 、i 、 j 、兰、s 、2 、圭、2 等。 ( 2 ) 字符在水平方向可分为多个连通体，如“、 、等。 ( 3 )同一个字符的大连通体部件外接矩形框包含小连通体外接矩形框，如等。 ( 4 ) 三个距离很近的小连通体可以构成一个字符，如、兰等。 对于这些字符进行识别时，识别结果是单个连通区部件的编码，但是有些连通区部 件本身不对应任何编码，这时需要根据已知信息对连通区部件进行合并。具体步骤为： 步骤1 ：在切分时记录下每个部件的位置坐标。设a ，b ，c 为任意三个连通区，它们 的左上角及右下角坐标分别为( a ，a ，) ，( a ，a b ) ，( 局，e ) ，( 耳，b b ) 和( c ，g ) ，( c ，g ) 。 定义d 为一个阈值，该值表示公式中普通字符的平均高度，如公式3 1 所示。 拈吉善( 彳- a i , ) 。- 1 ) 步骤2 ：利用识别结果和部件的位置坐标对由多个部件组成的字符进行合并。合并 连通区时，从上向下进行扫描，对这些连通区部件的合并规则如下所示： 规则1 ：对于由两个部件组成的字符，如果公式3 2 成立，则合并后字符的左上角 及右下角坐标分别为( a ，a ，) 和( 毋，坟) 。 ( k 一耳l d ) n ( 1 4 一忍l d ) = l ( 3 - 2 ) 规则2 ：对于由三个部件组成的字符，如果公式3 3 成立，则合并后字符的左上角 及右下角坐标分别为( m i n ( a l ，局，c ，) ，m i n ( a , ，e ，c ，) ) 和( m a x ( 4 ，b ，c ) ，m i n ( d b ，色，c 6 ) ) ( m a x ( 4 ，b r ，c ) 一m i n ( 4 ，马，c ，) ) d = 1 ( 3 - 3 ) 【( m a x ( a 6 ，眈，c b ) 一r a i n ( a , ，e ，e ) ) d = 1 步骤3 ：最后将合并后的字符送到识别器进行识别。 采用上述规则能够将由多个连通区组成的公式符号合并，但是对于、等符 号，它们的高度大于阈值，无法合并。考虑到它的每个部件都对应f 这个符号的编码， 可以将它的编码和位置信息送入结构分析模块进行合并。 第4 章公式字符识别器的研究与设计 第4 章公式字符识别器的研究与设计 经过几十年的研究，许多现有的符号识别技术已经能够获得令人满意的结果。但是 数学公式字符的特点给识别带来很大的困难。为了正确识别，首先必须将这些符号进行 识别预处理，即去除字符图像中的噪声或毛刺，避免它们对字符特征抽取的影响，然后 将去除噪声后大小不一的字符归一化成相同大小，提取特征和字典中的字模进行匹配得 到该字符所对应的编码。 4 1 数学公式字符识别方法综述 本节首先介绍字符识别中常见的一些算法，然后结合该系统的需要提出一种适合该 系统的字符识别方法。经过多年的研究，不同的方法被用于不同的符号识别，现在被研 究的主要的识别方法有统计识别方法、结构识别方法、神经网络识别方法以及s v m 识 别方法。 4 1 1 统计识别方法 统计识别方法又称为决策论识别方法，这种识别方法一般选取同一类字符中共有 的、相对稳定的并且分类性能好的统计特征作为特征向量。常用的统计特征有字符二维 平面的位置特征、字符在水平或者垂直方向投影的直方图特征、矩特征和字符经过频域 变换或其它形式变换后的特征等。它是从被研究的模式中选择能够表示它的若干特征 ( 设有d 个) ，每一个模式都可由一个d 维特征向量来表示，于是每一个模式就在d 维 特征空间占有一个位置。这样就构成了模式集，通过各类模式集的概率分布，推断出输 入模式属于某类模式集的概率，从而进行决策。即统计模式识别是从模式中抽取出一组 特征的测量值，在数值特征基础上，利用决策函数对模式的特征向量进行分类的方法， 是一种确定性的方法【2 4 1 1 2 5 1 。常见的统计模式识别方法有： - 模板匹配法。模板匹配并不需要特征提取过程。字符图像直接作为特征，与字典中 的模板相比，相似度最高的模板即为识别结果。这种方法简单易行，可以并行处理； 河北大学丁学硕士学位论文 但是一个模板只能识别同样大小、同种字体的字符，对于倾斜、笔划粗细不均没有 良好的适应能力。 利用变换特征的方法。对字符图像进行二进制变换( 如w a l s h ，h a r d a m a ) 或更复 杂的变换( 如k a r h u n e n l o e v e ，f o u r i e r ，c o s i n e ，s l a n t 等) ，变换后特征的维数大 幅度降低。但是这些变换不是旋转不变的，因此对于倾斜变形的字符的识别会有较 大的偏差。二进制变换的计算虽然简单，但变换后的特征没有明显的物理意义。k - l 变换虽然从最小均方误差角度来说是最佳的，但是运算量太大，难以实用。总之， 变换特征的运算复杂度较高。 笔划密度特征。笔划密度的描述有许多种，这里采用如下定义：字符图像某一特定 范围的笔划密度是在该范围内，沿水平、垂直或对角线方向扫描时的穿透次数。这 种特征描述了汉字各部分笔划的疏密程度，提供了比较完整的信息。在图像质量可 以保证的情况下，这种特征比较稳定。在脱机手写体的识别中也经常用到这种特征。 但是在字符内部笔划粘连时误差较大。 基于统计特征的字符识别技术对形近字符区分能力弱，因此，通常应用于字符的粗 分类。对于识别字符集比较小、输入图像质量比较高的图片也可以担当主要的识别任务。 4 1 2 结构识别方法 结构识别方法，就是把待识别对象看成是一个模式，该模式又可以分化成若干个子 模式，子模式又可以分解为若干个基元，可以通过对基元的识别进而识别子模式，最终 达成对该模式的识别。这种技术首先要提取字符的结构，根据识别策略的不同，结构的 选择也有所不同。可以选择字根、笔划，也可以选择比笔划更小的笔段。提取出的结构 又称作字符的子模式、部件、基元。所有基元按照某种次序排列起来就成了字符的特征。 基于结构的字符识别实际上是将字符映射到基元组成的结构空间进行识别。结构字符识 别技术的识别过程是在提取基元的基础上，利用形式语言和自动机理论，采取词法分析、 树匹配、图匹配和知识推理的方法分析字符结构的过程。常用的结构特征有：笔划的走 向、孤立的点，以及是否含有闭合笔画等。由于汉字自身具有很强的结构性，结构特征 字符识别技术在汉字识别上有较多应用。常见的结构模式识别方法有： 第4 章公式字符识别器的研究与设计 识别决策树方法。决策树也可以成为多级识别树或多级分类器，这是文字识别中进 行分类、识别的一种有效的方法。识别决策树就是根据某个特征基元的有无，对整 体作一分为二的处理，通过逐级分类判别，直至树叶得到最后的识别结果。识别决 策树是一个以上结点的有穷集，它存在一个唯一的根结点，其余结点可以分为若干 个互不相交的子树集合，叶子结点的集合即为识别字符集。图4 1 所示为数字0 9 的 识别决策树。在一个识别决策树中有两个重要信息：其一是关于结点的信息，即描 述结点的字符集；其二是描述相邻结点关系的信息。设计识别决策树时需要特征越 少越好，也就是希望达到识别结果所经过的步长要尽可能短，如果识别字域为n ， 理想的情况是只需要1 0 9 ，n 个特征，但实际识别时往往需要更多的特征。 0 9 8 香是 5 t 在上郜下部是直妄 图4 1 数字0 - 9 的识别决策树 戛旨撬n 句法识别器。在句法识别中，第一种信息相当于模式基元，第二种信息定义了基元 与其他模式之间的物理关系。在字符识别中，一个字符就是一个模式，一个模式又 可以分解成若干个子模式，不能再分的子模式称为基元。这样一个字符就可以用基 元和子模式的多树结构信息来描述，从而形成模式的形式语言描述文法。因此，不 同的字符模式有不同的描述文法，对各种不同文法设计出识别器，就可以依据字符 的结构进行识别。 叉 蓐 是熏一个一 河北大学- t 学硕士学位论文 与统计识别方法相比，字符的结构识别技术更便于区分字形相近的字符。但是由于 对结构特征的描述和比较要占用大量的存储和计算资源，因此算法在实现上相对复杂、 识别速度慢。 也有人将统计识别与结构识别相结合，网格特征就是结构识别与统计识别结合的产 物，字符图像被均匀地或非均匀地划分为若干区域，称之为“网格。在每一个网格内 寻找各种特征，如笔划点与背景点的比例，交叉点、笔划端点的个数，细化后的笔划的 长度、网格部分的笔划密度等。特征的统计以网格为单位，即使有些点的统计有误差也 不会造成太大的影响，增强了特征的抗干扰性。 4 1 3 神经网络识别方法 利用神经网络【2 6 】来进行模式识别，不仅可根据样本进行学习，改善识别能力，而且 不需要对模式分布进行一些统计上的先验假设可提高自适应性。由于神经网络的高速并 行处理，分布存储信息等特性符合人类视觉系统的基本工作原理，具有很强的自学习性， 自组织性，容错性高，非线性高，鲁棒性强，并具有联想记忆功能和推理意识功能等， 能够实现目前基于计算理论层次上的模式识别理论所无法完成的模式信息处理工作。选 用神经网络方法进行字符识别，是因为神经网络具有如下特点：极强的抗噪声能力，并 行处理的能力；算法简单，运算量小。常见的神经网络识别方法有b p 神经网络方法和 自组织特征映射神经网络方法。 4 1 4s v m 识别方法 s v m ( s u p p o r tv e c t o rm a c h i n e ，支持向量机) 的基本思想【27 j 是：首先通过非线性 变换将输入空间变换到一个高维空间，然后在这个新空间中求的最优线性分类面，而这 种非线性变换是通过定义适当的内积函数来实现的。支持向量机的输出是若干中间层节 点的线性组合，而每一个中间层节点对应输入样本与一个支持向量的内积，因此又被叫 做支持向量网络( 如图4 2 所示) 。由于最终的判别函数只包含与支持向量的内积的求 和，因此识别时的计算复杂度取决于支持向量的个数。 第4 章公式字符识别器的研究与设计 输f l ： 8 g n ( e a i y i k “，砷4 - i - - - 1 权值w t = 口i n 旗卡s 个支持向馈 xj ，x 2 。，k 的 ：辩线性变换 输入向节 x = ( x l ，x 2 ，x d ) 图4 - 2 支持向量机示意图 这种方法是建立在统计学习理论的v c 维理论和结构风险最小原理基础上的，根据 有限的样本信息在模型的复杂性( 即对特定训练样本的学习精度) 和学习能力( 即无错误 地识别任意样本的能力) 之间寻求最佳折衷，以期获得最好的推广能力。 在s v m 中，只要定义不同的内积函数，就可以实现多项式逼近、贝叶斯分类器、 径向基函数方法、多层感知器网络等许多现有学习算法。目前，s v m 算法在回归估计、 语音识别、人脸图像识别、文章分类、字符识别等方面都有应用。 4 2 识别预处理 现实系统中的噪声是不可避免的，是影响数学公式识别效果的重要因素，在预处理 阶段，可以采用图像平滑的技术来减少各种干扰因素，从而加强有用信息口8 】；另外公式 中的字符大小不一也是影响字符识别正确率的主要因素，因此在识别之前也要将字符归 一化成规定大小。 在进行预处理之前，首先要清楚数字图像的表示法。数字图像的通用表示法是位图 方式。二值图像足以满足字符识别的信息要求，二值图像的表示法有点阵表示法和跳转 表示法两种。点阵表示法很直观，一个坐标点对应一个像素点，适用于以像素为处理单 位时的图像描述；跳转表示法直接采用跳转次数以及跳转坐标来描述图像，突出了图像 的跳变特征，用跳转法表示图像，可以减少处理的数据量，从而大大提高处理速度。点 阵表示法和跳转表示法是取图像的不同特征来描述同一幅图像，二者之间可以相互转 换。以下对两种图像表示法分别进行介绍。 1 q 洞北大学1 = 学硕十学位论文 对于二值图像，普通点阵法以样点的像素值函数来表示图像，其表达式为： 厂( ) ： l薯翥七譬童0 i m , 0