一种新的基于图论聚类的分割算法

计算机科学2008V ol 35 9

一种新的基于图论聚类的分割算法*)

刘锁兰1, 2 王江涛2 王建国2 杨静宇2

(江苏工业学院信息科学与工程学院常州213164)

(南京理工大学计算机科学与技术学院南京210094)

摘要针对传统图论聚类法在分割图像时对噪声和模糊边界敏感, 产生伪割集以及计算复杂度大的问题, 对传统算法进行了相应的改进, 即首先将每个像素作为一类改为将图像中灰度相同的像素作为一类; 其次在计算权值时改进权函数定义, 将节点与区域间的空间近邻关系约束进权函数表达式, 而非传统算法中仅考虑节点与节点间的灰度和位置关系。对比实验表明, 该算法只需要设计少量的参数即可自动完成聚类, 所需的存储空间以及实现的复杂度相比于传统图论聚类法都得到极大改善。关键词图论, 聚类, 权函数, 分割

New Segmentation Technique Based on Clustering of Graph Theory

LIU Suo lan 1, 2 WA N G Jiang tao 2 WA N G Jian guo 2 Y A NG Jing yu 2

(Sch ool of Information S cien ce &Engin eering, Jiangsu Polytech nic University, Changzh ou 213164, China) 1(School of Computer S cience &T echnology, Nanjing University of Science &Technology, Nanjing 210094, China) 2

Abstract In image segmentatio n, the traditio na l method o f g raph theo ry clustering is sensitiv e to sa lt &pepper no ise and fuzzy edg es, pro duces much pseudo cutting set and comput ational complex it y. So , an improv ed appr oach is pro po sed in the paper. F irst, a new ly classify ing method is pro po sed, w hich is based o n the same gr ay values, r ather than the com mo nly used each pixel. T hen, the def initio n o f weig ht functio n is impr oved, w hich co nsiders the spatial relatio n between pixel and reg ions, not o nly the gr ay values and position r elation betw een tw o pix els. Ex per imental results show that the new method can automatically seg ment images with few er parameter s to other contr ast algo rithms, and the r equired st orag e space and r ea lized co mplexity g et sat isfied improv ement to the t raditio nal alg or ithm s. Keywords G raph theo ry, Clustering , W eight function, Segment

作为一类, 这样使得数据处理量极大且影响计算效率。基于此, 本文分别提出相应的改进方法, 以期解决上述问题, 从而改善图论聚类法在图像处理和分析领域的应用。

1 引言

图像分割是图像处理领域中极为重要的内容, 也是自动目标识别的重要组成部分。图像分割的应用非常广泛, 如对医学图像的分割能自动地描绘出医学图像中感兴趣的区域, 对交通图像的分析和对雷达图像的目标分解等等。图像分割的正确性和自适应性在一定程度上影响着目标检测和识别的智能化程度。在众多分割方法中聚类是最受欢迎的方式之一, 许多基于门限的图像分割技术都与聚类相关。早在1979年Coleman 和A ndrew s 就提出用聚类算法进行图像分割。在各种聚类方法中常见的有谱系法、图论法、目标函数法和统

[1 3]

计学方法等。其中, 基于图论聚类的分割技术是近年来图像领域研究的热点。图论法在图像领域的应用始于20世纪80年代, 它要求将图像映射为一个带权的无向图, 把像素当作节点, 构造最小支撑树, 利用最小剪切准则得到阈值从而实现图像的最优分割[2]。而连接每两个节点的边的权值表示此两节点属于同一类的可能性, 权值的大小与两节点的相似性、近邻性、连续性等密切相关。然而在实际中传统图论聚类法由于是以样本数据的局域连接特征作为聚类的主要信息源, 这造成该方法在图像处理领域应用的缺陷, 即无法处理类之间相互很接近的数据

[4]

2 图论聚类方法

2. 1 图论聚类理论及优缺点

