Image Segmentation

在stanford中的cs131課程提到的Graph-based segmentation，剛好介紹到這篇論文，就來研讀一下。 論文網址：Felzenszwalb, Pedro F., and Daniel P. Huttenlocher. “Efficient graph-based image segmentation.” International journal of computer vision 59.2 (2004): 167-181. 本篇論文是基於圖的(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 ...