0改进的快速模糊聚类图像分割算法

第26卷 第8期 计 算 机 仿 真 2009年8月 文章编号：1006—9348(2009)08—0212—04 改进的快速模糊聚类图像分割算法 李志梅 ，肖德贵 (1．湖南大学计算机通信学院，湖南 长沙 410082； 2．桂林航天工业高等专科学校计算机系，广西 桂林 541004) 摘要：模糊 C均值(FCM)聚类算法用于图像分割具有简单直观、易于实现的特点，但是存在计算量大、运算速度慢、抗噪能 力差等问题，为解决上述问题提出了一种改进的快速 FCM算法(FFCM)， 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 将空间信息融人到标准 FCM算法中，将图像 从像素空间映射到其灰度直方图特征空间，实现 快速聚类，然后在快速聚类的基础 上，充分利用像素的邻域特性，依据最 大隶属度原则，划分图像像素的类别归属，对隶属度函数做一定改进。实验结果表明，既能快速有效地分割图像，又具有较 好地抗噪能力。 关键词：模糊 C均值；聚类；图像分割 中图分类号：TP391 文献标识码 ：A An Improved Image Segmentation Algorithm of Fast Fuzzy Clustering LI Zhi—mei ，XIA0 De—gui (1．Computer Communication College of Hunan University，Changsha Hunan 410082，China； 2．Computer Science Department of Guilin College of Aerospace Technology，Guilin Guangxi 541004，China) ABSTRACT：FCM clustering algorithm is characterized by its simplicity and applicability in image segmentation． But it a]so has many problems，such as the great amount of calculation，low operation speed and inferior resistance to noise．So this paper proposes a modified fast FCM algorithm for image segmentation(FFCM)．With the modified al- gorithm，space message is firstly integrated into the standard FCM algorithm and images are mapped to gray—scale histogram space from pixel space，on the basis of which the optimal threshold is obtained by the principle of maximum membership，and membership function can be improved by the full use of pixel’S neighborhood feature．The new al— gorithm is shown to be effective in image segm entation and has good performance of resisting noise． KEYWORDS：FCM；Clustering；Image segmentation 1 引言 图像分割是图像分析、理解和识别的关键技术 ，是计算 机视觉研究中经典的研究课题之一，也是图像处理的难点之 一 。 所谓图像分割是指将图像分解成互不相交的不同空间 区域，使得每个区域的像素具有相似的特征，不同区域内的 像素间就会存在特征差异，以便把感兴趣的物体从复杂的背 景中分离出来。 近些年来，由于比传统的硬分割算法能保留更多的原始 图像信息，模糊分割算法引起了人们的关注，特别是模糊 C 均值(FCM)聚类算法作为一种无临督聚类算法已成功地应 用在图像分析和图像分割等领域。它是Dunn在推广硬C均 基金项目：国家自然科学基金资助项目(90715029) 收稿日期：2008—07—09 修回tJ期：2008一O8—04 — 212一 值(HCM)算法的基础上提出的⋯，Bezdek把这一工作进一 步推广到聚类分析中 。FCM算法的基本思想是通过迭代 来优化用于表示图像像素点 与C类中心的相似度的目标函 数 ，以获取极大值，从而得到最优聚类 ，该算法具有良好的 局部收敛性和分割效果。但是使用 FCM对大样本数据进行 聚类时将耗费大量的时间和空间资源 ，而且对于信噪比低 的图像，分割结果很不理想。为了解决上述存在的的问题， 国内外已有很多学者提出了许多快速 FCM聚类算法，文献 [5]提 出了一种 降低迭代计算量提 高性能的快速算法 2rFCM，该算法通过降低图像的分辨率来减少样本的数量， 从而降低运算量，但降低分辨率的做法会使图像有用信息丢 失，导致图像分割错误。文献[6]提出的算法通过选取恰当 的聚类中心来减少迭代次数，缩短迭代时间，但不具有通 用性。 本文对标准模糊C均值聚类分割算法进行了改进，将空 间信息融人到标准的 FCM算法中，通过利用灰度直方图代 替图像的像素点进行聚类，减少FCM迭代过程中的的数据 存储量，以提高算法的收敛速度。即首先用快速 FCM算法 计算出图像各点的隶属度和聚类中心，然后此基础上，充分 利用像素的邻域特性，依据最大隶属度原则，划分图像像素 的类别归属，对隶属度函数做一定改进。实验结果表明，该 方法能快速有效地分割图像，并具有较好地抗噪能力。 2 标准模糊 C均值聚类分割算法(FCM) FCM聚类算法实现方法是根据图像像素和聚类中心的 加权相似性测度 ，对 目标函数进行迭代优化以确定最佳聚 类。其基本思路为：将数据集 X= ． ：⋯ ， } Rpn分为 C 类， 中任意样本札对 i类的隶属度为 “ ，分类结果可以用 一 个模糊隶属度矩阵U={u } R 表示，模糊 C均值聚类 是通过最小化隶属度矩阵 U和聚类中心矩阵 的 目标函数 (U，V)来实现的： ，m( ， )=∑∑ u ) d ( ) (1) 其中，u 为第k个像素对第i类的隶属度，U={ }为模糊隶 属度矩阵，V={ 。， ． ⋯ ， }为 C个聚类中心点集，2≤c≤ n，m∈[1，o。)为模糊加权指数，它控制数据划分过程的模糊 程度，当m：1时，模糊聚类就退化为硬 c均值聚类。Nikhil 等人的的研究表明 ]，m的经验取值区问范围为[1．5，2．5]， 通常 m=2是比较理想的取值。 (Xk )为第 个像素到第 类中心的距离，定义为： , k i (机， )=I — =( 一 ) a(x^一 ) (2) 其中，A为 P×P的正定矩阵，当A是单位矩阵时(A=，时)， 即为欧几里德距离。FCM就是通过反复迭代优化目标函数 I， (U，V)来实现的，执行步骤如下： 1)初始化聚类中心 V： { l， 2，⋯ ，F } 2)计算隶属矩阵 Uik 1 ⋯ ，n ‘3 、 (钆，口，) 3)更新聚类中心 ∑( = l ∑ = 1 并计算 ( ， ) 4)选取合适的矩阵范数(如欧几里德距离)，比较 和 “ ，若Il 川 一 ll< ，则停止迭代；否则k=k+1，转到 2)。 传统的 FCM算法在图像分割中已经获得了广泛的应 用，而且对大多数问题均能获得良好的分割效果。但是， FCM算法是一种迭带优化的运算方法，需要反复计算 和 ，直到算法收敛。当用于图像分割时，由于图像样本的数据 量／'t很大(一幅256×256的图像，n=65536)，计算极为耗 时。本文采用了一种快速 FCM图像分割算法(FFCM)，该算 法将图像从像素空间映射到其灰度直方图特征空间，减少了 FCM迭代过程中的的数据存储量，提高了算法的收敛速度 ， 从而使算法的速度大大提高。并在此基础上，充分利用像素 的邻域特性，对隶属度函数做一定改进，在克服噪声对分割 的影响方面表现出较强的鲁棒性。 3 快速 FCM算法(FFCM) 设图像大小为 MxN m， )是图像阵列在位置(in，n) 处的像素灰度值 m，n) {0，1⋯ ．，L一1}， 是图像的灰 度级数，图像的一维灰度统计直方图函数为 H(1)，定义为 M 日(z)：∑∑8[f(m，n)一z] m u i,g 0 l∈{0，1⋯ ．L一1} (5) 式中：函数 占(0)=1，6(1≠0)=0；H(1)为具有灰度级 l的像 素个数。将原始 FCM算法中的数据项-厂(m， )用统计直方 图 (f)来代替，从而得到新的聚类目标函数为 c ￡一l Jm(U， ： )=∑∑ u ) H(f)t rl—Vi (6) 由 层灰度级隶属函数约束条件： ∑“ =1 l E{0⋯1⋯L一1} (7) 最小化上述 目标函数，从而得到新的快速 FCM迭代函 数 U和聚类中心矩阵 V： L—l ∑( ) (z) f=0 (8) (9) 从上述的快速 FCM算法中不难看出，由于引入 了直方 图统计特性，使算法处理的数据个数大大下降，算法的速度 大大提高。虽然快速 FCM算法的速度提高了，但分割效果 与 FCM算法效果一样。 4 改进的快速 FCM 算法 由于传统的 FCM算法和快速的 FCM算法分割图像是 隶属度的计算，只考虑了图像中当前的像素值 ，未考虑与邻 域像素点之间的相互关系，当分割的图像中不含噪声或噪声 很低时能得到较好的分割效果，但对噪声干扰的图像进行分 割时，抗噪能力较差。为了克服这个问题，在快速 FCM算法 基础上进行改进。 对一幅含有噪声的图像，首先用快速的 FCM 聚类算法 计算图像每层灰度级的隶属度 U ，由像素点和噪声点所在的 灰度级确定它们每点对应的隶属度u ，然后，利用像素的邻 域特性，对隶属度函数改进：假设周围邻域像素对中心像素 一 213 一 的作用关系为 q 其中qik为 属于第 i类的概率大小 ，则改 进后的模糊隶属度表达式为 ：Uikq 1≤ ≤ ，1≤ i≤c (10) 由式(10)给出的新的隶属度，得到改进的 FCM算法的 目标函数为 ．， ( ， )=∑∑(u ) d ( ， ) (11) 则对应的模糊隶属度矩阵和聚类中心表示为 “ 藕 qik 2’ ∑( ) = l ∑( tik) t=T (13) 与标准 FCM算法对比，该算法的关键是如何确定 q 因 此首先给出q 的实现方法 抖Ⅳ： (14) 式中# 为 邻域的像素数目，# 为 邻域的像素中属于 第 i类的数目。# 町任意给定，#Ⅳ 是住快速 FCM算法改 敛后确定，根据最大隶属度原则将其邻域像素归到隶属度最 大的一类中，统计}{l邻域中属于每一类的总数¨。 算法的具体实现为： 1)利用快速 FCM算法埘图像进行初始分割，根据式(8) 和(9)分别得到收敛后的隶属度和聚类中心矩阵作为算法的 初始参数； 2)利用初始的隶属度矩阵，根据最大隶属度原则计算出 ，再根据式(14)计算出q 3)根据式(12)和式(13)计算 新的隶属度和聚类中心 矩阵； 4)判断算法是否收敛，如果不收敛，则将所得的隶属度 作为初始化隶属度，转到2)，否则转到5)； 5)根据隶属度矩阵，利用最大隶属度原则，输出分割结 果，算法结束。 该算法利用快速 FCM算法进行初始化，算法收敛速度 提高，且考虑了与邻域像素间的相互关系，削弱 r噪声对聚 类的影响。 5 实验结果与分析 为了说明FFCM算法在图像分割中的有效性，将其与传 统的FCM算法进行比较分析。 5．1 图像分割算法的准确度比较 以含有伪斑点的颅脑图像 的分割为例，在 WindowsXP (主频为3．06G)，内存为 512M的计算机J-，分别用传统的 FCM算法和改进的 FCM算法 (FFCM)对其分割，结果如图 1，图2所示： - --— — 214 ---—— ■ ■ (a)原阁 fb)FCM分割结果 ■ (t、)FFCM分割结果 图 1 图像分 割结果对比图 由【冬I 1【j 以看 ，FCM和 FFCM办法都能将目标从背景 中有效的分剂m米， 的分割质城十1j ，这表明 FFCM方 法并不改变模糊聚类的 能 回国 (a)含噪图像 (b)FCM分割结果 回 c )改进的FF、cM分割结果 图2 加噪图像的分割结果 【ll 2 以看Ⅲ，FCM办法平¨改进的FFCM方法都较好 地分割出H标的主体，fff 像(b)ffI的噪声较大，而图像(c) 中的 标清晰度较岛， 像巾的噤 点较少。 5．2 传统 FCM 算法和 FFCM 算法速度比较 表1 两种算法的运行时间对比【单位：秒) 算法 标准 FCM算法 快速 FCM算法 耗时 734 6 表 1所示为 FCM和 FFCM两种算法的运行时间比较结 果，不难看出，FFCM算法所用的分割时问明显少于传统的 FCM算法。 6 结束语 通过对标准 FCM算法的研究，提出了一种改进的 FCM 算法，在快速 FCM算法基础上，将图像从像素空间映射到其 灰度直方图特征空间，充分利用像素的邻域特性 ，依据最大 隶属度原则，划分图像像素的类别归属 ，对隶属度 函数做了 一 定改进。实验结果表明，该算法分割速度明显高于标准 FCM算法对原始图像的分割，并对噪声具有较强的鲁棒性。 参考文献： [1] J C Dunn．A fuzzy relative ofthe ISODATA process and its use in detecting compact well—separated clusters[J]．J．Cybemet，1973， 3(3)：32—57． [2] J C Bezdek．Pattern Recognition with Fuzzy Objective Function A1一 gorithms[M]．New York：Plenum Press，1981． [3] A K JAN，N MURTYM，P J FLYNN．Data clustering A review [J]．ACM computer Su~ey，1999，31(3)：264—323． [4] Young W on lin et．A1．On the color image segmentation algorithm based on the thresh holding and the fuzzy c means techniques[J]． Pattern Recongniton，1990，23(6)：935—952． J KE．Fast Accurate Fuzzy Clustering thwu~ Reduced Precision [C]．Master's Thesis University of South Florida，1999． Ming _ Chuan Hung Don — Ijn Yang．An Efficient Fuzzy C—meaIls Clustering Algorithm” [C]．Proceedings of IEEE Intemational Conference on Data Mining SaIIJose．2001．225—232． P R NIKHIL．J C BEZDEK．On cluster validityfortllefuzzy C— means model[J]．IEEE Transactions on Fuzzy Systems，1995，3 (3)：370—379． Y A Tolias，S M Panas．Image Segm entation by a Fuzzy Clustering Algorithm using Adaptive Spatially Constrained Membership Func— tions[J]．IEEE Transactions on Systems，Man and Cybernetics， 1998，28(3)：359—369． Yu Jian，Cheng Qiansheng，Huang Houkuan．AnMysis of the Weighting Exponent in the FCM[J]．IEEE Trans SMC—PartB， 2004，34(1)：634—639． [作者简介] 李志梅(1972一)，女(汉族)，宁夏陶乐人，硕士研 究生，讲师，研究方向：数字图像处理。 肖德贵(1972一)，男(汉族)，湖南南县人，博士，副 教授，硕士研究生导师，主要研究方向：智能视觉监 视／监控，视频信息处理。 (上接第211页) 5 测试结果 场景面片数：129600 渲染帧率：197．55帧／秒 更新遍历时间：0．07毫秒 剔除时间：0．35毫秒 绘制时间：2．15毫秒 最终的模拟效果如图5所示。 图5 用OSG实现的镜面反射 6 结论 本次实验中，通过使用 OSG开发库实现了镜面反射特 效，对场景图技术有 了深入的理解，实践证明，该方法能快 速、真实的模拟镜面反射。 参考文献： [1] 华炜，彭群生．包含整体镜面反射的虚拟场景实时漫游算法 [J]．软件学报，2000，ll(9)：1241—1247． [2] Dave Astle，Kevin Hawkins．OpenGL游戏编程[M]．重庆：重庆 大学出版社，2006． [3] 申闫春等．基于OSG的三维仿真平台的 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 与实现[J]．计算 机仿真，2007，24(o6)：207—211． [4] Peter Shirley．计算机 图形 学 [M]．北京 ：人 民邮电出版 社，2007． [5] Richard S Wright．OpenGL超级宝典 [M]．人 民邮电出版 社，2005． [6] 潘汉军，刘娅．光线反射过程的矩阵表达方法[J]．2004，25 (4)：9—13． [作者简介] 曹 莉(1979一)，女(汉族)，河南新乡人，硕士研 究生，主要研究方向为虚拟现实技术。 李绍彬(1974一)，男(汉族)，北京人，博士生，讲 师，主要研究领域为数字媒体技术、数字电视技术。 申闫春(1957一)，男(汉族)，河南开封市人，教授， 中国计算机用户协会仿真应用分会理事，主要研究方向为流媒体技 术、虚拟现实技术。 一 2l5 — 1 ] ] ] 1 J Administrator »Ø¸´ 1