圖像分割——譜聚類

1、 Graph Cut Graph Cut Graph Cut Spectral Clustering李翔2014/4/4圖像分割譜聚類譜聚類Spectral Clustering 譜聚類算法： 1、建立在圖論中的譜圖理論基礎(chǔ)上的一種分類算法 2、本質(zhì)是將聚類問題轉(zhuǎn)化為圖的最優(yōu)劃分問題 3、是一種點對聚類算法 由數(shù)據(jù)點間相似關(guān)系建立矩陣，獲取該矩陣的前n個特征向量，并且用它們來聚類不同的數(shù)據(jù)點。譜聚類步驟1）根據(jù)數(shù)據(jù)構(gòu)造一個）根據(jù)數(shù)據(jù)構(gòu)造一個 Graph ，并用，并用W表示這個表示這個Graph的鄰接矩陣的鄰接矩陣 Graph 的每一個節(jié)點對應(yīng)一個數(shù)據(jù)點，將相似的點連接起來，并且邊的權(quán)重用于表

2、示數(shù)據(jù)之間的相似度。把這個 Graph 用鄰接矩陣的形式表示出來，記為 W 。2) 構(gòu)造出構(gòu)造出Laplacian矩陣矩陣L 把每一列元素加起來得到N 個數(shù)，把它們放在對角線上（其他地方都是零），組成 一個N*N的矩陣，記為D 。并令L = D - W 。3) 求出求出L的前的前k個特征值以及對應(yīng)的特征向量個特征值以及對應(yīng)的特征向量 在本文中，除非特殊說明，否則“前k個”指按照特征值的大小從小到大的順序4) 將這將這K個特征向量組成個特征向量組成N*K的矩陣進(jìn)行聚類的矩陣進(jìn)行聚類 把這k個特征（列）向量排列在一起組成一個N*k的矩陣，將其中每一行看作k維空間 中的一個向量，并使用 相應(yīng)算法進(jìn)行

3、聚類。聚類的結(jié)果中每一行所屬的類別就 是原來 Graph 中的節(jié)點亦即最初的N個數(shù)據(jù)點分別所屬的類別。譜聚類相似度1、圖的最短距離圖的最短距離 任意兩點之間的最短距離。我們用兩點之間的最短距離表示相似度 2、邊聚類系數(shù)、邊聚類系數(shù)兩點共存三角形的個數(shù) / 兩點度的最小值3、邊稠密度系數(shù)、邊稠密度系數(shù)： 與兩點相鄰的邊數(shù) / (1/2)n(n-1)4、 Betweenness: 圖中任意兩點的最短路徑經(jīng)過這條邊的數(shù)5、圖像中加入位置信息和亮度信息、圖像中加入位置信息和亮度信息譜聚類聚類原理相關(guān)定義：1、用G = (V,E)表示無向圖，其中V和E分別為其頂點集和邊集；2、某條邊屬于某個子圖是指該邊

4、的兩個頂點都包含在子圖中3、假設(shè)某邊的兩個端點為 i, j，則該邊的權(quán)重為wi,j,可知對于譜聚類中wi,j=wj,i,且 wi,i=04、對于圖的某種劃分方法Cut：所有兩端點不在同一子圖中的邊的權(quán)重之和， 它可以被看成該劃分方案的損失函數(shù)，希望這種損失越小越好,即在圖像分割的過程中找到這個函數(shù)對應(yīng)的最小值，即找到了最好的分割方式 以二分無向圖為例 譜聚類聚類原理(Laplacian) Laplacian矩陣矩陣 假設(shè)無向圖G被劃分為G1和G2兩個子圖，該圖的定點數(shù)為：n = |V|,用q表示n維指示向量，每個分量定義如下可知所以得到Laplacian矩陣特點:1、L為半正定矩陣，所有的特征

5、值都大于02、L矩陣有唯一的0特征值，其對應(yīng)的特征向量為1,1,1T譜聚類聚類原理(分割方法)1、Minimum Cut 定義 ，此時的Cut函數(shù)變?yōu)?從這個問題的形式可以聯(lián)想到Rayleigh quotient(瑞利商) R(L,q)的最大值和最小值分別在矩陣L的最大特征值和最小特征值處取得，且q的值取 在相對應(yīng)的特征向量 所以原式可化為求解下下特征系統(tǒng)的特征值和特征向量： 顯而易見L的最小特征值是0，對應(yīng)的特征向量為1,11T，于是最優(yōu)解應(yīng)該是在第 二小的特征向量處開始取 4)2, 1(LqqGGCutT譜聚類聚類原理(分割方法)2、Normalized Cut 實際當(dāng)中，劃分圖時除了要考

6、慮最小化Cut外,還要考慮劃分的平衡性，為緩解出現(xiàn)類似一個子圖包含非常多端點而另一個只包含很少端點的情況,還要考慮到子圖內(nèi)部的相似性。 公式可變?yōu)槿缦滦问剑核栽跍p少了子圖之間的Cut值的同時也增加了子圖內(nèi)部的相似度。保證了分割的平衡性 ), 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表示為 那問題就變成求解下特征系統(tǒng)的特征值和特征向量： 譜聚類求特征向量及聚類3 、求出、求出L的前的前k個特征值以及對應(yīng)的特征向量個特征值以及對應(yīng)的特征向量 a2-way：將原始樣本數(shù)據(jù)映射到一維空間(k=1); 求出最小的兩個特征值，由于最小的特征值為0，所以實際只剩下一個特征值和一 對應(yīng)的n維特征向量，將這個特征向量進(jìn)行分類，分為兩類。再到每一個子圖中迭 代的進(jìn)行2-way分類。 b. k-way；將原始樣本數(shù)據(jù)映射到由k個正交向量組成的k維空間S。 求出最小的k個特征值，用k-means等