（应用数学专业论文）基于一般图形voronoi图的版面分割方法.pdf

河北师范大学硕士论文 摘要 摘要 随着社会的发展，电子文档的应用越来越广。因此，把记录在纸上的文字识 别出来并转化为电子文档的o c r 文字识别系统成为广泛关注的热点，相应的版面 分割处理也成为重要的研究课题。 目前，随着复杂版面的出现，版面的编排已经不再局限为矩形。这使得传统 的版面分割算法大部分已不再适用，同时处理复杂版面的各种版面分割方法应运 而生。本文提出了一种基于一般图形v o r o n o i 图的版面分割方法。该方法是一种 基于连通域的分割算法。首先将文档图像进行二值化及滤波预处理，选择适当的 结构元素对该二值化图像进行膨胀，然后把经过处理后的外部边缘作为一般图形 v o r o n o i 图的生成元，再根据离散生成法生成v o r o n o i 图后与原图像进行并运算， 从而完成最后的版面分割。该方法操作简单、有效，适用范围广，尤其对中文版 的非m a n h a t t a n 版面有很好的效果。 关键词：版面分割；一般图形v o r o n o i 图；膨胀；连通域 第1 页 河北师范大学硕士论文 摘要 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h es o c i e t y , e l e c t r o n i cd o c u m e n ti sm o r ea n dm o r e p o p u l a r h o wt or e c o g n i z et h ew o r d sw r i t t e no l lt h ep a p e ra n dc h a n g et h e mi n t o e l e c t r o n i cd o c u m e n th a sb e c o m eah o t s p o t c o r r e s p o n d i n g l y , t h ep r o c e s so fp a g e s e g m e n t a t i o nh a sa l s ob e c o m eai m p o r t a n tr e s e a r c hp r o b l e m n o w a d a y s ，w i t ht h ea p p e a r a n c eo fc o m p l e xp a g e ，t h el a y o u to f t h ep a g eh a s n o t l i m i t e dr e c t a n g l e ，w h i c hm a d et h eu s e dm e t h o d si n a p p l i c a b l e w eg i v eam e t h o d b a s e do nv o r o n o id i a g r a m sf o rg e n e r a lf i g u r e s t h i sm e t h o di sa l s oap a g e s e g m e n t a t i o na l g o r i t h mb a s e do nc o n n e c t i v i t y t h ei m a g e sn e e dt ob ec h a n g e di n t o b i n a r yi m a g e sa tf i r s t a n dt h e nas u i t a b l es t r u c t u r i n ge l e m e n ti s u s e dt op e r f o r m d i l a t i o no p e r a t i o n a f t e r w a r d s ，t h eo u t l i n eo ft h ed i l a t i o nr e s u l ti ss e l e c t e dt ob et h e g e n e r a t o ro ft h ev o r o n o id i a g r a m e x p e r i m e n t ss h o wt h em e t h o di sv e r ye f f i c i e n t e s p e c i a l l yi nn o n - m a n h a t t a nl a y o u tw r i t t e ni nc h i n e s e a n dt h i sm e t h o di sa c c u r a t e ， e f f i c i e n ta n de a s yt op e r f o r m k e yw o r d s ：v o r o n o id i a g r a mf o rg e n e r a lf i g u r e s ；d i l a t i o n ；p a g es e g m e n t a t i o n ； c o n n e c t i v i t yr e g i o n 第2 页 河北师范大学硕士论文 第一章绪论 随着计算机技术的广泛应用，互联网技术的迅速发展，用电子格式存储的文 件越来越多，应用越来越广。电子文本具有存储空间小，便于检索、传输、更新、 保密等显而易见的优点。因此，2 0 世纪8 0 年代后期，人们就提出了无纸化办公的 概念，并围绕这个概念进行了一系列的研究。开发出了许多实用的o c r ( 光学字符 识别) 系统，将记录在纸上的文字信息识别出来，转化为计算机能够阅读、处理和 存储的电子文档。通常，当用o c r 系统处理印刷文档时，需要将其中的文本区、图 像区及图表区等各个分栏分割开，以便分别进行解释和处理。最初，这些工作是手 工完成的，为了减少人的干预，提高o c r 全过程的自动化程度及工作效率，版面分 割就成为一个受到广泛关注的研究课题。 版面分割是把文档组成部分( 如正文、标题、图片和版画) 分离的过程。版 面分割方法的好坏是至关重要的，它直接影响着包括版面分类在内的文档图像理 解的其它过程。 最初的版面分割方法一般是针对比较规则的版面，如矩形版面、m a n h a t t a n 版面等。这类版面的分割方法简单，处理速度快，分割效果较好。近年来，随着 对版面理解系统研究的增多，也出现了一些可用于分割比较复杂版面( 如嵌入式 版面、非m a n h a t t a n 版面等) 的方法。其中对非m a n h a t t a n 版面的研究较多。 非m a n h a t t a n 版面是指具有以下性质的文档图像编排方式：( 1 ) 文档组成部分 的形状是任意的，不限于矩形；( 2 ) 文档组成部分之间由空白隔开( 非重叠版 面) 。分析这类文档图像的主要问题之一是如何表示文档组成部分的边界。这个 问题可以用边为任意长度、任意方向的多边形来解决。 本文对文档图像的版面分割方法做了研究。并在此基础上提出了一种基于一 第3 页 河北师范大学硕士论文 般图形v o r o n o i 图的版面分割方法。该方法分割准确、简单易行，可以较精确地 描述文档组成部分的边界，且与图像的旋转角度无关，尤其对复杂的非 m a n h a t t a n 版面有很好的分割效果。 第二章版面分割的介绍 随着计算机技术的快速发展，文档分析及自动处理的实用化引起了人们的广 泛兴趣。文档分析是通过分析文档图像从而识别版面结构的过程。版面分割是文 档分析的首要步骤，它将文档图像分为多个子区域，每个子区域仅包含一种数 据类型，分割算法的最终目标是将文档中插图区域和文本区域分离。 文档版面可以分为两种类型：m a n h a t t a n 版面和非m a n h a t t a n 版面。 m a n h a t t a n 版面的区域边界有水平或竖直的分割线，而非m a n h a t t a n 版面可以 有任意形状的版面组成部分，并且可以任意安排位置。文本区域指的是标题、栏 标题、段落、脚注和表格；非文本区域是指图片和版画。 2 1 版面分割方法的分类 版面分割的方法按搜索顺序一般可分为3 类：自上而下的方法或称为模式驱 动法、自底向上的方法或称为数据驱动法以及其它方法。另外，从被分析的对象 的角度，又可以分为基于前景的分割方法和基于背景的分割方法。 2 1 1 自顶向下的分割方法 这类算法典型的是由高层的一系列假设开始，然后试图在下层细节上通过搜 索一棵隐含的假设树来证实每一个假设，最终在最底层完成证明。也就是说从文 本页面的整体出发，将页面分割成几个属性不同的小一点的区域，然后将小的区 域进一步划分，依次进行，直到不能继续划分为止。其中，游程平滑算法与投影 第4 页 河北师范大学硕士论文 轮廓切分算法是应用较为广泛的两种自顶向下的分割算法。 游程平滑算法的基本方法是设定一个阈值，把游程长度小于这个阈值的连续 “0 ”的序列用等长的“1 ”序列来代替，从而将文本页面分割成小块，如文献【1 】。 投影轮廓切分算法是由于文本行之间，不同段落之间都存在空白间隔，使文本页 面在x 轴、y 轴的投影在间隔处出现谷点，从而在谷点处沿x 轴、y 轴进行切分， 把文本页面分割成小块，如文献【2 】。 这类分割算法处理速度快，一般对规则版面处理效果好。但是该算法需要一 些先验知识，如知道文本页面由文字区与图像区之间有一定的间隔等等。此外， 这类方法对文本的倾斜十分敏感。 2 1 2 自底向上的分割方法 自底向上的策略先在最底层的细节进行合并，也就是从文本页面的像素或小 的区域出发，判断各个小区域的属性，将属于相同类型的区域进行合并，逐渐形 成大的区域，依次进行，直到整个页面处理完毕。例如，由字符形成单词，然后 将词合并成行，行合并成段落等等，直到整个版面完成聚集在一起。 连通分量分析算法是自底向上的代表算法，该算法根据文本区和图像区的连 通分量具有不同的特性，采用不同的连通分量特征值作为判决条件。该方法一般 先把文本页面分割成几个小块，对每一个小块得到一个或者几个特征值，然后根 据特征值进行分类判别，最后对各个小块进行综合，如文献【9 】。 2 1 3 其他方法 目前，对于含有丰富对象的文档图像的分割算法研究己取得较好的效果。过 去，用自底向上方法分析目标像素仍是应用于版面分割的主要方法。此外，还有 基于纹理特性的分割与分类算法。该方法把文本页面不同属性的部分看作纹理特 第5 页 河北师范大学硕士论文 征不同的区域进行纹理特性的区分。这类方法不受文本倾斜的影响，但缺点是处 理速度慢，而且不易形成规则形状的输出。 k i s ee ta 1 提出了基于点为生成元的v o r o n o i 图的文档分割方法【”，该方法把 部分v o r o n o i 边作为文档组成部分的边界，其中使用了两个特征量：最小距离和 面积比。但是该方法由于生成元较多，效率较低。文献f 5 】提出了一种基于 d e l a u n a y 三角剖分的文本区域提取方法。但由于汉字的笔画复杂，单个字的笔 画之间大都不是连通的整体，使得该方法对于汉字的处理也不能直接适用。还有， o g o r m a n 提出了一种最近k 邻域分析的算法【“。该算法能把文本行连起来从而 给出连通域中文本块的轮廓，旋转角度、字间距和行间距的准确测量由文档投影 图获得，文本行用平行、相对距离和方向识别。 2 2 本文所做的工作及本文的组织结构 本文将一般图形v o r o n o i 图应用于文档图像的分割。该方法是一种基于连通 域的分割算法。首先将文档图像进行二值化及滤波预处理，选择适当的结构元素 对该二值图像进行膨胀，然后把经过处理后的外部边缘作为一般图形v o r o n o i 图的生成元，再根据离散生成法生成v o r o n o i 图后与原图像进行并运算，从而完 成最后的版面分割。该方法操作简单、有效。适用范围广，尤其对中文版的非 m a n h a t t a n 版面有很好的效果。 本文按照以下结构组织：第三章介绍版面分割的两个预处理操作：二值化处 理和噪声点消除。第四章介绍一般图形v o r o n o i 图和数学形态学膨胀的概念，从 而引出本文提出的一般图t 髟v o r o n o i 图版面分割算法。第五章介绍该算法的优缺 点及待改进之处。第六章为结论，最后为参考文献。附录中为该算法的程序实现。 第6 页 河北师范火学硕士论文 第三章版面分割的预处理 在本文中，文档图像的二值化处理和噪声点消除统称为版面分割的预处理操 作。 3 1 二值化处理 把一个不理想的原始模拟图像转变成较理想的二值图像是版面分割预处理 过程的重要环节。印刷或书写在纸上的文字，由于油墨的深浅不同，纸张反光的 不同，有时纸上还会有不可避免的污点，使得扫描文档的亮度不均。因此，二值 化处理是极为重要的，而且直接影响分割结果的好坏。 3 1 1 直方图法 怎样从多值的数字图像中取出目标物体，最常用的方法就是设定某一阂值 t ，用t 将图像的数据分成两大部分：大于t 的像素群和小于t 的像素群。 阈值化的变换函数表达式如下： f ( i ，) = ：菇乡岔；孓r 其中，t 为指定的阈值。该变换函数为阶越函数，只需给出阈值点t 即可。 阈值的选取一般采用直方图法。 对应于每一个灰度值，求出在图像中具有该灰度值的像素数的图形叫做灰度 直方图，简称直方图。用横轴表示灰度值，纵轴表示像素数，统计一幅图像的像 素按灰度分布的图形，如图3 1 。 阐值灰度值 图3 - 1 直方图 第7 页 河北师范大学硕f 二论文 当文字图像部分与背景的灰度值相差很大时，会在直方图中有两座明显的山 峰，选谷底处的值作为阈值即可。但是当对比度不大时。则无明显的谷底，不能 确定阈值。 3 1 2 微分直方图法 本文采用微分直方图法，用图像中具有灰度值s 的所有像素的微分和代替 直方图中纵轴的像素数。其中具有灰度值s 的像素的微分是指该像素与周围8 邻域像素灰度值差的绝对值的和，则微分值最大的灰度值被认为是最佳的阈值。 该方法认为文字图形的边缘部分与背景部分的灰度值会急剧变化，所以利用灰度 的变化率来决定阈值。但实际中，边界附加的灰度值的变换范围大，通常先进行 增强对比度后再求微分直方图，使微分直方图中有明显的峰。 阐值灰度值 图3 - 2 微分直方图 3 2 扫描文档图像的噪声消除 经过二值化处理后的图像中往往有一 定量的噪声点，这些噪声点有些孤立地存 在，有些将图片区域或文本区域连在一起， 从而在后继操作时使文本区域或图片区域 被过度分割或过度融合，从而影响对文档 组成部分边界的精确描述，如图3 - 3 所示 e 1 3 - 3 被空白包目的噪声点 第8 页 河北师范大学硕士论文 在本文中，我们用数学形态学中的开运算方法来消除噪声点。这是由于开运 算具有消除细小物体，在纤细点处分离物体的作用，这正适合本文中的要求。 3 2 1 数学形态学的介绍 数学形态学是一门新兴的图像处理与分析学科，其基本理论和方法在视觉检 测、生物医学图像分析、机器人视觉、图像压缩编码、纹理分析等诸多领域，都 取得了非常成功的应用。它是建立在严格数学理论基础上的学科，其基本思想和 方法对图像处理的理论和技术产生了重大影响。事实上，形态学图像处理已成为 计算机数字图像处理的一个重要研究领域。 形态学图像处理的基本思想，是利用一个称作结构元素的“探针”收集图像 的信息。当探针在图像中不断移动时，便可考察图像各个部分间的相互关系，从 而了解图像的结构特征。数学形态学基于探测的思想，与人的f o a ( f o c u so f a t t e n t i o n ) 的视觉特点有类似之处。作为探针的结构元素，可直接携带知识( 形 态、大小、甚至加入灰度和色度信息) ，来探测研究图像的结构特点。 3 2 1 1 腐蚀 腐蚀是数学形态学最基本的运算。它的实现是基于填充结构元素的概念。利 用结构元素填充的过程，取决于一个基本 的欧氏空间运算平移。将一个集合a 平移距离x 可以表示为a + x ，其定义为： 彳+ x = 口+ x ：a 彳) 从几何上看( 如图3 4 所示) ，a + x 表示 a 沿矢量x 平移了一段距离。探测的目的 图“二值图像的平移 就是标记出图像内部那些可以将结构元 第9 页 河北师范大学硕七论文 素填入的( 平移) 位置。 集合a 被集合b 腐蚀，表示为彳淞，其定义为 彳6 曰= x ：b 十xc 7 彳 其中c 表示子集关系，a 称为输入图像，b 称为结构元素。a o b 由将b 平 移x 但仍包含在a 内的所有点x 组成。如果将b 看作为模板，那么，彳绞坝由 在平移模板的过程中，所有可以填入a 内部的模板的原点组成。 如果原点在结果元素的内部，那么， 腐蚀具有收缩输入图像的作用如图3 5 所示。与此相反，当结构元素不包含原点 时，腐蚀可以用于填充图像内部的孔洞， 这是腐蚀运算一个值得注意的特性。 3 2 1 2 膨胀 图3 - 5 腐蚀运算示意图 二值数学形态学的第二个基本运算是膨胀。膨胀是腐蚀运算的对偶运算( 逆 运算) 。膨胀的方称为： a b = u a + b ：b b ) 其中，b 表示用来进行膨胀的结构元素，结构元素内的每一个元素取值为0 或1 ，它可以组成任何一种形状的图形，在图形中有一个中心点；a 表示输入图 像。此公式的含义是用b 来膨胀a 得到的集合彳o b ，彳。口是由b 映像的位移 与a 至少有一个像素相同时，b 的中心点位置的集合。通常是拖动结构元素在a 图像域移动，横向移动间隔取一个像素，纵向移动间隔取一个扫描行。在每一个 位置上，当结构元素b 的中心点平移到a 图像上的某一点( x ，y ) ，如果结构元 素的像素与目标物体至少有一个像素相交，那么就保留( x 。y ) 像素点，从而达 第1 0 页 河北师范大学硕士论文 到使物体边界向外扩张的效果。为了进一步说明膨胀的原理，下面通过图3 - 6 来 说明。 图3 - 6 示意了用结构元素b ( 如图( b ) 所示) 对目标图像a ( 如图( a ) 所示) 进行膨胀运算并得到运算结果( 如图( c ) 所示) 的过程。图c a ) 中白色的部分 代表背景，灰色的部分代表目标图像a 。图( b ) 中黑色的方格代表结构元素的 中心点，灰色的方格代表邻域。图( c ) 中灰色的部分表示原目标图像，黑色的 部分表示膨胀出来的结果。在膨胀处理过程中，将结构元素在图像中移动，如果 结构元素的邻域与目标图像a 有部分重合，则保留图像中对应于中心点的像素 点。通过这个例子可以看出，膨胀实际上是把图像的外围扩充了一圈，同时保留 图像内部的部分。 ( a ) 原图( b ) 结构元素图 ( c ) 膨胀示意图 图3 - - 6 膨胀运算示意图 3 1 2 3 开运算 开运算是以腐蚀和膨胀定义的，先腐蚀后膨胀的过程就称为开运算。原图经 过开运算后，能够去除孤立的小点、毛刺和小桥( 即连通两块区域的小点) ，消 除小物体、平滑较大物体的边界，同时并不明显改变其面积。 利用图像b 对图像a 做开运算，用符号ao b 表示，其定义为： ao b = ( 么o b ) o b 公式中b 表示用来进行开运算的结构元素，结构元素内的每一个元素取值为0 第”页 河北师范大学硕上论文 或1 ，它可以组成任何一种形状的图形，在图形中有一个中心点；a 表示原图像 经过二值化后的像素集合。为了更好的理解开运算在图像处理中的作用，我们看 下面的等价方程： a o b = u 口+ 石：b + x c 7 _ 椰 这个方程表明，开运算可以通过计算所有可以填入图像内部的结构元素平移 的并求得。即对每一个可填入位置作标记，计算结构元素平移到每一个标记位置 时的并，便可得到开运算的结果。事实上，这正是先作腐蚀，然后作膨胀运算的 结果。 图3 7 左边是被处理的二值图像a ，针对的是黑点，中间是结构元素b ， 标有小三角的点是中心点，即当前处理元素的位置。拿b 的中心点和a 上的点 一个一个地对比。对于腐蚀运算：如果b 上的所有点都在a 的范围内，则该点 保留，否则将该点去掉。对于膨胀运算：如果b 上有一个点落在a 的范围内， 则该点就为黑。 图3 7 开运算示意图 可以看到，当使用圆盘结构元素时，开运算对边界进行了平滑、去掉凸角。 在凸角点周围，图像的集合结构无法容纳给定圆盘，从而使凸角点被开运算删除。 而当使用线段结构元素时，沿线段宽度方向较大的部分才能够保存下来，而较小 的凸部分将被删除。因此，经过开运算后，能够去除孤立的小点、毛刺和小桥， 第1 2 页 河北师范人学硕士论文 平滑较大物体的边界，同时并不明显改变其面积。 在本文中，我们用3 3 的结构元素对图像进 行开运算，从而去掉孤立噪声点和连接文本区域与 图片区域的噪声点( 这是预处理操作的必要步骤， 原因将在4 2 3 2 节具体介绍) 。然而，文本行中 一些孤立的笔画( 如“永”字的”或者“杰” 字的“m 、”等等) 也有可能被除去。但这对后续 操作不会产生影响。处理结果如图3 - 8 所示。 图3 - 8 滤波结果 第四章基于一般图形v o r o n oi 图的 文档图像分割算法 4 1 一般图形v o r o n o i 图 v o r o n o i 图是计算几何的一个重要分支，成功地解决了找最近点、求最大空 圆、求n 个点的凸包、求最小树等问题，在计算几何的理论和应用中发挥着很大 作用。另外，v o r o n o i 图在计算机辅助设计、地理信息处理、计算机图形学、模 式识别、机器人、城市规划等许多领域也有应用。 4 1 1 v o r o n o i 图的定义 最简单、最基本的v o r o n o i 图，是平面上的以点为生成元的v o r o n o i 图。其 定义如下： 定义1 ：给定平面上的点集s ， s = p i ，p 2 ，p 。) ，将由 k ) = n 扣l d 只) 吠易马) ) “ 图4 1 点为生成元的v o r o n o i 图 第1 3 页 河北师范大学硕士论文 0 = 1 。2 n ) 所给出的对平面的分割，称为以用0 = 1 2 n j 为生成元( 或母点) 的v o r o n o i 图，简称为v o r o n o i 图，记为v o r ( s ) ( 见图4 1 ，图中的黑点为v o r o n o i 图的生成元) 。其中d ( p ，办) 为p 和b 间的e u c l i d 距离。该图中的顶点和边分 别称为v o r o n o i 顶点和v o r o n o i 边。 4 1 2 一般图形v o r o n o i 图的定义 类似地，可以定义生成元为任意平面几何图形 的v o r o n o i 图，我们称为一般图形v o r o n o i 图。 定义2 ：设厶( i 一1 ，2 ，n ) 为二维欧氏空间 中n 个互不交叉的任意图形，将由 k 心) 。0 伽l 配厶) 始) ( i = 1 2 n ) 囤4 - 2 一般图形t o r o n o i 图 所给出的对平面的分割称为一般图形厶( i = 1 2 n ) 的v o r o n o i 图( 见图4 - 2 。 其中，图中的粗黑线条为生成元，细线条为v o r o n o i 边) 。 4 1 3 一般图形v o r o n o i 图的生成算法 对于一般图形v o r o n o i 图的生成，目前较好的方法为离散生成算法”。i ，该算 法的实现与生成元的具体形状无关，且不关心v o r o n o i 边的几何形状，无需复杂 计算，可以使近似效果达到理想程度。具体描述如下： s t e p l ：对每一生成元指定种颜色，使不同生成元之间颜色互不相同。 s t e p 2 ：在各个生成元的边界上选取具有代表性的点，称为母点。 s t e p 3 ：对每个母点，以母点为圆心，用母点所在生成元的颜色，逐渐向外扩 展画圆。当屏幕上所有的像素都画上颜色时，结束。 s t e p 4 ：横向、纵向扫描屏幕，抽取v o r o n o i 边。 第1 4 页 河北师范大学硕士论文 4 2 基于一般图形v o r o n o i 图的文档图像分割算法 随着社会的发展，报纸、杂志、文档等印刷体的版面越来越复杂，它们的版 面不再局限为传统的矩形版面。文本段落和图像区域会出现各种各样的形状，并 且以各自不同的倾斜角旋转和排列。对于这样的复杂的版面，大多数传统的版面 分割算法都不适用。这种文档图像分割的主要问题之一为如何表示文档组成部分 的边界，这个问题可以用边为任意长度，任意方向的多边形解决。 而一般图形v o r o n o i 图的v o r o n o i 边正好具有这种特性，因此，本文提出了 一种一般图形v o r o n o i 图的版面分割方法。我们注意到，无论在传统版面还是复 杂版面中，文本区域或图像区域之间都有一定的空白间隔。如果我们把这些区域 的边缘作为一般图形v o r o n o i 图的生成元，则这些区域就会在空白间隔处找到彼 此分离的界线。这样就可以解决复杂版面的版面分割问题。首先该算法无需额外 的倾斜检测与校正，而且不是基于像素级别的处理，因此该算法的执行速度相当 快。同样也可以避免在其它算法中出现的轮廓跟踪或边缘检测时出现的各种问 题。该方法十分灵活，这是因为无论打印区域的形状如何的奇怪，都可以通过确 定它的v o r o n o i 区域来对它进行有效地分割。 4 2 1 算法描述 算法的基本思想是，首先将灰度文档图像进行二值化处理，并用数学形态学 中的开运算除去版面中的噪声点，然后用适当的结构元素对文档版面进行膨胀处 理，使相邻的字词以及属于同一段落的文本行连接起来( 以形成相对独立的连通 基元，便于下一步的分割工作) ，对膨胀的结果图进行边缘提取，同时去掉文本 区域及图片区域中出现的内部边缘，把剩下的外部边缘作为一般图形v o r o n o i 图的生成元，构造一般图形v o r o n o i 图。最后将生成的v o r o n o i 图与原图像进行 第1 5 页 河北师范大学硕士论文 并运算。 具体做法是： s t e p l ：用微分直方图法取得阈值，将灰度文档图像进行二值化处理。 s t e p 2 ：用数学形态学中的开运算进行滤波，除去图像中的噪声点，以避免 生成多余的母点，致使文本区域或图片区域被过度分割。 s t e p 3 ：用统计的方法，找到文档图像的字间距，和行间距聊，并用一个大 小为“+ o r ) 术( m + 仃) ，且矩阵元素均为1 的结构元素对文档图像 进行膨胀处理，其中盯为一个小正数。 s t e p 4 ：对膨胀后的图像进行边缘提取，并去掉文本和图像中的内部边缘。 s t e p 5 ：把经上述处理后的外部边缘作为一般图形v o r o n o i 图的生成元，构 造一般图形v o r o n o i 图。 s t 印6 ：把生成的一般图形v o r o n o i 图与原图像进行并运算，得到文档图像 的版面分割。 4 2 2 算法流程 在本文的算法中，版面分割的实现是通过一般图 形v o r o n o i 区域的确定来完成的。它包括六个主要的 步骤，流程图如图4 - 3 所示。各个步骤的具体操作将 在各个章节详细介绍。 4 2 3 连通域的生成 4 2 3 1 字间距和行间距的获取 字间距和行间距是下面膨胀处理中结构元素选取 的重要参数，而它们的取值与结果及编排形式密切相 第1 6 页 图4 - 3 算法流程 河北师范大学硕上论文 关，因此有必要从输入图像中估值。为此，我们利用横、纵扫描中连通域之间的 距离d 的分布率来估值。 但汉字的笔划复杂，很多字的笔画之间存在小于字间距的内部间距，使得扫 描统计时，出现许多小于字间距且数量居多的小间距。这将对字间距的统计产生 不好的影响，所以要对汉字进行必要的处理，消除这种笔画之间的间隔对算法的 影响。 从上述章节中可以知道，膨胀运算具有扩张图像的作用，并且如果图像内部 存在尺寸小于结构元素尺寸的空洞，那么膨胀运算具有填补这些孔洞的作用。这 个作用从膨胀运算的定义中也可以清楚地看出来。因此，我们首先用一个小的结 构元素进行膨胀处理，使单个字的笔画之间形成连通的整 体，以提高计算d 分布率的准确性。 汉字的笔画基本都在一个外接矩形之内，字中间的孔 p 洞也基本接近方形，所以我们选择方形的结构元素。在实 验过程中，我们采用的结构元素是一个3x3 的正方形结 构元素，原点位于中心。处理结果如图4 4 所示。 图4 _ 4 填充字符孔洞 接着，我们进行横向扫描，并记录两个黑色像素点之间的距离z ，最后统计 这些d 出现的频率。对于纵向扫描也是相同过程。我们可以看到，两次扫描的d 分布图中都会出现一个波峰，则横向扫描的d 分布图中波峰处所对应的距离值即 为字间距，而纵向扫描的d 分布图中波峰处所对应的距离值即为行间距。 4 2 3 2 膨胀处理 由于汉字笔画复杂，单个字的笔画之间大都不是连通的整体。因此，基于像 素的方法先找出图像中的所有连通域，再根据字内部的间距、字间距和行间距对 第1 7 页 一。，p_一一一一一，f，im壤 。t- 一h一l“；_ 一-“，n膳 ：- t，l- t一一0一一肝nh刊鼍即一一v一-咿 河北师范大学硕士论文 它们进行合并是非常复杂的，速度较慢。而形态学的膨胀运算具有扩张图像的作 用，这样的话，若能选择合适的结构元素。就能把单独的字及属于同一段落的文 本行连接起来。 这里，图像中的白色像素为背景像素，值为0 ：黑色像素为目标像素，值为 1 。实验中，我们用一个大小为( ，- i - 盯) 木( 研+ 盯) ，且矩阵元素均为1 的结构元 素对目标像素进行膨胀，其中，、聊分别为文档 图像的字间距和行间距的统计值。对于分辨率为 2 0 0 d p i 的图像，我们使用实验值仃= 3 。膨胀 结果如图4 5 所示。 下面介绍噪声点对膨胀处理的影响。 上文中提出必须要去掉孤立噪声点及区域 之间的噪声点，这是因为膨胀是对二值化物体边 界点进行扩充，将与物体接触的所有背景点合并 到该物体中，使边界向外部扩张的过程。如果两 年5 膨胀结果 物体之间的距离比较近，则膨胀运算可能会把两个物体连接在一起。特别是当两 物体之间有噪声点时，膨胀运算把两个物体连接在一起的机率更大，从而引起文 本区域或图片区域的过度融合。对于孤立的噪声点，膨胀处理后会变为更大的连 通单元，在生成v o r o n o i 图的过程中将作为单独的生成元存在，从而使文本区域 或图片区域被过度分割。 4 2 3 3 连通域的边缘提取 图像经过膨胀处理后，需要把边缘提取出来，作为一般图形v o r o n o i 图的生 成元。边缘提取的方法有很多，常用的几种方法有梯度算子、r o b e r t s 算子、 第1 8 页 河北师范大学母l 上论文 l a p l a c i a n 算子等等。不同的方法有各自的处理效果，应用范围也各不相同。但 这些处理都能够突出边界，得到一定的分割效果。 在本文中，需要处理的图像为二值图像，本文采用了处理二值图像的一种简 单的方法来提取边缘。该方法的原理就是掏空内部点。用一个一维数组来记录处 理的像素点的周围8 个邻域的信息，如果8 个邻域的像素点的灰度值和中心像素 的灰度值相同，就认为该点是在图像的内部，否则，认为该点是在图像的边缘。 开辟一块内存缓冲区，将原图像保存在内存中。依次处理图像中的每一个像素， 如果该点为内部点，则在内存缓冲区将该像素点置为白色，否则保持不变。最后 将内存中的数据复制到原图像中就得到了图像的轮廓。该方法处理速度快，处理 结果符合算法要求。 文档图像经过膨胀处理后，在文本区域和图片区域中常常会产生白色孔洞， 这样经过边缘提取后就会出现内部边缘，如图4 - 6 和图4 - 7 所示。 图4 6 图片区域中的内部边缘 图4 7 文本区域中的内部边缘 第1 9 页 河北师范大学硕士论文 如果这些内部边缘也作为一般图形v o r o n o i 图的生成元，将会使文本区域和 图片区域被过度分割。采用以下规则进行处理： 定义3 包围盒，是充分紧密包围连通区域的矩形。表不为 r e c t , ( t o p , ，b o t t o m , ，l e f , t ，r i g h t ) 其中，蛔陆，b o t t o m f 为连通域中所有像素点的纵坐标的最大值和最小值； l e f t , ，r i g h 为连通域中所有像素点的横坐标的最小值和最大值。 ( t o p , ，l e f t , ) ，( b o t t o m ，r i g h t ，) 为矩形区域的左上角、右下角的坐标。 规则1 ：包含规则。如果包围盒 r e c t , ( t o p , ，b o t t o m , ，t e f , t ，r i g h t ，) 及 r e c t j ( t o p j ，b o t t o mj ，l e f t j ，r i g mj 、) ( f ) ， r e c t , 满足r e c t ，cr e c t j ，则去掉r e c t j 所包围的连通域。 经过规则1 处理后，各个连通域是互相独立的，文本区域及图片区域的内部 边缘均被去除，处理结果如图4 - 8 所示。 图4 8 去除内边缘 4 2 3 4 构造v o r o n o i 图和文档分割 把这些最终得到的外部边缘作为一般图形v o r o n o i 图的生成元，构造一般图 形v o r o n o i 图。对于图像3 - 8 ，生成的v o r o n o i 图如图4 9 所示。图4 1 0 为生 成的v o r o n o i 图与原图像进行并运算，最终得到的版面分割的结果。 第2 0 页 河北师范大学硕士论文 图4 9 生成v o r o n o i 图图4 1 0 非m a n h a t t a n 版面分割结果 3 算法的实验结果及讨论 该方法是用v i s u a lc + + 6 0 在w i n d o w s2 0 0 0 环境下实现的，并对多幅文档 图像进行了版面分割实验。由实验结果可知，该方法能够对任意的文档版面进行 有效分割。由图4 - 1 0 、图4 - 1 1 和图4 - 1 2 的结果上可以看出，用一般图形v o r o n o i 图的方法可以精确地表示文档组成部分的边界，并且对于非m a n h a t t a n 版面及有 一定旋转角度的版面的分割效果也很好。但与其它基于密度特征的分割方法一 样，对于字间距较大的标题行或注释行仍有可能被错误分割( 如图4 1 0 中的大 标题行及图4 - 1 1 中右下角的小标题行及图片下方的注释行) 。 这是因为文档中的标题行通常是选用远远大于正文字体的字体，占用的空间 也很大，由于膨胀处理中结构元素的限制，所以标题行常常被过度分割。但是在 以后的识别过程中还需进行将文本行分割为单个字符的操作，因此较少的标题行 或注释行被过度分割，反而有利于后续识别过程的进行。然而对于图像底部的注 释行和图像的距离很近的情况，注释行就会被错误地分割为图像的一部分，而在 版面分析中将会丢失本身的文本信息。 第2 1 页 河北师范大学硕士论文 图4 - 1 1 矩形版面的分割结果 图4 - 1 2 倾斜版面分割结果 第五章本算法的优缺点及待改进之处 5 1 算法的优点 在计算效率方面，程序的运行效率也是比较高的，这是因为： 1 算法不需要对倾斜的版面进行额外的倾斜检测和倾斜校正的预处理 过程。 2 由于本文的结构元素的选取是采用统计特征得到的，提高了算法的适 应性。 3 v o r o n o i 图的生成是在较大的连通基元的外边缘上直接生成的，不涉 及像素级的处理，并且无需冗余v o r o n o i 边的删除及v o r o n o i 边的合 并处理，同样也大大减少了其它算法中用点v o r o n o i 图处理时过度分 割的情况。 4 该算法能够较完全地找出文档图像的各个区域，分割准确，信息的丢 第2 2 页 河北师范大学硕士论文 失非常少。另外，由于是对文档图像的整体信息进行考虑，速度较快， 而且应用范围广。 5 2 算法的不足与尚待改进之处 任何算法都是基于一定的前提条件提出的，并且在某些特定的条件下才可以 最大地发挥作用，本文也不例外。由于本文的统计参数与文字连通区域数目在文 档总的连通区域中所占的比例是有关的( 比例数越小，对参数统计的影响越大) ， 本方法对文字占优势的文档分析效果比较好。对于文本区域不占主体的文档图 像，只需用不同的方法找到字间距和行间距即可。这也是本文需要进一步研究的 问题。而且，对于非常复杂的版面形式，文本页面背景很复杂，例如包含图像或 者花纹的情况，本文的算法就不能应用了。而且其它的基于几何特征的分割方法 也不能适用。算法的不断改进就是希望减少限制条件，同时最大可能的扩展算法 的适用范围。 第六章结论 本文提出一种基于一般图形v o r o n o i 图的版面分割方法，该方法的主要特点 如下： 首先本文采用数学形态学中的膨胀运算把单个字词及属于同一段落的文本 行连接在一起，以便进行后续处理，提高了算法的运行速度。 其次，本文是在膨胀后的较大的连通基元的外边缘上构造一般图形v o r o n o i 图的，从而大大减少了其它算法中构造点v o r o n o i 图的结果中太多过度分割的情 况。 最后，该方法的边界v o r o n o i 边是具有任意方向和任意长度的。因此，可以 第2 3 页 河北师范大学颂上论文 更好的处理非m a h a n t t a n 版面及其它的复杂版面。 但与其它基于密度特征的分割方法一样，本文也有自身的缺点及需要改进之 处。主要待研究的问题有： 1 膨胀的结构元素中。值的精确确定； 2 把与图像区域距离很近的注释行从图像区域中分离出来： 3 对于文本区域不占主体的文档图像的结构元素的选择。 第2 4 页 河北师范大学硕士论文 参考文献 1 1 】s t r o u t h o p o u l o s ，c ，p a p a m a r k o s , n ，c h a m a z a s ，c p l a ；u s i n gr l s a a n dan e u r a l n e t w o r k j ；e n g i n e e r i n ga p p l i c a t i o n o fa r t i f i c i a l i n t e l l i g e n c e e a a i 1 2 ( 1 9 9 9 ) ( 11 9 1 3 8 ) 1 2 lj a e k y uh a ，r o b e r tm h a r a l i e k ，i h s i nt p h i l l i p s r e e u r s i v e x yc u tu s i n g b o u n d i n gb o x e so fc o n n e c t e dc o m p o n e n t s j 【3 lk o i c h ik i s e ，a k i n o is a t o ，m o t o it w a t a s e g m e n t a t i o no fp a g ei m a g e su s i n gt h ea r e a v o r o n o i d i a g r a m c o m p m e r v i s i o na n d i m a g eu n d e r s t a n d i n g ， 7 0 ( 3 ) ( 19 9 8 ) 3 7 0 一3 8 2 f 4 ly i x i a o ，h o n g y a n t e x tr e g i o n e x t r a c t i o ni nad o c u m e n ti m a g eb a s e do nt h e d e l a u n a yt e s s e l l a t i o n j p a t t e r nr e c o g n i t i o n ，3 6 ( 2 0 0 3 ) 7 9 9 8 0 9 【5 】m i h r a nt u c e r y a n ，a n i lk j a i n t e x t u r es e g e m e n t a t i o nu s i n gv o r o n o i p o l y g o n s j i e e e t r a n s a c t i o n so np a t t e m a n a l y s i s a n dm a c h i n e i n t e l l i g e n c e ，1 2 ( 2 ) ( 1 9 9 0 ) 2 l1 - 2 1 6 【6 ll o g o r m a n t h ed o c u m e n ts p e c t r u mf o rp a g el a y o u ta n a l y s i s j i e e et r a n s p a t t e ma n a l m a c h i n t e l l 1 5 ( 11 ) ( 1 9 9 3 ) 11 6 2 - 11 7 2 1 7 la a n t o n a c o p o u l o s p a g es e g m e n t a t i o nu s i n gt h ed e s c r i p t i o no f t h eh a - c k g r o u n d j c o m p u t v i s i o n l m a g e u n d e r s t a n d i n g ，7 0 ( 3 ) ( 1 9 9 8 ) 3 5 0 一3 6 9 【8 1l c i n q u e ，l l o m b a r d