【正文】 較好的圖像分割效果，因此受到越來越多國內(nèi)外學(xué)者和專家的關(guān)注。通過對基于圖論的組合優(yōu)化算法的研究和改進，提出了一種改進的基于圖論的 Normalized Cut 準(zhǔn)則的組合優(yōu)化算法，并應(yīng)用到閾值圖像的分割中，該算法的實時性上和分割的效果上都取得了很好的成效，同時還具有較好的抑制噪聲的能力。第三章 介紹和分析了基于圖論的圖像分割方法中常用的運用NormalizeCut準(zhǔn)則割集作為分割準(zhǔn)則的圖像分割方法，并在把這種方法運用到閾值化的圖像分割的基礎(chǔ)上，分析了在該種方法中像素點間的相關(guān)性權(quán)值的計算公式的不足，提出了一種具有抗噪性的基于歸一化準(zhǔn)則的圖像分割方法，通過實驗結(jié)果，驗證了該種圖像分割方法的優(yōu)勢和實用性。并用類似于基因勢函數(shù)的計算公式作為圖權(quán)公式，該公式以統(tǒng)計學(xué)的形式更為全面的反映了兩像素點間的相似性，同時又避免了通過手動的形式來設(shè)置控制像素點間相似性因素的差異敏感程度參數(shù)的不足，提高了算法的通用性。在此基礎(chǔ)上提出了本課題的研究意義。而有關(guān)圖的劃分的理論是基于圖論的圖像分割方法的理論基礎(chǔ)，為圖像分割提供了一種新的理論方法。其中，集合 Vex 中的元素個數(shù)，即圖的頂點數(shù)，是由圖 G 的構(gòu)成來決定，稱為圖 G 的階。一般情況下，人們依據(jù)連接兩頂點間的邊是否具有方向，把圖分為無向圖和有向圖。通常情況下這些數(shù)值又稱為圖中邊的權(quán)值。對于無向圖來說，頂點 VX的度是指與 VX 相連接的邊的數(shù)目，一般記為 deg(VX ) 。9i ii而圖 G 中每個頂點都有兩個度。如圖 所示的有向圖表示為如下形式，G = G(Vex, Eag )，其中Vex = {v1, v2 , v3 , v4 , v5 , v6}，Vag = {v1v2 , v1v6 , v2v3 , v4v3 , v4v5 , v6v5 , v6v1}。權(quán)值集合是和邊集合中的元素是一一對應(yīng)的。如果用頂點代表事物，而連接兩頂點的邊則來表示相應(yīng)這兩個事物直接的一種關(guān)系權(quán)重。這中劃分準(zhǔn)則是圖的最佳也是最簡單的準(zhǔn)則。11w8w7圖像的分割圖像圖像的像素圖像的相鄰像素相鄰像素間的相似度圖的分割圖 G={V,E}圖的頂點：V圖的邊：E圖的邊權(quán)值：W圖 圖像分割與圖的分割間的關(guān)系 圖像的描述圖像是人類視覺的基礎(chǔ)，是自然景物的客觀反映，是人類認識世界和人類本身的重要源泉。在提取目標(biāo)時這些特征也不是都要全部考慮的，而是根據(jù)實際情況選取恰當(dāng)?shù)奶卣?。圖 可以更好的把圖與圖像對應(yīng)起來 基于圖論的圖像分割基于圖論的圖像分割方法的基本思想就是把圖像的圖像的結(jié)構(gòu)轉(zhuǎn)換為圖的結(jié)構(gòu)，把能夠求出一個圖的最佳劃分的理論知識運用到圖像的分割中來，從而獲取較為理想圖像分割效果。通過這種方法，就可以把復(fù)雜的圖像分割問題轉(zhuǎn)換到圖的最優(yōu)劃分的問題，可以認為是一種點對聚類的最佳方法 [24]。根據(jù)圖的某種特定劃分建立相應(yīng)的能量函數(shù)，該能量函數(shù)的最小值即對應(yīng)圖像的一個最佳分組 [25]。該方法首先運用最短生成樹的理論來對圖像進行粗分割，然后再用多段圖的方法多分割后的圖像進行進一步的分割和合成。同年，劉丙濤等人 [29]提出了一種基于圖論的 SAR 圖像分割新方法，該方法運用 GornoryHu 算法得到對應(yīng)的等價樹和多尺度結(jié)構(gòu)對圖像進行最優(yōu)劃分，從而來對圖像進行分割。這種割集的特點是求解簡單，但可能會造成孤立點的分割現(xiàn)象，因此較易傾向于較小的分割。235。該割集的特點是速度較慢，但可以避免劃分向短邊偏釋。相對于較為簡單的閾值分割方法來說，基于圖論的圖像分割方法在局部處理和抑制噪聲能力上有較為明顯的優(yōu)勢。因此，基于圖論的圖像分割方法的特點可以總結(jié)為以下幾點：（ 1）在圖像的分割中全局信息和局部特征的兼顧性基于圖論的圖像分割方法結(jié)合了圖論網(wǎng)絡(luò)處理數(shù)據(jù)時局部特征和使用目標(biāo)函數(shù)易于處理全局信息的優(yōu)點，在全局特征和局部特征的之間找到了一種平衡，使得實現(xiàn)算法有較好的魯棒性。雖然閾值法圖像分割簡單，但不易得到圖像中局部信息，而基于區(qū)域的圖像分割方法則容易產(chǎn)生過分割，也不能很好的把握全局信息。其主要原因就是這種方法可以在進行圖像分割時提取重要的信息，忽略不重要的信息，從而減少了數(shù)據(jù)的處理時間，使得基于圖論的圖像分割方法有著“智能”的特點。 基于圖論的圖像分割方法的缺陷不足基于圖論的圖像分割方法的雖然具有較好的分割效果和應(yīng)用前景，但是這種分割方法還是存在著一定的缺陷和不足。但是這種實現(xiàn)方式還是存在一定的算法復(fù)雜性的問題，尤其是在求解這種大規(guī)模權(quán)值矩陣的特征向量時，是一個非常復(fù)雜的問題，因為在解決這個問題是不僅要花費較多的時間，還需要大量的存儲空間來提供算法的實現(xiàn)。本文也在這個基礎(chǔ)上，實現(xiàn)了基于Normalize Cut 準(zhǔn)則和 MinMax Cut 準(zhǔn)則的圖像分割方法的改進。尤其是在處理含義椒鹽噪聲或隨機噪聲、邊界不明顯、背景復(fù)雜的圖像時，基于圖論的圖像分割方法的分割效果也就無法達到理想的效果。如果想達到理想的分割效果，就必須人為的來更改這些參數(shù)的值。本章針對這一問題，提出一種新的具有抑制噪聲能力的圖像分割方法。而閾值化圖像分割方法是一種非常簡單的圖像分割方法，并且在圖像分割領(lǐng)域也有很長的研究。因此，閾值分割是圖像分割中一類重要方法。 基于圖論的圖像分割與閾值化分割結(jié)合的優(yōu)勢作為一種新型的理論工具，圖劃分理論被應(yīng)用到圖像分割中來，從而形成一種基于圖論的圖像分割方法。文獻[44]中作者采用 Normalized Cut 割集準(zhǔn)則來區(qū)分圖像中的目標(biāo)和背景，把Normalized Cut 準(zhǔn)則與圖像的閾值分割結(jié)合起來。該方法采用Normalized Cut劃分測度作為劃分目標(biāo)和背景的閾值圖像分割準(zhǔn)則，采用基于灰度值的權(quán)值矩陣代替基于圖像像素個數(shù)的權(quán)值矩陣來描述像素之間的關(guān)聯(lián)，并在圖權(quán)計算中，增加了該像素點與其鄰域的空間相關(guān)信息，更全面地反映了兩相鄰像素間的相關(guān)性，從而提高了算法的抗噪能力。 w(u, v) 是用來衡量節(jié)點 u 和 v 的相似程度，為E 中元素的邊權(quán)值。 X19()??在公式（ ）中， D是一個對角矩陣，對角線上的元素為 di = ∑ w(i, j) ，矩陣j的大小為 N N 。為了得到圖像的一個分割結(jié)果，可以通過對應(yīng)的全圖的最優(yōu)劃分來實現(xiàn)，而全圖的最優(yōu)劃分可以通過特征系統(tǒng)式（）中的第二個最小的特征值對應(yīng)的特征矢量來完成。 最佳分割求解的改進若 I = [ f ( x, y)]M N 表示大小為 M N 的數(shù)字圖像，V={（i，j）：i=1，2，…，M；j=1，2，…，N}，表示圖像中個像素點的位置集合，M和N分別是圖像的高度和寬度。假設(shè)定義圖G中連接兩個節(jié)點u和v的邊權(quán)值為 w(u, v) ，對任意門限t（0tL1）就可以把圖像分為兩部分，即背景和目標(biāo)。令f（x，y）為圖像在像素（x，y）處的灰度值，那么V、K和f（x，y）滿足下面的條f ( x, y) ∈ K ， ?( x, y) ∈VV j = {( x, y) : f ( x, y) = j, ( x, y) ∈V }, j ∈ K()()L?1∪Vii =0= V V i ∩ Vj= ?i, j ∈ K()把圖像I中的每個像素點看作無向圖的一個節(jié)點，那么就可以用一條邊將每對節(jié)點連接起來，并為每個邊賦予權(quán)值，該權(quán)值反映了這兩個像素點的相關(guān)性。 改進的基于 Normalized Cut 準(zhǔn)則的圖像分割方法本章對基于Normalized Cut準(zhǔn)則的圖像分割方法的改進主要體現(xiàn)在以下兩個方面，首先在圖權(quán)計算中，增加了該像素點與其鄰域的空間相關(guān)信息，更全面地反映了兩相鄰像素間的相關(guān)性，從而提高了算法的抗噪能力。其中的元素為 w(i, j) ， 235。最小的 Ncut 值對應(yīng)的劃分就是圖 G 的最優(yōu)劃分。這種分割方法把 Normalized Cut 準(zhǔn)則作為圖劃分的依據(jù)，同時把Normalized Cut 作為衡量圖像分割最優(yōu)化的能量函數(shù)。但是，該方法抗噪性較差。通過對能量函數(shù)進行組合優(yōu)化來實現(xiàn)對像素18的合理分類。雖然很多國內(nèi)外學(xué)者嘗試用很多的方法來解除這種難題，但是效果仍然是不盡理想，因此有必要把一些新的理論和思想引進來，以便獲得較好的效果來，這也是挑戰(zhàn)這種難題的一個很好的研究領(lǐng)域 [43]。 閾值化分割在基于圖論的圖像分割方法中的應(yīng)用人們在處理圖像時，尤其是在處理灰度圖像時，人們發(fā)現(xiàn)圖像中人們感興趣部分(目標(biāo)圖像)與其周圍的部分(背景圖像)在灰度值上存在著很大的差異。實驗結(jié)果表明，使用該方法進行圖像分割，不僅具有很好的分割效果，而且具有很強的抑制噪聲能力。 本章小結(jié)本章主要介紹了圖的基本概念以及圖劃分的理論、圖與圖像間的相互對應(yīng)關(guān)系，從而引出了基于圖論的圖像分割方法中的一些基本方法、常用的割集準(zhǔn)則，以及基于圖論的圖像分割方法的研究進展、特點和存在的不足，為下文的基于圖論的圖像分割方法的改進提供了理論基礎(chǔ)。（ 3）對圖像的通用性有待于提高傳統(tǒng)的基于圖論的圖像分割方法在描述圖像信息間的相似性關(guān)系時，即在確定像素點間或區(qū)域間的相似性計算公式中，都涉及到一些參數(shù)的人為設(shè)置。因此在單純的基于圖論的圖像分割方法中，描述像素點間的相互關(guān)系的連接權(quán)值矩陣的取值是否恰當(dāng)，以及能否較好的體現(xiàn)出圖像信息間的特征，都將嚴(yán)重影響圖像的分割效果。因此，如何能夠行之有效提高算法的實現(xiàn)速度，是基16于圖論的圖像分割方面一個主要的研究方向。因此有必要針對這些缺陷不足對基于圖論的圖像分割方法做進一步的改善，使得這種圖像分割方法能具有更好的應(yīng)用前景。不僅能在一般的圖像中取得較好的分割結(jié)果，還可以在處理視頻圖像， 3D 圖像時取得較好的優(yōu)越性 [40]；不僅可以針對灰度圖像進行較好效果的圖像分割，也可以對彩色圖像進行有效的分割。（ 2）智能化的分割 [39]基于圖論的圖像分割方法與計算機視覺中的空間變量的結(jié)合體現(xiàn)了在這種方法在進行圖像分割時運算量的智能化的降低，這也是基于圖論的圖像分割方法的又一特點。在基于圖論的圖像分割方法中把圖中15的節(jié)點映射為圖像中的像素點或者某個細化后的區(qū)域，而圖中的邊則映射為圖像中的像素點或區(qū)域間的相似性度量。雖然在算法在實現(xiàn)的速度上，沒有其他一些簡單的算法快，但是其應(yīng)用的范圍比較廣。該準(zhǔn)則一般是通過求解方程L0 Z 0 = d0 來實現(xiàn)的，該割集的特點是速度較快。 Z 標(biāo)準(zhǔn)特征系統(tǒng)來實現(xiàn)，該割集的特點是能有效的克服劃分孤立點的問題，但當(dāng)類間重疊較大時容易出現(xiàn)歪斜劃分。 Z 標(biāo)準(zhǔn)特征系統(tǒng)來實現(xiàn)，該割集的準(zhǔn)則的特點是較易傾向于出現(xiàn)較大的分割。同年，李小斌等人 [30]也提出了一種新的加權(quán)割的圖像分割方法，作者通過數(shù)學(xué)理論來證明了這種加權(quán)割模型的的特點，使得該方法能夠同時達到類內(nèi)最小一致性和類間最大相異性。2008 年， Wenbing Tao 等人 [28]提出了一種新的基于圖譜理論的圖像閾值分割方法。2003 年，Pavan 等人 [26]提出一種結(jié)合圖論和聚類理論的新的圖像分割方法，在該方法中，作者將聚類直覺觀念和圖中節(jié)點顯性集間的關(guān)系進行了類似對比，通過節(jié)點顯性集在邊緣帶權(quán)圖中的推廣，建立了一種標(biāo)準(zhǔn)單形和顯性集的二次極值關(guān)系，使得該方法能夠較好的應(yīng)用于局部交互的計算單元，并具有一些生物學(xué)的優(yōu)勢。基于圖論的圖像分割方法的研究主要體現(xiàn)在：最優(yōu)割集的設(shè)計，分割中圖譜方法的應(yīng)用，以及算法實現(xiàn)上的快速性。 基于圖論的圖像分割方法研究進展基于圖論的圖像分割方法是近幾年來國內(nèi)外在圖像分割領(lǐng)域的一個新研究熱點問題。如果把組成圖像的像素點看作是圖的頂點的話，那么就可以把圖像轉(zhuǎn)換一種特殊的圖的結(jié)構(gòu)，同時，在圖像中，每個像素點都與其周圍的像素的存在著某種關(guān)系，這也正是用像素點表示一幅12圖像的原因，而像素點間的關(guān)系就可以表示為圖中的邊。一幅圖像中包含有大量的信息，比如灰度圖像中圖像的灰度，彩色圖像中圖像的色彩，還有圖像的紋理、邊緣以及圖像中目標(biāo)的形狀特征等。由于二者之間存在著一定的聯(lián)系，因此才使得基于圖的一些理論應(yīng)用到圖像中來。把圖 G 劃分為 A、 B 兩部分就是將連接 A 和 B 部分間的邊移去，并且 A 和 B 間滿足： A ∩ B = ?, A ∪ B = Vex ，A 和 B 之間的相異度是指所有移走的邊的權(quán)值總和。如圖 所示的有向圖表示為如下形式， G = G(Vex, Eag ,Weg ) ，其中Vex = {v1, v2 , v3 , v4 , v5 , v6}, Eag = {v1v2 , v2v3 , v3v4 , v4v5 , v5v6 , v6v1, v