（计算机应用技术专业论文）图像谱方法分割的研究及应用.pdf

摘要摘要图像分割是模式识别和图像处理的重要组成部分，针对具体的图像有不同的分割方法，其中基于图论的图像谱方法分割是近年来国际上图像分割领域的一个新的研究热点。尽管谱聚类算法具有坚实的谱图理论基础，并且在实践中也得到了很好的应用效果，但仍存在许多问题：如何建立节省空间的快速谱聚类算法，使用什么核函数构造邻接矩阵，如何自动确定谱聚类的数目。本文针对以上问题做了一些具体的研究，首先，从理论上分析了谱分割的n y s t r o m采样快速算法，由于可以通过1 的样本点对总体样本做出比较准确的估计，所以与传统经典的谱方法分割相比，大大的降低了空间和时间复杂度，并且通过具体实验与传统谱方法比较，总结了n y s t r o m 采样的谱分割的优点。其次，重点考虑到衡量两个样本间相似度的核函数对整个谱聚类的重要性，首次提出使用了权重马氏距离高斯核计算样本的相似度矩阵。与欧氏距离和普通的马氏距离相比较，马氏距离消除了欧氏距离中各个指标量纲不同，各个量纲相关性对计算结果的影响，然而，在计算两个特征向量之间的距离的时候，马氏距离只粗略的认为两个向量属于同一个类，同分布，没有考虑到两个向量不属于同一个类时，结果依赖于类规模大小的情况，所以，本文提出的加权马氏距离高斯核更能贴切的反映两个样本之间的相似度，并且通过具体的分割实验结果，验证了这种核函数的优越性。再次，考虑到每次手动的调整谱聚类的中心数，对分割结果有很大的影响，针对具体的实验，尝试提出了一种自动的聚类方法，这种方法简单累加各个向量的指标相似度，达到一定的相似度阈值归为一类，结果得出的极少的孤立的游离向量可以归入相似的类内，实验结果表明，这种做法能得到比较理想的结果，但是缺陷在于，必须针对具体的图像调试具体的相似度阈值。最后，分析了一种新的谱分割算法：基于图谱理论的图像分割方法，这种方法不但运算时间短，而且分割效果比一般的阂值分割方法效果好，考虑到这种方法要调整参数以找到合适分割效果，本文将马氏距离高斯核和自行提出的局部马氏距离高斯核应用于其中，避免了调整参数对分割效果带来负面影响的同时，获得了很好的分割效果。关键词：图论；谱聚类；n y s t r o m 估计；帅；模式识别；图像分割；n c u ta b s t r a c ta b s t r a c ti m a g es e g m e n t a t i o ni sa ni m p o r t a n te l e m e n to fp a t t e r nr e c o g n i t i o na n di m a g ep r o c e s s i n g t h e r ea r em a n yd i f f e r e n ti m a g es e g m e n t a t i o nm e t h o d s ，o n eo fw h i c hi si 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 di ti sn e w l yd e v e l o p i n gt e c h n i q u ei nr e c e n ty e a r s ；i tf i r m l yb a s e so ns p e c t r a la n dg r a p ht h e o r y , a n di sw i d e l ya p p l i e dt op r a c t i c e ，b u tt h em a i nc h a l l e n g e so ft h et e c h n i q u ea r eh o wt oc o n s t r u c tt h es i m i l a r i t ym a t r i x ，h o wt or e d u c et h et i m ec o m p l e x i t yo ft h ea l g o r i t h m ，a n dh o wt oj u d g et h en u m b e ro ft h ec l u s t e r i n ga u t o m a t i c a l l y i nt h ep a p e r , i tr e s e a r c h e st h ei m a g es e g m e n t a t io nb a s e do ns p e c t r a lt h e o r yf r o md i f f e r e n ta n g l e st or e m o v et h eo b s t a c l e sm e n t i o n e da b o v e f i r s t l y , i ta n a l y z e st h ea l g o r i t h mn a m e ds p e c t r a lg r o u p i n gu s i n gt h en y s t r o mm e t h o d ，c o m p a r e st h ep e r f o r m a n c eb e t w e e nt h ea l g o r i t h ma n dt r a d i t i o n a ls p e c t r a ls e g m e n t a t i o nm e t h o dt os u m m a r i z et h ea d v a n t a g e so ft h ea l g o r i t h m b e c a u s et h et i m ec o m p l e x i t yo ft h ea l g o r i t h mi sl o w e rt h a nt h et r a d i t i o n a lo n eo b v i o u s l y s e c o n d l y , b e c a u s ei ti ss i g n i f i c a n tt ou s et h es u i t a b l ek e r n e lf u n c t i o nf o rc o m p u t i n gt h es i m i l a r i t ym a t r i xi nt h ea l g o r i t h m ，i ts t r u c t u r e san e wk e r n e lf u n c t i o nn a m e dw e i g h t e dm a l l a l a n o b i sd i s t a n c eg a u s s i a nk e r n e la tt h ef i r s tt i m e s i m u l t a n e o u s l y , i ti n t r o d u c e ss e v e r a lk e r n e lf u n c t i o n sf o rc o m p u t i n gt h ea f f i n i t ym a t r i x ，a n da n a l y s e st h e i re f f e c t i ta l s oa n a l y s e st h a tw e i g h t e dm a h a l a n o b i sd i s t a n c ei sm o r ea p p r o p r i a t ef o rc o m p u t i n gt h es i m i l a r i t yb e t w e e nt w op i x e lt h a nm a h a l a n o b i sd i s t a n c e ，u s e sw e i g h t e dm a h a l a n o b i sd i s t a n c eg a u s s i a nk e r n e lf o rn y s t r o m - n c u ts e g m e n t a t i o nt oo b t a i nab e t t e rs e g m e n t a t i o nr e s u l t t h i r d l y , b e c a u s et h en u m b e ro ft h es e g m e n t a t i o nb l o c ka f f e c t st h es e g m e n t a t i o nd i r e c t l y ，i no r d e rt oj u d g et h en u m b e ro fc l u s t e r i n ga u t o m a t i c a l l y , i ti m p o r t sas i m p l ec l u s t e r i n gm e t h o di n s t e a do fk - m e a n sf o ra t t a i n i n gab e t t e rr e s u l t ，b u tt h em e t h o dm u s te s t a b l i s hr e l a t e dp a r a m e t e r sb yd e b u g g i n gp r o g r a m s oi t sl i m i t a t i o n sm a k ei to n l ya p p l yt os o m es p e c i f i ci m a g e s h o w e v e r , i ts u p p l i e san e wm e t h o dt h a te s t i m a t et h en u m b e ro fc l u s t e r i n gf o rs p e c t r a lc l u s t e r i n g a tl a s t ，i ti n t r o d u c e san o v e lt h r e s h o l d i n ga l g o r i t h mb a s e do ns p e c t r a lm e t h o dw h i c ha c h i e v e si m p r o v e di m a g es e g m e n t a t i o np e r f o r m a n c ea tl o wc o m p u t a t i o n a lc o s t t h ea l g o r i t h ms h o w st h es u p e r i o rp e r f o r m a n c ec o m p a r e dt oe x i s t i n gt h r e s h o l d i n ga l g o r i t h m b u ti tn e e d st oa d j u s tp a r a m e t e r sf o rf i n a ls e g m e n t a t i o n s o m e t i m e s ，e v e ni fi ta d j u s t sp a r a m e t e r s ，t h er e s u l to ft h es e g m e n t a t i o ni sn o ts a t i s f a c t o r i l y ；i tc o n v e n i e n t l yi m p l e m e n t st h ea l g o r i t h mu s i n gt h em a h a l a n o b i sg a u s s i a nk e r n e lo rl o c a lm a h a l a n o b i sg a u s s i a nk e r n e ls t r u c t u r e da tt h ef i r s tt i m e ，a n do b t a i n sc l e a rr e s u l t sb u tn o tt oa d j u s tp a r a m e t e r s k e y w o r d s ：g r a p ht h e o r y ；s p e c t r a lc l u s t e r i n g ；n y s t r o ma p p r o x i m a t i o n ；w e i g h t e dm a h a l a n o b i sd i s t a n c e ；p a t t e r nr e c o g n i t i o n ；i m a g es e g m e n t a t i o n ；n o r m a l i z e dc u t s独创性：声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。签名：尊铂& 一日期：i 趟丛二一关于论文使用授权的说明本学位论文作者完全了解江南大学有关保留、使用学位论文的规定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。签名：导师签名：盔歪鑫一日期：山形p 多，孑第一章绪论第一章绪论1 1 研究背景模式识别是一门以应用为基础的学科，目的是将对象进行分类。这些对象可以与应用领域有关，它们可以是图像、信号波形或者任何可测量且需要分类的对象。早在2 0世纪6 0 年代以前，模式识别主要是统计学领域中的理论研究，但计算机的发展提高了模式识别实际应用的需求，而反过来又对理论发展提出了更高的要求。模式识别的重要性主要体现在应用领域的广泛性和迫切性，它在很多方面都与机器视觉和图像处理密切相关。要在这些应用领域中达到预期的目标，模式识别还依赖于一些其他学科的发展，如计算机图形学和计算机视觉等。模式识别大体可以分为模板匹配、句法、神经网络方法、统计模式识别、结构模式识别五种基本方法。聚类分析和聚类算法的研究是模式识别中很重要的一个分支，它广泛地应用于以上方法。一个模式识别系统一般包括以下几个部分( 如图卜1 ) f l 】：1 数据获取：这通常取自一些传感器。2 目标分割：将需要的对象从背景中分割出来，它是模式识别中最深层的问题之一，且依赖于具体的问题和具体的领域。3 处理：目的是去噪声，加强有用的信息，进行归一化，并对一些退化现象进行复原。4 特征形成提取选择：特征形成是指由传感器测得的一组基本向量，这样的特征称为原始特征，应该取尽可能少的但显著的特征，这会降低测量的代价，也会使分类器的设计变得简单。而特征提取是对这些原始特征进行变换，以得到有利于分类、更本质、更少的新特征。特征选择是在给定的一组特征中选择一个子集的过程。希望获得的特征是：保持信息，且来自同一个类的不同模式的特征非常接近，不同类的模式的特征相距很远。5 学习：根据特征提取得到的特征设计分类器，完美性能的分类器通常不可获得。学习是重要的，过去2 5 年来的反复实验和经验表明从样本集的学习是设计分类器的最有效方法。6 分类：利用分类器给待测试模式一个类别标记。分类的难易程度取决于两个因素，分别是来自于同一个类别的不同个体之间的特征波动和属于不同类别的样本的特征值之间的差异。7 后处理：根据分类结果评价分类器性能，分类器性能的一个简单度量是分类器的错误率。以上提及的每一步，这些步骤的操作相互独立，但其区分也不是绝对的，在应用中有些步骤可以合并。江南大学硕士学位论文训练阶段分炎缔果测试阶段图1 - 1 统计模式识别系统f i g 1 - 1s y s t e mo fs t 撕s f i e a lp a r e mr e c o g n i f i o n可以运用模式识别聚类方法进行图像分割【2 】。根据图像特点和处理目的，提取每个像素的特征，设每个像素提取n 个特征，这些特征的数值便是该像素所对应的模式特征点在n 维特征空间中的坐标。如果特征选取较好，那么在特征空间中，图像像素的特征点往往表现出类聚，此时运用模式识别聚类技术对特征点进行分类，特征点的类别反映了对应像素的类别，从而实现图像分割。在一些情况下，由于特征是区域性的，所以不是针对某个像素而是针对各个像素的邻域或图像的各个子图提取n 个特征。对于绝大多数图像像素，最基本的特征是灰度。传统的图像处理方式中的图像分割是以灰度为特征的像素或区域分割技术，将灰度直方图的谷点作为门限的图像分割方法实际就是在一维灰度特征空间的分类。除了用像素灰度作为特征，若还利用像素其他特性作为特征，根据这些特征进行像素分类，图像分割效果会更好。通常还利用灰度和空间关系的信息，如像素的梯度、像素小块邻域平均灰度以及纹理参数和颜色等。选用什么特征用于分类是十分重要的，他决定能否进行有效的图像分割，所选取的特征应能反映像素或像素间关系的主要属性，同时特征应具有可分性，即不同的类型区域中的像素所具有的这些特征值显著不同，并且特征之间相关性不大，一个特征值不能由别的推倒或者推论出来，否则不仅没有带来任何新的信息反而可能会增加分类的困难或开销。特征个数以能实现正确分类所必须的最少个数为好。常用的分类方法可参阅模式识别书籍【3 】。目前，利用模式识别的某些技术进行图像分割的一般有，利用聚类算法和坐标变换进行分类，利用神经网络知识分类，利用谱图理论的谱聚类进行图像分割，本文主要针对谱聚类图像分割方法进行研究。1 1 1 图像分割图像是客观世界能量或状态以可视化形式在二维平面上的投影，是社会生活中最常见的一种信息媒体。它传递着物理世界的能量和食物状态信息，是人类获取外界原始信息的主要途径。“图是物体投射或放射光的分布，“像是人的视觉系统对图的接受在大脑中形成的印象和反映，是主观和客观的结合。在生产、科研或日常生活中看到的场景图像，包含着物体的“大量的信息，通过感觉、知觉、记忆、认知、搜索、形成2第一章绪论概念，直到最终理解和识别视觉刺激。数字图像处理实际上是利用计算机对图像信息进行加工处理，以改善图像质量、压缩图像数据或从图像中获得更多信息。在模式识别中，对图像的分割更感兴趣。为了有效地进行图像描述和分析，往往需要先将图像划分成若干个有意义的区域。要输出气泡的轨迹坐标，应先将气泡的轨迹从背景分离出来；要得到地貌图和目标，应根据各种类型区域不同的反射特性，将城区、农田区、森林区、水域及目标等划分开；要获得物体间的关系，应将各物体区域划分开。这种为后续工作有效进行而将图像划分为若干个有意的区域的技术称为图像分割( i m a g es e g m e n t a t i o n ) 。这里所谓的“有意义一是指所分割的图像区域与场景的各个目标及背景的像相一致。但从实际上讲，所谓“有意义 是指所进行的图像分割便于后续工作实现既定的目标和任务。图像分割在图像处理、分析和理解和部分模式识别中是十分重要的技术环节，图像分割的质量的优劣、区域界线定位的精度直接影响后续的区域描述以及图像的分析和理解。显然图像分割所遵循的基本原则是，使区域内部所考虑的特征或属性是相同或相近的，而这些特征或属性在相邻的区域中则不同，存在差异。目前有许多图像分割方法，从分割操作策略上讲，可以分为基于区域生成的分割方法、基于边界检测的分割方法和区域生成与边界检测的混合方法。所谓基于区域生成的方法，就是直接找出特征相近的像素点，从而生成区域，本文要研究的图像的谱方法分割从一定意义上讲就是区域生成方法的图像分割；基于边界检测方法是，首先检测出图像特征不一致性所在点，并将他们连成边界，这些边界就将图像分成许多区域；第三种方法是根据特征同一性准则，特征相近的像素点形成区域，不一致之处的点连成边界。从方法上讲，可以直接根据灰度大小进行分割，也可以根据灰度分布进行分割，还可以根据图像模型进行分割。虽然有许多图像分割方法，但至今还没有找到对任何图像都有效的图像分割算法，就是说任何一种分割算法都有他的局限性和针对性。因此要使图像分割效果好，应充分利用对象知识，所采用的分割方法和对象的特点要“匹配 。实践表明，一个提高图像分割效果的途径是将一些分割算法组合起来形成一个系统，根据图像的特点，分层次有针对性地使用不同的分割算法。图像分割所依据的属性或特征可能是像素的灰度、小区域的平均灰度、灰度方差、小区域的灰度分布、灰度纹理、像素点或小区域的颜色等等。由于几乎各种不同的颜色都可以由红绿蓝三基色按照某种比例混合而成，所以在本文中都将彩色图像转为灰度图像处理，主要以图像“灰度 和像素点的空间位置为基本属性进行讨论。图像分割可以看作是模式识别问题，图像分割可以形式化定义如下：令有序集合r 表示图像区域( 像素点集) ，对r 分割时将r 分成若干个满足下面5个条件的有序非空子集足，足，r ：3江南大学硕士学位论文1 ) ur = 尼i = l2 ) r n 尺，= ，v i ，jf 3 ) 尸( r ) = t r u e ，v i o4 ) 尸( ru r j ) = f a l s e ，f 职与尺，相邻。5 ) 足；是连通区域，v i 式中，p ( r ，) 是对集合尺；中所有元素的逻辑谓词，即属性或特征均一性准则，o 是空集。条件1 ) 表示图像中任一个像素点都属于某一个子区域，即分割是彻底的；条件2 )表示一个像素点不能同时属于两个区域，即区域不能重叠；条件3 ) 表示区域内各像素点属性或特征是相近的；条件4 ) 表示相邻的两个区域属性或特征是不同的；条件5 )表示同一个区域中像素点是连通的。除了图像描述分析需要图像分n 多 i - ，在图像编码和很多模式识别方法中，某些技术都是在图像分割之后进行的。有一些具体的图像分割方法如下，边界检测的基本方法，拟合曲面求导提取边界，统计判决法提取边界，模糊数学方法提取边界，直方图比较法确定分割灰度门限，利用模式识别某些技术进行图像分割等等，本文主要研究的是利用模式识别的谱聚类的基于图论的图像分割。1 1 2 基于图论的图像分割简介基于图论的图像分割技术是近年来国际上图像分割领域的一个新的研究热点。该方法将图像映射为带权无向图，把像素视作节点，利用最小剪切准则得到图像的最佳分割。该方法本质上将图像分割问题转化为最优化问题，是一种点对聚类方法，对数据聚类也具有很好的应用前景。但由于其涉及的理论知识较多，应用还处在初级阶段。首先看看怎么对图进行划分，再按上面陈述的方法把图像映射为带权的无向图就可以实现对图像的划分了。令图僻( v ，e ) ，要将图g 划分为两个部分a 、b ，且有a u b = v ，a f i b = o ，节点之间的边的连接权存放在邻接矩阵w ( m ，v ) 中，节点间的连接权可以通过权函数求得。则将图g 划分为a ，b 两个部分的代价函数为：c u t ( a ，b ) = w ( u ，d( 1 1 )_ y 口使得式( 1 1 ) 的剪切值最小的划分( a ，b ) 即为图g 的最优二元划分，这一划分准则称为最小割集准则。这只是一种剪切准则，只对应一种分割方式，常用的剪切准则如表( 1 1 ) 1 4 1 所示。4第一章绪论表1 1 几种常见准则对比t a b 1 1t h ec o n t r a s to fc o m m o nc u t s准则准则形式特点m i n i m u mc u t 5 】a v e r a g ec u t 6 】n o r m a li z ec u t l 7 1m i n - m a xc u t 8 】r a ti oc u t t 9 1is o p e r i m e t r i cr a t i o 1 0 1c u t ( a ，b ) = w ( u ，力_ 彳v e b觚删埘2 箐+ 箐，：竺坚盟+ 丝! 丝! 堕a s s o c ( a ，v ) a s s o c ( b ，v )a s s o c ( a ，y ) = w ( u ，dm c u f ：c u t ( a , b ) + c u t ( a , b )w 【彳)w 【占)胁c 郇j i = 嚣c u ta 耠1 5，i，j心n f 罂，助丘为区域s 的体s 场t 。积，i 甜i 为s 边界所包含的面积易倾向于较小的分割易倾向于出现较大分割当类间重叠较大时，易出现歪斜划分后置处理需要花费大量时间速度较慢，可避免划分向短边偏移速度较快对图若按照以上准则划分时，不同的准则有不同的实现方式但基本上归纳为以下两种：一种是将最优准则转化为求解矩阵方程【6 】1 7 1 【8 1 【1 0 】，另一种方法是使用所定义的准则直接进行图缩减f 5 】 9 1 ；把图像按要求映射为图后，就可以按照以上方式进行图像分割了。1 1 3 聚类与谱聚类迄今为止，聚类还没有一个学术界公认的定义。这里给出e v e r i t t 1 1 l 在1 9 7 4 年关于聚类所下的定义：一个类簇内的实体是相似的，不同类簇的实体是不相似的；一个类簇是测试空间中点的会聚，同一个类簇的任意两个点间的距离小于不同类簇的任意两个点间的距离；类簇可以描述为一个包含密度相对较高的点集的多维空间中的连通区域，它们借助包含密度相对较低的点集的区域与其它区域相分离。聚类是数据挖掘、模式识别等研究方向的重要研究内容之一，在识别数据的内在结构方面具有极其重要的作用。聚类主要应用于模式识别的语音识别、字符识别等，机器学习中的聚类算法应用于图像分割和机器视觉。聚类的另一个主要应用是数据挖掘、时空数据库应用、序列和异类数据分析等。典型的聚类过程主要包括数据( 或称为样本) 准备、特征选择和特征提取、接近度计算、聚类、对聚类结果进行有效性评估等步骤【1 2 】 1 3 1 14 1 。没有任何一种聚类算法可以普遍适用于揭示各种多维数据集所呈现出来的多种多样的结构。根据数据在聚类中的积聚规则以及应用这些规则的方法，有多种聚类算法。江南大学硕士学位论文聚类算法可以大致分成层次化聚类算法、划分式聚类算法、基于密度和网格的聚类算法和其他聚类算法。最近几年，谱聚类方法在模式识别中得到了广泛的应用。与传统的聚类方法比较，他具有能在任意形状的样本空间上聚类，且收敛于全局最优解的优点。为了能在任意形状的样本空间上聚类，且收敛于全局最优解，研究者开始用谱方法来聚类。谱方法聚类是由数据点间相似关系建立矩阵，获取该矩阵的前n 个特征向量，并且由它们来聚类不同的数据点。谱聚类方法建立在图论中的谱图理论上。s h i 和m a l i k 吲在2 0 0 0 年根据谱图理论建立2 - w a y 划分的n o r m a l i z e d c u t ( n c u t ) 的目标函数，设计了用于图像分割的算法。图像的谱方法分割在本质上和图论方法相一致，此类算法不必如基于图论的方法针对具体的剪切准则求解分割，而是可以直接对原图像构造亲和力矩阵( 即相似度矩阵或邻接矩阵) w 或l a p l a c i a n 矩阵l ，然后求解矩阵的特征矢量并以此为基础直接或迸一步构造矢量指导分割。目前几种常用的谱分割方法如下表( 1 2 ) ：。表1 2 几种常见的谱分割算法t a b 1 2s e v e r a ls p e c t r a ls e g m e n t a t i o na l g o r i t h m s其中，文献1 1 7 】是一种较规范较常用的谱分割方法，本文的后续研究和实验，基本都是建立在此基础上。1 1 4 谱聚类的由来将数据集看做一个图中所有顶点的集合，顶点之间的连线权重表示数据点之间的相似性程度，如果数据点在一个连通分支之内，就认为其处于同一个类中，这样将聚类问题转化为图的连通性问题【1 8 】。据此可以提出基于最小( 大) 生成树( m i n i m u m m a x i m u ms p a n n i n gt r e e ) 【1 9 j 的聚类算法。基本思想是通过删除最小( 大) 生成树中满足特定条6第一章绪论件的边，然后检查连通性得到各个类。具体说来，现在常用的条件有如下两条：( 1 )如果预知聚类的类数k ，则可以将最小( 大) 生成树中的边权重降序排序，删除k - 1 条具有最大( 小) 权重的边即可。( 2 ) 聚类的类数预先并不知道，但是知道不合适边的权重阈值，删除权重大于此阈值的边即可。但是以上算法受到最小( 大) 生成树本身结构的影响，特别是其中边的权重分布的影响。如果一类中的权重普遍大于另一类中的权重，可以预想以上算法不会有好的聚类结果。如图( 卜2 ) 所示的聚类集，一般称如图( 1 - 2 ) 所示的聚类集为倾斜聚类集，用如上两种算法显然不会得到好的结果。最近，文献【7 1 中提出另一种基于图的聚类算法一一谱聚类( s p e c t r a lc l u s t e r i n g )一刊o n i l a li z e dc u t ，可以很好地对上述样本进行聚类。谱聚类是一种能根据顶点之间的权值对图进行划分的方法，本质上它是一种基于矩阵特征向量提取新数据特征的方法。图l _ 2 倾斜数据集f i g 1 2s l o p ed a t as e t最早理论上把图的划分问题与相似矩阵有关的特征向量( 矩阵谱分析理论) 联系起来的是d o n a t h 和h o f f m a n 的文献1 2 0 】，同一年，f i e d l e r 2 l 】证明图的两划分问题与拉普拉斯矩阵的第二特征向量密切相关，他建议用该向量进行图划分。但是在机器学习领域中，文献中最早将聚类、图划分问题和相似矩阵有关的特征向量联系起来，并构造了实用算法的是h a g e n 和k a h n g ，他们于1 9 9 2 年提出的r a t i oc u t 2 2 】引入了类规模平衡项来最小化类间相似度，建立了基于矩阵谱分析的聚类算法。c h a n ，s c h l a g 和z i e n 又在1 9 9 4 年提出了一种多路率切判据算法f 2 3 】。但倾斜划分的问题始终没有更好的解决。2 0 0 0 年，s h i和m a l i k 提出n o r m a li z e dc u t 7 1 ，较好的解决了m i nc u t 将少数样本点孤立为一类的倾斜问题。为了解决倾斜问题，d i n g ，h e 和z h a 也于2 0 0 1 年提出了m i n - m a xc u t 8 】，n g 等人在2 0 0 2 年提出n j w 方法【1 7 1 ，上述算法的本质部分都是基于矩阵谱分析理论，因此这类算法统称谱聚类。目前，由于文本处理、生物信息处理等特殊的需求，需要处理不同对象之间的联合聚类，简称异质聚类。因为二部图可以表示两种对象及它们的相互关系，因此对异质聚类可以很自然的转换为二部图的划分问题。由于谱聚类可以处理图划分问题，自然容易想到谱聚类也可以解决这类二部图划分问题。d h i l l o n 2 5 】就利用矩阵谱分析理论对二部图进行划分，高等人【2 6 】更将此理论用来解决具有星状结构的多种对象联合聚类问题，提出了相容联合聚类算法，同样是基于矩阵谱分析理论。这些算法的提出证明了机器学习快速发展的另一个重要动力实际应用驱动。7江南大学硕士学位论文1 2 研究现状首先，分析基于图论的图像分割的研究现状：1 ) 最优剪切准则的设计；如表( 1 1 ) 所示，针对基于图论的图像分割，现在已经提出了不少剪切准则，但是各个准则都有自己对应的优缺点。2 ) 谱方法用于图像分；g i j ；目前已经提出了几种谱方法，但是研究空间很大，也是一个研究热点，这正是本文研究的基础，本文将基于其中常用的谱方法做改进。3 ) 快速算法设计；由于谱分割计算相似度矩阵及其特征向量浪费时间和空间，所以研究者针对性的提出了许多改进的快速算法，如概率采样与s v d 估计【2 7 1 ，使用相似度矩阵w 稀疏【1 0 1 ，n y s t r o m 采样构造相似度矩阵【2 8 】1 2 9 等等，考虑到n y s t r o m 采样构造相似度矩阵方法估计的准确性和高效性，本文的实验基本基于这种快速算法。4 ) 其他图论分割方法；尽管谱聚类算法具有坚实的谱图理论基础，并且在实践中也取得了很好的效果，但是仍存在一些关键问题，以下再来看看谱聚类的研究热点和现状。1 ) 如何构造邻接矩阵w ：在谱聚类算法中，边的权值是顶点i 与j 的相似度s i m( i ，j ) ，故表示图的邻接矩阵w 也是样本空间的相似度矩阵。相似度矩阵的构造依赖于两个样本间相似度的构造。2 ) 自动地确定聚类的数目：聚类数目的确定对聚类的质量有很大的影响。当聚类数目大于实际聚类数，k - w a y 谱聚类的效果很差。因此如何自动地确定聚类数目是一个关键问题，是未来的一个研究方向。3 ) 运用到海量数据中去：当用谱聚类时，不可避免地要计算矩阵的特征值与特征向量。通常这种计算的代价很大，求解非稀疏矩阵的所有特征向量的标准解法需要o ( n 3 ) 。同时当应用到海量数据时，相似度矩阵也很大，可能会超出计算机内存。如前所述，n y s t r o m 采样构造相似度矩阵并估计它的主特征向量，能得到一个满意的结果。1 3 研究意义与目标虽然有许多图像分割方法，但至今还没有找到对任何图像都有特别效果的图像分割算法，就是说任何一种算法都有它的局限性和针对性。基于图论( 包括谱方法) 的图像分割技术是近年来国际图像分割领域的一个新的研究热点。虽然其分割技术表现出了比较好的结果，且得到了一定的实际应用，但是考虑到构造亲和力矩阵以及求它的特征向量，需要耗费大量的时间和空间，针对谱分割的这个缺点，研究者提出了不少的快速算法。其中n y s t r o m 采样的谱分割对这方面的工作做得很突出，就抽样部分像素求它们的相似度矩阵就能估计出这个图像的相似度矩阵及其主特征向量，用来指导分割。如前所述，尽管谱分割算法具有坚实理论基础，但是就目前状况而言，存在着一些关键问题，本文针对这些具体问题进行了尝试性的研究。首先，考虑到基于图论( 包含谱划分) 分割算法需要许多理论基础，而且在国内没有引起足够的重视，本文会系统的介绍基于图论的分割算法理论，谱聚类的理论，着重介绍n y s t r o m 采样的谱分割理论，同时通过比较得出它的优点。8第一章绪论其次，在构造邻接矩阵的时候，计算两个样本点的相似度的权函数种类很多，但是各有优缺点。考虑到计算相似度构造邻接矩阵是谱分割关键的一步，本文首次提出了权重马氏距离高斯核来计算两个样本的相似度，从理论上分析了它比欧氏距离核和马氏距离核的优势，而且从实验结果上得到了验证。再次，谱聚类中，聚类数目的确定对聚类的质量有很大的影响，因此如何自动地确定聚类数目是一个关键问题，是未来的一个研究方向。由于时间问题，本文只能仓促的尝试提出一种简单的聚类算法，针对具体的图像情况，手动调整门限后，可以实现自动聚类，得到比较好的结果，但是与最理想的结果有一点差距；希望在以后的研究工作中能提出一些比较通用的自动聚类算法，来解决谱分割面i 临的这种困境。最后，分析了种新的谱分割算法：基于图谱理论的图像分割方法，这种方法不但时间运算时间短，而且分割效果比一般的闽值分割方法效果好，本文对其做了一定的调整和改进，获得了很好的分割效果。基于图论的图像分割近年来成为图像分割领域的一个热点，在国内的一些刊物上也开始有一些研究成果，但是这些算法都基于比较多的理论知识，所以还没有得到充分的研究，同时希望能引起同行对这个领域的关注。1 4 论文结构本文由5 章组成，各章的主要内容安排如下：第1 章为绪论，分为4 个小节。第l 小节介绍了课题研究的背景；第2 小节简要介绍了课题研究相关内容的研究现状；第3 小节则介绍课题研究的意义和目标；第4 小节则介绍了本文的章节安排。第2 章是图谱分割理论基础。这一章主要内容是较全面的总结和回顾图像表示，图像分割，图像的谱分割，以及聚类的相关知识等等。第l 小节主要介绍了图像在计算机中的描述和用于谱分割的图像图的方式表示；第2 小节系统的回顾了基于图论得图像分割的主要方法；第3 小节则介绍了图像的谱方法分割和n y s t r o m 采样的谱分割；第4 小节详细的阐述了聚类的基本知识。第3 章是权重马氏距离高斯核在谱分割中的应用。在这一章中重点分析研究了权重马氏距离，构造出了权重马氏距离高斯核的形式，并应用于谱聚类中，效果理想。第1小节对n y s t r o m 采样的谱分割相关知识进行理论证明，列举常用核函数；在第2 小节中，权重马氏距离高斯的提出和研究；第3 小节里，对这些理论和实验进行总结。第4 章是谱分割中聚类改进和谱阈算法改进。这章主要分两个部分，谱分割的后期聚类改进和一种新方法( 结合谱图理论和阈值分割) 的研究。在第1 小节里，针对谱聚类的难点之一：确定聚类数，提出种后期聚类算法以试图确定聚类数；第2 小节中，对基于图谱理论的阈值分割算法的改进研究，并用大量实验揭露问题，解决问题；并在第3 小节中对整个章节进行总结。第5 章为总结与展望。在这一章里，主要是对本文进行了回顾总结，并对以后的工作和方向进行了展望。9江南大学硕士学位论文第二章图谱分割理论基础通过前面一章的介绍，可以了解到，基于图论的图像分割需要很多的理论基础，而且基于图论的图像分割( 包括谱分割) 的研究面临着一些困难，比如，怎样实现快速而且节省空间的图论图像分割，用什么核函数建立邻接矩阵，怎么样实现后期的自动聚类分割和自动确定聚类数。为了解决这些问题，本章的主要任务是详细的阐述这些理论基础，包括图像的描述，基于图论的图像分割理论分析，谱分割的理论分析，以及后期需要使用的聚类算法分析，通过这些理论基础的介绍，能更清晰的把握基于图论的图像分割算法原理，同时，有利于理解这些理论的联系，来针对性的尝试解决基于图论的图像分割( 包含谱分割) 所面临的困难。2 1 图像的描述和表示视觉活动是人类最重要的基本活动之一，人们在日常生活、社会活动、工作学习、科研生产中，无时无刻不在进行着视觉活动。视觉信息是人类获取外部知识、了解世界的主要途径和重要形式。据统计，人类大约有8 0 以上的信息是通过视觉获取的。在许多情况下，没有任何其他形式比图像传递的信息更丰富和真切。由于人类的视觉具有完善的感知能力，许多科研工作的中间或最后的结果数据都要以可视的图像形式表现出来，以利于人们对其理解、分析和应用。图像信息处理是研究人或机器对图像信号的产生和采集，信息的形成、提取、分析、综合、表达和利用的理论与方法的科学，是一门兼具综合性与交叉性的学科。它在理论上涉及数学、物理学、生理心理学、信号处理、控制科学、计算科学和技术等众多科学知识；该学科的理论任务是研究和发现信息的各种形式及各个阶段的内在转换规律，而其应用目标是研发出能帮助或代替人类视觉的智能机器系统。既然图像里包含了丰富的信息，要利用计算机进行数字图像处理之前，对图像的描述和在计算机中的表示就成了必要的工作。本节主要介绍图像的一些特征描述，同时考虑到基于图论的图像分割是把图像映射到图，所以还要介绍图这种数据结构，最后具体的阐述把图像映射到图的过程。2 1 1 图像的描述一副图像中含有大量的信息，有图像的灰度、色彩及角点、边缘和图像中目标的形状等等特征。但在研究中可能并不需要所有信息，根据研究的目标往往只对其中部分特征感兴趣，这不仅可以较好地提取了研究目标的特征，也降低了在处理过程中计算复杂度。针对图像处理的特殊性，图可以很好的描述图像的结构信息。图像是一个以像素为单位的矩形区域。常用的图像文件格式：b m p 、j p e g 、t i f e 、g i f 等。图像的描述是对图像各组成部分的性质和彼此之间关系的描述。图像特征是指图像场中可用作标志的属性，其中有些是视觉直接能感受到的自然特性，有些需要通过变换或测量才得到的人为特征。图像的描绘大体分为区域描绘、关系描绘等，区域描述1 0第二章图谱分割理论基础是在图像中感兴趣的区域被分割出来后，对各个分割区域特点的描述，如形状、凹凸度等，关系描述则是研究把这些区域组织为一个有意义的结构。常见的图像自然特征有亮度，彩色，纹理或轮廓等；人为特征有直方图，投影特征，标记，f o u r i e r 描绘子，矩特征，比例特征，边心矩，线条和角点特征等。1 ) 纹理特征：是指这区域由紧密混杂在一起的某些单元构成，这种单元或局部结构在比它更大的范围内大致作均匀重复排列。2 ) 直方图特征：统计各像素点的灰度值所得到的直方图，可用来估计图像的概率分布，从而形成一类特征。图像直方图的形状可给出图像特性的许多信息。3 ) 投影特征：将物体向x 轴和y 轴投影，由此获得的投影特征由于具有良好的比例、平移不变性，可以作为描述物体形状的特征。4 ) 标记：是一种当图像中有多个物体时，将它们分开来，以分别进行描述的方法。首先进行水平扫描，当找到一个物体区域时，将其赋予一个标号，在扫描完毕后，根据区域的连通性将相连区域的标号归并，这样，图像中的每一个物体都将具有一个唯一的标号，物体就被区分开来了。5 ) f o u r i e r 描绘子：由于区域的边界时一条封闭的曲线，因此相当于边界上某一固定的起始点玩来说，沿边界曲线上的一个动点b 的坐标变化则是一个周期函数。通过规范化之后，这个周期函数可以展开成f o u r i e r 级数。而f o u r i e r 级数中的一系列系数是直接与边界曲线的形状有关的，可作为形状描述，称为傅里叶描绘子，区域边界的像素点可以用以弧长为函数的曲线切线角来表示，也可以用复变函数表示。6 ) 矩特征：当一个区域r 只是以其内部点的形式给出时，有兴趣找到另一种区域描绘子，它的大小、旋转和平移的变化都是不变的。“矩”就是其中一种。7 ) 边心距：无论物体如何旋转、平移，其形心到其边界上某一特定点的距离都将是不变的，这就可以以其作为描述物体形状特征的度量，称之为边心距特征。如果将其作归一化处理，则边心距特征还将具有比例不变性。通过以上的图像特征，还可以得到如角点、线条、拐点、顶点、边缘、边界、形状等结构特征，彩色图像中还有色度、色饱和度等。由于图是由点和边组成，故只要有点和边就可以构成不同形式、不同类型的图，研究者利用这样的一个或几个特征可以构成各种各样的图，如区域邻接图、线段构成的图、特征点构成的图等等。2 1 2 图的介绍本节主要介绍一些图的基本概念和术语【3 。一个图是由非空点集v = 矿( g ) 和y 中元素的无序对的一个集合e = e ( g ) 所构成的二元组，记为g = ( y ( g ) ，e ( g ) ) ，简记为g = ( v ，e ) ，v 中的元素称为顶点或点，e 中