（计算数学专业论文）中文科技文档中数学公式的抽取.pdf

大连理工大学硕士学位论文 摘要 随着计算机和互联网的发展，越来越多的资料被以文档图像的形式存储到计算机 上。通过网络进行信息的存储、查找和传播也越来越成为当前信息流通的主要渠道。 如何快速、高效地将这些文档图像转化为可编辑的格式成为急需解决的问题，文档图 像分析技术作为一个新的研究领域应运而生。 光学字符识别( o c r ) 是文档图像分析的核心技术。现有的o c r 系统对打印字 符已经能做到很高的识别率。而数学公式由于其存在二维结构，单纯通过扩充识别系 统字库无法完全记录公式图像所含全部信息。如何将打印科技文档中的公式进行定 位、识别和重组，依然是一个正在研究中的课题。虽然已经提出了多种算法，但这些 算法大部分是针对英文环境下的文档。由于中英文在字库技术，字符连通体构成上的 诸多不同，简单地将英文环境下算法移植到中文环境下会产生大量错误，且没有利用 中文文档的特点，是不可取的。 本文首先在绪论中介绍了文档图像分析技术，以及模式识别和神经网络等相关领 域的背景知识。在定位数学公式啪寸候，本文给出的新算法需要对数学符号进行识 别。第二章主要介绍了利用z e m i k e 距提取字符的特征，由自组织特征映射( s o f m ) 神 经网络和b p 神经网络组成多分类器进行符号识别的技术。 第三章首先回顾了当前一些应用于英文环境中的公式定位算法，提出了这些算法 在应用于中文科技文当时会出现的问题，讨论了标记连通体这一当前文档分析技术中 非常依赖的技术。并对中文字符的特点，中文文档排版的特点，人类阅读方式，及科 技文档中普遍存在的公式分布局部性进行了讨论。 在此基础上，本文提出了一种新的算法，该算法采用输入框组并行的读入目标， 并判定其是否是规则汉字，从而规避了标记连通体步骤。并且利用了公式分布的局部 性，对不同密度采用速度不同的算法，从而提高了整体公式定位速度。对于算法中遇 到的各种具体问题，包括输入框标准的确定，汉字的确认，排版微调造成的所占空间 的小差异等等，都给出了具体的解决方法。 在本文的最后部分，分析了系统中仍然存在的问题，并讨论了新系统未来的扩展 方向。 关键词：文档图像分析；公式抽取；中文文档环境；连通体标记：公式分布局部性 大连理工大学硕士学位论文 e x t r a c t i o no fm a t h e m a t i c sf o r m u l a si nc h i n e s es c i e n t i f i cd o c u m e n t a b s t r a c t w l t l lt h ed e v e l o p m e n to fc o m p u t e ra n di n t e r a c t m o r ea n dm o r ed a t ah a v eb e e ns t o r e d i n t oc o m p u t e ri nt h ef o r mo fd o c u m e n ti m a g e s a n di n t e r a c th a sb e c o m et h em a j o rm e d i af o r s t o r a g e ，s e a r c h i n ga n ds p r e a d i n go fi n f o r m a t i o n h o wt oc o n v e r s et h o s ed o c u m e n ti m a g e si n t o e d i t a b l ef o r mi naf a s ta n de f f i c i e n tw a yi sap r o b l e mt ob er e s o l v e du r g e n t l y , i nw h i c hd o c u m e n t i m a g ea n a l y s i s ( d i a ) a r i s e sa san e wa c a d e m i cr e s e a r c hf i e l d 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 ) i st h ec o r et e c h n i q u eo fd i a t h ee x i s t e do c rs y s t e m sh a v eav e r yh i g hr e c o g n i t i o nr a t i o b u tb e c a u s eo ft h ep l a n a rs t r u c t u r eo fm a t h e m a t i c s f o r m u l a s ，r e c o g n i z i n gb ym e r e l ye n l a r g i n gt h es y m b o ll i b r a r yw i l ln o tr e c o r dt h ei m a g ei r t f o r - m a r i o nc o m p l e t e l y h o wt oa b s t r a c t ，r e c o g n i z ea n dr e c o n s t r u c tm a t h e m a t i c sf o r m u l a si np r i n t e ds c i e n t i f i cd o c - u m e n t si saq u e s t i o ni nd i s c u s s i o n w h i l em a n ya l g o r i t h m sh a v e b e e nd e v e l o p e d ，m o s to ft h e m c a no n l yb eu s e di na ne n g l i s hc o n t e x t d u et ot h ed i f f e r e n tc o m p o n e n t ss t r u c t u r eo fe n g l i s h l e t t e r sa n dc h i n e s ec h a r a c t e r s ，d i r e c t l yt r a n s f e r r i n gt h ea l g o r i t h m si n t oc h i n e s ec o n t e x tw i l l g e n e r a t en u m e r o u se r r o r s ，a n da l s oi saw a s t e o ft r a i t sc h i n e s ed o c u m e n t s c h a p t e r1r e v i e w st h eh i s t o r ya n dr e l a t e dt e c h n o l o g yi nd o c u m e n ti m a g ea n a l y s i s ，p a t t e r n r e c o g n i t i o n ，a n da r t i f i c i a ln e u r a ln e t w o r k s s i n c et h er e c o g n i t i o no fm a t h e m a t i c ss y m b o l si sn e c e s s a r yf o ro u rf o r m u l ae x t r a c t i o na l g o f i t h m ，i nc h a p t e r2t h ef e a t u r e so fc h a r a c t e r sa r ee x t r a c t e db yt h ez e r n i k em o m e n t s ，a n da m u l t i c l a s s i f i e rc o m p o s e do fs o f ma n db pn e u r a ln e t w o r k si st h e na d o p t e df o rt h es y m b o l s r e c o g n i t i o n c h a p t e r3p r e s e n t st h ep r o b l e m so c c u r r e dw h e no n et r i e st oe x t r a c tf o r m u l a sf r o mc h i n e s e s c i e n t i f i cd o c u m e n t sb yr e v i e w i n gs o m ee x i s t e df o r m u l a se x t r a c t i o na l g o r i t h m so r i e n t e di ne n g l i s hc o n t e x t d i s c u s s e da r ec o m p o n e n t sl a b e l i n g ，t r a i t so fc h i n e s ed o c u m e n tt y p e s e t ，h u m a n r e a d i n gh a b i t ，a n dt h el o c a l i t yo ft h ed i s t r i b u t i o no fm a t h e m a t i c sf o r m u l a s t h r o u g ht h ea b o v ed i s c u s s i o n s ，an e wa l g o r i t h mi sp r o p o s e d ，i nw h i c hag r o u po fs t a n d a r d i n p u tp a n e sa r eu s e dt oj u d g ei ft h ei n p u ti m a g ei sac h i n e s ec h a r a c t e nt h e r e f o r ec o m p o n e n t s l a b e l i n gi ss k i p p e d u t i l i z i n gt h el o c a l i t yo ft h ed i s t r i b u t i o no fm a t h e m a t i c sf o r m u l a s ，d i f f e r e n t 桑伯男：中文科技文档中数学公式的抽取 m e t h o d sa r ea d o p t e da c c o r d i n gt od i f f e r e n td i s t r i b u t i o ni n t e n s i t yi no r d e rt og e n e r n l ya c c e l e r a t e t h es p e e do ft h ea l g o r i t h m m a n ys p e c i f i cp r o b l e m ss u c ha sd e f i n i n gt h es t a n d a r di n p u tp a n e ， c o n f i r m i n gt h ei n p u ti m a g ea sac h i n e s ec h a r a c t e r , a n dm i n e rd i f f e r e n c ec a u s e db yc h i n e s e t y p e s e ta r ec o n s i d e r e di nt h i sc h a p t e r a tt h ee n do ft h i st h e s i s ，t h er e m a i n i n gp r o b l e m si nt h es y s t e ma r ea n a l y z e d ad i s c u s s i o n o nt h ee x p a n s i b i l i t yo ft h en e wa l g o r i t h mi sa l s oi n c l u d e d k e y w o r d s ：d o c u m e n ti m a g ea n a l y s i s ；f o r m u l ae x t r a c t i o n ；c h i n e s ed o c u m e n tc o n t e x t ； c o m p o n e n tl a b e l i n g ；f o r m u l ad i s t r i b u t i o nl o c a l i t y 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学 或者其他单位的学位或证书所使用过的材料与我一同工作的同志对本研 究所做的贡献均己在论文中做了明确的说明并表示了谢意 作者签名 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使 用规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和 电子版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或 部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇 编学位论文。 作者始勃暑作者签名：望! 笪娈 导师签名：邈 7 1 盟年月盈日 大连理工大学硕士学位论文 1 1 文档图像分析 1 1 1 文档图像分析概述 1绪论 广l 1 i 。彳f 、。么、一 脚“妇e 一h a m 一“之 凶； 图1 1 信息的多种格式 f i g 1 1 v a r i o u sf o r m so fi n f o r m a t i o n 为了能够使用计算机管理、存储、传播和共享记录在纸张上的信息，必须将纸质 文档通过扫描或人工录入等手段电子化。而靠人工将大量文本重新录入计算机显然是 不现实的。目前，通过扫描仪等计算机输入设备，将文档以图像格式输入计算机系 统，是文档电子化的最简单手段。 。 与传统的纸质文档相比，电子化文档传播成本低、速度快、范围广，且更易于保 存和管理。随着计算机存储能力的不断提高以及保存、共享历史文档的需要，越来越 多的文档被扫描成图像格式存储在计算机中。如何自动提取出这些文档图像中包含的 桑伯男：中文科技文档中数学公式的抽取 信息，进而实现高效率分类、检索、重新利用这些文档图像成为了一个重要课题。为 解决这个问题，文档图像分析( d o c u m e n ti m a g ea n a l y s i s ，简称d i a ) 近年来吸引了越来 越多的注意力。 文档图像分析是关于从扫描得到，或计算机生成的数字图像中恢复符号结构的理 论和实践，是数字图像处理( d i g i t a li m a g ep r o c e s s i n g ，简称d i p ) 的一个分支，主要目 标在于将文档图像转换成便于修改、储存、恢复、重用和传播的符号格式【2 】。d i a 可以粗略的分为自顶向下( t o p - d o w n ) 和自底向上( b o t t o m - u p ) 以及二者混合型三种模 式。这几种模式间的区分并不绝对，一般来说，自顶向下分析先把文档图像分割成大 区块，然后再将大区块进一步分割成行或单词；自底向上分析的过程与之相反，先找 到文档图像中的单词j 由单词组成行，由行组成段落【3 】。需要指出的是，无论哪种模 式，都不可避免的要对文档图像进行像素级的操作。 1 。1 2 文档图像分析设计的相关技术 d i a 主要涉及到的技术有：图像预处理、粘连字符分割、连通成分标记、版面分 析与逻辑结构分析、特征提取、o c r 、文档重建等。 1 图像预处理；在文档图像分析之前，通常需要将文档图像进行一些预处理，以去 除其中的干扰和冗余的信息。适当的预处理过程能够有效的降低后继处理过程的 难度。文档图像的预处理过程一般包括：去除噪声、二值化、倾斜矫正。 2 粘连字符分割；于扫描精度、印刷质量等方面的原因，扫描得到的文档图像普遍 存在着字符间粘连的情况。事实上，由于计算机使用的字体的固有性质，即使是 计算机生成的英文文档，在不经扫描的情况下直接转换成文档图像，字符粘连的 现象也依然存在。目前，粘连印刷体字符的分割已经有了很多种方法【4 】。其中比 较常用的是最短路径法【5 】。 3 连通成分标记；连通成分标记是d i a 中最广泛使用的技术之一。连通成分标记针 对图像中的所有像素进行操作，事实上相当于对文档图像中的所有像素进行一次 粗分类。虽然非常耗时，o g d l a 的很多步骤都需要利用到连通成分标记，尤其是 本文应用的数学公式提取和识别方面。而本文的主要目的之一就是希望找到一种 规避连通成分标记的公式定位算法。 2 一 大连理工大学硕士学位论文 4 版面分析与逻辑结构分析：版面分析( l a y o u ta n a l y s i s ) 和逻辑结构分析( l o g i c a l s t r u c t u r ea n a l y s i s ) 是d i a 的核，t l , 技术，也是难点之一。当文档图像不止由纯文本 组成时，在识别其中包含的文本前，必须对文档图像的版面布局进行分析，定位 其中图片、表格、文本行、数学公式等高层对象( 与其相对，字符等基本元素称 为低层对象) 的位置，并对所得到的高层对象进行分类，以便对不同的高层对象 采取不同的策略进行处理。本文的主要工作是从中文文档中提取出其中包含的数 学公式，并加以识别，既属于版面分析与逻辑结构分析的任务。 5 光学字符识别；光学字符识别( 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 是 一个涉及到模式识别、人工智能、模糊数学、计算机科学等多学科的的综合课 题，具有大概4 0 年的发展史。为了获取文档图像中文字部分包含的信息，需要对 文档图像包含的文字进行识别，并将识别结果以能够再次编辑的格式( 例如a s c i i 码) 保存。光学字符识别可以分为印刷体识别和手写体识别两大类本文中在公 式定位和公式识别阶段都需要用到o c r 技术，在本章的后两节中还将简要介绍 相关的模式识别和人工神经网络概念。 6 文档重建：文档重建过程的目标是综合之前所有步骤的结果，由不可编辑的图像 文件最终生成可编辑的、显示效果与原稿完全相同的电子文档。为了达到这个目 标，需要将o c r 过程识别出的字符按版面分析和逻辑分析的结果重新排列、组 织。由于这个过程对于o c r 结果的正确率以及版面分析和逻辑分析的准确程度 都有极高的要求，实际工作中很难得到预期的结果。 1 2 模式识别 1 2 1 模式识别基本概念 模式识别是人类的一项基本智能，在日常生活中，人们经常在进行“模式识 别”随着2 0 世纪4 0 年代计算机的出现以及5 0 年代人工智能的兴起，人们当然也希望 能用计算机来代替或扩展人类的部分脑力劳动。作为一门研究对象描述和分类方法的 学科，( 计算机) 模式识别在2 0 世纪6 0 年代初迅速发展并成为一门新学科。 具体来说模式识别是一种从大量信息和数据出发，在专家经验和已有认识的基础 上，利用计算机和数学推理的方法对形状、模式、曲线、数字、字符格式和图形自动 3 一 桑伯男：中文科技文档中数学公式的抽取 完成识别的过程。模式识别包括相互关联的两个阶段，即学习阶段和实现阶段，前者 是对样本进行特征选择，寻找分类的规律，后者是根据分类规律对未知样本集进行分 类和识别。广义的模式识别属计算机科学中智能模拟的研究范畴，内容非常广泛，包 括声音和语言识别、文字识别、指纹识别、声纳信号和地震信号分析、照片图片分 析、化学模式识别等等。计算机模式识别实现了部分脑力劳动自动化。 模式识别研究主要集中在两方面，即研究生物体( 包括人) 是如何感知对象的， 属于认知科学的范畴，以及在给定的任务下，如何用计算机实现模式识别的理论和方 法。前者是生理学家、心理学家、生物学家和神经生理学家的研究内容，后者通过数 学家、信息学专家和计算机科学工作着近几十年来的努力，已经取得了系统的研究成 果。 模式识别已经在天气预报、卫星航空图片解释、工业产品检测、字符识别、语音 识别、指纹识别、医学图像分析等许多方面得到了成功的应用。所有这些应用都是和 问题的性质密切不可分的 其中字符识别是模式识别领域的一项传统的课题，这是因为字符识别不是一个孤 立的问题，而是模式识别领域中大多数课题都会遇到的基本问题，并且在不同的课题 中，由于具体的条件不同，解决的方法也不尽相同，因而字符识别的研究仍具有理论 和实践意义。 这篇论文中采用的是用神经网络识别数字、及公式符号，并在中文文本环境中定 位公式子图像的问题人工神经网络模式识别方法是近些年提出的新方法，为字符识别 研究提供了一种新手段，它具有一些传统技术所没有的优点：良好的容错能力、分类 能力强、并行处理能力和自学习能力。因而，采用神经网络识别方式是一种很好的选 择。 1 2 2 模式识别几种主要方法的比较 针对模式特征的不同选择及其判别决策方法的不同，可将模式识别方法大致分 为5 大类。这5 种识别方法均可实现字符识别，但它们特点不同，必须根据条件进行选 择。 1 统计模式法：它是从被研究的模式中选择能足够代表它的若干特征一个合理的 假设是同类的模式在特征空间中相距很近，而不同类的模式在特征空间则相距的 较远，这是因为相距近的模式意味着它们的各个特征相差不多，从而在同一类中 4 大连理工大学硕士学位论文 的可能性较大。如果用某种方法来分割特征空间，使得同一类模式大体上都在特 征空间的同一个区域中，则对于待分类的模式，就可以根据它的特征向量位于特 征空间中哪一个区域而判定它属于哪一类模式。统计模式识别方法的任务就是用 不同的方法划分特征空间，使得识别的目的能够达到。此方法比较成熟，能考虑 干扰、噪声等的影响，识别模式基元能力强。但对结构复杂的模式抽取特征困 难；不能反映模式的结构特征，难以描述模式的性质；难以从整体角度考虑识别 问题。 2 句法结构方法：它把模式的分层结构类比于语言中旬子的构造，这样，就可利用 形式语言学的理论来分析模式句子由单词按文法规则构成。同样，模式由一些 模式基元按一定的结构规则组合而成，分析模式如何由基元构成的规则就是结构 分析的内容。这相当于在形式语言学中对一个句子作语法分析。句法结构模式识 别就是检查代表这个模式的句子，是否符合事先规定的某一类文法规则，如果符 合，那么这个模式就属于这个文法所代表的那个模式类此方法识别方便，可从 简单的基元开始，由简至繁；除了分类的信息外，还能给出模式的结构信息，能 描述模式的性质，对图像畸变的抗干扰能力较强，但当存在干扰及噪声时，抽取 基元困难，且易失误。 3 逻辑特征法：就是其特征的选择对一类模式识别问题来说是独一无二的，即在一 类问题中只有1 个模式具有某1 种( 或某1 组合的) 逻辑特征，此方法建立了关于 知识表示及组织，目标搜索及匹配的完整体系；对需通过众多规则的推理达到识 别目标的问题，有很好的效果，但当样品有缺损，背景不清晰，规则不明确甚至 有歧义时，效果不好。 4 模糊模式方法：就是在模式识别过程中引入了模糊集的概念，由于隶属度函数作 为样品与模板相似程度的量度，故能反映整体的、主要的特性，模糊模式有相当 程度的抗干扰与畸变，从而允许样品有相当程度的干扰与畸变，但准确合理的隶 属度函数往往难以建立。目前有学者在研究，并将其引入神经网络方法形成模糊 神经网络识别系统。 5 神经网络方法：就是使用人工神经网络方法实现模式识别。可处理一些环境信息 十分复杂，背景知识不清楚，推理规则不明确的问题，允许样品有较大的缺损、 畸变，神经网络方法的缺点是其模型在不断丰富完善中，目前能识别的模式类还 5 一 桑伯男：中文科技文档中数学公式的抽取 不够多，神经网络方法允许样品有较大的缺损和畸变，其运行速度快，自适应性 能好，具有较高的分辨率。 综上所述，以上方法都各有利弊，至今还没有发展成统一的、有效的可应用于所 有的模式识别的理论。当前的一种普遍看法是不存在对所有的模式识别问题都使用的 单一模型和解决识别问题的单一技术，我们现在拥有的是一个工具袋，我们所要做的 是结合具体问题把统计的和句法( 结构) 的识别方法结合起来，把统计模式识别或句 法模式识别与人工智能中的启发式搜索结合起来，把人工神经元网络与各种以有技术 以及人工智能中的专家系统，不确定方法结合起来，深入掌握各种工具的效能和应用 的可能性，互相取长补短，开创模式识别应用的新局面。 1 2 3 神经网络方法解决模式识别问题的基本步骤 翔激 漱 缀火 震 焉凝 矗 不夫 t 图1 2 模式识别的基本步骤 f i g 1 2 b a s i cs t e p so f p a t t e r nr e c o g n i t i o n 模式识别的基本步骤见图1 2 ，由模式空间经过特征空间到类型空间是模式识别所 经历的过程。在物理上可以察觉到的世界里，适当地选择某些物体和事件，我们把它 6 大连理工大学硕士学位论文 们称为样本，对它们分别进行观测。每个样本的观测数据的综合都构成模式，所有的 样本观测数据则构成模式空间。由物理上可以察觉到的世界到模式空间经历的过程称 为模式采集。模式空间的维数是有限的，但还是非常多的，其中有些并不能有效地揭 示样本的本质正像人们对事物进行判断之前要进行综合分析一样，机器在做出判断 之前也要对模式空间里的各维元素进行综合分析，利用选择或者变换的方法提取最能 反应样本特征的主要特征，这些特征就构成特征空间。每个样本在特征空间里是一个 点由某些知识和经验可以确定分类准则，称之为判决准则。根据适当的判决准则， 分类器把特征空间里的样本区分成不同的类型，从而把特征空间塑成了类型空间 一个神经网络要实现模式识别需要先经过一个训练的过程，在此过程中网络需要 不断地接受一个模式集合( 模式空间的点集) 以及每个特定模式所属的类s o ；然后，把一 个以前没有见过但属于用于训练网络的同一模式总体的新模式( 模式空间的任意一点) 呈 现给神经网络。神经网络可以根据从训练数据中提取的信息识别特定模式的类别。神 经网络的模式识别本质上是基于统计特性的，各个模式可以表示成为类型空间的一些 点类型空间被划分为不同的区域，每个区域对应一个模式类。类型空间的边界由训 练过程决定我们可以根据各个模式类内部用统计方式确定边界。 图1 3 中神经网络模式识别机组成方式的一种，它分为两部分，用来作特征抽取的 无监督网络和作分类的监督网络。这种方法遵循传统的统计特性模式识别方法。用概 念术语来表示，个模式是一个磁崔的可观测的数据，即刷牲模式空间中的一个点z 。 特征抽取描述为一个变换，它将点z 映射成一个d 维特征空间相对应的中间点暑，( d 叩 中其 桑伯男：中文科技文档中数学公式的抽取 权值的改变量 略= 7 馘嘭 喀= 田唾 ( 2 7 ) 在线梯度法的缺点在于，由于每次对权值的更新都是局部的，网络有可能陷入局 部极小。对于这个问题，可以通过在权值更新规则中弓l 入一个惯性项的方法优化权值 更新的过程。 卜叩警啡) ( 2 9 ) 其中，“钿表示网络中的任一权值。由公式2 9 推出下列公式： c 川卜音鬻 在迭代过程中，通常取a 为( 0 ，1 ) 内的常数。 综合以上讨论我们看到，应用b p 网络时，所处理的信息( 工作流程) 是前向传播的， 因此称为前传网络而在网络学习阶段，是用误差的向后( 或称反向) 传播来逐层修改权 值，因此称为反向传播( b a c k p r o p a g a t i o n ) 算法 2 2 用z e r n i k e 矩进行特征提取 在绪论中关于模式识别的介绍中，我们已经提过用人工神经网络进行符号识别需 要对识别目标进行特征提取，然后将提取后的特征向量送入分类器进行分类。 z e m i l ( e 矩【l o 】是基于z e m i l 正交多项式的一种矩特征。z e r n i k e 多项式是定义在 单位圆上的一组多项式，通常用极坐标表示。z e m i k e 多项式按如下方式定义； = c e - f - i 砑( r ) 以c o s m o ，i f l , 0 = 、i 而r ? ( r ) 、压s i n m o ，m 0( 2 1 1 ) = 丽磁( r ) ，m = 0 其中，靠、m 均为非负整数，n m 且7 , 一1 7 7 1 i 为偶数，r 、0 是单位圆上的极坐 1 8 大连理工大学硕士学位论文 标，聊( r ) 是关于r 的径向多项式， 其中 鼬) = 加善胆而丽矬硭斋研一训 贸( r ) 的迭代公式如下： 七l 冠x ：( r ) = ( 如r 2 + 岛) j 留p ) + 缸稚2 ( r ) ( 2 1 3 ) h= 如= 如= h= 。n ( 半+ ，) ( 丁y 1 - - 7 r + ) 2 n ( n + 1 ) + 2 ) 一，n 2 ( 他- i - 1 ) 一n ( n + 1 ) ( n + 2 ) ( 2 1 4 ) 一z ( 半) ( 竿) c n 均 研( r ) 的导数芸j 蛩( r ) 的迭代公式如下： 其中 d 1 ( r ) 未碍? ( r ) = 如( r ) 蜀? ( r ) + 如( r ) 稚。( r ) ( 2 1 5 ) d 1 = n r ( , a 一1 ) 如= 啪n 1 ) + ( 竿) m 州2 1 ) 】 ( 2 1 6 ) 如一一。( 半) ( 竿) 二维平面上单位圆内图像的连续函数，( 卫，轳) 的礼阶z e m i l 【e 矩定义为： 厶二。= 半厂上+ 二曼，( z 勘【如r 出妇 ( 2 1 7 ) 桑伯男：中文科技文档中数学公式的抽取 其中， 为复共轭，复值函数k 。( 。，y ) 定义为： ( 。，y ) ；1 i 。( r ，口) = j 嚣( r ) 唧( i 枷)( 2 1 8 ) 矩特征提取具有抗旋转的性质。设，( z ，! ，) 是图像的分布函数，z e m i k e 矩的极坐标 表示为 a 。，= i f y ( r ，口) 肌( r ) 似p ( 1 m 目) r d r 甜 ( 2 1 9 ) 其中，知( r ) 是z e m i k e 多项式。当图像旋转角度日时 磁= 唧( 一卵) 则旋转后的z e m i k e 矩的模i | f 品0 = l f 昂， 利用1 4 阶z e m i k e 矩进行特征提取后， 陀2 0 ) 是旋转不变的 使用p c a 神经网络 i h 将得到的特征向量 压缩到1 8 维，以降低符号识别器的规模和识别难度。送入分类器识别失败后，还需进 行粘连字符分割的工作。， 2 3 数学符号的识别 由s o f m 神经网络和b p 神经网络组成数学符号识别的分类器。选用i 嬲中 的1 8 5 个常用数学符号用s o f m 神经网络进行粗分类。在s o f m 中，我们设a 是由3 5 个 神经元组成网格，所有神经元排列成环形结构，每个神经元只受前后两个神经元的影 响。取距离函数为阶梯函数。 垆傺：2 叫功 其中，屯是获胜单元k 与另一个单元巧之间的距离，刀( ) 和( k ) 是迭代次数k 的 函数。 $ o f m 网络的训练分为两步。 第一步是粗分类阶段，这一阶段般需要上千次迭代；使训练样本经过网络映射 后得到位置大致正确的获胜单元。开始时应该在k 的较大调整邻域内修改权值，然后随 着迭代步数k 的增加而逐渐收缩调整邻域。设置r ( 0 ) = 0 9 ，a ( 0 ) = 1 0 ，最大迭代次数 一2 0 一 大连理工大学硕士学位论文 k = 1 0 0 0 0 ，令q ( k ) = 叩( 0 ) ( i k k ) ，a ( 七) = a ( 0 ) ( 1 一k k ) 。 第二步是分类细化阶段，令町( k ) 兰0 0 0 5 ，a ( k ) 兰0 ，h ( d j 。，k ) 的支集不包括输出 层获胜神经元的临域，即每次迭代只有获胜神经元的权值得到更新。 通过s o f m 粗分类，我们得到3 5 个大类，每个大类对应一个b p 网络。这样降低 了b p 网络的分类模式数，提高了训练速度。 接下来，针对每一组符号，分别训练一个b p 神经网络用于识别具体的符号。即对 属于该类的符号进行细分类，并将识别结果以1 5 马薛格式保存。选取网络的活化函数为 s i g m o i d 函数 9 ( 茹) 5 再i 涵 ( 2 2 2 ) 学习速率 町( 功= ： ( k - 一1 。) ) ( ( 1 。+ - 弓：主( ( 的k ) e e ( k - 一。1 ； ( 2 2 3 ) 惯性项 m ，= 嗡篡二2 ， 其中，叩( o ) = 0 1 ，a ( o ) = 0 1 5 ，e = 0 0 2 ，隐层和输出层的活化函数都是公式2 2 2 表 示的s i g m o i d 函数，但参数稍有差别。s i g m o i d 函数的斜率与参数口有关，令隐层活化 函数的历= o 0 4 ，输出层活化函数的压= 0 5 。为避免系统过早的陷入饱和区，连接 隐层和输出层的权向量都选取为小的随机数。实验表明，训练后的b p 网络的识别率能 够达到9 0 以上 2 l 一 大连理工大学硕士学位论文 3中文环境中数学公式的抽取 随着计算机和网络的发展，通过网络存储和查找各种资料，由于其方便、低成本 的特点，已经成为当前信息资源共享和传播的主要途径。然而人类几千年文明所积攒 的大量科技成果和信息均是以纸质印刷品甚至手写品的形势存在的，存储和查找都不 够便捷且成本过高。o c r ( 光学字符识别) 系统提供了一种将纸质文档转化成可编辑 的电子文档的解决方案， 3 。1 该领域研究概况及相关问题 3 1 1 现有算法介绍 1 9 9 6 年，r lf a t e m a n 等人提出了一种自底向上的公式定位方法【1 6 】首先对文档 图像全篇扫描，画出所有的连通体。在把文档图像中包含的所有符号进行识别后，将 这些符号分成数学公式符号和文本两类，将所有的数学公式符号进行适当的组合，最 终合并出文档中的数学公式 1 9 9 7 年，h j l e e 等人对以上方法作了改进，提出了一个分为两个主要步骤的公 式定位方法 1 7 1 8 1 首先，利用行间距、行高、字符密度等信息提取出独立公式行， 然后，对文本行中的每个符号进行识别，寻找其中存在的公式符号，并将这些符号组 合，提取出内嵌公式行 在这之后，1 9 9 8 年k i n o u e 等人【2 6 】，2 0 0 0 年ug a r a i n 等人 2 7 1 ，2 0 0 3 年，s e c h o w d h u r y 等人【2 8 】，也都提出了基于类似原理的改进算法其中g a m i n 等人提出以公 式( 3 1 ) 计算行内所有符号左下角像素的标准偏差，来提取独立的公式行。 5 8 d = 去f z - z 野一( 砉m ) 。 ( 3 1 ) n n - 这些算法的一个共有的特点是：首先它们都要对目标文档全篇进行连通体的标记， 在下面2 2 的分析中我们将看到这是相当费时的。其次，在定位文本行中的内嵌公式的 时候都是采取寻找特殊数学符号，再以此为根按某一算法向周围进行扩展，从而确定 公式范围。这样做的缺点在于仅仅利用了数学公式在特殊符号上的特点，却没有充分 利用数学公式如像素分布密度、连通体间隔不规则性等宏观的、模糊的特点。 2 3 桑伯男：中文科技文档中数学公式的抽取 另外一个共同的缺点是，这些算法在寻找公式时，不考虑文档特点、公式密度， 始终采用相同的公式定位算法，即都不断地对每一个输入目标图像进行模式识别的动 作，判断其是否为某些特殊数学符号，这实际上也是相当费时和可以避免的。 最后，由于我们将在3 1 4 中详细叙述的中文科技文档的特点，这些算法在向中文 环境迁移时也都存在各种各样的问题。本文所提出的算法将致力于解决以上不足。 3 1 2 标记连通体的讨论 以2 0 0 3 年，f l ic h a n g 等人【2 9 给出的算法为例： 该算法自顶向下，从左至右的逐行扫描图像，l 为用来标记连通成分的标签，初始 值为o 对扫描遇到的1 像素p 执行以下操作： ( 1 ) 如果p 左侧为m 像素且p 没有被标记，那么p 是一个外部轮廓的开始点l = 工+ 1 ，将p 标记为l ，找出包含p 的外部轮廓，并将轮廓上的所有1 像素都标记为l 在 标记轮廓的过程中，将轮廓追踪算法绕1 像素顺时针旋转时经过的0 像素都标记为1 ( 2 ) 如果p 左侧是一个标记为m 的1 像素，且p 没有被标记，那么将p 也标记为m ， ( 3 ) 如果p 右侧是一个没有被标记为1 的0 - 像素，那么p 是一个内部轮廓的开始点 依本文所述的轮廓追踪算法找出包含p 的内部轮廓，并用与p 相同的标签标记轮廓上的 所有1 像素在标记轮廓的过程中，将轮廓追踪算法绕1 像素顺时针旋转时经过的o 像 素都标记为- 1 使用f uc h a n g 算法标记图像中的连通成分的过程如图3 1 通过上述介绍，我们发现标记连通体是一个相当繁琐、费时的步骤，即使忽略搜 寻和判断步骤，只定义标记像素点为一步，对一个如图1 1 所示的外部轮廓为, r r , 祀，内 部空心为p q 的连通体，画出单个连通体需要约( ( m + 1 ) ( n + 1 ) 一( p 一1 ) ( q 1 ) ) 步。 而由于在画完一个连通体之前无法确认下一个连通体的位置，所以不同连通体之间的 标记只能顺序进行。一个科技文献每页的连通体应该在1 0 0 0 这个数量级上，而中文文 档中由于每个汉字都由多个连通体组成，这个数量还要大。 3 1 3 对人类阅读方式的借鉴 人类每时每刻都在通过视觉进行图像的输入和处理，并对处理后的图像进行模式 识别。这套系统能够快速运行在于人类总是并行的处理输入的图形，并且只根据特定 的目的对特定的模式敏感，而对其他模式进行模糊处理。 2 4 大连理工大学硕士学位论文 ab cd 图3 1连通成分标记过程 f i g 3 1 p r o c e s so fc o m p o n e n tl a b e l i n g 具体到文字阅读来说：首先，我们在阅读时为了达到一定的速度，都是同时读入 数个文字，进行同步识别然后再读入后续的多个文字，以前面的文字作参考继续阅 读。其次，我们在阅读的时候并不是先画连通体再识别，而是根据经验有一个预期识 别目标的输入范围框，先识别再根据识别结果调整输入范围。 具体到公式定位来说：如果我们的目的是要找到公式的位置，那么对于文字部分 并不需要进行准确的识别，只要模糊的知道是文字就可以了。而对公式的定位可以先 通过公式在黑像素分布密度、分布结构等方面与文字行的明显差异先找到异常区域， 然后再在异常区域具体寻找特殊符号，并准确定位公式范围。 3 1 4 公式分布局部性及中文科技文档的特性 通过对大量科技文档的观察，我们发现科技文档中存在这样的共性，即数学公式 的分布存在局部性，以下简称为局部性。所谓局部性即指在一个宏观的层面上，不同 学科的科技文献出现公式的频率不同，有些学科的科技文献可能全文只出现一两个公 2 5 桑伯男：中文科技文档中数学公式的抽取 ? 阅i 图3 2汉字的连通成分组成 f i g 3 2c o m p o n e n t s t r u c t u r eo fc h i n e s ec h a r a c t e r 由图可见，当分辨率足够大时，一个中文字符“阅”就由5 个连通体组成，而且连通 体之间的位置关系并没有一定的规律可循，这不仅增加了画连通体的工作量，而且即 便画完连通体仍无法准确判断模式识别目标单位的准确范围，还需要有成熟的连通体 合并算法，如果算法通过连通体相对位置关系判断是否为公式，考虑到中文文档中汉 字的连通体之间同样有二维结构，也会增加误识的情况。 但中文文档还有一个特点可以加以利用，即英文文档中大小写的高宽不统一，在 一行中的所在位置也不一样，而中文文档中除标题行和内容段的字号有所区别外，每 个字的高宽都是基本统一的，高宽所占空间与汉字不一致的标点符号和括号又比较容 易识别。 3 2 公式抽取新算法的特点 3 2 1 规避画连通体步骤 从对以往算法的介绍，我们看到：一方面，画连通体为文档图像分析带来了繁重 的计算量：但另一方面，画连通体给出了确定模式识别范围的方法，似乎不画连通体 就无法确定每次送入模式识别模块的对象的具体范围在哪里。能不能找到一种不需要 一2 6 大连理工大学硕士学位论文 画连通体而找到识别目标输入范围的方法? 通过对人类视觉原理的观察，我们发现人在进行模式识别时并不进行画连通体的 步骤，而是对即将要识别的物体有一个先验的期望大小，在根据识别结果判断期望大 小应该放大还是缩小，直到识别成功。本文所给出的算法受此启发，使用一个字符读 取框去顺序的读取中文字符，而中文读取框的大小来自对目标文本本身的统计数据， 从而达到识别系统对不同文档的自适应性。 这个方法在机器视觉和对英文文档的识别中同样可以使用。但由于所识别目标大 小的差异性，需要更多型号的输入框，和一套自动根据识别结果调整输入框大小的辅 助算法，实现起来相对复杂。而中文文档，一方面由于汉字由多连通体组成的特点，