（光学工程专业论文）光学公式识别技术研究.pdf

摘要摘要光学公式识别技术作为将印刷体数学公式自动输入计算机的有效手段，可以弥补现有光学字符识别系统难以识别数学公式的不足，促进科技文献的数字化。本文针对光学公式识别这一有别于普通文本的二维模式识别、分析与重构问题的关键技术展开研究，包括公式字符与符号的切分与识别、公式结构分析与理解和公式重构等三个方面。主要工作如下：1 面向公式识别的需要，设计了对公式图像进行噪声去除、二值化、倾斜和变形校正的预处理方案，以改善识别性能。实验表明了该方案的有效性。2 针对与普通文本有很大差别的二维公式符号的切分问题，提出基于组合策略的公式符号自组织反馈切分算法，在切分过程中，根据识别情况对部件或符号进行合并或切分操作。针对符号粘连问题，通过对纵向粘连情况的归纳，提出基于符号知识的公式符号纵向粘连切分方法，对其进行智能切分，并设计了斜向和横向粘连符号的切分算法；融入“基于整体 的切分方法，对常见粘连符号，建立整体识别字典进行识别。实验结果表明，该方法具有较高的准确性。3 在公式符号识别中，在定义符号图像跳转函数表示法的基础上，提出基于跳转函数的方向线素特征快速提取方法，避免了耗时的轮廓提取操作，并设计了层次结构的公式符号识别器，有效地提高了符号识别的准确率和效率。4 在公式结构分析中，根据公式特点，提出融入几何信息的公式符号最大匹配分词算法，提高了符号串提取的准确性；针对传统结构分析方法存在的问题，提出基于语义的主基线定位方法，根据符号语义对符号关系进行智能分析以得到正确的基准符号；提出符号功能的模糊分类方法，将模糊逻辑应用于符号功能分析中，以适应公式在利用符号空间关系表达隐性运算关系时所存在的不确定性；提出动态的符号基线归属判别方法，根据符号综合特征判断其基线归属。上述改进措施提高了结构分析的准确性和适应性。5 在公式重构中，提出智能匹配的公式重构算法，根据所处理公式的特点选择l a t e x 参数，实现了公式的准确重构。关键词光学字符识别光学公式识别公式符号切分公式符号识别公式结构分析公式重构跳转函数a b s t r a c ta sa ne f f e c t i v em e a n so fa u t o m a t i c a l l yi n p u t t i n gp r i n t e df o r m u l a si n t oc o m p u t e r s ，t h et e c h n o l o g yo fo p t i c a lf o r m u l ar e c o g n i t i o nc a nr e m e d yt h ed e f e c to fe x i s t i n go p t i c a lc h a r a c t e rr e c o g n i t i o ns y s t e m st h a tt l l e yf a i lt op r o p e r l yp r o c e s sm a t h e m a t i c a lf o r m u l a s ，a n df u r t h e l m v a n c et h ed i g i t a l i z a t i o no fs c i e n c ea n dt e c h n o l o g yd o c u m e n t s u pt od a t e ，o p t i c a lf o r m u l ar e c o g n i t i o ni ss t i l la nu n s o l v e dp r o b l e mo fc o m p l e xt w o - d i m e n s i o n a lp a t t e r nr e c o g n i t i o na n da n a l y s i s 砸sr e s e a r c hw o r kf o c u s e so ni t sk e yt e c h n i q u e s ，w h i c hi n c l u d ef o r m u l as 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 o r m u l as t r u c t u r ea n a l y s i sa n df o r m u l ar e c o n s t r u c t i o n 1 1 圮m a i nc o n t r i b u t i o n sc a nb es u m m a r i z e da sf o l l o w s ：1 t om e e tt h es p e c i a ln e e do ff o r m u l ar e c o g n i t i o n ，af o r m u l ai m a g ep r e - p r o c e s s i n gs o l u t i o ni n c l u d i n gi m a g ed e n o i s i n g ，b i n a r i z a t i o n ，s k e wa n dd i s t o r t i o nc o r r e c t i o ni sd e s i g n e da n di m p l e m e n t e dt oi m p r o v et h ea c c u r a c yo fr e c o g n i t i o n 田1 ee x p e r i m e n t a lr e s u l t ss h o wt h ee f f e c t i v e n e s so fi t 2 as e l f - o r g a n i z i n gs e g m e n t a t i o na l g o r i t h mw i t hf e e d b a c km e c h a n i s mb a s e do nt h eh y b r i ds t r a t e g i e si sp r o p o s e dt os e g m e n tf o r m u l as y m b o l sa r r a n g e di nt w od i m e n s i o n s i tc a l lm e r g eo rs e p a r a t ec o m p o n e n t sa n ds y m b o l sa c c o r d i n gt ot h er e c o g n i z i n gr e s u l t t os e g m e n tt o u c h i n gs y m b o l s ，as e g m e n t a t i o nm e t h o do fs y m b o lt o u c h i n gi nv e r t i c a li sp u tf o r w a r dw h i c hs e p a r a t e st h es y m b o l si n t e l l i g e n t l yo nt h eb a s i so ft h ei n d u c t i o no ft h er e g u l a r i t ) ，o ft o u c h i n gs y m b o l s a n da na l g o r i t h mo fs e g m e n t i n gd i a g o n a lo rh o r i z o n t a lt o u c h i n gs y m b o l si sd e s i g n e d m e a n w h i l e ，ag l o b a lb a s e da p p r o a c hi se m p l o y e dt op r o c e s sm u l t i p l et o u c h i n gs y m b o l sw h i c ha p p e a ri nf o r m u l a sf r e q u e n t l ya saw h o l eo b j e c tw i mac o r r e s p o n d i n gf e a t u r ed i c t i o n a r y 砀ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h em e t h o dh a sah i g ha c c u r a c y 3 aj u m p i n gf u n c t i o ni sd e f i n e dt oe x p r e s sf o r m u l ai m a g e sa n dar a p i de x t r a c t i o nm e t h o do fd i r e c t i o n a ld e m e n tf e a t u r eb a s e do nt h ej u m p i n gf u n c t i o ni sp r o p o s e di ns y m b o lr e c o g n i t i o n ，w h i c hc o u l da v o i dt h et i m ec o n s u m i n go p e r a t i o no fc o n t o u re x t r a c t i o n b e s i d e s ,ar c c o g n i z e ro ff o r m u l as y m b o l si sd e s i g n e db a s e do nh i e r a r c h i c a ls t r u c t u r e t h u s ，b o t ha c c u r a c ya n de f f i c i e n c yo fs y m b o lr e c o g n i t i o nh a v eb e e ni m p r o v e d a b s t r a c t4 i nf o r m u l as t r u c t u r a la n a l y s i s ，am a x i m u mm a t c h i n gw o r ds e g m e n t a t i o na l g o r i t h mi n c o r p o r a t i n gg e o m e t r i c a li n f o r m a t i o no ff o r m u l as y m b o l si sd e v e l o p e dt oi d e n t i f ys y m b o ls t r i n g sb a s e do nt h ef o r m u l ac h a r a c t e r i s t i c s t ot a c k l et h ep r o b l e m so ft r a d i t i o n a ls t r u c t u r a la n a l y s i sm e t h o d s ，w ep r o p o s eas e m a n t i cm e t h o do fl o c a t i n gd o m i n a n tb a s e l i n ew h i c hc o u l do b t a i nt h es t a r ts y m b o la c c u r a t e l yt h r o u g hi n t e l l i g e n ta n a l y s i so ft h es e m a n t i cr e l a t i o n s h i p so fs y m b o l s i no r d e rt o f i n d t h ei m p l i c i tc a l c u l a t i o nr e l a t i o n s h i p so fs y m b o l se x p r e s s e db ys p a t i a lf e a t u r e s ，w eg i v eaf u z z yc l a s s i f i c a t i o nm e t h o do fs y m b o lf u n c t i o nw h i c hi n t r o d u c e sf u z z yl o g i ct oi d e n t i f yt h es y m b o lf u n c t i o n t oi m p r o v et h ea n a l y s i sa c c u r a c y , w ea l s od e s i g nad y n a m i ca p p r o a c ht oa s s i g ns y m b o l st oc o r r e s p o n d i n gb a s e l i n e si nt e r m so ft h ei n t e g r a t e df e a t u r e so fs y m b o l s t h e s em e t h o d sh a v ei m p r o v e db o t ht h ea c c u r a c ya n dr o b u s t n e s so ff o r m u l as t r u c t u r a la n a l y s i s 5 i nt h er e c o n s t r u c t i o no ff o r m u l a s ，a ni n t e l l i g e n tm a t c h i n ga l g o r i t h mi sp r e s e n t e dt od e t e r m i n et h el a t e xp a r a m e t e r st h r o u g ht h el a y o u to ff o r m u l a s ，a n df i n a l l yt or e a l i z et h ee x a c tr e c o n s t r u c t i o no ff o r m u l a s k e y w o r d s ：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 p t i c a lf o r m u l ar e c o g n i t i o n ；f o r m u l as y m b o ls e g m e n t a t i o n ；f o r m u l as y m b o lr e c o g n i t i o n ；f o r m u l as t r u c t u r a la n a l y s i s ；f o r m u l ar e c o n s t r u c t i o n ；j u m p i n gf u n c t i o ni i i博、硕学位论文保密声明本论文因涉及国家基金笪曼【搓糊逻塑的麴堂公式结捡公扭皇堡鲤巫究滏项目的研究，有些内容为项目的保密部分。该项目正在进行，尚未结项。因此本论文全文部分需保密。保密期限：口6 个月口1 2 个月囹2 4 个月特此声明!申请人2 切糊，导师签名：科技处意见：学位委员会申请日期：如7 年版月e l河北大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了致谢。作者签名：1 j i 7 謦酋学位论文使用授权声明本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。本学位论文属于l 、保密西在2 2 2 翌年监月上日解密后适用本授权声明。2 、不保密口。( 请在以上相应方格内打“”)作者签名：幽重量!日期：呈竺全z 年旦月上日导师签名：哈y | | j 幻第1 章引言第1 章引言1 1 研究背景及意义在当今的信息化社会中，信息技术正在深刻影响着人们的生活。作为将光学与信息科学相结合的- f - j 学科，光信息科学与技术在信息的产生、采集、存储、传输、显示以及处理等各个环节中，起着重要的作用【。而大量的光学信息是以图像形式存在的，因此，研究用机器自动抽取图像信息的光学图像识别技术，成为光信息处理技术的重要组成部分1 1 1 。作为光学图像识别技术的一个重要研究领域，光学字符识别( 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 ) 技术得到了长足的发展和广泛的应用。早在1 9 2 9 年，t a u s c h e k l 2 就利用十块光学模板，通过测量总光量来识别用单副铅字印刷的数字，实现了第一台光学字符识别器，并申请了专利。1 9 3 3 年，h a n d e l 3 1 采用此类方法，为每个数字模板连接输出通道，在匹配过程中根据通道电压的不同，实现了数字识别。此后，人们对光学图像识别技术的探索就一直没有停止过。光学图像识别的基础是光学相关器，它能够对两个图形是否完全一致作出判别。但此类纯光学方法在进行图像处理时，只能对由强度或振幅分布表示的图像进行位移不变量的线性运算，运算误差不可避免，且装置的通用性小，使其应用受到了限制【1 4 ，5 1 。计算机于1 9 4 6 年的问世，使o c r 技术开始走向实际应用。计算机具有计算种类多，精度高的特点；可以克服纯光学方法的不足，胜任几乎所有类型的运算问题，很少带来运算误差；除了在数据采集与输出环节需要一定的硬件设备外，所要解决的问题更多地属于模型与算法的问题。因此，将光学方法与计算机方法相互结合，被认为是光学信息处理最有效的方法之一，计算机图像处理与光学信息处理也被认为是同一领域的技术问题【1 1 。传统的文字信息的手工录入方式需要由录入人员先逐一识别出文献上的文字，再根据某种编码输入方法，利用键盘将文字所对应的代码输入计算机，最终将所输入的全部文字按照某种标准的文件格式( 如t x t 、d o c 等) 存储，速度低、劳动强度大、准确性难以保证，使人们对大规模文献的数字化工作望而生畏，严重制约了文献资源建设的河北大学工学博士学位论文速度和规模，并进一步影响到以此为基础的文献信息传输、处理和应用等一系列工作的正常进行。而o c r 技术借助光学输入设备将印刷文献的数字图像输入计算机，由o c r程序对其进行自动的分析与识别，形成文字的代码，并以标准格式的文件存储。与手工录入时由入脑辨识文字相比，由于o c r 技术是利用可以高速、不间断工作的电脑来识别文字，其输入效率得到了大幅度的提升。在此过程中，基本无需人的参与，从而将人们从繁重的手工录入劳动中解脱出来。虽然和手工输入一样，存在误识问题，但录入人员的工作量已经明显减少。自上世纪六十年代英文、数字o c r 系统问世到上世纪八十年代汉字o c r 技术得到应用 6 1 ，在o c r 技术的帮助下，很多大型文献资源库建设得以顺利完成并得到了广泛应用。另外，传统手工输入方式只能输入文献版面上的文字信息，而不能处理版式信息( 如字体、字号、行字间距等) 和表格信息；o c r 技术却可以自动分析提取这些信息，并将这些信息与文字信息相结合，重构为反映文献版面原貌的标准格式文件。这无疑使得o c r 技术具有了更多的功能优势。随着我国信息化建设的不断发展与深化，信息资源建设越来越受到人们的重视。印刷文献是文字信息存在的主要方式，将其高效地输入计算机，是信息化建设首先要解决的问题。因此，进入二十一世纪以来，o c r 技术受到了前所未有的关注。但是，随着o c r 技术的普及和推广，其局限性也逐步显现出来。其中最突出的问题，是它难以处理文献、特别是科技文献中的印刷体数学公式。有别于以行为单位、一维分布的普通文字，公式符号频繁通过二维分布来表达运算信息，而且具有很多普通文本所不具备的特性，使得现有的o c r 软件还难以对其进行分析与识别，得到的往往是一些一维排列的乱码，不仅没有体现原始公式的内容和结构，更无从表达原始公式的运算意义。如图1 1 ( b ) 为图1 1 ( a ) 所示图像被o c r 软件识别的结果。正态分布的一维随机变量x 的概率密度函数p ( x 而1e x p 一芦式中，卢为随机变量x 的效学期望口2 是x 的方差p = e 【x 】= lx p ( x ) d z( a ) 原始图像第l 章引言i i 鬻纛鬻：霉。- e 【x l ，1r p ( i ) d z( b 】识别结果图1io c r 软件对公式图像的识别结果公式以形式化的方式表达信息，效率高，准确性好，被科技领域所普遍采用，是海量的科技文献中一项必不可少、种类繁多、数量巨大的成分。现有的o c r 技术由于难以处理公式，在识别古公式的印刷版面时会给使用者带来很大的麻烦；而公式的手工输入要比普通文字困难很多。因此研究能够自动输入印刷体数学公式的光学公式识别( o p t i c a lf o r m u l a r e c o g n i t i o n , 简称o f r ) 技术的理论和方法，拓展o c r 技术的功能，对于我国的信息资源建设，具有十分重要的理论和应用价值。1 2 国内外研究现状及分析1 9 6 8 年，b e r k e l e y 大学的a n d 啦o n 【1 首先对手写印刷公式的识别进行了研究。1 9 7 1年，m a r t i n i q 也对数学表达式的自动输入问题进行了探讨。时至今日，在所经历的近四十年的发展历程中，公式识别技术取得了一定的进展，发表了一批公式识别技术的研究论文。但由于公式自身的特点所导致的公式识别的复杂性，还存在许多有待解决的理论和技术问题1 1 0 l 。在公式识别技术的发展历程中，一方面。它受到模式识别技术和文字识剐技术旋展水平的制约，总体滞后于文字识别技术；另一方面，受到公式有别于一般文本的诸多特点的影响，公式识别技术又不同于文字识别技术，存在很多特有的难题。由此造成公式识别技术的发展在时问和各个技术环节之间的不平衡，给公式识别技术的实用化带来了很大困难，也使公式识别的起步阶段自a n d e r s o n 提出公式识别问题一直延续到二十世纪八十年代末足足经历了二十余年，其问只有十余篇相关论文发表。如c h a n g 等人【i ”提出了一种应用运算符优先级和作用域对公式进行分析的方法，虽然考虑到效率，但该河北大学工学博士学位论文方法只适用于以操作符为基础的结构模式。a n d e r s o n 1 2 】提出了一种基于语法的公式识别方法，采用自顶向下的句法分析方案将二维的字符分解为子问题，所定义的语法规则包含所有必要的分割指令。b e l a i d 和h a t o n l l 3 】将数学公式看作二维图形模式的典型实例，并将语法分析的方法应用于公式分析中。所提出的方法可用来识别书写在图形输入板上的二维数学公式。首先通过定位公式中的主要操作符开始进行分析，然后查找开始符号将公式分解为子表达式，在此过程中得到公式结构。公式符号识别采用了结构特征。w a n g 和f a u r e 1 4 , 1 s l 针对手写公式，设计了一个分割数学表达式的模块系统，建立属性关系树表达公式的层次结构。包括一系列按照图语法定义的、完成特定任务的数据驱动和知识驱动的专用模块，按照符号语义和公式语法分析表达式结构，其形式有助于对尚未识别的部件及其联系的可视化理解，但限于分析线性和上下标结构。c h o u 1 6 】以类似于采用隐马尔可夫模型进行语音识别的方式，利用随机上下文无关文法对数学公式进行分析。上世纪九十年代以后，随着o c r 技术的快速发展，公式识别技术也进入了一个稳步发展的时期，相关的研究受到重视，发表的论文数量也显著增加。f a t e m a n 等人【1 7 之川对公式定位、识别和分析等环节进行了研究，发表了四篇论文。所提出的方法可以将输入的公式图像表达为l i s p 语言。通过查找典型公式符号并依据一定的规则进行扩展后定位公式；通过建立2 7 维的特征向量和h a u s d o r f f 距离识别公式符号；在结构分析中，采用了分解方法。l e e 等人【2 1 翻】在1 9 9 3 至1 9 9 7 年，发表了四篇公式识别论文。所提出的方法包括版面分析，字符切分，特征抽取，字符识别，表达式分析，纠错和抽取。在字符识别中，采用了方向特征构成特征向量构造识别器；结构分析结果表示为公式关系树。该系统的识别率为9 6 ，系统的纠错功能可以使识别率提高2 5 。o k a m o t o 等人 2 5 - 2 8 】采用传统的模板匹配方法进行符号识别。结构分析由两个基本策略组成：一是特殊结构分析，采用自底向上的方法检测局部结构；二是基本结构分析，通过自顶向下的方法检测全局结构。分析结果表达为树结构。该系统在实验中采用4 0 0 d p i 的分辨率扫描公式，取得了较高的分析准确率，分析错误主要出现在角标的情况，如将指数符号错误地判断为右部符号。l a v i r o t t e 等人【2 9 3 0 】的方法分为符号识别、几何分析和句法分析三个阶段，并假定第第1 章引言一个阶段已经顺利完成，着重讨论了后两个阶段。定义了一个上下文相关的图文法对公式进行分析。通过在规则中添加上下文来消除其模糊性，进行有效的结构分析。i n o u e 等人【3 1 1 提出了处理含数学公式的日文科技文献的方法。专门设计了公式符号识别程序；在将含公式的文本行与纯文本行区分开以后，采用基线法，利用循环程序对公式区域进行自顶向下的分析，得到公式结构，并生成相应的t e x 源文件。k a c e m 等人f 3 2 , 3 3 l 专门研究公式定位问题，其特点是不依赖于识别结果。整个方案基于全局分割和局部分割。全局分割通过学习阶段利用模糊逻辑建立的模型来实现初始标记，从文本中分离孤立公式；局部分割利用前后关系扩展邻接符号，通过一些规则处理角标等关系，将公式从文本中分离出来。初始标记准确率为9 5 3 ，抽取准确率为9 3 。另外，在此期间发表的联机手写体数学公式识别的论文，虽然与印刷体数学公式识别的处理对象不同，但其中所提出的方法，可供印刷公式识别参考。k o s m a l a 等人【3 5 ，3 6 】提出了基于h m m s 的联机手写数学公式的识别方法。该方法要求书写者遵从一定的书写顺序，如一般的表达式应从左至右、从上至下书写；分式应先写分子、再写分数线、最后写分母；带括号的表达式应先写括号中的内容，最后再写括号等。w i n k l e r 等人【3 7 - 4 0 1 为了解决公式的手写方式所带来的问题，在公式符号识别和结构分析中应用了软决策方法。分析过程中若两个符号的关系得不到确定，则会产生多种选择。最后通过语法检查来剔除不合法的情况。进入二十一世纪，o c r 技术已逐渐走向成熟，随着社会对科技文献资源需求的日益高涨，解决公式识别问题已迫在眉睫，相关研究人员的注意力也更加集中在公式识别研究上。c h a u d h u r i 和g a r a i n 等人1 4 1 。4 5 1 对公式识别的各个环节进行了研究。采用n g r a m 语法模型进行符号扩展以定位嵌入公式，利用多个分类器进行符号识别，采用基于语法的方法对公式进行分析。s u z u k i 等人5 1 1 设计了用于日文文献的公式识别系统，能够识别印刷清晰的文献并以x m l 格式输出。c h a r t 等人【5 2 5 4 1 对联机手写公式识别进行了研究。采用句法结构方法识别手写符号，采取语法分析的形式分析公式结构。河北大学工学博士学位论文在国内，靳简明等人 5 5 - 5 8 , t 2 6 、王科俊等人【5 9 1 、陈洪波等人 6 0 i 、黄磊等人【1 2 7 1 均进行了公式识别方面的研究工作，取得了一定的成果。总之，国内外研究人员对公式识别技术的研究工作为公式识别技术的应用打下了良好的基础。对公式识别技术的进一步研究需要关注以下几个方面的内容。1 以理论研究为基础，在实际应用中进一步改善公式识别技术的性能。公式识别技术的识别过程和技术路线非常清晰，即在对二维公式符号进行切分、识别的基础上，利用符号的几何特征和识别结果，分析、理解公式的层次结构，再将其重构为某种线性的标准格式文件。其中，符号切分与识别属于光学字符识别领域的研究内容，在普通的一维文本识别中，已经得到了比较充分的研究；公式结构分析与理解属于二维模式的分析问题，已有许多针对此类问题的分析方法，如基于二维文法的分析方法。因此，公式的识别与分析已经具备了一定的理论基础。然而，由于公式排版在遵循一些基本原则的基础上，在表达运算关系，特别是一些隐性运算关系时，存在着很大的不确定性，加之纸张、印刷过程中产生的噪声和变形，给公式识别带来了很大的困难。例如，公式符号在二维空间中频繁发生粘连问题，针对一维文本的普通切分方法难以适应，导致识别率的下降。在结构分析中，很多排版系统所实现的公式不能严格地在几何上按照相应的层次关系分布，经常导致结构分析算法混淆符号间的层次关系。因此，在公式识别技术的研究中需要面向实际应用，通过实验检验算法、完善算法。2 对公式识别各个技术环节的系统性研究。公式识别技术的各个组成环节是一系列联系紧密、相互作用的有机整体。例如，切分的效果要受到识别结果的检验，而符号识别的质量是在结构分析与重构中体现出来的，结构分析与重构的正确进行也有赖于正确的识别结果。因此，针对某个环节的研究会受到一定程度的制约，需要将公式识别技术的各个环节有机地结合在一起，进行全面的研究。只有这样，才能使其充分融合，互相补充，达到一个总体上的最佳效果。3 对测试数据进行归纳和整理，丰富识别对象。数学公式无论从组成元素，到元素间所形成的关系，都非常复杂。构成公式的符号种类繁多，在表达不同领域的科学问题时，符号的用法和组合方式十分灵活，即使人脑，在分辨时也存在着一定的困难，需要一个适应的过程，这对于计算机这一学习能力尚未完善的机器，存在着很大的困难，第1 章引言如果在算法设计中不能充分考虑上述问题，就会在实际应用中产生大量的错误。此外，公式符号的层次规模没有受到限制，任何一个事先假定公式层数的结构分析算法，都是没有应用价值的，当层次较多时，在任何一层发生的错误，会直接影响以后的分析过程，在公式语法、语义方面产生很多的错误。故应在研究中充分考虑到公式的复杂性，从基础环节开始，适应复杂的公式结构。对公式样本数据库的整理、完善是一项非常重要的工作。目前，一些研究人员已经在这方面做了许多工作，并可以看到一些研究公式样本库的论文。建立用来进行测试的公共样本数据库，进行公式识别的测试活动，对于公式识别技术的研究与发展，以及研究人员及时发现、解决自己在研究工作中所存在的问题，是十分有益的。当然，在建立公式样本库时，会出现很多预想不到的问题，例如，如何使数据库中的公式样本具有代表性，如何保证公式数据库的开放性以使其能够得到不断的完善，样张的技术参数如分辨率、图像的种类( 彩色、灰度、二值等) 、图像文件的格式等，都会影响公式数据库的可操作性和权威性。此外，研究公式识别技术的评价体系也是一项非常重要的工作。有别于一般文本，对某个公式符号的识别错误常常会导致对整个公式结构的错误理解。例如，在符号识别阶段，将一个符号“ 误识成“e ”，则在公式结构分析时，无论是分析过程中对该符号作用域的分析，还是语法、语义含意的理解，都会发生改变。故符号识别率具有特别重要的意义。在结构分析中，某一个环节的结构分析错误，常常会使后面的分析过程全部处于错误的分支中，因此，结构分析的性能应该如何衡量，也是需要确定的问题。目前，一些研究人员意识到这项工作的重要性，已经做了必要的研究并发表了相关论文【5 7 1 。4 面向公式识别需求的图像预处理技术研究。公式图像在采集过程中经常会受到各种干扰，产生噪声和变形。由公式符号自身的特点以及公式的层次结构所决定，噪声和变形的存在会对公式识别与分析过程产生不良的影响，导致公式识别性能指标的降低。若要实现准确性高、适应性好的实用的公式识别系统，就需要面向公式识别技术对公式图像的要求，以已有的图像处理技术为基础，对公式图像的预处理技术展开比较充分的研究。因此，光学公式识别是一个充满困难和希望的研究课题，只有综合运用新的理论和技术，解决所存在的问题，才能尽快形成高性能的、满足用户需求的系统，加快信息资河北大学工学博士学位论文源建设的步伐。1 3 研究内容本文以印刷体数学公式作为处理对象，针对光学公式识别的关键技术展开研究工作，包括公式字符与符号的切分与识别、公式结构分析与理解、公式重构等三个方面。1 公式图像预处理技术研究。公式图像采集过程中，由于印刷文献和采集设备的原因，不可避免地包含多种噪声。这些噪声会干扰识别与分析过程，导致错误的产生。传统的去噪方法在去除噪声的同时，会对公式本身带来损伤。故需要面向公式识别的特定需求，研究和实现公式图像的识别预处理算法。本文设计了包括面向公式图像的去噪方法、公式图像的二值化方法、公式图像倾斜与变形失真的校正方法的预处理方案。实验表明本方案有效改善了识别效果。2 公式字符与符号( 以下简称公式符号) 切分方法研究。针对与一般文本切分有很大差别的二维公式符号切分问题，研究实现适应公式特点的符号切分方法与算法。提出了基于组合策略的公式符号自组织反馈切分算法，在切分过程中，根据当时的识别情况，智能地选择对当前部件或符号进行合并或切分操作，以解决公式中多部件符号或包含符号的切分问题；针对符号粘连的问题，本文通过对纵向粘连情况的归纳，提出了基于符号知识的公式符号纵向粘连切分方法，对纵向粘连进行智能切分；并设计了斜向与水平粘连的切分算法。融合“基于识别 和“基于整体”两种切分策略，对公式中常见的粘连符号，建立整体识别字典进行识别。3 公式符号识别方法研究。公式符号成分复杂且二维分布，尺寸和字体频繁变化，传统的面向普通文本的识别器难以适应。故需要研究设计公式符号的专用识别器。本文在符号识别中，定义了符号图像的跳转函数表示法，提出基于跳转函数的符号方向线素特征的快速提取方法，避免了耗时的符号轮廓提取操作，提高了公式符号特征提取的效率；并设计了层次结构的符号识别器，达到了较高的识别率。4 公式结构分析方法研究。公式具有二维层次结构，很多运算都是依靠符号空间关系隐性表达的，且具有不确定性。传统的分析方法存在适应性差的问题，需要根据公式特点，对其进行改进，研究实现高性能的结构分析算法。( 1 ) 在结构分析的初始环节，本文借鉴计算语言学中有关自然语言分词的思想，根据公式符号特点，提出融入几何信息的公式符号最大匹配分词算法，结合公式知识，第l 章引言昌一ii ii ii ii i , , 量宣置鼻鼻詈蕾e _准确地提取公式符号串，并在此过程中，对识别结果进行纠错处理，为高准确性的结构分析打下基础；( 2 ) 在结构分析起始点的选择问题中，提出基于语义的主基线定位方法，根据符号内容对其进行智能分析，得到正确的基准符号，避免结构分析起始点选择错误的发生。( 3 ) 为了提高结构分析算法的适应性，本文在结构分析过程中利用模糊数学的思想对符号的功能类型进行分析与判断，以适应公式符号在不确定位置所表达的隐性运算关系，解决符号关系的误判、漏判问题。( 4 ) 提出动态的符号基线归属判别方法，根据符号综合特征判断其基线归属，提高了分析的准确性；5 公式准确重构方法研究。设计实现能够根据识别与分析结果，建立反映原始公式情况的l a t e x 文件的方法和算法。本文在重构中提出智能匹配的公式重构算法，形成了解决重构问题的一整套方案，以改善重构效果。1 4 组织结构本文包括以下几个部分：第l 章引言。讨论光学公式识别技术的研究背景及意义，介绍该技术的国内外研究现状，给出本文的研究内容。第2 章光学公式识别技术。介绍光学公式识别技术的定义与组成，对其中有待解决的关键技术问题进行分析与归纳。第3 章公式图像的识别预处理。针对公式图像在采集过程中所产生的各种失真和变形，讨论去噪、二值化、倾斜和变形失真校正等有助于改进识别效果的公式图像预处理技术，设计面向公式识别需求的图像预处理方案。第4 章公式符号的切分与识别。分别对已有的切分和识别方法进行归纳，设计实现公式符号切分与识别的方法。第5 章公式结构分析。在对现有结构分析方法进行归纳的基础上，总结公式结构的语法、语义知识；然后，提出对传统结构分析方法进行改进的措施。第6 章公式重构。讨论利用结构分析阶段生成的公式结构树重构l a t e x 文件的方法。第7 章实验结果及分析。给出所实现的印刷公式识别系统对实际样张的实验结果，河北大学工学博士学位论文并对其进行分析。第8 章结论与展望。对本文工作进行总结，并提出对下一步研究工作的展望与设想。第2 章光学公式识别技术第2 章光学公式识别技术光学公式识别技术是光学图像识别技术的一个重要分支，属于复杂二维模式的识别与分析问题，包含很多面向一维文本的传统o c r 所难以处理的问题；加之公式中不仅使用运算符号来显性表达运算关系，还频繁利用符号空间关系来隐性表达符号之间的运算关系，因此，是光学图像识别领域，特别是文字识别研究的困难课题。光学公式识别技术作为印刷文献，特别是科技文献自动输入的重要手段，对其理论和方法的研究，可以有效地弥补传统o c r 技术在处理公式中所存在的缺陷，提高信息资源建设的效率。2 1 光学公式识别技术的定义在不同的时期，随着对公式识别技术研究的不断深化和发展，人们从一开始局限于公式符号的识别研究，逐渐发展到对公式的结构进行分析与理解，直至目前将公式定位与公式重构也纳入公式识别的研究范围，使公式识别研究与实际应用的距离正在逐渐缩短。在此过程中，专家们曾经给出了公式识别技术的多种定义，从中可以看出公式识别技术的发展历程。a n d e r s o n 7 , 1 2 1 将公式识别问题看作为典型的由公式符号组成的二维模式识别问题，公式模式利用特殊的结构来表达其含义，是句法模式识别最好的应用领域。f a t e m a n 等人【1 8 】认为，公式识别是将扫描文献分割为不同的区域，对区域内的图像进行识别，对识别结果进行分组，并将公式表达为l i s p 语言的过程。b l o s t e i n 和g r b a v e c 9 1 认为，公式识别是将二维分布的公式图像转换为计算机可处理的形式。他们将公式识别分为两个部分，符号识别和符号排列关系的分析；并进一步细分为六个步骤：前期处理( 包括去除噪声和纠斜) 、分割、符号识别、符号空间关系的鉴别、符号逻辑关系的鉴别以及重构等。其中，前三个步骤属于符号识别的范畴，后三个步骤属于符号排列关系的分析。c h a u d h u r i 和g a r a i n l 4 l 】则将公式识别定义为包含公式定位、符号识别以及符号组织等三个部分的系统，形成表达公式的含有格式信息的符号串。无论是按照功能进行定义，还是按照处理步骤进行定义，显然，上述定义的中心内容和组成部分是逐渐完善的。由此，我们可以尝试给出光学公式识别技术的如下定义：河北大学工学博士学位论文光学公式识别技术就是利用计算机对光学输入设备采集的印刷体数学公式图像进行识别、分析与理解，并依据识别与分析结果重构与原始公式一致的标准格式文件，从而实现印刷公式自动输入的方法和算法。2 2 光学公式识别技术的内容符号识别技术的理论基础是光学相关器【1 4 5 1 。对于两个实函数厂 ，力和g 似力，其相关函数【4 】定义为c ( 口，) = ，i ( x , y ) g ( x 一口，y - p ) d x d y( 2 1 )若f ( x ，力和g ，力分别为分布在两个透明片上的不透光图形，当满足口= o , p = 0 ，即两个透明片完全对齐，其上的图形取相同的坐标原点时，光束自左至右通过透明片被透镜聚焦到探测器上。显然，探测器上光强的积分c ( o ，0 ) 与两个图形的相似性具有一定程度的联系1 4 】。、缮蘑图2 1 光学图像识别器f 4 ，6 9 1图2 1 所示的相关器仅能判别两个形状、位置完全相同的图形，而图2 2 所示的非相干识别器【4 】采用了一个放置在透镜焦平面上的面光源以产生大量平行光。即使厂 ，力与g ，力的位置有一定的平移，当平行光束与厂阮力和go ，力所在的两个透明片上的透光部分一致的时候，经透镜聚焦后也会在焦平面上产生相关斑【4 】。扩展光源透镜f ( x ，y )g ( x ，y )透镜输出图2 2 非相干光学相关器【4 i1 2 -第2 章光学公式识别技术文字图像的光学识别器与上述装置有所不同，它采用光学模板匹配的方法实现图像识别。待识别图像为正字像方式，而字符模板为负模板方式，光线依次经过正字像、负模板，经透镜聚焦于光电器件，转换为电流输出。当正字像与负模板完全一致时，透光量为零；当正字像与负模板存在不一致时，就会有光线透过，在输出端产生电流 7 0 , 7 。因此，通过更换负模板检测输出电流，可以实现对图像的识别，如图2 3 f 7 0 , 7 1 1 所示。正字像负模板透镜光电器件放大器( 、】蘑蘼yv图2 3 光学模板匹配【7 0 7 1 】上述简单的模板匹配方法可能会产生一些错误。当负模板的像素集合是多于一个的正字像像素集合的真子集时，这些正字像就会被混淆。如英文字母“e 与“f 、“q 糟与“o 等【7 l 】。此时，h 锄姗【7 1 , 7 2 所提出的方法，如图2 4 7 1 , 7 2 1 所示，可以解决这一问题。正负字像负正模板图2 4 改进的光学模板匹配1 7 1 , 7 2 以此为基础，可以实现电子模板匹配的图像识别器，如图2 5 1 7 0 7 1 1 所示，对应于字母“e 的像素点阵，建立由光电管组成的模板，每个光电管对应一个像素，前景像素和背景像素分别连接正输出通道( 输出电压与光强成正比) 和负输出通道( 输出电压与光强成反比) ，则电流表的读数反映了识别对象与模板间的不一致性【7 0 7 1 】。这种识别机制很容易在计算机中得到实现。预先在计算机中保存标准字模的像素点阵，识别时，将待识别的图像像素与字模点阵进行匹配( 异或运算) ，根据匹配结果，判断图像与字模的相似性。1 3 河北大学工学博士学位论文图2 5 电子模板匹配【7 0 7 1 1基于上述光学图像识别的基本原理，一个光学公式识别系统的原理框图如图2 5所示。计算机r 主i 五i 三磊