在stanford中的cs131課程提到的Graph-based segmentation，剛好介紹到這篇論文，就來研讀一下。
本篇論文是基於圖的(Graph-Based)影像分割演算法，提出一個有效率的影像分割方式，並且影像分群的的結果是有意義的。
主要動機
過往的某些方法並沒有考慮到漸變的影像，使得分割結果不符合預期
問題描述
影像 $G$ 是由像素集合V與無向邊 $E$ 連接一組點對$(v_i, v_j)$，並且具有權重 $w(v_i, v_j)$，權重是由兩像素點之間的差異來產生
S是在影像G分割出來的一個區塊，並以 $G’=(V,E’)$ 表示， 其中$ E’\in E$
斷定為分割公式定義
斷定兩區域$C_1,C2$是否存在邊界分割，是基於量測兩個區域$C_1,C2$之間的相異性，以及評估區塊內部各自元素的相異性程度
$Dif(C_1, C_2)是兩區域之間的差異，差異是指將組件C_1中的節點v_i連接到C_2中的節點v_j的最小權重邊$
$Int(C)$是計算同一區域內兩兩像素點之間的最大權重
$MInt(C_1, C_2)$是個別區域內的內部差異
$\tau(C)是一個閾值，由設定參數k來控制最後產生的群集大小$
演算法流程
- 計算每個像素8相連或4相連的不相似度
- 將edge E按照不相似度non-decreasing排序edge權重得到$o_1,o_2,…,o_m$
- 開始分割動作，初始分割區域為$S^0$, 其中每個像素點$v_i$是獨立的一個區域
- 重複步驟並定義$q=1,…m$
- $S^q$的初始區域是由$S^{q-1}$組成, 定義$v_i, v_j$ 是一組前q小的edge權重對應的點對$o_q = (v_i, v_j) $
檢查點對合成條件是否符合, 合成條件參考$D(C1, C2)$, 符合則合併, 否則維持分割結果S並繼續執行到結束
測試結果
使用的測試資料是COIL database，
對不同的影像大小使用不同的參數k
結果圖：
除了上述的流程與演算法外，由於目前提到的演算方法只考慮到空間位置，及鄰近像素來建構圖的連接關係，假使色彩相同但距離有些許差異，也不會合併成相同區域。為了考慮更大範圍的鄰近空間，又不能考慮到過大的範圍，否則搜索範圍所消耗的時間會過大，論文作者使用一個歐式距離的範圍來取代前面提到的四相連\八相連，擴大搜索範圍。
{: width="881" height="342")
經過擴大鄰近範圍的ANN，降低的分割結果的零散程度。