（计算机应用技术专业论文）印刷体数学公式符号的切分与识别.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 ，光学字符识别) 技术可以将 印刷体文献中的文字高速、自动地输入计算机，且取得很高的识别率。但是科技文献中 包含大量的数学公式，o c r 还不能对其进行正确识别，只能将其存储为图片格式，不 仅占用大量空间，而且不能对其进行再编辑。因此，数学公式自动识别在将科技文献转 化为电子文档的过程中具有重要的意义。 印刷体数学公式识别系统包括公式抽取、公式符号识别、公式结构分析和公式重构 四个组成部分。其中，公式符号识别模块是系统的核心部分，其功能是将公式中的符号 图像转换成相应的代码，分为符号切分和符号识别两个阶段。针对传统的文字识别器在 识别公式符号中存在的问题，本文对印刷体数学公式符号切分和识别展开研究，设计了 能够适应公式符号二维分布、大小不一、多交叠、多字体等特点的切分和识别算法。首 先采用迭代自组织的符号切分方法对公式符号进行切分，为符号识别提供正确的符号位 置信息；然后对符号进行预处理，并采用基于游程特征的符号识别方法对公式符号进行 识别。通过对不同印刷质量文档的实验表明，本文设计的符号切分和识别方法能够取得 较高的识别率和令人满意的处理速度。 关键词光学字符识别；数学公式识别；字符切分；迭代自组织；游程特征 a b s t r a c t a b s t r a c t a sac a r r i e ro fr e c o r d i n gt e c h n i c a li n f o r m a t i o n ，c o n v e n i n gs c i e n t i f i cd o c u m e n t st o d i g i t a lf o r mi sa nu r g e n tn e e di nb u i l d i n gi n f o r m a t i o ns o c i e t y a tp r e s e n t ，t h eo c rs y s t e m s t h a th a v eb e e nw i d e l yu s e dc a na u t o m a t i c a l l yr e c o g n i z et h eo r d i n a r yt e x tw i t hh i g hs p e e da n d a c c u r a t er a t e as c i e m i f i cd o c u m e mg e n e r a l l yc o n t a i n sal a r g en u m b e ro fm a t h e m a t i c a l e x p r e s s i o n st h a tt h eo c rs y s t e m sc a n n o td e a lw i t h ，s ot h em a t h e m a t i c a le x p r e s s i o n sh a dt o b es t o r e da si m a g e sw h i c hn o to n l yt a k el o t so fs t o r a g es p a c e ，b u ta l s oc a n n o tb er e e d i t 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 fm a t h e m a t i c a le x p r e s s i o nb e c o m e so n eo ft h ek e yv e h i c l e si n t h ed r i v et o w a r d st r a n s c r i b i n gs c i e m i f i cd o c u m e m si m oe l e c t r o n i cf o r m s t h er e c o g n i t i o ns y s t e mo fp r i n t e dm a t h e m a t i c a le x p r e s s i o n sc a nb ed i v i d e di m of o u r s t a g e s ：m a t h e m a t i c a le x p r e s s i o ne x t r a c t i o n ，m a t h e m a t i c a ls 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 sa n dm a t h e m a t i c a le x p r e s s i o nr e c o n s t r u c t i o n t h em a t h e m a t i c a ls y m b o lr e c o g n i t i o n i sa ni m p o r t a n ts t a g ei nt h es y s t e ma n di t sf u n c t i o ni s g e t t i n gt h ec o d eo fs y m b o l sf r o m e x p r e s s i o ni m a g e s i tc o n s i s t so ft w os t e p s ：s y m b o ls e g m e n t a t i o na n ds y m b o lr e c o g n i t i o n a i m i n g a tt h ef a c tt h a tt h ec o m m e r c i a lo c r s y s t e m sc a n n o tr e c o g n i z em a t h e m a t i c a ls y m b o l s c o r r e c t l yb e c a u s eo ft h ed 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 or e s e a r c hw o r ko nt h er e c o g n i t i o no fp r i m e de x p r e s s i o n s a na p p r o a c ht h a ta d a p t st o m a t h e m a t i c a le x p r e s s i o nf e a t u r e ss u c ha sat w o d i m e n s i o n a ls t r u c t u r ea n daw i d ev a r i e t yo f f o ms i z ea n ds t y l ei sp r o p o s e df o rs y m b o ls 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 , a ni t e r a t i v e s e l f - o r g a n i z i n g m e t h o di su s e dt o s e g m e n ts y m b o l s i n e x p r e s s i o n s s e c o n d l y , a p r e - p r o g r e s s i n gi se m p l o y e dt od e a lw i t ht h es y m b o li m a g e ，a n das y m b o lr e c o g n i t i o nm e t h o d b a s e do nr u n l e n g t hf e a t u r ei sp r o p o s e dt og e ts y m b o lc o d ef r o mt h ei m a g e t h ee x p e r i m e n t s o nd i f f e r e mq u a l i t yd o c u m e n t ss h o wt h a tt h e s em e t h o d sc a no b t a i ns a t i s f a c t o r yr e c o g n i t i o n a c c u r a c yw i t hah i g hs 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 le x p r e s s i o nr e c o g n i t i o n ；s y m b o ls e g m e n t a t i o n ；i t e r a t i v e s e l f - o r g a n i z i n g ；r u n l e n g t hf e a t u r e 河北大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教育机构的学位或证书 所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了致谢。 作者签名：查堕壅!日期：盟年鱼月上日 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留并向国 家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。学校可以公布 论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 本学位论文属于 l 、保密，在2 鲤仝年笪月f 同解密后适用本授权声明。 2 、不保密1 3 。 ( 请在以上相应方格内打“”) 作者签名： 誊海燕 导师签名：塑竖鱼! 日期：垃年月上日 日期：矗乒年上月上日 第1 章引言 1 1 研究背景 第1 章引言 近年来，随着网络技术的飞速发展，技术资源的共享同趋频繁，将印刷文献转换为 电子文档成为信息交流的重要手段。利用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 技术应用领域，推进科技文献数字化进程的 关键性课题，具有重要的理论意义和良好的应用前景。 本课题来源于河北省自然科学基金资助项目印刷文档识别与重构若干核心技术的 新开拓( 项目编号：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 l l l 在其博士论文中首次提出，在随后的1 0 年内 陆续发表了几篇文章，但大部分工作停留在理论研究水平上。直到2 0 世纪8 0 年代后期 才重新得到研究者的重视。经过三十多年的发展，o c r 技术已经基本成熟，对普通文 本取得了很高的识别率，但是数学公式自身特点导致公式识别技术发展缓慢。目前，公 河北大学t 学硕十学何论文 式识别仍然处于理论研究阶段，市场上缺乏正确性高、适应性强的成熟产品。 国外对数学公式识别的研究较早，主要针对公式的定位和二维结构进行研究。除了 对数学公式识别某一方面的专门研究外，有些文章还构造出了比较完整的实验系统。 f a t e m a n l 8 】在一个数字图书馆项目中研究自动数学公式处理的问题，提出了一个能够将 无噪声的排版数学表达式转换成l i s p 表达式的原形系统。l e e 和w a n g l 7 l 设计了一个既 能识别文档中的文本又能识别文档中韵数学表达式的识别系统，该系统由六个模块构 成，完成数学表达式的自动抽取、识别和结构分析。s u z u k i m 和t a m a f i f t 9 】介绍了一 个英文文献识别系统i n f t y ，该系统由两个独立互补的识别引擎组成，分别对文献中 的普通文本和数学表达式进行识别。 由于数学公式属于复杂的二维嵌套结构，现有的适用于一维文本的字符切分方法不 能对其进行正确处理。大部分论文中，都是将单个连通域视为待识别符号，它可以正确 切分公式中具有二维嵌套结构的符号( 如“”，“p e ) 。公式符号笔画少，大部 分都是由一个笔画组成，但是对于由多个连通域构成的符号( 如“i ，“= ”) 来说， 它会被视为多个待识别符号，而不是作为一个整体识别，降低了符号识别率。另外， o k 锄o t 0 【l o 】【l l 】等人采用递归的水平和垂直投影切割方法对符号进行切分，h a 1 2 】是利用 x y 切分方法分割公式中的符号，前者是基于像素的切分，后者是基于边界框的切分。 实验表明粘连字符是导致公式识别错误的主要原因，而目前对粘连字符进行处理的文章 很少。其中，w a n g 1 4 1 采用曲线最短路径分割方法对粘连字符进行切分，n o m u r a l l 5 1 等人 设计在粘连字符的四角试探寻找独立字符，从而确定分割线位置。 在公式符号识别方面，因公式符号与普通的英文字符很接近，所以对识别方法进行 的研究很少，基本上沿用了传统的识别方法对公式中的符号进行识别。现有的识别技术 主要是统计方法【7 】【8 】【9 1 、结构分析方法【1 0 】【1 1 1 和神经网络法【1 2 】等。u g a r a i n 【1 3 1 等人从适应 公式符号特点出发，设计了多分类器结构的多层次符号识别引擎，提高了公式符号识别 的鲁棒性。 国内对数学公式识别的研究起步较晚。公式符号与汉字之间的区别较大，适用于汉 字的符号切分和识别方法不能处理公式符号情况。文献【1 6 】采用轮廓跟踪技术对中文印 刷文档中的数学公式字符进行切分，提取符号的网格和交叉点特征进行符号识别。文献 【1 7 】采用递归投影切分方法进行符号切分，同时设定高度阈值，采用种子填充算法对具 第1 章引言 有包含或者交叠结构的字符进行切分。也有人引入支持向量机对公式符号进行识别【2 1 】。 总之，国内外对数学公式识别的研究是文字识别领域的一个难点，还存在许多有待 解决的实质性问题。研究能够得到实际应用的系统性的公式识别方法，实现科技文献的 自动输入与理解，是公式识别研究的必然趋势。 1 3 文章组织 本文针对中文印刷体数学公式的识别进行研究，分别讨论数学公式符号的切分与识 别方法。全文的组织结构概括如下： 第1 章引言。简要介绍数学公式识别的研究背景和国内外研究现状。 第2 章数学公式识别系统。介绍数学公式识别系统的组成，并对公式识别难点作 了分析。 第3 章数学公式符号的切分。首先介绍已有字符切分方法，并指出将其应用到数 学符号切分的优缺点；在此基础上，提出并介绍本文采用的迭代自组织公 式符号切分方法。 第4 章数学公式符号的识别。首先总结现有的符号识别方法；之后详细介绍基于 游程特征的公式符号识别方法；最后对公式符号分类器进行设计。 第5 章实验过程及结果分析。分别针对数学公式符号切分和识别结果进行分析， 总结整体的符号切分识别结果。 第6 章结论与展望。对所做的研究工作进行总结，并对今后的研究工作提出建议。 河北人学t 学硕十学何论文 第2 章印刷体数学公式识别系统 根据数学公式输入方式的不同，可将数学公式识别系统分成联机识别和脱机识别两 类。联机识别是指公式书写与识别同时进行，是一种实时识别方法，也称为在线识别。 而脱机识别是对已经生成的公式图像进行识别，识别过程与文档生成过程无关，又分为 印刷体公式识别和手写体公式识别。本文研究e p , 届u 体数学公式识别方法。 2 1i ；p j 体数学公式识别系统组成 按照处理顺序，印刷体数学公式识别系统( 以下简称数学公式识别系统) 分为四个 功能模块：数学公式抽取，公式符号识别，公式结构分析和公式重构模块。如图2 1 所 不。 图2 1 数学公式识别系统框图 第2 章印刷体数学公式识圳系统 ( 1 ) 公式抽取模块。对印刷文档的扫描图像进行分析，定位文档中的独立公式和 嵌入公式。 ( 2 )公式符号识别模块。对公式抽取模块得到的公式图像进行符号切分，得到待 识别单个符号的图像；提取符号特征，在分类器中将提取的特征向量与标准 字典中的特征比较，得到符号图像所对应的代码，即识别结果。 ( 3 ) 公式结构分析模块。利用公式符号识别模块得到的识别结果和相关信息，确 定公式符号之间的逻辑关系。 ( 4 ) 公式重构模块。利用( 1 ) ( 2 ) ( 3 ) 的结果，构造出能够反映公式原貌的、 可以再编辑的标准格式文件( 如l a t e x 、m a t h m l 等) 。 数学公式符号识别是公式识别系统的核心部分，直接决定了系统的识别速度与识别 率。现有的o c r 识别引擎主要是针对文献中的普通文本进行切分识别，无法适应公式 的符号特点及结构特点，使得对公式符号的切分正确率和识别率都很低。因此，设计并 实现一个能够适用公式符号特点的识别引擎，是整个公式识别系统的关键之一。 2 。2 数学公式识别的关键问题 随着识别技术的迅速发展，现有的o c r 系统对普通文本的处理达到了很高的识别 率和识别速度。但是数学公式自身的特点，使得一般的o c r 技术无法对其进行正确识 别分析。数学公式识尉成为识别领域的一个技术难点，制约了o c r 技术的推广和应用。 数学公式具有以下特点： ( 1 )数学公式包含的符号种类很多。除了包含英文字符和数字外，还包括希腊 字母、运算符和特殊符号等。 ( 2 )公式符号包含的笔画少，结构简单；符号大小不一、相似性高，不易区分 ( 如图2 2 ( a ) 所示，数字“1 与英文字母“l ”相似) ；字体变化频繁， 常量、函数名_ 般使用正体，而变量为斜体( 如图2 2 ( b ) 所示) 。 ( 3 )公式中包含嵌套结构，通过空间位置关系表达不同含义，公式符号呈现二 维结构分布( 如图2 2 ( c ) 所示) 。 河北大学t 学硕十学佗论文 ( a ) 公式中相似符号示意图 ( b ) 公式符号正斜体示意图 ( c ) 公式二维结构示意图 图2 2 数学公式图像示例 上述这些特点，给公式符号切分和识别带来很大困难。现有的字符切分方法( 如投 影法、滴水法等) 仅适用于分割一维结构的普通字符，不能正确切分公式的二维嵌套结 构符号，如“”等。虽然公式符号集合不大，但是公式符号结构简单，包含的特征 信息少，且符号相似性高，适用于英文字符的识别方法对公式符号的识别率不高。因此， 设计适应公式结构特点的切分方法和针对公式符号集合的分类器，使之达到较高的识别 率，是对公式进行正确分析、理解和重构的基础。 第3 章数学公式符号的切分 第3 章数学公式符号的切分 公式符号识别模块首先要对待识别公式图像进行分析，确定公式包含的所有符号的 位置，得到单个符号的图像，之后才能对公式符号进行识别处理。正确的符号识别往往 依赖于正确的符号切分，因此公式符号的切分是公式识别系统实现的关键性步骤。 数学公式属于二维嵌套结构，相邻符号的大小和位置的相关性不明确，给符号切分 带来很大困难。公式符号的切分分为水平切分、垂直切分、右上角切分、右下角切分和 包含关系切分等，如图3 1 所示。加上印刷质量或者扫描质量低等原因，公式图像中不 可避免的出现符号粘连情况。实验表明，错误切分是造成识别率下降的主要原因之一。 ( a ) 水平切分示例 ( b ) 园 i 一 ( c ) 左上角和右上角切分示例( d ) 包含切分示例 图3 1 数学公式符号切分位置 3 1 公式符号切分方法综述 目前，应用到公式符号切分和粘连字符切分的方法有投影切分方法、轮廓跟踪方法、 曲线最短路径切分方法和四角试探切分法四种。 3 1 1 投影切分方法 投影法是利用行与行或者字与字之间的空白间隙对图像进行分割，分为水平投影和 垂直投影。水平投影就是在x 轴上统计每一像素行上的黑色像素的数量，依据行与行 7 圈一固 河北人学i ：学硕十学付论文 之间的空白特征，将可以确定行的位置。垂直方向上的投影与之类似。 投影法对一维结构的字符切分效果很好，投影特征易于计算，因此实现速度较快。 但对于由多个连通域组成的字符( 如“= ”，“i ”等) ，将被切分为多个待识别字符， 在识别之前需要对其进行合并。利用递归的水平和垂直投影切分虽然能分割公式中大部 分符号，但是无法处理具有包含关系或者交叠关系的符号( 如- ”，“f 等) 。 3 1 2 轮廓跟踪方法 利用轮廓跟踪方法1 3 2 1 能够获得图像的外部轮廓特征。对于数学公式符号，大部分符 号都由一个笔画组成，因此可以利用轮廓跟踪方法找到公式符号的边界，从而定位符号 的位置。 轮廓跟踪的基本方法是：首先根据某些严格的“探测准则 找到目标物体轮廓上的 像素，然后根据这些像素的某些特征用一定的“跟踪准则”找到目标物体上的其他像素， 从而得到整个目标物体的外围边界。下面介绍一个二值图像轮廓跟踪的算法。 ( 1 ) 按照从左到右，从下到上的顺序搜索图像，找到的第一个黑点一定是最左 下方的边界点，将其作为第一个边界像素，记为a 。它的右、右上、上、 左上四个邻点中至少有一个是边界点，记为b ； ( 2 ) 从b 开始找，按照右、右上、上、左上、左、左下、下、右下的顺序找相 邻点中的边界点c ； ( 3 ) 如果c 就是a ，则表明已经转了一圈，算法结束； ( 4 ) 否则从c 点继续找，直到找到a 为止。 判断当前点是不是边界点的条件是：如果当前点的上下左右四个邻点都不是黑点， 则将其视为边界点。 该方法将每个连通域看作是一个符号，将其应用到数学公式符号切分中，能够处理 二维结构的符号情况。但是对由多个连通域组成的符号，还需要额外合并处理，而且与 投影法相比，算法复杂性高，速度慢。 第3 章数学公式符号的切分 3 1 3 曲线最短路径切分方法 曲线最短路径切分方法是种常用的处理粘连字符切分的方法。该方法在待切分图 像上，寻找一条从上到下的代价最小的路径作为粘连字符的分割线。这种分割线分为两 部分，即通过黑色像素的黑色切割部分和不通过黑色像素的白色分割部分。显然，最优 的分割线应该是经过的黑色像素数最少，并且尽可能少地沿对角线移动。 这里只考虑三种运动形式：垂直向下移动、东南方向移动和西南方向移动。这种移 动形式避免了环状路径的形成，从而使算法变得简单。路径的代价可以通过下面的规则 计算【1 9 】： ( 1 ) 朝一个白色像素向下做一次移动的代价为0 ；而朝一个黑色像素向下做一次 移动的代价为1 0 。 ( 2 ) 朝一个白色像素向对角线方向做一次移动的代价为1 ；而朝一个黑色像素向 对角线方向做一次移动的代价为1 0 2 。 该方法算法简单，易于理解。但是不能保证找到的代价最小路径分割线都能正确的 分割粘连符号，错误的分割降低了字符切分正确率。 3 。1 4 四角试探切分方法 四角试探切分法是在粘连字符的四角上寻找独立字符，从而将粘连字符分成两个 字符。粘连切分步骤分为以下四步： ( 1 ) 在粘连字符x 的四角上寻找第一个字符。在单个字符集合中，将每个字符调 整到适当大小并加粗笔画，在粘连字符的四个角上进行模式匹配。如果当前 字符能够将粘连字符某个角上的所有黑色像素覆盖，则将其作为第一个切分 后的字符y 。 ( 2 ) 将找到的第一个字符从粘连字符上去除，剩下的部分视为第二个字符的图 像。 ( 3 ) 对第二个字符进行识别。识别方法同第一个字符识别方法相同，将识别得到 的字符记为z 。 ( 4 ) 确认切分正确性。把y 和z 字符图像合并成一个粘连字符w ，将x 与w 进行 河北人学t ：学硕卜学位论文 匹配。如果匹配成功，则将x 判断为由y 和2 组成的粘连字符。 在第( 1 ) 步和第( 3 ) 步中，都有笔画加粗的操作，它消除了符号不同字体和字号 间的细微差别，适应公式符号的字体和字号变化。第( 4 ) 步核实操作有效避免了因包 含关系引起的切分错误，如字符“d ( ”粘连时，通过( 1 ) 到( 3 ) 步后，可能将其切分 成字符“o 和“( ”，加入第( 4 ) 步就可以避免这种切分。 这种方法只是在粘连字符的四角上寻找能与之匹配的字符，如果粘连字符包含的字 符不在单个字符集合中，将找不到与之匹配的字符，不能进行切分。另外，该方法仅适 用于切分两个字符粘连的情况，不能处理多个字符的粘连。 3 。2 迭代自组织的公式符号切分方法 以上所提的符号切分方法，单独应用到数学公式符号切分时都有其局限性，降低了 符号切分正确率。针对数学公式的特点，本文提出了一种迭代自组织的字符切分方法对 公式符号进行切分。该方法不仅能够处理数学公式中具有包含或者交叠关系的符号切 分，而且依据不同的特征对由多个连通域构成的符号进行了合并处理。另外，通过对公 式中出现的粘连符号情况进行观察，采用两种快速简便的方法对粘连字符进行切分。具 体的切分过程如图3 2 所示。 识 别 结 果 图3 2 数学公式符号切分流程图 1 0 第3 章数学公式符号的切分 3 2 1 连通域搜索切分 数学公式包含的符号大部分都由一个连通域组成，为了适应公式符号的二维分布结 构，这罩采用连通域搜索算法对符号进行切分。连通域搜索算法是通过连通域标号的方 法，按照从左到右、自上而下的顺序扫描图像，找到图像中所有的连通域。 将连通域搜索算法【3 5 】得到的各个连通域作为单个待识别符号，视为对公式的切分假 设。对于公式中的大部分符号，该方法都能将其正确切分，特别是对于包含关系或者交 叠关系的符号( 如“”等) 。但是，该方法的一个缺陷就是会将由多个连通域组成的 符号切分成多个待识别符号，如图3 3 所示。 ( a ) 原始公式的图像 ( b ) 连通域搜索算法的切分结果 图3 3 连通域搜索算法切分数学公式示例 3 2 2 符号合并和分离规则 利用连通域搜索算法对公式进行符号切分后，那些由多个连通域构成的符号将被视 为多个待识别符号。这里通过一些符号合并规则对其进行适当的合并处理，这些规则是 基于符号间的几何位置关系以及符号识别结果建立的。 11 洞北入学f ：宁：帧十字何论文 詈詈! ! ! ! ! ! 皇! 鼍皇皇皇! ! 曼i i i 暑| 曼! 曼皇鼍! ! 詈詈曼曼! ! ! ! ! 曼詈曼曼暑曼! 詈詈詈墨曼! ! 毫暑皇詈皇詈鼍曼! 皇詈詈曼! ! ! 皇! 曼量! 曼! ! ! 皇! 设置，r ，b 为通过连通域搜索得到的公式区域中待识别符号s ，是，& 的连通 域，名，最，为所对应的连通域所包含的像素集合，置( 坼，_ ，咒，) 为连通域r 的四 个边界坐标，( r ) 为连通域r 的宽度( 如公式3 - l 所示) ，日( r ) 为连通域r 的高度( 如 公式3 - 2 所示) ，r a , 为连通域e 的宽高比( 如公式3 - 3 所示) ，c ( e ) 为连通域r 的识别 结果，d ( 曩，t ) 为连通域r 与t 在垂直方向上的间距。 形( r ) = 墨x r 一墨西 ( 3 1 ) ( r ) = 置一r i 以 ( 3 2 ) 赳= 形( 墨) 日( r ) ( 3 - 3 ) ( 1 ) 合并两个连通域部分交叠的符号。 规则3 1 ： 若rn e ga n dl r 而一e _ l 成a n di 形( r ) 一( e ) l o wa n d ( 1 日( 墨) 一日( 吩) i o ho ri h ( r ) 一日( e ) j _ m i n ( 日( r ) ，日( b ) ) 皖) 则 r = ru 弓，尸= p + c 其中见为两个连通域在x 轴方向上的偏差阈值，钆和眈分别为两个连通域宽度和 高度的偏差阈值。 主要用来处理“，“”，“”等由两个连通域构成且部件间部分交叠的符 号，如图3 4 所示。 图图 ( a ) 部分交叠的两个连通域( b ) 合并两个连通域后 图3 - 4 两个连通域合并示例 1 2 第3 章数公式符号的切分 mmmmmm ( 2 ) 合并三个连通域完全交叠的符号。该规则主要用来处理“”符号的合并情 况。 规则3 2 ： 若 t ，r k 冬ra n d，la n d 删k 1a n di 形( 一) 一形( r ) l 钆a n d w ( r j ) w ( r , ) 2 则 墨= rt jr ，ur ，只= p + f + 最 ( 3 ) 点合并。 规则3 3 ： 若c ( r ) = o x 2 ea n dd ( r ，一) 日( e ) + 臼a n d r j l r l j l r j x r 则 r l = r tur j ，p | = p l + p j 该规则主要用来合并包含的符号，如“i ”，“”等，如图3 5 所示。 豳 豳 ( a ) 包含点号的多个连通域( b ) 合并点号后 图3 5 点合并示例 ( 4 ) 线合并。 规则3 4 ： 若 c ( r ) = o x 2 da n dr a , o ra n dd ( r ，r ，) h ( r ，) + 9 a n d i e 一一只，一l 以a n dl w ( r , ) - w ( r ，) | j l l 并且在r 的上部或者下部存在横笔画，并且横笔画的宽度与r 的 宽度相等，则将此符号中的横笔画分割出来，剩下的部分再按照连通域搜索算法进 行切分。 ( 3 ) 确认是否为分数线粘连。 将第2 步得到的多个符号与原符号进行识别。如果原符号的识别距离大于第2 步切 分后的符号的平均距离，则认为原符号为分数线粘连，将第2 步得到的符号作为分 数线粘连切分结果。否则，认为原符号不存在分数线粘连，放弃第2 步的切分结果。 图3 - 9 为应用分数线粘连切分方法对分数线粘连符号的切分示例。该方法能处理大 部分的分数线粘连，但是对于单个分子或者分母与分数线粘连的情况，因其宽度与符号 平均宽度接近将不被当作分数线粘连的候选符号，该方法不能对其进行正确切分，如图 3 8 ( b ) 所示。 ( a ) 粘连公式( b ) 连通域搜索切分结果( c ) 分数线粘连切分成功 ( d ) 不能处理的粘连公式示例( e ) 连通域搜索切分结果( f ) 分数线粘连切分失败 图3 - 9 分数线粘连切分示例 3 2 4 建立粘连字典 目前已有不少针对粘连字符的切分方法提出，虽然这些方法能够对一些粘连字符进 行处理，但是算法复杂性比较大。为此，归纳公式中经常发生的规律性粘连符号组合， 将其中的高频度粘连组合符号视为一体，建立粘连符号字典，不失为一条处理粘连的捷 第3 章数。誓公式符号的切分 径。 数学公式中存在粘连符号的位置很多，如图3 1 0 所示，其中上下角标的粘连、左 右符号的粘连情况最多。通过统计实验中出现的粘连符号组合的同现概率，将其中常出 现的规律性符号组合作为整体进行训练建立粘连字典。 圈目圉画圆囵 图3 1 0 粘连符号示例 河北人学l ：学硕十学位论文 第4 章数学公式符号的识别 通过切分算法得到单个符号的图像后，需要进行符号识别特征的选择和抽取，设计 分类器，从而确定图像所对应符号的代码。数学公式符号的识别是理解和分析公式结构 的前提，直接决定了系统的识别速度和识别率，因此，公式符号的识别是公式识别系统 中的核心部分。 4 1 符号识别方法综述 对符号识别的研究已经有几十年的历史，许多现有的符号识别技术已经很成熟，符 号识别率达到很高的水平，取得了令人满意的结果。目前广泛应用的符号识别方法大体 分为统计识别方法、结构识别方法和神经网络识别方法。 4 1 1 统计识别方法 统计识别方法又称为决策论识别方法。它以数学上的决策理论为依据，并根据此理 论建立统计学识别模型。其基本模型是在对研究的图像进行大量统计分析，找出规律性 认识，抽出反映图像本质特点的特征进行识别。 这种方法一般抽取同一类字符中共有的、相对稳定的且分类性能好的统计特征组成 特征向量，利用决策函数对特征向量进行分类。常用的统计特征有网格特征、投影特征、 穿透特征、边缘特征、矩特征、笔画密度特征等。 统计识别方法是一种确定性方法，抗噪声能力较强，识别率较高，在字符识别中应 用最为广泛。但是，统计方法忽略了字符的细节和局部特征，对字形结构的描述能力不 足，使得一些统计特征差别很小，但是结构完全不同的字符容易发生混淆，区分形近字 符的能力较弱。 4 1 2 结构识别方法 结构识别方法是把待识别对象看成一个模式，该模式可以分化为若干较简单的子模 式的组合，而子模式又分为若干基元，通过对基元的识别进而识别子模式，最终达到对 1 8 第4 章数学公式符号的识别 该模式的识别。这种方法首先需要提取字符的结构特征，常用的结构特征有特征点、笔 画特征、部件特征、闭包特征等。将提取的特征作为字符的子模式、部件、基元，将所 有基元按照某种次序排列起来组成字符的特征。利用形式语言和自动机原理，采取词法 分析、树匹配和知识推理的方法分析字符的结构。 结构识别方法描述字符结构的能力很强，便于区分字形相近的字符。但是图像的微 小变化都会导致特征取值的变化，使得该方法对字符的局部变化十分敏感。 4 1 3 人工神经网络方法 人工神经网络是指利用工程技术手段模拟人脑神经网络的结构和功能，使机器具有 人脑那样的感知、学习和推理能力。神经网络就是一组相互连接的神经元，神经元之问 的每个连接都关联一个权重，网络通过调整权重实现输入样本与其相应正确类别的对 应。利用神经网络进行模式识别时，不需要对模式分布进行统计上的先验假设。常用的 神经网络识别方法有b p 神经网络方法和自组织特征映射神经网络方法。 神经网络识别方法自适应性高，具有很强的自学习能力、自组织能力，并且抗噪声 能力极强，容错性高，使其对符号识别问题显示出极大的优越性。但神经网络识别方法 在学习时需要大量的样本，耗费大量的时间，与统计识别方法和结构识别方法相比，运 算量很大。 4 2 基于游程特征的公式符号识别方法 数学公式符号集合包含大量的相似符号( 如符号“1 ”与符号“l ，符号“【”与 符号“】”等) ，并且符号的笔画少、结构简单，包含的符号特征少，不易区分，增大了 公式符号识别的难度。 本文在游程特征的基础上抽取符号的一些统计识别特征进行识别。采用基于游程特 征的符号识别方法，是为了更好的适应数学公式符号的特点，简化算法复杂度，提高符 号识别速度，从而达到较高的识别率。首先在抽取符号的游程特征基础上，选择宽高比 及孔洞特征对公式符号粗分类，之后提取符号的方向线素特征确定符号的编码，最后引 入识别后处理，利用语义规则提高符号识别率。符号识别流程图如图4 1 所示。 河北火学一1 ：学硕十学位论文 4 2 1 符号识别预处理 图4 1 公式符号识别流程图 由于文献的印刷质量或者扫描输入质量的原因，待识别的公式图像中不可避免的存 在各种噪声。为了避免其对符号特征提取的影响，在符号识别预处理阶段对图像进行平 滑处理，从而减少各种干扰因素，以增强有用信息。另外，切分得到的公式符号大小不 一，为了方便将提取的符号特征向量与字典中的标准向量进行比较，对符号进行归一化 操作。下面分别介绍平滑和归一化处理。 ( 1 ) 符号图像平滑处理 图像平滑处理的方法主要有八近旁内插法和掩膜处理法。其中，八近旁内插法是通 过判断当前像素的八近旁像素的平均值来决定该点是否为噪声，掩膜处理法是设计刀木，2 掩膜模板对图像进行平滑。 对于像素，将与其直接相邻或在对角线方向上相邻的八个像素_ ，x ：j 。定义为 它的八邻域像素，如图4 2 所示。 f 医。阿 豆 1 垒兰苎 幽4 - 2 像素矗的八邻域像幕分布示意凹 这早利用掩膜处理法，设计了一组3 * 3 的掩膜模板，如图4 3 所示 喇匝阻匝 停臣臣仟 代表。像素代表l 像紊代表可。可i 像素 强年3 掩膜模板示意圈 由以上掩膜模板可以得到该组模板下的平滑算法为 2 。兰n 【堕压n 堡n 三n 三) 堕n i n i ) ) ) v ( 畸“耳 ( o l “t “毛) v ( “鼍a k ) ) h = 1 时 1 当i n 【( x n ( v x o ) v ( x ，n 耳a ( x v ) ) 】= l 时 ( 4 1 ) ( 2 ) 符号图像归一化 图像归一化可以分为大小归一化、位置归化和方向归化。一般统计识别方法都 需要做大小归一化处理，将符号图像处理成与字典中的图像具有相同尺寸的图像。这里 对公式符号进行大小归一化处理，将不同尺寸的符号图像规范化为相同尺寸的符号图 像。利用如公式4 - 2 所示的变换矩阵将符号缩放到3 2 * 3 2 像素的符号。 阡腓荆 ，( 4 - 2 ) 将变换矩阵展开可得： x 2 0 嘎。 ( 4 3 ) i 乃2 ，y 。y o 六和工记为图像在x 轴和y 轴方向上的缩放比率，点( x 。，y 。) 对应原图像中的某个 点，它在新图像中对应的点为( 五，m ) 。 由于系统中将公式符号归一化到3 2 * 3 2 像素的符号，所以缩放比率可以通过公式 4 4 得到。 f 仁x = 3 2 w 3 2 h “- 4 ) i 厶= 一 其中，w ，h 分别为原公式符号的宽度和高度。 4 2 2 分类特征抽取 这里抽取符号的宽高比特征和孔洞特征，把符号集合分成六类。 设符号图像大小为( t t ) ( 以- - l ) ，其中，t 和t 为图像的外接矩形在x 轴方向上 的起点和终点，正和以为图像的外接矩形在y 轴方向上的起点和终点。 尺为符号的宽高比，如公式4 5 所示： r = ( i e - - i , ) ( l 一工) ( 4 5 ) 符号图像的孔洞是指由符号图像中封闭的笔画形成的封闭空白区域。孔洞特征的稳 定性高，分类能力强，对符号的字体和字形变换不敏感，也不受符号笔画粗细的影响。 因此，通过判断符号图像的孔洞个数和位置，可以有效的将公式符号集合中的符号进行 分类。 这里利用下面的算法在符号图像上提取孔洞特征。 ( 1 ) 按照从上到下、从左到右的顺序扫描待识别的符号图像，得到当前行中笔 第4 章数学公式符号的识别 面的起始位置： ( 2 ) 判断下行是否有两个笔画与当前笔画相接。如果存在，继续步骤( 3 ) 向 下寻找，否则该笔画不存在孔洞，继续步骤( 4 ) 判断下一个笔画； ( 3 ) 判断下一行是否存在一个笔画与当前行的两个笔画相接。如果存在，表明 找到一个孔洞，否则表明此笔画不含孔洞； ( 4 ) 结束当前笔画寻找孔洞步骤，回到步骤( 1 ) 判断下一个笔画，直到所有笔 画判断完。 这里用日代表符号孔洞个数，例如： “l ”，“5 ”，“t ”等的h = 0 ，符号“6 ”， “9 ”，“a ”等的h = 1 ，符号“8 ”，“b ”，“ 等的h = 2 。 4 。2 3 识别特征抽取 我们采用基于游程特征的识别方法对公式符号进行细识别，该方法在游程特征的基 础上，抽取公式符号的轮廓，提取公式符号的方向线素特征【3 4 】，将形成的特征向量与标 准字典中的特征向量比较，从而确定符号的编码。 ( 1 ) 抽取符号的游程特征 游程特征的原理是用一个符号值或者串代替具有相同值的连续符号。对于二值图像 来说，可以将点阵图像中的0 或1 代码转换成游程表示形式，例如0 0 0 1 1 1 1 1 0 0 对应的 游程特征为( 0 ，3 ) ，( 1 ，5 ) ，( 0 ，2 ) 。游程特征的定义如公式4 - 6 所示： 火三j ，= 量乡主孚萋 。歹 疗 c 4 6 ， 其中只为图像的第f 行、第列对应的像素值，k 为之后连续相同像素值的个数。 在公式符号的点阵图像上抽取游程特征，突出工图像的游程变换，不仅记录了游程 的长度，还标记了游程的起始位置信息。与在点阵图像上操作相比，在游程特征上对符 号图像进行特征抽取更加简便快速，有效减少了处理的数据量，大大提高了分析和处理 速度。 ( 2 ) 提取符号的轮廓 由于公式符号的笔画粗细随字体的变化不同，对所提的特征影响较大，为此在提取 河北火学t 学硕十学位论文 特征之前先提取符号的轮廓。当然，也可以对符号做细化处理，在符号的骨架上提取识 别特征，但是符号的骨架对噪声的影响很敏感，可能造成符号骨架畸变，给识别处理带 来麻烦。而符号的轮廓要比骨架稳定，描述符号外形的能力强，不易受噪声的影响。 对于二值图像来说，要提取图像轮廓需要扫描整个符号点阵，对每个黑像素点进行 判断，看其是否为轮廓点。这里，我们利用上面提取的符号的水平和垂直游程特征，判 断游程特征的起点和终点是否为轮廓点，即可提取符号的轮廓。两者相比，利用游程特 征的方法算法更简单，速度更快。 具体方法是： 在符号的水平游程特征上，得到游程的起点和终点。根据图像轮廓的定义，这 些起点和终点肯定是图像轮廓上的点，将其加入符号轮廓中； 同理，在符号的垂直游程特征上提取游程