（精密仪器及机械专业论文）基于模糊聚类分析的图像分割技术研究(精密仪器及机械专业优秀论文).pdf

上海大学硕七学位论文 摘要 图像分割是指将输入图像分成各具特性的区域并提取出感兴趣的部分 或目标的过程。模糊聚类是用模糊数学方法研究聚类问题，而且在很多领域 都有着较为广泛的应用。本文首先介绍了几种常见的图像分割技术，并说明 了它们各自的特点及应用范围。然后概述了模糊理论基础和聚类分析的常用 算法，着重介绍了c 均值聚类以及模糊理论和c 均值聚类相结合的模糊c 均值聚类算法及其在图像分割中的应用。 针对模糊c 均值( f c m ) 算法需要事先设定聚类数，且若聚类数设定不当， 容易导致错分类的问题，提出了一种利用类间距阈值搜索聚类数的方法来自 适应确定最佳聚类数的模糊聚类算法。针对受到光照不均匀影响的图片在直 接进行阈值分割造成的错分割问题，提出了在分割前对图像进行光照补偿的 预处理，从而降低光照不均匀对阈值分割造成的不利影响。 数字显微全息图像由于其成像机理的复杂性以及对成像环境的高要求 使图像的分割变得很困难。本文提出先通过均值滤波对人胚胎肾细胞数字显 微全息图像进行预处理，再利用加权模糊聚类算法进行图像分割，恢复了人 胚胎肾细胞的真实轮廓。 关键词：图像分割；模糊c 均值聚类；类间距阈值；光照补偿；数字显微 全息图像 v 上海大学硕士学位论文 a b s t r a c t i m a g es e g m e n t a t i o ni st h ep r o c e s so fd i v i d i n gi n p u ti m a g ei n t oa r e a sw i t hs p e c i f i c c h a r a c t e rt h e ne x t r a c t i n gi n t e r e s t i n gr e g i o n f u z z yc l u s t e r i n gt e c h n o l o g yr e s e a r c h e s c l u s t e r i n gq u e s t i o n s w h i c hu s et h e f u z z ym a t h e m a t i c sa l g o r i t h m t h e t h e s i s s u m m a r i z e ss o m ef a m i l i a ri m a g es e g m e n t i n gt e c h n i q u e sa n da p p l i c a t i o n sa n ds t u d i e s f u z z yc l u s t e r i n ga l g o r i t h mp r i n c i p l e sw h i c hw e r ea p p l i e dt ot h ei m a g es e g m e n t a t i o n a f u z z yc l u s t e r i n ga l g o r i t h mb a s e do nf u z z yt h e o r ya n dc m e a n sc l u s t e r i n gw a sa l s o i n t r o d u c e di nt h et h e s i s f u z z yc m e a n si so n eo ft h ea l g o r i t h m sf o rc l u s t e r i n gb a s e do no p t i m i z i n ga n o b j e c t i v ef u n c t i o n i fc l u s t e r i n gn u m b e rd i dn o tb ed e f i n e da p p r o p r i a t e l ya tf i r s t ，i t m a yi n d u c ew r o n gc l a s s i f i c a t i o n a i m i n g a ta b o v ep r o b l e m s ，p r o p o s e dan e w a l g o r i t h mb a s e do nt h et h r e s h o l do fc l u s t e r s d i s t a n c e t h en e wa l g o r i t h mc a nd e t e c t t h eo p t i m a lc l u s t e rn u m b e ra u t o m a t i c a l l y n o n u n i f o r mi l l u m i n a t i o nm a yc a u s ew r o n g s e g m e n t a t i o ni nt h et h r e s h o l ds e g m e n t a t i o no fi m a g e t oo v e r c o m et h ea b o v ep r o b l e m ， an o v e li r r a d i a n tc o m p e n s a t i o na l g o r i t h mf o ri m a g es e g m e n t a t i o ni sp r e s e n t e d d i g i t a lm i c r o s c o p i ch o l o g r a p h yi m a g e sa r eu s u a l l yd i f f i c u l tt ob es e g m e n t e d b e c a u s eo ft h e i r sc o m p l e x i t yi ni m a g i n gm e c h a n i c sa n dh a r dr e q u i r e m e n t si ni m a g i n g e n v i r o n m e n t t h i st h e s i sp r e s e n t st h ew e i g h t i n gf u z z yc l u s t e r i n ga l g o r i t h mt oa c h i e v e t h es e g m e n t a t i o na f t e rm e a nf i l t e r i n g t h er e s u l to fs e g m e n t a t i o ni n d i c a t e st h er e a l c o n t o u ro fh u m a ne m b r y o n i ck i d n e y k e y w o r d s ：i m a g es e g m e n t a t i o n ；f c m ；t h r e s h o l do fc l u s t e r s i n t e r v a l ；i n a d i a n t c o m p e n s a t i o n ；d i g i t a lm i c r o s c o p i ch o l o g r a p h yi m a g e v 1 上海大学硕士学位论文 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示t n 意。 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 1 1 日期：力球，乡 上海大学硕士学位论文 1 1 课题来源 第一章绪论 本课题来源于“高速高精度大行程定位工作台关键技术研究”( 教育部高等 学校重点学科建设资助项目( y 0 1 0 2 ) 、上海市重点学科建设资助项目( b b 6 7 ) ) ， 主要研究模糊聚类算法及其在图像分割中的应用问题。 1 2 课题研究的目的和意义 图像分割就是指把图像分解成各具特性的区域并提取出感兴趣目标的技术 和过程，它是由图像处理到图像分析的一个关键步骤，在图像工程中占有非常重 要的位置。从图1 1 所示图像分析的流程和涉及的步骤，可以了解图像分割在图 像分析中所处的地位和作用。图像分割已在诸如计算机视觉1 1 、模式识别【2 1 和医 学图像处理【3 】等实际中得到了广泛的应用。 图1 1图像分割在图像分析流程图中的位置 尽管人们在图像分割研究方面做了许多工作，提出的算法也数以千计，但至 今仍无通用的分割算法，也不存在一个判断分割是否成功的客观标准。在众多的 分割算法中，基于聚类分析的图像分割方法是图像分割领域中一类极其重要和应 上海大学硕士学位论文 用相当广泛的算法，而聚类分析中用得最普遍的是模糊c 均值聚类 4 1 。采用模 糊c 均值聚类的方法进行图像分割，避免了阈值设定的问题，聚类过程中不需 要任何人工的干预，对于图像分割自动化有重要的意义。 图像分割是图像处理领域一般都要解决的一项复杂繁琐的工作。而且图像分 割效果的判定存在许多主观因素，人眼视觉的主观性使图像分割等图像处理过程 比较适合用模糊手段进行处理。因此把模糊技术引入到图像分割过程中具有较高 的现实意义及应用价值。该课题研究重点将通过改进及提出新的算法来自适应确 定聚类数初值的确定问题及如何利用模糊聚类分析来解决一些实际应用中的图 像分割问题。 1 3 图像分割算法概述 z h a n g y 一5 j 提出一种对分割技术进行分类的方法。对灰度图像的分割常可基 于像素灰度值的不连续性和相似性，区域内部的像素一般具有灰度相似性，而在 区域之间的边界上一般具有灰度不连续性。所以分割技术可据此分为利用区域问 灰度不连续性的基于边界的技术和利用区域内相似性的基于区域的技术。另外根 据分割过程中处理策略的不同，分割技术又可分为并行技术和串行技术。在并行 技术中，所有判断和决定都可独立地和同时地做出，而在串行技术中，早期处理 的结果可被其后的处理过程所利用。一般串行技术所需计算时间比并行技术要 长，但抗噪声能力通常也较强【6 】。 表1 1图像分割技术分类表 分类边界( 不连续性)区域( 相似性) 并行处理并行边界类并行区域类 串行处理 串行边界类串行区域类 1 3 1 阈值化分割算法 取阈值是最常见的并行的直接检测区域的分割方法，其他同类方法如像素特 征空间分类可看作是取阈值技术的推广。阈值化分割已经有几十年的历史，是图 2 商人学学论立 像分割领域中较早出现的一类方法，也是最基本的方法在灰度图像的分析和识 别中起着重要的作用。阀值化分割目的是按照图像的灰度级，将图像空间划分成 与现实景物相对应的一些有意义的区域。各个区域内部灰度级是均匀的，而相邻 区域之间的灰度级是不同的，其间存在着边界。 闽值化分割有单闽值分割和多闽值分割。单闶值分割就是设定一个灰度闽值 t ，对于一幅扶度图像，( z ，y ) ，将图像中的像素分成两类：满足，( y ) t 的 和“x ，y 1 s t 所有像素其中一类称为目标，另一个称为背景。这种分割在机器 视觉、文字议别、生物医学图像分析、指纹与印章鉴定、光学条纹判读以及军事 目标议别等实际应用较为普遍。更一般地，多阈值分割则选择多个闽值，把整个 灰度范围划分成几个段，隶属于每个段内的像素成为类，这样就将图像分成了 多个扶度不同的区域。显然，单阈值分割是多闽值分割的一种特殊情形。 闽值化分割分为两个步骡：首先是确定台适的或者是最佳的闺值，然后是将 图像的像素的扶度跟闽值进行比较，进而确定每个像素所属的类。显然，两个步 骤中的难点和关键就是合适闽值的确定。闽值化分割中的各种各样的算法就是围 绕着闽值的选马( 方法展开的。 下面简单介绍常见的几种基于阕值的图像分割方法p 】： 1 ) 基于敏度直方圈的闽值选取 直方图给出了图像中各个扶度级再图像中所占的比例。图像分割的目的在于 将图像巾的前景从背景中提取出来，而前景与背景的灰度值有差距，这个差距在 直方图中表现出柬就是：直方图上会出现一个谷底值，如果我们将这个谷底所对 应的灰度值作为闽值，那么就可以将前景从背景中提取出来，可惜往往这个谷底 不是很明显，不过这是阉值选取的最基本的方法。 圈l2 基于灰度直方幽的阈值选取 上海大学硕上学位论文 2 ) 迭代法 求出图像中出现的最小灰度级r a i n ，和最大的灰度级m a x ，初始化阈值 r o = ( m i n + m a x ) 2 。步骤如下： ( 1 ) 根据阈值互将图像分为前景，和后景b ，u 为分割后前景的平均灰度等 级，v 为背景的平均灰度等级； ( 2 ) t ( i + i ) = ( u + v ) 2 ； ( 3 ) 如果t ( i + i ) = t ( i ) 则停止，否则返回( 1 ) 。 此方法对图像的分割效果较好，能分割出大部分前景，但是对于细节的分割 效果不是很好，而且数据的微小变化往往也会带来较大的结果差距。 3 1 大津法 8 】 由大津于1 9 7 9 年提出：对图像i m a g e ，记f 为前景与背景的分割阈值，前景 的像素数占图像比例为w o ，平均灰度为u 。，背景的像素数占图像比例为w l ，平 均灰度为u 。图像的总平均灰度为： “= w o u o + w tx 1 1 1( 1 1 ) 从最小灰度值到最大灰度值遍历f ，当t 使得值 g = ( 一“) 2 + 叫( 一“) 2( 1 2 ) 最大时t 即为分割的最佳阈值。对大津法可作如下理解：该式实际上就是类间方 差的值，阂值t 分割出的前景和背景两部分构成了整幅图像，而前景取值u 。，概 率为w n ，背景取值u ，概率为w ，总均值为u ，根据方差的定义即得该式。因 方差是灰度分布均匀性的一种度量，方差的值越大，说明构成图像的两部分差别 越大，当部分目标被错分为背景或部分背景被错分为目标都会导致两部分差别变 小，因此使类间方差最大的分割意味着错分概率最小。 直接应用大津法计算量较大，因此我们在实现时采用了等价的公式 4 上海人学硕士学位论文 g = w ( 一) 2 ( 1 3 ) 大津法选取出来的阈值非常理想，对各种情况的表现都较为良好。虽然它在很多 情况下都不是最佳的分割，但分割质量通常都有一定的保障，可以说是最稳定的 分割。由上可知，大津算法是一种较为通用的分割算法。在它的思想的启迪下， 人们进一步提出了多种类似的评估阈值的算法。 4 1 一种改进的大津法c 9 1 大津法得到了广泛的应用，但有人发现，大津法致命的缺陷是当目标物与 背景灰度差不明显时，会出现令人无法忍受的大块黑色区域，甚至会丢失整幅图 像的信息。为了解决这个问题，有人提出了灰度拉伸的增强大津法。这种方法的 原理其实就是在大津法的基础上通过增加灰度的级数来增强前后景的灰度差，从 而解决问题。灰度增加的方法是用原有的灰度级乘上同一个系数，从而扩大灰度 的级。特别地，当乘上的系数为1 时，这就是大津法的原型，因此，大津法可以 看作是这种方法的一个特例。 1 3 2 基于边缘检测的方法 图像的边缘是图像最基本的特征之一，基于边缘的分割方法可以说是人们 最早的图像分割研究方法。所谓边缘是指其周围像素灰度有阶跃变化的像素的集 合。边缘广泛的存在于物体与背景之间、物体和物体之间，它是图像分割所依赖 的重要特征。边缘检测方法试图通过检测不同区域间的边缘来解决图像的分割问 题【1 们。 边缘检测技术可以按照处理的顺序分为串行边缘检测以及并行边缘检测。 在串行边缘检测技术中，当前像素点是否属于检测的边缘，取决于先前像素的验 证结果；而在并行边缘检测技术中，一个像素点是否属于检测的边缘，是取决于 当前正在检测的像素点以及该像素点的一些相邻像素点。这样该模型可以同时用 于检测图像中的所有像素点，因而称之为并行边缘检测技术。边缘检测常借助于 微分算子进行，通过将微分算子对应的模板与图像相卷积，可检测出灰度不连续 ( 或突变) 的边缘。常用的微分算子有梯度算子( 例如r o b e r t 算子、p r e w i t t 算子、 上海大学硕士学位论文 s o b e l 算子) 、方向算子( 例如k i r s c h 算子) 、拉普拉斯算子、马尔算子、综合正交 算子、坎尼算子等【l l 】。 对于实际含有噪声的图像，仅用微分算子检测出的边缘点并不能组成封闭 的边界而将目标从背景中分离出来。所以还需要利用检测到的边缘点构成目标的 边界，例如，利用哈夫( h o l t 班) 变换，通过在参数空间的累加运算完成从图像空 间( 不连续) 边缘点获取区域封闭边界的工作。近年来，边缘检测技术领域出现了 一些新的方法，例如边缘拟合【1 2 1 3 1 曲线拟合基于反应扩散方程【1 5 舶】、形变模 型【1 7 - 1 8 1 的方法等等。 1 3 3 基于区域的分割方法 基于区域的方法假设同一区域中相邻的像素在视觉上应该有相似的特征，如 灰度特征、颜色特征或纹理特征等等。基于区域的分割算法的优点是充分应用了 图像的空间信息，分割出来的图像也都是连续的，且不受图像中的分支数的限制。 这类方法中最有名和常用的有：区域生长算法、分裂( s p l i t ) 和合并( m e r g e ) 算法。 区域生长的基本思想是将具有相似性质的像素集合起来构成区域。对每个需 要分割的区域找一个种子像素作为生长的起点，然后将种子像素周围邻域中与种 子像素有相同或相似性质的像素( 根据某种事先确定的生长或相似准则来判定) 合并到种子像素所在的区域中。将这些新像素当作新的种子像素继续上面的过 程，直到再没有满足条件的像素可被包括进来 1 9 】。 区域生长算法的研究重点： ( 1 ) 选择一组代表区域特征的种子像素； ( 2 ) 确定生长过程中的合并准则2 0 】； ( 3 ) 确定生长过程的中止规则。 区域生长方式的优点是计算简单，往往与其它分割方法一起使用。区域生长 方式的缺点是对噪音敏感，导致分割出的区域有空洞或在局部体效应的情况下将 分开的区域链接起来。 分裂合并算法的基本思想是先从整幅图像开始，通过不断分裂得到各个区 域。实际中通常先把图像分成任意大小且不重叠的区域，然后再合并或分裂这些 6 上海大学硕士学位论文 区域以满足分割的要求【2 l 】。这类方法中，常需要根据图像的统计特性设定图像区 域属性的一致性测度，其中最常用的测度是基于灰度统计特征，例如同质区域中 的方差( v a r i a n c ew i t h i nh o m o g e n e o u sr e g i o n s v w h r ) 。算法根据v w h r 的数值确 定合并或分裂各个区域。为了得到正确的分割结果，需要根据图像中的噪声水平 来选择v w h r 。实际图像中的噪声一般不能准确的确定，所以v w h r 常根据先 验知识或对噪声的估计来选定，它选择的精确度对算法性能影响很大。另外也可 借助区域的边缘信息来决定是否对区域进行合并或分裂 2 2 1 。 完整的分裂合并算法的主要步骤如下【2 3 1 ： ( 1 ) 初始化：将图像分成子图像，用四叉树( q t ) 表示； ( 2 ) 合并：由下向上通过检测每个结点的同质性，将其子结点合并； ( 3 ) 分裂：由上向下通过检测每个结点的同质性，将其子结点分裂； ( 4 ) 从q t 向r a g 转换：将四又树表示转为区域邻接图表达，即把在四叉树 表示中的目标结点里隐含的邻接关系转换为区域邻接图中的分支； ( 5 ) 组合：将具有同质性的邻接点组合起来，得到最终的分割结果。 1 4 论文的主要研究内容 本论文是以作者攻读硕士学位期间承担课题的工作为基础，在第一章中阐述 了课题研究的来源、目的、意义以及图像分割算法概述。第二章阐述了基于模糊 聚类的图像分割算法。第三章阐述了一种基于类间距阈值的模糊聚类算法。第四 章阐述了基于光照补偿的模糊聚类图像分割。第五章阐述了基于模糊聚类的数字 显微全息图像分割。最后的第六章对全文进行总结。 7 上海大学硕士学位论文 第二章基于模糊聚类的图像分割算法 2 1 模糊理论基础 2 1 1 概述【2 4 】 模糊数学是由扎德( l a z a d e h ) 教授于1 9 6 5 年创立，是- f l 运用数学方法研 究和处理模糊现象的数学新分支。它以“模糊集合”论为基础，提供了一种处理 不肯定性和不精确性问题的新方法，是描述人脑思维处理模糊信息的有力工具。 模糊现象是指客观事物之间难以用分明的界限加以区分的状态，模糊现象是 普遍存在的。例如高与短、美与丑等这样一些对立的概念之间，都没有绝对分明 的界限。而模糊数学则用精确的数学语言去描述模糊性现象，“代表了一种与基 于概率论方法处理不确定性和不精确性的传统不同的思想”，能够更好地反映模 糊性现象。这是模糊数学与普通数学在方法论上的根本区别。 模糊数学自诞生起就发展迅速、应用广泛。它涉及纯粹数学、应用数学、自 然科学、人文科学和管理科学等方面。在图像识别、人工智能、自动控制、信息 处理、经济学、心理学、社会学、生态学、语言学、管理科学、医疗诊断、哲学 研究等领域中，都得到广泛应用。 2 1 2 模糊集合论基础【2 5 】【2 6 】 正像用经典集合理论来描述非模糊现象一样，对模糊现象的刻画则是利用模 糊集合理论。与经典集合理论的定义域相对应，在模糊理论里面用论域x 表示 所研究对象的取值范围。 众所周知，在经典集合理论里，集合么可由其特征函数： 一= 三：三彳a c 2 ，心2 1ox 叠 ) 唯一确定：即x a 和x 诺d 有且只有一个成立。 而模糊现象的分界则是含糊不清的。为了刻画模糊现象，有必要将离散 8 上海犬学硕士学位论文 的两点 o ，1 ) 扩充为连续状态的区间 o ，1 】。这样，普通集合的特征函数就扩展为 模糊集的隶属函数。 定义2 1 ：设x 是论域，心是把任意x x 映射为 o ，1 上某个值的函数，即 心：x 一 0 ，1 x 一a 爿( x ) ( 2 2 ) 则称以为定义在彳上的一个隶属函数，由以( 石) 所构成的集合彳称为石上的 一个模糊集，以( x ) 称为工对彳的隶属度。 由此定义2 1 可看出，模糊集彳完全由其隶属函数所刻画，隶属函数心把彳 中的每一个元素z 都映射为【o ，1 上的一个值以( x ) ，表示该元素隶属于a 的程度， 值越大表示隶属程度越高。当心o ) 的值仅为0 或1 时，模糊集彳便退化为一个 普通集合，隶属函数退化为特征函数。 一般来说，若论域是离散且为有限集 石= 五，x 2 ， ( 2 3 ) 时，其模糊集可用 4 = 爿( 五) ，爿( 恐) ，z 爿( ) ( 2 4 ) 表示。 z a d e h 为了具体指出论域元素与其隶属度的对应关系，给出了如下形式的表 示方法： 彳：窆彳( 誓) 笔 ( 2 5 ) 其中，心( x i ) 为蕾对彳的隶属度。这里心( 薯) _ 不是分数，只有符号含义， 表示而对模糊集a 的隶属程度是儿( t ) ，符号不再是数学求和，而是各元素与 其隶属函数对应关系的一个总括。 9 上海大学硕士学位论文 2 1 3 模糊关系 描述元素之间是否相关的数学模型称为关系，描述元素之间相关程度的数学 模型称为模糊关系。为了区别于模糊关系，通常又称关系为普通关系。显然，模 糊关系是普通关系的拓广和发展，而普通关系则可视为模糊关系的特例。模糊关 系是模糊数学的重要的组成部分。当论域有限时，可用模糊矩阵表示模糊关系。 模糊矩阵为模糊关系的运算带来了极大的方便，成为模糊关系的主要运算工具。 1 模糊关系的定义 设x 、】，是两个非空集合，则直积 xxy = ( x ，y ) l xe x ，y y ( 2 6 ) 中的一个模糊子集晨称为从x 到l ，的一个模糊关系。 模糊关系j i 由其隶属函数 2 詹：x x y 一 0 ，l 】 ( 2 7 ) 完全刻画。序偶( x ，y ) 的隶属度为, u k ( x ，y ) ，它表明了( x ，y ) 具有关系j i i 的程度。 上述定义的模糊关系，又称二元模糊关系，当x = y 时，称为x 上的模糊关 系晨。当论域为n 个集合的直积 x l x 2 x n 时，它所对应的为n 元模糊关系j i i 。 2 模糊关系的运算 设灵、季是x xy 上的模糊关系，则定义一下模糊关系的并、交、包含、相 等、补等运算。 1 ) 并： k u $ v 【心( x ，y ) ，心( x ，j ，) ， v ( x ，j ，) x x y ( 2 8 ) 2 ) 交： 天n i 【蠢( z ，y ) ，纷( x ，y ) 】， v ( x ，y ) x 】， ( 2 9 ) 3 ) 包含：蠢s i , u k ( x ，y ) 纷( x ，y ) ， v ( x ，y ) x x y ( 2 1 0 ) 1 0 上海大学硕士学位论文 4 ) 相等：晨= j c 今声嘻( x ，少) = 心( x ，y ) ， v ( x ，y ) x x y 5 ) j 、： j i 。专令矗( x ，y ) = l - , u j i ( x ，y ) ， v ( x ，y ) x xy 6 ) 转置：晨r 营豆( y ，x ) = j i l ( x ，y ) ， v ( x ，y ) x xy 7 ) 恒等关系：若给定x 上的模糊关系，满足 ，啪) = 骺 则称，为x 上的恒等关系。 8 ) 零关系：若给定x y 上的模糊关系6 满足 ( 2 1 1 ) ( 2 1 2 ) ( 2 1 3 ) ( 2 1 4 ) 6 e ，6 ( x ，夕) = 0 ， v ( x ，y ) x xy ( 2 1 5 ) 则称5 为x x y 上的零关系。 9 ) 全称关系：若给定x x y 上的模糊关系雪满足 营车- q ( x ，y ) = l ， v ( x ，j ，) x xy ( 2 1 6 ) 则称啻为x y 上的全称关系。 3 、模糊关系的合成 模糊关系的合成是普通关系合成的推广，下边给出它的定义： 设u 、矿、w 是论域，亘是u 到矿的一个模糊关系，晨是v 到w 的一个普 通关系，亘对j f i 的合成亘。j f i 指的是【，到w 的一个模糊关系，它具有隶属函数 心。詹( “，w ) = v ( “o ( u ，u ) ( ，叫) ( 2 1 7 ) 当论域u 、矿、形为有限时，模糊关系的合成可用模糊矩阵的合成表示。 设亘、j i 、雪三个模糊关系对应的模糊矩阵分别为 则有 q = ( g 扩) r = ( ) 。埘 s = ( s k ) 刚 = l ( q 矿 ) ( 2 1 8 ) 上海大学硕士学位论文 即用模糊矩阵的合成q 。r = s 来表示模糊关系的合成亘。蠢= j 。 2 1 4 模糊矩阵 1 模糊矩阵的定义及其运算 ( 1 ) 模糊矩阵 如果对任意的f n 及m ，都有勺 o ，1 】，则称尺= ( 勺) 。为模糊矩阵。 通常以i j 表示全体甩行m 列的模糊矩阵。 ( 2 ) 模糊矩阵的并、交及补的运算 对任意r 、s 心。，r = ( 勺) 。，s = ( s f ，) 。，则 ru s = ( 勺vs ，) ( 2 1 9 ) rd s = ( 勺as 矿) ( 2 2 0 ) r 。= ( 1 一勺) ( 2 2 1 ) 分别称以上三式为模糊矩阵尺和s 得并、交运算，及模糊矩阵r 的求补运算。 如果 勺 s j ( i = l ，2 ，l ；_ ，= 1 ，2 ，所) ( 2 2 2 ) 则称模糊矩阵尺被模糊矩阵s 包含，记为s 。 如果 勺2s o ( i = 1 ，2 ，z ；_ ，= 1 , 2 ，m ) ( 2 2 3 ) 则称模糊矩阵尺被模糊矩阵s 相等。 模糊矩阵的并、交、补运算性质与普通矩阵类同。须指出的是，一般 刚1 r 。o ，r u r 。e ，即对模糊矩阵来说互补律是不成立的。 其中o 、e 分别称为零矩阵及全矩阵，即 o = o0 o0 00 0 0 o e = 上海大学硕十学位论文 2 模糊矩阵的合成 ( 1 ) 定义：设q = ( g f ) 。辨，r = ( ) 删是两个模糊矩阵，它们的合成q 。尺指的 是一个胛行，列的模糊矩阵s ，s 的第i 行第七列的元素等于q 的第f 行元素与 第k 列对应元素两两先取较小者，然后在所有的结果中取较大者，即 勘= 蚤( 劬八像) ，l i n ，l k l ( 2 2 4 ) 模糊矩阵q 与尺的合成q 。尺又称为q 对尺的模糊乘积，或称模糊矩阵的乘法。 ( 2 ) 模糊矩阵合成运算 1 ) 结合律( q 。r ) 。s = q 。( r 。s ) 2 ) 分配律 ( 2 2 5 ) ( qur ) 。s = ( q 。s ) u ( r 。s )s 。( q u r ) = ( s 。q ) u ( s 。r ) ( 2 2 6 ) 注意：对于“交”运算，不满足上述分配律，即 ( qn 尺) 。s ( q 。s ) n ( r 。s ) so ( 9 nr ) ( s 。q ) n ( s or ) 3 ) o 。r = r o o ：i 。r = r o ，= r 其中d 为零矩阵，j 为单位矩阵。 4 ) 若q r ，则q 。s r 。s ，s 。q 量s 。r 5 ) 若q l q 2 ，r l r 2 ，则q l 。r i q 2 。r 2 ( 2 2 7 ) ( 2 2 8 ) ( 2 2 9 ) ( 2 3 0 ) ( 2 3 1 ) 须特别指出的事，模糊矩阵的合成运算不满足交换律，即 q 。r r 。q ( 2 3 2 ) 3 模糊矩阵的转置 模糊矩阵的转置矩阵同普通矩阵的转置矩阵的概念是相同的，即把相应的行 变为列，列变为行即可得到转置矩阵，其性质类同于普通矩阵。 1 3 上海大学硕士学位论文 2 2 聚类分析 聚类就是把具有相似性质的事物区分开并加以分类。聚类分析就是用数学方 法研究处理给定对象的分类。“物以类聚，人以群分”，聚类问题是一个古老的问 题，是伴随人类的产生和发展而不断深化的一个问题，有关聚类分析的理论和应 用的研究已有大量的文献。 将一群物理的或抽象的对象，根据它们之间的相似程度分为若干组，其中相 似的对象构成一组，这一过程就称为聚类过程。一个聚类就是由彼此相似的一组 对象所构成的集合，不同的聚类中对象通常是不相似的。聚类分析就是从给定的 数据集中搜索数据对象之间所存在的有价值的联系。与分类不同，在开始聚类之 前用户并不知道要把数据分成几个组，也不知道分组的具体标准，聚类分析时数 据集合的特征也是未知的。聚类根据一定的聚类规则，将具有某种相同特征的数 据聚在一起，也称之为无监督学习。而分类，用户则知道数据可分为几类，将要 处理的数据按照分类标准分入不同的类别，也称为有监督学习。 传统的聚类分析通常是一种硬划分，它把每个待辨识的对象严格地划分到某 个类中，具有“非此即彼”的性质，所以这种类别划分的界限是明晰的。 2 2 1 常见的聚类算法【2 7 】【2 8 】【2 9 】 1 分裂法( p a r t i t i o n i n gm e t h o d s ) 给定一个有个元组的数据集，分裂法将构造c 个分组，每一个分组就代 表一个聚类c 1 ) ；设定迭代停止阈值s 0 ；初始化聚类原 型模式矿( o ) ；设定迭代计数器所：0 。 第一步：计算或更新划分矩阵【，( 川，v i k ： 1 9 上海大学硕士学位论文 f f $ 于r v i k ，如果j 力 o ，则有 “2 = 喜 器 击 一1 c 2 4 。， 如果j f ，使得印= o ，则有 甜，= 1 且对f ，有够= o ：擎坚户，c 4 。， 窆( “吖 第三步：如果妙川一矿0 s ，则转入下一步，否则令m = 朋+ 1 ，转向第 一步。其中为某合适的矩阵范数。 g = 鹕，m a x ( u 北) v i ，v k ( 2 4 2 ) 2 4 本章小结 本章介绍了模糊数学的理论基础，以及结合了模糊聚类的分割技术。重点阐 述了模糊c 均值聚类的原理、算法过程，以及其应用于图像分割时常用的基于 2 0 上海大学硕士学位论文 f c m 图像分割算法。 2 l 上海大学硕士学位论文 第三章基于类间距阈值的模糊聚类算法 3 1 概述 近年来，聚类分析技术又有了很多的有效聚类算法被不断提出。特别是 b e z d e k 在引入模糊集理论后提出的模糊c 均值算法( f c m ) 就是一种常用的聚类分 析方法。f c m 算法是基于目标函数的聚类算法，同其它聚类算法一样，它也要求 事先给定聚类数c 4 5 1 。然而，聚类数c 一般事先都无法确定。因此，如何得到最 佳聚类数c 是众多学者所关心的问题。 由于各种聚类算法的聚类结果一般都依赖于初值，即使聚类数c 保持不变， 算法决定的聚类结果也可能会有所不同 4 6 1 。因此对于同一个数据集，如何评估聚 类算法得出的不同聚类结果就成了一个关键问题，也就是人们称之为聚类有效性 的问题。解决这一问题的一个有效方法是构造聚类有效性函数，目前人们针对各 种聚类算法构造了许多聚类有效性函数，如针对h c m ( 硬c 均值) 算法与s i n g l e l i n l ( a g e 算法的h u b e n ss t a t i s t i c s 4 7 1 ；针对f c m 算法的x i e b e n ii n d e x 矽k 。人们 使用上述聚类有效性函数来计算合适的聚类数c ，即最佳聚类数。但是在此 方法2 _ o e ，必须要先确定的搜索范围，换句话说，就是设定一个，使得 c 懈。于剑等4 9 1 设计了一个聚类有效性函数聊，把作为一个已知的 参数。另外，我们也注意到即使用其他的方法确定c 0 ，同样也需要先确定c 懈， ! ! 1 l e ix u 等 5 0 】做出的阐述。 本章提出了一种基于类间距阈值的模糊聚类算法。算法首先通过计算确定类 间距阈值，然后计算经过每次f c m 算法后所得各类之间的间距，判断其和类间 距阈值的大小关系，以此作为聚类有效性的标准并确定最佳的聚类数。然后根据 计算所得的聚类数进行聚类以得到正确的聚类结果。 上海大学硕上学位论文 3 2 基于类间距阈值的模糊聚类算法 3 2 1 类间距阈值的确定 对于给定的样本集，当样本集中实际有c 个类别时，f c m 算法会按照指 定的聚类数c 将样本集分成c 类。为了演示f c m 算法的在设定了不同的聚类数 的情况下对聚类造成的影响，本文用m a t l a b 产生了中心坐标分别为( o 6 ，0 2 ) 、 ( o 2 5 ，0 6 ) 、( 0 8 ，o 8 ) 的三个二维正态随机矩阵，把这三个矩阵合成后作为 测试样本集。对于如图3 1 所示的测试样本，图中实际的类别数e = 3 。当设定的 聚类数c = 3 时，运用f c m 算法计算会得到如图3 2 所示的正确聚类结果。图3 2 中的小黑点代表经过f c m 聚类过程后得到的各个聚类的中心，为了使各个类相 区分，分别用v 、0 、等符号代表各个类所包含的样本。 图3 1c ，= 3 的测试样本 若设定的聚类数c 比实际的类别数e 大，通过f c m 算法进行聚类，则会在 其它分类基本不变的情况下而