基于圖的快速圖像分割算法

Efficientgraph-basedimagesegmentationG=(V,E)，每個節(jié)點對應(yīng)圖像中一個像素點，E是連接相鄰節(jié)點的邊，每個邊有對應(yīng)有一個權(quán)重，這個權(quán)重與像素點的特性相關(guān)。最后，我們將提出一類基于圖的查找最小割的分割方法。這個最小割準(zhǔn)那么是最小化那些被分開像素之間的相似度?！?8】原文中叫Component,實質(zhì)上是一個MST,單獨的一個像素點也可以看成一個區(qū)域。預(yù)備知識：圖是由頂點集〔vertices〕和邊集〔edges〕組成，表示為，頂點，在本文中即為單個的像素點，連接一對頂點的邊具有權(quán)重，本文中的意義為頂點之間的不相似度，所用的是無向圖。樹：特殊的圖，圖中任意兩個頂點，都有路徑相連接，但是沒有回路。如上圖中加粗的邊所連接而成的圖。如果看成一團亂連的珠子，只保存樹中的珠子和連線，那么隨便選個珠子，都能把這棵樹中所有的珠子都提起來。如果，i和h這條邊也保存下來，那么h,I,c,f,g就構(gòu)成了一個回路。最小生成樹〔MST,minimumspanningtree〕：特殊的樹，給定需要連接的頂點，選擇邊權(quán)之和最小的樹。上圖即是一棵MST。本文中，初始化時每一個像素點都是一個頂點，然后逐漸合并得到一個區(qū)域，確切地說是連接這個區(qū)域中的像素點的一個MST。如圖，棕色圓圈為頂點，線段為邊，合并棕色頂點所生成的MST，對應(yīng)的就是一個分割區(qū)域。分割后的結(jié)果其實就是森林。邊的權(quán)值：對于孤立的兩個像素點，所不同的是顏色，自然就用顏色的距離來衡量兩點的相似性，本文中是使用RGB的距離，即3圖割3.1我們定義D，衡量分割區(qū)域之間是否有明顯邊界。D是通過測量沿著兩個區(qū)域邊界元素的不相似度比照測量兩個區(qū)域內(nèi)部各自內(nèi)部元素之間不相似度。我們用C表示一個局部的內(nèi)在差異，是該區(qū)域最小生成樹上的最大權(quán)值。我們定義兩個區(qū)域間的不同是兩個區(qū)域連接邊的最小權(quán)值，如果C1，C2之間不想連，那么Dif(C1,C2)=無窮大，使用下面的閾值函數(shù)來控制兩個區(qū)域之間的差異性必須大于最小內(nèi)在差異，我們定義如下函數(shù)：其中MInt是：閾值函數(shù)控制著兩個區(qū)域之間的差異性必須大于他們內(nèi)在差異性，以便它們之間有明顯的邊界〔D為true〕。對于小的區(qū)域，Int(C)是對局部數(shù)據(jù)的特性的一個好的估計。在一些極端情況下，如果|C|=1，Int(C)=0。因此我們的閾值函數(shù)為這里的|C|是C的大小，K是某個特定常量參數(shù)。對于小的區(qū)域我們需要明顯的邊界。實際上k設(shè)置為一系列值.說明：當(dāng)二者都是孤立的像素值時，，所有像素都是"零容忍"只有像素值完全一樣才能合并，自然會導(dǎo)致過分割。所以剛開始的時候，應(yīng)該給每個像素點設(shè)定一個可以容忍的范圍，當(dāng)生長到一定程度時，就應(yīng)該去掉該初始容忍值的作用。原文條件如下增加項:其中為區(qū)域所包含的像素點的個數(shù)，如此，隨著區(qū)域逐漸擴大，這一項的作用就越來越小，最后幾乎可以忽略不計。那么就是一個可以控制所形成的的區(qū)域的大小，如果，那么，幾乎每個像素都成為了一個獨立的區(qū)域，如果，顯然整張圖片都會聚成一塊。所以，越大，分割后的圖片也就越大4算法和它的特性定義1分得太細(xì)。定義2分得太粗特性1相近的算法【6】算法1分割算法輸入：圖，有n個頂點和M條邊。輸出：對V的分割為首先將邊E按照權(quán)重大小由小到大排列為；開始一個分割，每一個頂點是它自己的區(qū)域；重復(fù)步驟3，q=1,....,m按照如下方法，通過構(gòu)建：按順序，和表示第q次相連的兩個頂點，比方，。如果和在的不相交的兩個區(qū)域中，并且是較小的相對于這些區(qū)域的內(nèi)在差異性，那么合并這兩個區(qū)域除非什么也不做。包含成為的一局部，讓包含成為一局部〔letCiq?1bethecomponentofSq?1containingviandCjq?1thecomponentcontainingvj〕。如果，將和合并到中成為。否那么=返回算法分析：具有全局特性，既不會分得太細(xì)也不會分得太粗。該算法是貪心決策引理1上述算法中的步驟3，如果和沒有合并，那么和中至少有一個最后會在分類的區(qū)域中。證明見paper4.1實施問題和運行時間實施主要是包括并查集結(jié)合排序和路徑壓縮〔adisjoint-setforestwithunionbyrankandpathcompression〕，參考《算法導(dǎo)論》〔IntroductiontoAlgorithms.TheMITPress〔麻省理工出版社〕,McGraw-HillBookCompany,1990.〕。運行時間分為兩個局部：1.按照從小到大給權(quán)值排序。整數(shù)權(quán)重使用計數(shù)排序〔countingsort〕可在線性時間內(nèi)完成。說明：并查集+排序+路徑壓縮動態(tài)聯(lián)通性假設(shè)我們輸入了一組整數(shù)對，即上圖中的(4,3)(3,8)等等，每對整數(shù)代表這兩個points/sites是連通的。那么隨著數(shù)據(jù)的不斷輸入，整個圖的連通性也會發(fā)生變化，從上圖中可以很清晰的發(fā)現(xiàn)這一點。同時，對于已經(jīng)處于連通狀態(tài)的points/sites，直接忽略，比方上圖中的(8,9)。在對問題進行建模的時候，我們應(yīng)該盡量想清楚需要解決的問題是什么。因為模型中選擇的數(shù)據(jù)結(jié)構(gòu)和算法顯然會根據(jù)問題的不同而不同，就動態(tài)連通性這個場景而言，我們需要解決的問題可能是：給出兩個節(jié)點，判斷它們是否連通，如果連通，不需要給出具體的路徑給出兩個節(jié)點，判斷它們是否連通，如果連通，需要給出具體的路徑建模思路：最簡單而直觀的假設(shè)是，對于連通的所有節(jié)點，我們可以認(rèn)為它們屬于一個組，因此不連通的節(jié)點必然就屬于不同的組。隨著Pair的輸入，我們需要首先判斷輸入的兩個節(jié)點是否連通。如何判斷呢？按照上面的假設(shè)，我們可以通過判斷它們屬于的組，然后看看這兩個組是否相同，如果相同，那么這兩個節(jié)點連通，反之不連通。為簡單起見，我們將所有的節(jié)點以整數(shù)表示，即對N個節(jié)點使用0到N-1的整數(shù)表示。而在處理輸入的Pair之前，每個節(jié)點必然都是孤立的，即他們分屬于不同的組，可以使用數(shù)組來表示這一層關(guān)系，數(shù)組的index是節(jié)點的整數(shù)表示，而相應(yīng)的值就是該節(jié)點的組號了。說明：計數(shù)排序〔countingsort〕計數(shù)排序假設(shè)n個輸入元素中的每一個都是介于0-k的整數(shù)，此處k為某個整數(shù)。計數(shù)排序顧名思義離不開計數(shù)，我們要計的是輸入元素中相同元素出現(xiàn)的次數(shù)。對每一個輸入元素x，確定小于x的元素的個數(shù)，那樣排序之后，x在最終輸出數(shù)組中的位置就可以確定了。例如：如果有17個元素小于x，那么x就位于第18個輸出的位置上。當(dāng)然有幾個元素相同時，這個方法就略微改良一下，因為不能將它們放在同一個位置上。為了檢查兩個頂點是否屬于同一個區(qū)域，我們對每個頂點使用set-find，為了合并兩個區(qū)域，我們使用set-union。因此每條邊最多有3個disjoint-set操作。如果我們知道每個區(qū)域的大小和Int。那么MInt可以在特定時間計算出來。在一個區(qū)域的MST中，最大權(quán)值的邊引起合并。首先單色〔強度〕圖像的情況。彩色圖是三個單獨的單目圖。對于n個像素的圖像，我們對一個邊連接著的兩個像素，使用基于絕對強度不同邊權(quán)重函數(shù)：求權(quán)重這里I(pi)是像素pi的強度值。在計算邊的權(quán)重前，一般，我們使用高斯濾波器對圖像進行平滑。高斯濾波器的。對于彩色圖像，我們運行程序3次，每次分別在紅、綠、藍這三個顏色通道，然后組合這三組。算法有一個運行參數(shù)，用來計算閾值函數(shù)的的k，這里的k是一個觀察值。全文用兩個k，主要是根據(jù)圖象分辨率和分割的粗細(xì)程度來確定。比方，一個128*128的COIL數(shù)據(jù)庫的圖像我們使用k=50,320*240或者更大的圖像，比方街道場景和棒球選手，k=300圖2是一個街道上的場景，注意到有一個可觀變量從草坪到柵欄〔Notethatthereisconsiderablevariationinthegrassyslopeleadinguptothefence.〕。我們的算法會處理這些變量。第二幅圖顯示了分割效果，每個區(qū)域隨機分配一種顏色。最大的6個區(qū)域是通過下面的算法得到的：柵欄后面的三塊草坪區(qū)域，草坪斜坡，面包車，公路。左下角缺失的公路局部是一個可見的直觀區(qū)域〔aspotduetoanimagingartifact〕。注意到面包車也不是統(tǒng)一的顏色，因為鏡面反射，但是由于有足夠的漫反射，它們被當(dāng)做內(nèi)部變量，并且合并為一個單一的區(qū)域。圖3是兩個棒球選手，在之前的例子中，草地局部是可觀的變量。統(tǒng)一制服的棒球選手也有很多變量，由于衣服的褶皺。算法找到了6個區(qū)域：墻、大都會隊徽、大草坪〔包括球員身下的一局部墻體〕、每個球員的衣服、第二個球員身下的一小塊草坪。大草坪包括了小局部墻體是因為在這個局部相對高的變量，并且在墻體和草地邊緣有長而緩慢的變化。對圖像進行分割的常用方法是基于每個像素映射到特征空間的一個點，然后對相似點進行聚類【3,4,9】。這局部我們將用第4局部描述的基于圖割的算法來考察來找到相似點的類。這里，圖上的每個頂點會有一個對應(yīng)的特征點，連接特征點vi個vj的邊(vi,vj)在特征空間是鄰近的而不是圖像中的相鄰像素點。我們將每個點與特定數(shù)目的最鄰近點相連，或者在特定的區(qū)域d內(nèi)將所有點相連。權(quán)重由特征空間對應(yīng)點的距離決定，實驗顯示，我們映射每個點到特征空間中的點(x,y,r,g,b),我們用點與點之間的歐幾里得距離作為邊的權(quán)值。類內(nèi)差，Int(C)，需要指定一個最小半徑將C中在特征空間中的所有特征點聯(lián)系在一起。通過一個半徑為r的球?qū)⒚恳粋€特征點進行替換。從最小生成樹的定義可以看出，當(dāng)且僅當(dāng)時，這些球體將會連接形成一個單一的空間。不同的區(qū)域，，hasasimpleunderlyingintuition.它指定一個最小的半徑連接C1和C2間最少一對點。我們的分割技術(shù)很大程度上是[4]，不是構(gòu)造一個所有點都是與另一個點相鄰的完全圖，我們要找到每個點都有最小的固定數(shù)量的鄰近點。那么有n個像素點的圖將會有n個邊。我們使用ANN近似最鄰近算法[1]來查找每個點的最近鄰點。給出一個5維的有成百上千個點。作為實例，我們對每個像素使用10個最近鄰點來生成圖的邊。對于先前方法的一個關(guān)鍵不同點是，圖像網(wǎng)格用來定義圖，特征空間中的最近鄰點獲得更多空間非局部特性。在圖割中，圖中所有的鄰域點都是相鄰的。這里，點在圖像中的位置可以使很遠(yuǎn)的，但依然會有大量的最鄰近點〔如果顏色高度相似并且影響圖像像素的是不相似顏色〕。比方，這將導(dǎo)致區(qū)域分割圖像不相連，在網(wǎng)格圖中將不會發(fā)生。圖6顯示了一個從[12]和[18]的合成圖及其分割效果圖。這里k=150,并且沒有進行平滑()。說明：前文是只用了空間位置來構(gòu)件圖的連接關(guān)系，缺點是明顯的，空間不相鄰，色彩完全一樣也白搭，于是中間稍微有斷開都會分成多個局部。于是另一種更為平等的策略是二者一塊考慮，先映射到特征空間，再構(gòu)建圖。此時有連接關(guān)系的就不一定是4/8鄰域了，由于有對邊，因此如果考慮所有邊的連接關(guān)系的話，太恐怖了！原文是對每個像素點找10個歐氏距離最近的點即10最近鄰，構(gòu)建圖，當(dāng)然，另外一種方法不是固定鄰居數(shù)目，而是限定距離范圍。那么類內(nèi)距離的解釋就和直