聚类分析及其在图像处理上的应用

1、聚类分析及其在图像处理上的应用1绪论1.1基于聚类的图像处理的研究现状聚类分析在图像处理中应用广 泛，其中一项重要的应用就是图像分 割。图像分割多年来一直受到人们的 高度重视，各种类型的分割算法相继 被提出。虽然人们在图像分割方面做 了许多工作，但是至今仍没有通用的 分割算法，也不存在一个客观的评价 准则。大多数分割算法都是针对一种 具体类型的图像提出的很难适用于所 有图像。实际上由于各个领域的图像 千差万别，也很难提出万能的分割算 法。基于聚类的图像分割方法是图像 分割领域中一类非常重要且应用广泛 的算法。2聚类分析概述2.1聚类的定义聚类的目的是将有限个无标注数 据划分到有限个离散的组或类

2、中，发现数据隐藏的部结构。Backer和Jain 1指出 数据的划分是依赖于所选择的相似性 度量的，通过主观地选择相似性度量 来达到有的的划分。至今，人们并没有 对聚类给出一个统一的定义。多数研 究者都是从部同质性和外部可分性对 聚类簇进行描述，即同类数据对象问 应该彼此相似，不同类间的数据对象 应该不相似3。在给出聚类的数学描述 之前，首先介绍与聚类有关的一辟术 语和数学表达方法。样本：指要进行聚类的数据集中的单个数据。样本一般是一个多维向量，向量的每个分量可以是数值型或者名词型的数据，一般称为特征或者属性。样本集：或称数据集，是由单个样本所 组成的集合，即是需要聚类操作的数 据整体，通常表

3、示为一个矩阵。相异度矩阵：该矩阵中的每个元素表$样本集中的每对样本之间的相异程 度，一般是非负值。相似度矩阵：该矩阵中的每个元素表 小？样本集中的每对样本之间的相似 程度，一般是非负值。类：或称簇，指通过聚类而形成的一组 同一类中的样本具有相似的特征。通 常用C或K表示类的个数。类原型：能够代表某个类性质的数据兀，可以是某类样本中的一个样本，或者是某类样本的一个加权值,也可以是能描述一个类特征的向量。划分矩阵U n*K：矩阵中的每个元素表示每个样本属于各个类的模糊隶属度K0 < utk < 1 口 以法二 LM ,且止之】，在此K表?样本标号,k表类标标号。通常获得的数据类型有两种

4、：一是数 据矩阵，二是相异度矩阵（相似度矩 阵）。假定数据集中有 n个样本：Xi ,i=1,2,.,n,每个样本有 p个变量（特征属性），则这n个样本可表 示成n*p（n个样本xp个变量）的数据 矩阵。Ml为2工1必区2【422X2p * * *,*入门1处12-*（2-1）其中每个对象对应为一个p维向量：r修二卜” t * .户ip）（2-2）1.2聚类的数据类型相异度矩阵存储的是n个样本两两之 问的相界度，表现形式足一个n*n维的 矩阵。I 0妣1)0J(3,1) dt 2) 0* *鲁fl4-I-din.)虹 2) 0(2-3)在这里d(i,j)是样本i和样本j之间 相异性的量化表示，通

5、常是一个非负 的数值，当样本i和样本j越相似， d(i,j)的值就越接近0;反之，两个样 本越不相似，的值就越大。d(i,j)= d(j, i),且 d(i,j)=0,因此得到形如(2-3)的矩阵。图像数据的表示日常应用中得到的图像一般分为两类：灰度图像和彩色图像。灰度图像的数值表示为一个二维矩阵I m*n图像 一共包含m*n个像素。在此，m和n分 别代表图像的高和宽，(ij)表示位于 第i行和第j列的像素，Iij表小其灰 度俏。彩色图像的数值表示为一个三维矩阵I m*n*3,像素的个数仍为m>n,3表示三个颜色通道，每一层的二维矩 阵表示该图像在某一个颜色通道的数 值。位于位置(i,j

6、)的像素对应的 颜 色特征向量表示为 I(i,j,1),I(i,j,2),I(i,j,3)。在许多t#况下，色彩是描述一幅图像 最简单有效的特征，而且人眼对色彩 的分辨率大大高于对灰度图像的分辨 率，因此彩色图像所携带的信息远远 大于灰度图像。一般的图像处理技术 最先应用于灰度图像，然后发展到彩 色图像，图像分割也不列外。颜色特征 可以来自于不同的颜色空间，不同的 颜色空间以不同的方式对图像颜色进 行描述。一共有四种不同的颜色空间： RG射色空间、XYZ颜色空间、HIS颜 色空间、Lab颜色空间。RGB®色空间 是基本的颜色空间，RGB对应于红(R)、 I(G)、蓝(B)三种基色，其

