1、 基于谱聚类的图像分割算法研究 071006308 郭晓媛 指导教师：管涛 摘 要 ：谱聚类能识别出在原空间中线性不可分的聚类，并且其效果优于传统聚类算法，谱聚类要想获得好的效果必须选择一个合适的尺度参数，本文针对自调节谱聚类算法和传统的谱聚类算法的缺陷，实现了一个可以自动的选取尺度参数的自适应谱聚类算法。它用全局 N近邻距离作为比例参数 s，达到了比其它传统聚类更好的效果。通过在 UCI 数据集上的实验对比和实际应用中的实验结果，表明了基于自适应谱聚类的图像分割算法适应性强、计算代价小、精度较高，性能优于或者不差于以往的类似算法。 关键词 ：图像分割；自适应谱聚类；聚类算法 Image Se
2、gmentation based on spectral clustering algorithm Abstract： Spectral clustering has been used to identify clusters that are non-linearly separable in input space, and usually outperforms traditional clustering algorithms. However, the performance of spectral clustering is severely dependent on value
3、s of the scaling parameter, This paper achieve a new algorithm to the overcom the draw backs of self-tuning spectral clustering and traditional spectral clustering,called as the adaptive spectral clustering(ASC), which can choose the scaling parameter automatically by using techniques similar to ker
4、nel selection. It takes average distance of N-near-neighbour as scaling parameter s, and could get better effect than other traditional spectral clustering. by the experiment contrasts in the UCI data sets and the results of experiments in applications show that the spectral clustering based on adap
5、tive image segmentation algorithm has stronger adaptability, lower calculate cost and higher precision. Its performance exceeds or at least not lower to the other similarity ones.We can see the characteristics and advantages of adaptive spectral clustering algorithm. Keywords: Image segmentation; ad
6、aptive spectral clustering; clustering algorithm一、绪论 图像分割作为图像处理与计算机视觉研究的难点和热点之一，其研究受到了各研究领域的高度重视，研究工作者对图像分割进行了广泛、深入的研究。图像分割几乎出现在有关图像处理的所有领域， 如在工业 自动化、生产程控、文件图像处理等。因此在这种情况下， 涌出了很多分割算法。但是这些算法都是针对某一类图像、某一具体的应用问题而提出来的，至今仍然没有提出适合所有图像的通用分割算法 。 本 文 先 简述了谱聚类算法的基础理论 、图像分割原理、 自适应谱聚类算法在图像分割中的应用 等 。然后 通过在 UCI 数
7、据集上的实验对比和实际应用中的实验结果， 得出了基于自适应谱聚类的图像分割算法 是 一种适应性强、计算代价小、精度较高，性能优于或者不差于以往的类似算法。 二 、 算法基础分析与图像分割原理 1. 谱聚类算法 定义 传统的聚类算法主要有 K-means 算法、EM 算法和模糊化的 C 均值 (FCM)算法等。这些算法都是建立在凸球形的样本空间上，当样本空间不为凸时，算法就会很容易 陷入局部最优。为了能够在任意形状的样本空间上聚类 且具有全局最优性，学者们研究出了一种新型的聚类算法，即 ： 谱聚类算法(Spectral Clustering Algorithm)。谱聚类是由数据点间的相似性建立矩
8、阵，即 ： 根据给定的样本数据集定义一个描述成对数据点相似度的亲和矩阵，并计算矩阵的特征值和特征向量，然后选择合适的特征向量聚类不同的数据点。 2. 谱聚类的算法思想 谱聚类算法的主要步骤： （ 1） 根据某种相似度的定义，由原始数据集建立表示样本集的相似性矩阵矩阵 S； （ 2） 由相似性矩阵构建拉普拉斯矩阵，并求解其 k 个特征值和特征向量，以特征向量做列，构建矩阵 H； A.2-way：将原始样本数据映射到一维空间（ k=1）； B.k-way：将原始样本数据映射到由 k 个正交向量组成的 k 维空间 M； （ 3） 将 k 维子空间 M 的行作为样本的新的数据表示，且基于这种新的样本表
9、示，将样本进行聚类。 A.2-way：在一维空间上根据目标函数最优原则划分，并在划分好的两个子图上迭代划分； B.k-way：利用传统的 k-means 或者其它传统聚类算法在 k 维空间上进行聚类。 3.自适应谱聚类算法 ASC 思想 自适应谱聚类算法 ASC的主要算法思想是：给定一组样本数量为 n，样本维数为 l 的样本 集 12, , ., lnS s s s R，将其划分为c 个聚类中，并给定一个大小为 h 的尺度参数集 12, ,., h ，首先根据尺度参数集 中的不同尺度参数构造出不同的相似性矩阵，进而得到不同的拉普拉斯矩阵，然后用迭代的方法（核选取的方法）求解出一个新的拉普拉斯矩
10、阵，利用这个新得到的拉普拉斯矩阵进行特征值分解以及后续的K-means 聚类。 4. 图像分割原理 图像分割是将整个图像区域分割成若干个互不交叠的非空子区域的过程，每个子区域的内部是连通的，同一区域内部具有相同或者相似的特性，这里的特性可以是灰度、颜色、纹理等。 分割出来的区域应该满足以下要求： （ 1） 分割出来图像区域的均匀性和连通性。其中，均匀性是指该区域中的所有像素点都满足基于灰度、纹理、彩色等特征的某种相似性准则，连通性是指该区域内存在连接任意两点的路径。 （ 2） 相邻分割区域之间针对选定的某种差异显著性。 （ 3） 分割区域边界应该规整，同时保证边缘的空间定位精度。 5. 图像分
11、割方法 （ 1） 阈值法 阈值分割法是简单的用一个或者几个阈值将图像的直方图分为几类，图像中灰度值在同一个灰度类内的像素属于同一个类，这是一种 PR 法。 （ 2）区域生长法 区域生长法是根据预先定义的标准，提取图像中相连接的区域的方法，它是利用区域的相似性即满足区域一致性准则对目标进行分割，是一种 SR 法。 （ 3） 边缘检测法 边缘检测法是基于图像不连续性的分割技术。由于一幅图像的大部分信息存在于不同区域的边缘上，而且人的视觉系统在很大程度上是根据边缘差异对图像进行识别分析。 三、 ASC 算法 思想 在图像分割中的应用 （ 1）在 matlab 中读取待分割的 RGB 彩色图像； （
12、2）将彩色图像从 RGB 空间转换到 LAB 空间，将所得的矩阵转换为样本数量为 n ，样本维数为 l 的样本集 12, , ., lnS s s s R； （ 3）用 2.1 节所给出的尺度参数选取方法确定一个大小为 h 尺度参数集 12, ,., h ； （ 4）构造一组相似性矩 阵 ()k n nAR ，定义为 2( ) 2e x p ( / )ki j i j kA s s ，当ij 时， ()0kijA ； （ 5）根据不同的相似性矩阵构造一组度对角矩阵 ()kD ， ()kD 主对角线上的元素 ()kijD为相应的相似性矩阵 ()kA 的第 i 行所有元素之和，进而构造出一组拉普拉
13、斯矩阵1/ 2 1/ 2( ) ( ) ( ) ( )k k k kL D A D ； （ 6）初始化 N，并赋值 1t ； （ 7 ） 对 于 给 定 的 1tN ， 计 算 矩 阵1n TTM k kkF L NN L的前 d 个最大特征值所对应的特征向量 12( , ,., )tdM m m m ； （ 8 ）对于给定的 tM ，计算矩阵1n TTN k kkF L M M L 的前 g 个最大特征值所对应的特征向量 12( , ,., )tgN n n n ； （ 9）置 1tt ，然后返回第（ 7）步直至收敛； （ 10）将得到的 M 进行归一化，并记归一化后的矩阵为 Y，其中2 1
14、/ 2/ ( )ij ij ijjY M M ； （ 11）把 Y 的每一行看作为空间 lR 中的样本，然后将这些样本用 K-means 算法进行聚类； （ 12）最后，把最初的样本点 is 划分为第 j聚类，当且仅当矩阵 Y 的第 i 行被划分为第j 聚类。 四 试验结果对比和分析 1.运行环境 本算法在 MATLAB7.1 环境下运行 ，所用系统为 windows XP。如图 1 图 1 算法运行环境 2. 演示图像分割的效果 图 2 原始图像 图 3 聚类结果 图 4 图像分割结果 3.用经典的图像分割算法与该算法进行对比分析 通过一系列的实验来验证自适应谱聚类的性能，我们从 UCI 机
15、器学习数据库中随机选取数据集进行实验，表 1 为数据集的特性，算法性能的评估以聚类的精度 作为 评估准则。 本文采用 k-means 算法和 Self-Tuning算法与自适应谱聚类算法 ASC 作 对比，如表2 所示： 其中， s0为样本数据的标准差，在实验中固定参数，重复试验 50 次。由表 2 可知，自适应谱聚类算法 ASC在 UCI数据集上的聚类效果明显优于 k-means 算法和Self-Tuning 算法。 在 UCI数据集上的实验证明了自适应谱聚类算法 ASC 在性能上优于其它两种算法，在图像分割上做的对比结果如下： 图 6 为 k-means 算法图像分割结果： 图 6 k-m
16、eans 算法分割图像结果 图 7 为 Self-Tuning 算法图像 分割 结果： 图 7 Self-Tuning 算法分割图像结果 将自适应谱聚类图像分割算法与k-means 算法 、 Self-Tuning 算法的图像分割 后 比较可以得出以下结论： （ 1）对自适应谱聚类算法 来说，聚类的区域数影响到聚类的结果，在允许的范围内，区域数越多， 分割出来的图像越清晰； （ 2）自适应谱聚类算法图像分割结果明显优于 k-means 算法和 Self-Tuning 算法，但在运行时间上来说，前者的运行时间明显要多于后两种算法； （ 3）自适应谱聚类算法对图像的大小也有一定的要求，即图像不能过
17、大。 由此可知，自 适应谱聚类算法中的迭代问题和循环问题还有待解决 。 参考文献 1Lihi Zelnik-Manor, Pietro Perona, Self-Tuning Spectral Clustering, 2004 2Francis R.Bach,Michael I.Jordan,Learning Spectral Clustering,2006 3蔡晓妍、戴冠中等，谱聚类算法综述，西北工业大学学报， 2008 4卜德云、张道强等，自适应普聚类算法研究，山东大学学报， 2009 5贾建华、焦李成 等，空间一致性约束谱聚类算法用于图像分割，西安电子科技大学学报， 2009 6张向荣等，基于免疫谱聚类的图像分割，西安电子科技大学学报， 2010 7丁亮、张永平、张雪英等，图像分割方法及性能评价综述，太原理工大学信息工程学院及宁波工程学院电子与信息工程学院，2010 8罗希平、田捷等，图像分割方法综述，模式识别与人工智能， 1999 9宋寅卯、刘磊等，图像分割研究方法及进展，电脑学习， 2010
