（计算机应用技术专业论文）结合图论与聚类算法的自然场景图像分割方法研究.pdf

- j 苏州大学学位论文使用授权声明 f i i ii i if l i tiii i i ii iiil 17 3 2 0 3 2 本人完全了解苏州大学关于收集、保存和使用学位论文的规定， 即：学位论文著作权归属苏州大学。本学位论文电子文档的内容和纸 质论文的内容相一致。苏州大学有权向国家图书馆、中国社科院文献 信息情报中心、中国科学技术信息研究所( 含万方数据电子出版社) 、 中国学术期刊( 光盘版) 电子杂志社送交本学位论文的复印件和电子 文档，允许论文被查阅和借阅，可以采用影印、缩印或其他复制手段 保存和汇编学位论文，可以将学位论文的全部或部分内容编入有关数 据库进行检索。 涉密论文口 本学位论文属 在年一月解密后适用本规定。 非涉密论文形 论文作者签名：童基丛一一日 导师签名：垃日 期：竺! ：! ! ：! 三 结合图论与聚类算法的自然场景图像分割方法研究 中文摘要 结合图论与聚类算法的自然场景图像分割方法研究 中文摘要 海量的自然场景图像需要被快速检索、分析，这要求能够快速准确的对这些图像 进行自动图像分割。由于自然场景图像具有光照不确定、背景复杂等特点，使得自然 场景图像的分割成为图像分割领域的难点和热点。 论文以自然场景图像为研究对象，对基于图论和聚类的分割方法进行了深入的研 究，并利用分割好的区域进行分类、检索等实验，取得了如下成果： ( 1 ) 针对现有的基于图论的分割方法执行速度慢，对突变边缘敏感及分割纹理图 像效果不好的问题，本文提出了一种新的基于图论的颜色一纹理区域分割方法。该方 法采用分块的颜色和纹理特征，同时将邻域相关性引入到块间权重中，最后利用最小 生成树缩减的方法进行图像分割。主客观的实验表明新算法对于复杂的自然图像分割 更准确，同时分割速度较n c u t 方法大幅提高。 ( 2 ) 为了解决现有聚类分割算法需要预先指定分类数、初始分类中心等问题，本 文提出了一种自适应a p 聚类图像分割算法。该方法根据图像的整体特征自动计算偏 向参数，避免了传统聚类分割算法需预先指定初始值问题，对复杂的自然图像分割时， 分割精度较基于k 均值聚类和模糊c 均值聚类的分割算法有了较大提高。 ( 3 ) 为了验证本文提出的自适应a p 聚类算法在基于区域图像检索系统中的实际 应用效果，提高基于区域图像检索的区域匹配准确率，论文提出了一种加权的区域匹 配方法。实验结果表明，由于区域匹配过程增加了重要区域的权重，减少了次要区域 权重，显著改善了基于区域图像检索系统的检索准确率。 ( 4 ) 聚类分割算法对于空间离散的区域分割效果好，基于图论分割方法对于连续 平滑的区域更有优势。论文利用两类方法的优点，提出一种新的结合图论与聚类的自 然场景图像分割算法。图像分割实验表明，该方法有效的利用了两类方法的优点，弥 补了各自的缺点，提高了自然图像分割的鲁棒性。 关键词：图像分割，图论分割，聚类分割，a p 聚类，区域匹配 作者：孟庆涛 指导老师：龚声蓉教授 本文的研究工作受江苏省自然科学基金项目( b 怼0 0 9 1 1 6 b l q 0 0 9 5 9 3 ) 的资助。 t h er e s e a r c ho fn a t u r a ls c e n e i m a g es e g m e n t a t i o n b a s e do ng r a p ha n d c l u s t e r i n g a b s t r a c t m a s s i v en a r l r a ls c e n ei m a g e sr e q u i r ef a s tr e t r i e v a la n da n a l y s i s i m a g e ss e l f - i d e n t i f i c a t i o na n df i l t e ra r et h ev e r yu r g e n tt a s k sf o rn a t i o n a ld e f e n s ef i e l d s ，a n di m a g e s e g m e n t a t i o ni st h ek e yt oc o m p l e t et h e mw e l l n a t u r a ls c e n ei m a g e s i n d e t e r m i n a t i o n , c o m p l e xb a c k g r o u n d ，n o n - u n i f o r mr e s o l u t i o n a n dt a r g e t o b j e c ti nn a t u r a li m a g ei s u n c e r t a i n t h e r e f o r e ，t h en a t u r a ls c e n ei m a g es e g m e n t a t i o ni sd i f f i c u l tp o i n ta n dh o t s p o ti n a r e ao fi m a g es e g m e n t a t i o n t h i sd i s s e r t a t i o nt a k e sn a t u r a li m a g es e g m e n t a t i o na si t s s u b j e c t ，d or e s e a r c h e sf u r t h e ro nt h ep o p u l a ri 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 y a n dc l u s t e r i n g m a s se x p e r i m e n t so fi m a g ec l a s s i f i c a t i o na n di m a g er e t r i e v a lw e r ed o n e u s i n gr e g i o n sb es e g m e n t e d c o m p l e t e dt h ea c h i e v e m e n t sa sf o l l o w s ： 1 f o rn - c u ta l g o r i t h mi si n e f f i c i e n ta n de f f i c i e n tg r a p h - b a s e di m a g es e g m e n t a t i o n i ss e n s i t i v et o s t r o n ge d g e si ni m a g e s t h e s ec l a s s i c a lg r a p h - b a s e di m a g es e g m e n t a t i o n i n f o r m a t i o na n dg r a p h b a s e dm e t h o d sc a nn o td e a lw i t l lt h ep r o b l e mo fd i s c r e t er e g i o n s i n o r d e rt oc o m b i n ea d v a n t a g eo ft w ot y p e so fa l g o r i t h m ，o v e r c o m et h e i rs h o r t c o m i n g s ，w e p r o p o s e dac o m b i n eg r a p ha n dc l u s t e r i n gn a t u r a ls c e n e si m a g es e g m e n t a t i o nm e t h o d e x p e r i m e n tr e s u l t so fi m a g es e g m e n t a t i o nd e m o n s t r a t e dt h a tt h em e t h o di se f f e c t i v et o a v o i ds p a t i a lc o n s t r a i n t sa n dr e g i o n sb es e g m e n t e di sm o r es m o o t ht h a nu s i n gs i n g l eo n eo f m e t h o d e x p e r i m e n to fr b i rs h o wt h a tt h i sa l g o r i t h mi saf e a s i b l em e t h o df o rt h e o r ya n d p r a c t i c e k e y w o r d s ：i m a g es e g m e n t a t i o n , g r a p h - - b a s e di m a g es e g m e n t a t i o n , c l u s t e r i n g b a s e di m a g e s e g m e n t a t i o n ，a pc l u s t e r i n g ，r e g i o nm a t c h i n g w r i t t e nb ym e n g q i n g t a o s u p e r v i s e db yg o n gs h e n g r o n g t h er e s e a r c ho ft h i st h e s i sh a ss p o n s o r e db yt h en a t u r a ls c i e n c ef o u n d a t i o no fj i a n g s u p r o v i n c e ( b k 2 0 0 9 116 ，b k 2 0 0 9 5 9 3 ) i i i 2 1 基于图论的分割方法概述。1 3 2 1 1 基本原理1 3 2 1 2 现有算法分析15 2 2 基于图论的颜色纹理图像分割算法1 8 2 2 1 算法思想18 2 2 2 算法步骤2 0 2 2 3 颜色特征向量提取过程21 2 2 4 小波能量直方图特征向量提取过程描述2 2 2 3 实验结果与分析2 3 2 3 1 分割效率比较2 3 2 3 2 分割结果样例分析2 3 2 3 3 基于区域图像检索系统验证2 4 2 4 本章小结2 6 第三章自适应a l p 聚类区域分割与加权区域匹配算法。2 7 3 1 相关聚类分割算法概述2 7 3 2 基于自适应偏向参数的a p 聚类的图像分割。3 0 3 2 1a p 聚类算法概述3 l 3 2 2 自适应a p 聚类3 3 3 2 3 基于自适应a p 聚类的图像分割算法3 5 3 3 加权区域匹配方法3 6 3 3 1 传统区域匹配方法介绍3 6 3 3 2 加权区域匹配算法3 6 3 4 实验结果与分析3 8 3 4 1 实验数据集3 8 3 4 2 几种基于聚类的图像分割方法比较3 8 3 4 3 基于区域图像检索实验结果4 0 3 5 本章小结一4 2 第四章结合图论与聚类的图像分割算法 4 1 算法思想4 3 4 2 算法步骤。4 5 4 3 实验结果与分析4 6 4 4 本章小结5 0 第五章总结与展望。 5 1 总结5 l 5 2 展望5 2 参考文献 攻读学位期间公开发表的论文。 致谢 5 9 6 0 第一章绪论 第一章绪论 在图像分析与理解过程中，人们通常感兴趣的不是整个图像，而是图像中某一个 或几个区域( 称为前景) ，它们通常与背景具有不同的性质特征，属于不同的事物。 为了识别和分析目标，需要将它们从图像中分离提取出来。图像分割就是这样一种技 术，是把图像分成各具特性的区域并提取出感兴趣目标的技术和过程。这里的特性可 以是像素的灰度、颜色，区域的形状与纹理等，感兴趣的目标可以对应单个区域，也 可以对应多个区域。 1 1 自然场景图像分割的研究背景与意义 图像可根据很多原则进行分类，如按照图像所包含的颜色多少分为单色图像、灰 度图像、彩色图像等；按照应用背景分为医疗图像、遥感图像、红外图像等。如果按 照图像数据来源和采集方法分为两大类：自然图像、人工图像。自然图像指通过客观 设备所获取的客观世界的图形化表述结果。如：室外风景照、遥感图像、s a r 图像 等。而人工图像则指利用那些人为手段，经过主观意念所形成的图像，例如绘画作品， 计算机绘制的图像等。 本文所研究的自然场景图像是自然图像中的一类，通过数码照相机等设备拍摄获 得。包括自然景观、建筑、交通工具、动物、人物、花草树木等自然场景的照片。 近些年，由于互联网与数码产品的普及，自然场景照片数量急剧增长，单靠人力 去组织管理如此巨大数量的照片已经越来越困难。因此，如何提高图像的存储、检索、 传输效率显得尤为重要。人们很自然的想到如何使用计算机智能系统，对自然场景图 像进行分割，利用分割好的区域进行分类、压缩、检索等操作。因此，自然场景图像 的分割与人们的日常生活息息相关。 同时，自然场景图像分割技术也是图像分析、计算机视觉等领域的一项关键技术。 的如图1 1 所示，要想分析理解图像的内容，首要的步骤就是分割图像成有意义的区 域，只有这一步分割的准确，后面的图像分析、理解及对象识别才有意义。因此自然 场景图像分割是计算机视觉、自然图像分析与理解的基础，对其开展研究具有重要的 理论意义与应用价值。 第一章绪论结合图论与聚类算法的自然场景图像分割方法研究 图1 1 图像分割在图像工程中的位置 自然场景图像分割的应用领域非常广泛，几乎涵盖了图像处理与机器视觉的所有 领域。主要包括： ( 1 ) 安全领域：通过图像分割方法把图像中的感兴趣的目标分割出来。以便进行 特征提取和目标自动识别。处理的图像主要包括视频监控图像、网上的数码照片等。 ( 2 ) 智能交通分析：通过分割把交通监控获得的图像中的车辆目标从背景中分割 出来，进而进行车牌识别、车型识别、车辆跟踪等。 ( 3 ) 图像压缩：将图像分割成不同的对象区域对以提高压缩编码效率。 ( 4 ) 基于内容的图像分类与检索：通过对自然场景图像的分割、感兴趣区域的分 割，进行大型图像数据库的分类与检索。 ( 5 ) 计算机视觉：现代机器人技术、自动驾驶技术都离不开计算机视觉，然而计 算机视觉识别对象的第一步就是对自然场景图像的分割。 自然场景图像分割的应用领域还远不止这些方面，正是由于有着广泛的应用，才 使得众多的学者不断致力于自然场景图像分割理论的研究。尽管人们在图像分割方面 已取得了巨大的研究成果，但目前针对自然场景图像的分割技术还存在着诸多问题需 要解决。正是由于自然场景图像分割的不确定性及分割任务的重要性，人们至今仍在 不断研究探索新的分割理论与分割算法。 2 结合图论与聚类算： = = 的自然场景图像分割方法研究 第一章绪论 1 2 自然场景图像特点 自然图像是对外在客观世界的客观表现，对于同一事物必将获得相同或几近相同 的图像结果，所以自然图像具有特定的规律与性质： ( 1 ) 自相似性和尺度不变性 所谓自相似性( s e l f - s i m i l a r i t y ) 是指自然图像的局部和全局较为相似，例如海岸线 的局部经过放大之后和全局基本相似；而尺度无关性( s c a l ei n v a r i a n c e ) 表达类似的概 念，是指自然图像的统计规律并不随图像尺寸的变化而变化。实际上，该两项特性是 源于自然图像满足的分形( f r a c t a l ) 特性。 早在1 9 8 2 年，b e n o i tb m a n d e l b r o t 就以分形几何的方法来分析自然图像的特点。 此外，a l e xp p e n t l a n d 通过比较诸如山、树、云等自然景观，发现分形函数可以很好 的作为这些景观图像的数学模型，更进一步，他还采用分形布朗平面( f r a c t a lb r o w n s u r f a c e ) 模型作为分析工具，并取得了很好的结果。eps i m o n c e l l i 认为自然图像的分 形统计特性将会为进一步的研究动物、人类的视觉系统功能奠定扎实的基础。 gj b u r t o n 和d j f i e l d 的工作可能是最早给出关于图像尺度不变性结果的研 究，而d a n i e ll r u d e r m a n 则更为明确地指出，自然图像具有明显的尺度不变性，即 如果对自然图像进行尺度上的放大或缩小操作，图像像素点的边缘分布不会发生变 化。r u d e r m a n 利用图像像素点对比度l o g ( i ( x ) l o ) 的统计直方图( h i s t o g r a m ) 进行分析， 得到尺度不变性的结论。而z h u 通过对图像小波分解后系数的直方图进行研究，得到 更为广泛的不变性。a n t o n i ot u r i e l 则是引入测度论思想讨论自然图像对比度的特性， 认为自然图像满足多分形( m u l t i f r a c t a t i o n ) 的性质。除针对像素点的讨论外，a l v a r e z 还用数学形态学的方法来分析自然图像的拓扑特性，同样发现自然图像存在明显的尺 度不变性。 除了上面的一般统计规律外，部分学者还研究了图像经过滤波之后联合统计量的 统计规律，发现图像的小波变换后的系数在尺度间、方向间、位置间存在明显的相关 性。c 。z e t z s c h e 在一系列研究中发现，若将图像通过偶对称或奇对称g a b o r 滤波器滤 波后，则其联合密度具有循环对称性，且有较大峰值，故而能揭示其较强的相关性。 j s h a p i r o 则从充分利用小波系统之间的相关性，给出了一种具有良好性能的启发式 的图像压缩算法。e p s i m o n c e l l i 等深入研究了自然图像对于带通滤波器的响应，发 第一章绪论 结合图论与聚类算法的自然场景图像分割方法研究 现响应振幅具有很强的相关性。 ( 2 ) 非高斯性 以往的研究都将自然图像视为平稳的二阶随机过程，往往假设满足g a u s s i a n 模 型。但越来越多的研究成果颠覆了该假设，他们的基本结论便是自然图像具有显著的 非高斯性，需要采用更复杂的模型才能较好地拟合自然图像。如果采用传统的方法 ( f o u r i e r 变化和谱分析) 来分析自然图像，得不到所假设的软通g a u s s i a n 过程的结 果。相反，自然图像的功率谱是满足规律p 佃) = a 圳卜”，虽然r 会随着图像的变化 而变化，但是变化量一般很小【l 】。另外有部分学者基于自然图像的小波分解系数而进 行非高斯性的研究，发现小波分解系数具有显著的重尾特性( h e a v yt a i l ) ，中部的尖 峰突出，并且具有很大的峰度( k u r t o s i s ) 。此外小波分解系数在不同的尺度间具有相当 大的相关性( c o r r e l a t i o n ) ，即尺度间相关性( i n t e r s c a l ec o r r e l a t i o n ) 。所有的这些结论都 和标准的g a u s s i a n 过程相差迥异。m a l l e t 在此基础上使用广义l a p l a c i a n 密度模型 ( g e n e r a l i z el a p l a c i ad e n s i t ym o d e l ) 对自然图像的多尺度、正交小波分解系数进行建模。 z e z s c h e 发现，自然图像投影至任何局部化的、零均值的线性核上都将产生较大的峰 度值。j i n g g a n gh u a n g 在他的博士论文中发现，如果使用8 8 均值为0 的滤波器对 自然图像进行滤波，则将产生高峰度、长指数尾部的特征。该项工作为讨论如何使用 极大化峰度或是其他非高斯测度的方法对自然图像进行线性分解提供了可行性。 ( 3 ) 边缘主导性和高维奇异性 a n nb l e e 和d a v i dm u m f o r d 1 】将大量自然图像分割为3 3 的图像块，发现其中 超过1 2 的高对比度的图像块都可以解释为边缘的片段。故可判定，边缘是自然图像 导角色的成分，称之为边缘主导( e d g ed o m i n a t e ) 特性。该结论也基本上符合 然景观的认知，即人们对图像中边缘更敏感，通过边缘分割得到各个子对象， 上进行图像理解，从而产生视觉。d a v i dd o n o h o 经过进一步分析1 2 1 ，认为自 非高斯性以及尺度间相关性都可以使用边缘主导的特性来进行解释。 实际上是信号中的非连续点连接成的一条曲线，而非简单孤立的非连续点， 谓高维奇异性。这对传统的信号分析方法提出了更高地挑战。传统的f o u r i e r 法只能较好地分析连续信号，小波分析方法也只能较好地分析具有独立非连 号。因此，传统的方法并不能对边缘主导的信号进行有效地分析2 。正因为 得有效进行自然图像高维奇异性的分析便成为自然图像分析的关键。 4 结合图论与聚类算法的自然场景图像分割方法研究 由于自然场景图像分割的复杂性，分割方法的研究面临着巨大的困难与挑战，但 自然场景图像分割的重要的研究价值引起了众多学者、研究机构的重视。在自然场景 图像分割方面除了在理论上取得的成就，在具体分割算法的研究上也取得了很多新的 研究成果【3 ，4 1 。 i 3 图像分割技术现状 作为计算机视觉和图像处理中的关键技术之一，图像分割的研究受到了众多学者 的关注。自2 0 世纪7 0 年代以来，已提出了上千种类型的图像分割方法。如：阈值分 割法、区域分割法、边缘分割法、聚类分割法、图论分割法及其他很多特定理论的图 像分割方法等，本节对几类图像分割方法进行了简要概述。 ( 1 ) 阈值化分割方法 阈值分割法是灰度图像分割普遍采用的方法，这种方法先确定一个处于图像灰度 取值范围之中的灰度阈值，然后将图像中各个像素的灰度值都与这个阈值相比较，并 根据比较结果将对应的像素划分为两类：像素的灰度值大于阈值的为一类，小于等于 阈值的为另一类。这两类像素一般分别属于图像中的两类区域( 也称为前景和背景) ， 所以对像素根据阈值分类达到了区域分割的目的。 阈值分割的关键在于阈值选取，根据使用图像的整体信息还是局部信息可以分为 上下文相关( c o n t e x t u a l ) 方法和上下文无关( n o n c o n t e x t u a l ) 方法；根据阈值的作用范围 分为全局阈值法( g l o b a lt h r e s h o l d i n g ) 、局部阈值法( 1 0 c a lt h r e s h o l d i n g ) 。阈值的选取除 了取决于图像灰度值和该点邻域的某种局部特性之外，所选的阈值还应该与像素点的 位置有关。常用的阈值选取方法有：极小值点阈值选取方法、最佳阈值搜寻方法和迭 代阈值选取方法等。阈值法是研究最早也最成熟的图像分割方法，主要应用于灰度图 像，表1 1 列出了几种常见的阈值分割方法。 阈值分割的方法很多，每一种方法几乎都有其独特的优点和实际应用的背景。总 体来讲，阈值分割适用于特征空间峰谷明显，目标和背景的灰度分布接近正态分布、 细节较少且分割目的为提取特定目标的简单图像。阈值分割的优点是计算简单，分割 速度较快。然而它的缺点也很明显：首先，对于大多数目标和背景的灰度分布未知、 峰与峰之间重叠、彼此遮掩的情况甚多以至于难以分辨的图像，它们的分割阈值难以 第一章绪论结合图论与聚类算法的自然场景图像分割方法研究 确定；其次，通常阈值选取仅利用了像素信息，对内容复杂、细节较多的图像分割效 果较差。同时阈值方法大都是基于这样的假设：图像中目标和背景的灰度级区间是严 格分开的。然而实际应用中由于自然场景图像光照不均或噪声干扰，这样的假设并不 总是成立的。在这种情况下，阈值分割需要和其它方法相互结合使用，才能获得最佳 或满意的分割结果。 表1 1 几种常见的基于阈值的图像分割方法 准则阈值化方法优点缺点 分割得到的目标和背景 p 分位数( p - t i l e )无需任何迭代和搜索。 严重依赖先验概率的 的概率应该等于其先验法 5 l额估计。 概率。 最优阈值位于目标和背 最频值法( 也称 计算简单要求直方图具有明显 景两个概率分布的交叠m o d e 法) 【6 】的双峰特性 处。 使目标类和背景类的类 o t s u 方法【7 】计算简单、效果稳定要求目标与背景的面 内方差最小、类间方差最积相近 大。 图像的某种后验熵最大熵方法【8 】计算简单对直方图模型有要求 b a y e s 判断误差最小 最小误差法【9 】计算简单，适用于目标 对直方图模型有要求 与背景很不均衡的图像 分割前后图像的矩保持矩不变门限法1 1 0 l无需任何迭代和搜索稳定性不佳 不变 图谱划分测度图谱阈值法【1 1 1二值化分割效果较好在图谱划分时计算复 杂 ( 2 ) 基于边缘检测的方法 这类方法主要基于图像灰度级的不连续性，通过检测不同均匀区域之间的边界来 实现对图像的分割，这与人们的视觉过程有些相似。根据执行方式的不同，该类方法 通常又分为串行边缘检测技术和并行边缘检测技术。 串行边缘检测技术首先要检测出一个边缘起始点，然后根据某种相似性准则寻找 6 结合图论与聚类算法的自然场景图像分割方法研究第一章绪论 与前一点同类的边缘点，这种确定后继相似点的方法称为跟踪。根据跟踪方法的不同， 这类方法又可分为轮廓跟踪、光栅跟踪和全向跟踪三种方法。相比于其余两种方法， 全向跟踪可以克服由于跟踪的方向性可能造成的边界丢失，但其搜索过程会付出更大 的时间代价。串行边缘检测技术的优点在于可以得到连续的单像素边缘，但是它的效 果严重依赖于初始边缘点，由不恰当的初始边缘点可能得到虚假边缘；较少的初始边 缘点可能导致边缘点漏检。 并行边缘检测技术通常借助空域微分算子，通过模板与图像卷积完成，因而可以 在各个像素上同时进行，从而大大降低了时间复杂度。常见的边缘检测方法有r o b e r t s 算子、l a p l a c i a n 算子、s o b e l 算子、p r e w i t t 算子、k i r s h 算子、w a u i s 算子、l o g 算 子、c a n n y 算子等。 上述算法和其他边缘检测算法虽然在检测的准确性和边缘定位精度上有所差异， 但是他们都有一个共同的缺点，即不能得到连续的单像素边缘，而这对于分割来说是 至关重要的。所以，通常在进行边缘检测以后，需要进行一些边缘修正的工作，如边 缘连通、去除毛刺和虚假边缘。此外也有人使用f a c e t 模型或h o u g h 变换检测边缘， 但是这两种方法的复杂度往往是让人难以忍受的。 同传统的边缘检测算法相比，s n a k e 模型从另一个角度探讨了边缘检测问题。首 先，给出一条封闭曲线作为初始的边缘轮廓。此后，一方面使用梯度场作为外力，让 曲线尽量靠近真实边缘；另一方面使用曲线长度、平滑程度等作为内力，约束曲线的 形状。在这两种力量的共同作用下，最终得到精确的、连续的物体边缘。这种方法省 去了对边缘繁琐的后处理，但是这却是以提供初始轮廓为代价的。由于图形信息所提 供的外力场是很微弱的，所以初始轮廓应当比较接近真实边缘，否则算法可能无法收 敛到真实边缘。 ( 3 ) 基于区域的分割方法 基于区域的图像分割技术就是把图像分裂成像素集合，按照灰度值的相似性将像 素划归到各个区域。基于区域相关的阈值化分割方法有：直方图转换法、基于二阶灰 度统计的方法、松弛迭代法、区域生长和分裂合并以及基于过渡区提取的分割方法等。 r o s e n f e l d 、m a s o n 、w e s z k a 等人先后提出了直方图转换的几种具体方法，后来 w e s z k a 和r o s e n f e l d 对其进行了统一，即通过构造图像的灰度级。边缘二维散射图， 并计算在灰度级轴上的各种加权投影，可以得到上述所有变换后的直方图。后来w u 7 像分割。 分裂合并方法是把输入图像分成任意大小且不重叠的区域，然后再按照一定的相 似性准则合并或分裂这些区域以满足分割的要求。这类方法一般需要根据图像的统计 特性设定图像区域属性的一致性测试判断准则。因此，这个准则设定的好坏直接影响 着分割的质量。常用的分裂方法有：金字塔分割法、分水岭( w a t e r s h e d s ) 算法。合并算 法中两种最常用的有r a g ( r e g i o na d j a c e n tg r a p h ) 算法、n n g ( n e a r e s tn e i g h b o rg r a p h ) 算法。近年来，一些基于进化论的合并方法也提出来了，这些方法不需要使用任何阈 值，但大多数收敛速度很慢。 8 结合图论j 聚类算法的自然场景图像分割方法研究 第一章绪论 基于过渡区提取的分割方法是近年来兴起的一种新的图像分割方法，基本思想 是：根据某种准则提取过渡区像素，由过渡区像素的灰度均值或其灰度直方图峰值对 应的灰度值作为分割门限。基于过渡区提取的分割方法的优点在于，它既利用了像素 分布的空间信息，可以较好地定位边界，又利用了直方图阈值分割的简单、抗噪性能， 但其理论研究还很不完善，现有方法的缺点是抗噪性能仍不够理想，过渡区提取不稳 定等。 ( 4 ) 基于特定理论的分割方法 在理论研究上，每当有新的理论和方法提出来，人们就试图将其应用于自己的领 域，在图像分割方面的研究亦如此。图像分割技术的发展与许多其它学科和领域，如 数学、物理学、生物学、电子学、计算机科学等学科密切相关。由于图像分割的复杂 性，每当有新的数学工具或方法提出来，人们就尝试着将其用于图像分割，因而提出 了不少特殊的算法，如利用马尔可夫随机场( m a r k o vr a n d o mf i e l d ) 1 5 】、隐马尔可夫模 型( h i d d e nm a r k o vm o d e l s ) 、g i b b s 随机场，分形( f r a c t a l ) 、g a b o r 滤波器、分形几何、 动态规划、组合优化、数学形态学( m a t h e m a t i c a lm o r p h o l o g y ) 1 1 6 1 神经网络( n e u r a l n e t w o r k s ) 、模拟退火( s i m u l a t e da n n e a l i n g ) 、遗传算法( g e n e t i c g o r i t h m ) 、蚁群算法 ( a n tc o l o n ya l g o r i t h m ) 、小波分析理论和信息论【1 8 1 等理论的图像分割方法 1 9 1 。 1 4 图像分割技术的评价标准 图像分割评价是通过对图像分割算法性能与分割结果的研究以达到优化分割的 目的，分两种情况：( 1 ) 掌握各算法在不同分割情况中的表现，以通过选择算法参数 来适应分割具有不同内容的图像和分割在不同条件下采集到的图像的需求；( 2 ) 比较 不同算法在分割给定图像时的性能，以帮助在具体分割应用中选取适合的算法或改进 已有的算法。 为达到分割评价的目的，对评价方法提出的基本要求有。第一、应具有通用性， 即评价方法要适用于评价不同类型的分割算法并适用各种应用领域情况；第二、应采 用定量的和客观的性能评价标准，定量是指可以精确地描述算法的性能，客观是指评 价摆脱了人为的因素；第三、应选取通用的图像进行测试以使评价结果具有可比性， 同时这些图像应尽可能地反映客观世界的真实情况和实际应用领域的共同特点。图像 9 第一章绪论 结合图论与聚类算法的自然场景图像分割方法研究 分割的评价方法分为分析方法( a n a l y t i c a lm e t h o d s ) 与经验方法( e m p i r i c a lm e t h o d s ) 两 种。分析方法主要是对算法本身进行参数分析，如算法复杂度等。复杂度越大说明算 法运算时间越长，算法越差。分析法直接研究分割算法本身的原理特性，通过分析推 理得到算法性能。分析法评判算法只针对算法本身进行分析而不需要实现算法，在评 价时不会受到实现算法时产生的误差近似等影响。实验方法则根据分割图像的质量间 接地评价算法的性能，用待评价的算法去分割图像，然后借助一定的质量测度来判断 分割结果的优先。可以进一步分为经验好坏评价方法( e m p i r i c a lg o o d n e s sm e t h o d s ) 和经 验差异度方法( e m p i r i c a ld i s c r e p a n c ym e t h o d s ) 。经验好坏评价方法不需要客观分割结 果，使用区域非均匀性、熵等参数评价分割结果的好坏。经验差异度方法需要客观真 实的分割结果作为参照进行评价，所涉及的参数衡量的是实际分割结果与理想分割结 果的“差异 。常见的差异度参数有最终测量精度、错分概率、变形率等等。经验好 坏的评价未使用参考图像，其结果受不同图像的影响较大。经验差异度是一种经常使 用的客观评价方法，但客观真实分割结果一般由人工分割得到，本身具有一定的主观 性且工作量较大，差异度参数的构造往往也是局限于某类图像的评价。文献 2 0 】曾提 出一种包含性能分析、图像合成、算法测试三个模块的分割评价框架。该框架可用于 评价大多数分割算法，并有助于选择合适的图像分割方法。 尽管已经提出了许多的图像分割评价算法，图像分割的研究仍缺乏可靠的、通用 低，e g b i s 算法对 于图论的颜色一纹 组成块特征向量， 结合图论与聚类算法的自然场景图像分割方法研究第一章绪论 将邻域相关性引入到块间权重中，最后利用最小生成树缩减的方法进行图像分割。实 验表明该方法在分割强边缘图像与纹理丰富图像时比e g b i s 分割算法更鲁棒，同时分 割速度较n c u t 方法大幅提高。 ( 2 ) 由于传统聚类分割算法需要预先指定分类数、初始分类中心，在使用这些聚 类算法分割图像时，没办法做到完全的无监督。因此，本文提出了一种自适应a p 聚 类图像分割算法，根据图像的整体特征自动计算偏向参数，再利用分块的颜色、纹理 特征向量进行聚类分割，解决了传统聚类分割中初始值的确定问题，完全做到无监督 的图像分割。同时，试验结果表明，自适应a p 聚类分割算法的分割精度较传统的 k - m e a n s 、f c m 聚类分割算法更高。 ( 3 ) 为了在基于区域图像检索系统中检验自适应a p 聚类图像分割算法的实际应 用效果，提高图像检索系统中区域匹配准确率，论文提出了一种加权的区域匹配方法。 该方法利用各个目标区域的区域面积与各区域位置等信息计算区域之间的权值，并利 用改进的h a u s d o r f f 距离作为距离度量方法，最后进行加权区域匹配。r b i r 实验结 果表明，由于增加了重要区域的权重，同时减少了次要区域权重，显著改善了r b i r 系统的检索准确率。 ( 4 ) 针对聚类分割算法缺少空间关联信息，图论分割方法无法处理离散区域的问 题。论文提出一种新的基于图论与聚类的自然场景图像分割算法。该方法首先用图论 分割方法把图像分割成多个内部特征相似、空间相连的小区域；再利用区域特征的相 似性对每个小区域的区域特征向量进行聚类，把内容相同、空间分离的区域聚为一类， 实现自然场景图像的分割。该方法结合了聚类与图论分割算法的优点，有效的弥补了 两类算法各自的缺点。分割结果表明，新的分割算法在分割自然场景图像时较单独的 使用聚类分割或图论分割算法分割的准确性显著提高。 全文内容如下安排： 第一章介绍自然场景图像分割的研究背景、现状、主要应用及图像分割的分类， 通过分析自然图像的概念与特点，分析自然场景图像区域分割算法研究的理论价值与 现实意义，并给出图像分割常用的分割评价准则。 第二章分析总结各类基于图论的分割算法的特点与研究现状，提出基于图论的颜 色纹理区域分割算法，并给实验结果进行详尽分析。 第三章概述现有聚类分割算法，分析它们的优缺点，提出基于自适应a p 聚类的 第一章绪论 结合图论与聚类算法的自然场景图像分割方法研究 图像分割算法与加权图像区域匹配方法，并通过图像分割与图像检索的实验验证所 提方法的有效性。 第四章根据图论分割与聚类分割的特点，提出结合图论与聚类的自然场景图像分 割算法，并对实验结果进行客观评价。 第五章对本文完成的主要研究工作进行总结，并对进一步的研究工作进行展望。 结合图论与聚类算法的自然场景图像分割方法研究第二章基于图论的颜色纹理区域分割方法 第二章基于图论的颜色纹理区域分割方法 针对经典图论分割方法中，n c u t 方法分割效率低，e g b i s 算法在分割纹理图 像或有突变边缘的图像时，分割效果不理想的问题，本文提出了基于图论的颜色纹 理图像分割算法，采用分块的小波能量直方图与三阶颜色矩组成块特征向量生成图顶 点的集合，同时考虑邻域相关性计算块问权重，再计算块间的加权的相似度，作为图 的边权值，最后利用最小生成树缩减的方法进行图像分割，在有效弥补了e g b i s 分 割方法中的两个问题的同时，分割速度较n c u t 方法有大幅提高。 2 1 基于图论的分割方法概述 在过去的几十年中，基于图论的分割方法引起了人们越来越多的兴趣。是近年来 许多研究人员研究的热点问题。本节着重介绍了基于图论的图像分割方法，首先详细 地阐述了基于图论的分割方法的工作原理，然后分析了各类基于图论的分割方法的优 缺点和研究现状。 2 1 1 基本原理 基于图论的分割方法可以把图像映射为带权的无向图g = ( y ，e ) ，其中y 是由所 有结点，i 组成的集合，e 表示顶点与巧之间的边e 盯的集合。根据一定规则为每条 边计算一个边权值w ( ( v i ，1 ，) ) 。利用一定的最优化准则使分割结果中区域内的边有较 低的权值，区域间的边有较高的权值。常见的最优化准则有如下几种： ( 1 ) 图的最优划分准则2 2 】 图g = ( v ，e ) 被划分为彳、b 两部分，且有au8 = y ，a n b = ，节点之间的边 的连接权为w = ( ”，1 ，) ，则将图g 划分为彳、b 两部分的代价函数( c u ts i z e ) 为 c u t ( a ，b ) = w ( u ，1 ，) ( 2 - 1 ) “e - - e 占 当c u t ( a ，b ) 值最小时的划分即为图g 的最优二元划分，这种划分准则称为最小割 集( m i n i m u mc u t ) 准则。 ( 2 ) 图像的晟佳分割 第二章基于图论的颜色- 纹理区域分割方法结合图论与聚类算法的自然场景图像分割方法研究 将待分割图像映射为带权的无向图g = ( v ，e ) ，像素集被看作节点集以边缘集被 映射为边集e ，像素之间的连接权为w = ( f ，j f ) ，则将图像二值划分为两个集合( 区域) 么、b 的代价函数为 c u t ( a ，b ) = w ( u ，v ) ( 2 2 ) 对于一幅图像，使得上述代价函数最小的划分即为图像的最佳分割。 ( 3 ) 权函数 权函数一般定义为两个节点之间的相似度。在基于图论的图像分割方法中，常见 的权函数有如下形式【2 3 】 驴x p ( * 吨仃；卜乜砘一矿慨甜 ，( 2 - 3 ) 上式权函数中，对于灰度图像，f 的值为像素的灰度值，置为像素的空间坐标， 仃，灰度高斯函数的标准方差，盯r 为空间距离高斯函数的标准方差，为两像素之间 的有效距离，超过这一距离则认为两像素之间的相似度为0 。由相似度函数得出，两 像素之间的灰度值越接近则两像素之间的相似度越大，两像素之间的距离越近则其相 矩 从 值 阵 成 结合图论与聚类算法的自然场景图像分割方法研究第二章基于图论的颜色纹理区域分割方法 的对角矩阵即为度矩阵，度矩阵常用d 表示。 l a p l a c i a n 矩阵为l = d 一形，在图论分割算法中l a p l a c i a n 矩阵为常用的标准矩阵。 ( 5 ) 势函数、f i e d l e r 矢量及谱 势函数为代表某像素划分归属的指示矢量( i n d i c a t o rv e c t o r ) 。其定义为 f 1