张竞丹 1，邓志东 1，郭百宁 2
1清华大学计算机系智能技术与系统国家重点实验室，北京，100084；
2微软亚洲研究院，北京，100080
zhangjd00@mails.tsinghua.edu.cn； michael@tsinghua.edu.cn；
bainguo@microsoft.com
摘要:本文提出了一种图象分割算法，它主要应用于基于内容的图象查询系统。本算法有效结合
了图象的局部和整体信息，可以在没有监督的情况下将彩色图象分割成带有较完整信息的区域。这
个算法由两个分割阶段构成：在粗分阶段，算法运用基于边界强度变化的区域生长算法进行局部最
优化的分割；在细分阶段，算法将粗分结果构造成一个无向图、定义了边的权重矩阵，并采用了全
局最优化的图划分技术。试验证明本算法能快速有效的对多种类型的真实图象进行分割。
关键词:图象分割，区域生长，正规化划分。
Two Stage Unsupervised Segmentation of Color Images
Jingdan Zhang1，Zhidong Deng1，Baining Guo2
1Department of Computer Science and Technology, Tsinghua University, Beijing, 100084 , China;
2Microsoft Research Asia. Beijing 100080
zhangjd00@mails.tsinghua.edu.cn; michael@tsinghua.edu.cn; bainguo@microsoft.com
Abstract In this paper, we present a novel image segmentation method, which is used in content-based
image retrieval system. This method efficiently combines the local and global information to achieve
unsupervised segmentation of color images and can divide images to meaningful regions. The method
consists of two steps: coarse segmentation and fine segmentation. In the first step, a region growth
algorithm based on the variation of edge’s intensity is used to segment images locally. In the second step,
the graph is constructed using the preliminary partition result and the weight of edges is calculated. Then
we use graph theoretic framework of normalized cuts to find partitions of the image. Experiments show the
effectiveness of this algorithm on real images.
Keywords Segmentation, Region growth, Normalized cut.
引言
图象分割是图象处理、分析的一项关键技术。在基于非特定目标、非特定环境的应用
中（如基于内容的图象查询系统），图象分割的要求是：在没有高层知识约束的情况下将
图象分割成有“意义”的区域。每个区域内的元素具有一致的“属性”和较完整的信息，
区域和区域之间有较明显的边界和差距。在分割结果中，一个物体对象内部的细节与颜色
渐变应被忽略，而且一个物体对象只应被表示为一个或少数几个分割区域。本文所提出的
分割算法主要是针对这类应用。
图象分割的方法众多，并且各自有不同的运用范围，并没有一种适合于所有图象的分
割算法[1]，这个领域的最新发展中，有基于象素聚类的 [9]，有基于马尔科夫链的 [10]。在这
些方法中，利用图划分的全局优化法是一类引人注意的算法。这类方法先把图象转化成一
个无向图 GV,E)，其中图象中的每个象素是图的顶点，图的边的权重表示象素之间的关
系紧密程度。在此基础上确定一个划分准则，然后利用图的划分算法对图象进行分割。这
类方法存在两个难点，一个是如何确定划分准则，另一个是如何在这个准则下进行划分。
在文章[2] 中，确定了最小相似度约束，并在此约束下利用最大流算法来进行图划分，但是
这个方法倾向于将图中的孤立点划分出来。文章 [3]对这个问题进行了修正，提出了正规化
的划分函数（Normalized cuts），并且在此准则下将NP难度的图划分问题转化成一个利
用求矩阵特征值得到次优解的问题。因为这种方法保证了全局最优性，因此能得到较好的
分割结果。但其缺点是当待分割图象较大时，计算量巨大。
也可以从局部入手进行分割，比较典型的是利用区域生长算法，这类算法比较常用于
医学图象的分割。如在 [4][5]中均采用了一定的区域生长准则，并通过此准则不断的对有相
同属性的区域进行扩张，直到达到稳定。在这方面让人重视的还有分水岭算法 [6]，这种算
法是通过在图象的不同区域同时进行区域生长，并且引入了相互竞争的概念。这类方法往
往能找到局部最优的分割，但是很难达到全局最优性。
也有不少方法是将局部和全局相结合，比较典型的如 [7]。在这篇文章中，作者先利用
区域生长法对图象进行粗分，然后再利用相似性约束对粗分区域进行合并，从而给出最后
结果。由于这种混合的方法能充分利用图象的局部和全局信息，因此具有较好的分割效果。
本文提出了一种新的图象分割方法，主要运用于基于内容的图象查询系统的彩色图象
分割。它利用一种基于边界强度变化的区域生长算法对图象进行粗分，并将结果转化成一
个无向图 GV,E)，然后利用 [3]中提出的方法在全局最优化约束的条件下进行细分。试验
结果表明此方法有效的结合了图象的局部和全局的信息，分割速度快，而且用它分割不同
类型的图，都能得到满意的结果。
2 分割算法
2.1 基本模块
算法的基本流程如图 1:
将粗分结果转化
用正规化划分割结果
区域生长法对
输入图象
高斯滤波
图象进行粗分成图 GV,E)分进行细分
图 1算法流程图
输入图象先进行高斯滤波，除去图象中的噪音并且对图象进行平滑。然后利用基于边
界强度变化的区域生长算法对图象进行粗分，粗分得到的每块区域有基本一致的颜色和较
强的轮廓。然后定义块和块之间的关系函数，计算权重矩阵，将粗分结果转化成无向图。
最后利用正规化划分对图进行递归二分切割，从而得到最后的结果。
2.2 基于边界强度变化的区域生长算法
进行粗分的目的是将图象预先分割成多个小块，每个小块有基本一致的颜色和较强的
边缘信息。在这里，我们采用了基于边界强度变化的区域生长 [4]的思想。它的特点是能够
找到复杂形体的边界，计算过程不依赖于物体的拓扑结构，并且能抵抗一定的噪音。它的
基本思想是模拟液体的侵蚀过程，即区域边界的生长速度受边界的曲率、边界的强度变化
的影响，并且在满足一定的条件时停止生长。可以这样设想这个过程：将一滴酸性液体滴
到金属表面，金属表面具有不同的抗酸能力，则液体在金属表面的扩散边界的形态会受到
其曲率和表面抗酸性的影响，其扩散过程就类似于我们所要实现的区域生长过程。
在算法具体的实现过程中，为了加快分割速度，我们进行了一定的简化。首先是不考
虑生长边界的曲率对生长速度的影响，其次是将基于边界强度变化的生长速度函数用一个
距离函数代替。以一个种子点进行区域生长的算法具体如下：
r
设s0是种子点， d(s)是距离函数， R是待扩展的点的集合， I(r) (s) 为点s的颜色， I
为已扩展的点的颜色的平均值。
a. 令R
={s0}，d(s0) =
0 ，其余的点的d值为+∞；
b. 若R为空，或是 R中的点的最小 d值大于 Threshold参数，则算法结束；否则进
行如下几步：
r
(1) 从R中取出d值最小的点s，标记其为已扩展点，更新I
；
(2) 检查点 s的八连通域，若其中点 q不是已扩展点，则计算 r
d
←d
(s) +
1 +
punish(I,I(q(r) )) 。若d
<d(q) ，则d(q) ←d
，并将q放入R。
其中 punish是一个惩罚函数，其目的是将生长边界的强度变化体现到距离函数 d
中。这样当边界颜色值变化越大，生长的速度越慢。在算法实现中，我们发现将 punish
函数定义成为一个二值函数即可产生较好的效果。
选取适当的参数，用这个算法可以快速有效的找到区域的边界。同时，这个算法可以
容忍一定的噪音。图 2是一个加有 20%高斯噪音的图象，可以看出这个算法可以承受一定
的噪音，准确的找到区域的边缘，是比较稳定的。
在实际计算时，开始我们把图象中的所有点设为未扩展点，然后选取任意未扩展点为
种子点进行一次区域生长，直到图象上的所有点都标记为已扩展点，最后的结果即是粗分
结果。注意种子点的选取方式对粗分结果有影响，但是因为最后还要进行全局最优化细分，
我们发现种子点的选取方式对最后结果影响不大。同时，一般输入的图像是自然图象，色
彩变化比较丰富，可能导致有过多细碎的区域。因为我们最后无需对这些细小区域进行分
割，因此可以将这些过小的区域合并到性质相似的大块区域中去，从而提高后面的细分速
度。
一个最小二分一个较好的划分
图2 用区域生长算法所得到的分割结果 图 3 最小二分会导致将图中的小块区域划分出来
2.3 构造无向图
我们把粗分结果变换成无向图G＝(V,E)，其中每个区域为图中的一个顶点，区域和
区域之间的的关系的紧密程度通过边的权值表示，关系越紧密，权值越大。一般来说两块
区域的关系紧密程度是由它们的颜色差异和距离差异决定的，两块区域的颜色差异越大，
则他们的关系应该越小，反之关系越大；同时若它们的距离越大，则关系越小，反之关系
越大。通过前面的粗分，每一块内部的颜色基本一致，因此我们可以用每一块的颜色的均
值来代表这一块的颜色。但是因为每一块的形状不固定，所以用这一块的几何重心来刻划
这一块的位置是不合理的。我们可以认为每个区域是由若干的象素点构成，两块区域之间
的相似关系由组成它们的点的相似关系的总和构成，这个方法类似于计算两个不规则形体
之间的引力的过程。