7、余所有颜色 空间都可由RGB颜色空间经过线性或 非线性变换得出的。给定一幅待分割的图像，我们可以直接获得像素的位置信息，灰度值 （灰度图像）或者RG的色特征值（彩色 图像），这些特征也是图像分割中最常 用的特征属性。但是对于一些复杂图 像,单纯依赖这些底层特征不能得到 满意的分割结果。基于这些底层特征， 人们提取了更多有效的特征 ，其中常 用的有描述物体表面灰度变化的纹理 特征和根据特定对象的先验信息加入 的形状特征。最近，人们开始借助一辟 先进的电子产品提取深度信息，通过 加入这辟高层特征来改善对特定类图 像的分割结果。在提取特征之后，就可以得到每 个像素点的一个向量表小 ，也就可以 看成是

8、高维空间中的一个数据点。但 是，像素点又和传统的数据不同，每个 像素点在阁像中的位置是固定的，每 个像素点的邻域像素点都可以直接通 过位置信息获得，这一特性也在图像 数据的相似度计算上得以体现。2.3聚类算法近些年来，聚类分析一直是研究 热点问题。基于相似度矩阵的聚类算 法指的足给定相似度矩阵的情况下即 可进行聚类处理的算法。只要给定相 似度计算模型，则基于相似度矩阵的 聚类算法也可以处理数据矩阵，即首 先根据数据矩阵计算出相似度矩阵，然后利用基于相似度矩阵的聚类算法 进行聚类。2.3.1 基于数据矩阵的聚类算法基于数据矩阵的聚类算法只能处理数据矩阵对象，其中很多经典的类原型聚类算法都可以划分

9、到这一类聚一个簇可以由类原型表示，达到对原类算法中,如K均值型聚类算法，模糊C 均值型聚类算法（FCM）, EM®聚类算法 等。这辟算法之所以称为类原型聚类 算法，是因为每个类可以由类原型来 代表，在对数据进行划分的同时也给 每个类找到具有代表作用的类原型。有的数据集的压缩编码，这也可以说(2-5)是聚类的另外一个功能。给定一数据 矩阵凶n*p表示n个p维样本。K均值算法K均值算法将n个样本划分到K个 簇C = C1,C2,。9，使得簇样本具 有较高相似度，簇间样本具有较低相 似度。设V= VI, V2,Vk为K个类 对应的类中心(类原型)，其中Vk是第 Ck个簇中样本的平均值，每个

