一种基于模糊聚类的快速图像分割算法

第39卷　第2期2007年4月

西安建筑科技大学学报(自然科学版)

J 1Xi ’an Univ. of Arch. &Tech. (Natural Science Edition )

Vol. 39　No. 2

Apr. 2007

一种基于模糊聚类的快速图像分割算法

杨润玲1,2, 高新波2, 介　军1

(1. 西安建筑科技大学信控学院, 陕西西安710055;2. 西安电子科技大学电子工程学院, 陕西西安710071)

摘　要:提出一种基于二维直方图加权的模糊c 均值图像快速分割算法. 通过将原图像和它的平滑图像相结合, 构造一个二元组的“广义图像”, 广义图像的直方图就是原图像的二维直方图. 然后对此二维直方图进行塔形分解得到金字塔的上一层———顶层, 相应地称原二维直方图为底层. 最后, 利用加权模糊c 均值聚类算法分别对顶层和底层进行模糊聚类, 从而实现对原图像的分割. 实验结果与性能分析表明, 该算法具有较高的分割速度和良好的抑制噪声的能力.

关键词:图像分割; 加权模糊c 均值聚类算法; 塔形结构; 二维直方图

中图分类号:TP391. 41　　　　文献标识码:A　　　　文章编号:100627930(2007) 0220280206　

图像分割是模式识别和计算机视觉中的经典研究课题. 它利用不同的图像特征将原图分成各自独立的区域, 从而抽取出感兴趣的目标. 因此, 图像分割方法的正确性和自适应性在一定程度上影响着目标检测和识别的智能化程度, 其分割速度影响着实用性.

在众多的图像分割方法中, 模糊c 均值(FCM :Fuzzy c 2Means ) 聚类算法可解决灰度图像中存在的模糊、不确定性问题. 该方法是由Dunn 提出, 经过Bezdek 的推广后[1], 获得了十分广泛的应用. 但在对大数据样本集聚类时, 该算法极为耗时, 而且对于低信噪比的图像的分割结果很不理想. 针对其不足, 国内外已有很多学者提出了许多快速FCM 聚类算法[2,3], 或者融合其它新方法来提高图像分割性能, 比如结合直方图的方法[4,5]、结合金字塔的方法[6]等. 这些方法大多将原始图像映射至特征空间以减少聚类样本数, 或者采用量化和聚合原始数据使其样本数锐减, 或者通过金字塔的各层依次寻找最优聚类中心以便很好地指导高分辨率塔底的聚类分割, 以减少塔底的大数据集运算从而提高分割速度. 但上述方法应用于低信噪比图像时, 分割效果并不理想. 如文献[4]在其二维直方图(2D H :22Dimensional Histo 2gram ) 的构造时, 采取了原图像邻域平均法来获得平滑图像, 这种做法虽能降低噪声, 却使物体边缘变

得模糊, 从而影响了分割的性能. 另一方面, 基于2D H 的图像分割, 待聚类的样本集仍然很大, 且对聚类初始化较敏感, 并非总能保证分割速度的显著提高和良好的分割结果.

在分析前人工作的基础之上, 提出一种基于2D H 加权的塔形模糊c 均值(2D H 2PWFCM :2D H and Pyramid Weighting FCM ) 聚类算法. 首先构造一个合理的2D H , 然后对其进行金字塔(Pyramid ) 分解, 最后利用加权模糊c 均值(WFCM :Weighting FCM ) 聚类算法对金字塔各层进行模糊聚类, 从而实现对原图像的快速分割.

1　标准的FCM 算法

设集合X ={x 1, x 2, …, x n }是特征空间上n 个待聚类样本的集合,V ={v 1, v 2, …, v c }是c 个聚类原型的集合, c 是满足2≤c ≤n 的整数. FCM 聚类算法定义的目标函数为

n

c

J m (U ,V ) =

i =1j =1

∑∑

u ij d ij

m 2

, s. t. U ∈M f c (1)

3收稿日期:2005209205　　修改稿日期:2006211228

基金项目:国家自然科学基金资助项目(60202004) ; 教育部重点项目(104173)

作者简介:杨润玲(19762) , 女, 陕西西安市人, 讲师, 硕士研究生, 主要从事图像处理、图像分割研究.

第2期　　　　　　杨润玲等:一种基于模糊聚类的快速图像分割算法

c

n

