I m p l e m e n t

　

1. Segmentation

分出區塊的方法，主要是由RGB值判斷，方法如下：

1.      對每一像素判斷其右、右下、下、左下四個方向的像素，若兩像素RGB值差異不超過設定的範圍，

        則設定該方向的像素與此像素為同一區塊；否則，設定該方向的像素為另一個新區塊。

2.      再來，判斷其左、左上、上、右上四個方向的像素，若與其中一個方向的像素，二個像素的RGB值差異不超過我們設定的範圍，

        則將此像素所屬區塊與該方向的像素所屬區塊合併為同一區塊。之所以要進行這一個動作，是因為在某些情況下，

        同一區塊可能被分做二個區塊甚至更多，所以才要進行合併的動作，下圖為簡單的範例：

　

原圖

錯誤(未進行合併動作)

正確

　

 

3.        由於單純只由RGB值作判斷的話，很容易分割出過多過小的區塊，因此做完上述動作後，會再進行過小區塊的合併。

          首先，程式必須計算所有區塊的像素數量，再對每一區塊計算與其相鄰的區塊中，差異度最小的區塊。

4.        設定區塊內像素若少於一定值，則認定此區塊過小，必須與其他區塊合併。

          將過小區塊與步驟3中找到的最相似的區塊合併為一個大區塊。此時若發現二個相鄰區塊會合併到對方的區塊，則設定區塊數較小的區塊合併到對方的區塊。

5.           重複步驟3與步驟4，直到所有區塊夠大為止。

 

使用者輸入部分：

接下來由使用者簡單畫幾條線，標示該影像中何者為前景？何者為背景？

其方法如下：

1.  首先使用者必須先選擇按鈕F代表接下來畫的是前景，或者選擇按鈕B代表背景，選擇按鈕C則可以清除使用者標示的部份。

2.  程式讀入使用者選擇的按鈕後，使用者開始在影像上畫線標示前、背景位置。程式讀入所有使用者標示的位置，記錄在一個矩陣中。

3.  當使用者按下按鈕S，表示使用者已選擇完畢。此時，程式根據剛才存的矩陣判斷區塊為前景或背景；

    若一個區塊內同時有二或多個以上的像素被標示為不同的種類，或者沒有任何像素被標示，則不設定此區塊為前景或背景。

　

　

2. Cutout

在判斷未標示部份是前景或背景之前，我們必須對每個區塊作衡量，我們希望所有前景區塊為一群，

所有背景區塊合為一群，所以我們加上了 鍊結 的概念。鍊結的能量越大，表示兩區塊同為前景 or 背景的可能性越大，

當所有的標示完成，我們用 Maxflow 切斷鍊結最弱的部分，和標示為前景相連的部分即視為前景，反之亦然。

模型如下圖所示：

　

 

圖解：

S 為前景起點

T 為背景起點

水平面上每點代表一個區塊，

切斷點為水平面上較細(能量較小)的鍊結。

　
 

由於目標是把區塊分成前景 (1 ) 或背景 (0) ，故可視為一個 “ binary labeling “ problem。

參考 paper 採用的 Gibbs energy E(X) [Geman and Geman. 1984 ]:

其中 V 為圖片上的每個區塊， ε 為兩區塊間的鍊結。

 

n           其中E1是 likelihood energy ，可視為 跟標示前/背景的相似度。

在上頁的模型中，E1 即為水平面連結到上下兩端點的鍊結能量。因為我們希望越相近的區塊鍊結越大，

所以當某區塊被使用者標示為前景，我們就設該區塊到前景（S）的能量為 Max，到背景（T）的能量為0。

反之，當某區塊標示為背景，則和前景（S）的能量為 0 ，和背景（T）的能量為 Max。而未標示的區塊，則必須判斷是前景 or 背景的可能性。

Step 1: 找K-mean

我們先把標示起來的前背景區塊各當成一個 RGB 樣本，在 RGB 三度空間裡，任意取 k 個標示點{x, y, z}，

將每個樣本分類到最接近的標示點。取每個標示點的平均 RGB 值。若標示點{x, y, z}和平均值{R, G , B}不同，

把標示點移至平均點上，重新取平均值，一直重複上述步驟，直到所有標示點不再劇烈更動為止。

Step 2: 求最小距離

當我們遇到一個未標示的區塊，就用區塊的平均 RGB 值，到前背景樣本裡去找最接近的標示點，

計算平均值和最接近標示點的距離。在前景樣本的距離，命之為 dfn  ，到背景樣本裡求得的距離命之為  dBn 。

Step 3: 定義能量

可想而知，若區塊的平均 RGB 值較接近前景，則 dfn 較小，但我們希望越接近前景能量越大，

於是我們將對前景的能量設為   對背景的能量則設為 。

n           而 E2 是 piror ，可視為 與相鄰區塊的相異度，定義如  ：  ，

我們取兩相鄰區塊邊界上的 RGB 差異當作 Cij ，差異越大，Cij 值越大。但我們希望兩區塊差異較小時鍊結能量較大，所以我們設兩區塊的能量為 。

　

3. Maxflow

　

While ( there exists a path p from S to T )

        Do ( flow (p) <- min{ flow (u, v) | (u, v) is in p} )

                For( each edge ( u, v) in p ) {

                        Do F[u, v] <- F[u, v]  -  flow(p)

F[v, u] <- F[v, u]  +  flow(p)

}

 

當所有鍊結能量都標示完成，我們用 Maxflow尋找能量較少的鍊結。

我們可將所有鍊結想像成一片由 S 出發，T結束的水管網，而能量就是水管的截面積大小（亦可視為單位時間可通過的流量）。

 

一開始，由S先任找一條通路到終點，通路 p 的流量應該會被通路上的最小截面積min{ flow (u, v) | (u, v) is in p} 所限制，

我們稱通路 p 的流量為 flow (p) ，此時將所有通路上的 S -> T 方向流量減去 flow (p)  ，此時通路上必有一條鍊結能量被減為 0 ，該處便是鍊結最弱處。

但因為我們的目的是求出 S，T各自有哪些 node ，所以我們必須把水管看成是雙向流通的。

當我們減掉 S->T 方向的流量，表示 T->S 方向也可以有相同大小的流量，所以除了 F[u, v] - flow (p) ，還要把 F[v , u] 加上flow (p) 。

重複此動作，我們就可以做到將所有區塊分為 S T 兩群，最後將和 S 相連的輸出為前景，和 T 相連的輸出為背景即可完成。