【正文】 4） H ( A ∪ Aj ) = False, ?i, j, i ≠ j且A與Aj相鄰（5） ?Ai都是連通的區(qū)域條件（1）表明所有分割的子區(qū)域組成了整幅圖像，也就是說圖像中的任意一個(gè)像素點(diǎn)都可以在某個(gè)子區(qū)域中找到。人們通過建立不同的模型，運(yùn)用各種數(shù)學(xué)理論和工具，從圖像自身的特征出發(fā)，形成了錯(cuò)綜復(fù)雜的針對(duì)灰度圖像和彩色圖像的分割算法 [46]。根據(jù)跟蹤的方法不同，又可以這中方法分為光柵跟蹤、輪廓跟蹤和全向跟蹤。同樣利用邊緣修正并行邊緣檢測(cè)在算法實(shí)現(xiàn)方面也要付出相當(dāng)大的代價(jià)。顯而易見，單閾值分割是多閾值分割的一種特例。區(qū)域分裂合并法的前提是從整個(gè)圖像出發(fā)，從而逐漸的分裂或合并所形成的分割結(jié)果 ；區(qū)域生長(zhǎng)法則是從單像素出發(fā)，同時(shí)考慮到像素及其空間鄰域像素之間的關(guān)系，并逐漸合并從而形成所需要的分割結(jié)果 [9]?；趨^(qū)域的方法的缺點(diǎn)則是：由于物體的輪廓線經(jīng)常是任意形狀的，因此在分割的速度上都較慢。基于圖論的圖像分割技術(shù)是近年來國內(nèi)外在圖像分割領(lǐng)域的一個(gè)新的研究熱點(diǎn)。即在算法的本身就具有一定的針對(duì)性?？v觀圖像分割技術(shù)的發(fā)展歷程，雖然在圖像分割技術(shù)上來說，很難得到一個(gè)非常理想的圖像分割方法。因?yàn)閱我坏膱D像分割算法都具有一定的針對(duì)性和局限性。圖像分割就是指把圖像分成各具特性的區(qū)域并提取出感興趣目標(biāo)的技術(shù)和過程?；趫D論的圖像分割方法是近年來一個(gè)研究熱點(diǎn)，該方法把圖像看作是一個(gè)帶權(quán)圖，圖中的節(jié)點(diǎn)對(duì)應(yīng)著圖像的像素，權(quán)值的大小表示兩點(diǎn)間的相關(guān)性。本論文的結(jié)構(gòu)安排如下:第一章 在閱讀大量的國內(nèi)外文獻(xiàn)基礎(chǔ)上，研究了有關(guān)圖像分割的基本理論，深入地探討了有關(guān)圖像分割的方法，總結(jié)了圖像分割的含義，分類及發(fā)展現(xiàn)狀和今后的趨勢(shì)。第五章 總結(jié)了論文的研究課題和所做的工作，并對(duì)下一步的研究計(jì)劃和研究前景進(jìn)行了展望。圖是由若干頂點(diǎn)和連接這些頂點(diǎn)的邊構(gòu)成 [21]。這些數(shù)值表示為兩頂點(diǎn)間的聯(lián)系。（ 2）有向圖在圖 G 中，如果連接兩個(gè)頂點(diǎn)間的邊是有方向的，那么圖 G 就稱為有向圖。這些信息就可以體現(xiàn)在賦予圖中邊上權(quán)值，一般表現(xiàn)為兩頂點(diǎn)間的聯(lián)系的緊密性。把圖 G 劃分為 A、 B 兩部分就是將連接 A 和 B 部分間的邊移去，并且 A 和 B 間滿足： A ∩ B = ?, A ∪ B = Vex ，A 和 B 之間的相異度是指所有移走的邊的權(quán)值總和。一幅圖像中包含有大量的信息，比如灰度圖像中圖像的灰度，彩色圖像中圖像的色彩，還有圖像的紋理、邊緣以及圖像中目標(biāo)的形狀特征等。 基于圖論的圖像分割方法研究進(jìn)展基于圖論的圖像分割方法是近幾年來國內(nèi)外在圖像分割領(lǐng)域的一個(gè)新研究熱點(diǎn)問題。2003 年，Pavan 等人 [26]提出一種結(jié)合圖論和聚類理論的新的圖像分割方法，在該方法中，作者將聚類直覺觀念和圖中節(jié)點(diǎn)顯性集間的關(guān)系進(jìn)行了類似對(duì)比，通過節(jié)點(diǎn)顯性集在邊緣帶權(quán)圖中的推廣，建立了一種標(biāo)準(zhǔn)單形和顯性集的二次極值關(guān)系，使得該方法能夠較好的應(yīng)用于局部交互的計(jì)算單元，并具有一些生物學(xué)的優(yōu)勢(shì)。同年，李小斌等人 [30]也提出了一種新的加權(quán)割的圖像分割方法，作者通過數(shù)學(xué)理論來證明了這種加權(quán)割模型的的特點(diǎn)，使得該方法能夠同時(shí)達(dá)到類內(nèi)最小一致性和類間最大相異性。 Z 標(biāo)準(zhǔn)特征系統(tǒng)來實(shí)現(xiàn)，該割集的特點(diǎn)是能有效的克服劃分孤立點(diǎn)的問題，但當(dāng)類間重疊較大時(shí)容易出現(xiàn)歪斜劃分。雖然在算法在實(shí)現(xiàn)的速度上，沒有其他一些簡(jiǎn)單的算法快，但是其應(yīng)用的范圍比較廣。（ 2）智能化的分割 [39]基于圖論的圖像分割方法與計(jì)算機(jī)視覺中的空間變量的結(jié)合體現(xiàn)了在這種方法在進(jìn)行圖像分割時(shí)運(yùn)算量的智能化的降低，這也是基于圖論的圖像分割方法的又一特點(diǎn)。因此有必要針對(duì)這些缺陷不足對(duì)基于圖論的圖像分割方法做進(jìn)一步的改善，使得這種圖像分割方法能具有更好的應(yīng)用前景。因此在單純的基于圖論的圖像分割方法中，描述像素點(diǎn)間的相互關(guān)系的連接權(quán)值矩陣的取值是否恰當(dāng)，以及能否較好的體現(xiàn)出圖像信息間的特征，都將嚴(yán)重影響圖像的分割效果。 本章小結(jié)本章主要介紹了圖的基本概念以及圖劃分的理論、圖與圖像間的相互對(duì)應(yīng)關(guān)系，從而引出了基于圖論的圖像分割方法中的一些基本方法、常用的割集準(zhǔn)則，以及基于圖論的圖像分割方法的研究進(jìn)展、特點(diǎn)和存在的不足，為下文的基于圖論的圖像分割方法的改進(jìn)提供了理論基礎(chǔ)。 閾值化分割在基于圖論的圖像分割方法中的應(yīng)用人們?cè)谔幚韴D像時(shí)，尤其是在處理灰度圖像時(shí)，人們發(fā)現(xiàn)圖像中人們感興趣部分(目標(biāo)圖像)與其周圍的部分(背景圖像)在灰度值上存在著很大的差異。通過對(duì)能量函數(shù)進(jìn)行組合優(yōu)化來實(shí)現(xiàn)對(duì)像素18的合理分類。這種分割方法把 Normalized Cut 準(zhǔn)則作為圖劃分的依據(jù)，同時(shí)把Normalized Cut 作為衡量圖像分割最優(yōu)化的能量函數(shù)。其中的元素為 w(i, j) ， 235。令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中的每個(gè)像素點(diǎn)看作無向圖的一個(gè)節(jié)點(diǎn)，那么就可以用一條邊將每對(duì)節(jié)點(diǎn)連接起來，并為每個(gè)邊賦予權(quán)值，該權(quán)值反映了這兩個(gè)像素點(diǎn)的相關(guān)性。 最佳分割求解的改進(jìn)若 I = [ f ( x, y)]M N 表示大小為 M N 的數(shù)字圖像，V={（i，j）：i=1，2，…，M；j=1，2，…，N}，表示圖像中個(gè)像素點(diǎn)的位置集合，M和N分別是圖像的高度和寬度。 X19()??在公式（ ）中， D是一個(gè)對(duì)角矩陣，對(duì)角線上的元素為 di = ∑ w(i, j) ，矩陣j的大小為 N N 。該方法采用Normalized Cut劃分測(cè)度作為劃分目標(biāo)和背景的閾值圖像分割準(zhǔn)則，采用基于灰度值的權(quán)值矩陣代替基于圖像像素個(gè)數(shù)的權(quán)值矩陣來描述像素之間的關(guān)聯(lián)，并在圖權(quán)計(jì)算中，增加了該像素點(diǎn)與其鄰域的空間相關(guān)信息，更全面地反映了兩相鄰像素間的相關(guān)性，從而提高了算法的抗噪能力。 基于圖論的圖像分割與閾值化分割結(jié)合的優(yōu)勢(shì)作為一種新型的理論工具，圖劃分理論被應(yīng)用到圖像分割中來，從而形成一種基于圖論的圖像分割方法。而閾值化圖像分割方法是一種非常簡(jiǎn)單的圖像分割方法，并且在圖像分割領(lǐng)域也有很長(zhǎng)的研究。如果想達(dá)到理想的分割效果，就必須人為的來更改這些參數(shù)的值。本文也在這個(gè)基礎(chǔ)上，實(shí)現(xiàn)了基于Normalize Cut 準(zhǔn)則和 MinMax Cut 準(zhǔn)則的圖像分割方法的改進(jìn)。 基于圖論的圖像分割方法的缺陷不足基于圖論的圖像分割方法的雖然具有較好的分割效果和應(yīng)用前景，但是這種分割方法還是存在著一定的缺陷和不足。雖然閾值法圖像分割簡(jiǎn)單，但不易得到圖像中局部信息，而基于區(qū)域的圖像分割方法則容易產(chǎn)生過分割，也不能很好的把握全局信息。相對(duì)于較為簡(jiǎn)單的閾值分割方法來說，基于圖論的圖像分割方法在局部處理和抑制噪聲能力上有較為明顯的優(yōu)勢(shì)。235。同年，劉丙濤等人 [29]提出了一種基于圖論的 SAR 圖像分割新方法，該方法運(yùn)用 GornoryHu 算法得到對(duì)應(yīng)的等價(jià)樹和多尺度結(jié)構(gòu)對(duì)圖像進(jìn)行最優(yōu)劃分，從而來對(duì)圖像進(jìn)行分割。根據(jù)圖的某種特定劃分建立相應(yīng)的能量函數(shù)，該能量函數(shù)的最小值即對(duì)應(yīng)圖像的一個(gè)最佳分組 [25]。圖 可以更好的把圖與圖像對(duì)應(yīng)起來 基于圖論的圖像分割基于圖論的圖像分割方法的基本思想就是把圖像的圖像的結(jié)構(gòu)轉(zhuǎn)換為圖的結(jié)構(gòu)，把能夠求出一個(gè)圖的最佳劃分的理論知識(shí)運(yùn)用到圖像的分割中來，從而獲取較為理想圖像分割效果。11w8w7圖像的分割圖像圖像的像素圖像的相鄰像素相鄰像素間的相似度圖的分割圖 G={V,E}圖的頂點(diǎn)：V圖的邊：E圖的邊權(quán)值：W圖 圖像分割與圖的分割間的關(guān)系 圖像的描述圖像是人類視覺的基礎(chǔ)，是自然景物的客觀反映，是人類認(rèn)識(shí)世界和人類本身的重要源泉。如果用頂點(diǎn)代表事物，而連接兩頂點(diǎn)的邊則來表示相應(yīng)這兩個(gè)事物直接的一種關(guān)系權(quán)重。如圖 所示的有向圖表示為如下形式，G = G(Vex, Eag )，其中Vex = {v1, v2 , v3 , v4 , v5 , v6}，Vag = {v1v2 , v1v6 , v2v3 , v4v3 , v4v5 , v6v5 , v6v1}。對(duì)于無向圖來說，頂點(diǎn) VX的度是指與 VX 相連接的邊的數(shù)目，一般記為 deg(VX ) 。一般情況下，人們依據(jù)連接兩頂點(diǎn)間的邊是否具有方向，把圖分為無向圖和有向圖。而有關(guān)圖的劃分的理論是基于圖論的圖像分割方法的理論基礎(chǔ)，為圖像分割提供了一種新的理論方法。并用類似于基因勢(shì)函數(shù)的計(jì)算公式作為圖權(quán)公式，該公式以統(tǒng)計(jì)學(xué)的形式更為全面的反映了兩像素點(diǎn)間的相似性，同時(shí)又避免了通過手動(dòng)的形式來設(shè)置控制像素點(diǎn)間相似性因素的差異敏感程度參數(shù)的不足，提高了算法的通用性。通過對(duì)基于圖論的組合優(yōu)化算法的研究和改進(jìn)，提出了一種改進(jìn)的基于圖論的 Normalized Cut 準(zhǔn)則的組合優(yōu)化算法，并應(yīng)用到閾值圖像的分割中，該算法的實(shí)時(shí)性上和分割的效果上都取得了很好的成效，同時(shí)還具有較好的抑制噪聲的能力。從上世紀(jì) 50 年代，人們就可以研究圖像的分割方法，隨著研究的深入和計(jì)算機(jī)科學(xué)技術(shù)的發(fā)展，以及與新理論和新工具的借鑒和結(jié)合，到目前為止，專家學(xué)者們以及提出了上千種各種類型圖像分割方法，而且這方面的研究仍在積極進(jìn)行。這些6部分常稱為目標(biāo)或前景(其他部分稱為背景).它們一般對(duì)應(yīng)圖像中特定的、具有獨(dú)特性質(zhì)的區(qū)域。目前的圖像分割方法都中對(duì)多種圖像分割方法的結(jié)合。到目前為止，我們還沒有一個(gè)標(biāo)準(zhǔn)化、系統(tǒng)化的認(rèn)識(shí)，同時(shí)也缺乏對(duì)這要知識(shí)的認(rèn)識(shí)和了解。這就使得人們?cè)谶M(jìn)行圖像分割時(shí)，只能針對(duì)某類圖像進(jìn)行分割，沒不能對(duì)所有的圖像進(jìn)行分割。（5） 結(jié)合其他特定理論的分割方法近年來，大量學(xué)者致力于將新方法、新概念應(yīng)用于圖像分割中，在圖像分割方面，結(jié)合特定理論的圖像分割方法已取得了較好的應(yīng)用效果。基于區(qū)域的分割方法在圖像的空間關(guān)系上，不僅考慮到像素的相似性，而且還考慮到空間區(qū)域上的鄰接性，因此可以有效地消除噪聲的4干擾，在算法上有很強(qiáng)的魯棒性。目前較常用的閾值算法包括：基于灰度直方圖的波峰與波谷法、最大熵法、最小誤差法、模糊集法、最大類間方差法等。目前常用的確定閾值的方法有：P參數(shù)法，判別分析狀態(tài)法。通常情況下在利用上述邊緣檢測(cè)方法的同時(shí)，需要進(jìn)一步的對(duì)邊緣進(jìn)行修正，如虛假邊緣剔除、去除毛刺和邊緣連通等。根據(jù)執(zhí)行方式的不同，可以把該類方法分為串行邊緣檢測(cè)和并行邊緣檢測(cè)。這就使得圖像的分割只是針對(duì)具體的應(yīng)用，而無法用一種通用的方法來解決。（4）區(qū)域邊界的齊整性：每個(gè)分割后的區(qū)域邊界必須保證在空間位置的準(zhǔn)確性，從而使得分割后的區(qū)域邊界齊整。這是因?yàn)橥ㄟ^對(duì)圖像的分割處理后，就可以把人們感興趣的圖像目標(biāo)區(qū)域從占據(jù)不同區(qū)域的背景區(qū)域中提取出來，從而為下一步的圖像處理奠定基礎(chǔ)。本人授權(quán)合肥工業(yè)大學(xué)可以將學(xué)位論文的全部或部分論文內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存、匯編學(xué)位論文。關(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. ot