【正文】 揮著重要的作用，而在視覺系統(tǒng)中，人類在感知周圍的信息時，往往是通過自己所看到圖像來反映的，因此圖像是人們獲取外部信息的一種重要的途徑。由于計算機(jī)視覺技術(shù)的發(fā)現(xiàn)，特別是數(shù)字圖像處理方法的發(fā)展，使得人們可以通過計算機(jī)來克服這種人眼觀察下的不足，運(yùn)用計算機(jī)能夠精確的處理數(shù)據(jù)的特性來對圖像進(jìn)行處理，從而獲得較為較為理想的信息 [1]。因此圖像分割后的效果的好壞與否將會直接地影響下一步的圖像處理的結(jié)果，甚至?xí)绊懙膱D像處理后的最終結(jié)果。分割后的區(qū)域除了滿足各自的區(qū)域一致性外，還需同時滿足下面的幾個條件：1（1）區(qū)域的連通性：分割出來的圖像區(qū)域內(nèi)必須存在能夠連接任意兩個像素點(diǎn)的路徑，并且分割后的區(qū)域內(nèi)部不會存在著一些小的空洞，內(nèi)部是平整的。 圖像分割的數(shù)學(xué)定義基于上述圖像分割的條件，可以把圖像分割做如下形式化的定義 [3]：把圖像的像素點(diǎn)集合用一個有序集合 A 來表示，同時把具有相同性質(zhì)的謂詞用 H 來表示，這樣的話，就可以把 A 分割成為若干個有序非空子集 A1, A2 , A3子集要滿足如下條件：ni =1（2） Ai ∩ Aj = 246。條件（4）表明任意兩個相鄰的子區(qū)域具有某種特征上的差異性。2（1） ∪ Ai = Ai i 圖像分割的分類作為一個非常具有挑戰(zhàn)性的圖像處理技術(shù)，圖像分割的研究歷史已經(jīng)有幾十年了。基于邊緣的分割方法的基本思想就是根據(jù)不同區(qū)域間的特征不連續(xù)性特點(diǎn)來檢測出區(qū)域間的邊緣，從而實(shí)現(xiàn)圖像分割。串行邊緣檢測技術(shù)的基本原理是先是檢測出一個邊緣起始點(diǎn)，然后利用一定的相似性準(zhǔn)則來尋找與前一點(diǎn)客歸屬為同一類的邊緣點(diǎn)，這種通過根據(jù)后繼相似點(diǎn)查找同類的方法又稱之為跟蹤。并行邊緣檢測技術(shù)則是借助空域微分算子，使用其模板與圖像卷積來實(shí)現(xiàn)，這種方法可以針對每個像素同時進(jìn)行，因此能夠在很大程度上降低算法的時間復(fù)雜度。常用的邊緣修正的方法有相位編組法、啟發(fā)式連接和層次記號編組法等。閾值化分割包括單閾值分割方法和多閾值分割方法。多閾值分割則需要選擇多個閾值，把整個灰度范圍劃分成幾個段，屬于每個段內(nèi)的象素成為一類，這樣就將圖像劃分成多個灰度不同的區(qū)域。但這也導(dǎo)致了該類算法的缺點(diǎn)。（3） 基于區(qū)域的分割區(qū)域的分割法在傳統(tǒng)意義上可以分為分裂合并和區(qū)域生長兩種基本形式。和區(qū)域生長算法不同的是，區(qū)域分裂合并法則不需要先找指定的種子像素點(diǎn)，它按照某種一致性準(zhǔn)則直接進(jìn)行分裂或合并區(qū)域，當(dāng)相鄰的區(qū)域相似性一致時，通過合并運(yùn)算合并為一個大的區(qū)域，相反的，當(dāng)一個區(qū)域內(nèi)不滿足一致性原則就分裂成幾個小的區(qū)域。無論是合并運(yùn)算還是分裂運(yùn)算，都可以很好的將分割深入到像素級，因此在圖像分割的精度上有較高的保障。一些常用的距離度量準(zhǔn)則都可以作為相似性的度量標(biāo)準(zhǔn)。圖論、小波分析和小波變換、模糊理、神經(jīng)網(wǎng)絡(luò)、遺傳算法、粗糙集理論、數(shù)學(xué)形態(tài)學(xué) [1315]等以近年來發(fā)展迅速的灰色系統(tǒng)理論等數(shù)學(xué)工具的利用，為圖像分割提供了更多的選擇，并且針對不同的圖像有效地改善了分割效果。但由于該方法涉及的理論知識較多, 應(yīng)用研究也還處在初級階段, 因此該法將會成為圖像分割領(lǐng)域中一個具有挑戰(zhàn)性的研究熱點(diǎn)。造成這種局面的主要原因，主要是因?yàn)橐韵氯齻€方面[16]：（1）由于現(xiàn)實(shí)生活中，圖像的種類復(fù)雜，使得人們在研究對圖像進(jìn)行分割5時，在對算法進(jìn)行設(shè)計時，都有時針對某類圖像的，而沒有考慮其他的圖像。因此，應(yīng)該借助各種新的理論和工具來彌補(bǔ)這種不足。所以，設(shè)計一個適用性很好的圖像分割算法仍然是一個很有挑戰(zhàn)性的事情。這些新的理論知識和工具的引入，為圖像分割方法開辟了新的思路，也為圖像分割方法的研究注入了新鮮的動力和活力。這種結(jié)合后的圖像分割方法具有一定的優(yōu)勢。（3） 對特定鄰域的知識的注入和對特殊問題的解決也是圖像分割方法研究中的一個熱點(diǎn)和重點(diǎn)。為了辨識和分析目標(biāo)，才有可能對目標(biāo)進(jìn)一步利用。由于圖像分割的廣泛應(yīng)用，因此圖像在不同領(lǐng)域也有著其不同的應(yīng)用名稱，比如在在目標(biāo)檢測領(lǐng)域中的目標(biāo)輪廓技術(shù)，圖像求差和圖像區(qū)分技術(shù)等，以及在圖像識別技術(shù)中的目標(biāo)識別和目標(biāo)跟蹤等等。因此對這方面的研究有著極其重要的理論意義和現(xiàn)實(shí)意義。雖然基于圖論的圖像分割方法具有一定的優(yōu)勢，但是這類方法一般都有較高的復(fù)雜性，使得算法實(shí)時性較差，同時在區(qū)分像素點(diǎn)間的相似性時，也存在這一些問題。其次，提出了一種改進(jìn)的基于圖論的MinMax Cut 準(zhǔn)則的組合優(yōu)化算法，該算法把傳統(tǒng)的基于 MinMax Cut 準(zhǔn)則圖像分割方法，應(yīng)用到閾值圖像分割中，大大節(jié)約了算法的實(shí)現(xiàn)時間和空間，同7時也取得了較好的分割效果。第四章 針對基于圖論的圖像分割方法中通用性的不足，提出了一種基于MinMax Cut的閾值化圖像分割方法。通過實(shí)驗(yàn)結(jié)果，驗(yàn)證了本章算法的實(shí)用性。并對本論文的主要內(nèi)容和結(jié)構(gòu)安排進(jìn)行了介紹。 圖的含義及表示圖是關(guān)系的一種數(shù)學(xué)表示。而邊集合 Eag 中元素的個數(shù)也是由圖 G 的構(gòu)成決定的，稱為圖 G 的規(guī)模。通常情況下，人們在運(yùn)用圖時常常給圖中的邊賦予一定的數(shù)值，這種圖為加權(quán)圖。（ 1）無向圖在圖 G 中，如果連接兩個頂點(diǎn)間的邊是沒有方向的，那么圖 G 就稱為無向圖?？梢园褕D 中的無向圖表 示 為 如 下 形 式 ， G = G(Vex, Eag ) ，Vex = {v1, v2 , v3 , v4 , v5 , v6} ，Vag = {v1v2 , v1v4 , v1v6 , v2v3 , v2v4 , v3v4 , v4v5 , v5v6} 。即出度和入度。（ 3）加權(quán)圖從實(shí)際問題中抽象出來的圖中頂點(diǎn)和邊上往往都包含有一定的信息。對于加權(quán)圖，圖中頂點(diǎn)的度并非所有與之相連接的邊的數(shù)目，而是與之相連接所有邊上的權(quán)值之和。 G = (Vex, Eag ,Weg ) 表示一個圖，Vex 表示頂點(diǎn)集合， Eag 表示邊集合，Weg 表示權(quán)值集合， w(vi , v j ) 表示頂點(diǎn)就 i 和 j 上邊的權(quán)值。 圖與圖像關(guān)系圖是由頂點(diǎn)集和邊集組成一種拓?fù)浣Y(jié)構(gòu)圖，而圖像則是由一個一個的像素點(diǎn)組成?！皥D”是物體反射或透射的分布，“像”是人的視覺系統(tǒng)所接受的圖在人腦中所形成的印象或認(rèn)識 [23]。 圖與圖像的聯(lián)系一般情況下，圖像都是由像素點(diǎn)組成的，因此可以用 I = {v1, v2 , v3 ? ? ? vn}來表示一幅圖像 I，vi 就表示圖像中的一個像素點(diǎn)。圖的最佳劃分的關(guān)鍵是尋去最佳類的劃分，也是一種點(diǎn)對聚類的問題，同樣基于圖論的圖像分割方法的關(guān)鍵也是聚類優(yōu)化問題。這樣方法應(yīng)用在數(shù)據(jù)的聚類上也會有很好的前景。目前較為代表性的方法如以下幾個。通過實(shí)驗(yàn)驗(yàn)證了該方法的有效性，同時該方法對復(fù)雜背景下的圖像有較好的分割效果，同時在對邊緣準(zhǔn)確性、空間相關(guān)性以及圖像區(qū)域分割等方法都有較好的分割效果。通過實(shí)驗(yàn)結(jié)果驗(yàn)證了具有實(shí)時性和最優(yōu)解。（2）Average Cut（平均割）這種割集的準(zhǔn)則定義形式為 [32]： Avrcut ( A, B) =cut ( A, B) cut ( A, B)A B該割集的實(shí)現(xiàn)方式是通過求解方程 (D ? W )Z = 235。 + 1Z 標(biāo)準(zhǔn)特征系統(tǒng)來實(shí)現(xiàn)，該割集的特點(diǎn)是使得劃分后的兩部分能同時達(dá)到最小類間一致性和最大類內(nèi)相似性，但在后置處理時需要花費(fèi)大量的時間（4）Normalize Cut（歸一化割）這 種 割 集 的 定 義 形 式 是 [34] ： Nmcut ( A, B) =cut( A, B)Assoc( A,V )+cut ( A, B)Assoc(B,V )其中14+asso( A,V ) =∑u∈A,v∈Vw(u, v) ， asso( A, B) =∑u∈B,v∈Vw(u, v)該準(zhǔn)則一般是通過求解方程 (D ? W )Z = 235。（6）Isoperimetri Ratio Cut（等周割）這種割集的定義形式是 [36]： H = InfS?SVolS= Inf∑ W (eij )eij ∈?S∑ dii，其中 VolS 可以認(rèn)為是區(qū)域 S 的體積， ?S 為邊界 S 所包含的面積。而相對于一些基于區(qū)域分割方法來說，基于圖論的圖像分割方法在分割效果上不容易會產(chǎn)生過分割的現(xiàn)象。將圖論網(wǎng)絡(luò)與目標(biāo)函數(shù)功能的深層次作用的結(jié)合為圖論以及網(wǎng)絡(luò)理論在圖像處理中的應(yīng)用提供了極好的實(shí)踐根據(jù) [38]基于圖論的圖像方法的首要解決的問題就是如何把圖與圖像之間相對應(yīng)，從而使得圖劃分的理論應(yīng)用到圖像中來?；趫D論的圖像分割方法可以通過選擇合適的劃分準(zhǔn)則和設(shè)置合適的相關(guān)性關(guān)系公式，使得在處理全局和局部分割時取得一定的優(yōu)勢。（ 3）適用范圍較廣基于圖論的圖像分割方法中對聚類和譜分割的運(yùn)用和結(jié)合，使得這種方法的應(yīng)用范圍越來越廣泛，適應(yīng)性也越來越強(qiáng)。尤其是在單純的使用這種分割方法時，這種無法很好的區(qū)分互相很接近的數(shù)據(jù)類的缺陷就會很明顯的表現(xiàn)出，同時算法的實(shí)時性也不好。并且當(dāng)圖像的尺寸越大時，這種計算規(guī)模和存儲規(guī)模也越大，從而使得算法的速度也就很慢，這也是限制該方法在實(shí)際應(yīng)用中效率不高的主要原因。（ 2）對圖像信息間有效的區(qū)分能力有待于提高基于圖論的圖像分割方法在實(shí)現(xiàn)最優(yōu)劃分實(shí)現(xiàn)像素點(diǎn)間或區(qū)域間的聚類時，一般都是把這些像素點(diǎn)或區(qū)域間的連接特征作為聚類時的主要依據(jù)，這就導(dǎo)致了這些數(shù)據(jù)類間相互關(guān)系較為接近時，無法區(qū)分出其間的相似性，或者這種區(qū)分能力不夠清楚。因此如何優(yōu)化割集和權(quán)值矩陣計算公式是基于圖論的圖像分割方法的一個重要方向。因此如何解決相似性計算公式的通用性，也是基于圖論的圖像分割方法一個研究方向。該方法采用 Normalized Cut 準(zhǔn)則劃分測度作為劃分目標(biāo)和背景的閾值分割準(zhǔn)則，采用基于灰度值的權(quán)值矩陣代替基于圖像像素個數(shù)的權(quán)值矩陣來描述像素之間的關(guān)聯(lián)，把基于圖論的圖像分割方法與圖像的閾值化分割方法進(jìn)行了有效的結(jié)合，大大節(jié)約了算法的時間和存儲空間；并在圖權(quán)計算中，增加了像素點(diǎn)與其鄰域的空間相關(guān)信息，以提高算法的抗噪性。因此能把兩者進(jìn)行有效的結(jié)合，能很好的來彌補(bǔ)單純的基于圖論的圖像分割方法的不足。該類方法簡單易行而深受廣大學(xué)者的關(guān)注，但是能夠自動選擇最佳閾值仍是現(xiàn)在面臨的難題。這種新型的圖像分割方法的基本原理是把圖像映射為一個帶權(quán)的無向圖，而圖中的節(jié)點(diǎn)對應(yīng)著圖像中的像素或者圖像區(qū)域，權(quán)值的大小表示兩點(diǎn)間的相關(guān)性。這種新的圖像分割方法通過避免復(fù)雜的特征系統(tǒng)求解的問題，從而減少了算法的計算復(fù)雜度和所需的存儲空間，并且還取得了較好的分割效果。 基于 Normalized Cut 準(zhǔn)則的圖像分割方法基于 Normalized Cut 準(zhǔn)則的圖像分割方法是一種典型的基于圖論的圖像分割方法?？梢詫Ⅻc(diǎn)集 V（整個圖）分成兩個獨(dú)立的子集（子圖）A 和B，其中 A=VB，點(diǎn)集 A 和 B 之間的分離度是指移去連接 A 和 B 中所有節(jié)點(diǎn)的邊所付出的代價，也稱其為劃分（cut），即：cut( A, B) =∑u∈A,v∈Bw(u, v)()為能夠得到最優(yōu)分割集，采用 Shi 和 Malik 等人提出的 Normalized Cut準(zhǔn)則準(zhǔn)則來作為描述兩類間的分離度，該準(zhǔn)則能有效的克服劃分孤立點(diǎn)的問題[44]，其定義為：Ncut( A, B) =cut ( A, B)asso( A,V )+cut ( A, B)asso(B,V )()其中 asso( A,V ) =∑u∈A,v∈Vw(u, v) 是 A 中的節(jié)點(diǎn)與圖中所有節(jié)點(diǎn)的連接權(quán)值之和。而W是一個對稱矩陣。同時也可對分割得到的子圖采用遞歸算法以相同的方式做進(jìn)一步的劃分，直到得到滿意的結(jié)果為止。K={0，1，2，…，L1}表示圖像所有灰度的集合，L是圖像的灰度級。其對應(yīng)的圖G=（V，E）則可劃分為V={A，B}，可以把A和B分別表示為：tA = ∪Vii =0B =，L?1∪ Vii =t +1，i ∈ K()20式（ ）可以轉(zhuǎn)換為Cut(A,B) =∑u∈A,v∈Bw(u, v)同理可以得到t L?1i =0 j =t +1 u∈Vi v∈V j()t L?1i =0 j =0∑ ∑ w(u, v) ]u∈Vi v∈V j()Asso(B,V ) =L?1 L?1i =t +1 j =0 u∈Vi v∈V j()通過構(gòu)建一個對稱矩陣M[44]，通過M矩陣可以很容易求 Ncut ( A, B) ，則基于歸一