（模式识别与智能系统专业论文）复杂结构文档图像中数学公式的定位.pdf

声卜 川p w m ab s t r a c t wi 由 t h e r a p i d d e v e l o p m e n t o f t h e g l o b a l i n f o r m a z a t i o n , t h e i n f o r m a t i o n s e a r c h i n g b e c o m e s m o r e a n d m o r e i m p o r t a n t . a s a s o u r c e o f i n f o r m a t i o n t h e s e p a r a t i o n o f i n f o r m a t i o n i s b e c o m i n g a n i n d i s p e n s a b l e p a r t o f i n f o r m a z a t i o n p r o c e s s . i t s t h e k e y t e c h n i q u efor c o n v e r t i n g叨 t r a d i t i o n a l k n o w l e d g e i n t o e l e c t r o n i c a l f o r ma t . 玩t h i s p a p e r w e s t u d y o n a s u b p r o b l e m o f i n f o r m a t i o n s e p a r a t io n -m a t h e m a t i c a l f o r m u l a e x t r a c t i o n i n d o c u m e n t i m a g e w i t h c o m p l e x l a y o u t . w e p r o p o s e a n o v e l m e t h o d m o d a l o f m a t h e m a t i c a l f o r m u l a e x t r a c t i o n i n d o c u m e n t i m a g e w i t h c o m p l e x la y o u t . t h e m o d a l s u m u p t h e f o r m u l a e x t r a c t i o n i n t o t w o m a i n p r o b l e m : d o c u m e n t l a y o u t a n a l y s i s a n d d o c u m e n t e l e m e n t c l a s s i f i c a t i o n . a c c o r d i n g t o t h e i n t e r n al i ty o f t h e d o c u m e n t i m a g e w i t h c o m p l e x la y o u t , w e c l a s s i 勿t h e m a t h e m a t i c a l f o r m u l a i n t h i s k i n d o f d o c u m e n t i n t o t w o c a t e g o ry f o u r 钾 p e . w e a l s o p r o p o s e t h e c o r r e s p o n d i n g e x t r a c t i o n m e t h o d o f e a c h t y p e o f f o r m u l a . o n t h e b a s i s o f e x t r a c ti o n m o d a l o f t h e f o u r t y p e m a t h e m a t i c al f o r m u l a , w e i m p l e m e n t a f o r m u l a e x t r a c t i o n s y s t e m . w e a l s o s h o w t h e d e t a i l o f t h a t s y s t e m i n t h i s p a p e r . wit h t h i s s y s te m w e c a n l o c a t e t h e f o r m u l a i n t h e d o c u m e n t i m a g e b o t h p r e c i s e l y a n d r a p i d l y . i n t h i s p a p e r t h e s y s t e m e v a l u a t i o n i s al s o g i v e n . t h e p a p e r e v al u a t e s t h e f o r m u l a e x t r a c t i o n s y s t e m i n b o t h v e r a c i ty a n d v e l o c i ty . a t t h e l a s t o f t h i s p a p e r t h e mo d i fi c a t i o n d i r e c t i o n o f t h e f o r m u l a e x t ra c t i o n me t h o d i s p r o p o s e d ma t h e m a t i c a l , f o r m u l a , m a t h e m a t i c a l f o r mu l a e x t r a c t i o n , i s o l a t e f o r m u l a , i n l i n e f o r m u l a , d o c u m e n t i m a g e l a y o u t a n al y s i s , c l u s t e r , s y m b o l r e c o g n i t i o n n 目录 图 目 录 图2 - 1文档图像中的文字、公式、表格二 “ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 图2 一 文档图像中的公式文字和图. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 图2 一 独立公式和内嵌公式. ” . ” ” “ . ” “ . “ . ” . “ . “ . ” . ” “ “ :.” :.” 二 ， 图 2 - 4独立行公式 ( 单行). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 0 图 2 一独立行公式 ( 多行). . . . . . . . . . . . . ; . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 0 图 2 一 内嵌公式 ( 显式). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 0 图 2 - 7内嵌公式 ( 隐式)二 “ . . . “ . ” . ” :. “ . . ” “ 二 ” . . . . . . . . . . . . . . . . . . . . ; . . . . 1 0 图 2 - 8复杂结构文档图像中数学公式定位方法模型. . . . . . . . . . . . . . . . . . . 1 1 图自 顶向下一次划分. ” . ” “ “ “ . ” . ” “ “ ” . ” :.“ ” “ :.” ” . ” 二 ” . . . . . . . . . . . 1 3 图自 顶向下二次划分. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 4 图2 - 1 1 x -y投影示意图. . . . . .“ :. ” ” . “ . ” 二 “ “ ” “ “ “ ” 二 “ . . . . . . . . . . . . . . 1 4 图2 - 1 2自 底向上查找连通体. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 5 图2 - 1 3自 底向上的聚合. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 5 图2 - 1 4模式识别问题的一般解决流程. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 7 图2 - 1 5版面特征的各参数. . “ 二 ” ” . ” “ ” ” . ” . ” ” ” .“ ” 二 ” . . . . . . . . . . . . 1 8 vi 目录 图 3 - 1 o f r定位系统的工作流程图“ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 图 3 一完全单、双栏版面结构.“ “ “ “ . . . - - - 一 “ . . ; . . . . . . . . . . . . . . . . . . . . . . 2 4 图 3 - 3有通栏成份的版面结构二 ” “ “ . ” . ” ” ” “ . “ :.“ :.” 二“ . . . . . . . . . . . . . . 2 4 图 3 -0 区域和行的直观示意图. ” ” ” ” . . .， - - - - 一tt ” ” ” . - - - - - 一 ” . . . . . . . . 2 5 图 3 - 5一次区域划分示意. “ . “ ” ” ” ” . “ “ .” “ “ . . ” ” ” . “ . “ ” “ 二 2 6 图 3 - 区域划分结果. . ” “ ” . . “ . “ “ :.“ . . “ . “ . ” . ” ， “ . “ 二 “ “ ” :.2 7 图 3 - ，行切分结果. ” ， ” . “ ” 二 “ ” ” “ ” . “ .“ . “ 二 。 . .“ . ” “ ” . “ 二 “ . . . . . . . 2 9 图 3 - 8一个公式被分为两行. . ” “ 二” “ :.“ . “ “ 二” . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 0 图 3 - 9断行重组后的结果. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 0 图 3 - 1 0两类空白的分布. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 图 3 - 1 1 w o r d 划分结果. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 图 3 - 1 2拆分不完全的w o r d . . . . . . . . . . . . . . . . . ” 二 ” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 4 图 3 - 1 3拆分过细的w o r d . . . . . . . . . . . . . . . 一” . “ “ “ _“ ” . 一” . . . . . . . . . . . . . . . 3 4 图 3 - 1 4内嵌公式定位流程. ” ” ” “ 二 “ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 6 图 3 - 1 5文字的b a s e l i 二和m e a n l i n e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 一” . . . . . 3 6 0了0 34 图 3 - 1 6定位识别引擎工作流程二 “ :.“ “ :-” . ” ” “ ” “ “ . . “ “ “ . “ 图 3 - 1 7被分裂的内嵌公式 ( 注意等号)二 “ 一 .- ” “ . . - 一 - - - - - - - . . . . . . . . . vn 目 录 图 3 - 1 8内嵌公式w o r d的合并二 二 “ 二 ” 二 ” . . . . . . . . . . . . . . . . . . . . . . . . . ; . . . . . . . . . . . . . . 4 1 图 4 - 1准确率自 动评系统测流程图. . . . . . . . . ; . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3 目录 表 目 录 表 3 - 1 定位识别分类器的参数. ” ” “ “ _ 一” 一:.” 二 “ . . . . . . . . . . . . . . . . . . . 3 9 表 4 1 准确率评侧结果. . . . . . . . . . . . . . . . . . ; . . . . . . . . . . . . . - 一 ” . . . . - - - - - - - - - . . . . . . . . . . . . . . 4 5 表 4 2时间消耗评测结果. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ; . . . . . . . . . . . . . . . . . . . . 4 5 ix 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、 保存、使用学位论文的规定， 同意如下各项内容:按照学校要求提交学位论文的印 刷本和电子版 本;学校有权保存学位论文的印刷本和电子版，并采用影印、 缩印、 扫描、 数字化或其它手段保存论文; 学校有权提供 目 录检索以 及提供 本学位论文全文或者部分的阅览服务: 学校有权按有关规定向国家有 关部门 或者机构送交论文的复印件和电 子版: 在不以 赢利为目 的的 前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学 位 论 文 作 者 签 名 : 1孵 夕 。 刁年 丁 月 2 61 日 经指导教师同意， 本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名:学位论文作者签名: 解密时间: 年月日 各密 级的 最长保密年限及书写格式 规定如下: 内 部 _5 年 最长5 年，_ 可 少于5 一牟尧 i z 10 f, 7 % t 10x )(mi l: 20 f , 7 t 20 tf ) 南开大学学位论文原创性声明 本人郑重声明: 所呈交的学位论文， 是本人在导师指导下， 进行 研究工作所取得的 成果。 除 文中己 经注明引用的内容外， 本学位论文 的 研究成果不包含任何他人创作的、 己 公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出 贡献的其他个人和集 体， 均已 在文中以明确方式标明。 本学位论文原创性声明的法律责任 由 本人承担。 学 位 论 文 作 者 签 名 : - , 鹏 平 厂月 x日 第一章 引言 第一章 引言 第一节 全球信息化的浪潮 最新的 研究成果表明， 人类的文明大概起源于2 0 万年前， 有文字记载的 人 类文明 史也有5 0 0 0 多年，在这漫长的历史长河中人们不断战天斗地，不断地改 造世界， 创造了今天的高度文明，我们在享受祖先留给我们的巨大的物质财富 的同时 也 在享受着祖先给我们留 下的一笔更为巨 大的财富那就是人类积累下来 的各种知识，而在这庞大的知识中又有很大一部分是数学。 数 学 语言作为“ 唯一的国 际 科学 语言” ， 不受 种族、 国 家、 文 化和任 何方言 的限制， 数学语言被认为是最完美， 最有内 涵的语言。而数学公式，作为数学 语言最准确的表达方式，出 现在各个领域的文档中，1 9 9 1年发射的美国旅行者 号宇宙探测器就将数学公式铭刻在所搭载的物品上期待外星人可以看懂我们地 球的文明。可以说:数学公式是构成大多数科学和工程科技文档的重要部分， 尤其是理工科资料文档，数学公式往往更是其核心内容。 美国 著名的未来学家托夫勒在其出 版的著作 第三次浪潮中将人类社会的 发展分为三个阶段: 第一次浪潮为农业阶段，从约 1万年前开始;第二阶段为 工业阶段，从 1 7世纪末开始;第三阶段为信息化 ( 或者服务业)阶段，从 2 0 世纪5 0 年代后期开始。我们现在正亲历着如托夫勒所言的第三次浪潮社会。人 类社会的发展表明，信息传递的速度是直接影响社会发展速度的重要因素，如 何让信息 传递的更快更远一直是人类社会所面临的问题，而信息传递的速度又 取决于信息的载体。从最早的口口 相传到后来的以纸为媒介的信息传递，到现 在的因 特网可以说信息传递的方式发生了质的飞跃。在我们所处的信息社会中， 信息传递的速度可以按照爱因斯坦所说的宇宙最快速度光速进行传播，他的唯 一要求就是我们的信息要以电磁信号的方式保存。怎样将人类社会前两次浪潮 阶段所积累下来的知识电子化是我们在信息社会所面临的一个重要问题。当信 息社会发展到一定阶段，人类必然对于当今发展起来的信息交换、检索平台产 生依赖，到那个时候不能被搜索到的信息就等于不存在，如果我们不能将现有 的知识电子化那就意味着我们将失去祖先留给我们的巨大财富。数学公式的定 位、识别、理解正是要解决将数学公式电子化的问题。 第一章 引言 第二节 数学公式定位系统综述 1 .2 . 1光学字符识别与光学公式识别综述 光学字符识别 ( o p t i c a l c h a r a c t e r r e c o 咖t i o n , o c r ) ，是属于图型识别的 一门学问。其目 的就是要让计算机知道它到底看到了什么，尤其是文字资料。 o c r的概念形成是比计算机诞生还要早的事情0 1 9 2 9 年， 德国的科学家t a u s h e c k 首先提出了o c r的 概念， 并且申 请了专利。 几年后， 美国科学家h a n d e l 也提出 了利用技术对文字进行识别的想法. 但这种梦想直到计算机的诞生才变成了现 实。伴随着上个世纪中叶二次世界大战的结束，整个世界进入了一个空前规模 的建设时期，随之而来的是人们之间的交流增多，邮件系统每天所要处理的邮 件量的增加迫切需要能够自 动完成邮件分拣的技术。 现代o c r技术正是在这一 背景下兴起的， 他最初只是着眼于邮政编码的自 动识别， 随着o c r技术的成熟， 他的应用领域也进一步拓展， 不断出 现的新需求也不断地促进着o c r技术的进 步。 光学公式识别 ( o p t i c a l f o r m u l a r e c o g n i t i o n , o f r ) ， 是利 用o c r 技术解决 数学公式的识别理解等问题的技术。 o f r的问题的提出 基本是在o c r技术刚刚 发展的 初级阶段完成的， 在人们初步完成了一维文字的识别后，马上就对二维 的 数学公式的 识别产生了 兴 趣。 早 在1 9 6 8 年a n d e r s o n i 就在 他的 博士论文中 提 出数学表达式识别与理解的问 题。之后越来越多的研究者开始关注并研究这个 问题，而且在9 0 年代一度成为模式识别领域的一个热门问题。第一届到第五届 i c d a r ( i n t e r n a t i o n a l c o n f e r e n c e o n d o c u m e n t a n a l y s i s a n d r e c o g n i t i o n ) 大会上就有1 2 篇与数学公式识别直接相关的文章。虽然在数学公式识别方面的 研究很多，但是大家还是普遍认为数学公式的二维结构是数学公式相对于普通 的文字o c r处理的 难点。 纵观现 有研究成果， 在数学公式的 符号识别方面大家 已 经做的很好，但是在公式定位和公式语意理解方面还没有特别成熟的技术出 现，在这两方面还有很长的路要走。 1 . 2 . 2 数学公式定 位研究的历史 尽管公式识别这个课题很早就提出 来，而且近年来有许多 人都在研究它， 第一章 引言 但它现在还只是处在理论研究阶段，目 前市场上还没有此类产品面世，之所以 这样主要存在两个方面的原因: 1 )数学公 式 往 往是二 维结构 1 2 1 ， 比 起文 字的 一维 结 构确实 存在着难点， 加 之数学公式形式多样，也增加了处理的难度。 2 )数学公式的 识别应该遵循定位、 识别、 理解这样一个过程， 但是在前期 的研究过程中， 学者们的眼光普遍放在了 识别上， 因为他们认为识别更 有挑战性， 更能引起他们的兴趣， 当公式符号的识别取得了一定的进展 之后他们突然意识到他们的技术不能商品化， 因为他们的研究是给予一 个假设那就是他们要识别的公式都已经从文档图像中精确地提取出来 了， 当这个假设在实际中不能成立的时候他们就会发现他们的识别技术 是没有用武之地的。 基于上面的原因，数学公式定位大概分为两个阶段: ( 1 ) 人工定位阶段: 在这个阶段学者们感兴趣的是数学符号的识别，他们对公式的定位和 提 取 不 感 兴 趣 。 在x u e - d o n g t i a n 2 】等 的 论 文 中 就 有 这 样的 话: s o f a r , m o s t o f t h e r e s e a r c h o n t h e f o r m u l a s r e c o g n i t i o n a s s u m e d t h e f o r m u l a s a r e a i s k n o w n . v e ry f e w p a p e r s h a v e a d d re s s e d s p e c i fi c p r o b l e m s r e l a t e d t o m a t h e m a t i c a l f o r m u l a s e x t r a c t i o n . 在这个阶段所有给出数学公式符号识 别的系统要么假定所有的公式都已 经准确定位，要么就是用人工的方 法进行定 位. 直到1 9 9 5 年h s i - j i n n l e e 的 论文发 表， 才第一次 提到了 数学公式的定位问题，由 此数学公式定位研究进入了一个新的阶段。 ( 2 )自 动定位阶段， 这一阶段自1 9 9 5 年开始一直到现在。 在这一阶段出现 了 很多数 学公式自 动定位的研究成果， 提出了 各种各样的定位方法 - i t 在这一阶段， 很多学者都将主要精力放在了公式定位的研究上， 公式定 位不再是数学公式识别的附属问题， 而是数学公式识别技术商品化所必 须要克服的 一个瓶颈问 题。 本文也是在现有数学公式定位的研究成果基 础之上， 对数学公式定位方法的研究和探索， 着眼于解决公式定位中的 准确性和性能的矛盾。 第一章 引言 第三节 本文研究问越的提出 1 . 3 . 1问 题的提出 对于文档图像中 数学公式的定位，已 经有一些成果给出了定位方法， 但是 还没有已有的成果是研究复杂文档图像中数学公式的定位。本文以印刷体科技 文献为研究对象。这种文档图像的特点是: ( 1 ) 文档结构复杂 科技文档在版式上通常存在单栏、多 栏、 单栏多栏混合、 有通栏标题图 表等复杂版面结构。 ( 2 ) 版面元素多 科技文献往往为了能够对问题做出清晰的描述，会使用图、表、公式、 文字等多种表达手段，使得科技文献文档图像中版面元素较多。 ( 3 ) 公式对于文档的理解意义重大 数学公式往往内涵深刻，包含信息量大，在科技文献中大量使用，因此 对于公式的定位对于机器理解科技文献具有重要的意义。 对于印刷文档图像中数学公式的定位，虽然已 经有了一些研究成果， 但是 没有任何一个研究成果可以 解决文档图像中的所有类别的公式定位，本文就是 要在现有成果的基础上建立一个综合的定位方法模型，来解决所有类别的数学 公式的定位。 在现有的发表的对于数学公式定位的 成果中，从大的方法模型上区分定位 的方法主要分为两类:自 底向上定位和自 顶向下定位。 自 底向上定位方法模型是先确定扫描文档图像中最小的单位连通体( c c s ) , 然后根据连通体的位置关系，将联通体聚合成词 ( w o r d )行 ( l i n e )段 ( b l o c k ) 等，再根据每一行的版面特点，将行分类为公式行或是文字行。 自 顶向 上的定位方法模型是先将整个文档图 像当作一个大的b l o c k , 然后根 据版面中的空白 情况将这个大的b l o c k 划分为小的b l o c k ，再用同样的方法将各 个小的b l o c k 继续划分，直到某一个粒度级别，最后划分出来的就是行 ( l i n e ) , 最后根据行的特征将行分类为公式行或是文字行。 在两类方法模型中，都会在最后根据行 ( l i n e )的特征对行 ( l i n e ) 进行分 类，在行 ( l i n e ) 特征的选取上同 样也存在着两种流派。一个流派是使用结构特 第一章 引言 征作为分类的主要依据。通过对印刷体图像的观察中我们可以 看到，公式行的 上下左右的空白是比较大的，有时公式还有标签在公式的后面，更主要的特征 是公式一般具有二维结构。普通文字行没有这种特征。另外一个流派通过对符 号的识别找出行 ( l i n e )中数学符号，然后一这些符号为基础， 通过一定的规则 向符号两端进行扩展，最终找到整个公式。 上 述的方法模型对于数学公式定 位往往会存在一些问 题。自 底向 上的定位 方法使得系统处理的粒度太小，往往会造成速度上的问题，同时他对于公式的 定位是一个由小到大的增长过程，增长的限度是这种方法存在的一个问题，增 长的太小则公式定位不完全，或是将一个公式分裂成多个公式;增长的太大就 会将非公式成分引入到公式中。 这些都会造成公式定位的不准确。自 顶向下的 定位方法是将版面进行递归的分解，分解的限度也是这个方法的一个关键问题， 分解太小就会将多个公式定位成一个公式，或者在公式中包含文字行，反之则 会使公式分裂成多个。 在两种特征选取方法中使用识别特征的会使定位速度下降，因为数学符号 较之普通文字来说字符集是很大的， 所以识别分类速度难以保证，而单纯使用 结构特征又会造成定位的准确性下降。 综合以 上几点， 我们认为 在数学公式定位系统中主要存在的矛盾就是定位 精度和定位速度之间的矛盾。所以 本文的主要目 标就是调和速度和精度的矛盾 在保证速度的基础上构建尽可能高精度的定位系统。 1 . 3 .2本文工作的重点和难点 数学公式处理技术发展如此缓慢，这和数学公式定位过程中存在的难点是 分不开的。在数学公式中，字符和符号是按二维的复杂结构排列的，这使得公 式提取相当困难，即便是能够准确识别出公式中的每个符号，也不一定能够定 位出公 式来1 10 1 1 1 1 1 . 总的说来，数学公式提取存在着以 下几个难点: ( 1 )内 嵌公式与文本往往混杂在一起， 界限不明显， 使得定位相当困 难。 ( 2 ) 公 式中的 字符并 不是 简 单 线性排列的 ， 而是呈二维结构 排列分布的 1 2 1 ， 例如，矩阵， 除式等。 字符的出现位置是随机的， 没有一定规律， 相邻 两字符的位置关系也不是很确定，这就给公式中字符定位带来一定困 难。 ( 3 ) 数学公式的 字 符 集 较大， 上的困难。 第一章 引言 这使得使用识别方法的公式定位也存在着性能 ( 4 )科技文献文档图像的 版面结构复杂， 版面元 素种类很多， 不同 种类有着 不同的特征，对这些特征进行分类，最终找到公式也存在着一些困难。 ( 5 ) 数学公 式 形 态多 样， 让机 器来区 分 这些形 态并 定 位出 公 式存在相当 大的 困难。 数学公式的定位， 也是要依靠模式识别的一些通用方法， 对于这 些方法而言先验知识是相当重要的， 但是由于数学公式形态的多样， 就 造成了先验知识的庞大， 并且难以覆盖全面， 这些困难最终会造成公式 区分、定位的困难。 本文将构造一个方法模型来实现印刷体文档图 像中数学公式的定位，工作 的重点将放在提高定 位的精度上，同时也要兼顾定 位的速度，精度x 速度将是 我们的优化目标. 第四节 本文内容组织 本文主要针对上述问题， 提出并设计一个合理的、实用性强、高精度的快速 的数学公式定位模型。根据这一模型，实现通用的、快速的、精确的印刷体数 学公式定位，它支持独立行公式和内嵌公式的定位，它结合了自 顶向下和自 底 向上识别与不识别相结合的方法思想，实现了高精度和快速的的数学公式定位。 本文是对近一年半工作的总结，全文结构划分为五章: 第一章 引言。 简要叙述了课题研究背景、 数学公式定位的国内外研究现状、 数学公式定位的必要性和难点，最后简要介绍本文的行文安排. 第二章 数学公式定位的方法模型。首先分析总结了国内 外学者关于数学公 式定位的不同方法，并对他们方法的不足之处进行阐 述，在此基础上本文随后 提出我们的系统中所应用的公式定位模型， 。 第三章 复杂结 构文档图 像中数学公式定位模型的 实现。 首先介绍了 本文所 实现的定位方法的总体流程。然后对版面拆解的整个过程进行了详细描述，接 着本文详细介绍了 在版面拆解的基础上对于两类数学公式一独立行公式和内嵌 公式一具体的定位方法。 第四章 实验结果总结与分析。在这一章中我们给出了对于数学公式定位性 第一章 引言 能评价的指标，评价的方法和我们实现的系统的 评价结果，并对实现结果进行 分析，指出系统的不足和改进的方向。 第五章 总结与展望。本章总结了该课题的工作并对未来的工作提出自己的 建议。 第二章 数学公式定 位的方法模型 的直观图像。 f r u i i v i dua l c oe t t i c i e n t s : l a e ; l r z 0 = n -1黯( ) l e ) 二 t h e t o gl i k e li h o o d r a t i o i s t h e s u m o f t h e瑰 图 2 - 4独立行公式 ( 单行) p r o b a b i l i t i e s . t h e p r o b a b i li ty o f e r r o r , i n t h i s c a w, 3 s t 1 2 j w h e r e 场 d e n o t e s e x p e c t a ti o n u n d e r h y p o t h e s i s 场. a l s o o f 图 2 - 5独立行公式 ( 多行) cl u t t e r / s e n s o r mo d e l s t a 礴 1 一: i f o r 二u , 】 ( b e f o r e 图 2 - 6内嵌公式 ( 显式) d e t e c t i o n -， u n d e r a s 声 图 2 - 7内嵌公式 ( 隐式) 独立行公式是指公式独立占 据一块版面位置，不与文字行相混杂，单行独 立公式和多行独立公式的区别在于公式是否是由多个公式行组成。内嵌数学公 第二章 数学公式定位的方法模型 式是指与文字行相混杂的公式，显式内嵌公式是指版面特征与普通文字有明显 区别的内嵌公式，而隐式内嵌公式是指公式在版面特征上于普通文字行根本无 法区分的公式. 第三节 复杂版面文档图像中数学公式定位方法模型 复杂结构文档和简单结构的文档不同，在复杂结构文档中存在很多版面元 素，各种版面元素以 一定的组织形式混杂在版面图像中.我们的目 的是要找到 这些版面元素中的公式，但是不幸的是公式是和其他版面元素馄在一起的，因 此我们需要一个版面元素分离的过程来将各个元素分开，然后再确定各个版面 元素的属性。 图2 - 8 给出了我 们解决复杂结构文档图像的 方法模型图。我们的方法模型 在功能划分上分为两大部分，版面分解和版面元素属性判定 ( 虚线标出) 。 版面分解版面元索挑性列定 图 2 - 8复杂结构文档图像中数学公式定位方法模型 版面分解的作用是将需要属性判定的版面元素分离出来，而属性判定是判 定分离后的版面元素的属性。版面元素的属性包括:图、表、单行独立公式、 第二章 数学公式定位的方法模型 多行独立公式、显式内嵌公式、隐式内嵌公式。在整个方法模型中，虽然从功 能上分为两大部分，但是在流程上版面拆解和版面元素属性判定是交叉进行的。 整个定位过程实际上是按照层次递进进行的。 在最初的区域划分中我们只使用较大的区域之间的空白 将整个版面分割成 不同的分块。在稍后的区域属性判定中我们根据区域的特征找出图、表区域。 去除图表之后的区域，要进一步划分成行，行的划分比区域划分时需要更 小的空白阐值。行的属性判别将依据行的版面特征区分出独立公式行和非独立 公式行。 去除独立行公式的版面就只剩下内嵌公式和普通文字了。 但是这两种版面 元素混杂在一起，并且混杂的程度比 前述的版面元素更加厉害，这就需要我们 将行分解文更小的单位单词。接下来我们的版面分析模块将进一步将行分 为单词， 然后对每个单词的属性进行判断，以 找出内嵌公式。 在进行了属性判定之后的版面元素还需要进行后处理。因为进行版面元素 属性判定时，只考虑了版面元素本身的特征，并没有考虑这个版面元素周围其 他版面元素之间的关系，是一种局部的决策，后处理就是要从版面元素之间的 关系出发完善决策结果，目 前阶段后处理主要包括独立行公式的合并和内嵌公 式的扩展。 在接下来的两节中我们将就复杂结构文档图像定位模型中的两个主要功能 模块进行介绍。 第四节 版面结构的分析 版面结构分析是复杂结构文档图像中数学公式定位区别于简单结构文档图 像定位的主要特征。对于文档结构分析， 现有的研究成果中主要提出两种类型 的方法，自 顶向下的分析方法和自 底向上的聚合方法。 下面我们先对这两种方法做一个简单介绍， 然后在这两种方法的基础之上， 详细描述一下本文进行文档结构分析时所使用的方法。 2 .4 . 1现有方法总结 在现有发表的有关版面分析的论文中提出的方法大致分为两类:自 顶向下 第二章 数学公式定位的方法模型 的分析方法和自 底向上的聚合方法。 ( 1 )自 顶向 下的版面分 析方 法 自 顶向下的方法，是将版面从大到小的划分过程。他起初将整个版面看成 一个大的区域，然后根据版面中的空白将整个版面划分为若千独立区域。然后 再将各个独立区域按照相同的方法划分，直到区域中的空白小于某一个阂值位 置。 x u e d o n g t i a n 在文献 r e s e a r c h o n m a t h e m a t i c a l f o r m u l a s e x t r a c t i o n fr o m c h i n e s e d o c u m e n t 中提到的就是这种方法。如图2 - 9 和图2 - 1 0 所示。 _ _ _ _尸7 a 7 _ _ _ . 一， . 翎刁 侧， 二a 穿 :. 如二 “ .顽 ，月认 甲 ，护户_ _ _华 州 竺 竺 丫 竺_ _ . _ 二 二 二 .二 竺竺 竺 犷 二鸯耳 ) 延渺馨要 阵 遥 甲兮牛丝墨 鼓鳞签毖1 鸳 l罗二 夕竺少 _ _ 二 竺只 二 _ 二 了岔二 份 犷 犷七 月 欲件 尸几 竺 呀 二石几了=艺 力 巴 ，阴.二公， 止月二 心 ; 竺二 二竺 乙一盆 凭月: 忿了 代二忆伫 尸 之二 借 份二 二几丁 了气 月 二 ， 。 ，“. ， ， ， 公.i， ， ， 叱 套 裤二共 涣锥一 .-. ts u y.，一 w a w au.rty am e+wa, 羚:dv ,rus a:wa 丝 竺 竺 ， 一一 ，h n , t ! ,. v 吵 阅 f 弃 二 : 二 一 一 一 。_k s r 云 二 益 啥 丫 孟 益 留 止 于 三云 三 三 怜 尔 ; 翎翩芯口嘟找 趁氛 习 ir w ” “ 二:咒份竺 .-吮 益公品 公 孟 益，忿奋 二 ; 召 心 盆 篇 心言- 一_ 闷 . ， 古 人月j.j .袖 “ 户 . ，. 月 . . 小 砂 心沪.、 ， 尸 .j 少. 0 州 竺份巴份严 于 望 竺份竺 泞 口 尹 . 二竺之 少 竺 里 份口 t j. 竺 甘 迎 巴里 阶 和 渭， 石 二 “ 万 巴 乏 于 巴 ， 母 二 ， 挤 笋 汤 二 写 i c : :,.聋撼 澡硫ywtlrlr y i y 子: 涪 蕊 子 议 兴二 志 沪 、 二 l n + 乏y w .j 如 图2 - 9自顶向下一次划分 1 3 第二章 数学公式定位的方法模型 l飞一绍 引 巴 说签之 _日 长 肖一 *h1 阵仁名 万 沈 吮呀醉照 r ，. 一 冲， ， ， ， - 一 一- 一.t l之 .， 月 勺 . 嘴 ， ， 二 ， 口司， 护 、 口 ，r . 吧 甲性照竺 肠盔乏 .-=二 一花爪蕊 弓 瑟戴暴续 1_ 1 巴 竺尸 竺 竺 .少二 竺月 少 二少 艺 巴 竺.里 甲 刀 咬 ! 硬 赞 月吮川七 路峪 二， 声 1书 p 肠、 .日 . . . 知 召 门 翻 吕曰 口 加 . j二 . 口 、内 ， ， 碑 口里 几: 琶r 芬 乡 尝 沈 姚: c .i ; u . 二 七z 忿. a . w y w iv 4 ， . ， 。 可洲咸.，“ 伟翻 户、 ，、 聋井习 匕 菩 兹 全 戮 滚 滚裁 t. :na 口 竺七 - . . 一， r 、 尸. ，“.l， 二 二 七 引 . 竺 甲_ 丁 山 又 _ _ . _ _叨 月竺 一 . ， - 一气， ，一 :. r一 一 ， 1一 匕 把 : 匕 ; 二巴少 二 盅 1 畔井下之二 3 _ 不 灵芬歹琴 只 芭 三d g w .净三 弓 三 丁 _ _ 护 ， 吃、 * 浦， 公。 . ， 内. 口 j 。曰马 .， 司 匕石加d日.口.门山白侧山曲. 口 ， i . - 扮 刁 ， 二 r竺二竺于生 . ， 尸呼丫 早鬓 班 到卜 笠 片 苛 二 二 二 二 长 二二二 刁 r， 尸气 二 尸品 产 甲公留.， 一 一 ， 一 图2 - 1 0自 顶向下二次划分 自 顶向下的划分方法最大的优点就