資源描述：
《基于圖的快速圖像分割算法》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、.Efficientgraph-basedimagesegmentation2.相關工作G=(V,E)，每個節(jié)點對應圖像中一個像素點，E是連接相鄰節(jié)點的邊，每個邊有對應有一個權重，這個權重與像素點的特性相關。最后，我們將提出一類基于圖的查找最小割的分割方法。這個最小割準則是最小化那些被分開像素之間的相似度?！?8】原文中叫Component,實質上是一個MST,單獨的一個像素點也可以看成一個區(qū)域。預備知識：圖是由頂點集（vertices）和邊集（edges）組成，表示為，頂點，在本文中即為單個的像素點
2、，連接一對頂點的邊具有權重，本文中的意義為頂點之間的不相似度，所用的是無向圖。樹：特殊的圖，圖中任意兩個頂點，都有路徑相連接，但是沒有回路。如上圖中加粗的邊所連接而成的圖。如果看成一團亂連的珠子，只保留樹中的珠子和連線，那么隨便選個珠子，都能把這棵樹中所有的珠子都提起來。如果，i和h這條邊也保留下來，那么h,I,c,f,g就構成了一個回路。最小生成樹（MST,minimumspanningtree）：特殊的樹，給定需要連接的頂點，選擇邊權之和最小的樹。上圖即是一棵MST。本文中，初始化時每一個像素點都
3、是一個頂點，然后逐漸合并得到一個區(qū)域，確切地說是連接這個區(qū)域中的像素點的一個MST。如圖，棕色圓圈為頂點，線段為邊，合并棕色頂點所生成的MST，對應的就是一個分割區(qū)域。分割后的結果其實就是森林。邊的權值：對于孤立的兩個像素點，所不同的是顏色，自然就用顏色的距離來衡量兩點的相似性，本文中是使用RGB的距離，即...3圖割3.1我們定義D，衡量分割區(qū)域之間是否有明顯邊界。D是通過測量沿著兩個區(qū)域邊界元素的不相似度對比測量兩個區(qū)域內部各自內部元素之間不相似度。我們用C表示一個部分的內在差異，是該區(qū)域最小生成
4、樹上的最大權值。我們定義兩個區(qū)域間的不同是兩個區(qū)域連接邊的最小權值，如果C1，C2之間不想連，則Dif(C1,C2)=無窮大，使用下面的閾值函數(shù)來控制兩個區(qū)域之間的差異性必須大于最小內在差異，我們定義如下函數(shù)：其中MInt是：閾值函數(shù)控制著兩個區(qū)域之間的差異性必須大于他們內在差異性，以便它們之間有明顯的邊界（D為true）。對于小的區(qū)域，Int(C)是對局部數(shù)據(jù)的特性的一個好的估計。在一些極端情況下，如果
5、C
6、=1，Int(C)=0。因此我們的閾值函數(shù)為這里的
7、C
8、是C的大小，K是某個特定常量參數(shù)。對
9、于小的區(qū)域我們需要明顯的邊界。實際上k設置為一系列值.說明：當二者都是孤立的像素值時，，所有像素都是"零容忍"只有像素值完全一樣才能合并，自然會導致過分割。所以剛開始的時候，應該給每個像素點設定一個可以容忍的范圍，當生長到一定程度時，就應該去掉該初始容忍值的作用。原文條件如下????增加項:其中為區(qū)域所包含的像素點的個數(shù)，如此，隨著區(qū)域逐漸擴大，這一項的作用就越來越小，最后幾乎可以忽略不計。那么...就是一個可以控制所形成的的區(qū)域的大小，如果，那么，幾乎每個像素都成為了一個獨立的區(qū)域，如果，顯然整張圖
10、片都會聚成一塊。所以，越大，分割后的圖片也就越大4算法和它的特性定義1分得太細。定義2分得太粗特性1相近的算法【6】算法1分割算法輸入：圖，有n個頂點和M條邊。輸出：對V的分割為0.首先將邊E按照權重大小由小到大排列為；1.開始一個分割，每一個頂點是它自己的區(qū)域；2.重復步驟3，q=1,....,m3.按照如下方法，通過構建：按順序，和表示第q次相連的兩個頂點，比如，。如果和在的不相交的兩個區(qū)域中，并且是較小的相對于這些區(qū)域的內在差異性，那么合并這兩個區(qū)域除非什么也不做。包含成為的一部分，讓包含成為一
11、部分（letCiq?1bethecomponentofSq?1containingviandCjq?1thecomponentcontainingvj）。如果，將和合并到中成為。否則=4.返回算法分析：具有全局特性，既不會分得太細也不會分得太粗。該算法是貪心決策引理1上述算法中的步驟3，如果和沒有合并，那么和中至少有一個最后會在分類的區(qū)域中。證明見paper4.1實施問題和運行時間...實施主要是包括并查集結合排序和路徑壓縮（adisjoint-setforestwithunionbyrankandp
12、athcompression），參考《算法導論》（IntroductiontoAlgorithms.TheMITPress（麻省理工出版社）,McGraw-HillBookCompany,1990.）。運行時間分為兩個部分：1.按照從小到大給權值排序。整數(shù)權重使用計數(shù)排序（countingsort）可在線性時間內完成。http://blog.csdn.net/dm_vincent/article/details/7655764http://www.cnb
