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