深圳大学研究生课程论文
题目基于空间模糊聚类的图像分割优化算法
成绩
专业信息与通信工程课程名称、代码模糊数学理论年级研一
姓名梁运恺同组人叶韩
学号2150130406 2150130407
时间2015/1/6
任课教师李良群
基于空间模糊聚类的图像分割优化算法
【摘要】针对传统模糊C－均值(FCM)算法抗噪性能差的问题，提出一种新的基于空间模糊聚类的图像分割优化算法。该算法通过在传统FCM算法基础上加入图像特征项中像素间的空间位置信息，解决了传统FCM对噪声敏感的问题，增强了算法的鲁棒性。实验结果表明，该算法可实现有效分割，分割效果显著优于传统FCM 算法。
【关键词】图像分割；模糊聚类；ＦＣＭ算法；空间位置信息；
The Spatial Fuzzy Clustering Optimization Algorithm
for Image Segmentation
Abstract: For the poor anti-noise performance limitations of the traditional fuzzy C-means (FCM) algorithm. We proposed a new spatial fuzzy clustering optimization algorithm for image segmentation .we added a wealth of spatial information between pixels in the image feature items, so that the traditional FCM sensitive to noise was solved. And the robustness of the algorithm was enhanced. Experimental results show that our algorithm can achieve the effective segmentation the noise images. And the results are significantly better than those by traditional FCM image segmentation algorithm.
Keywords: image segmentation; fuzzy clustering; FCM algorithm; spatial information
1.引言
图像分割是图像处理到图像分析的关键步骤，是进一步理解图像的基础。图像分割本质上是基于某种相似性准则对像素进行分类，在期望的分割结果中，属于同类的像素特征不仅在数值上相似，其空间位置信息也有紧密联系。数据聚类方法对图像进行分割具有直观和易于实现的特点，其中最有效的是模糊C－均值（Fuzzy C-means ,FCM）聚类算法。但传统的FCM算法未考虑图像的空间信息，在处理受噪声污染的图像时常会得到不理想的分割结果，因此，本文提出一种改进的FCM算法。针对传统FCM算法在分割过程中只考虑本地信息的问题，本文算法加入有影响力的特征因子，即空间位置信息。实验结果表明，本文算法可显著
抑制噪声并保留实际图像的特征。
2. FCM 聚类简介
2.1 模糊集合基本知识
首先说明隶属度函数的概念。隶属度函数是表示一个对象x 隶属于集合A 的程度的函数，通常记做μA (x)，其自变量范围是所有可能属于集合A 的对象（即
集合A 所在空间中的所有点），取值范围是[0,1]，即0<=μA (x)<=1。μA (x)=1
表示x 完全隶属于集合A ，相当于传统集合概念上的x ∈A 。一个定义在空间X={x}上的隶属度函数就定义了一个模糊集合A ，或者叫定义在论域X={x}上的模糊子集。对于有限个对象x 1，x 2，……，x n 模糊集合可以表示为：
X}x |)x ),(x {(u A ~
i i i A ∈= 有了模糊集合的概念，一个元素隶属于模糊集合就不是硬性的了，在聚类的问题中，可以把聚类生成的簇看成模糊集合，因此，每个样本点隶属于簇的隶属度就是[0，1]区间里面的值。
2.2 C 均值聚类
C 均值聚类也称K 均值聚类（K-Means ），已经应用到各种领域。它的核心思想如下：算法把n 个向量x j (1,2…,n)分为c 个组G i (i=1,2,…,c)，并求每组的
聚类中心，使得非相似性（或距离）指标的价值函数（或目标函数）达到最小。当选择欧几里德距离为组j 中向量x k 与相应聚类中心c i 间的非相似性指标时，
价值函数可定义为：
)c x (J J 2
c 1i G k,x i k c 1i i i k ∑∑∑=∈=-== 这里是组I 内的价值函数。这样J i 的值依赖于G i 的几何特性和c i 的位置。
一般来说，可用一个通用距离函数d(x k ,c i )代替组I 中的向量x k ，则相应的
总价值函数可表示为：
))c (x d (
J J i k c 1i G k,x c 1i i i k -==∑∑∑=∈= 为简单起见，这里用欧几里德距离作为向量的非相似性指标，且总的价值函数表示为（2）式。
(1) (2)
(3)
划分过的组一般用一个c×n 的二维隶属矩阵U 来定义。如果第j 个数据点x j 属于组i ，则U 中的元素u ij 为1；否则，该元素取0。一旦确定聚类中心c i ，可导出如下使式子最小的u ij ：
?????≤≠=其他0c -x c -x ，如果i k 对每个1u 2k j 2i j ij 重申一点，如果c i 是x j 的最近的聚类中心，那么x j 属于组i 。由于一个给
定数据只能属于一个组，所以隶属矩阵U 具有如下性质：
n j u
c j i .....111i =?=∑=
且 n u
c i n j ij =∑∑==11 另一方面，如果固定u ij 则使（6.2）式最小的最佳聚类中心就是组I 中所有
向量的均值：
∑∈=
k k G x k k x ,i i G 1c 这里|G i |是G i 的规模。 为便于批模式运行，这里给出数据集x i （1，2…，n ）的K 均值算法；该算
法重复使用下列步骤，确定聚类中心c i 和隶属矩阵U ：
步骤1：初始化聚类中心c i ,i=1,…,c。典型的做法是从所有数据点中任取c
个点；
步骤2：用式（6.4）确定隶属矩阵U ；
步骤3：根据式（6.2）计算价值函数。如果它小于某个确定的阀值，或它相对上次价值函数质的改变量小于某个阀值，则算法停止；
步骤4：根据式（6.5）修正聚类中心。返回步骤2。
该算法本身是迭代的，且不能确保它收敛于最优解。K 均值算法的性能依赖于聚类中心的初始位置。所以，为了使它可取，要么用一些前端方法求好的初始聚类中心；要么每次用不同的初始聚类中心，将该算法运行多次。此外，上述算法仅仅是一种具有代表性的方法；我们还可以先初始化一个任意的隶属矩阵，然后再执行迭代过程。
K 均值算法也可以在线方式运行。这时，通过时间平均，导出相应的聚类中心和相应的组。即对于给定的数据点x ，该算法求出最近的聚类中心ci ，并用下(4) (5) (6)
(7)
面公式进行修正：
)(c k i c x -=?η
这种在线公式本质上嵌入了许多非监督学习神经元网络的学习法则。 2.3模糊C 均值聚类（FCM ）
模糊C 均值聚类即众所周知的模糊ISODATA ，是用隶属度确定每个数据点属于某个聚类的程度的一种聚类算法。1973年，Bezdek 提出了该算法，作为早期硬C 均值聚类（HCM ）方法的一种改进。
FCM 把n 个向量xi （i=1,2,…,n）分为c 个模糊组，并求每组的聚类中心，使得非相似性指标的价值函数达到最小。FCM 与HCM 的主要区别在于FCM 用模糊划分，使得每个给定数据点用值在0，1间的隶属度来确定其属于各个组的程度。与引入模糊划分相适应，隶属矩阵U 允许有取值在0，1间的元素。不过，加上归一化规定，一个数据集的隶属度的和总等于1:
n j u
c j i .....111i =?=∑= 那么，FCM 的价值函数（或目标函数）就是式（2）的一般化形式:
2111),...,(ij c i n j m ij c i i c d u J c c U J ∑∑∑====
这里u ij 介于0，1间；c i 为模糊组I 的聚类中心，d ij =||c i -x j ||为第I 个聚
类中心与第j 个数据点间的欧几里德距离；且是一个加权指数。
构造如下新的目标函数，可求得使式子(6.10)达到最小值的必要条件：
)1()
1(),...,(),...,,,...,(J 11211
1111∑∑∑∑∑∑=====-+=-+=c i ij m j i ij
c i m j m
ij c
i ij m j i c m c u d u u c c U J c c U λλλλ 这里j=1到n ，是(9）式的n 个约束式的拉格朗日乘子。对所有输入参量求导，使式（10）达到最小的必要条件为：
∑∑==n j m ij j n j m
ij
i u x u /c 1 和
))(
/(1u 1)1(2∑=-=c k n j k ij ij d d (8)
(9)
(10)
(12)
(13)
(11)
由上述两个必要条件，模糊C均值聚类算法是一个简单的迭代过程。在批处
和隶属矩阵U[1]：
理方式运行时，FCM用下列步骤确定聚类中心c
i
步骤1：用值在0，1间的随机数初始化隶属矩阵U，使其满足式（9）中的约束条件；
，i=1,…,c；
步骤2：用式（12）计算c个聚类中心c
i
步骤3：根据式（10）计算价值函数。如果它小于某个确定的阀值，或它相对上次价值函数值的改变量小于某个阀值，则算法停止；
步骤4：用（13）计算新的U矩阵,返回步骤2；
上述算法也可以先初始化聚类中心，然后再执行迭代过程。由于不能确保FCM收敛于一个最优解。算法的性能依赖于初始聚类中心。因此，我们要么用另外的快速算法确定初始聚类中心，要么每次用不同的初始聚类中心启动该算法，多次运行FCM。
2.4 FCM算法的应用
通过上面的讨论，我们不难看出FCM算法需要两个参数一个是聚类数目C，另一个是参数m。一般来讲C要远远小于聚类样本的总个数，同时要保证C >1。对于m，它是一个控制算法的柔性的参数，如果m过大，则聚类效果会很次，而如果m过小则算法会接近HCM聚类算法。
算法的输出是C个聚类中心点向量和C*N的一个模糊划分矩阵，这个矩阵表示的是每个样本点属于每个类的隶属度。根据这个划分矩阵按照模糊集合中的最大隶属原则就能够确定每个样本点归为哪个类。聚类中心表示的是每个类的平均特征，可以认为是这个类的代表点。从算法的推导过程中我们不难看出，算法对于满足正态分布的数据聚类效果会很好，另外，算法对孤立点是敏感的。
3 FCM算法的优化
传统FCM方法分割图像只考虑了灰度特征，而忽略了像素间丰富的空间依赖关系，仅将像素作为独立的点进行处理，使其对图像中的噪声和异常值较敏感，噪声像素因其异常特征常会被错误的分类，导致本属于同类的像素不能连续，无法形成有效分割区域。本文提出的基于空间位置信息的模糊聚类算法可有效解决该问题，提高传统ＦＣＭ算法的鲁棒性。
3.1算法描述
本文算法加入了对像素间空间位置信息的考虑，即算法主要使用像素间的空间关系和灰度级关系两个特征。定义如下：
j i G S ij ij ij ≠?=H 其中：第ｉ像素表示局部中心像素；第ｊ像素表示Ｎ个ｉ像素周围邻域像素的集合；Ｓｉｊ表示局部空间关系；Ｇｉｊ表示局部灰度级关系；Ｈｉｊ表示图像的局
部特征。
Ｓｉｊ使像素间的相互影响根据其到中心像素的距离而改变，定义如下：
22ij )()(S i j i j b y a x -+-= 其中(ｘｊ,ｙｊ)，(ａｉ,ｂｉ)分别表示ｊ像素和聚类中心ｉ像素的空间坐
标．G ij 使像素间的相互影响根据其灰度级的距离而改变，定义如下：
2ij )()(f G i i j j b a f y x ---= 其中：ｆ(i)表示空间窗口内中心像素的灰度值；f(j)表示同一窗口内第ｊ个像素的灰度值。引入上述定义后，根据Lagrange 乘数法，得到初始参数如下：
)1/(2k )])(/()[(),(u --=∑--=c p i j j i k i i i v w v w y x
]),(/[]),([),(v 11c q i i i k i c q i i i k i i k y x w y x y x ∑∑===μμ
其中ｗｉ即为通过加入空间信息后得到的初始聚类中心矩阵。最后，用带有
空间信息的FCM 算法将图像分割，先用式(17)与(18)对隶属度函数和聚类中心矩阵进行更新，再迭代直到满足条件ε<-|V |new old V 时收敛，从而得到最终的分割结果。
(14)
(15)
(16)
(17)
(18)
4 实验结果
4.1 FCM聚类结果
图4.1 FCM图像分割系统
4.2 FLICM聚类结果
图4.2 FLICM图像分割系统
4.3 实验结果分析
综上所述，本文提出了一种基于灰度信息和空间信息的自适应空间聚类方法，该算法通过在聚类目标函数中引入空间约束，扩大了特征空间，充分利用了图像中丰富的空间位置信息。用本文算法对图像进行分割，实验结果表明，该算法抗噪声能力强，分割效果好，是一种有效的模糊聚类图像分割方法。
5 总结
经过学习模糊数学这门课，通过FCM模糊聚类算法，让我了解了FCM模糊聚类可以有效的对一些模糊的样本进行分类，同时FCM在各个领域都得到有效的应用。经过几周的摸索，将应用于图像分割的FCM进行优化，加深了模糊概念的理解。在编写程序的过程中，遇到了不少的难题，在我与叶韩同学的团结协作，在李良群老师的帮助下，最后克服各种困难，完成了代码的编写。
【参考文献】
[1] Chin-Wei B, Rajeswari M. Multiobjective Optimization Approaches in Image Segmentation –The Directions and Challenges[J]. International Journal of Advances in Soft Computing & Its Applications, 2010, 2(1).
[2] Zou Kaiqi, Wang Zhiping, Hu Ming. An Improved FCM algorithm for Color Image Segmentation[C]// icicic. IEEE Computer Society, 2008:200-200.
[3] Bezdek J C. A Convergence Theorem for the Fuzzy ISODATA Clustering Algorithms[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 1980, pami-2(1):1-8.
[4]Cai W, Chen S, Zhang D. Fast and robust fuzzy c-means clustering algorithms incorporating local information for image segmentation[J]. Pattern Recognition, 2007, 40(3):825-838.
[5] 陈骥思, 余艳梅, 殷宇,等. 自适应快速FCM彩色图像分割研究[J]. 计算机工程与应用, 2010, 46(07):178-180.
[6] Qu A B. Research on image segmentation algorithm based on fuzzy clustering[C]// Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series. Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, 2013:88784I-88784I-6.
[7] Zhang X, Zhao R, Nie X. Automatic Segmentation Algorithm of Video Object[J]. Computer Engineering, 2006, 32(24):159-161.
[8] Wang X Y, Bu J. A fast and robust image segmentation using FCM with spatial information[J]. Digital Signal Processing, 2010, 20(4):1173-1182.
[9]Cai W, Chen S, Zhang D. Fast and robust fuzzy c-means clustering algorithms incorporating local information for image segmentation[J]. Pattern Recognition, 2007, 40(3):825-838.
本科生毕业设计 姓名：学号： 学院：计算机科学与技术学院 专业：计算机科学与技术 设计题目：基于谱聚类的图像分割 专题：图像分割的设计与实现 指导教师：职称：副教授
大学毕业设计任务书 学院计算机专业年级学生姓名 任务下达日期： 毕业设计日期： 毕业设计题目： 毕业设计专题题目 毕业设计主要内容和要求： 院长签章：指导教师签字：
中国矿业大学毕业设计指导教师评阅书 指导教师评语（①基础理论及基本技能的掌握；②独立解决实际问题的能力；③研究内容的理论依据和技术方法；④取得的主要成果及创新点；⑤工作态度及工作量；⑥总体评价及建议成绩；⑦存在问题；⑧是否同意答辩等）： 成绩：指导教师签字： 年月日
中国矿业大学毕业设计评阅教师评阅书 评阅教师评语（①选题的意义；②基础理论及基本技能的掌握；③综合运用所学知识解决实际问题的能力；③工作量的大小；④取得的主要成果及创新点；⑤写作的规范程度；⑥总体评价及建议成绩；⑦存在问题；⑧是否同意答辩等）： 成绩：评阅教师签字： 年月日
中国矿业大学毕业设计答辩及综合成绩
需求分析 一、利用前台，得到一张原始JPG图片； 二、把这张图片传到后台，JAVA通过JRI调用R； 三、利用R调用K-Means的改进算法，实现对这张图片的处理，由于一张图片的 像素值是一个矩阵，可以得到一组关于像素值的数据； 四、把这组像素值进行分类，对各类赋予不同的颜色进行标记，从而区分出需要的 图片信息； 五、把得到的新图片传到前台； 六、前台对进行处理后的图片进行显示，从图像中得到需要的信息，从而实现图像 的分割。
深圳大学研究生课程论文 题目基于空间模糊聚类的图像分割优化算法 成绩 专业信息与通信工程课程名称、代码模糊数学理论年级研一 姓名梁运恺同组人叶韩 学号2150130406 2150130407 时间2015/1/6 任课教师李良群
基于空间模糊聚类的图像分割优化算法 【摘要】针对传统模糊C－均值(FCM)算法抗噪性能差的问题，提出一种新的基于空间模糊聚类的图像分割优化算法。该算法通过在传统FCM算法基础上加入图像特征项中像素间的空间位置信息，解决了传统FCM对噪声敏感的问题，增强了算法的鲁棒性。实验结果表明，该算法可实现有效分割，分割效果显著优于传统FCM 算法。 【关键词】图像分割；模糊聚类；ＦＣＭ算法；空间位置信息； The Spatial Fuzzy Clustering Optimization Algorithm for Image Segmentation Abstract: For the poor anti-noise performance limitations of the traditional fuzzy C-means (FCM) algorithm. We proposed a new spatial fuzzy clustering optimization algorithm for image segmentation .we added a wealth of spatial information between pixels in the image feature items, so that the traditional FCM sensitive to noise was solved. And the robustness of the algorithm was enhanced. Experimental results show that our algorithm can achieve the effective segmentation the noise images. And the results are significantly better than those by traditional FCM image segmentation algorithm. Keywords: image segmentation; fuzzy clustering; FCM algorithm; spatial information 1.引言 图像分割是图像处理到图像分析的关键步骤，是进一步理解图像的基础。图像分割本质上是基于某种相似性准则对像素进行分类，在期望的分割结果中，属于同类的像素特征不仅在数值上相似，其空间位置信息也有紧密联系。数据聚类方法对图像进行分割具有直观和易于实现的特点，其中最有效的是模糊C－均值（Fuzzy C-means ,FCM）聚类算法。但传统的FCM算法未考虑图像的空间信息，在处理受噪声污染的图像时常会得到不理想的分割结果，因此，本文提出一种改进的FCM算法。针对传统FCM算法在分割过程中只考虑本地信息的问题，本文算法加入有影响力的特征因子，即空间位置信息。实验结果表明，本文算法可显著
function [mu,mask]=kmeans(ima,k) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%% % % kmeans image segmentation % % Input: % ima: grey color image % k: Number of classes % Output: % mu: vector of class means % mask: clasification image mask % % Author: Jose Vicente Manjon Herrera % Email: jmanjon@fis.upv.es % Date: 27-08-2005 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%% % check image ima=double(ima); copy=ima; % make a copy ima=ima(:); % vectorize ima mi=min(ima); % deal with negative ima=ima-mi+1; % and zero values s=length(ima); % create image histogram m=max(ima)+1; h=zeros(1,m); hc=zeros(1,m); for i=1:s if(ima(i)>0) h(ima(i))=h(ima(i))+1;end; end ind=find(h); hl=length(ind); % initiate centroids mu=(1:k)*m/(k+1);
聚类分析 1.聚类分析定义： 2.聚类方法： 3.谱聚类： 3.1 常见矩阵变换 3.2 谱聚类流程 3.3 谱聚类理论前提、证明 3.4 图像分割实例结果 4.总结：
聚类分析： ?聚类分析（Cluster analysis，亦称为群集分析）是对于静态数据分析的一门技术，在许多领域受到广泛应用，包括机器学习，数据挖掘，模式识别，图像分析以及生物信息。
算法分类： ?数据聚类算法可以分为结构性或者分散性。 ?结构性算法以前成功使用过的聚类器进行分类。结构性算法可以从上至下或者从下至上双向进行计算。从下至上算法从每个对象作为单独分类开始，不断融合其中相近的对象。而从上至下算法则是把所有对象作为一个整体分类，然后逐渐分小。 ?分散型算法是一次确定所有分类。K-均值法及衍生算法。 ?谱聚类（spectral clustering）
结构型：层次聚类的一个例子：
分散型：K-均值算法：
分散型k-means 及其衍生算法的比较：K-means K-Medoids K-Means算法： 1. 将数据分为k个非空子集 2. 计算每个类中心点（k-means
１６４计算机技术与发展第１７卷 一定的规则把模糊聚类划分转化为确定性的分类。 ４实验结果及分析 实验是在ＷｉｎＸｐ＋Ｍａｔｌａｂ６．５的平台上进行的。ＣＰＵ：ｐ４Ｉ８Ｇ＋内存：７６８Ｍ。 实验对图２进行加均值为０，方差为Ｏ．００５的高斯噪声，显示如图３所示。再针对２幅图做实验。 图２实验原图图３加噪后的图 实验一：对图２进行分 析，从图上可以很容易地分 辨出该图应该被分为３类， 图４（ａ）就是对图２的灰度 直方图处理。由于受到边 缘信息和各类问的互相重 叠，不可区分。在灰度４０ 到１２０的波峰和波谷很难 区别。而运用梯度和灰度 的二维直方图就除了灰度 信息更添加了梯度信息，图 ４（ｂ）只显示了梯度小于３０ 的点。其实就是把原来的 灰度直方图的像素点的出 现频率沿梯度做分摊，越处 于边缘处相关度越小，被分 的越厉害，更加显现是波 谷。处于目标内部相关度 越高，被分的越小，更加显 现是波峰。如图４（ｃ）所示， 波谷与波峰的差更明显。 峰值，并进行聚类方法的图像分割。聚类结果如表１所示。对没有处理的直方图，它的聚类数月会受噪声和边界的均匀过渡的影响，使类数或多或或少。这将直接影响后面的图像分割。 表１原图和加噪后图像的聚类数目和各类的类峰 毒熬燮峰值 隅像娄数ｃ 蹦４（ａ）：直接直方日１２２ 图４（ｅ）：投影后直古圉４０ 图５（ａ）：加噪匿的直方图 图５（ｃ）：加噪图的直方图５３１１５ ５结论 图像分割是计算机视觉研究的重要方面，但图像分割一直是一个难题。文中运用模糊聚类，而聚类数 图４原始图像的处理过程与比较 ３橼龋吨亟直翼篷 ０１０。２００ ３栅｛后一罐蠹专瞄 图５加噪后的处理过程与比较 已经不再有灰度在４０到１２０之间峰谷很难分的情况。 实验二：对图３滤波去噪再求出其直方图，如图５（ａ）所示。此时只是明显地显示单峰了。再用同样的方法求出梯度和灰度的二维直方图，如图５（ｂ）所示，再投影得到如图５（ｃ）所示的直方图，从图中可以明显地看出经过这样处理后的直方图显现的是３峰。 实验三：分别对直接的直方图和处理后直方图运用该文的聚类数目的自动确定方法进行出聚类数和类 目是完全自动确定的，使模糊聚类完全实现了无监督化。通过一维商方图，用高斯模板对一维直方图进行卷积，去除噪声。再用峰值的数日作为ＦＣＭ的聚类数目，但简单的卷积去噪，不能去除局部的最大值，效果也不是很好，很容易分割过细，机器叉十分耗时，而且无法辨认。而文中就添加了一个梯度信息，增加了背景与目标问的空白区域，使波峰和波谷的区分度更高。同时在梯度和灰度的二维直方图抛弃掉梯度比较大的 （下转第１８０页） 热 ！盆 帕 ５ ｏ
模糊C均值聚类算法在图像分割中的应用 【摘要】由于在大多数图像分割场合，不可能清楚知道图像中的各个物体位置，因此在一定意义上图像分割可以作为一个聚类问题来解决。并且由于图像具有的模糊和不均匀性，因而模糊C均值聚类技术在图像分割中得到成功的应用。本文对标准模糊C均值聚类分割算法进行了简单的介绍，采用了一种结合空间信息的快速模糊C均值聚类分割算法。 关键词：图像分割，模糊聚类算法，模糊C均值聚类算法 1、模糊聚类算法 传统的聚类方法在划分对象时是硬性的，对象归属哪一类是明确的，不能同时属于两个或者多个类别。换句话说，每一个对象与最终的类别是一一对应的，不会出现一个元素分属多个类的情况，类与类之间有着严格的界限。自然世界中的事物都存在模糊性，没有“非此即彼”的严格界限，一个事物与多个类别都相关的情况是十分正常的。因此，要精确地表示这种复杂的关系就需要对这种“亦此亦彼”的性质进行描述。与硬性的聚类划分相比，模糊聚类将模糊集合理论引入到聚类算法中，利用模糊数学对处理事物之间模糊关系的精确描述，能更好地解决了现实世界中的实际问题。 模糊聚类算法用数学的方法描述了对象与不同类别之间的隶属关系，打破了严格的类别界限，建立起样本对于类别的不确
定性的描述，实现了聚类问题的软划分。隶属度是样本类属模糊性的度量，隶属度的大小用来区分对象隶属于不同类别的差异程度。使用模糊聚类算法来对数据对象集合进行划分需要构造模糊分类矩阵。 模糊聚类算法多种多样，随着对模糊聚类的研究，模糊聚类算法不断发展和改进。其中，基于模糊关系和目标函数是最常见的两类，前者出现较早，对对象集合的大小有局限性，后者以其简便、通用性高、容易实现等优势逐渐成为各个领域最流行的模糊聚类方法。神经网络的发展也为模糊聚类分析注入了新的活力，尤其是提高了方法的效率，因此这类方法受到了各国研究者的重视。 2.模糊C均值聚类算法在图像分割中的应用 模糊C 均值聚类算法(Fuzzy C-means，FCM)是一种经典的模糊聚类算法，它是从硬C 均值聚类算法(Hard C-means，HCM)改进优化而来的。模糊集合理论出后，1969 年RusPini在自己的文章中阐述了模糊划分这一概念，并给出了硬聚类算法的原理，Dunn 提出了模糊聚类算法，此后各国的研究者利用这一概念，通过对目标函数进行优化提出了多种聚类方法。Bezdek通过改进模糊聚类算法提出了模糊C 均值聚类理论。模糊C 均值聚类算法属于基于目标函数的模糊聚类算法的范畴，即基于目标函数的非线性迭代最优化方法，依据最小二乘原理，通过计算目标函数的均方差，得出每个数据点对类中心的隶属程度和目标函数的最
谱聚类算法及其在图像分割中的应用 1 引言 在对图像的研究和应用中，人们往往仅对图像中的某些部分或者说某些区域感兴趣。这些部分常称为目标或前景（其他部分称为背景），它们一般对应图像中特定的具有独特性质的区域。为了辨识和分析目标，需要将它们从图像中分离提取出来，在此基础上才有可能对目标进一步利用。图像分割就是指把图像分成各具特性的区域并提取出感兴趣目标的技术和过程。这里的特性可以是像素的灰度、颜色和纹理等，预先定义的目标可以对应单个区域，也可以对应多个区域。 多年来，对图像分割的研究一直是图像技术研究中的热点和焦点，它不但是从图像处理到图像分析的关键步骤[1]，而且是计算机视觉领域低层次视觉中的主要问题。图像分割的结果是图像特征提取和识别等图像理解的基础，只有在图像被分割后，图像的分析才成为可能。 图像分割在实际应用中已得到了广泛的应用，如图像编码、模式识别、位移估计、目标跟踪、大气图像、军用图像、遥感图像、生物医学图像分析等领域。同时，图像分割也在计算机视觉和图像识别的各种应用系统中占有相当重要的地位，它是研制和开发计算机视觉系统、字符识别和目标自动获取等图像识别和理解系统首先要解决的问题。概括地说只要需对图像目标进行提取测量等都离不开图像分割。 对分割算法的研究已经有几十年的历史，至今借助于各种理论已经提出了数以千计的分割算法[2]，而且这方面的研究仍然在积极进行。尽管人们在图像分割方面做了许多工作，但至今仍无通用的分割算法，也不存在一个判断分割是否成功的客观标准。因此已经提出的分割算法大都是针对具体问题的，并没有一种适合于所有图像的通用的分割算法。实际上由于不同领域的图像千差万别，也不可能存在万能的通用算法。 现有的分割算法非常多，大体上可以分为以下几类：阈值化分割、基于边缘检测的、基于区域的、基于聚类的和基于一些特定理论工具的分割方法。从图像的类型来分最常见的：有灰度图像分割、彩色图像分割和纹理图像分割等等。本
信息疼术2018年第6期文章编号=1009 -2552 (2018)06 -0092 -03 DOI：10.13274/https://www.doczj.com/doc/7c11828669.html,ki.hdzj.2018. 06.019 基于聚类的图像分割方法综述 赵祥宇\陈沫涵2 (1.上海理工大学光电信息与计算机学院，上海200093; 2.上海西南位育中学，上海200093) 摘要：图像分割是图像识别和机器视觉领域中关键的预处理操作。分割理论算法众多，文中 具体介绍基于聚类的分割算法的思想和原理，并将包含的典型算法的优缺点进行介绍和分析。经过比较后，归纳了在具体应用中如何对图像分割算法的抉择问题。近年来传统分割算法不断 被科研工作者优化和组合，相信会有更多的分割新算法井喷而出。 关键词：聚类算法；图像分割；分类 中图分类号：TP391.41 文献标识码：A A survey of image segmentation based on clustering ZHAO Xiang-yu1，CHEN Mo-han2 (1.School of Optical Electrical and Computer Engineering，University of Shanghai for Science and Technology，Shanghai200093，China；2.Shanghai Southwest Weiyu Middle School，Shanghai200093，China) Abstract:Image segmentation is a key preprocessing operation in image recognition and machine vision. There are many existing theoretical methods,and this paper introduces the working principle ol image segmentation algorithm based on clustering.Firstly,the advantages and disadvantages ol several typical algorithms are introduced and analyzed.Alter comparison,the paper summarizes the problem ol the selection ol image segmentation algorithm in practical work.In recent years,the traditional segmentation algorithms were improved and combined by the researchers,it believes that more new algorithms are blown out. Key words:clustering algorithm；image segmentation；classilication 0引百 近年来科学技术的不断发展，计算机视觉和图像 识别发挥着至关重要的作用。在实际应用和科学研 究中图像处理必不可少,进行图像处理必然用到图像 分割方法,根据检测图像中像素不重叠子区域，将感 兴趣目标区域分离出来。传统的图像分割方法:阈值 法[1]、区域法[2]、边缘法[3]等。近年来传统分割算法 不断被研究人员改进和结合，出现了基于超像素的分 割方法[4]，本文主要介绍超像素方法中基于聚类的经 典方法，如Mean Shift算法、K-m eans 算法、Fuzzy C-mean算法、Medoidshilt算法、Turbopixels算法和 SLIC 算法。简要分析各算法的基本思想和分割效果。 1聚类算法 1.1 Mean Shil't算法 1975年,Fukunaga[5]提出一种快速统计迭代算法，即Mean Shilt算法（均值漂移算法）。直到1995 年,Cheng[6]对其进行改进，定义了核函数和权值系 数，在全局优化和聚类等方面的应用，扩大了 Mean shil't算法适用范围。1997至2003年间，Co-maniciu[7-9]提出了基于核密度梯度估计的迭代式 搜索算法,并将该方法应用在图像平滑、分割和视频 跟踪等领域。均值漂移算法的基本思想是通过反复 迭代计算当前点的偏移均值，并挪动被计算点，经过 反复迭代计算和多次挪动，循环判断是否满足条件, 达到后则终止迭代过程[10]。Mean shil't的基本形 式为： 收稿日期：2017-06 -13 基金项目：国家自然科学基金资助项目（81101116) 作者简介：赵祥宇（1992-)，男，硕士研究生，研究方向为数字图像处理。 —92 —
龙源期刊网 https://www.doczj.com/doc/7c11828669.html, 几种聚类算法在图像分割中的应用研究 作者：苗欣雨 来源：《科教导刊·电子版》2015年第19期 摘要本文具体介绍了图像分割中几种聚类算法的工作原理。通过对比，分析了几种算法的优缺点，总结了在实际工作中对算法的选择问题。 关键词聚类算法图像分割均值漂移 K均值聚类 中图分类号：TP391.41 文献标识码：A 通常在分析以及使用图像时，人们需要的不是整幅图像而仅仅是其中的某些目标。图像分割就是把需要的部分分割出来，再进一步分析处理图像。每个图像都有它独有的特点，对图像进行分割时要想达到预期的结果就必须选择合适的算法，由此可见对算法的研究是很关键也很必要的。目前常用的几种分割方法有k均值聚类算法、模糊c均值算法、均值漂移算法等。 1聚类算法 1.1均值漂移算法 均值漂移（Mean Shift）算法是一种有效的统计迭代算法。均值漂移的算法原理是，在样本中随机选择一圆心为o，半径为h的区域，得出这个区域中所有样本点的平均值，圆心处的样本密度必然比均值处的样本密度小或者相等，将均值定为新的圆心重复以上步骤，直到收敛到密度极大值点。 1.2 K均值聚类算法 k均值聚类由于其原理简单而使用很广泛。该算法的工作原理是，首先将n个样本分为k 个组，在每组中随机选择一个元素当作聚类中心。然后得到其他采样点到这个中心的欧氏距离，把采样点归类到与之欧氏距离最小的聚类中心所在的类中。计算新形成的聚类中采样点的平均值，得到新的聚类中心。重复上述过程，直到每个样本都分类正确为止。 1.3模糊C均值聚类算法 模糊C均值是为解决实际应用问题对K均值进行改进得来的。在实际应用中图像目标在类别属性方面没有那么严格的区分。所以想出利用隶属度来判断每个目标样本的所属，来更好的划分。模糊C均值聚类的具体工作原理是，算法将n个样本分为c个组，得到各个组的聚类中心，最终让非相似性指标的目标函数达到最小。算法给各个样本点赋予0～1之间的隶属度，通过隶属度的值来判断样本归属于各个分类的程度。同时有规定一个样本的隶属度加和后值为一。
机器学习报告 一．绪论 聚类是探索性数据分析中广泛采用的一种技术，其应用范围包括统计学、计算机科学、生物学、社会科学和心理学等等。在处理经验数据的时候，我们可能倾向于根据数据的“近似表现”将数据确定到一定的类别。而本次我们小组的实验主要是基于聚类算法中的谱聚类方法，通过对两种谱聚类方法的实验和一些应用，验证算法的效果，加深对该方法的理解。 由于谱聚类的数值实现很简单，利用简单的线性代数学方法就能有效解决，而且相比传统的K 均值方法等聚类方法有很多优点，所以谱聚类方法称为了很流行的现代聚类算法之一。 以K 均值方法为例，正如我们所知，该方法主要存在这样一些问题：首先，其只适用于凸球形的样本空间，如果样本空间非凸，则会陷入局部最优，导致聚类效果不佳；再有，由于该方法计算使用的是欧氏空间中的原始数据向量，所以在样本维数很大的时候，K 均值算法的计算量会很大，导致了计算的困难；聚类数K 难以确定等等。而谱聚类则能很好地解决这些问题。 在本次实验中，我们小组根据相关文献，认真学习和讨论了谱聚类的先关概念。首先，我们研究了一般的谱聚类和标准化谱聚类的概念和它们的异同，并通过实验对比，验证了谱聚类的效果，其中标准化谱聚类有显著的优势。接下来，将谱聚类应用于图像分割问题，显示出谱聚类良好的应用价值。最后，我们查阅相关文献，尝试从另外一个角度去理解谱聚类方法。通过这次学习，我们对谱聚类的理解得到了大大加深，对于很多疑难的地方也通过查看有关文献和小组讨论得到了解决，并通过小组合作锻炼了自身的团队意识和配合工作的能力。 二．谱聚类基本思想 谱聚类是一种基于图论的聚类方法，把样本看作图的顶点，样本间的相似度对应带权值的边（其中相似度可以通过高斯核函数等方法构造），根据类间相似度最小，类内相似度最大的原则，便可以将样本聚类问题变成了图的分割问题：分割使得连接不同类之间的边的权值尽可能小，而类内点之间的边的权值尽可能高。虽然这样对应的最小化图分割问题是一个NP-HARD 问题，但是我们可以将其转化为最小化图的Laplace 矩阵的特征值问题。 具体地，给定样本特征之后，我们首先要计算样本两两之间的相似度值，并通过这些值构造出近邻矩阵。以高斯核函数为例，计算公式如下： 22||||(2)i j x x ij w e σ--= 作为第i 个样本和第j 个样本之间相似度的度量。而近邻矩阵如下： ()ij W w =。
毕业论文声明 本人郑重声明： 1．此毕业论文是本人在指导教师指导下独立进行研究取得的成果。除了特别加以标注地方外，本文不包含他人或其它机构已经发表或撰写过的研究成果。对本文研究做出重要贡献的个人与集体均已在文中作了明确标明。本人完全意识到本声明的法律结果由本人承担。 2．本人完全了解学校、学院有关保留、使用学位论文的规定，同意学校与学院保留并向国家有关部门或机构送交此论文的复印件和电子版，允许此文被查阅和借阅。本人授权大学学院可以将此文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本文。 3．若在大学学院毕业论文审查小组复审中，发现本文有抄袭，一切后果均由本人承担，与毕业论文指导老师无关。 4.本人所呈交的毕业论文，是在指导老师的指导下独立进行研究所取得的成果。论文中凡引用他人已经发布或未发表的成果、数据、观点等，均已明确注明出处。论文中已经注明引用的内容外，不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究成果做出重要贡献的个人和集体，均已在论文中已明确的方式标明。 学位论文作者（签名）： 年月
关于毕业论文使用授权的声明 本人在指导老师的指导下所完成的论文及相关的资料（包括图纸、实验记录、原始数据、实物照片、图片、录音带、设计手稿等），知识产权归属华北电力大学。本人完全了解大学有关保存，使用毕业论文的规定。同意学校保存或向国家有关部门或机构送交论文的纸质版或电子版，允许论文被查阅或借阅。本人授权大学可以将本毕业论文的全部或部分内容编入有关数据库进行检索，可以采用任何复制手段保存或编汇本毕业论文。如果发表相关成果，一定征得指导教师同意，且第一署名单位为大学。本人毕业后使用毕业论文或与该论文直接相关的学术论文或成果时，第一署名单位仍然为大学。本人完全了解大学关于收集、保存、使用学位论文的规定，同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、扫描、数字化或其它手段保存或汇编本学位论文；学校有权提供目录检索以及提供本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有关部门或者机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权大学可以将本学位论文的全部或部分内容编入学校有关数据库和收录到《中国学位论文全文数据库》进行信息服务。在不以赢利为目的的前提下，学校可以适当复制论文的部分或全部内容用于学术活动。 论文作者签名：日期： 指导教师签名：日期：
第30卷第3期 杭州电子科技大学学报V ol.30,N o.3 2010年06月Journal of Hangzh ou Dianzi University Jun.2010 结合灰度共生矩阵和模糊聚类的图像分割技术 李慧慧,余正生 (杭州电子科技大学图形图像研究所,浙江杭州310018) 收稿日期:2009-10-26 基金项目:浙江省自然科学基金资助项目(Y 1090609) 作者简介:李慧慧(1984--),女,山西长治人,在读研究生,计算机辅助几何设计. 摘要:该文主要研究了灰度共生矩阵和模糊均值聚类两种图像分割方法,对于这两种方法分别提 取了4种纹理特征描述符:角二阶矩、对比度、相关性和熵来进行图像分割。并结合两种方法得出 一种改进的图像分割方法。分别用这两种方法和改进后的方法对lean 图进行分割并对分割的结 果进行比较分析,实验证明改进后的方法优于灰度共生矩阵法,且优于模糊聚类法中用对比度和 熵进行图像分割的效果,提高了图像的分割精度。 关键词:灰度共生矩阵;模糊聚类;隶属函数;聚类中心;隶属矩阵 中图分类号:TP391 文献标识码:A 文章编号:1001-9146(2010)03-0063-04 0 引 言 随着计算机科学技术的不断发展,图像处理和分析逐渐形成了自己的科学体系。图像分割的效果直接决定了后续图像分析、图像理解和模式识别的性能,具有重要的研究价值。图像分割的方法和种类有很多,本文讨论了灰度共生矩阵和模糊聚类两种图像分割的方法[1-3]。两种方法都是提取了4种相同的纹理特征值,使用相同的聚类方法,所不同的是灰度共生矩阵法是通过求灰度图像的灰度共生矩阵;而模糊聚类法是通过求隶属度函数[4]来实现。因为聚类时,每次迭代优化目标函数都要计算聚类中心和隶属度函数[5,6],运算量很大,十分耗时,灰度共生矩阵法中为了降低运算量,利用了灰度直方图统计信息,在此灰度空间上进行聚类极大的降低了运算量。通过对两种方法运行结果的比较,提出了基于两种实验方法的一种改进方法,改进的方法效果明显比灰度共生矩阵好,并且比模糊聚类中用描述符熵和对比度进行图像分割的效果好。 1 预处理 设样本集为X ={X 1,X 2,…,X n },用聚类算法把X 硬划分成c 个模式子集S i (i =1,2,…,c ),则有: X ∪c i =1S i ,S i ∩S j =Φ i ≠j ,1≤i ,j ≤c (1) 聚类是通过最小化关于隶属度矩阵U 和聚类中心V 的目标函数J m (u ,v )来实现的: J m (u ,v )=∑n k =1∑c i =1(u ik )m d 2ik (x k ,v i )(2) 式中,c 为聚类的个数,m 为加权指数,文中m 取为2,U ={Uik}为模糊划分矩阵,它把数据样本点和聚类模式联系起来,U ik 表示X 中任意样本X k 对i 类的隶属度,并需满足条件:
模糊聚类法在图像分割中的应用 摘要：模糊聚类算法是模糊理论中的一个重要的分支,是现今模糊理论中应用最广泛的领域之一,并取得了丰富的成果。由于图像所具有的模糊性,近年来一些学者将模糊理论引入到图像处理中,应用模糊理论进行图像分割,图像增强以及边缘检测。本文在研究模糊理论的基础上,对模糊聚类算法在图像分割中的应用进行了一定的探讨。 关键词：模糊理论，图像分割，模糊聚类 0.引言： 随着计算机技术的飞速发展，数字图像分割技术触及工业检测、环境监测、军事和宇宙探索等多诸多学科领域。从统计学的观点上看，图像分割可以分为基于概率统计的硬分割和基于模糊数学的软分割。在实际应用中，图像分割结果受到图像许多方面特征的制约，例如：图像的灰度、纹理或颜色等硬分割方法在综合考虑这些因素时往往顾此失彼，因而分割结果并不理想但若将上述因素用模糊集合来表示，利用隶属度综合考虑各因素对图像分割结果的影响，则能准确反映图像的特征。因此，基于模糊数学的模式分类在图像分割中得到了广泛应用基于模糊聚类的软分割具有以下几个鲜明的特点：1）模糊聚类分割算法不使用训练样本，这使得非监督图像分割成为可能。2) 在进行模糊聚类分割算法构建时，只需建立模糊优化函数，仅有隶属度聚类中心和核
函数带宽这个未知参数传统的图像聚类分割方法是一种硬划分，将每个像素划分到某一类中，在现实中，像素的归属伴随着不确定性，而隶属度是描述不确定性的强有力工具。随着模式识别、人工智能和逼近理论的不断发展，特别是非参数密度估计方法的发展，为模糊聚类核函数的选取提供理论依据，从而将图像分割问题转化为确定最优超平面的分类函数。3) 采用进化算法，如遗传算法、免疫算法和模拟退火等，优化目标函数获得对数据的最佳分类。 1.图像分割技术简介及聚类分析法 图像分割是一种关键的图像分析技术，是从图像处理进行到图像分析的关键步骤，也是进一步图像理解的基础。图像分割按照不同的特性，如灰度、颜色、纹理等，将图像分成若干个各具相似特性的区域，以便能提取出所需要的目标。在图像分割前，对图像的加工主要处于图像处理的层次，图像分割后，对图像的分析才成为可能。图像分割在实际中也已得到广泛的应用，例如在工业自动化，在线产品检验，以及军事、体育、农业工程等方面。概括来说，在各种图像应用中，只要需对图像目标进行提取，测量等都离不开图像分割。每当有新的数学工具或方法提出来，人们就试着将其用于图像分割，基于聚类分析的图像分割方法是图像分割领域中一类极其重要和应用相当广泛的算法，其在应用领域取得的巨大成功引起了广大关注。 2.聚类分析算法的分类
BI YE SHE JI （20 届） 基于聚类的图像分割系统的设计与实现——分割算法模块
摘要 图像分割的算法研究已有很多年的历史，一直以来都得到了人们的高度重视。关于图像分割的原理和方法世界各国均有不少的论文发表，但一直以来没有一种一般的分割方法能够适用于所有图像分割处理。传统的图像分割方法的劣势在于不能满足人们的要求，为后续的图像分析和理解带来了困难。随着计算机技术以及计算机性能的迅猛发展，及其相关技术的发展和成熟，结合色彩处理，图像增强等技术，个人计算机上就能够实现图像分割处理。 图像处理技术有很多种，如图像分析，颜色转换，去噪等，但其中最主要的图像处理技术是图像分割技术，从图像中将某个特定区域与其它部分进行分离并提取出来的部分进行检测，变换，识别等处理操作。 图像的分割是实现图形理解的基础,也是计算机图形学中的一个基本问题,并且在其 他很多领域得到了应用。由于图像的格式和色彩形状不同,要实现通用且快速的图像分割仍然是一个难题。图像分割的主要研究内容有：建立可靠有效的分割模型,减少分割算法的运算量，降低分割算法的复杂度,提高分割算法的通用性及抗噪性等。但是因为分割模型的不同,各种分割方法在不同的分割模型表现出不同的优缺点。有阈值分割方法，边界分割方法，区域提取方法，结合特定理论工具的分割方法等。本文只对这些方法做简单的介绍。 本文中着重介绍的是，基于聚类的分割算法，聚类分析是一种无监督分类法,它通过归类相似性质（结构色彩）的样本实现分类。在缺少相关知识时,图像分割可以通过聚类分析完成。基于聚类分析的图像分割算法的通用性好，并且对样本空间的约束小。无论是灰度图像、彩色图像分还是纹理图像,都可以应用聚类分析方法完成分割。但是基于聚类分析的分割方法也有缺点,主要就是因为聚类分析分割算法计算量大,有可能出现极值问 题并且对噪声样本比较敏感。本文分析了当今图像分割的研究成果以及面临的主要问题,针对聚类算法用于图像分割的特点,着重对聚类算法进行了算法实现，并能用图片的形式呈现出来。 通过对聚类算法的是实现，本文在其基础上还对分割后的图片进行重新合并的操作，合并操作通过比对，计算图片碎片的相似度进行实现。 关键词：图像分割，复杂度，样本空间，聚类分割，合并，相似度