（模式识别与智能系统专业论文）文档图像中无线表的自动处理.pdf

摘要 摘要 表格自动处理是文档图像处理领域的研究热点之一，既有重要的学术研究意 义，也有广泛的应用价值。针对有线表的处理技术已经趋于成熟，但是针对无 线表的自动处理技术尚存在诸多不足，难以满足现实应用需求。 本文总结了无线表自动处理技术的研究成果，建立了完整的无线表描述机制 与处理系统结构，实现了针对无线表的自动定位、结构分析和格式重现。 本文利用启发式规则和文本块竖直聚类思想，提出稳定的无线表自动定位判 断准则和处理方法。基于表格结构描述机制对无线表进行良好的结构描述与分 析，并实现了对无线表结构的重现和格式转化。 本文实现了完整的无线表自动处理系统，并基于真实样本集进行性能评测， 处理精度达到9 0 ，可满足各类文档图像处理的应用需要。 关键字 文档图像理解、表格特征、表格逻辑结构、表格版面结构 a b s ”a c t a b s t r a c t t h et a b l ea u t o m a t i cp r o c e s s i n gi sa ni m p o r t a n tr e s e a r c hf i e l do fd o c u m e n ti m a g e a n a l y s i sd o m a i n ( d i a ) i th a sn o to n l y a ni m p o r t a n tm e a n i n go fs c i e n c eb u ta l s o b r o a dp r a c t i c a la p p l i c a t i v ev a l u e t h ep r o c e s s i n gt e c h n o l o g ya b o u tt h et a b l e c o n s i s t i n go ft a b l el i n e h a sg o o de f f e c t ，b u tt h ea u t o m a t i cp r o c e s s i n gt e c h n o l o g y a b o u tt h et a b l ew i t h o u tt a b l el i n es t i l lh a sm u c hs h o r t c u ta n dc a nn o ts a t i s f yp r a c t i c a l n e e d t h ep a p e rs u m m a r i z e dt h ep r e v i o u s l yw o r k sa b o u tt h ea u t o m a t i cp r o c e s s i n go f t a b l ew i t h o u tt a b l el i n e ，t h e ns e tu pac o m p l e t ed e s c r i p t i o nm e t h o do ft a b l es t r u c t u r e f e a t u r ea n dap r a c t i c a l p r o c e s s i n gs y s t e m ，t h es y s t e mr e a l i z e dt a b l ea u t o m a t i c i d e n t i f i c a t i o np r o c e s s i n g ，t a b l ed e c o m p o s i t i o np r o c e s s i n ga n df o r m a tc o n v e r s i o n i nt h ep a p e r , w ep r o p o s e dar o b u s tt a b l ed e t e r m i n a n tc r i t e r i o na n da l la u t o m a t i c p r o c e s s i n gm e t h o dw h i c hu s i n gh e u r i s t i c sr u l i n ga n dt h em e t h o do fh i e r a r c h i c a l c l u s t e r i n g b a s i n go i lt h et a b l es t m c t u r ed e s c r i p t i o nm e t h o d ，w ec a ne f f i c i e n t l y d e s c r i b et h et a b l es t r u c t u r ea n dd e c o m p o s et h et a b l e t h ep a p e rr e a l i z e dat a b l ea u t o m a t i cp r o c e s s i n gs y s t e m ，t h es y s t e mt a k e sar e a l i t y g r o u n dt r u t hs e t sa si n p u ta n do b t a i n s9 0 c o r r e c td e t e c t i o nr a t e s i tc a ns a t i s f yt h e p r a c t i c a ln e e do fv a r yk i n d sd o c u m e n ti m a g e k e y w o r d s d o c u m e n ti m a g eu n d e r s t a n d i n g ，t a b l ef e a t u r e ，t a b l el o g i c a ll a y o u t ，t a b l ep h y s i c a l l a y o u t 南开大学学位论文电子版授权使用协议 ( 请将此协议书装订于论文首页) 论文灸弼1 虱像丰王j 毛毒南区自丢i 盍b 理 系本人在 南开大学工作和学习期间创作完成的作品，并已通过论文答辩。 本人系本作品的唯一作者( 第一作者) ，即著作权人。现本人同意将本作品收 录于“南开大学博硕士学位论文全文数据库”。本人承诺：已提交的学位论文电子 版与印届0 版论文的内容一致，如因不同而引起学术声誉上的损失由本人自负。 本人完全7 解i 窟珏太坐国盘焦差王堡在：焦田堂焦i 佥塞曲簧堡盘逵。同意 南野大学豫书馆在下遮蓖瘟内免费使用本人作品的电子舨： 本作品呈交当年，在校园网上提供论文目录检索、文摘浏览以及论文全文部分 浏览服务( 论文前1 6 页) 。公开级学位论文全文电子版于提交1 年后，在校园网上允 许读者浏览并下载全文。 注：本协议书对于“非公开学位论文”在保密期限过后同样适用。 院系所名称：求鹾镭毹缉定卿 作者签名：球解 学号：口2 0 2 9 矿 日期：z - o c 年6 月f 日 象经作卷，导师嚣蕞 蜘全支繇 内容目录 图目录 图1 1 表格自动处理系统流程5 图2 1 设计风格良好的表格图像实倒7 图2 2 无线表表格版面结构定义9 图2 3 带有表格标愿和注释域的无线表表格实例1 0 图2 4 表格版面结构描述1 l 图3 1 文档图像表格定位算法基本流程1 7 图3 2 原始文档图像和b l o c k 抽取结果1 8 图3 3 平均行高和平均行间距统计直方图1 9 图3 4 文本b l o c k 行位置关系1 9 图3 5 块间距离示意图2 1 图3 6 文本块竖直近邻聚类规则 图3 7 表格结构的文本块捧列2 2 图3 8 文本块竖直聚类算法处理过程示例2 3 图3 9 竖直聚类算法不能处理的几种版面结构2 3 图3 1 0 列候选表格区域竖直投影2 4 内容目录 图3 1 l 聚类处理结果实例2 5 图3 1 2 表格行列特征参数2 5 图3 ，1 3 紧凑形版面结构处理实例 图3 1 4 无线表结构分析和表示数据流示意图3 3 图3 1 5 线条交点的类壅及描述幽】3 4 图4 1 系统结构图。” 图4 2 无线表白动处理结果实例 图4 3 不能处理的无线表样张实例 附录；表格型文档版面结构分类实倒4 9 内容目录 表目录 表3 1线条交点方向属性3 4 表4 1 无线表定位测试结果统计4 0 表4 2 无线表结构分析测试结果统计4 0 v i l 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务：学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：张褥 p f 年石月f 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名t学位论文作者签名： 解密时问：年 月日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：张辉 2 万年6 月 目 第一章前言 第一章前言 第一节本文研究背景 长久以来，人类信息传承的主要方式是通过各种各样的文档记录来完成的， 随着时代的发展，承载这些信息的介质也在发生着变化，从最初的岩石、竹简 到皮革、纸张，再到磁带、光盘等电子介质，其中纸介质一直担负着主要的角 色，其数量以惊人的速度增长，然而这些以纸张作为载体的文档在保存、检索、 修改和传播等方面都有着明显的困难。随着计算机技术的发展和在生活中的广 泛应用，人们开始考虑采用计算机识别技术将其转换成相应的电子文档保存， 以便于在大量的文档中能快速检索到需要的信息并加以利用，这即是文档图像 分析( d o c u m e n ti m a g ea n a l y s i s ) 技术。文档图像分析( d i a ) 是提取和恢复数 字图像中的信息及其结构特征的理论和工程研究，目的是将文档图像信息转变 成计算机可理解、编辑和检索的信息并加以保存。d i a 的主要理论基础是数字 图像处理( d i s t a li m a g ep r o c e s s i n g ) 和模式识别( p a a e nr e c o g n i t i o n ) 等多项技 术，尽管早在1 9 世纪就有关于光学字符识别的专利提出，但随着计算机的发展 和d i a 理论基础的成熟，d i a 实际上出现于2 0 世纪5 0 年代，而作为一个独立 的研究领域也只是近2 0 年的事情。 表格作为一种最常见的通用数据组织和表达形式，由于具有强大的数据组织 功能以及便于查询、统计、计算的能力，使其大量存在于各种各样的文档之中。 表格可以作为独立的文档存在，也可以作为内容组成部分，与段落、图形、标 题等组织在一起，形成复杂的文档结构，因此在利用d i a 技术进行文档转换的 过程中，不可避免的要对文档图像中的表格进行检测分析和相应的转换。 文档图像中的表格自动处理研究兴起于最近l o 余年，最早是tw a t a n a b e 和 他的同事在1 9 9 0 年前开始了这方面的研究，并于1 9 9 6 年发表了利用分类树来 进行表格版面结构识别的论文i l l 。同年，加拿大滑铁卢大学的x i n x i nw a n g 博士 也在其博士论文中提出了表格逻辑结构的描述模型 4 1 。如今文档图像的表格定位 与分析已经发展成d i a 领域中的一个独立研究方向，世界各地很多研究者都在 进行表格自动处理方面的研究，如贝尔实验室、华盛顿大学、纽约r e n s s e l a e r p o l y t e c h n i c 研究所等。 第1 页 第一章前言 d ，l o p r e s t i 和g n a g y 【2 】【3 】按研究对象的不同将文档图像中的表格处理研究划 分成5 个层次：像素级( p i x e l s ) 、原型级( p r i m i t i v e s ) 、结构级( s t r u c t u r e s ) 、 文档级( d o c u m e n t s ) 和文档集合级( c o r p u s ) 。它们分别针对不同的研究对象， 采用的研究方法也有很大区别，对于一般的文档图像表格处理系统来说，其研 究范围至少要涵盖了前四级。近年来针对如s g m l x m l 、t e x t ( a s c i i 码) 等格 式的电子文档的表格定位、分析和信息提取也有很多的研究出现体l 【叭，由于其处 理对象的不同，电子文档的表格定位是基于字符进行的，跨越了像素级，在 定程度上说已经超出了d i a 领域的研究范畴，但它们都是针对表格结构进行的， 有着相似的处理目标，因此两者的研究很多是同时进行的，其研究成果也可以 同时用于这两种应用。此外表格评测机制的研究由于与表格定位、分析的研究 密不可分，国内，外也有不少的研究成果 5 1 6 1 7 1 1 3 8 。表格自动处理的研究发展到 今天，已经出现了一些可以实际应用的表格处理系统l i h ，在文档图像处理技 术、表格结构定位、表格结构分析和表示以及表格结构的识别等算法研究领域 上取得了大量的成果。 然而，目前进行的研究中很多是针对一些特定表格或结构大致已知的表格类 型进行的研究，通过检索已发表的相关论文文献资料可以看到，对通用表格识 别进行的研究中还存在着很多未能克服的问题，现有的d i a 文档图像处理工具 对通用表格型文档的处理结果也存在着许多无法让人满意的问题，因此构建针 对一般的表格图像的自动处理系统，并在此基础上逐步研究和艇决上述问题是 当前表格自动处理研究的基本方向。 t 2 1 表格定义 第二书文档图像中的表格分析 当人们看到表格型文档图像时，无论什么样的表格，他们都可以很容易的指 出表格区域并能理解其各种数据关系，但如果要他们为表格下一个准确清晰的 定义，却又是非常困难的，这是由于人在使用表格文档的时候，使有了很多先 验知识，两这些知识又是基于庞扎的经验和实例两来的，要想从其中总结出一 个具有典型共性的东西具有很大的难度。然而，在进行表格自动处理研究过程 中，我们要面对类型繁多的表格对象，利用计算机进行表格识别处理是不可能 麓2 页 第一章前言 通过建立庞大的先验知识库来实现的，所以在进行通用表格自动处理研究前， 我们必须首先建立一个准确的概念，也就是说需要明确什么是表格，表格具有 那些特征。 在英文牛津词典中，表格( t a b l e ) 的定义是：a na r r a n g e m e n to fn u m b e r s ， w o r d so fi t e m so fa n yk i n d ，i nad e f i n i t ea n dc o m p a c tf o r m ，s oa st oe x h i b i ts o m es e t o ff a c t so rr e l a t i o n si nad i s t i n c ta n dc o m p r e h e n s i v ew a y ，f o rc o n v e n i e n c eo fs t u d y ， r e f e r e n c e ，o rc a l c u l a t i o n 这个定义指出表格是一种明确和紧凑的数据排列，目的是用清楚和便于理解 的方式表达信息及信息问的关系，以便于学习、参考、检索和计算。 d l o p r e s t i 和g n a g yt 2 1 也给出了一个表格定义：用来表述信息的2 - - d 数据 集合；数据沿着至少一个轴线呈重复排列的规则结构；单元数据类型由水平或 垂直索引决定。 不难看出虽然这两个定义的表述方式不同，但都指出了表格存在的共同的特 性；存在着最小数据单元：这些单元具有特定的排列方式；单元之间存在着一 定的逻辑联系；表格通过数据单元和单元间的联系共同表达信息。 1 2 2 表格特征 从表格定义中我们可以得出一些表格特性的简要描述，然而在我们开始研究 之前，我们仍然有必要从三个方面详细明确一下本文所关注的表格特征： 1 表格内容是由一些相互关联的表格基本单元构成。这些单元可能是数字、文 本、符号、图表或者数学公式等，其中一些基本单元( e n t r i e s ) 构成表格主体 ( b o d y ) ，另些辅助单元( 1 a b e l s ) 用来说明这些基本单元。 2 表格单元是以阵列的方式出现，以行列结构来表述基本单元之间的联系。辅 助单元通常是用来索引位于行( 列) 中的基本单元，不同的行( 列) 之间有明 显的分隔，行( 列) 单元具有数据类型一致性的特点。 3 表格的目的是用一种紧凑的组织方式表达信息，并能易于理解、检索、比较 和计算，而这个目的是通过表格的组织形式来实现。因此一个良好的表格首要 的条件是组织形式易于理解，单元排列格式清晰。 在明确了表格定义和表格特征后，我们下面的研究都将依据表格的这些特征 来进行。 第3 页 第一章前言 1 2 3 表格分类 文档图像中的表格可以依据不同的分类标准进行各种各样的划分，在这里我 们以文档图像中表格识别处理为出发点，按照表格的表现方式将其划分为两大 类：有线表和无线表。 有线表：利用文字和直线在二维平面上的不同位置关系将文字所携载的信息 按一定形式和逻辑意义进行划分的表格文档【39 1 。有线表框架是由各种线条表 示，如横线、竖线及少量的斜线等，线条构成不同表格单元之间的边界。 无线表：表格单元通过整齐的排列规则，并利用文本间的空白区域在二维空 间上形成具有典型表格特征的一类表格文档。 从上述定义中我们可以看出，区分这两类表格的一个明显特征就是表格单元 分隔符的表现形式，而正是这种不同的分隔方式构成了表格定位和结构分析算 法研究的不同出发点，本文随后对此将进一步进行阐述。 第三节表格处理基本渣程 图1 1 给出了一个典型的表格文档自动处理系统流程，右侧为处理流程所采 用的对应处理技术。 在一个表格自动处理系统中，最主要的步骤在于表格区域定位和表格结构分 析两步，大部分表格文档处理的研究都是集中在这两个环节中。其中表格区域 定位是对文档中可能存在的表格区域进行检测和定位，利用系统前几步所获取 的信息，如线条、连通体和文档图像背景等信息。利用版面特征并采用一定的 启发式规则来定位并区分表格和文档中其它元素，如文本、图表、标题、线条 等。表格结构分析则是对已定位的表格区域进行版面结构和逻辑结构的分析， 通常是利用预先建立的表格逻辑结构模型，采用模型驱动的方法对表格区域内 的数据单元进行分析，获取表格的版面结构和逻辑结构，并恢复表格区域内数 据单元原有的相互关系，最后采用一种易于计算机理解的存储方式来保存表格 分析结果。 第4 页 第一章前言 图1 1 表格自动处理系统流程 第四节本文的研究范围和目的 目前表格处理研究多集中在对已知表格版面结构的定位和分析研究上，采用 大量复杂的启发式规则，但对般表格文档结构中的普通表格缺乏一个比较有 效的分析处理机制，尤其是对于缺乏先验知识类型的表格文档：此外文档图像 中存在着大量的类似表格结构的文档结构，如多列文本结构、图表等，以及文 档图像生成过程中由于各种嗓声干扰导致图像质量低下等原因，也一直影响着 对一般表格结构的区域定位和结构分析处理的效果，这些问题都亟待于解决。 本文关于文档图像中的无线表自动处理系统的研究是建立在南开大学机器 智能研究所开发的o c r 识别软件包r t k 的基础上，并以其作为研究平台来进 行。r t k 目前含有针对一般有线表格的表格定位和分析模块，它是利用对文档 图像中的线条检测来实现表格定位和分析的，不具有处理含有表格线条分隔符 第5 页 第一章前言 不全的表格或无线表的表格型文档图像的能力，同时由于处理过程中过于依赖 线条分隔符，导致处理结果存在一些不足。 基于上述认识我们界定本文的研究范围和目的： 1 研究对象为印刷体表格型文档图像中具有表格特征的一般无线表表格及 其结构。对于利用线条分隔方式构成的具有复杂版面的有线表和一些特殊表格， 诸如元素周期表、表格元素为图片及一些特定财务报表等，虽然它们也具有一 般表格特征，但本文不将其列为研究对象。 2 利用表格结构所具有的行列特征，对文档图像中文本块的版面排列规则 进行分析，研究并提出一个完整的、健壮的无线表自动定位和结构分析算法流 程，该算法将能够处理具有尽可能多的版面形式的表格型文档。 3 针对利用文本块排列方式来表现表格特征的表格结构建立一个简单、有 效的表格结构描述方法，并基于该方法提出的约束条件进行无线表定位和结构 分析处理，提取并理解表格逻辑结构。 4 针对r t k 的处理流程，设计适用于r t k 的无线表表格处理模块，建立 一个完整的、可实用的无线表自动处理系统，并与原系统良好兼容( 与r t k 中 原有线表处理流程的良好兼容和与r t k 中o c r 处理流程的良好兼容) 。 5 本文提出并实现的表格定位和结构分析算法也可以用于对基于a s c h 字 符的各种电子文档中的表格结构进行区域定位、结构分析和理解。 第五节本文内容组织 本文第二章中将首先介绍通用表格逻辑结构描述模型的研究现状，在此基础 上提出了一个简单、直观的表格版面结构描述方法，随后提了基于连通体级上 进行表格自动处理所需要的一些约束规则，并详细分析了无线表自动处理的机 制和方法； 第三章主要介绍我们提出的基于文本块排列和表格版面结构分析的表格定 位算法，并给出了一个详细的表格定位和结构分析流程； 第四章介绍我们基于r t k 平台上的无线表自动处理系统的实现及其处理结 果实例，然后在一个小测试样张集基础，介绍了该系统的测试结果，并就系统 存在的不足进行了详细的分析，最后提出了系统改进的方向。 第五章则简单总结了系统的实现过程和目前所处的研究现状。 第6 页 第二章无线表的结构描述和自动处理方法 第二章无线表结构描述和自动处理方法 第一节引言 一个设计良好的表格必须具备的功能要求是：读者能够在最少的指导下快速理解和使 用表格；在查找过程中能够很容易的准确定位所要查找的信息位置；在比较和解释过程中 能够避免大量时间耗费在计算过程中。从表格定义可以看出表格是由一组数据和一系列数 据关系构成，而一个风格良好的表格主要是通过合理的设计来实现对表格数据间关系简洁 恰当的表述，图2 1 给出了一个具有良好设计风格的表格图像实例。然而同样的数据关系 在表格中可以用不同的版面结构来表示，如不同的行列布局和不同的排序方式等，不同逻 辑关系的表格，也可能有着相似的版面结构，因此在表格自动处理过程中，全面和良好的 表格结构描述方法有着至关紧要的作用，通常它定义了要处理的表格所必须具有的结构特 征，同时也提出了表格定位和结构分析过程中所适用的一系列的约束规则。换句话说就是： 在没有合理的表格描述方式的帮助下，表格处理只可能提取表格单元数据及表格元素位置 信息，却无法获得表格元素间的关系信息，进而无法实现对表格结构的理解、检索、编辑 和计算。 c o m p a r i n gs e l e c t e df r o z e nd e s s e r t s 4 翻t _ c 蕾( i b o l i l 啊证钾呻p ) w 0 1 1 1 h - 7 8 洲o 。f 协a r 肿c a i 埘j o f r 1 2 t si n 0 蠲k t 商蝴g i d d u k h d 诅k b c n j 州u 毒h lm 憎r 碡c 哪l e t = d 眦 e s k i m o p kc b c 如- = e n d h 锥ib c 王，删 f r 0 2 1 r u l l h u i i t y o l u n h ，s m l w l x r y ih v 35 0 z ) h 啦觚础1 扣簟峨c h o l - 王。讲v l n i l l a h c i d i l h 嘏l y q n l v # , n i l l l h c i d l i i j 摹1 1 f 忡晔“扣i i l c b o c o i k _ 哪s 瑶 s i m 出刊删r c b o c o l e l cc h 砸 s i m p & c 升砷咐u 曲l tv l m * l l l l 啊c i | 。 - k s i c w s c m u r m 廿n o h l n u i _ m h r n 僦h s u ：v t o o 叫f 幢d e 印c h o c o l k kr l l o l l l ，* e t o l u l i t t v l m l l “d i p p e d i n c i 肿嘶1h o 2 沁) t o f u l b u tl i t t 埘f b e n 0 rm o c b e s k i mm 波p o l y d c x l r o c ( c l l u l 州 n mm i l ki “m c r e a m g l u r e s k i mm i l k c e l l u l o s e m a h , x l e x l n n s b mm i 艮i k 帆s0 u ”卫u n s k i m m i l k i i o w1 0 洲e c 哪m s k i mm i l kc m m 1 u a ri m s k i mm - i kl o c u s tb c 柚g u m 1 ：u = ug u 丌， s k mm i l k s l m p 概t h f u b | l i m t c i mm i l k ，n s w is i m p k m ，i ，m i l ”t w h o l e m i l k c n m - l 【m u - e u - n s k i mm i l k m = h o d e x m n g u 盯b 岍 t 口缸g u m _ t d f ug u m s m ，n h m * l l c n - d t 抖嘲f r o z e ny 哩”n ，c b o c o l e t t 2 0i硼 s k i m m i l k d 0 “d l o w h ly o v a n 1 l = 1 2 9o l i ids k i m m i l k 代b y m m ，v m d l l e 1 1 0 i 8s k i m m i l k 图2 1 设计风格良好的表格图像实例 g u i f # u mc = t o hb e * * ng u m c c l l o k s t t u 。g “。 m j 【岫x 伽n i v d t x h o 蟑 表格结构描述方法可以分为表格版面结构描述( 物理结构) 和表格逻辑结构描述模型。 一般而言，表格版面结构主要是描述文档图像或文本文件中的表格区域定位信息和几何特 征的集合，如分隔符定位信息、分隔符交点定位信息、字符定位信息、相关文本信息( 如 第7 页 。勰砧d m ”o 喀i h o 雒m o 吣，0 4 4 o 3 d 8 0 婚竹瑚mm胁渤mm脚帅 第二章无线表的结构描述和自动处理方法 标题、注释等) 、以及其它符号的定位信息和它们对应的几何信息；表格逻辑结构则描述 了表格内部各组成元素的类型和表格构成方式的最小关系集，如线条分隔符类型、线条交 点类型，表格索引关系( 行索引、列索引、行列复合索引等) ，表格区域类型( 表格标题、 行头、列头、表格单元等) 、表格维数关系、表格内部各区域间关系( 如邻接关系、包含 关系、单元拓扑关系等) 、表格格式属性等，通常表格逻辑结构描述模型不包括具体的文 本内容信息。表格逻辑关系和表格版面结构之间存在着l ：n 的关系，即有限的表格元素可 以构成多个不同的版面结构的表格，而n 具有不可计算性，x i n x i nw a n g 在他的博士论文 中证明了这是一个n p 一完全问题【4 】。 针对表格描述方法而言，很多学者提出了不同的表格结构描述模型，如e g r e e n 和m k r i s h n a r n o o r t h y 提出了基于标记方法来分析表格结构的描述模型【1 “，o s a m u h o r i 和d a v i d s d o e r m a n n 则提出了基于边框进行分析的表格描述模型1 1 4 1 ，tw a t a n a b e 提出了采用分级决 策树描述的表格结构描述模型川，c p e t e r m a n l l 3 】也提出了自己的表格描述模型，但公认为 最为完整的表格逻辑结构描述模型是x i n x i nw a n g 博士在其博士论文中提出的表格逻辑结 构模型【4 】。w a n g 的表格逻辑结构描述模型可以分为三个部分：抽象的表格索引关系；行列 及区域位置的拓扑定义；字符、分隔符类型和版面约束的格式属性。这种模型定义优点在 于简单合理，概念划分清晰，通过逻辑结构而不是表格单元来描述模型，便于实现对表格 的编辑处理。虽然w a n g 的模型能够很好的描述表格逻辑结构，却没有对表格物理结构( 表 格版面结构) 进行描述，也没有对表格相关文本进行定义，如注释、标题等，同时不能对 可能存在的子表结构进行处理。 史广顺博士在其博士论文中提出了一种针对表格版面结构的描述口8 1 ，该定义认为表格 版面结构是由一系列表格图像元素和在这些元素上的关系组成，表格元素主要由数据分隔 符( 黑线条和白色空白) 、数据内容、版面信息( 物理位置和几何大小) 组成，位于元素 上的关系则由相邻、相交和包含三种关系构成，表格的基本组成单位是简单区域。基于这 种简单区域的思想则可以比较好的对表格版面结构进行表示和说明。 第二节无线裘的表格结构描述 2 2 i 无线表表格结构描述方法设计 对于表格结构描述方法而言，其性能好坏取决于它所描述的表格属性是否合理、对文 档图像中其它元素的排它程度及使用的对象和关系的可靠性，同时表格描述方法的建立必 须有助于实现两个主要的目标：表格定位和结构分析。对于一个满足上述条件的表格描述 方法而言，它必须建立在对大量各种形式和来源的文档图像集合的观察基础上，如统计学、 社会学、科技文献和商业文书等各方面的书籍、学术论文、报纸和杂志等，同时要求能够 第8 页 第二章无线表的结构描述和自动处理方法 全面的描述这个文档集合中的表格特征。 因此在建立表格结构描述方法时，应该遵循以下原则： 表格结构描述方法应尽可能的解释更多的表格类型。 表格版面结构描述的基本元素是基于像素的连通体和连通体的集合，不涉及表格特定 的内容信息。 表格版面结构描述方法必须是计算机可理解、计算和判别的，并可以基于该描述来恢 复表格版面结构。 表格版面结构必须体现表格逻辑结构的特性，而又独立于逻辑结构。 必须满足大批量普通表格结构自动处理的工程应用需要m l 。 基于上述原则，我们从已有的大量文档图像样张中，挑选出大量包含表格实例的样张， 通过详细的观察并结合r t k 已有的研究成果，在此基础上针对无线表特有的版面结构特征 提出了一个简单的无线表表格描述方法及相关约束规则。 2 2 2 无线表版面结构定义 参考文献3 8 1 对表格版面结构做了一个比较完整的定义，并利用树型结构对表格版面结 构进行了描述，该定义主要是利用数据分隔符作为版面结构分析的依据，因此本文针对无 线表给出了个基于文本块排列的表格版面结构定义，如图2 , 2 所示。 列头 子列头 k 膏 嘲o f n t q b - 器k 。 行琴弼鬻酬b n d , a ， 溜勰黼。器。椭 1 4 9 2 ：1 0 黜 ：器臻+ l a t i 蝴 ! h h 1 4 08 砷m b 一鼬t 1 3 - b 棚d 。 耵l 哪a 节她州 1 弛a 叫 1 3 08 n w2 1 3 0h 帅 1 2 7e 轴 b 9 9 o 7 7 7 7 32 8 铘- “行 数据单元 、列 图2 2 无线表表格版面结构定义 1 2 1 2 b o 1 0 o 域 很多表格具有一些附加的说明区域，如标题和注释，它们是从属于表格的附属内容， 用来对表格进行补充说明的，通常位于表格体的顶部或底部，对表格内部的版面结构和逻 辑结构没有影响，因此，在进行表格版面分析过程中，本文将不考虑这些区域的影响，如 图2 - 6 是一个带有表格标题和注释的表格实例。 第9 页 黧瓣 第二章无线袭的结构描述和自动处理方法 ii n d i v i d u a lt i c k e to p t i o n s l f t 衰格标题 a d u l t c h i l d u n l w 粥霜! ；t u d i o sf l o r i d a $ 3 2 b 6 2 65 0 ( 3 9 y 幅) se=world$28s52 4 ，5 0 ( 3 。9 y 哟 m a r d i c 酾j 摹2 b 9 5 1 9 9 s ( 3 1 y r s ) f o r tu ber审$28951 9 9 s ( 3 11 y r o k i n 9h m r y sfeast$289519 9 5 ，3 ，y r s ) c a r u s o sp |lace$28951 9 9 5 r 3 11 y r s ) w t e rm n l a s 1 6 9 51 49 5 ( 3 1 2 y r s ) c h u r c hs t r e e ts 疆t l o c t s 1s8 s1 0s s ( j 12 y r t ) c y p r e s sg a r d e n s3 2 1 s 0 t 4 0 0 ( 3 一娜) m e d i e v a l t i m e s d i n n e r t h e a t f t $ 2 7 o o1 90 0f 3 1 2 y r s ) a r a b i a n n i g h t s d i n n e r t h e a t r e $ 3 0 0 0 1 8 1 4 ( 3 1 1 y r s ) b u s c hg - e n st h ed m c o n t i n e n t $ 2 75 02 7 5 0u n d e r3 匝堕曼要里至夏蜜囊曼巫亘曼垂k 表格注释 惮。 图2 3 带有表格标题和注释域的无线表表格实例 本文部分术语及定义沿用参考文献【38 j 的描述，如数据分隔符( d a t as e p e r a t o r ) 、简单区 域( s i m p l e r e g i o n ) 、内容块( c o n t e n t b l o c k ) 、框架线( f r a m e l i n e ) 和网格矩阵( g r i d m a t r i x ) 等，此夕 弓i 进了分组( g r o u p ) 、子行( 列) 头( s u b - r o w c o l u m nh e a d e r ) 和域( r e g t o n ) 的概念。 分组：是由多个具有相同性质的行( 列) 构成的行( 列) 的集合，在版面结构上表现 为相邻，并具有一个公共的行( 列) 头，我们用一个序列表达式表示为：( g r o u p ，m e m b e r s e t ) ，如图2 2 中表格含有的列分组：( c a b i n ， d b i ，s l ；i ) ，对于没有分组的行列结构 我们可以用( l a b e l ，p ) 表示。 子行( 列) 头：当分组的指示域位于表格行( 列) 头中，我们称分组头为行( 列) 头， 如c a b i n ；分组成员行( 列) 头为子行( 列) 头，如d b i 和s g i 。 内嵌行头( e m b e d d e dr o v eh e a d e r ) ：由于无线表的排版格式限制，在对行进行分组时， 行分组头可能会嵌入进表格体内，如图2 2 中的分组行头s a i l ，这种内嵌的分组行头同 表格行的一个显著区别在于位于单独的一行，本文定义这种分组行头为内嵌行头。 域；多个相邻的数据单元构成的矩形区域。 表格版面通常是在二维平面上以行列结构排列来表现的，但表格的逻辑维数却可以是 一维、二维或多维的，如图2 - 2 所示的表格结构，由于有分组的存在。在逻辑维数上则表 现为多维结构特征。 2 2 3 无线表表格结构描述方法 由于表格自动处理系统的研究是利用r t k 作为平台进行的，从系统的角度出发，我们 需要考虑系统原有的处理机制和表述方式，因此本文中基于文本块排列的表格版面结构描 述方法考虑了对原有系统的兼容。我们采用网格矩阵作为我们保存表格版面结构全局与局 第1 0 页 第二章无线表的结构描述和自动处理方法 部信息的基本方式，也用于作为表格版面结构信息的输出接口，如图2 4 所示，本文可以 采用树型结构来对无线表版面结构进行描述。 说明：t a b l e ：衰格根结点 v 晒：竖l 赣嚣分隅柑( 寰格整直框架缱) h d s 水平蠡据升隔符 c r t 衰格列分姆区埔s e l l ：衰椿列区域 d c ：囊格蠹据单元 图2 4 表格版面结构描述 数据分隔符和数据单元是构成表格版面结构的基本信息单位，它们共同构成表格版面 结构的主体。其中数据分隔符指表格版面中分隔表格单元的黑色线条( 黑线) 或白色空白 区域( 白线) 。 表格版面结构描述方法是基于表格数据单元排列的行列特征来分层描述的，其中表格 列分组层在复杂维数情况下会多次分层。基于这种无线表表格描述方式，我们采用“全局 一局部一全局”的处理流程，首先是基于文档图像中的连通体对整个文档的版面结构进行 分析，提取可能的表格候选区域，利用全局信息对表格候选区域进行局部分析，获取单元 数据和数据分隔符信息，然后再进行全局处理获取整个表格的版面结构。 我们也可以通过一种更适于计算机语言描述的嵌套序列来对表格版面结构进行表述， 如图2 - 4 的表格描述的序列表示为： t a b l e - - - - ( t a b l e ， v d s i ，( c r l ， v d s l ，( s c r l ， ， ) ，v d s 2 ，( s c r k ， f h d s l ，d c l ，h d s 2 ，d c m ，h d s m + i ) ) ，v d s 2 ) ，v d s 2 ，v d s n ，( c r n ， ) ， v d s n + i ) ) 。 在建立表格描述方法和处理系统时，我们充分考虑了系统的兼容性设计，在表格版面 结构分析完成后以网格矩阵和单元格链表的方式进行表格信息存储。由于我们采用了同系 统相一致的输出接口，从而无线表处理流程的输出可以作为r t k 其它相关处理模块的输 第1 1 页 第二章无线表的结构描述和自动处理方法 入，并利用统一的表格逻辑结构模型对表格信息进行理解和信息提取，从而达到同原系统 的完全兼容。 第三节无线表自动处理约束规则 本文的表格版面结构描述方法主要是利用表格行列特征及表格单元数据块在版面结构 上具有规则排列的特征并基于简单区域的概念建立的，对于文档图像而言，表格区域只是 表格文档诸多构件中的一类，有些非表格文档构件的版面结构同表格版面结构具有一定的 相似性；有些文档图像的版面结构非常复杂 其它各种原因会影响对表格区域的准确判断 用一些启发式先验知识。 同时由于噪音等原因导致的图像质量低下和 这些情况都要求在我们需要在处理过程中采 对此，我们给出了以下一些基于先验知识的说明： 规则1 ：表格结构具有空间独立性和封闭性。 表格结构作为文档图像中的独立元素结构，在版面上同其它文档成员之间是以某种特 定的方式进行分隔，如表格框架线( 线条或较大的空白区域) 、明显的版面结构差异等。 规则2 ：表格内各列之间不发生空间重叠现象。 表格是具有多列结构的文档图像元素，列在版面结构上是通过分隔符来划分的，而分 隔符是独立的图像元素，因此表格列之间是可以竖直切分的。这种分隔方式同表格所要表 达的逻辑功能相一致，也符合人们对表格的阅读、理解和检索的习惯。 规则3 ：表格分组局部上也满足表格行列特征。 表格采用分组的方式进行重新分列，分组子列符合表格特征，子列间的竖直切分不能 切分分组列头，表格分组行头可以处在行头指示域中，也可以位于表格体内以单独的一行 来对表格行进行分组，如图2 2 所示分组。 规则4 ；表格数据单元具有统一的属性。 同一列中的表格数据单元具有相同的对齐方式，如左对齐、右对齐和居中等。同一表 格中不同的列同样具有相同的对齐方式。同一个表格中的表格数据单元具有相同的属性， 如字体大小、同一行中的数据具有相同的水平基线。表格数据单元可以是一行也可以是多 行的，