图论聚类法最早是由Zahn 提出来的, 又称作最大(小) 支撑树聚类算法[5]。图论聚类法的前提是要把聚类的数据表示成一个带权的无向图。图是由一些节点以及连接节点之间的边或线所构成的几何图形。在图论中, 它可以反映一些对象之间的关系。两点之间不带箭头的连线称为无向边e i 。由点和无向边构成的图叫无向图, 简称图, 记作G =(P, E) 。其中P 是图G 的点集合, E 是图G 的边集合。

对无向图G 的每一条边(p i , p j ) , 相应地有一个数w 表示边(p i , p j ) 上的权。权函数一般定义为两节点之间的相似度。在基于图论的图像分割方法中, 常见的权函数表达形式如下[5]:

w (p i , p j ) =ex p (-! F(p i ) -F(p j ) ! 22/ ) *

exp (-! X(p i ) -X(p j ) ! 2/ X ) , if ! X(p i ) -X (p j ) ! 2

。另外, 在初始化时由于将每个像素

0, else

其中F(p i ) , F(p j ) 为节点p i , p j 的灰度值, X (p i ) , X (p j ) 为

*) 基金项目:国家自然科学基金重点项目(60632050) , 国家自然科学基金项目(60472060, 60472061) 。刘锁兰博士, 研究方向为图像处理、模式识别; 杨静宇教授, 博士生导师, 研究方向为模式识别理论与应用、计算机视觉、智能机器人技术等。

两节点的位置, !∀! 2表示一个矢量的二范数。为灰度高斯函数的标准方差, X 为空间距离高斯函数的标准方差, 因此和 X 分别控制权值w (p i , p j ) 对两节点p i 和p j 的灰度差异及空间位置差异的敏感程度。r 为两像素之间的有效距离, 是一个正数, 决定参与计算可能权值的领域节点的个数, 随着r 的增加, 参与计算权值的节点个数也增加, 同时计算量也相应地增大。但是若超过这一距离则认为两节点之间的相似度为0。可见, 此相似度函数认为两节点之间的灰度值越接近则相似度越大, 距离越近则其相似度也越大。

给图中的每条边e i 赋以权值w (e i ) , 那么最小支撑树(M ST ) 是指满足下列条件的支撑树:

