谱聚类算法及其在图像分割中的应用 1 引言 在对图像的研究和应用中，人们往往仅对图像中的某些部分或者说某些区域感兴趣。这些部分常称为目标或前景（其他部分称为背景），它们一般对应图像中特定的具有独特性质的区域。为了辨识和分析目标，需要将它们从图像中分离提取出来，在此基础上才有可能对目标进一步利用。图像分割就是指把图像分成各具特性的区域并提取出感兴趣目标的技术和过程。这里的特性可以是像素的灰度、颜色和纹理等，预先定义的目标可以对应单个区域，也可以对应多个区域。 多年来，对图像分割的研究一直是图像技术研究中的热点和焦点，它不但是从图像处理到图像分析的关键步骤[1]，而且是计算机视觉领域低层次视觉中的主要问题。图像分割的结果是图像特征提取和识别等图像理解的基础，只有在图像被分割后，图像的分析才成为可能。 图像分割在实际应用中已得到了广泛的应用，如图像编码、模式识别、位移估计、目标跟踪、大气图像、军用图像、遥感图像、生物医学图像分析等领域。同时，图像分割也在计算机视觉和图像识别的各种应用系统中占有相当重要的地位，它是研制和开发计算机视觉系统、字符识别和目标自动获取等图像识别和理解系统首先要解决的问题。概括地说只要需对图像目标进行提取测量等都离不开图像分割。 对分割算法的研究已经有几十年的历史，至今借助于各种理论已经提出了数以千计的分割算法[2]，而且这方面的研究仍然在积极进行。尽管人们在图像分割方面做了许多工作，但至今仍无通用的分割算法，也不存在一个判断分割是否成功的客观标准。因此已经提出的分割算法大都是针对具体问题的，并没有一种适合于所有图像的通用的分割算法。实际上由于不同领域的图像千差万别，也不可能存在万能的通用算法。 现有的分割算法非常多，大体上可以分为以下几类：阈值化分割、基于边缘检测的、基于区域的、基于聚类的和基于一些特定理论工具的分割方法。从图像的类型来分最常见的：有灰度图像分割、彩色图像分割和纹理图像分割等等。本文所要介绍的基于谱聚类的图像分割，是基于聚类分析方法中的一种。传统的聚类算法是建立在凸球形的样本空间上，当样本空间不为凸时，算法会陷入“局部”最优。相对于这些传统算法，谱聚类能在任意形状的样本空间上聚类，且收敛于全局最优解。
2 谱聚类算法的基本原理 聚类分析是模式分类中的经典问题。它是通过抽取数据的“潜在”结构，将相似数据组成类或类的层次结构。它不需要先验知识和假设，故它也称作是无监督学习。传统的聚类算法主要是k-means算法和EM算法。这些算法都是建立在凸球形的样本空间上。当样本空间不为凸时，算法会陷入“局部”最优。 为了能在任意形状的样本空间上聚类，且收敛于全局最优解，研究学者最近开始利用谱方法来聚类。谱方法聚类是由数据点间相似关系建立矩阵，获取该矩阵的前n个特征向量，并且用它们来聚类不同的数据点。谱聚类方法建立在图论中的谱图理论上。最初，它是用于负载均衡和并行计算，VLSI等方面，如Hagen和Kahng[3]将基于ratio-cut的目标函数图划分算法用于VLSI设计中。最近，学者们也开始将谱聚类方法用于机器学习中。Shi和Malik[4]在2000年根据谱图理论建立了2-way划分的Normalized-Cut(Ncut)的目标函数，设计了用于图像分割的算法，由此发展出一系列算法：k-way划分的Ncut算法(Ng和WeissL[5])；Normalized Cut与随机游动关系的算法(Meila和shi[6])；基于二分图的算法(Zha[7]和Dhillon[8] )等。并且，谱聚类方法的应用也开始从图像分割领域扩展到文本挖掘(DhillonE[8])和生物信息挖掘领域(Chris Ding[9])等领域中。
2．1 图划分问题与聚类 聚类算法的一般原则是类内样本间的相似度大，类间样本间的相似度小。假定将每个数据样本看作图中的顶点y，根据样本问的相似度将顶点间的边赋权重值，就得到一个基于样本相似度的无向加权图：G(V，E)。那么在图G中，我们可将聚类问题转变为如何在图G上的图划分问题。划分的原则是：子图内的连权重最大化和各子图间的边权重最小化。 针对这个问题，Shi和MalikEz提出了基于将图划分为两个子图的2-way目标函数Ncut：
其中cut(A，B)是子图A，B间的边，又叫“边切集”。 从式(1)，我们可以看出改进后目标函数不仅满足类间样本间的相似度小，也满足类内样本间的相似度大。
如果考虑同时划分几个子图的话，则基于k-way的Normalized-cut目标函数为：
除了Ncut目标函数外，还有Hagen和Kahng提出的Ratio-Cut和Ding等提出的Min-Max Cut。三个目标函数中，Ratio-Cut只考虑类间相似性最小，且最易产生“倾斜”的划分。而Min-Max Cut与Ncut一样满足类内样本问的相似度大而类间样本的相似度小的原则，与Ncut具有相似的行为。
2．2 谱图理论 谱图理论是一个具有很长历史的理论。它是利用矩阵理论和线性代数理论来研究图的邻接矩阵，根据矩阵的谱来确定图的某些性质。谱图理论分析的基础是图的Laplacian矩阵，它是Fiedler[11]1973提出来的。 假设一无向加权图G= ，其表示形式为一对称矩阵：W=[Wij]n*n，其中Wij表示连接顶点i与j的权值。那么该图的Laplacian矩阵表示为： L=D-W 其中，D为对角阵。Laplacian矩阵是对称半正定矩阵，因此它的所有特征值是实数且是非负的：
如果G是c个连接部件，那么L有c个等于0的特征向量。如果G是连通的，第二个最小特征值不为0，则它是G的连接代数值(Fiedter-value)。其对应的特征向量为Fiedler向量。 当我们考虑2-way划分时，令P是A的划分指示向量：
那么：
考虑到约束，则 将X放松(松弛)到连续域[-1,1]，获得minNCut的问题就是： 根据瑞利商原理，式(10)的优化问题等于下列等式的第二最小特征值的求解问题：
对应于第二最小特征值对应的特征向量X2则包含了图的划分信息。人们可以根据启发式规则在X2寻找划分点i，使得值大于等于X2i的划为一类，而小于X2i的划为一类。同理，我们可以推理得到k-way Ncut目标函数式(6)的最优解在式(11)的是个最小特征值对应的特征向量所组成的子空间上。 2．3 算法描述 谱聚类算法由三个部分组成： 1．建立表示样本集的矩阵S。 2．计算S的k个特征值与特征向量 a．2-way：将原始样本数据映射到一维空间(k=1)； b．k-way；将原始样本数据映射到由k个正交向量组成的k维空间S’。 3．将k维子空间S’ 的行作为样本的新的数据表示，且基于这种新的表示，将样本进行聚类。 a．2-way：在一维空间上根据目标函数最优原则划分，并且在划分好的两个子图上迭代划分； b．k-way：利用传统的k-means或其它传统聚类算法在是维空间上进行聚类。 上述的描述是算法的一个框架，在具体的算法中，不同的算法在数据集矩阵S的表示上存在着不同，如：根据2-wayNcut的目标函数，S=D-1/2LD-1/2；根据随机游动关系，S=D-1 W 等。
3 谱聚类算法在图像分割中的应用 谱聚类方法最初是在图像分割中应用 shi和Malik[4]将像素作为顶点，根据像素的亮度和空间位置确定连接像素点问边的权值，利用2-wayNcut的谱聚类方法迭代地进行图的分割。该方法获得了满意的效果。 M.Gu,H.Zha等人[10]分析了在不规则图上进行k-way图划分的谱松散模型，并且根据该模型，提出了k-way Ncut与k-way Min-Max cut不同目标函数设置的下限值，同时分析了对应于最优解的特征空间或单个特征向量的代数结构，为将谱图理论运用到k-way图划分问题中，提供了理论基础。 Meila和shi[6]将相似性解释为Markov链中的随机游动，分析了这种随机游动的概率转移矩阵P=D-1W 的特征向量(其中：W是相似度矩阵)，并且根据随机游动对Ncut进行了概率的解释，提出了基于随机游动的新的算法。同时，在这个解释框架下提出了多个特征相似矩阵组合下的谱聚类方法，在图像分割中也取得了很好的效果。 Zha[7]等人和Dhillon[7]研究了基于二分图G= 上的谱聚类。聚类目标是使得在最小化二分图上的不匹配顶点对间的边权重和最小，故目标函数可以用变形的Ncut表示；
将二分图的邻接矩阵W转换对称矩阵 ： 然后再根据谱图理论对二分图上划分的目标函数式(12)进行分析(与2的分析相似)。Zha等人与Dhilion发现最小化目标函数式(12)可以等同于与二分图相关联的边权重矩阵的奇异值分解。Dhillonc将其运用到文档聚类中，对CMU的Newsgroup20做了实验，取得了很好的效果。基于二分图模型，该算法同样也可以用于市场分析中交易-商品的分析，生物信息挖掘中的Gene expression profiles。 Zha等人分析了核k-means的方法，发现最小化核k-means的目标函数等同于一个由数据向量组成的Gram矩阵的迹最大化问题。同时，迹最大化问题的松散解可以通过Gram矩阵的部分特征分解获得。首次用谱松散的方法获得核k-means的目标函数的全局最优解。Dhillon[11]在此基础上，又研究了加权核k-means的目标函数，将其与Ncut目标函数建立联系，提出了一个可以单调递减Ncut值的新颖的加权核k-means算法。 Ncut是一个可行的聚类目标函数。它的求解是一个NP难问题。传统的方法是宽松的谱松散方法。Xing与Jordan则分析了对Ncut的半正定规划(SDP)模型。根据该模型，对Ncut提出了一个比谱松散更紧的下限。同时指出Ncut本身不能刻画最优的聚类，但它可以通过不同的松散方法获得合理的聚类。 图一所示为一种基于PCA加权的Ncut图像分割结果：