【文章內(nèi)容簡介】 碼，分析了 Kruskal 算法存在的缺點(diǎn)，并做了相應(yīng)的改進(jìn)。將分水嶺與最小生成樹方法結(jié)合，提出了 K ?VW 方法，通過實(shí)驗(yàn)進(jìn)行驗(yàn)證。第五章總結(jié)與展望，總結(jié)了本文的主要工作，指出以后需要進(jìn)一步完善的地方。8第二章 基于圖論的圖像分割方法圖論起源于著名的柯尼斯堡七橋問題。1736 年歐拉用抽象分析法將這個(gè)問題轉(zhuǎn)化為一個(gè)圖論問題：用點(diǎn)代替每塊陸地，用連接相應(yīng)兩點(diǎn)的一條線代替橋。歐拉證明了這個(gè)問題無解，并且給出了對(duì)于一個(gè)特定圖以某種方式走遍的判定法則。從 19 世紀(jì)中葉到 20 世紀(jì)中葉，圖論問題大量出現(xiàn)，如漢密爾頓圖問題、四色猜想等。這些問題的出現(xiàn)進(jìn)一步促進(jìn)了圖論的發(fā)展。1847 年，克?；舴颍↘irchhoff）用圖論分析電網(wǎng)絡(luò)，這是最早一個(gè)應(yīng)用于工程科學(xué)的例子。隨著計(jì)算機(jī)科學(xué)的迅猛發(fā)展，在現(xiàn)實(shí)生活中的許多問題，如交通網(wǎng)絡(luò)問題，運(yùn)輸?shù)膬?yōu)化問題，社會(huì)學(xué)中某類關(guān)系的研究，都可以用圖論進(jìn)行研究和處理。圖論在計(jì)算機(jī)領(lǐng)域中，諸如算法、語言、數(shù)據(jù)庫、網(wǎng)絡(luò)理論、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、人工智能等方面都有廣泛應(yīng)用。近年來基于圖論的圖像分割技術(shù)是國際圖像分割領(lǐng)域中一個(gè)新的研究熱點(diǎn)。該方法將圖像映射為帶權(quán)無向圖，將像素視為節(jié)點(diǎn)，利用某種準(zhǔn)則得到圖像的最佳分割，將圖像分割問題轉(zhuǎn)化為最優(yōu)化問題。 基本理論概念 圖的分割 圖、加權(quán)圖和連通圖圖是由若干給定的頂點(diǎn)及連接兩頂點(diǎn)的邊所構(gòu)成的一種拓?fù)鋱D形，用頂點(diǎn)代表事物，用連接兩頂點(diǎn)的邊代表相應(yīng)兩個(gè)事物間的關(guān)系。若用符號(hào)G 代表圖，則G = (V , E) ，其中V 代表頂點(diǎn)的集合，E 代表邊的集合，每條邊對(duì)應(yīng)著兩個(gè)相關(guān)的頂點(diǎn)。對(duì) E 中的每條邊e ，賦給一個(gè)實(shí)數(shù) w( e) ，稱為邊e 的權(quán)，每個(gè)邊都賦有權(quán)的圖稱為加權(quán)圖。權(quán)在不同的問題中會(huì)有不同的含義，可以表示距離、費(fèi)用、時(shí)間、電阻等。在無向圖G 中，如果從頂點(diǎn)u 到頂點(diǎn)v 有路徑，則稱u 和v 是連通的。如果圖中任意兩個(gè)頂點(diǎn)u 和v 都是連通的，則稱圖G 是連通圖，否則稱為非連通圖。 子圖、補(bǔ)圖和割兩個(gè)圖G = (V , E) 和G’= (V ’,E’)，若V’是V 的子集， E’是 E 的子集，則9稱G’為G 的子圖。給定一個(gè)圖G ，由G 中所有節(jié)點(diǎn)和所有能使G 成為完全圖的添加邊組成的圖，稱為圖G 相對(duì)于完全圖的補(bǔ)圖（Complement），或簡稱為G 的 補(bǔ)圖。若G = (V , E) 為連通圖，邊集 E1 ? E ，使圖G 刪除了 E1 的所有邊后，所得到的子圖是非連通圖，而刪除了 E1 的任何真子集后所得到的子圖仍是連通圖，則稱 E1 是G 的一個(gè)邊割集（Edge Cutest）。若某一條邊構(gòu)成一個(gè)邊割集，則稱該邊為割邊（Cut Edge），割邊的集合叫做割集（Cut Set），割集的權(quán)值之和稱作割（Cut）。 鄰接矩陣鄰接矩陣（Adjacency Matrix）是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè) G =（V , E）為無向圖。其中V = ( v1 , v2 , ,vn ) ，那么 n n 鄰接矩陣 A =[ aij ]，其中：1,( v , v) Eaiji j=( vi , v j ) E(21)0 或∞,例如圖 21 中G 的鄰接矩陣如圖 22 所示。圖 21 G 圖 22 G 的鄰接矩陣如果G 為加權(quán)圖，則將 aij =1改為 aij = w(i , j) 。例如圖 23 中G’的鄰接矩陣 如圖 24 所示。圖 23 G’ 圖 24 G’的鄰接矩陣10 圖的最優(yōu)分割準(zhǔn)則令圖G = (V , E) ，G 被劃分為 A 和 B 兩部分，且有 A ∪ B =V ， A ∩ B = ，頂點(diǎn)間邊上的權(quán)為 w(u , v) ，將圖G 劃分為 A 、 B 兩部分的代價(jià)函數(shù)為：cut ( A, B ) = ∑ w(u , v)（22）u∈ A , v∈B使得式（22）值最小的劃分準(zhǔn)則稱為最小割集準(zhǔn)則。常見的割集準(zhǔn)則有歸一化切割（Normalized Cut）[28]、最小切割（MinimumCut）[33]、平均切割（Average Cut）[34]、比例切割（Ratio Cut）[35]、等周切割（Isoperimetric Cut） [36]、最小最大切割（Minmax Cut）[37]、前景切割（ForgoundCut）[38]、嵌套切割（Nested Cut）[39]。最優(yōu)分割準(zhǔn)則的實(shí)現(xiàn)一般有兩種方式：將最優(yōu)準(zhǔn)則轉(zhuǎn)化為求解矩陣方程；使用所定義的準(zhǔn)則直接進(jìn)行圖縮減。 圖像的分割圖像分割是將人們感興趣的具有同質(zhì)特性的目標(biāo)區(qū)域提取出來的過程，在分割過程中可以使用像素的灰度、顏色、紋理等特性。在圖像處理早期階段，因?yàn)閳D像主要是灰度圖像，所以發(fā)展起來的圖像分割技術(shù)也針對(duì)灰度圖像，隨著成像設(shè)備技術(shù)的發(fā)展，彩色圖像成為主要的處理對(duì)象，原來的技術(shù)不能直接應(yīng)用在彩色圖像上，需要根據(jù)圖像中的多種信息來進(jìn)行分割。 圖像到圖的轉(zhuǎn)化將圖像映射到加權(quán)圖（Weighted Graph），用圖G 中的頂點(diǎn)vi V 表示圖像中的像素，用圖的邊eij 表示像素之間的相鄰關(guān)系，邊上的權(quán)重 wij 表示像素特征之間的差異或相似性。 權(quán)函數(shù)權(quán)函數(shù)一般定義為兩個(gè)節(jié)點(diǎn)之間的相似度，常見的權(quán)函數(shù)有如下形式：|| X i ? X j2|| Fi ?Fj ||22||2|| X? X rw(i , j)exp( ?) ,ij||= exp( ?)σ22（23）σI2X,otherwise0對(duì)于灰度圖像，F(xiàn)i 和 Fj 分別表示像素i 和 j 的灰度值，Xi 和 X j 分別為像素i和 j 的空間坐標(biāo)，σI 為灰度高斯函數(shù)的標(biāo)準(zhǔn)方差，σX 為空間距離高斯函數(shù)的標(biāo)11準(zhǔn)方差， r 為兩像素之間的有效距離。這種權(quán)值函數(shù)的定義，考慮到空間距離，對(duì)于灰度圖像計(jì)算量很大，對(duì)于彩色圖像計(jì)算量更大。在不考慮空間距離的鄰域系統(tǒng)中，可以簡單地把權(quán)函數(shù)定義為相鄰像素特征之間的絕對(duì)差值：w(i , j ) =| Fi ? Fj |（24）對(duì)于灰度圖像， Fi 的值為像素的灰度值，對(duì)于 RGB 顏色空間的彩色圖像，F(xiàn)i 可以是 R、G、B 中的任意顏色分量，或者是其組合；對(duì)于 HSI 顏色空間， Fi可以是 H、S、I 的組合，或者是 H 和 S 的組合。還有其它一些利用圖像的灰度、顏色、紋理、距離、形狀、運(yùn)動(dòng)等信息構(gòu)造權(quán)函數(shù)的方法，但是對(duì)于不同的圖像，選擇一種信息還是幾種信息的組合，分割圖像的效果可能是不同的。 鄰域系統(tǒng)鄰域系統(tǒng)定義了像素間的相鄰關(guān)系，一階鄰域系統(tǒng)為 4 連通結(jié)構(gòu)，二階鄰域系統(tǒng)為 8 連通結(jié)構(gòu)，一般圖像分割算法使用二階鄰域系統(tǒng)，如果為了減少運(yùn)算量，可以使用 4 連通結(jié)構(gòu)，但是分割效果不如 8 連通結(jié)構(gòu)。如圖 25 為 4 連通結(jié)構(gòu)，像素 p 的坐標(biāo)為( x, y) ，它的 4 連通鄰域坐標(biāo)分別為 ( x , y ?1) 、 ( x , y +1) 、 ( x ?1, y) 、 ( x +1, y) ，如果 p 位于圖像的邊界，則 p 的某一鄰域像素位于圖像的外部。圖 25 p 的 4 連通鄰域 圖 26 p 的 8 連通鄰域如圖 26 為 8 連通結(jié)構(gòu)， p 的另外 4 個(gè)連通鄰域坐標(biāo)分別為( x ? 1, y ?1) 、 ( x + 1, y ?1) 、 ( x ?1, y +1) 、 ( x +1, y +1) ，如果 p 位于圖像的邊界，則 p 的某些鄰域像素位于圖像的外部。 圖像的最佳分割12將圖像分割為多個(gè)小區(qū)域時(shí)，對(duì)圖像分割效果的好壞，沒有絕對(duì)的客觀評(píng)價(jià)準(zhǔn)則，使用不同的圖像，不同的分割原則和方法，得到的效果可能互有好壞，無法找到通用的方法適用于所有的圖像。除了從方法的時(shí)間復(fù)雜度、空間復(fù)雜度、抗噪性等客觀指標(biāo)分析外，一般是基于人類的視覺系統(tǒng)，對(duì)人的視覺系統(tǒng)看到的結(jié)果進(jìn)行評(píng)價(jià)，即分割結(jié)果是否將我們感興趣的目標(biāo)區(qū)域（前景）和背景區(qū)域精確分割開，是否存在錯(cuò)誤分割、過分割或者欠分割。各種算法分割出的區(qū)域與人類視覺判斷的分割區(qū)域之間會(huì)有 3 種誤差：一種是分割后的圖像中存在冗余區(qū)域；一種是應(yīng)分割開的區(qū)域未被分割；另一種是分割算法沒有正確給出邊界。在基于圖論的圖像分割方法中，可以明確地規(guī)定圖像分割的準(zhǔn)則，將圖分割成多個(gè)子集，子集內(nèi)頂點(diǎn)間關(guān)系緊密，而子集間頂點(diǎn)的關(guān)系松散。若使用分割函數(shù)，可以設(shè)一幅圖像為一個(gè)帶權(quán)無向圖G = (V , E , W ) ，像素集當(dāng)做節(jié)點(diǎn)集V ，邊緣集當(dāng)做邊集 E ，像素間的連接權(quán)為 w(i , j) 。將圖像二分為集合 A 、B 的代價(jià)函數(shù)為cut ( A, B ) = ∑ w(i , j) ，對(duì)于一幅圖像，使得cut ( A, B) 函數(shù)最小的劃分i∈ A , j∈B即圖像的最佳分割，這種分割準(zhǔn)則應(yīng)對(duì)某類圖像具有可靠的一致性或穩(wěn)定性，相鄰區(qū)域之間的邊界應(yīng)是完整和精確定位的。 彩色空間分割 RGB 向量空間分割RGB 顏色空間是一種立方體空間結(jié)構(gòu)模型，用 Red、Green、Blue 三個(gè)基本分量表示顏色，不同的顏色處在立方體上或者其內(nèi)部。使用 RGB 彩色向量空間分割圖像的方法直觀，給定一個(gè)感興趣的彩色點(diǎn)樣品集，可以得到一個(gè)彩色平均估計(jì)，這種彩色是希望分割的彩色。令這個(gè)平均彩色用 RGB 向量α來表示，分割的目的是將給定圖像中的每個(gè) RGB 像素分類，因此需要設(shè)置相似性度量。最簡單的度量之一是歐氏距離，令 z 代表 RGB 空間中的任意一點(diǎn)，如果它們之間的距離小于特定的閾值 D0 ，則稱α與 z 是相似的，α與 z 之間的歐氏距離為：11T= [( a? z)2+ ( a? z)2+ ( a? z2]2（25）D (α, z) =（α ? z ）（α ? z ）2RRGBB)G其中，下標(biāo) R,G , B 表示向量α與 z 的 RGB 分量。 HSI 向量空間分割13如果只在單獨(dú)的平面上分割一幅彩色圖像，可以選擇 HSI 顏色空間，它是接近人對(duì)顏色視覺感知的一種彩色空間。色調(diào)（Hue）反映顏色的類別，區(qū)分不同顏色的特征屬性。飽和度（Saturation）表示顏色接近光譜色的程度，反映顏色的純度。強(qiáng)度（Intensity）表示顏色明暗的程度，主要受光源強(qiáng)弱影響。HSI 三個(gè)分量間的相關(guān)性比 RGB 三個(gè)分量間的小，而人眼對(duì) H、S、I 變化的區(qū)分能力比對(duì) R，G、B 的強(qiáng)。在 HSI 空間中彩色圖像的每個(gè)均勻性彩色區(qū)域都對(duì)應(yīng)一個(gè)相對(duì)一致的色調(diào)，這使色調(diào)能夠用來進(jìn)行獨(dú)立于陰影的彩色區(qū)域分割。因此 HSI（色調(diào)、飽和度和強(qiáng)度）顏色空間模型可從攜帶的彩色信息中消去強(qiáng)度分量的影響，使 HSI 模型成為開發(fā)基于彩色描述的圖像處理方法的理想工具。 三種基于圖論的圖像分割方法基于圖論的圖像分割，使劃分的兩個(gè)子圖內(nèi)部相似度最大，子圖間的相似度最小，盡量避免出現(xiàn)分割粗糙現(xiàn)象或者過度分割現(xiàn)象。Ratio Cut 方法直接使用定義準(zhǔn)則進(jìn)行圖縮減，而 Normalized Cut 方法結(jié)合譜方法，求解矩陣方程。 Ratio Cut 分割法Ratio Cut[35]是 Wang Song 提出的具有穩(wěn)定的邊權(quán)函數(shù)的圖割模型，定義了一個(gè)新的代價(jià)函數(shù)，并給出尋找最小比例割的執(zhí)行算法。在構(gòu)建的圖 G 中，賦給每條邊 (u , v) 兩個(gè)權(quán)重 w1 (u , v) 0 和 w2 (u , v) 0 ，w1 (u , v) 為第一邊權(quán)重，表示兩個(gè)區(qū)域之間的相似度； w2 (u , v) 為第二邊權(quán)重，表w (u , v)示U (u) 與U ( v) 之間邊的數(shù)目； w1 (u , v) 為邊權(quán)重比率，如果 w2 (u , v) =1，邊權(quán)重2比率表示的就是兩個(gè)區(qū)域間每條邊在單位長度上的平均一致性。定義第一邊界代價(jià)函數(shù)和第二邊界代價(jià)函數(shù)分別為：c1 ( A,