w(M ST ) =min {#w (e i ) }

e ∃E i

间的灰度关系以及二维位置关系所引起的分割缺陷甚至错误, 最终得到较理想的权重描述、分割效率和分割效果。因此, 定义节点之间以及节点与区域之间的近邻关系, 并在此基础上构造空间关系的权函数表达式[7,8]。

定义1(节点之间的位置近邻关系)

p i , p j ∃G, 若d (p i , p j ) =! X (p i ) -X (p j ) ! 2表示节点p i , p j 之间的街区距离, 则说明p i , p j 具有距离为d (p i , p j ) j 的位置近邻关系。

此定义表明了距离d (p i , p j ) j 越大, 那么节点p i , p j 之间的位置近邻关系越弱。

定义2(节点与区域之间的近邻关系)

p i ∃G, 区域Z k ! G, 若节点p i 到区域Z k 之间的距离

(

根据文献[5, 6]进行如下聚类分割:

(1) 利用prim 算法在图G =(P , E) 上构造最小支撑树M ST ={(U , T ) |U =P, T ={e 1, e 2, %, e k -1}};

(2) 设定一阈值t, 从M S T 中删去权值大于阈值的边, 形成P 上的森林F ={(P, E &) |E &=T -{e &|w(e &) >t};

(3) 获得包含在森林F 中的所有树{(P i , T i ) |i =1, 2, %q}:F =∋(P i , T i ) , 其中∋P i =P , ∋T i =E &;

i =1

定义为D (p i , Z k ) =#[ex p(-d (p i , p n ) ) ], 则表示节点p i 区

n =1

k (

域Z k 之间具有距离为D (p i , Z k ) 的近邻关系。其中N k 表示区域Z k 包含的节点个数, p n 表示区域中的第n 个节点。

此定义说明了节点p i 与区域Z k 的距离D (p i , Z k ) 越大, 那么节点p i 与区域Z k 近邻关系越强。

因此, 综合考虑利用图论法分割图像时权值的计算和以下几方面因素有关:

(1) 与两节点的像素灰度差有关, 若差值越小, 则形成森林时对阈值度越高, 属于同一类的可能性就越大;

(2) 与两节点的邻近性、连续性及空间分布因素有关:(a) 与区域Z k 的面积有关, 若面积越大, 则节点属于区域Z k 的可能性就越大, 即w(p i , Z k ) ) N k ;

(b) 与节点到区域Z k 的距离有关, 若距离越大, 则属于区域Z k 的可能性就越大, 即w (p i , Z k ) ) D(p i , Z k ) 。

(3) 与和 X 相关。它们分别为正尺度因子, 控制权值w 对两节点的灰度差异及空间位置差异的敏感程度;

(4) 与r 相关。它决定了参与计算权值的邻域节点的个数, 随着r 的增加, 参与计算权值的节点个数也增加, 同时计算量也相应地增大。

在传统图论聚类法以每个像素作为一个节点, 依照灰度和部分空间关系计算权值时, 由于对噪声以及模糊边界敏感导致产生伪割集, 从而影响了分割效果。本文作如下算法改进:

(1) 在初始化时将灰度相同的像素p i 划分为一类, 而非将每个像素作为一类。根据像素灰度的不同把原始图像分为若干个子图。要求每个子图的像素灰度都相同, 因而最多可分为255个子图。每个子图都包含多个不连通但灰度相同的区域Z k ;

(2) 对每个子图进行连通域标记, 这样就把原始图像分成了若干个连通域, 连通域内灰度都相同;

(3) 将每个连通域作为一类;

(4) 计算权重。不但只计算连通域边缘节点间的权重, 还加入节点区域空间关系约束引起的权重即W =(1- ) w + w &, 其中 ∃[0, 1]为空间关系影响因子, w 为采用传统图论算法定义的权值, w &为利用了空间区域近邻关系所得的权值。定义w &={w (p i , Z k ) }={N k ∗D (p i , Z k ) /#[N k ∗D

k =1n

(4) 每棵树作为一个聚类, 完成分割。

由上述分析可以发现, 图论聚类方法解决的第一步是建立与问题相适应的图, 图的节点对应于被分析数据的最小单元(像素) , 图的边(或弧) 对应于最小处理单元数据之间的相似性度量。因此, 每一个最小处理单元数据之间都会有一个度量表达, 这就确保了数据的局部特性比较易于处理。图论聚类法是以样本数据的局域连接特征作为聚类的主要信息源, 因而其主要优点是易于处理局部数据的特性。

相对地, 图论数据聚类法应用于图像分割也存在缺点:它对椒盐噪声以及模糊边界比较敏感; 易产生伪割集; 分割速度慢。对噪声、模糊边界的敏感以及伪割集的产生, 其部分原因是由于边界权重是基于像素而不是基于区域, 但主要原因是图论方法的固有缺陷, 即无法处理类之间相互很接近的数据, 即它的相似性区分能力不够理想。若将图像中所有节点的灰度作为图像特征空间中的元素, 则传统图论聚类法就能对特征空间进行划分, 从而实现图像中目标的分割, 但是传统权值的计算仅考虑两节点间位置的近邻性并没有考虑节点与区域间的相关性, 即忽略了节点与区域之间的空间特征分布。2. 2 改进方法

通过上述对图论聚类方法的缺点分析可以看出, 边界权重基于像素而不是基于区域且计算时忽略了节点与区域之间的空间特征分布是对噪声和模糊边界敏感以及产生伪割集的主要原因。另外, 在初始化时把每个像素作为一类, 这样使得数据量极大, 且增加了计算复杂度。

由于图像经常被看成离散像素点的集合, 致使图像分割变成了单纯的对灰度进行统计的过程。传统的直方图阈值法、特征空间聚类等分割方法均如此[7]。它们不考虑像素间的有序性, 即忽略了像素间存在的空间关联。而事实上, 图像中目标分割不仅仅是对灰度情况统计, 像素间的空间近邻关系对于维持目标的完整性也起关键作用。

本文提出的改进权函数空间关系的图论聚类算法, 其基本思想是:首先在初始化时将灰度相同的像素划分为一类以降低计算复杂度, 然后在传统图论算法计算权重系数时通过增加节点与区域之间空间关系的约束来修正因仅考虑节点之

(p i , Z k ) ]}。

(5) 构造最小支撑树, 聚类, 实现图像分割。

实验证明改进算法能够有效分割出含噪图像中的目标主体及边界模糊的图像, 对类之间相互很接近的数据具有较强

的处理能力, 从而有效地解决分割过程中出现的伪割集以为目标分割不完整的问题。将灰度相同的像素作为一类具有更强的客观性和应用性, 相比于传统图论聚类法其存储空间以及实现的复杂度得到极大减化, 运行效率有明显的提高。

些领域得到应用, 其所涉及的图像类型也在逐步扩大。在医学领域, 可以利用图论聚类将脑部M R 图像分割成灰质(GM ) 、白质(WM ) 、脑脊髓(CSF) 等脑组织和其它脑组织区域等, 从而指导医学实验和手术过程, 如G amio l J C 和Be longie S J 等[10]将图论方法用于脊椎骨磁共振图像的分割; 在地理研究领域, 文献[11]首先借助聚类法将图像有效分割, 进而为目标自动识别提供特征参数; 在彩色图像处理领域, 文献[12, 13]利用图论和颜色理论将一幅彩色图像分成若干个理想区域, 分别对各区域进行处理, 从而实现分割; 在纹理分割领域, M alic J 等[14]将图论中的no rmalize cut 准则用于图像轮廓与纹理分析, 从而将图像信息分为干涉轮廓和纹理基元, 以及利用邻域像素及周围区域像素之间的关系构造最小支撑树, 再根据区域同质性要求形成森林, 实现纹理最优分割[15]。

随着应用的发展, 在图像处理领域对基于图论聚类的理论又提出了许多新的要求[13, 16]:在图像分割中聚类算法如何快速实现以满足应用要求; 如何把聚类技术同新的技术相结合从而取得更好的分割结果; 如何挖掘和利用实际应用中的先验知识, 并指导聚类才能在速度和质量上同步提高; 现有的聚类及模糊聚类都是针对静态数据的, 因而如何对运动情况下的目标进行有效分割还需在理论上继续开拓和创新。

3 实验结果对比分析

为了验证本文算法的有效性, 我们采用一系列的图像进行实验来测试其性能, 并分别设置权重因子 =0. 25, =0. 5

[9]

和 =0. 75。Sezgin 和Sankur 将所有的阈值分割方法根据它们所利用的信息的不同分为六大类:基于直方图的阈值分割方法; 基于聚类分割的阈值分割方法; 基于熵的阈值分割方法; 基于属性相似度的阈值分割方法; 基于空间信息的阈值分割方法以及基于局部信息的阈值分割方法。因此进一步将改进算法与传统图论聚类法以及选用上述六大类型中具有代表性的几种分割方法进行比较实验分析。为了使评价和比较更加具有实际意义, 选用的测试图像大多为实际图像, 每一个图像都包含有明确的目标和背景。结果如图(1) 和(2) 所示, 其中图(a) 为原始图像, (b) 为图(a) 的直方图, (c) 为用Ramesh 方法分割的结果, (d) 为用O tsu 方法分割的结果, (e) 为用Abutaleb 方法分割的结果, (f) 为用一维模糊划分最大熵法分割的结果, (g) 为用传统图论法分割的结果, (h) 为用本文方法分割的结果且 =0. 25, (i) 为用本文方法分割的结果且 =0. 5, (j) 为用本文方法分割的结果且 =0. 75

。

参考文献

[1][2]

Shi J, M alik J. Normalized cuts and image segmen tation [J ]. IEEE Transactions on PAM I, 2000, 22(8) :888 905

M urtagh F. A su rvey of recent advances in hierar chical cluste ring algorithms [J]. T he Computer Journ al, 1983, 26(4):354 359

章毓晋. 图像分割[M ]. 北京:科学技术出版社, 2001

Pavan M , Pelillo M . A new graph theoretic appr oach to cluste ring an d segmen tation [J ].C om puter Vision and Pattern Recog nition, 2003(1) :145 152

钱云涛, 赵荣椿, 谢维信. 鲁棒聚类+基于图论和目标函数的方法[J]. 电子学报, 1998, 26(2) :91 94

殷剑宏, 吴开亚. 图论及其算法[M ]. 中国科学技术大学出版社, 2003

刘华军, 任明武, 杨静宇. 一种改进的基于模糊聚类的图像分割方法[J]. 中国图像图形学报, 2006, 11(9) :1312 1316

陈大力, 薛定宇, 高道祥. 图像混合噪声的模糊加权均值滤波算法仿真[J]. 系统仿真学报, 2007, 19(3) :527 530

Sezgin M , Sanku r B. S urvey over image th res holding techniques and quantitative performance evaluation[J]. J ou rnal of Electron ic Imag e, 2004, 13(1) :146 165

Gam iol J C, Belongie S J, M ajumdar S. Normalized cuts for s pi nal M RI segm entation [C], Proc. CARS 2002. Paris, France, 2002

Zhu ykov A, S arycheva L. Cluster analysis of territories by the totality of ecological an d socioeconomic indices [J ]. Geoscience and Remote Sensing Sym posium, 2001(4) :1971 1972Vlach os T , Con stantinides A G. Graph th eoretical approach to color pictu re segmentation and con tou r classification [J]. Com munications , Speech and Vision, 1993, 140(1) :36 45

M akrogiannis S, Econ omou G, Fotopoulos S, et al. Segmentation of color images using multiscale clustering and graph theoretic region s ynthes is [J ]. IEEE T rans action s on Sys tems, M an and Cybernetics, 2005, 35(2) :224 234

M alic J, Belongie S, Leung T , et al. C on tou r and tex tu re analysis for image segm entation [J ]. Intl J ou rnal of Computer Vision, 2000, 5(1) :7 27

Ahmed H , Dask alakis C N, Xydeas C. A novel graph theoretic texture s egmentation algorithm [J ]. Intl Acoustics, Speech, and Signal Pr ocess ing, 1991(4) :2709 2712

高新波, 谢维信. 模糊聚类理论发展及应用的研究进展[J ]. 科学通报, 1999, 44(21) :2241 2251

[3][4]

[5][6][7][8][9]

[10]

[11]

从实验结果中可以看出对所有的测试图像采用本文方法均能从背景中将目标提取出来, 且随着参数的增大, 目标的完整性越强。这主要是因为越大, 则权函数中表达的节点与区域之间空间关系的约束性越强, 因而对类之间相互很接近的数据处理能力有显著提高。从结果中还可看出, 本文的分割方法较其它几种方法具有较好的适应性和鲁棒性, 不仅能完成较大目标的有效分割, 而且能完成较小目标的分割, 对边界模糊和含噪较严重的图像也显示出极佳的处理效能。另外, 在初始化时将灰度相同的像素划分为一类, 而非将每个像素单独作为一类, 这不仅缩减了算法所需的存储空间而且使得数据处理的复杂度得到了极大改善。

结束语基于图论聚类的分割技术已经在图像处理的一

[12]

[13]

[14]

[15]

[16]