10、族可以 由对应的类原型来表示。K均值算法通 过最小化类误差平方和准则函数来对 数据进行划分，其目标函数定义如下：荣尤0 = 2 -躁俨七二1君EC*(2-4)在此Ck包含所有到第k个类中心 Vk距离最小的样本点，可描述如下。C - I片 w 川k = arg min |x(- - 广 网IN-用£为a为Vjk =IQI(2-6)K均值算法是一个贪心算法，通过 迭代地更新类中心和各个簇成员来得 到公式(2-4)的局部最优解。K均值 聚类算法主要包括以下几个步骤：1 .初始化：随机选取个样本作为 初始的类中心；2 .样本指派：计算样本到各个类 中心的欧氏距离，将样本划分到距离 其最近的类

11、；3 .更新：重新计算每个新簇的类 中心；4 .重复步骤2和3直到簇样本不 再发生变化后停止。K均值算法的主要优点有收敛速 度快，储存空间小，时间复杂度低等。 一般的K均值型聚类算法的时间复杂 度为O (nKt),其中n是数据集中样 本的个数，K是期望聚类的个数，t是迭代次数。要根据相似度模型计算出相似度矩模本C均值算法Dunn在1973年提出模糊C均值聚类思想，之后Bezdek把这一工作进一 步推广到一个模糊目标函数聚类的优 化算法，并证明了该算法的收敛性。模糊C均值聚类算法给出每个样本属 于各个类的程度，即隶属度(menibershipvalue)。相比K均值聚类的硬化分,模糊划分更丰富地

12、反映了样本与各个类原型的相关度，从而可以更好的推测数据集的部结构。2.3.2基于相似度矩阵的聚类算法基于相似度矩阵的聚类算法是以相似度(相异度)矩阵为基础。如果数据是用数据矩阵的形式表现的，在使用基于相似度矩阵的聚类算法之前 阵。与基于数据矩阵的聚类算法相比， 这类算法使用起来更灵活，无论输入 是数据矩阵还是相似度矩阵都能够进 行聚类操作，相反基于数据的聚类算 法则不能处理只给出相似度矩阵的聚 类问题。然而，一些应用领域往往无法 给出明确的数据矩阵，而是给出一辟 数据点白关系(如相似度)，社团分析 中常碰到这类情况。直接使用相似度 矩阵进行聚类的典型聚类算法有基于图的聚类算法、基于类原型的 K

13、中心算法(K-medoids)和AP聚类算法、层次聚类算法以及基于密度的聚类算法等。基于图的聚类算法基于图的聚类算法是一类基于无向图的聚类算法。假定将侮个样本看 作图中白顶点V,根据样本间的相似度 为顶点间的边E赋于权重W这样得到 一个基于样本相似度的无向加权图G=(V,E)。将样本映射到图之后，可以 使用图论中很多成熟的理论来进行聚类，一类非常流行的基于图的聚类算 法是谱聚类算法，这类算法也是本文 的基础算法，很多相关实验也是基于 这类算法完成的。因此，下面会比较详 细的介绍几种常用的谱聚类算法。谱 聚类算法的思想源于谱图划分理论，其本质是将聚类问题转化为图的 最优化分问题。与传统聚类算法假

14、设 一样，基于图论的最优划分准则也是 使划分的子图部相似度最大，子图之 问的相似度最小。不同的划分准则会得到不同的聚类结架。表 2.1给出了 一辟常见的划分准则。由于图划分问题的本质，求图划 分准则的最优解是一个NP难问题。求 解图划分问题一个主要的工具是图的 拉普拉斯矩阵法（Laplacian matrices）。这类矩阵的学习已经形成 了一个完整的体系，称为谱图论早在 1973年,Donath 和 HoffmanfN 就提出 利用图的邻接矩阵的特征向量来求解图划分问题。同年,Fiedlerl发现了图的2-way划分与该图的拉普拉斯矩阵对应的第二小特 征信对应的特征向量有密切关系，并提出使用

15、这一向量对图进行划分。这 一特征向量代表了最佳图划分的一个 解（即势函数），后来将这一特征向量 命名为Fiedlerl 向量。基于谱图理论，原来的图划分问题 就可以转换成求解相似度矩阵或 Laplacian矩阵的谱分解问题，因此将 这类方法统称为谱聚类，可以认为谱 聚类是对图划分准则的逼近。AuthH.lef.McAodObrcwt Rhcbuii附Minim岫 cut幽A,用= £ %ShiiVlik1*厢Mi同EL跟队用=堕力言自强暧Rark加加财尚二湍蜂四明版刖3Mm（儿盼瑞1工 *I F-fr', >'D谱聚类中常用的相似性度量为空间相似性计算模型中的高

16、斯型相似性计算方法。相似度矩阵通常用W或A表示，有时也称为亲和矩阵（AffinityMatrix), Wij = Wji=Sij 。在得到相似度矩阵后即可求解拉普拉斯矩阵，不同的文献可能使用不同类型的拉普拉斯矩阵，不同的拉普拉斯矩阵即得 到不同的谱映射方法。在给出不同类型的拉普拉斯矩阵之前，先引入矩阵 D。D为对角矩阵，.二小啊即可 以看作是每个顶点的度，所以也称为 度矩阵。图的拉普拉斯矩阵分为两类：非规拉普拉斯矩阵和规拉普拉斯矩阵。非规拉普拉斯矩阵定义为：L= D-W(2-7)规的拉普拉斯矩P$有两种形式，分别为：= D'l/2LD-lf2 =/一 DWif2(2-8)Lrw = /

17、7附(2-9)在此将第一个矩阵标记为 Lsym, 因为该矩阵为对称矩阵；第二个矩阵 标记为Lrw,因为该矩阵与随机游走有密切关系。根据不同的准则函数及谱映射方 法，文献中已提出很多种不同的谱聚 类算法。众多的谱聚类算法中应用最 广的要数Shi和Malik提出的Ncut谱 聚类算法_,Ng等。人提出的NJW算法。 Ncut算法最初是用于求解两类问题， 可以迭代地对之前步骤得到的子图进 行划分来得到期望的聚类个数，所以 也属于迭代谱聚类算法中的一种。NJW 算法是针对多类问题提出，使用更多 的特征向量并且直接计算 k路分割对 数据进行聚类。谱聚类算法的主要优势在于该类 算法对簇的形状没有很强的假设