ij

281

M f c ={U ∈R |u ij ∈[0, 1], Πi , j ;

nc

j =1

∑u

=1, Πi ; 0

i =1

∑u

ij

) 为加权指数; u ij 是第j 类中样本x i 的隶属度, U =[u ij ]n ×式中:m ∈(1, ∞c 为模糊划分矩阵; d ij =‖x i

-v j ‖为样本距聚类中心v j 的欧氏距离; M f c 是X 的模糊c 划分空间.

利用拉格朗日乘子法, 可以推导出式(1) 的两个优化迭代公式

n

c

u ij =

k =1

∑

(2)

d ik

2

m-1

-1

, v j =

n

∑u

i =1

m ij

x i

(3)

m ij

∑u

最后选择合适的矩阵范数比较前后两次的划分矩阵U , 若两者之差小于要求或给定误差, 则迭代停止, 得到最终划分矩阵U 以及聚类原型矩阵V.

2　2D H 2PWFCM 算法

2. 1　加权模糊c 均值聚类算法(WFCM 算法) [7]

WFCM 算法可以表述为如下数学规划问题:

n

c

J m (U ,V ) =

i =1j =1

∑∑

w i u ij d ij

m 2

, s. t. U ∈M f c (4)

式中:w i 为每个样本的权系数, 主要用于聚类中心的调整, 其余参数如1所述. 利用拉格朗日乘子法, 也

可以推导出式(4) 的两个优化迭代公式

n

c

u ij =

k =1

∑

(

2) d ik

2

m-1

-1

, v j =

n

∑

i =1

w i u ij x i

(5)

i

m ij

m

∑w u

当每个样本的权系数相同时, 即认为各类样本对分类影响一致时, WFCM 算法就退化为标准的FCM 算法.

2. 2　基于2D H 加权的FCM 图像分割算法

前述FCM 图像分割算法中, 待分析的样本是像素, 因此样本含量会随着图像尺寸的增大而增大. 由于样本的特征为灰度, 所以便出现了基于一维直方图(1D H :12Dimensional Histogram ) 加权的FCM 图像分割算法[4], 以提高分割的速度. 1D H 表示了灰度与其出现的频度的关系. 对于8bit 灰度图像, 待分类样本值介于0至255之间. 可把每一级灰度在图像中出现的频度作为该级灰度样本的加权系数.

在1D H 中由于噪声干扰等原因, 不能表现出明显的双峰或者多峰(这些峰分别对应于不同的目标和背景) , 因而无法获得满意的分割结果. 但图像中像素与其邻域之间存在较大的相关性, 可以由原图和邻域平滑图像来构造2D H , 那么目标和背景的分布在2D H 中就会比在1D H 中容易区分. 2D H 表示的是原图F (x , y ) 中灰度值为s , 同时在平滑图像I (x , y ) 的同一位置具有灰度值为t 的二元组(s , t ) 与其出现的频度的关系. 即, 将原图像和它的平滑图像相结合, 构造一个二元组的“广义图像”, 该广义图像的直方图就是原图像的2D H. 本文在图像平滑时, 考虑到既要滤除噪声, 又要保留图像的边缘细节, 因此利用了一种基于高阶统计量的图像平滑去噪法[8]获得其平滑图像. 以上是对于信噪比较高的图像(如图像的PSNR >25) 采取的2D H 构造方法, 这里称做2D H 的第一种构造方法. 如果图像的噪声强度较高(如PSNR

了一个独立的高斯白噪声N (0,0. 006) . 图1(b ) 是其1D H , 图1(c ) 和(d ) 分别对应其由第一种和第二种方法分别构造的2D H. 可以看出, 在噪声的干扰下,1D H 没有明显的多峰分布, 但在2D H 中, 这种情况得到了很大改善, 尤其是后一种2D H , 不但显示了较明显的峰谷特性, 而且二元组更加贴近底面对角线分布, 从而更加有利于2D H 的WFCM 聚类.

2D H 加权的FCM (2D H -WFCM ) 聚类算法, 与WFCM 算法不同的是, 样本集不是单个像素的灰

图1　含噪图像及其灰度直方图

Fig. 1　Image wit h noise and it s intensity histogram

度值, 而是广义图像的灰度值, 即二元组的灰度值, 加权系数变成了二元组出现的频度. 考虑到2D H 中

贴近对角线分布的二元组数目较多, 这里对其进行塔形分解得到金字塔的上一层———顶层(相应地称原2D H 为底层) . 这里塔形分解采用的是对底层256×256进行2×2平均抽取获得顶层, 所以顶层尺寸为128×128, 当然还可以不断平均抽取获得更高层. 由于2D H 塔形结构各层的分布相似, 并且顶层的二元组数目至少减少为底层的1/4, 因此先对顶层采用WFCM 聚类算法得到比较合适的聚类中心, 然后再合理地映射至底层作为其WFCM 聚类中心的初始值, 以便更好地指导底层的聚类, 从而减少底层迭代时间, 提高分割速度. 最后, 将底层二元组的分类标识赋给原图像, 便得到了原图像的分割结果.

基于上述分析,2D H -PWFCM 图像分割算法的实现步骤如下:

步骤一:输入原始图像, 用基于高阶统计量的图像平滑去噪方法获得其平滑图像; 步骤二:构造2D H ; 塔形分解获得两层金字塔:底层和顶层;

步骤三:初始化顶层的聚类类别数c; m =2; 顶层聚类中心, 利用式(6) 初始化在2D H 底面的对角线上; 设定每一层迭代停止阈值ε=0. 01;

v i =

c +L

3i (6)

其中L =128, i =1, 2, …, c

步骤四:利用WFCM 算法对顶层进行模糊聚类;

步骤五:如果相邻两次迭代中顶层的隶属度U 矩阵相减后的最大值小于ε, 则算法停止并输出聚类中心矩阵V , 否则转向步骤四;

步骤六:用顶层输出的聚类中心V 合理地初始化底层的聚类中心; 步骤七:利用WFCM 算法对底层进行模糊聚类;

步骤八:如果相邻两次迭代中底层的隶属度U 矩阵相减后的最大值小于ε, 则算法停止并输出划分矩阵U , 否则转向步骤七;

步骤九:将划分矩阵去模糊, 再合理地映射至原图像, 最终获得分割结果.

3　实验结果与分析

为了验证本文算法的有效性, 分别以人造图像和自然图像进行了实验, 比较了标准FCM 算法与2D H 2PWFCM 算法的图像分割效率, 测试环境为:赛扬2100GHZ CPU , 256M 内存, Matlab6. 1编程工具仿真实现. 3. 1　分割时间的比较

如表1所示是两种算法对不同尺寸高信噪比图像进行分割时的运行时间比较. 对于此类待分割图像, 其2D H 是由第一种方法构造的. 可见新算法的图像分割

表1　高信噪比的不同尺寸图像分割中

两种算法的分割时间对比

Tab. 1　Segmentation time comparison on different size of images wit h high PSNR

Image size 6464128×128256×256512×512

FCM New

algorithm/s algorithm/s 1. 328017. 7970106. 7810187. 1090

0. 54703. 843010. 797012. 9680

Enhanced times 2. 44. 69. 914. 4

速度明显提高, 尤其是图像尺寸越大, 这种优势越明显.

表2是两种算法对不同尺寸低信噪比图像进行分割时的运行时间比较. 其中, 新算法I 指其2D H 由第一种方法构造, 新算法II 指其2D H 由第二种方法构造. 由表2可见, 新算法I 、II 的分割速度均高于标准FCM 算法, 并且随着图像尺寸的增大这种优势呈递增的趋势. 值得注意的是, 当图像信噪比较

低, 即图像受噪声污染较严重时, 采用第二种2D H 的构造方法, 使得待聚类的二元组分布更加集中(比较图1(c ) 和(d ) , 这一点清晰可见) , 从而分割的速度又进一步地提高了.

表2　低信噪比的不同尺寸图像分割中两种算法的分割时间对比

Tab. 2　Segmentation time comparison on different size of images wit h low PSNR

Image size 64×64128×128256×256512×512

FCM algorithm/s New algorithm I/s

1. 484015. 6090109. 9070509. 1720

1. 01607. 875026. 930045. 9130

Enhanced times

1. 52. 09. 933. 1

New algorithm Ⅱ/s

0. 73403. 984010. 547015. 3750

Enhanced times

2. 44. 69. 933. 1

3. 2　分割性能的比较

首先构造一幅64×64大小的图像, 共3种灰度值0、179、255, 并叠加一个独立高斯白噪声N

(0,0. 006) , 如图2(a ) 所示. 图2(b ) 是FCM 算法的分割结果, 图2(c ) 和(d ) 分别是新算法I , II 的分割结果. 表3给出了三种算法的分割性能对比. 显然, 对低信噪比图像分割时, 新算法II 的分割性能最好, 新算法I 的分割性能次之, 标准FCM 算法的分割性能最差

.

表3　三种分割算法的性能比较

Tab. 3　Performance comparison of t hree algorit hms

Algorithm FCM algorithm New algorithm I New algorithm II

Wrong numbers 69120

Wrong rate/%1. 680. 290

Segmentation time/s 1. 48401. 01600. 7340

图2　含噪图像及三种算法的分割结果

Fig. 2　Image wit h noise and it s segmentation result s of t hree algorit hms

3. 3　实际应用的比较

如果新算法的2D H 均来自原图像, 那么其二元组将分布在2D 平面的对角线上, 这样一来, 新算法和标准FCM 算法的分割情形是一致的, 所以分割结果一定相同, 所不同的是两者的分割效率. 实际上, 新算法的2D H 取自原图像和平滑图像, 自然两种算法分割结果不完全一样. 表4给出了两种算法对同一幅标准Lena 图像的分割性能比较, 两种算法所得到聚类中心间的欧氏距离为1. 73, 分割差异率为0. 86%.可见两种算法的分割精度很接近, 但是新算法的分割速度却是FCM 算法的9. 9倍.

表4　两种算法对标准Lena 图像的分割结果

Tab. 4　Segmentation result comparison of two algorit hms

Algorithm FCM algorithm New algorithm I

Segmentation time/s

106. 781010. 7970

Clustering center 26,66,101,137,19226,67,102,138,192

Segmentation difference/%

0. 86

如果待分割图像信噪比较低, 在新算法中2D H 将采用第二种构造方法. 本文对受噪声污染的Lena

图像(信噪比为22. 35) 进行实验, 表5是三种分割算法的性能比较. 平均绝对误差是以表4中FCM 算法对标准Lena 图像分割后获得的聚类中心为参考进行计算的. 可见新算法对含噪图像的分割精度明显高于FCM 算法的分割精度, 尤其是基于第二种2D H 的新算法II , 其分割后的聚类中心更加贴近真实的聚类中心, 而且从分割结果图像上也可以看出三种算法分割效果的差异.

表5　三种算法对噪声污染的Lena 图像的分割结果比较

Tab. 5　Lena image wit h noise and segmentation result s comparison of t hree algorit hms

Algorithm FCM algorithm New algorithm I New algorithm II

Segmentation time/s

109. 907026. 938010. 5470

Clustering center 20,65,106,146,19924,66,105,142,19525,67,104,140,193

Segmentation difference/%

5. 62. 81. 8

4　结论

研究了FCM 聚类算法, 提出了2D H 加权FCM 聚类分割新方法, 并且合理引入塔形结构进行模糊

聚类, 从而实现了2D H 2PWFCM 算法在图像分割中的应用. 实验结果表明, 本文提出的2D H 2PWFCM 算法, 分割速度明显大于直接运用标准FCM 算法对原始图像的分割. 与此同时, 对低信噪比图像, 该算法的分割精度也高于FCM 算法, 尤其是基于第二种2D H 生成思想的2D H 2PWFCM 算法, 其分割性能优于基于第一种2D H 的2D H 2PWFCM 算法. 参考文献　R eferences

[1]　B EZDEK J C. Pattern recognition with objective function algorithms[M ].New Y ork :Plenum Press , 1981. [2]　丁　震, 胡钟山. FCM 算法用于灰度图像分割的研究[J].电子学报,1997,25(5) :39243.

DIND Zhen , HU Zhong 2shan. FCM algorithm for the research of intensity image segmentation[J].Electronic Jour 2nal , 1997,25(5) :39243.

[3]　ESCHRICH S , KE J , HALL L O. Fast accurate f uzzy clustering through data reduction[J].IEEE Transactions on

Fuzzy Systems , 2003, 11(2) :2622270.

[4]　YE Q X , HUAN G Z H , XIAO Q. Histogram based f uzzy C 2mean algorithm for image segmentation [J].Interna 2

tional Conference on Image , Speech and Signal Analysis ,1992(3) :7042707.

[5]　刘健庄. 基于二维直方图的图像模糊聚类分割方法[J].电子学报,1992,20(9) :40246.

L IU Jian 2zhuang. A f uzzy clustering method for image segmentation based on two 2dimensional histogram[J].Elec 2tronic Journal , 1992,20(9) :40246.

[6]　L IU J Z ,XIE W X. Pyramid segmentation of color images using f uzzy c 2means clustering algorithm[J].Proceedings

of Computer , Communication , Control and Power Engineering , 1993(2) :113021133.

[7]　高新波, 李　洁, 姬红兵. 基于加权模糊c 均值聚类与统计检验指导的多阈值图像自动分割算法[J].电子学报,

2004,32(4) :6612664.

GAO Xin 2bo , Li Jie , J I Hong 2bing. A multi 2threshold image segmentation algorithm based on weighting f uzzy c 2means clustering and statistical test [J].Electronic Journal ,2004,32(4) :6612664.

[8]　杨守义, 罗伟雄. 一种基于高阶统计量的图像平滑去噪法[J].中国图像图形学报,2002,7(7) :6542657.

YAN G Shou 2yi , L UO Wei 2hong. A smoothed method of image noise based on high order cumulant [J].Journal of image and graphics ,2002,7(7) :6542657.

(编辑　白茂瑞)

A fast im age segmentation algorithm based on f uzzy clustering

YA N G R un 2li n g

1, 2

, GA O X i n 2bo , J I E J un

21

(1. School of Information and Control Engineering , Xi πan Univ. of Arch. and Tech. , Xi πan 710055, China ;

2. School of Electronic Engineering , Xidian Univ. , Xi πan 710071, China )

Abstract :This paper studies the application of f uzzy c 2means (FCM ) clustering algorithm in the image segmentation , and a fast image segmentation method is presented based on a 2D histogram weighting FCM algorithm. Firstly , by combining original image and its smooth image , a generalized image is constructed. Secondly , the 2D histogram is decomposed into a pyramid structure with 2layers (one upper and one lower ) . Finally , the weighting FCM algorithm is performed on the two layers respectively to implement the original image segmentation. The experimental results illustrate that the pro 2posed algorithm can implement image segmentation quickly and suppress the noise effectively.

K ey w ords :image segmentation ; wei ghting f uz z y c 2means cl ustering al gorithm ; p y rami d st ructure ; 2D histog ram

Biography :YAN G Run 2ling , Associate Professor , Candidate for Master , Xi πan 710055, P. R. China , Tel :[**************]9,E 2mail :

fengling0303@163. com

(上接第275页)

[6]　L EEN S K ,RO Y D C P. Information management to integrate cost and schedule for civil engineering projects[J].

Journal of Construction Engineering and Management , 1998,124(4) :3832389.

[7]　CL EV AN T A B. Harvesting the value of information [J].Journalof Management in Engineering ,1999,15(4) :37242. [8]　KAREEM A , K L IN E S. Performance of multiple mass dampers under random loading [J].Journal of Structural

Engineering 1995(121) :3482361.

(编辑　白茂瑞)

Applied study of attributes synthesis on assessing

the monomer house perform ance

X U Yong 2ge , L I U Guo 2g uo

(School of Management ,Xi ’an Univ. of Arch. &Tech. ,Xi ’an 710055,China )

Abstract :The synthesis evaluation for monomer house performance is an important constituent in the evaluation for the house and facility performance. The existing evaluation methods can provide a set of synthesis evaluation indexes for mon 2omer house , but they cannot f ully reflect each index πs importance degree , so they are not practical for buyers of the house. Based on the thought of ABC classification technique , the paper aims at reclassifying the indexes of the monomer house according to their importance degree in the light of dividing them into 4sorts , and thus forming the multi attributes classification. This new method ,the method of evaluation with multi attributes ,can overcome the defaults existing in the traditional methods of synthesis evaluation where the importance of various indexes can not be exactly reflected. Further 2more , because the new method can highlight the importance of various indexes of monomer house , it is really suitable for the actual situation , especially for buyers of the house.

K ey w ords :monomer horse ; sy nthesis eval uation ; f uz z y j ud gment

3Biography :XU Y ong 2ge , Associcate Professor , Candidate for Ph. D. , Xi πan 710055, P. R. China , Tel :[**************]9, E 2mail :

yongge @vip.sohu. net