【文章內(nèi)容簡介】 以歸并的點為止。如此往復，直到再沒有像素點可以被合并，這樣一個區(qū)域就形成了。和區(qū)域生長算法不同的是，區(qū)域分裂合并法則不需要先找指定的種子像素點，它按照某種一致性準則直接進行分裂或合并區(qū)域，當相鄰的區(qū)域相似性一致時，通過合并運算合并為一個大的區(qū)域，相反的，當一個區(qū)域內(nèi)不滿足一致性原則就分裂成幾個小的區(qū)域。因此區(qū)域分裂合并算法的研究重點是對分裂和合并的準則設計?；趨^(qū)域的分割方法的優(yōu)點為：由于閾值化分割方法很少或沒有考慮到空間關系，使得在多閾值選擇上受到諸多的限制，而基于區(qū)域的分割算法則完全可以彌補這種不足?；趨^(qū)域的分割方法在圖像的空間關系上，不僅考慮到像素的相似性，而且還考慮到空間區(qū)域上的鄰接性，因此可以有效地消除噪聲的4干擾，在算法上有很強的魯棒性。無論是合并運算還是分裂運算，都可以很好的將分割深入到像素級，因此在圖像分割的精度上有較高的保障?；趨^(qū)域的方法的缺點則是：由于物體的輪廓線經(jīng)常是任意形狀的，因此在分割的速度上都較慢。（4） 基于聚類的分割基于聚類分割就是按照樣本之間的相似性原則把集合劃分成若干個互不相交的子集，劃分的結(jié)果應滿足某種表示聚類準則質(zhì)量最大化。如果用距離表示兩個樣本間的相似性時，就會把特征空間劃分成若干個區(qū)域，這樣每一個區(qū)域相當一個類別。一些常用的距離度量準則都可以作為相似性的度量標準。聚類分割中典型的算法有模糊C均值算法 [10] 、K均值算法 [11]、分層聚類方法 [12] 和期望最大化等。雖然聚類算法不需要訓練集，但對初始分割時需要提供一個初始參數(shù)，同時初始參數(shù)的選定的恰當與否對最終分類結(jié)果有很大的影響，因此對于聚類分割，初始參數(shù)的選取成為該方法的一個技術難點。（5） 結(jié)合其他特定理論的分割方法近年來，大量學者致力于將新方法、新概念應用于圖像分割中，在圖像分割方面，結(jié)合特定理論的圖像分割方法已取得了較好的應用效果。圖論、小波分析和小波變換、模糊理、神經(jīng)網(wǎng)絡、遺傳算法、粗糙集理論、數(shù)學形態(tài)學 [1315]等以近年來發(fā)展迅速的灰色系統(tǒng)理論等數(shù)學工具的利用，為圖像分割提供了更多的選擇，并且針對不同的圖像有效地改善了分割效果?；趫D論的圖像分割技術是近年來國內(nèi)外在圖像分割領域的一個新的研究熱點。該方法基本思想是將圖像映射為帶權無向圖, 把圖像的像素點視作節(jié)點, 利用最小剪切準則得到圖像的一個最佳分割。該方法在本質(zhì)上把圖像分割問題轉(zhuǎn)化為圖的最優(yōu)化問題, 是一種點對聚類方法, 因此在數(shù)據(jù)聚類也會有很好的應用前景。但由于該方法涉及的理論知識較多, 應用研究也還處在初級階段, 因此該法將會成為圖像分割領域中一個具有挑戰(zhàn)性的研究熱點。 圖像分割的發(fā)展現(xiàn)狀及趨勢圖像分割方法的重要性以及國內(nèi)外學者的高度關注，使得圖像分割技術得到了很好的發(fā)展，到目前為止，已經(jīng)形成了很多種圖像的分割方法，但是由于圖像本身的特性，使得每種圖像分割方法都是針對某一類圖像的，即每種圖像分割算法只能針對特定的圖像取得較好的分割結(jié)果，而不能對所有種類的圖像都得到較好的分割結(jié)果。算法本身具有一定的針對性，而沒有不具有算法的通用性。這就使得人們在進行圖像分割時，只能針對某類圖像進行分割，沒不能對所有的圖像進行分割。造成這種局面的主要原因，主要是因為以下三個方面[16]：（1）由于現(xiàn)實生活中，圖像的種類復雜，使得人們在研究對圖像進行分割5時，在對算法進行設計時，都有時針對某類圖像的，而沒有考慮其他的圖像。即在算法的本身就具有一定的針對性。（2）人們在對圖像進行分割時，尤其在設計圖像的分割算法時，不僅需要數(shù)學理論的支持，還需要對心理學的借助，這是因為人們在處理圖像時，視覺心里的反映是一個很重要的方面，不能被忽視。而目前大多數(shù)的圖像分割算法，由于各種原因，而沒有很好的考慮到這一點，因此很難取得較好的圖像分割效果。因此，應該借助各種新的理論和工具來彌補這種不足。同時，在面對數(shù)量龐大，各式各樣的圖像庫，我們還要主要圖像算法的實時性，因此對圖像分割算法的研究，仍然有一定的挑戰(zhàn)性。（3）人類視覺系統(tǒng)是一個復雜的系統(tǒng)，它涉及到很多領域的知識和理論。到目前為止，我們還沒有一個標準化、系統(tǒng)化的認識，同時也缺乏對這要知識的認識和了解。所以，設計一個適用性很好的圖像分割算法仍然是一個很有挑戰(zhàn)性的事情。縱觀圖像分割技術的發(fā)展歷程，雖然在圖像分割技術上來說，很難得到一個非常理想的圖像分割方法。但對新知識新理論的借助，對這要技術上的克服不是沒有一定的可能的，而且這也是圖像分割方法的發(fā)展的一個必然趨勢。目前主要的研究思路包括以下幾個方面：（1） 神經(jīng)網(wǎng)絡 [16]、模糊算法 [17]、遺傳算法 [18]、圖論算法 [19]、粗糙集理論、小波分析 [20] 、形態(tài)學等新的方法和概念應用到圖像分割領域。這些新的理論知識和工具的引入，為圖像分割方法開辟了新的思路，也為圖像分割方法的研究注入了新鮮的動力和活力。同時這些新理論和新工具的借鑒，避免了單一算法的不足，提高了圖像分割算法的有效性。（2） 對 多 種 圖 像 分 割 算 法 的 結(jié) 合 時 圖 像 分 割 方 法 的 另 一 個 新 的 研 究 思路，也受到人們越來越高度的重視。目前的圖像分割方法都中對多種圖像分割方法的結(jié)合。這種結(jié)合后的圖像分割方法具有一定的優(yōu)勢。因為單一的圖像分割算法都具有一定的針對性和局限性。而兩種或者兩種以上的方法的結(jié)合，往往可以避免這種單一算法的不足，起到揚長避短，各顯其優(yōu)的特性。當然這種結(jié)合的優(yōu)勢，要在有效的結(jié)合下才能顯示，僅僅把兩種算法放在一起是無法發(fā)揮這樣優(yōu)勢的。（3） 對特定鄰域的知識的注入和對特殊問題的解決也是圖像分割方法研究中的一個熱點和重點。人們對圖像分割方法的研究不再局限于圖像分割處理技術的方面，與其他領域的圖像處理的結(jié)合將會成為圖像分割技術的另一個研究熱點。 課題的提出與研究的意義在對圖像的研究和應用中，人們往往僅對圖像中的某些部分感興趣。這些6部分常稱為目標或前景(其他部分稱為背景).它們一般對應圖像中特定的、具有獨特性質(zhì)的區(qū)域。為了辨識和分析目標，才有可能對目標進一步利用。圖像分割就是指把圖像分成各具特性的區(qū)域并提取出感興趣目標的技術和過程。這里特性可以是像素的灰度、顏色、紋理等，預先定義的目標可以對應單個區(qū)域，也可以對應多個區(qū)域。圖像分割技術不僅是一種重要的圖像處理技術，而且還在人類的生產(chǎn)和生活中得到廣泛的應用，因此受到了越來越多人的關注，吸引了越來越多專家和學者的重視和研究。由于圖像分割的廣泛應用，因此圖像在不同領域也有著其不同的應用名稱，比如在在目標檢測領域中的目標輪廓技術，圖像求差和圖像區(qū)分技術等，以及在圖像識別技術中的目標識別和目標跟蹤等等。無論圖像分割技術的名稱如何變化和改變，但其本身的核心仍然不會偏離圖像分割技術的。圖像處理中，圖像分割是最為基礎和重要的領域之一，也是低級計算機視覺中最基本最重要的研究內(nèi)容，是成功進行圖像分析、理解與描述的關鍵技術，因為圖像分割結(jié)果的質(zhì)量直接影響以后進行的分析、識別和解釋的質(zhì)量。從上世紀 50 年代，人們就可以研究圖像的分割方法，隨著研究的深入和計算機科學技術的發(fā)展，以及與新理論和新工具的借鑒和結(jié)合，到目前為止，專家學者們以及提出了上千種各種類型圖像分割方法，而且這方面的研究仍在積極進行。因此對這方面的研究有著極其重要的理論意義和現(xiàn)實意義?；趫D論的圖像分割方法是近年來一個研究熱點，該方法把圖像看作是一個帶權圖，圖中的節(jié)點對應著圖像的像素，權值的大小表示兩點間的相關性。通過對能量函數(shù)進行組合優(yōu)化來實現(xiàn)對像素的合理分類。這種運用圖劃分的理論來實現(xiàn)對圖像中目標圖像的分割方法，相對于其他的圖像分割方法，在某些方面取得了較好的圖像分割效果，因此受到越來越多國內(nèi)外學者和專家的關注。雖然基于圖論的圖像分割方法具有一定的優(yōu)勢，但是這類方法一般都有較高的復雜性，使得算法實時性較差，同時在區(qū)分像素點間的相似性時，也存在這一些問題。因此有必要把基于圖論的圖像分割方法與其他的有關圖像處理的理論和知識進行有效的結(jié)合，以便取得更好的圖像分割效果。 研究內(nèi)容及論文的組織結(jié)構(gòu)論文首先對圖像分割的方法進行了研究，同時深入的研究了基于圖分割理論的圖像優(yōu)化組合分割算法。通過對基于圖論的組合優(yōu)化算法的研究和改進，提出了一種改進的基于圖論的 Normalized Cut 準則的組合優(yōu)化算法，并應用到閾值圖像的分割中，該算法的實時性上和分割的效果上都取得了很好的成效，同時還具有較好的抑制噪聲的能力。其次，提出了一種改進的基于圖論的MinMax Cut 準則的組合優(yōu)化算法，該算法把傳統(tǒng)的基于 MinMax Cut 準則圖像分割方法，應用到閾值圖像分割中，大大節(jié)約了算法的實現(xiàn)時間和空間，同7時也取得了較好的分割效果。本論文的結(jié)構(gòu)安排如下:第一章 在閱讀大量的國內(nèi)外文獻基礎上，研究了有關圖像分割的基本理論，深入地探討了有關圖像分割的方法，總結(jié)了圖像分割的含義，分類及發(fā)展現(xiàn)狀和今后的趨勢。第二章 介紹了圖的基本概念以及圖劃分的理論、圖與圖像間的相互對應關系，從而引出了基于圖論的圖像分割方法中的一些基本方法、常用的割集準則，以及基于圖論的圖像分割方法的研究進展、特點和存在的不足，為下文的基于圖論的圖像分割方法的改進提供了理論基礎。第三章 介紹和分析了基于圖論的圖像分割方法中常用的運用NormalizeCut準則割集作為分割準則的圖像分割方法，并在把這種方法運用到閾值化的圖像分割的基礎上，分析了在該種方法中像素點間的相關性權值的計算公式的不足，提出了一種具有抗噪性的基于歸一化準則的圖像分割方法，通過實驗結(jié)果，驗證了該種圖像分割方法的優(yōu)勢和實用性。第四章 針對基于圖論的圖像分割方法中通用性的不足，提出了一種基于MinMax Cut的閾值化圖像分割方法。該方法采用MinMax Cut劃分測度作為區(qū)分目標和背景的閾值化分割準則。在描述圖像各像素間的相似性關系權值矩時，把基于圖像像素的權值矩陣換成基于灰度級的權值矩陣，大大節(jié)約了算法實現(xiàn)的復雜度和算法所需要的存儲空間度。并用類似于基因勢函數(shù)的計算公式作為圖權公式，該公式以統(tǒng)計學的形式更為全面的反映了兩像素點間的相似性，同時又避免了通過手動的形式來設置控制像素點間相似性因素的差異敏感程度參數(shù)的不足，提高了算法的通用性。通過實驗結(jié)果，驗證了本章算法的實用性。第五章 總結(jié)了論文的研究課題和所做的工作，并對下一步的研究計劃和研究前景進行了展望。 本章小結(jié)本章對圖像分割進行了概述，主要介紹了圖像分割的數(shù)學定義，需要滿足的條件，以及國內(nèi)為學者對圖像分割方法的大致分類，并對常用的圖像分割方法進行了簡單的介紹，同時也對進行圖像分割方法的發(fā)展狀況以及今后的發(fā)展趨勢進行了綜述。在此基礎上提出了本課題的研究意義。并對本論文的主要內(nèi)容和結(jié)構(gòu)安排進行了介紹。8第二章 圖論的基本理論知識 圖的基本概念及理論在數(shù)學領域，圖是離散數(shù)學的一個分支，有關圖的理論是一門實用價值很高的學科。在計算機科學領域，圖是一種特殊的數(shù)據(jù)結(jié)構(gòu)，它有著自己獨特的定義形式，也從不同的理論出發(fā)點劃分出不同種類的圖。而有關圖的劃分的理論是基于圖論的圖像分割方法的理論基礎，為圖像分割提供了一種新的理論方法。 圖的含義及表示圖是關系的一種數(shù)學表示。圖是由若干頂點和連接這些頂點的邊構(gòu)成 [21]。一般情況下，若用 G 表示一個圖的話，那么可以用非空頂點集合Vag = {v1, v2 , v3 ? ? ? vn} 和非空邊集合 Eag = {E1, E2 , E3 ? ? ? Em}組成。其中，集合 Vex 中的元素個數(shù)，即圖的頂點數(shù)，是由圖 G 的構(gòu)成來決定，稱為圖 G 的階。而邊集合 Eag 中元素的個數(shù)也是由圖 G 的構(gòu)成決定的，稱為圖 G 的規(guī)模。邊集合 Eag中的每個元素，即圖的邊都是由圖中的兩個不同的頂點組成，可以表示為Ex ∈VV j ，因此圖中邊就是連接頂點 i 和頂點 j 的弧，也可以用 VV j 來表示。 圖的分類由于出發(fā)點和目的不同，可以把圖分為不同的種類。一般情況下，人們依據(jù)連接兩頂點間的邊是否具有方向，把圖分為無向圖和有向圖。通常情況下，人們在運用圖時常常給圖中的邊賦予一定的數(shù)值，這種圖為加權圖。這些數(shù)值表示為兩頂點間的聯(lián)系。數(shù)值的大小可以表示為這種聯(lián)系的緊密程度。通常情況下這些數(shù)值又稱為圖中邊的權值。（ 1）無向圖在圖 G 中，如果連接兩個頂點間的邊是沒有方向的，那么圖 G 就稱為無向圖。也就是說，連接兩個頂點 i 和 j 的邊是無方向的，先后順序是無關的，即：VV j 和 V jVi 表示的是同一條連接兩個頂點 i 和 j 的邊，因此也可以認為組成邊的頂點偶對是無序的。在圖 G 中每個頂點都有一個度。對于無向圖來說，頂點 VX的度是指與 VX 相連接的邊的數(shù)目，一般記為 deg(VX ) ?？梢园褕D 中的無向圖表 示 為 如 下 形 式 ， G = G(Vex, Eag ) ，Vex = {v1, v2 , v3 , v4 , v5 , v6} ，Vag = {v1v2 , v1v4 , v1v6 , v2v3 , v2v4 , v3v4 , v4v5 , v5v6} 。（ 2）有向圖在圖 G 中，如果連接兩個頂點間的邊是有方向的，那么圖 G 就稱為有向圖。也就是說，連接兩個頂點 i 和