图像分割——谱聚类

1、 Graph Cut Graph Cut Graph Cut Spectral Clustering李翔2014/4/4图像分割谱聚类谱聚类Spectral Clustering 谱聚类算法： 1、建立在图论中的谱图理论基础上的一种分类算法 2、本质是将聚类问题转化为图的最优划分问题 3、是一种点对聚类算法 由数据点间相似关系建立矩阵，获取该矩阵的前n个特征向量，并且用它们来聚类不同的数据点。谱聚类步骤1）根据数据构造一个）根据数据构造一个 Graph ，并用，并用W表示这个表示这个Graph的邻接矩阵的邻接矩阵 Graph 的每一个节点对应一个数据点，将相似的点连接起来，并且边的权重用于表

2、示数据之间的相似度。把这个 Graph 用邻接矩阵的形式表示出来，记为 W 。2) 构造出构造出Laplacian矩阵矩阵L 把每一列元素加起来得到N 个数，把它们放在对角线上（其他地方都是零），组成 一个N*N的矩阵，记为D 。并令L = D - W 。3) 求出求出L的前的前k个特征值以及对应的特征向量个特征值以及对应的特征向量 在本文中，除非特殊说明，否则“前k个”指按照特征值的大小从小到大的顺序4) 将这将这K个特征向量组成个特征向量组成N*K的矩阵进行聚类的矩阵进行聚类 把这k个特征（列）向量排列在一起组成一个N*k的矩阵，将其中每一行看作k维空间 中的一个向量，并使用 相应算法进行

3、聚类。聚类的结果中每一行所属的类别就 是原来 Graph 中的节点亦即最初的N个数据点分别所属的类别。谱聚类相似度1、图的最短距离图的最短距离 任意两点之间的最短距离。我们用两点之间的最短距离表示相似度 2、边聚类系数、边聚类系数两点共存三角形的个数 / 两点度的最小值3、边稠密度系数、边稠密度系数： 与两点相邻的边数 / (1/2)n(n-1)4、 Betweenness: 图中任意两点的最短路径经过这条边的数5、图像中加入位置信息和亮度信息、图像中加入位置信息和亮度信息谱聚类聚类原理相关定义：1、用G = (V,E)表示无向图，其中V和E分别为其顶点集和边集；2、某条边属于某个子图是指该边

4、的两个顶点都包含在子图中3、假设某边的两个端点为 i, j，则该边的权重为wi,j,可知对于谱聚类中wi,j=wj,i,且 wi,i=04、对于图的某种划分方法Cut：所有两端点不在同一子图中的边的权重之和， 它可以被看成该划分方案的损失函数，希望这种损失越小越好,即在图像分割的过程中找到这个函数对应的最小值，即找到了最好的分割方式 以二分无向图为例 谱聚类聚类原理(Laplacian) Laplacian矩阵矩阵 假设无向图G被划分为G1和G2两个子图，该图的定点数为：n = |V|,用q表示n维指示向量，每个分量定义如下可知所以得到Laplacian矩阵特点:1、L为半正定矩阵，所有的特征

5、值都大于02、L矩阵有唯一的0特征值，其对应的特征向量为1,1,1T谱聚类聚类原理(分割方法)1、Minimum Cut 定义 ，此时的Cut函数变为 从这个问题的形式可以联想到Rayleigh quotient(瑞利商) R(L,q)的最大值和最小值分别在矩阵L的最大特征值和最小特征值处取得，且q的值取 在相对应的特征向量 所以原式可化为求解下下特征系统的特征值和特征向量： 显而易见L的最小特征值是0，对应的特征向量为1,11T，于是最优解应该是在第 二小的特征向量处开始取 4)2, 1(LqqGGCutT谱聚类聚类原理(分割方法)2、Normalized Cut 实际当中，划分图时除了要考

6、虑最小化Cut外,还要考虑划分的平衡性，为缓解出现类似一个子图包含非常多端点而另一个只包含很少端点的情况,还要考虑到子图内部的相似性。 公式可变为如下形式：所以在减少了子图之间的Cut值的同时也增加了子图内部的相似度。保证了分割的平衡性 ), 2()2, 1(), 1()2, 1()2, 1(GGCutGGCutGGCutGGCutGGNcut), 2()2, 2(), 1() 1, 1(2)2, 1(GGCutGGCutGGCutGGCutGGNcut谱聚类聚类原理(分割方法)2、Normalized Cut 定义d1 = Cut（G1,G）,d2 = Cut(G2,G) 所以Ncut(G1,G2) = 其中 用泛化的Rayleigh quotient表示为 那问题就变成求解下特征系统的特征值和特征向量： 谱聚类求特征向量及聚类3 、求出、求出L的前的前k个特征值以及对应的特征向量个特征值以及对应的特征向量 a2-way：将原始样本数据映射到一维空间(k=1); 求出最小的两个特征值，由于最小的特征值为0，所以实际只剩下一个特征值和一 对应的n维特征向量，将这个特征向量进行分类，分为两类。再到每一个子图中迭 代的进行2-way分类。 b. k-way；将原始样本数据映射到由k个正交向量组成的k维空间S。 求出最小的k个特征值，用k-means等