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

《基于圖的快速圖像分割算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、.Efficientgraph-basedimagesegmentation2.相關(guān)工作G=(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)。最后，我們將提出一類基于圖的查找最小割的分割方法。這個(gè)最小割準(zhǔn)則是最小化那些被分開(kāi)像素之間的相似度?！?8】原文中叫Component,實(shí)質(zhì)上是一個(gè)MST,單獨(dú)的一個(gè)像素點(diǎn)也可以看成一個(gè)區(qū)域。預(yù)備知識(shí)：圖是由頂點(diǎn)集（vertices）和邊集（edges）組成，表示為，頂點(diǎn)，在本文中即為單個(gè)的像素點(diǎn)

2、，連接一對(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)都

3、是一個(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ū)域邊界元素的不相似度對(duì)比測(cè)量?jī)蓚€(gè)區(qū)域內(nèi)部各自內(nèi)部元素之間不相似度。我們用C表示一個(gè)部分的內(nèi)在差異，是該區(qū)域最小生成

4、樹(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ì)。在一些極端情況下，如果

5、C

6、=1，Int(C)=0。因此我們的閾值函數(shù)為這里的

7、C

8、是C的大小，K是某個(gè)特定常量參數(shù)。對(duì)

9、于小的區(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ū)域，如果，顯然整張圖

10、片都會(huì)聚成一塊。所以，越大，分割后的圖片也就越大4算法和它的特性定義1分得太細(xì)。定義2分得太粗特性1相近的算法【6】算法1分割算法輸入：圖，有n個(gè)頂點(diǎn)和M條邊。輸出：對(duì)V的分割為0.首先將邊E按照權(quán)重大小由小到大排列為；1.開(kāi)始一個(gè)分割，每一個(gè)頂點(diǎn)是它自己的區(qū)域；2.重復(fù)步驟3，q=1,....,m3.按照如下方法，通過(guò)構(gòu)建：按順序，和表示第q次相連的兩個(gè)頂點(diǎn)，比如，。如果和在的不相交的兩個(gè)區(qū)域中，并且是較小的相對(duì)于這些區(qū)域的內(nèi)在差異性，那么合并這兩個(gè)區(qū)域除非什么也不做。包含成為的一部分，讓包含成為一

11、部分（letCiq?1bethecomponentofSq?1containingviandCjq?1thecomponentcontainingvj）。如果，將和合并到中成為。否則=4.返回算法分析：具有全局特性，既不會(huì)分得太細(xì)也不會(huì)分得太粗。該算法是貪心決策引理1上述算法中的步驟3，如果和沒(méi)有合并，那么和中至少有一個(gè)最后會(huì)在分類的區(qū)域中。證明見(jiàn)paper4.1實(shí)施問(wèn)題和運(yùn)行時(shí)間...實(shí)施主要是包括并查集結(jié)合排序和路徑壓縮（adisjoint-setforestwithunionbyrankandp

12、athcompression），參考《算法導(dǎo)論》（IntroductiontoAlgorithms.TheMITPress（麻省理工出版社）,McGraw-HillBookCompany,1990.）。運(yùn)行時(shí)間分為兩個(gè)部分：1.按照從小到大給權(quán)值排序。整數(shù)權(quán)重使用計(jì)數(shù)排序（countingsort）可在線性時(shí)間內(nèi)完成。http://blog.csdn.net/dm_vincent/article/details/7655764http://www.cnb