18、，可 以处理更一般化的聚类问题。K均值聚 类算法建立在球形的样本空间上，适 合发现千犬簇，对于含有任意形状簇 的数据集往往得不到期望的聚类结 果。处理更多类型的数据集是近几年 谱聚类流行起来的主要原因。但是也 正是由于谱聚类是直接基于相似度矩阵的聚类算法，不同的相似度矩阵得 到的聚类结果可能会有很大差界。K中心点方法K中心点方法也可以看作是K均值 算法的一个变形算法，之所以将其归 类为基于相似度（相异度）矩阵的聚类 算法是因为K中心点算法选用族中位 置最中心的对象作为类代表点 （类中 心），而不是簇中对象的平均值（质 心）。K中心点方法仍是基于最小化所 有对象到类中心之间的相异度之和的 原则来

19、执行，在已知对象与对象间的 相异度时，该方法就能对对象进行聚 类。K中心点方法采用中心点来代替质 心，减少了对噪声和孤立点数据的敏 感程度。K中心点聚类算法的基本策略是： 首先为每个族随机选择一个代表点；剩余的数据点根据其与代表点的距离 分配给最近的一个簇。然后反复用非 代表点来替换代表点，以改进聚类的 质量，降低聚类质量的代价函数，即数 据点到其类代表点的平方误差和。每 次代表点替换发生时，检查代价函数 是否降低，如果降低则保留替换，否则 放弃该替换，重复上述过程直到代价 函数不再发生变化为止。给定聚类数 K,典型的K中心点聚类算法的主要步 骤概括如下：1 .初始化：随机选取足个样本作 为初

20、始的中心点；2 .样本指派：计算样本到各个类 中心的距离，将样本划分到距离其最 近的中心点所代表的簇；3 .类中心替换：随机地选择一个 非类中心点，计算用选中的样本代替 原来的类中心的代价函数，如果代价 函数降低，则替换原有的中心点形成 新的K个中心点集合；4 .重复步骤2和3直到类中心点 不评发生变化后停止。PAM （Partitioning AroundMedoids )是最早提出的K中心点算 法之一。虽然K中心算法比K均值算 法在处理噪声点时表现的要健壮，但是K中心点算法的执行代价比 K均值 方法高，其时间复杂度为如果数据集 规模和类的个数较大，PAM算法的效率 会很低为了用K中心点方法

21、处理大规 模数据集，Kaufman和Rousseeuw将抽 样方法和PAMT法结合提出了 一个新 的尺中心点方法，称为 CLARA(Clustering LARge Applications)算法 CLARAB法 + 再考 虑整个数据集，而是从整个数据集中 进行抽样，选取数据中的一小部分作 为数据的样本，然后用PAMT法从这些 选中的样本中选择中心点。为了减少 抽样样本对最终聚类的影响，CLARA算 法采取多次抽样，对每次抽样样本应 用PAMT法，返回这几次抽样最好的聚类结果作为最终 结果。通过抽样处理，CLARA算法一次 抽样的时间复杂度为对),其中s是抽样样本的大小。CLARA?法的一大缺

22、点是 不能保证最佳的个类中心点被选中为 最终的类中心点，如果在抽样的时候 这辟数据点没有被抽中，那么CLARAT法将永远找不到最佳聚类。为了改进CLARAJ法的聚类质量，Ng和Han提出 了 CLARAN潴法(Clustering LargeApplications based upon RANdomizedSearch),该算法也采用了抽样技术，但是在搜索的每个阶段不诉使用一个固定的抽样集合，而在搜索的每一步都会随机的抽取样本，其时间复杂度为5岛)。CLARANS法的聚类质量也依 赖于所用的抽样方法。3实验与分析针对相似度计算模型和数据特征两方 面的工作，实验分为两部分：基于不同高斯型相似度的实验结果和基于不同 特征的实验结果。每部分都使用模拟(a)(b)数据及实际数据对相应方法进行测试 聚类算法选用NJW倍聚类算法。3.21基于不同高斯型相似度的聚类结 果下面给山基于六种高斯型相似性度量 的聚类结果。六种相似性度量分别为： 标准高斯核相似度(SC)自适应高斯 核相似度I(STI)、自适应高斯核相似 度n (STH)局部密度的自适应相似度 (CNN)加权自适应相似度I (WSTI)以 及加权自适应相似度n (wsTn)。3.3模拟数据首先对模拟数据进行实验，部分数据 集来自文献。对于各种相似