【正文】 B) =∑vi ∈A,v j ∈Bw(vi , v j )通過樹圖縮減的方式來實現(xiàn)該割集的圖像分割，這是基于圖論的圖像分割方法中最簡單也是最常見的一種割集準(zhǔn)則。這種方法通過將圖像映射為帶權(quán)的無向圖，再把圖像的像素點看作為圖中的頂點，運用圖中的最佳割集從而得到圖像的一種最佳分割效果。把 G 劃分為 A 和 B 兩部分的代價函數(shù)可以記為：cut( A, B) =∑vi ∈A,v j ∈Bw(vi , v j )圖 G 的最優(yōu)二元劃分就是使得 cut( A, B) 值最小的劃分 A 和 B。也就是說，連接兩個頂點 i 和 j 的邊是有方向的，組成邊的頂點偶對先后是有順序，即： G = G(Vex, Eag ) 和 V jVi 表示的是兩條連接兩個頂點 i 和 j 不同的邊。一般情況下，若用 G 表示一個圖的話，那么可以用非空頂點集合Vag = {v1, v2 , v3 ? ? ? vn} 和非空邊集合 Eag = {E1, E2 , E3 ? ? ? Em}組成。第二章 介紹了圖的基本概念以及圖劃分的理論、圖與圖像間的相互對應(yīng)關(guān)系，從而引出了基于圖論的圖像分割方法中的一些基本方法、常用的割集準(zhǔn)則，以及基于圖論的圖像分割方法的研究進(jìn)展、特點和存在的不足，為下文的基于圖論的圖像分割方法的改進(jìn)提供了理論基礎(chǔ)。這里特性可以是像素的灰度、顏色、紋理等，預(yù)先定義的目標(biāo)可以對應(yīng)單個區(qū)域，也可以對應(yīng)多個區(qū)域。但對新知識新理論的借助，對這要技術(shù)上的克服不是沒有一定的可能的，而且這也是圖像分割方法的發(fā)展的一個必然趨勢。該方法基本思想是將圖像映射為帶權(quán)無向圖, 把圖像的像素點視作節(jié)點, 利用最小剪切準(zhǔn)則得到圖像的一個最佳分割。區(qū)域生長算法的基本思想是先在每個待分割的區(qū)域中找一個或多個種子像素點作為生長的起點，然后根據(jù)某種相似性準(zhǔn)則來進(jìn)行區(qū)域增長，直至沒有可以歸并的點為止。（2） 基于閾值的分割閾值化圖像分割方法是圖像分割方法中最為常見也是最簡單的一種分割方法。通過對國內(nèi)外文獻(xiàn)的研究，可以把圖像分割的方法歸納為以下五類：（1） 基于邊緣的分割邊緣在圖像視覺中具有非常重要作用。圖像分割的重要作用如圖 所示 [2]。pepper 噪聲參數(shù)下三種方法的信噪比........................... 25表 image 在不同 saltamp。基于圖論的圖像分割方法是圖像分割領(lǐng)域中的一個研究熱點，該類方法將圖像映射為帶權(quán)無向圖，把像素視作節(jié)點 , 利用最小割集準(zhǔn)則得到圖像的最佳分割，會有一些問題不可避免的出現(xiàn)。關(guān)鍵詞：圖劃分；圖像分割；Normalized Cut；MinMax CutResearch of Threshold Image Segmentation Based on GraphTheoryABSTRACTAs one of the most important and typical problems in image processing andputer vision fields, image segmentation is the basic premise in image visionanalysis and pattern segmentation based on graph theory is aresearch focus in image segmentation fields,this approaches are the formation of aweighted graph,where each vertex corresponds to an image pixel,the bestsegmentation of the image can be obtained by minimal cut sets,and achieve goodresults of image some problems and deficiencies may be found inthe process of implementation, if we just simply use this approaches. other theoriesare bined with this approaches to get better effectiveness.Aiming at the problem exists in the image segmentations based on graphtheory, the thesis bines the Normalized Cut standard and MinMax Cut standardwith threshold image segmentation, and improves the putational formula whichused to measure the similarity between the pixels to reach a well effectiveness. Themain works can be organized as follows:Part one: To make sure the feasibility of the bination of the two methods, thetheories and progress of image segmentation based on graph theory and thresholdsegmentation were researched.Part two: Aiming at the problem in the process of the image segmentationsbased on graph theory, a new algorithm is presented to resist noise in the process ofimage segmentation. Normalized Cut standard is adopted as the standard of thedivision between the objective and background, and the relevant space informationbetween pixels and its neighborhood are used to improve the noise immunity. Theexperimental results show that the method has well noise immunity.Part three: Aiming at the inadequate of monality in the image segmentationsbased on graph theory, a new method based on MinMax Cut threshold imagesegmentation is proposed. This method adopts Min Max dividing measure as thethreshold segmentation rule to distinguish the target and background. In describingthe weight matrix of similarity between the pixel values of each image,we useweight matrix based on grey level to replace that based on image pixels so that thealgorithm plexity and the storage space degrees are greatly saved. By using theputational formula of the potential function as the graph weight matrices, theformula can reflect the similarity between pixels better in statistics. Meanwhile, itavoids the defect by the manual forms to set the control of some similaritiesbetween the degree of sensitivity parameters, and improves the monality of thealgorithm. The experimental results show that the algorithm has been betterpractical.Key words: Graph Cut； image segmentation； Normalized Cut； MinMax Cut插圖清單圖 圖像分割的作用 ................................................................................................. 1圖 圖 圖 無向圖 ............................................................................................................. 10有向圖 ............................................................................................................. 10加權(quán)圖 ............................................................................................................. 11圖 圖像分割與圖的分割間的關(guān)系 ....................................................................... 12圖 cameraman 圖片及其分割結(jié)果...................................................................... 23圖 image 圖片及其分割結(jié)果 ................................................................................. 23圖 加了 saltamp。這是因為通過對圖像的分割處理后，就可以把人們感興趣的圖像目標(biāo)區(qū)域從占據(jù)不同區(qū)域的背景區(qū)域中提取出來，從而為下一步的圖像處理奠定基礎(chǔ)。這就使得圖像的分割只是針對具體的應(yīng)用，而無法用一種通用的方法來解決。通常情況下在利用上述邊緣檢測方法的同時，需要進(jìn)一步的對邊緣進(jìn)行修正，如虛假邊緣剔除、去除毛刺和邊緣連通等。目前較常用的閾值算法包括：基于灰度直方圖的波峰與波谷法、最大熵法、最小誤差法、模糊集法、最大類間方差法等。（5） 結(jié)合其他特定理論的分割方法近年來，大量學(xué)者致力于將新方法、新概念應(yīng)用于圖像分割中，在圖像分割方面，結(jié)合特定理論的圖像分割方法已取得了較好的應(yīng)用效果。到目前為止，我們還沒有一個標(biāo)準(zhǔn)化、系統(tǒng)化的認(rèn)識，同時也缺乏對這要知識的認(rèn)識和了解。這些6部分常稱為目標(biāo)或前景(其他部分稱為背景).它們一般對應(yīng)圖像中特定的、具有獨特性質(zhì)的區(qū)域。通過對基于圖論的組合優(yōu)化算法的研究和改進(jìn)，提出了一種改進(jìn)的基于圖論的 Normalized Cut 準(zhǔn)則的組合優(yōu)化算法，并應(yīng)用到閾值圖像的分割中，該算法的實時性上和分割的效果上都取得了很好的成效，同時還具有較好的抑制噪聲的能力。而有關(guān)圖的劃分的理論是基于圖論的圖像分割方法的理論基礎(chǔ)，為圖像分割提供了一種新的理論方法。對于無向圖來說，頂點 VX的度是指與 VX 相連接的邊的數(shù)目，一般記為 deg(VX ) 。如果用頂點代表事物，而連接兩頂點的邊則來表示相應(yīng)這兩個事物直接的一種關(guān)系權(quán)重。圖 可以更好的把圖與圖像對應(yīng)起來 基于圖論的圖像分割基于圖論的圖像分割方法的基本思想就是把圖像的圖像的結(jié)構(gòu)轉(zhuǎn)換為圖的結(jié)構(gòu)，把能夠求出一個圖的最佳劃分的理論知識運用到圖像的分割中來，從而獲取較為理想圖像分割效果。同年，劉丙濤等人 [29]提出了一種基于圖論的 SAR 圖像分割新方法，該方法運用 GornoryHu 算法得到對應(yīng)的等價樹和多尺度結(jié)構(gòu)對圖像進(jìn)行最優(yōu)劃分，從而來對圖像進(jìn)行分割。相對于較為簡單的閾值分割方法來說，基于圖論的圖像分割方法在局部處理和抑制噪聲能力上有較為明顯的優(yōu)勢。 基于圖論的圖像分割方法的缺陷不足基于圖論的圖像分割方法的雖然具有較好的分割效果和應(yīng)用前景，但是這種分割方法還是存在著一定的缺陷和不足。如果想達(dá)到理想的分割效果，就必須人為的來更改這些參數(shù)的值。 基于圖論的圖像分割與閾值化分割結(jié)合的優(yōu)勢作為一種新型的理論工具，圖劃分理論被應(yīng)用到圖像分割中來，從而形成一種基于圖論的圖像分割方法。