輸入圖片

不同參數(shù)下的分割結(jié)果

原圖片

產(chǎn)生superpixel的方法

1. How to segment an image into regions???? 怎樣把一張圖片分割成不同的區(qū)域？

2. How to define a predicate that determines a good segmentation???? 如何判定一個(gè)好的分割？

3. How to create an efficient algorithm based on the predicate???? 怎樣根據(jù)這個(gè)判定創(chuàng)造一個(gè)好的算法？

4. How do you address semantic areas with high variability in intensity?怎樣處理亮度變化較大的分割區(qū)域？

5. How do you capture non-local properties in an image?如何獲取圖像的非局部特征？

第一個(gè)問題:怎樣把一張圖片分割為不同區(qū)域？

一個(gè)無(wú)向圖，由邊，節(jié)點(diǎn)，權(quán)重組成

在這篇論文中，兩點(diǎn)之間邊的權(quán)重指的是兩個(gè)頂點(diǎn)的不相似性，使用兩個(gè)頂點(diǎn)RGB之間的平方差來(lái)得到。

樹：特殊的圖，圖中任意兩個(gè)頂點(diǎn)，都有路徑相連接，但是沒有回路。如上圖中加粗的邊所連接而成的圖。如果，i和h這條邊也保留下來(lái)，那么h,I,c,f,g就構(gòu)成了一個(gè)回路，就不是樹了。

最小生成樹（MST,minimum spanning tree）：特殊的樹，給定需要連接的頂點(diǎn)，選擇邊權(quán)之和最小的樹。上圖即是一棵MST。

第一個(gè)問題解答：本文中，初始化時(shí)每一個(gè)像素點(diǎn)都是一個(gè)頂點(diǎn)，然后逐漸合并得到一個(gè)區(qū)域，確切地說(shuō)是連接這個(gè)區(qū)域中的像素點(diǎn)的一個(gè)MST。如圖，棕色圓圈為頂點(diǎn)，線段為邊，合并棕色頂點(diǎn)所生成的MST，對(duì)應(yīng)的就是一個(gè)分割區(qū)域。分割后的結(jié)果其實(shí)就是一棵一棵的書。

最小生成樹示意圖

第二個(gè)問題：如何判定一個(gè)好的分割？

最左邊原始圖中，左部分是斜坡區(qū)，右側(cè)平緩區(qū)，嵌在平緩區(qū)里的是高頻區(qū)

一個(gè)好的分割就是能夠區(qū)分好這三種區(qū)域的分割。

先看一下，我們?cè)嫉姆指钤斐缮蠄D中間效果的原因。

如何確定兩個(gè)區(qū)域是否可以合并

判定紅色區(qū)域和綠色區(qū)域是否合并，通過(guò)紫色邊<不相似性>來(lái)判斷，設(shè)置一個(gè)唯一閾值，如果小于這個(gè)閾值，就合并。對(duì)于高頻區(qū)，我們可以稱為二維碼區(qū)，想要把這個(gè)區(qū)域分割成一個(gè)區(qū)域，這個(gè)閾值就得設(shè)置成很大的數(shù)，那么對(duì)于斜坡和平緩區(qū)，所有的值都會(huì)小于這個(gè)閾值，導(dǎo)致，這三個(gè)區(qū)域并到一起，失去分割效果。相反，如果，我們的閾值設(shè)置的很小，就會(huì)導(dǎo)致二維碼區(qū)域保留，一小塊一小塊的。

造成貼圖的中間的那個(gè)不正確分割效果圖的原因是，我們?cè)O(shè)置的閾值適中，把二維碼圖并到了平緩區(qū)中。

第三、四個(gè)問題：怎樣根據(jù)這個(gè)判定創(chuàng)造一個(gè)好的算法？怎樣處理亮度變化較大的分割區(qū)域？

我們應(yīng)該對(duì)于不同的區(qū)域設(shè)置不同的閾值。根據(jù)這個(gè)想法，作者提出了自適應(yīng)的閾值調(diào)整方法。這樣，對(duì)于高頻區(qū)，我們的閾值自動(dòng)變大，平緩區(qū)閾值自動(dòng)小，這樣就可以實(shí)現(xiàn)上面三個(gè)高頻，斜坡，平緩區(qū)的分割了。

C1和C2表示兩顆MST

Mint表示同一顆樹下權(quán)重最大的邊（最不相似的兩個(gè)點(diǎn)）

Dif 表示鏈接兩個(gè)樹的最小權(quán)重邊

如果Dif>=Min（Mint(c1),mint(c2)），兩個(gè)樹之間的距離>min(這兩個(gè)樹中最大的那兩個(gè)權(quán)重邊);? 表示他們不是同一個(gè)類，不能合到一起。Min（Mint(c1),mint(c2)表示c1和c2能夠共同容忍的最大差異。

對(duì)于初始點(diǎn)，圖片的每一個(gè)像素都是一個(gè)獨(dú)立的MST,所以必須是兩個(gè)像素值完全一樣才能滿足上面條件，所以我們，要設(shè)置一個(gè)初始閾值，這個(gè)閾值要有一個(gè)性質(zhì)，隨著我們樹的變大（C變大），這個(gè)初始閾值tao(C)逐漸趨向于0,使得我們的自適應(yīng)閾值起作用。k控制合并后的區(qū)域的大小。k=0,表示，所有像素值完全相同才可以合并。k非常大，不同像素值之間可以有差異。

左邊是k小，右邊k大

初始閾值,c表示樹節(jié)點(diǎn)的個(gè)數(shù)

算法步驟：首先，下圖中的每一個(gè)圓點(diǎn)都是代表一個(gè)像素，

1. 我們先對(duì)每一個(gè)像素計(jì)算與他相鄰的八個(gè)位置的不相似性，也就是他們之間權(quán)重。

2.按照從小到大的順序排列，選出最小的邊，把他們合并到一個(gè)分割里面

3.此時(shí)，就要參照，兩顆樹如何合并了，如果類間的差異<類內(nèi)共同容忍的最大差異，那么合并，更新新區(qū)域，一直重復(fù)這個(gè)操作

4.更新該類的不相似度閾值，C變大了。

5.結(jié)束條件，找不到一條邊能夠滿足條件，結(jié)束。

算法步驟

如何獲取圖像的非局部特征？

使用了位置，顏色作為每個(gè)像素的描述

計(jì)算兩個(gè)pixel的歐式距離，選取10個(gè)最近鄰，保證時(shí)間復(fù)雜度。這個(gè)是用來(lái)解決分割區(qū)中間稍微有斷開的情況，如果只考慮顏色方面的信息，會(huì)導(dǎo)致分割區(qū)域被斷開，如果考慮他們的位置信息，可以稍微避免這個(gè)問題。

對(duì)于彩色圖片，上文是將R,G,B作為距離，整張圖片只進(jìn)行一次分割，原文說(shuō)對(duì)每一個(gè)通道都進(jìn)行一次分割，最后對(duì)結(jié)果取交集，也就是說(shuō)圖片中的兩個(gè)點(diǎn)要?jiǎng)澐值酵粋€(gè)區(qū)域，則在R,G,B三個(gè)通道的劃分結(jié)果中，始終在同一個(gè)區(qū)域作為最終分割結(jié)果。