（模式识别与智能系统专业论文）中文版面分析关键技术的研究.pdf

博士论文中文版面分析关键技术的研究 摘要 版面分析是版面信息处理系统的重要组成部分，旨在将纸制文档内容转化为电子 信息，以便进一步通过版面理解实现版面数字化。版面分析的正确性，直接影响到版 面理解的结果，进而决定着版面信息处理系统输出结果的语义关系和逻辑关系是否正 确。在各种版面文档中，中文版面以其排版形式的多样化，以及汉字的多笔划等特点， 使版面分析远较西文版面为复杂，以致成为当前版面分析技术的瓶颈。因此，对中文 版面分析的研究具有重要的理论意义与实用价值。 版面分析的主要内容在于分析版面的几何结构。由于版面的复杂性，版面分析所 涉及的内容非常广泛。不同类型的版面反映的信息不同，版面分析过程所需的处理方 法也不同。本文对中文版面分析过程中所涉及的若干关键技术进行了深入的研究，主 要包括版面倾斜检测、版面区域分割与识别、版面对象顺序确定，以及表格识别等技 术，其中具有创新性的研究成果主要体现在以下几个方面： l 、基于视窗变换的版面倾斜检测算法 版面在扫描输入时，不可避免地会发生倾斜现象，以致对后续处理产生影响。为 对版面进行倾斜检测与校正，该算法首先选取适当视窗，通过对视窗内容细节部分进 行变分辨率处理，提取相关特征点进行直线拟合，达到检测版面倾斜角度的目的。实 验结果表明，该方法能快速准确地检测出各类版面的倾斜角度，并具有良好的适应性。 2 、基于版面边缘增强的版面倾斜检测算法 考虑到版面复杂度对视窗选取效率的影响，本文又提出了一种基于版面边缘增强 的版面倾斜检测算法。该算法首先对倾斜的图像利用算子进行处理，得到一个图像块， 该图像块的边界信息能较好的表示原版面的边乔信息，然后，用4 方向链码表示该图 像块的边界，从图像块书提取近似直线信息。最后，用最小二乘算法进行直线拟合， 计算版面的倾斜角度。实验结果表明该算法准确度高、速度快而且与图像的内容无关。 3 、基于层次提取的版面分割与识别 版面分割与区域识别是将版面进行空间划分，生成若干包含不同数据类型的区 域。该算法首先将版面划分为图像、图表和文本等多个层次，先对版面中的图像层和 图表层中的主要线段分别进行提取，再利用连通区域法对文本层进行分析，通过文本 “模糊”、边缘检测、段落提取、投影周期性的判断，对图形、表格与文本各部分加 以区分。可以看出，该算法将版面分割与区域识别相结合，提高了算法的效率。 4 、基于有向图的版面对象顺序确定 该算法利用版面对象的空间结构建立空间结构有向图，将版面对象之间的顺序确 定，转换为在有恂图空间进行遍历搜索的过程，通过图的遍历生成遍历树来确定版面 摘要博士论文 对象顺序。实验结果表明该算法有效。 5 、基于面向对象的有向图模型表格识别方法 该算法首先提取空表格中各对象的特征及属性，建立相应表格模型，再对待识别 表格提取特征，采用两级匹配，充分利用其与模型之间特征线及相关特征线的匹配相 似度，结合逻辑关系确定表格类型，达到表格识别的目的，从而提高了表格识别的正 确率。实验结果表明，该方法具有高效、灵活的特点。 最后，本文建立个票据版面分析实验系统，并在此实验系统基础上，对文中所 提出的版面倾斜检测、版面分割与识别、版面对象顺序的确立及表格识别等算法进行 了相关实验。实验结果表明，本文所提方法，在票据版面分析中，实际应用效果良好， 所提方法具有通用性。 2 关键词：文档图像处理，版面分析，倾斜检测，表格识别 博士论文 中文版面分析关键技术的研究 a b s t r a c t l a y o u ta n a l y s i si s 觚i m p o r t a n tp a r ti nd o c u m e n tl a y o u ta n a l y s i sa n du n d e r s t a n d i n g i t i su s e dt ot r a n s f e rc o n t e n ti np a p e rd o c u m e n tt oe l e c t r o n i cd i g i t a li n f o r m a t i o nf o rf i l r t h e r d i g i t a l i z a t i o no ft o t a ll a y o u t ，o u to fd i f f e r e n tk i n d so fd o c u m e n tl a y o u t s ，c h i n e s e d o c u m e n tl a y o u ti sw i t hd i v e r s i f i e dc o m p o s i t i o na n dc o m p l i c a t e dc h i n e s ec h a r a c t e r s t h i s m a k e si tm o r ed i f f i c u l ti na n a l y z i n gc h i n e s ed o c u m e n tl a y o u tt h a nt h el a y o u to fo t h e r a l p h a b e t i cl a n g u a g e s i th a sb e e nab o t t l e n e c ki nd e v e l o p m e n to fl a y o u ta n a l y s i s t e c h n o l o g yc u r r e n t l y t h u s ，t h es t u d yo fl a y o u ta n a l y s i si so fi m p o r t a n tt h e o r e t i c a l s i g n i f i c a n c ea n da p p l i c a t i o nv a l u e b e c a u s eo ft h ec o m p l e xo fl a y o u t , t h es c o p eo fs t u d yo b j e c tf o rl a y o u ta n a l y s i si s e x t r e m e l yw i d e d i f f e r e n tk i n do fi a y o u tr e f e r st od i f f e r e n ti n f o r m a t i o n , w h i c hn e e d s d i f f e r e n tp r o c e s s i n gm e t h o di nl a y o u ta n a l y s i s an u m b e ro fk e yt e c h n o l o g i e so fc h i n e s e l a y o u ta n a l y s i sw e r es t u d i e da n dp r e s e n t e di nt h i sd i s s e r t a t i o n ，w h i c ha r es k e wd e t e c t i o n a n dc o r r e c t i o n ，b l o c ks e g m e n t a t i o na n dr e c o g n i t i o n , d e t e r m i n a t i o no fl o g i c a lo r d e ri n l a y o u ta n dt a b l er e c o g n i t i o n t h ei n n o v a t i o n a la c h i e v e m e n t si n v o l v e dt h e s er e s e a r c h e sa r e a sf o l l o w s ， il a y o u ts k e wd e t e c t i o na l g o r i t h mb a s e do nw i n d o wt r a n s f o r m t h es c a n n e dl a y o u ti sw i t l li n e v i t a b l es k e ww h i c hw o u l dc a u s en e g a t i v ea f f e c to n f o l l o w - u pp r o c e s s i n g ap r o p e rw i n d o w i ss e l e c t e di nt h i sa l g o r i t h mf o rs k e wd e t e c t i o na n d c o r r e c t i o n t h es k e wd e t e c t i o ni sa c h i e v e db yc o n d u c t i n gv a r i e dr e s o l u t i o np r o c e s s i n gf o r d e t a i lc o n t e n ti nt h ew i n d o wa n dl i n ef i t t i n go ft h o s ee x t r a c t e dc h a r a c t e r i s t i cp o i n t s e x p e r i m e n t a lr e s u l t ss h o wt h a tt h i sa l g o r i t h mi s 、i 也g o o da d a p t a b i l i t ya n dc a l ld e t e c tt h e s k e wo f d i f f e r e n tl a y o u tr a p i d l ya n d a c c u r a t e l y 2 l a y o u ts k e wd e t e c t i o na l g o r i t h mb a s e do ne d g ee n h a n c e m e n t c o n s i d e r i n gt h ei n f l u e n c eo f c o m p l i c a t e dl a y o u to nt h ee f f i c i e n c yo f w i n d o ws e l e c t i o n , a n o t h e rl a y o u ts k e wd e t e c t i o na l g o r i t h mi sp u tf o r w a r d sb a s e do ne d g ee n h a n c e m e n t i n t h i sa l g o d t h m ，a l li m a g eb l o c ki so b t a i n e df r o mp r o c e s s i n gi m a g eb yo p e r a t o r t h eo r i g i n a l e d g ei n f o r m a t i o ni sr e p r e s e n t e db yt h a to ft h ei m a g eb l o c k a4 - d i r e c t i o nc h a i nc o d ei s u s e dt os t a n df o rt h ee d g eo ft h i si m a g eb l o c k t h e na p p r o x i m a t el i n ei n f o r m a t i o nc a nb e e x t r a c t e df r o mt h ei m a g eb l o c k s k e wa n g l ei sc a l c u l a t e db yl e a s ts q u a r e sa l g o r i t h ma tl a s t e x p e r i m e n t a lr e s u l t ss h o wt h a tt h i sa l g o r i t h i ni sa c c u r a t ea n dr a p i d ，a n di n d e p e n d e n to f t h e c o n t e n to f l a y o u t 3 塑茎 竖圭丝塞 3l a y o u ts e g m e n t a t i o na n db l o c kr e c o g n i t i o nm g o f i t h mb a s e do nh i e r a r c h ye x t r a c t i o n l a y o u ts e g m e n t a t i o n a n db l o c kr e c o g n i t i o ni st od i v i d e l a y o u t i n t od i f f e r e n t g e o m e t r i c a lz o n e sa n dg e n e r a t e sd i f f e r e n tb l o c k sw i t hd i f f e r e n tt y p e so fd a t a f i r s t l y , t h e l a y o u ti ss e g m e n t e di n t od i f f e r e n tl e v e l so fi m a g e ，f i g u r ea n d t e x t t h em a i nl i n es e g m e n t i se x t r a c t e df r o mi m a g el e v e la n df i g u r el e v e lb ym a t h e m a t i c a lm o r p h o l o g y t h et e x t l e v e li sa n a l y z e db yc o n n e c t i v i t y f i g u r e ，t a b l ea n dt e x ta r ed i s c r i m i n a t e db yt e x tb l u r r i n g ， e d g ed e t e c t i n g ，p a r a g r a p he x t r a c t i n g ，p r o j e c tp e r i o d i c i t ye s t i m a t i n g l a y o u ts e g m e n t a t i o n a n db l o c kr e c o g n i t i o ni sc o m b i n e di nt h i sa l g o r i t h mw h i c hi m p r o v e st h ep r o c e s s i n g e f f i c i e n c y 4d e t e r m i n a t i o no fl o g i c a lo r d e ri nl a y o u tb a s e do nd i r e c t e dg r a p h s p a c es t r u c t u r ed i r e c t e dg r a p hi s s e tu pf r o ma n a l y s i st h es p a c es t r u c t u r eo fl a y o u t o b j e c t s t h i st r a n s f e r st h ed e t e r m i n a t i o no fl o g i c a lo r d e ro fl a y o u to b j e c t si n t ot r a v e r s i n g s e a r c hi nd i r e c t e dg r a p h s ，f r o mw h i c ht h el o g i c a lo r d e ro fl a y o u to b j e c ti sd e t e r m i n e d t h e e f f i c i e n c yo f t h i sm e t h o dw a sp r o v e db ye x p e f i m e n t s 5at a b l er e c o g n i z i n ga l g o r i t h mb a s e do nd i r e c t e dg r a p h t a b l em o d e li se s t a b l i s h e db ye x t r a c t i n gc h a r a c t e r i s t i c sa n da t t r i b u t eo fe m p t yt a b l e f e a t u r ee x t r a c t i o ni sc o n d u c t e df o rt h et a b l eu n d e rr e c o g n i z i n g t a b l er e c o g n i t i o ni s a c h i e v e db yl o g i c a lr e l a t i o n s h i pa n dt w os t a g em a t c h i n gw h i c hm a k e s u s eo ft h em a t c h i n g s i m i l a r i t yo ff e a t u r el i n eb e t w e e nm o d e la n dt h eu n d e rr e c o g n i z i n gt a b l e t h u st h e a c c u r a c yo fr e c o g n i z i n gi si m p r o v e d e x p e r i m e n t a lr e s u l t ss h o wt h a tt h i sa l g o r i t h m i s f l e x i b l ea n de f f i c i e n c y f i n a l l ya l le x p e r i m e n t a ls y s t e mf o ra n a l y s i sb i l ll a y o u ti se s t a b l i s h e dt ov a l i da b o v e a l g o r i t h m s ，s u c h a ss k e wd e t e c t i o na n dc o r r e c t i o n , l a y o u ts e g m e n t a t i o na n db l o c k r e c o g n i t i o n ，d e t e r m i n a t i o no fl o g i c a lo r d e ri nl a y o u ta n dt a b l er e c o g n i z i n ga l g o r i t h m e x p e r i m e n tr e s u l t si l l u s t r a t et h a tt h e s ea l g o r i t h m sa r ee f f e c t i v ea n du n i v e r s a li na n a l y z i n g t h ei m a g eo f b i l l k e y w o r d s ：d o c u m e n ti m a g ep r o c e s s i n g ，l a y o u ta n a y s i s ，s k e wd e t e c t i o n ， f o r mr e c o g n i t i o n ， 4 声明 - 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名： 加7 年7 月7 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名： 砷年7 月7 日 博士论文 中文版面分析关键技术的研究 l 绪论 1 1 课题研究的背景及意义 随着信息技术和计算机技术的发展和普及，人类社会已进入信息时代。各种信息 如爆炸般与日俱增，使人们每天都要接触到来自各方面的大量信息，并对其中有关内 容及时进行加工和处理，例如，文件资料的分类存储、整理和利用，包括各种文件资 料库、档案库的建立、情报资料的检索与通讯以及文本的自动翻译等。 当前信息的主要存在形式有纸质出版物和电子出版物两大类【l 】。前者以纸质材料 为载体，包括图书、报刊等，直接存储并显示传统的文字与字符；后者以其他材料为 载体，包括光盘、磁盘等，以数字化字符形式存储，经计算机处理后，可以按多媒体 方式显示传统的文字、字符。二者相比较，前者在存储成本、记录密度、交换形式、 共享手段、查阅方便性等诸多方面均远落后于后者，因而当前电子出版物日益增多。 但是纸质出版物已有上千年的历史，内容繁多、数量巨大，并将在今后以其便于阅读 与长期保存等特点，而与电子出版物长期共存【2 】。为此，如何对这两种出版物取长补 短，使电子出版物的优越性能在纸质出版物中得到应用，特别是对纸质出版物的内容 数字化，提高其转换过程中的自动化程度与工作效率，已成为有效获取与利用信息亟 待解决的问题。 当前解决这一问题的主要途经是发展光学字符识别技术。光学字符识别，简称为 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 ) ，是模式识别学科中一个开展较早的研究领域， 在模式识别的历史上，具有重要的地位【3 】( 4 】，经过几十年的发展，已取得了很大的进 展。目前在o c r 技术中，单字识别技术已经比较成熟，制约其系统性能的瓶颈主要 是版面分析和版面理解技术，以致直接关系到o c r 技术在日常工作和生活中的实际 应用，例如：名片中的信息提取，信件分拣中的邮政编码识别1 5 】，- 1 - 程图纸中的零部 件信息的存储与修改【6 】，图表文档中的自动分析 7 1 ，图书文档的计算机化文件的标引 与检索【刖，手写体签名的自动分析及个人身份安全性确认f 9 1 ，音乐曲谱1 1 川以及地理信 息图】中的内容识别等。 版面分析和版面理解实际上是特定的图像理解问题，其研究内容涉及图像处理、 人工智能、模式识别和情报检索等多学科的交叉领域。版面分析主要是针对版面的几 何结构，其结果直接影响到版面分割的正确性，进而影响到系统的识别率；而版面理 解主要针对版面的逻辑结构，其结果不仅影响系统识别率，而且决定了系统的输出结 果的语义关系和逻辑关系；二者关系密切，互相依赖。这些都是整个o c r 系统的主 要组成部分【i z l ，是版面分析与处理的关键技术问题，具有重要的理论意义和广泛的实 用价值。本课题的工作主要集中在版面分析方面的研究。 1 绪论博士论文 1 2 版面分析与版面理解概述 1 2 1 版面信息处理系统 版面信息处理系统的主要构成如图1 2 1 所示。 图1 2 1 版面信息处理系统示意图 阿磊习 l兰竺l 可以看出，系统主要由三大部分组成：文档扫描输入，版面分析与版面理解，版 面重构。 第一部分：文档扫描输入。 获取版面图像，输入版面信息处理系统。 第二部分：版面分析与版面理解。 版面分析的主要作用是，将获取的版面图像，根据不同区域特征，划分为图像、 图形、表格和文本等类型，并对图像和表格区域记下区域坐标，以便在版面重构时恢 复原状。 版面理解的主要作用是，对版面分析得到的版面信息按类型分别作进一步处理。 对于图像区域，将其保存为各种图像格式；对于图形区域，通过线条分析转换为矢量 图：对于表格区域，将表格框线和表格内容分别处理，表格框线用制表符表示，表格 内容由识别模块处理：对于文本区域，经过文本切分、特征提取、编码文本识别及识 别后处理等过程，将文本以计算机内码形式存盘，再判断同一版面各文本区域之问的 逻辑次序，以便得到符合原文内容的文本编码。 版面分析与版面理解在实际运行过程中，是密切关联而不是截然分开的。 第三部分：版面重构。 将经过处理的各个区域，按处理形成的文档，重构为r t f 或x m l 等文档格式， 再现视觉上的原版面。 在上述版面信息处理系统中，版面分析与版面理解的效能，直接关系到系统的自 博士论文 中文版面分析关键技术的研究 动化程度、工作速度和版面重构结果。因此，研究准确、高效的版面分析与版面理解 方法，是版面信息处理系统的重点，具有重要的理论意义和实用价值。 1 2 2 版面分析及其常用方法 版面分析是对版面内的图像、图形、表格和文本信息和位置关系所进行的自动分 割、识别的过程。版面分析研究的对象包括，文本版面、表格版面、图像版面和图文 混合版面。版面分析是o c r 系统，进入自动化阶段的首要步骤。版面分析结果直接 影响到整个系统的效能。因此，版面分析方法对提高整个o c r 系统的质量起着十分 重要的作用。 由于版面的复杂性，早期研究版面分析的重点，多停留在如何得到高效的单字识 别上，而对版面上的宏观问题，例如，图像的倾斜、版面区域的分割与区域识别等， 则主要依靠人工干预。随着版面分析自动化程度要求的提高，这种主要依靠人工干预 的o c r 系统已不能符合要求。 另外，对于中文版面来说，它与西文版面有着很大的区别p 3 1 1 4 4 1 1 4 5 1 ，主要体现在， 版面各属性区域的相对位置变化复杂，因此按西文版面做出的版面分析系统，不能完 全适用于中文版面分析的需要。当前，市场上应用于中文版面的o c r 产品，虽然在 单字识别率和识别速度上基本令人满意。但是对中文版面分析的效果远不及西文版面 的分析效果。现有版面分析系统，过分依赖设定的经验阈值进行版面分析，使得系统 存在通用性差、分析结果不稳定等问题。同时，由于不能有效地对同一版面中，各版 面对象之间的顺序进行判断，也影响了版面分析结果。因此版面分析在工作速度、识 别准确性和自动化程度上，急待进一步提高，以适应中文版面的版面分析系统的需要。 版面分析的目的在于，提高文档电子化处理过程的智能程度，自动完成扫描版面 的倾斜检测与校正，版面的区域分割与区域识别，并为识别后的版面重构提供各区域 相对位置等相关信息。现有的版面分析方法通常可分为三类： 1 自顶向下方法 f l n n t ( t o p d o w n ) 1 3 】1 1 4 1 1 1 5 】f 1 6 1 版面分析方法，包括循环投影x y 切分法和r x y c 递归投影法等。这种版面分析方法是，从版面整体出发，通过纵向投影和横向投影的 方法，搜索各区域之间的空白条带，通过这些分隔条带，来确定各个区域的边界。这 种方法虽然简捷易实现，但其前提条件是，版面中必须存在满足一定阂值的纵向或横 向的空白条带。而在实际版面中，由于不可预测的原因，如图像倾斜等对分隔条带搜 索的干扰，可能得到错误结果，故其局限于只能处理无嵌入式矩形版面，而对于复杂 版面，尤其是中文报干廿版面不能适用。 2 自底向上方法 自底向上( b o t t o m - u p ) 1 7 1 1 $ 1 1 1 9 1 1 2 0 1 版面分析方法，包括游程码平滑切分方法、k - 近邻聚类方法、连通区域提取算法切分方法等。这种版面分析方法是，基于图像处理 l 绪论 博二 ：论文 中连通区域的概念，从搜索版面图像中的连通区域开始，先全面获得最底层的版面信 息，并逐步合并具有相同属性的连通区域，从而得到版面分割结果，再利用相关特征 进行区域识别。这种方法的优点是，能完整地获取版面信息，因而能处理复杂版面结 构，但是计算所花费的时间较长，速度较馒。 3 混合型方法 这种版面分析方法比较灵活，体现为以某一种方法为主线同时融合其他方法。利 用此方法开发的版面分析系统，常具有较优越的性能，例如四叉树方法【2 l j 和纹理分析 方法1 2 2 】【2 3 j 等。四叉树方法是，将版面根据四叉树分为不同的区域，利用局部方差的 统计信息判断其区域内属性是否相同。如果某区域内属性不同，则根据纵、横向的投 影特性，将区域切分为四个部分：如果两个区域的属性相同，且与它们的并集属性相 同，则将二者合并；重复上述操作，直到没有切分和合并操作为止。纹理分析方法是， 基于不同属性区域的纹理特征不同的特点，通过自底向上获取版面各区域的纹理特征 进行版面分析，如文本区域中，存在明显的文本行和行间隔条带，并呈规律性交替出 现；表格区域中，存在明显的表格框线，通过合并同纹理的子区域，达到版面分割的 目的，并通过纹理特征进行区域识别。基于此思想的纹理分析方法有，g a b o r 滤波技 术和多层前馈神经元网络，前者通过调整不同的g a b o r 滤波器，以获取纹理区域内的 空域频率和方向特征；后者则基于特定纹理结构判定。此外，还有通过小波分析方法， 自适应的自顶向下和自底向上的版面分析方法等。每种方法虽然都有其特长的一面， 但目前尚无一种具有广泛适用的通用方法。 1 2 3 版面理解及其常用方法 版面理解是从版面中获取文档信息，以形成目标格式文件的过程。版面理解的主 要工作包括：划分版面对象的逻辑关系，确定标题和内容，以及确定版面阅读顺序等。 实际上版面理解是一个层次概念，例如，确定版面中的各对象的逻辑关系，可以认为 是一层理解；将文本图像转换为其a s c i i 编码，也是一层理解；通过对自然语言理解 分析出版面的内在语意，则是更高层次的理解。目前，对一般文档尚不能达到高层次 的理解“。 般而言，版面可以通过其几何结构和逻辑结构来描述。版面的几何结构描述的 是，版面各组成对象及其几何性质，如区域位蹙、大小等；而版面的逻辑结构，则表 达了版面各组成对象之间的相互关系。对版面的理解，可以通过由版面几何结构向逻 辑结构的转化来实现，而这种转换的实现，正是上述高层次理解的难点所在。 因为版面的几何结构与逻辑结构之间的对应关系非常复杂，目前只有当这两个结 构之间的对应关系比较简单而固定时，二者之间的转换才可以较容易地进行。例如， 根据版面中，不同区域的属性及位置关系，可以知道哪些区域代表文章的标题、作者 和摘要等。节百在现实世界中，由于版面的种类纷繁复杂，不同种类的版面具有不同的 4 博士论文中文版面分析关键技术的研究 排版规范，即使是同类版面，其版面也存在一定变化。因此，同一个逻辑结构可以对 应版面不同的几何结构，这就使得由版面几何结构向逻辑结构的转化具有很多不确定 性，难以建立统一的转换模型。 为了降低上述不确定性，现常采用两种方法，一种将所处理的版面类型限制在结 构化版面内，例如，信函、表单、名片、科技杂志等。这些版面的几何结构与逻辑结 构具有比较明确的对应关系，可直接通过建立版面模型，确定版面对象的几何坐标或 版面对象之间的关系【3 1 1 4 1 7 1 ，对各版面对象进行定位。另一种是，为了使系统能处理 具有较大变化的版面，将与版面相关的知识引入系统，以指导版面逻辑结构的分析。 版面上不同区域之间的关系，一般通过不同区域之间的位置关系和排版规则来确 定，目前版面理解的算法大致可分为下面3 种： 1 基于树型分割结果的版面理解算法f 1 3 】【1 4 2 6 1 该算法利用递归纵横分割的结果，直接导出各个不同区域间的顺序关系，即将整 个版面看作是树的根节点，将第一次分割的结果看作是根节点的子节点，再对每个子 节点进行分割，得到子节点相应的子节点，直到不能再分割为止。 2 基于格式描述语言的版面理解算法 版面描述语言是最有效的描述版面结构的方法之一。文献 2 7 1 用形式定义语言 ( f o r md e f i n i t i o nl a n g u a g e ，f d l ) 表示知识规则，并以此为依据进行版面理解。f d l 的基本概念是，将版面的几何结构和逻辑结构都用一系列矩形区域来描述，使版面理 解程序自动解释执行该语言的描述定义，分析版面中逻辑对象及其相互关系。但如何 完整且有效地用f d l 定义版面理解过程中所需的知识，如何设计版面解释程序，仍 然是目前存在的主要问题。 3 基于知识的版面理解算法 2 s 1 1 2 9 1 由于不同的版面具有不同的先验知识，因此可用不同版面模型的形式来定义版面 的先验知识，再使用这些模型将版面表示成可分析的结构，从而利用知识来引导版面 理解。其中，最重要的是确定各种版面的先验知识，也就是确定各种版面的几何结构 和逻辑结构之间的关系。例如，对于书籍、杂志等规则版面，其排版通常是有一定规 则可循的，即使是复杂的版面( 如报纸) ，其标题，图像可能排列无规则，但其文本 一般也是遵照一定的规则排版的。利用这些知识，可以对版面分析的结果进行逻辑结 构描述，即逻辑标注。 1 3 国内外研究现状 版面分析与版面理解技术是随着计算机应用的普及而发展起来的，已有几十年的 历史1 2 5 1 1 3 叭，并成为光学字符识别( o c r ) 技术最早应用的工程领域之一。八十年代 初期，版面分析与版面理解的研究，大多集中于对布局结构较简单的文本版面进行分 割【3 】：到九十年代初，对版面对象进行逻辑标注的研究开始逐步展开【3 2 j 。目前，版 1 绪论博l 论文 面分析与理解技术的研究，已发展到针对各个不同领域的版面，采用不同的技术、多 角度地研究阶段，并逐步得到实际应用。 目前，国外许多大学和研究机构，都在版面分析与版面理解领域建立了研究中心 或实验室，并取得了重要的研究成果。这些研究机构从不同的角度，对版面分析与 版面理解技术以及其各个阶段的算法进行了研究，其中较为著名的机构有： 1 美国纽约州立大学b u f f a l o 分校的文档分析与识别中心，成立于1 9 7 8 年，它 是在版面分析与理解领域中，较早建立的研究机构之一，该中心以数字化的文档作为 研究对象，主要研究方向包括，手写体识别、信封与信件的自动处理、智能字符识别、 表格处理以及日文文档识别等。 2 加拿大c o n e o r d i a 大学模式识别与机器智能研究中心，成立于1 9 8 8 年，该中 心在国际字符识别权威d r c y s u e n 的带领下，在字符识别、版面分析与理解以及 自然语言理解等方面的研究居世界领先水平。 3 德国d f k i 研究中心，成立于1 9 8 8 年，包括五个主要研究小组，其中之一就 是由著名的版面分析专家d r a d e n g e l 领导的信息管理与文档分析小组。 4 美国n e v a d al a sv e g a s 大学的信息科学研究所，成立于1 9 9 0 年，主要任务是 提高版面理解的自动化技术。 5 美国w a s h i n g t o n 大学的智能系统实验室，在版面分析与理解领域，最早开发 了用于o c r 和版面分析与理解算法的c d r o m 版面数据库，该版面数据库不仅包括 各文本、图纸版面的图像，还包括版面中相应对象，如字符、符号和线条等的有关信 息，便于对文档分析与理解过程中的各个算法进行系统、客观的评价。 此外，还有美国m a r y l a n d 大学语言与媒体处理实验室、意大利f i r e n z e 大学和s i e n a 大学合作的实验室文档分析技术研究实验室( d a n t e ) 等。其中m a r y l a n d 大学 与w a s h i n g t o n 大学合作的版面属性格式描述( d a f s ) 已成为一个通用的版面结构表 示方法。至于汉字识别及相应的版面分析技术的研究，主要集中在日本，其系统一开 始就采用大量硬件设备，价格昂贵，再加上日文中使用的汉字只是汉字的一小部分， 与我国汉字具有较大区别。 国内在o c r 领域的研究起步较晚，8 0 年代集中在单字识别领域，到9 0 年代才出 现版面分析的研究。由于中文版面设计复杂，规范性差，版面内文本、图像交错，横、 竖排版交融，各个文本块的字体、字号频繁变化，文本块间的l 日j 隔线、花边线繁多； 再由于汉字本身特点，多数汉字由几部分组成，其偏旁部首容易和标点符号相混淆， 以至对版面区域的分割与区域识别造成干扰。因此，中文版面分析所需解决的困难远 较西文为多，随着中文出版物形式越来越多，版面千变万化，版面分析技术已日益成 为o c r 中的关键问题。为了提高版面分析的正确性，有的中文o c r 系统采用手动干 预，由用户划分版面区域并标示区域属性，或提供常用的版面格式菜单，用户根据具 博士论文 中文版面分析关键技术的研究 体版面分析对象选择，例如，单栏书本、多栏报纸、杂志、手写文稿等，这些对用户 的限制无疑会降低版面分析的自动化程度，与其发展趋势相悖。 目前，在国家高技术研究发展“8 6 3 ”计划、国家重点科技攻关计划、国家自然 科学基金和军事基础研究基金等大力推动下，中文版面分析与版面理解的研究己从汉 字识别发展到全面研究，并出现了一批可供实用的研究成果，例如，复旦大学的字符 识别机，中科院的自动化所的邮政编码识别机，重庆大学的表格自动阅读机，北京邮 电大学的银行票据图像处理与识别引擎，以及清华大学、汉王公司等推出的产品，包 括汉王的尚书、汉王表格自动录入系统、蒙恬o c r 文字扫描辨识系统、清华文通 t h o c r 、清华紫光o c r 等，这些软件在文字识别速度和识别率方面，基本上都能 达到令人满意的效果，并且有些还能支持繁体字的识别，以及表格的识别。但是，在 版面分析方面，往往需要人工干预。例如，为了提高版面分析的正确性，须根据版面 情况，利用菜单选择“报纸版面”或“杂志版面”等，从而使其在实际中的应用受到 限制，版面分析速度、准确性和自动化程度均有待大幅度的提高。 综上所述，目前对版面分析与版面理解技术的研究已取碍了部分成果，其中的扫 描输入文档的预处理和版面分析阶段的研究已广泛展开，并提出了许多有价值的概念 和方法，对版面理解的研究也在不断深入，西文版面分析与版面理解已开始进入实用 阶段，而中文版面分析与版面理解尚有较大差距，有待进一步的技术突破。 1 4 目前存在的问题 目前版面分析与版面理解技术存在的问题，主要有以下几方面： 1 版面的倾斜检测 由于版面分析与版面理解以及字符识别算法等对扫描输入的版面倾斜都很敏感， 所以版面的倾斜检测与校正是版面处理系统中一个重要的预处理内容。一般对倾斜检 测算法的要求是速度快，精度高，而实际上这两项指标是相互制约相互影响的，越精 确的算法，往往消耗时间越多。目前已经提出了许多针对不同版面的倾斜检测算法， 这些算法主要分为两类，即基于统计的方法和基于先验知识的方法。其中基于统计的 方法进行倾斜检测时，不涉及所处理版面的内容，因而具有广泛的适应性，例如投影 轮廓分析法口2 1 3 4 】【3 5 1 1 3 6 】、h o u g h 变换方法【3 7 】p 8 1 等，但运算量大，且精度无法保证。而 利用版面的先验知识的方法，运算的效率和精确度都会得到提高，但应用范围受到很 大限制。例如基于文本行的方法【4 1 1 4 2 1 和聚类方法 2 0 1 9 9 1 1 4 0 1 等。目前还没有一种较为通 用的版面倾斜校正方法。 2 版面分割与区域识别 版面分割是将版面进行空间划分，以得到若干个不同属性的区域，区域识别则是 将分割后生成的区域，根据其所包含的数据类型进行识别。传统的版面分析方法，通 常是将版面分割与区域识别分开，即先进行版面分害如再进行区域识别。分割采用的 l 绪论博士论文 方法和中间数据与区域识别的方法基本无关，因此在区域识别阶段，还要重新生成识 别所需数据，计算量较大。 3 版面理解 版面分析是版面几何结构的生成过程，而版面理解则是将版面的几何结构映射为 逻辑结构的过程。同样的版面布局并非表示同样的逻辑含义，而具有同一逻辑含义的 版面可以有多种布局方式。因此，从几何结构到逻辑结构的映射，不是简单的一一对 应关系。目前多数版面理解方法是，将几何对象直接映射为逻辑对象，这只适用于己 知的、简单的版面布局与逻辑结构，对于较为复杂的版面尚无能为力。另外，在研究 中，对版面几何结构生成方法的讨论较多，而对于版面理解的注意则较少。 4 表格识别 在版面分析与版面理解领域中，根据所研究对象的种类不同，产生了多个研究分 支，表格版面分析是这些分支中十分重要和典型的一个。由于表格的结构化形式，表 格识别的主要工作在于对表格类型进行识别，并对表格对象进行划分，包括标题单元 及填写单元等，单元通常由纵横直线相交的矩形框构成，需要用户填写的内容可能是 打印机打印的或手写的汉字、数字或符号等，因此它是线图形、印刷体汉字、数字、 符号及手写汉字、数字、符号等多项识别技术的综合运用，目的在于提取和识别表格 单元中的有效信息。在实际应用中，表格种类繁多，在进行表格版面分析与版面理解 时，特征的选择、非线性因素的影响和填写时人为因素的介入等，都成为表格版面处 理的难点，所以耳前尚未形成通用的解决方法。 1 5 本文研究工作概述 据前所述，版面分析与理解的过程，可归纳为四个处理层次( 如表1 ，5 1 ) ，各 层次包含有各自待解决的关键技术。本文对其中预处理层和分析层所涉及的，版面倾 斜检测与校正、版面分割与区域识别、表格识别等技术，进行了深入的探讨和研究， 主要工作和研究成果如下： 1 提出了一种基于视窗变换的版面倾斜检测方法。 该算法首先选取适当视窗，通过对视窗内容细节部分进行变分辨率处理，提取相 关特征点进行直线拟合，达到检测版面倾斜角度的目的。实验结果表明，该方法能快 速准确地检测出各类版面的倾斜角度，并具有良好的适应性。 8 表1 5 1 版面分析与理解的四个层次 处理层次( 由低