（管理科学与工程专业论文）基于图论的文档图像分割应用研究.pdf

山东师范大学硕一l ：学位论文 中文摘要 随着信息技术的发展，文档图像在办公自动化、数字图书馆、网上阅卷、电 子商务、电子政务等项目中获得广泛的应用。在这些应用中，纸质文档通常采用 扫描方式形成数字化文档图像进行存储、传输、显示和打印。为了保证对文档图 像的有效处理，对文档图像的分割研究显得尤为重要。 论文分析了文档图像的特点，指出文档图像是由一些具有特定性质的区域块 组合而成，通常包括文字块、线图、连续色调图像( 真彩色图) 和半色调图像( 带 调色板的图) 。其中，文字和线图保存了图像较多的细节以及结构信息，具有较 高的空间分辨率特征，这一部分区域对颜色分辨率的要求不高；而连续色调和半 色调的图像则保存了较多的颜色信息，通常要求较高的颜色分辨率，但对空间分 辨率的要求不高。也就是说文档图像大多数是由具有明显不同特征的部分组合而 成，通常来说包含文本区域、线图区域和插图区域，而文本区域又包含文字的轮 廓和文字的背景颜色，插图区域通常是高分辨率的彩色图像。这些区域不仅在逻 辑意义上具有独立性，而且在颜色分辨率和空间分辨率上也具有明显不同的特 性。这种图像特征明显却逻辑上具有独立性的文档图像更适合利用具有全局分割 特性的分割方法去处理。 基于图论的图像分割是近年来正处在发展中的一种新兴的图像分割技术。该 技术具有全局分害特性。本文介绍和阐述了整合图像分割和图割理论的基本框 架。幅图像可以被映射成一个加权的无向图，其中像素点被当作图中的顶点， 而相邻的像素之间的视觉性质( 比如灰度级别，颜色或者纹理) 的相似度当作相应 的边的权值，于是图像的分割结果就可以通过对图的最小割方法来获得。具体研 究了归一化方法。基于n c u t 的图像分割方法有很多优点，能够给出具有全局特 征分割结果，具有很好的数学理论背景，但是也隐藏了一些缺点。比如算法中涉 及到特征方程的求解问题，计算量过打，不适合大幅图像的分割，为了使该方法 具有实用性，本文使用自适应像素块映射为单一的节点，降低生成图的边和节点 数目；修改邻域系统适应块结构，提高区域间邻近性和连续性，通过试验证明得 到了可以接受的算法效率。 山东师范人学硕1 ：学位论文 为了提高计算速度，我们受到著名的多分辨率信号处理和金字塔型结构的启 发，引入了一种用于图分割计算的多尺度计算方法。最后我们进行了几个数值实 验，结果表明这种多尺度计算方法能够降低分割算法的运算时间，并且能够获得 与传统分割方法近似相同的分割结果，特别是对于图像中所要分割目标在整个图 中所占比例较小的情况，速度提高更为明显。 关键词：图像分割，图论，归一化割， 2 山东师范大学硕十学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y ，d o c u m e n ti m a g e sa r e w i d e l y u s e di nt h e p r o j e c t s o fo a ( o f f i c ea u t o m a t i o n ) ，d a ( d i g i t a l l i b r a r y ) ，e c ( e l e c t r o n i cc o m m e r c e ) ，e l e c t r o n i cg o v e r n m e n t ， e t c i nt h e s e a p p l i c a t i o n s ， d o c u m e n t so fp a p e ra r eu s u a l l ys c a n n e di n t od i g i t a l d o c u m e n ti m a g e st ob es t o r e d ，t r a n s m i t t e d ，d i s p l a y e da n dp r i n t e d i no r d e r t oe n s u r et h ee f f e c t i v e l yp r o c e s so ft h ed o c u m e n ti m a g e ，d o c u m e n ti m a g e s e 鲫e n t a t i o nr e s e a r c hi sp a r t i c u l a r l yi m p o r t a n t t h et h e s i sa n a l y s i st h ec h a r a c t e ro fd o c u m e n ti m a g e s ，f i n dt h a tt h e i m a g e sa r em a d eo fs o m er e g i o n sw i t hs p e c i a lc h a r a c t e r s t h er e g i o n s i n c l u d et e x tb l o c k s ，1i n eg r a p hb l o c k s ，c o n t i n u e t o n ei m a g e sb l o c k s ( t r u e c o l o ri m a g e ) a n dh a l f t o n ei m a g e sb l o c k s ( i m a g e sw i t hc o l o rp a l e t t e ) t e x t a n dl i n eg r a p h sb l o c k sr e s e r v em o r ed e t a i l sa n ds t r u c t u r ei n f o r m a t i o n ， w h i c hw o u l dd e m a n dm o r es p a c er e s 0 1 u t i o n ， b u t1 i t t l ec 0 1 0 r r e s 0 1 u t i o n c o m p a r a t i v e l y ，t h er e g i o n so fc o n t i n u e t o n ei m a g e sb l o c k so r h a l f t o n ei m a g e sb l o c k sa r ew i t hm o r ec o l o ri n f o r m a t i o n ，u s u a l l yd e m a n d m o r ec o l o rr e s 0 1 u t i o n ，b u tl i t t l es p a c er e s 0 1 u t i o n t h a ti st os a yt h e m a j o r i t yo fd o c u m e n ti m a g e sa r es i g n i f i c a n t l yd i f f e r e n tb y s o m e c o m b i n a t i o no ft h ec h a r a c t e r i s t i c so f ， n o r m a l l yc o n t a i n st h et e x t o f r e g i o n a l ，r e g i o n a la n di 1 1 u s t r a t i o n sc h a r tt h er e g i o n ， a n dt h et e x to f r e g i o n a l l a n g u a g ea l s oc o n t a i n st h eo u t li n eo ft h eb a c k g r o u n dc 0 1 0 ra n d t e x t ， i l l u s t r a t i o n so ft h er e g i o na r eu s u a l l yh i g h r e s o l u t i o nc o l o r i m a g e s ， t h e s ea r e a sn o to n l yi nt h el o g i c a ls e n s eo fi n d e p e n d e n c e ， b u t a l s oi nc 0 1 0 ra n ds p a t i a lr e s o l u t i o n si sa l s ou ps i g n i f i c a n t l yd i f f e r e n t c h a r a c t e r i s t i c s t h ed o c u m e n ti m a g ew i t ho b v i o u s l yi m a g ef e a t u r e sa n d i n d e p e n d e n c e i sm o r es u i t a b l et ou s ec h a r a c t e r i s t i c so f o v e r a l1 s e g m e n t a t i o np a r t i t i o n st od e a lw i t h i m a g es e g m e n t a t i o nb a s e do ng r a p ht h e o r yi san e w l yd e v e l o p e di m a g e 3 山东师范人学硕l 学位论文 s e g m e n t a t i o nt e c h n i q u ei nr e c e n ty e a r s t h et e c h n 0 1 0 9 yh a st h e c h a r a c t e r i s t i c so ft h eo v e r a l ls e g m e n t a t i o n t h i st h e s i si n t r o d u c e sa n d i 11 u s t r a t e sag e n e r a lf r a m e w o r kt o i n t e g r a t e t h ea r e a so f i m a g e s e g m e n t a t i o na n dg r a p h c u tt h e o r y t h ei m a g ei sm a p p e di n t oaw e i g h t e d u n d ir e c t e dg r a p ha n d t h ep i x e l sa r ec o n s i d e r e da sv e r t e x e sa n dt h e s i m i l a r i t yb e t w e e nt h ev i s u a lp r o p e r t i e s( e g g r a y 一1 e v e li n t e n s i t y ， c 0 1 0 ro rt e x t u r e )a te a c hp a i ro fn e i g h b o r i n gp i x e l si sa s s i g n e da st h e r e s p e c t i v ee d g ew e i g h t t h e r e f o r et h ei m a g es e g m e n t a t i o nc a nb eo b t a i n e d b yc u t t i n gt h eg r a p hw i t ham i n i m u mc u tc r i t e r i a s p e c i f i cr e s e a r c ho n m e t h o d so fn o r m a l i z e d i no r d e rt oi n c r e a s et h es p e e do ft h ei n t e r a c t i v e s e g m e n t a t i o n ， w ei n t r o d u c eam u l t i s c a l em e t h o df o rt h ec o m p u t a t i o no f g r a p hp a r t i t i o nt h a ti sm o t i v a t e db yt h ew e l l 一k n o w nm u l t i r e s o l u t i o n sig n a lp r o c e s sin gt h e o r ya n dt h ep y r a m ids t r u c t u r e w ep e r f o r man u m b e r o fn u m e r i c a le x p e r i m e n t st os h o wt h a tt h i sm u l t i s c a l ec o m p u t a t i o nm e t h o d c a nr e d u c et h er u n n i n gt i m eo ft h es e g m e n t a t i o na l g o r i t h m ，a sw e l la sc a n p r o d u c en e a r l yt h es a m es e g m e n t a ti o nr e s u l ta st h ec o n v e n t i o n a lg r a p hc u t s m e t h o d ，e s p e c i a l l yw h e nt h eo b j e c tt ob ee x t r a c t e di ss m a l lc o m p a r e dt o t h ew h o l ei m a g e k e yw o r d s ：i m a g es e g m e n t a t i o n ，g r a p ht h e o r y ，n o 彻a l i z e dc u t 4 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得( 注：如没有其他需要特别声 明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 办砂 翩嫁多事囊 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权兰 盈可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 西、i 、磅夕 导师签字： 签字日期：2 0 0 9 年莎月2 日 辨囊 签字日期：2 0 09 年铜上日 山东师范大学硕十学位论文 1 1 问题的提出 第1 章绪论 图像技术是各种与图像有关技术的总称。图像技术根据其抽象程度和研究方 法等不同一般分为：图像处理，图像分析和图像理解。图像分割( i m a g e s e 鲫e n t a t i o n ) 就是图像分析领域的一门重要的图像技术。 随着信息技术的发展，文档图像在办公自动化、数字图书馆、电子商务、电 子政务等项目中已获得广泛的应用，在这些应用中，纸质文档通常采用扫描方式 形成数字化文档图像进行存储、传输、显示和打印。 借助机器对海量的文档图像进行分析和理解变的尤为重要，文档图像的广泛 应用，对于文档图像的分析和理解也成为学术界以及应用上研究的重点。对文档 图像分析就是对图像中感兴趣的目标进行检测和测量，获得他们的客观信息从而 建立对文档图像的描述。目的在于识别文档图像中的文字和图形区域，并进一步 提取用户所需要的目标信息。主要的工作可以分为两类：( 1 ) 对文字区域处理的 纹理分析：包括倾斜检测，段落、行、字的定位，并最终通过o c r 技术实现文字 的识别；( 2 ) 图形分析：处理线图中的线和字符成分，标志图等。文档图像分析 研究的主要内容如图l 所示： 5 山东师范人学顾二l 学位论文 图1 1 文档图像处理系统图 文档图像分析的一般步骤包括数据采样，像素级的处理和特征提取，然后对 文字区域和图形区域分别进行识别和处理。在像素级的处理中，主要包括图像的 二值化处理，图像的矢量量化，更重要的则是图像的分割技术。 对文档图像理解的重点则是在图像分析的基础上，进一步研究图像中各目标 的性质和它们之间的相互关系，并得出对原始成像客观场景的解释，从而指导和 规划行动。那么对文档图像的分割就成了文档图像理解的基础，是文档图像信息 提取识别的前提。 1 2 图像分割研究背景 在对图像的研究和应用中，人们往往仅对图像中的某些部分感兴趣，这些部 分称为目标或前景，其它部分成为背景。前景目标往往对应着图像中特定的，具 有独特性质的区域。为了辨别和分析目标，需要将它们分离提取出来，在此基础 上才有可能对目标进一步利用。图像分析就是指把图像分成各具特性的区域并提 取出感兴趣目标的技术和过程。这里的特性可以是像素的灰度，颜色，纹理等， 而预先定义的目标可以对应单个区域，也可以对应多个区域。 借助集合的概念我们可以对图像分割做如下的定义弛1 ： 令集合r 代表整个图像区域，对r 的分割可看作将r 分成n 个满足以下五个 条件的非空子集( 子区域) 尾，r ，r ： _ v 1 u r = 尺； f = l 2 对所有的i 和j ，i j ，有r n 乃= o ； 3 对i = l ，2 ，n ，有p ( r ) = 豫晒； 4 对i j ，有p ( r u q ) = ，舭胚； 5 对1 ，2 ，n ，冠是连通的区域。 其中p ( r ) 是对所有集合r 是连通的区域。 6 山东师范大学硕l ：学位论文 其中，条件1 是指对一幅图像的分割结果中全部子区域的总和应能包括图像 中的所有像素，或者说分割应将图像中的每个像素都分进某个子区域。条件2 是指分割结果中各个子区域是互不重叠的，或者说在分割结果中一个像素不能同 时属于两个区域。条件3 指出在分割结果中每个子区域都有独特的特性，或者说 属于同一个区域的像素应该具有某些相同的特征。条件4 是指分割结果中，不同 的子区域具有不同的特性，没有公共元素，或者说属于同区域的像素应该具有一 些不同的特性。条件5 是指分割结果中同一个子区域内的像素应当是连通的，即 同一个子区域内的任两个像素在该子区域内相互连通，或者说分割得到的区域是 一个连通子集。实际应用中图像分割不仅要把幅图像分成满足上面五个条件的 各具特性的区域而且需要把其中感兴趣的目标区域提取出来，而所谓的感兴趣的 目标完全是人为确定的。只有这样才能算真正有意义的分割。 图像分割的研究多年来一直受到人们的高度重视，至今已提出了上千种各种 类型的分割算法1 。由于现有的分割算法非常多，要将它们全部分类非常困难， 但对一些传统的分割方法我们可以大致将其分为三类：l 边缘检测和连接算法； 2 设置阈值进行分割；3 基于区域特征的分割。 1 通过边缘检测来实现图像分割是一种非常直观有效的分割方法。其实现步 骤通常包括两步：第一步，通过适当的方法检测图像中的边缘；第二步，将这些 不连续的边缘曲线“组装 成边界。图像中的边缘通常是灰度，颜色，纹理等性 质不连续的地方，因此，要实现边缘的检测一个最基本的方法就是对图像进行求 导，求导后数值较大的位置正是边缘所处的位置。人们将这个基本的检测原理推 广发展，提出了很多的边缘检测算法和检测模板，其中最基本的有梯度算法和拉 普拉斯算法，检测模板包括r o b e r t s 钉，p r e w i t t 朝，k i r s c h 引，r o b i n s o n 7 1 ，f r e i 和c h e n 随1 以及c a n n y 1 等模板。另外当图像的边缘是某些特定形状的曲线( 如直 线，圆等) 时，可以采用霍夫n 们( h o u g h ) 变换方法进行检测。1 9 6 2 年霍夫提出一 种判断图像中的点是否处在同一条特定形状的曲线上的方法，称作霍夫变换。霍 夫变换结合了过去很多年的研究成果提出了全局像素连接和曲线检测的选择方 法。以后又有许多以这种基本方法为基础的改进方法，例如，l o 和t s a i n 提出 一种检测细线n 2 3 的方法，g u i l 等人提出一种霍夫变换的快速实现算法和简单曲 线的检测。d a u l n 3 1 4 1 等人对检测椭圆弧的方法做了进一步推广，s h a p i r o 解决了 7 山东师范大学硕 j 学位论文 对灰度级图像的霍夫变换的实现问题等等。 2 设置阈值进行图像分割就是一种门限处理技术。例如对一幅灰度图像，从 背景中提取目标对象的一种显然的方法是选择一个门限值t 将目标对象与背景 按照灰度级别进行区分。灰度值大于t 的像素就是目标对象，小于t 的像素就是 背景。在这个基本原理基础上人们发展并提出了许多用于图像分割的门限处理方 法n5 1 ，例如最基本的全局门限处理方法，自适应门限方法，最佳全局自适应门限 方法，利用边界特性改进的局部门限处理以及基于不同变量的门限等等。 3 基于区域的分割方法是直接寻找分割区域的一种图像分割方法。图像分割 就是将图像区域r 分割成各具特性的子区域r 1 ，r 2 ，r n ，基于区域的分 割方法正是基于这一原则，将具有相同或相似特性的像素或子区域聚合成更大的 区域从而实现整体图像的分割。具体的实现方法有区域生长，区域分裂和合并等 方法。h a d d o n 和b o y c e n 明n 以及p a v l i d i s 和l i o w 所做的以分割为目的的整合区 域和边界信息的工作是这方面最早进行的研究。另外，h o j j a t o l e s l a m i 和 k i t t l e r n 踟提出了更进一步的区域生长方法，是对传统区域生长方法的一种有效 的改进。上述三种类型并不能把所有的分割方法都囊括在内，特别是随着近年来 各学科的交叉发展以及现代智能技术的发展，出现了一些新型的更加复杂的分割 算法，例如基于动态轮廓模型( a c t i v ec o n t o u rm o d e l ：，a c m ) 的s n a k e n 印算法， 基于图论( g r a p ht h e o r y ) 的分割算法瞳们乜，以及利用神经网络的智能图像的分割 算法瞳2 3 等等。 1 3 基于图论的图像分割技术 图论( g r a p ht h e o r y ) 是离散数学的一个分支，它以图( g r a p h ) 为研究对象， 研究顶点( v e r t e x ) 和边( e d g e ) 组成的图形的数学理论和方法。图论中的图是由若 干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物 之间的某种特定关系，用顶点代表事物，用连接两顶点的边表示两个相应事物间 具有某种关系。图论起源于1 8 世纪欧拉研究和解决的柯尼斯堡七桥问题。图 论的研究对象相当于一维的拓扑结构。图论真j 下的发展始于2 0 世纪5 0 年代，这 与计算机技术和网络技术的飞速发展是分不开的。另外在诸如物理学，化学，生 8 山东师范大学硕一i ：学位论文 物学，运筹学，信息论，控制论，社会科学以及经济管理，金融学各方面都有广 泛的应用，并且随着信息时代的发展，图论正日益显现出其在众多领域的强大活 力。 图像分割已经有几十年的历史，存在海量的研究结果和文献，但是人们仍然 没有找到通用的方法，获得理想的结果。目前存在的图像分割方法都基于不同的 图像模型，利用不同的特性，有各自一定的使用范围和优缺点幽1 。从总体来看， 首先，图像分割的目标是极力接近人类视觉的感知效果，反映图像的全局特征， 但是没有很好地解决。其次，图像分割技术需要处理大量原始图像信息，需要很 高的计算资源，从而限制了大多数方法的实际应用。 基于图论( g r a p ht h e o r yb a s e d ) 的图像分割方法是近年来国外研究的热点 之一。其主要思想是将图像映射到加权图( w e i g h t e dg r a p h ) ，像素对应图的节 点( v e r t e x ) ，像素之间的相邻关系对应图的边( e d g e ) ，像素特征之间的差异 ( d i f f e r e n c e ) 或相似性( s i m i l a r i t y ) 对应边上的权重( w e i g h t ) ，然后利用 图论中的成熟理论对图像进行切割( c u t 或者p a r t i t i o n ) 和组合( g r o u p ) 。基 于图论的图像分割方法大体分为两个方向，分别对应两种思想：“大而化之 ，“小 而并之”。具有代表性的图论方法就是归一化割和最小生成树两种方法。 最早的图的分割方法就是设置一个固定的阈值，割断权值小于这个阈值的 边，将图分割成一个个的子图。z a h n 瞳胡提出了一种基于图的最小生成树( m i n i m u m s p a n n i n gt r e e ，m s t ) 的分割方法。这种方法被应用到离散点的分簇和图像分割。 应用于前者时，图中边的权值是表示各个离散点之间的距离，而应用于后者时， 图中边权值通常基于相邻的像素的灰度差别。z a h n 的m s t 分割的做法也是简单 的将图中权值最小( 对应的图像像素灰度差别最大) 的边割断来构造子图，达到分 割的目的。但是这种简单的割断最小权值边的方法存在很大的缺陷。这是因为图 像中往往灰度剧烈变化的区域的像素之间的灰度差别很大，对应的图中边权值很 小，如果简单得设置某个阈值将这些边割断，就会造成错误的分割，例如会将灰 度变化剧烈的区域分割成很多细小的区域，或者将灰度变化相对小，但是确属边 缘的部分融合到一起。u r q u h a r t 乜6 1 针对这个问题提出一个归一化( n o 硼a l i z e d ) 方法来试图克服这个缺点，它使用节点上连接边的最小权重来归一化其他边的权 重，取得一定的效果。但是这个归一化方法不能提供一个合理的自适应分割准则， 9 山东9 i l j 范大学硕一 ：学位论文 同样不能对剧烈变化区域作良好分割。f e l z e n s z w a l b 和h u t t e n l o c h e r 1 在2 0 0 4 年提出了他们的分割准则，即比较区域之间和区域内部的特征差来判定是否在两 个区域之间存在边界，这个准则能够适应图像的内容，所以能够获得全局的视觉 特征。同时，这个方法在算法效率上有很好的优势，成为了“小而并之 思想的 典型代表。 基于图论图像分割方法的另外一条路径是对图进行切割，切割准则是使分离 的像素之间的相似度最小。图像切割就是“大而化之”的方法例。w u 和l e a h y 啪1 在1 9 9 3 年提出了这个准则，但是这个方法倾向于分割出小区域。因此s h i 和 m a l i k 在1 9 9 7 年提出归一化切割方法来克服这个缺点，他们后来在2 0 0 4 丰富了 这个方法的描述啪3 。这个方法使用区域内部的相似性来归一化区域之间的相似 性，然后使之最小口。它考虑了区域的自相似性( s e l f s i m i l a r i t y ) ，在理论和 实践上更进了一步。这些方法比早期的基于图论的方法的共同优点是能够获取非 局部特征，但是也存在很多不足，比如计算效率问题、连续空间到离散空间的近 似问题等。 s h i 和m a l i k 的方法利用了矩阵谱的概念，使用相似度矩阵的特征值和特征 向量来获得图像的分割。w e i s s 删在1 9 9 9 年分析了p e r o n a 和f r e e m a n 3 的方法、 s h i 和m a l i k 的方法、s c o t t 和l o n g u e t h i g g i n s 的方法、以及c o s t e i r a 和 k a n a d e 口2 1 的方法，试图找出它们之间的联系与区别，进而统一谱方法。在谱方法 中，c h u n g 等人1 的工作提供了理论基础，而f o w l k e s 钔等人的工作也提供一种 利用谱理论进行分割的方法。 分层的金字塔对数据和图像进行表现和分析的研究有几十年的历史。l a n c e 和w i l l i a m s 在1 9 6 7 年将分层结构用于聚类，而h o r o w i t z 和p a v l i d i s 在1 9 7 6 年用于图像分割钉。人们在二十世纪九十年代逐步丰富和完善规则与非规则金字 塔的分割方法。其中，使用图来表现金字塔的方法得到了比较深入的研究，比如 h a x h i m u s a 和k r o p a t s c h 删的工作( 2 0 0 4 年) 、k r o p a t s c h 3 7 1 的对偶图( d u a lg r a p h ) ( 1 9 9 5 年) 、b u r n 等人的组合地图( c o m b i n a t o “a lm a p ) ( 2 0 0 3 年) 等。 l o 山东师范人学硕卜学位论文 1 4 本文的主要内容 基于图论的图像分割方法和金字塔分层实现方式是近年来图像分割技术研 究的热点问题。在众多的研究基础和思路上面，本文将研究内容分为两个方面： 基于最小生成树的分割算法和归一化分割算法，包括理论基础、实现方式、改进 途径和优化方法等；非规则金字塔图像分割方法，包括自适应块结构和缩减核， 用图来描述金字塔各层的对应图像的像素信息。 基于最小成生树的图像分割方法和归一化的图像分割方法是图论方法应用 于图像分割比较具有代表性的两种方法，都能够获得良好的全局分割效果。随后 我们将重点分析归一化分割理论，虽然该方法具有成熟的理论基础，能够提取整 幅图像的特征，同时度量不同分组之间的总体不相似性和各个组内相似性的总 和，但由于计算效率问题只能适用于小图像，为了能使之有效的应用到文档图像 分割中，本文通过适用于文档图像的改进的自适应块结构和金字塔分层结构相结 合，本文研究的方法是先对金字塔高层构造自适应块结构的图进行归一化分割， ，。 然后将分割后的子区域提取出来，再将子区域细化到金字塔低层进行更加细致的 分割。相比整幅图像计算量大大降低，试验表明分割质量大体相似。达到了本文 研究的要求。 1 5 本章小结 本章首先论述了文档图像分割作为图像分割领域一个分支的重要性和需 求，着重介绍了图像分割的研究背景和运用图理论做图像分割的研究现状，以及 提出了本文所要研究的内容。 在下一章里我们将对图像分割方法进行综述，回顾和总结图的基础理论和 经典的图分割方法。第三章我们将图的分割理论运用于图像分割，提出几种实用 的分割算法并给出实验结果。第四章我们将引入图像的金字塔结构，并于归一化 分割方法结合，进一步提高算法的计算速度，给出试验。 山东师范人学硕i j 学位论文 第2 章图像分割综述和图的分割 图像分割作为一个具有挑战性的图像处理技术，已经有几十年的历史了。人 们从图像本身的特征出发，利用各种数学理论和工具，使用不同的模型，对灰度 以及彩色图像进行分割处理，形成了错综复杂的图像分割方法。各种方法相互交 叉，相互影响，相互促进，形成了一个庞大的体系。一般的图像处理技术最先应 用于灰度图像( g r a yi m a g e ) ，然后发展到彩色图像( c 0 1 0 ri m a g e ) ，图像分割 也不例外。本章首先介绍一般的图像分割方法，再详细地介绍基于图论的图像分 割方法，最后给出图像分割系统的一般结构， 2 1 一般图像分割方法 早期的图像处理针对于灰度图像，随着图像采集设备和计算机技术的发展， 彩色图像的处理与应用成为主流。在此基础上，人们可以利用彩色图像的某一通 道信息，使用成熟的灰度图像处理技术来处理彩色图像；另外，人们也对完全的 颜色信息进行研究，提出了一些新的处理方法。 针对图像分割方法，人们提出不同的标准来进行分类。第一，最具有直觉 性的标准是基于两个基本属性：非连续性( d i s c o n t i n u i t y ) 和同质性 ( h o m o g e n e i t y ) 非连续性是指灰度级上的突然变化，因此可以通过检测点、 线和边等来分割图像；同质性是指区域内灰度级的相似性，因此可以通过阈值化 ( t h r e s h 0 1 d i n g ) 、聚类( c l u s t e r i n g ) 、区域增长( r e g io ng r o w i n g ) 以及区域 分离和合并( s p l i t t i n ga n dm e r g i n g ) 来进行图像分割。第二，我们可以将图 像分割方法大致划分为三个类别：基于特征空间( f e a t u r e s p a c eb a s e d ) 的方 法、基于图像空间( i m a g e d o m a i nb a s e d ) 的方法以及基于物理特征( p h y s i c s b a s e d ) 的方法，每个类别可以继续细分。第三，根据分割的自动与否，我们可 以分为自动分割方法和半自动分割方法。自动分割方法在分割过程中不需要人为 干预，半自动分割方法需要输入先验知识，比如区域增长方法中的初始化区域种 1 2 山东师范大学硕：卜学位论文 子选择。汹1 我们使用第二类标准来对图像分割方法进行分类，其中，神经网络和模糊理 论可以看作是数学工具，它们常常和其他方法结合起来，完成图像的分割。 2 1 1 基于特征空间的方法 一直方图阈值 描述与说明： 1 通过判别直方图的峰值( 又称m o d e ) 和谷值进行分割，每 个峰值对应一个区域，是灰度图像分割中广泛使用的方法； 2 对于彩色图像来说，通过直方图分割有三个途径：一是将颜 色空间中的三个分量分别生成直方图，然后进行组合来分割；二是在颜色三维空 间中直接生成直方图；三是将三维空间映射到二维空间进行处理； 3 因为噪声干扰，直方图上往往尖齿很多，因此需要使用滤波 器进行平滑处理； 4 阈值分为全局性阈值和自适应性阈值； 5 优点：不需要图像的先验知识，而且计算复杂度低； 6 缺点：1 ) 对于没有明显峰值，或者宽平谷值的图像来说，这个方法没有 效果；2 ) 不考虑空间信息，因此不能保证分割的区域是连续的。 二聚类 主要的聚类方法有：k m e a n so rc m e a n s ，f u z z yk m e a n s ，a d a p t i v e k m e a n s ，i s o d a t a ，m e a ns h i f t ，c o m p e t i t i v el e a r n i n g ，c o n n e c t e dc o m p o n e n t s ， c o n s t r a i n e dg r a v i t a t i o n a l ， c l u s t e r i n g ， t r e e m u l t i s c a l ec l u s t e r i n g ，g r a p hc u t 等。 描述与说明： 1 聚类是一种广泛的分割方法，在这个方法里面，人们提出了 很多不同的实现技术，一般可以分为两步：1 ) 将特征空间中的点进行聚类；2 ) 将聚类映射回图像空间域，形成分离的区域； 2 聚类方法最早应用于灰度图象分割，后来应用于彩色图像分 割( 使用部分或全部颜色信息) ； 3 聚类是一种自动分割技术，不需要任何先验知识； 1 3 山东师范人学硕1 ：学位论文 4 聚类的类别内部相似度较高，类别之间较低，每个类别代表了图像中的 一个区域； 5 自适应k m e a n s 方法利用了区域和空间信息，因此可以看作 基于特征空间和基于图像空间方法的结合体； 6 基于图论的分割方法也可以看作一种特征空间上的聚类，它可以使用任 何特征，这是本文的研究对象，我们在下面将详细阐述； 7 优点：直接分类，易于实现； 8 缺点：1 ) 不容易确定聚类的数目；2 ) 图像往往决定特征，没有确切的 方法选取合适的特征以获得良好的分割效果；3 ) 没有使用空间信息。 三分离及合并 主要方法包括：分离，合并，分离与合并的组合。 描述与说明 1 分离是将非同质的区域一直分离到同质区域为止，一般使用四叉树来描 述； 2 在满足同质准则的前提下，合并过程将相邻的区域合并到一起，直到这 个区域最大化，一般使用区域邻接图( r e g i o na d j a c e n c yg r a p h ，r a g ) 描述这 个过程； 3 分离的结果产生过多小分割区域，因此使用合并过程来将它们合并； 4 很多情况下，颜色区间的光滑性和连续性可以用马尔科夫随机场( m a r k o v r a n d o mf i e l d ，m r f ) 来河寿足； 5 我们可以将分离及合并技术与区域增长技术一起划分为基于区域的方 法； 6 优点：当区域同质准则易于定义时很有效果，而且比基于边的方法对噪 声抗干扰能力大； 7 缺点：本质上是顺序化的，因此在计算时间和内存上开销比较大。 四区域增长 描述与说明： 1 区域增长技术从预选择的种子点开始，根据某个同质准则，逐渐将相邻 符合同质准则的点合并起来，直到不能合并新的点； 2 主要目标是处理单个区域，也可以使用不同的增长过程将图像中所有符 1 4 山东师范大学硕一l ：学位论文 合条件的点都合并起来； 3 增长结束后，可能存在很小的区域，或者在多次增长过程中产生的具有 同质特征的相邻区域，因此需要后处理技术将这些区域合并起来，形成更大的区 域； 4 区域增长技术可以看作顺序化的聚类过程，因此分割结果与像素的处理 顺序有关系； 5 主要优点：分割的区域在空间上相连，具有紧致性( c o m p a c t ) ； 6 问题：如何合适地选取种子点和同质准则； 五基于边的方法 描述与说明： 1 通过检测区域之间的边来进行分割，也就是检测不连续性； 2 在灰度图像中，边可以通过梯度或者拉普拉斯函数来检测，它们是标量 函数； 3 彩色图像中的梯度函数可以通过两种方式来定义：1 ) 在三个颜色通道 中使用一个准则来计算梯度值；2 ) 在单个通道中计算梯度，然后根据特定准则 将它们合并； 4 可以分为两类处理过程：顺序化和并行化； 5 优点：边检测技术与人眼感知物体是类似的，对于区域之间有明显对比 的情况很有效果； 6 缺点：1 ) 在图像中边是病态的情况下或者边很多的情况下不好使用；2 ) 不容易形成封闭边界；3 ) 噪声影响大。 2 1 2 基于神经网络的方法 常见的方法有h o p f i e l dn e u r a ln e t w o r k s ( h n n ) ，t h es e l f 一0 r g a n i z i n gm a p ( s o m ) ，b a c kp r o p a g a t i o n ( b p ) 算法、l o c a ll i n e a rm a p ( l l m ) n e t w o r k 、 o s c i l l a t o r yc e l l u l a rn e u r a ln e t w o r k ( o c n n ) 、c o n s t r a i n e ds a t i s f a c t i o n n e u r a ln e t w o r k ( c s n n ) 。 描述与说明： 1 神经网络模仿生物神经元的信息处理过程，由很多相连的处理单元构成， 1 5 山东师范大学顾l ：学位论文 每个单元具有简单的功能； 2 三个属性：高度的并行性，具有高速计算能力，适合实时应用；任何程 度的非线性，处理单元之间相互依赖，可以对任何功能进行建模；很好的鲁棒性， 抗干扰能力强； 3 在图像分割应用中的优点：允许计算空间信息； 4 缺点：1 ) 事先需要知道分割结果；2 ) 初始化可能影响分割结果；3 ) 事先需要学习过程用来训练神经网络，并且训练时间很长，也需要避免过分训练。 2 1 3 基于模糊理论的方法 描述与说明： 1 在图像处理、分析以及识别的各个级别中，都存在着不确定性 ( u n c e r t a i n t y ) ；而且在系统中，前一级的处理结果会影响后一级，因此系统需 要足够的灵活度来处理这种不确定性； 2 模糊集理论( f u z z ys e tt h e o r y ) 为图像分割提供了一个机制，可以表 达和操作这种不确定性，注意这种不确定性不是随机性； 3 图像分割的输出应该是模糊子集，其中每个像素都有属于某个区域或者 某个边的度( d e g r e e ) ，由归属值( m e m b e r s h i pv a l u e ) 来表达； 4 模糊集理论可以用在聚类中，允许聚类之间有模糊的边界，比如f u z z y k m e a n s ，这是基于特征空间的方法； 5 模糊集理论可以看作一个数学工具，应用于多种场合，它往往和其他分 割方法结合使用； 6 可以灵活地应用于各个颜色空间中； 7 缺点：不容易确定模糊成员属性，并且计算量很大。 2 1 4 集于物理特征的方法 1 6 描述与说明： 1 数学工具与前面所述没有显著的区别，最大的不同是在于反射属性下物 山东师范大学硕：b 学位论文 理颜色模型，如表2 1 中颜色空间中“物理模型 所示； 2 基于物理空间的方法目标是克服阴影、投影和高光的影响，可以应用于 阴影的分割； 3 大部分工作都是基于二色反射模型( d i c h r o m a t i cr e f l e c t i o nm o d e l ) 、 近似颜色反射模型( a p p r o x i m a t ec 0 1 0 r r e f l e