网络出版时间：2011-03-14 16:57
网络出版地址：wwwki/kcms/detail/11.2127.TP.20110314.1657.001.html
2010-11-22
王虹，覃刘波
WANG Hong, Qin Liubo
武汉理工大学信息工程学院，武汉430063
Institute of Information Technology, Wuhan University of Technology,Wuhan 430063,China
E-mail:whong2002@vip.sina
WANG Hong, Qin Liubo. A method of image segmentation based on fast global K-means
algorithm and region merging
Abstract: In this paper, a method of image segmentation is presented, which base on fast global
K-means and region merging. Firstly, medial filter is used to remove the noise of target image.
Secondly, the initial segmented result is obtained by using fast global K-means clustering
algorithm in the color space. Finally, a region merging strategy is used to merge the initial regions
with the goal of forming the final segmentation result. The simulation results indicate that
compare with other methods, the segmentation result is well consistent with human perception,
especially in image details.新新电影
Key words:image segmentation; fast global K-means algorithm; region merging; clustering
analysis
摘要：提出一种融合快速全局K-means与区域合并的图像分割方法。该方法首先利用中值
滤波方法对图像去噪；然后运用快速全局K-means算法对图像的颜空间进行聚类分析；
最后结合区域合并准则，对初始分割合并得到最终的分割结果。实验表明，与同类算法比较，
本方法的分割结果在图像细节方面能够很好地满足人的主观视觉。
关键字：图像分割；快速全局K-means；区域合并；聚类分析
文献标识码：A 中图分类号：TP391
1引言
在计算机视觉和图像分析中，图像分割是指将图像中具有特殊意义的不同区域分开来，并使这些区域相互不相交，且每个区域应满足特定区域的一致性条件。图像一旦被分割，就
可以作进一步的处理，如基于内容的图像检索、分类及识别等。因此，图像分割是图像处理
和模式识别中的一个重要研究领域。早期的图像分割主要集中在灰度图像的分割上，近年来，
彩图像的分割也越来越受到人们的关注，原因有两点：1）彩图像能够比灰度图像表现
更多的信息；2）随着技术的进步，采集彩图像的手段越来越多。目前，最常用的图像分
割方法主要有：阈值分割法，边缘分割法，分水岭法，区域分割法等[1]。
K-means算法在数据挖掘，模式识别，机器学习等领域有广泛的应用，是最重要的数据分析方法之一[2]。它通过不断的迭代来实现聚类，当算法收敛到迭代条件时，得出聚类结果。
由于其思路简单，能够快速对大规模的数据进行分析，具有快速，易于实现的特点，因而，
它适合应用于图像分割领域。但其过分依赖于初始聚类中心，导致聚类结果不能够达到全局
最优，另外，利用它对图像进行聚类分析时，主要是利用颜空间信息，因而它对噪声会比
俞秀松较敏感。因此利用该算法进行图像分割时，如何降低噪声影响，以及快速确定初始中心，达
到最优解，成为一个急需解决的问题[3]。
本文结合全局最优化的聚类方法与区域合并思想，提出一种结合快速全局K-means[4]与区域合并的图像分割方法。该方法利用全局K-means对图像的彩空间进行聚类，由此得
到初始分割结果，接着利用区域合并准则，对得到的初始结果进行区域合并，并得到最终的
分割结果。
保障机制
作者简介：王虹（1962-），女，教授，研究方向：信息理论与信号处理、数字图像处理；覃刘波（1
983-），
男，硕士研究生，研究方向：图像处理与智能识别、信息传输与处理
2 方法原理及框图
本方法主要分为三个阶段：图像预处理，聚类分割，区域合并。
首先为了降低图像噪声的影响，我们对原始图像进行平滑滤波处理，该阶段为预处理阶
段。本文采用中值滤波处理，并得到处理后的图像[5]。
接着，利用快速全局K-means 聚类算法对图像的彩空间进行聚类分析。该过程主要是对图像的颜进行聚类分析，即对像素点的颜值进行聚类，得到初始分割。为了减少K-means 对初始聚类中心的依赖性，我们采用快速全局K-means 聚类算法。由于考虑了整个彩空间的颜值，聚类能够得到一个全局最优的结果，并具有一定的抗噪能力。
最后，结合 [6,8]提出区域合并准则，对初始分割结果进行区域合并，得到最终分割结果。运用快速全局K-means 聚类算法，仅仅利用了图像的颜信息，得到的分割结果中，被划分为同一类别的像素并不一定在空间上属于同一区域，而且不同区域之间也存在着一定的相似性，因此需要结合图像的颜信息和空间信息进行区域合并，得到最终分割结果。
3 3.1 如下：
1i X Y =Y 称为12...n X X X ，的中值。
我们把一个特定长度或形状的领域称为窗口，在一维中，中值滤波器是一个奇数各像素点的滑动窗口，窗口正中间的值用窗口各个像素的中值替代。设输入为2
{,}i X i I ∈，则滤波器的输出为： {}{.........}i i i n n i n Y med X med X X X −+==
我们把它推广到二维，则定义输出为：
2()(){}{,,),(,)}
i i i s j s Y med X med X s A i j I ++==∈∈ 彩图像彩空间属于高维的，我们分别对各个彩分量进行滤波，然后得到最终的滤波结果。去噪效果如图2所示。
科学中国人
(a)原图(b)中值滤波(c)高斯噪声(d)滤波结果
(e)椒盐噪声(f)滤波结果(g)乘性噪声(h)滤波结果
图2 原始图像与去噪图像的比较
从图像中，我们可以看到中值滤波器能够较为完美的消除图像中的随机噪声，达到实验的要求，因此本文中我们采用中值滤波器来对图像进行去噪处理。
3.2彩空间聚类与初始分割
在对原始图像做上述处理后，我们对去噪后的图像进行聚类分析，得到初始分割结果。在这一步骤中，本方法要求有较高的效率，并且能够满足精度要求。本文采用快速全局K-means算法对图像进行初始分割[7]。算法描述如下：
Step1[初始化]：计算所有样本数据的均值作为第一簇的中心：
1
1
1n
i
i
m x
n
=
=∑，并且设置q=1；
Step2[终止条件]：q=q+1，若q>k，转到Step5；
Step3[寻下一个簇中心]：以
121
,,...,
q
m m m
−
为前1
微计算机信息q−个簇中心，计算
2
1
1
max(,0)
N
j
n k n j
j
b d x x
−治理结构
=
=−−
∑，
选择使
n
b最大的样本点
n
x作为第q个簇的初始中心，令
q n
y x
=得到各簇新质心12
,,...,
q
y y y。其中，
1
j
k
d
−
表示
j
x与距离它最近的簇中心的距离，也就是
j
x距离它所属中心的距离；
Step4[算法循环]：令
i i
m y
=，1,2,...,
i q
=，转到Step2；
Step5[聚类算法]：结合得到的聚类中心，应用K-means算法进行聚类分析，得到聚类结果，算法终止。
从上述算法步骤中我们可以看到：首先利用循环得到聚类中心，然后利用聚类算法得到聚类结果。我们利用该算法对图像进行彩空间的聚类分割，并得到初始的分割结果。
下表中给出了针对不同的数据量，算法的耗时结果：
表1 不同样本数的耗时比较
样本数量
聚类
数目
耗时
中心聚类
256*256 5 2.841519 0.550430
300*300 5 4.615284 0.530334
321*481 5 8.856472 0.324832
说明：表1中，中心表示本方法到初始中心的耗时，聚类表示应用算法聚类的耗时，单位都为秒（s）。
上表中的数据是我们多次统计得出的平均值，由表中我们可以看到，随着数据量的增大，到初始中心所需要的时间会增大，聚类所需的时间在减小。
为了对比K-means与本文用到的聚类算法的时间消耗，我们做如下对比。表2中给出了针对不同的数据量，K-means与本文算法在聚类方面的时间消耗。
表2 不同样本数不同算法的耗时比较
样本数量 聚类 数目
耗时
K-means 本文算法
256*256 5 0.715562 0.830853
300*300 5 1.011004 4.516807 0.512946
321*481 5 1.087430 8.822781 0.313672
说明：表2中本文方法的时间消耗包括两部分，分别为：初始中心选择和聚类耗时。上述所有的耗时单位都为秒（s ）。由表2我们可以看到，虽然随着样本数量的不断增大，K-means 算法的时间在逐渐增大，本文算法到初始中心的时间消耗也在增大，这与Matlab 不善长于执行循环有关。但在实际应用中我们一般采用编译型语言C++实现，来提高算法效率，有研究表明，C++写出的并行算法效率，是Matlab 的20-50倍。
3.3 区域合并准则
运用上述算法得到的初始分割仅仅利用了图像的颜信息，得到的是一个过分割结果，经过聚类后各像素点按照颜值被划分到不同的类别中去，区域之间还有很多的相似性。结
合[6,8]的合并策略，我们给出一种区域合并准则，对初始分割结果进行区域合并，得到最终分割结果。
3.3.1 区域距离度量准则
区域距离度量是衡量区域是否能够进行合并的一个重要指标，它直接决定区域合并后的效果以及图像分割的最终结果。结合图像的颜、空间和邻接信息，我们判定进行区域合并的必要条件为：两个独
立的区域在彩空间上相近，空间上相邻，在区域的邻接处没有显著的边缘出现。
式（1）给出了初始分割后的颜距离： *i j
color ij i j i j N N D N N μμ=−+ （1）
其中i N 与j N 分别表示第i 和第j 个区域所包含的像素个数，i μ与j μ表示这两个区域的颜均值，*表示欧氏距离。
式（2）给出了区域的边界距离：
2edge
ij i j D μμ=− （2）
式（3）给出了区域距离度量准则函数
**1color edge
D p D q D p q ⎧=+⎨+=⎩
（3） 式（1）中的分子部分乘积使包含像素数目较少的区域与其它区域的颜距离减小，从而能 够有利于小区域的优先合并，保证了分割的高效性与准确性。式（2）中的边界距离有利于 平缓过渡的区域优先进行合并。由于颜距离与边界距离所处的数量级并不相同，因此， 式（3）中的p 与q 是用作调节两种距离的作用大小。本文采用区域邻接矩阵来存储区域 之间的邻接关系。
3.3.2 终止区域合并准则
应用上述区域合并准则，我们可以对聚类后的区域进行合并，但何时停止合并过程才能得到一个理想的结果是一个十分重要的问题，这直接关系到图像分割的最终结果。传统的终止合并方法有基于阈值的和区域数目的，但基于阈值的方法很容易受到局部区域的影响，而且需要根据不同的图像来进行调整，基于区域数目方法要根据不同的图像，人工进行数目调整。本文我们给出一种新的区域合并终止准则。
假如图像I 中包含N 个像素，定义颜的均值与方差如下：
()X mean I = （4）
21()t x X S x X N
∈=−∑ （5） 设图像I 经过合并后包含有l M 个区域，定义区域的均值与方差如下： ()r r X mean
I = （6）
2
1111()l l r M M N r r R i j i i j S S x X N =====−∑∑∑（7） 其中1,2,...,l r M =，r N 表示第r 的区域的像素数目，r j x 表示第r 个区域的第j 个像素的颜值。
我们定义颜散度函数如下：
/t R S S S = （8）
由函数定义，我们可以看到，本质上S 是图像区域内颜的方差t S 与各区域方差之和R S 的比值。t S 越大，表明图像区域内的颜越不相似，R S 越小，表明区域内颜差别越小。当图像区域中只包含一种颜时，I 就为图像一致区域，此时0S =。随着区域的不断合并，也即M 的不断减小，图像的颜散度会不断增加(0~1)S ∈，当图像内的所有区域合并为一个区域时，S 达到1。我们定义/l l m M M =（0~1）为剩余数目比例。以图2中的图像为例，我们得到S 与l M 之间的关系曲线图。
图3 图像颜散度曲线图
在图像分割中，我们希望用尽可能少的区域表示一幅图像的信息，即l m 越小越好，然而从分割效果来看，我们希望分割后图像区域内的信息损失的越小越好，也就是颜散度S 越小越好，但从图2来看，这两个问题是矛盾的，它们不可能同时达到最小值，因为每合并一次区域S 就会增大，为了得到理想的分割结果，我们定义
*l Y S n m =+ (9)
这里[/]l n S M =用来调节l m 与S 对分割结果的影响。当Y 达到最小值时，也就是终止合并时，剩余区域数目l M 与图像区域散度S 达到最佳的方案。
3.3.3 区域合并实现算法
区域合并具体实现如下:
(1) 假设共有m 个区域，定义邻接矩阵(,)a D m m ；
(2) 如果区域i 与区域j 邻接，则(,)1a D i j =，否则，(,)0a D i j =；
(3) 判断式(9)中的Y 是否达到最小值，若没有，则执行步骤(4)，否则终止算法，得到结果；
(4) 搜索区域距离D ，得到距离最小的两个区域，设区域标号为,t s ；
(5) 搜索邻接矩阵(,)a D m m ，若(,)1a D t s =，则进行合并，否则，令(,)D t s =+∞，返回
步骤(3)。
3.3.4 区域合并预处理—区域重划分
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议