【正文】 同時也可對分割得到的子圖采用遞歸算法以相同的方式做進(jìn)一步的劃分，直到得到滿意的結(jié)果為止。這種新的圖像分割方法通過避免復(fù)雜的特征系統(tǒng)求解的問題，從而減少了算法的計(jì)算復(fù)雜度和所需的存儲空間，并且還取得了較好的分割效果。該方法采用 Normalized Cut 準(zhǔn)則劃分測度作為劃分目標(biāo)和背景的閾值分割準(zhǔn)則，采用基于灰度值的權(quán)值矩陣代替基于圖像像素個數(shù)的權(quán)值矩陣來描述像素之間的關(guān)聯(lián)，把基于圖論的圖像分割方法與圖像的閾值化分割方法進(jìn)行了有效的結(jié)合，大大節(jié)約了算法的時間和存儲空間；并在圖權(quán)計(jì)算中，增加了像素點(diǎn)與其鄰域的空間相關(guān)信息，以提高算法的抗噪性。并且當(dāng)圖像的尺寸越大時，這種計(jì)算規(guī)模和存儲規(guī)模也越大，從而使得算法的速度也就很慢，這也是限制該方法在實(shí)際應(yīng)用中效率不高的主要原因。將圖論網(wǎng)絡(luò)與目標(biāo)函數(shù)功能的深層次作用的結(jié)合為圖論以及網(wǎng)絡(luò)理論在圖像處理中的應(yīng)用提供了極好的實(shí)踐根據(jù) [38]基于圖論的圖像方法的首要解決的問題就是如何把圖與圖像之間相對應(yīng)，從而使得圖劃分的理論應(yīng)用到圖像中來。（2）Average Cut（平均割）這種割集的準(zhǔn)則定義形式為 [32]： Avrcut ( A, B) =cut ( A, B) cut ( A, B)A B該割集的實(shí)現(xiàn)方式是通過求解方程 (D ? W )Z = 235。這樣方法應(yīng)用在數(shù)據(jù)的聚類上也會有很好的前景。 圖與圖像關(guān)系圖是由頂點(diǎn)集和邊集組成一種拓?fù)浣Y(jié)構(gòu)圖，而圖像則是由一個一個的像素點(diǎn)組成。即出度和入度。而邊集合 Eag 中元素的個數(shù)也是由圖 G 的構(gòu)成決定的，稱為圖 G 的規(guī)模。第四章 針對基于圖論的圖像分割方法中通用性的不足，提出了一種基于MinMax Cut的閾值化圖像分割方法。由于圖像分割的廣泛應(yīng)用，因此圖像在不同領(lǐng)域也有著其不同的應(yīng)用名稱，比如在在目標(biāo)檢測領(lǐng)域中的目標(biāo)輪廓技術(shù)，圖像求差和圖像區(qū)分技術(shù)等，以及在圖像識別技術(shù)中的目標(biāo)識別和目標(biāo)跟蹤等等。這些新的理論知識和工具的引入，為圖像分割方法開辟了新的思路，也為圖像分割方法的研究注入了新鮮的動力和活力。但由于該方法涉及的理論知識較多, 應(yīng)用研究也還處在初級階段, 因此該法將會成為圖像分割領(lǐng)域中一個具有挑戰(zhàn)性的研究熱點(diǎn)。和區(qū)域生長算法不同的是，區(qū)域分裂合并法則不需要先找指定的種子像素點(diǎn)，它按照某種一致性準(zhǔn)則直接進(jìn)行分裂或合并區(qū)域，當(dāng)相鄰的區(qū)域相似性一致時，通過合并運(yùn)算合并為一個大的區(qū)域，相反的，當(dāng)一個區(qū)域內(nèi)不滿足一致性原則就分裂成幾個小的區(qū)域。閾值化分割包括單閾值分割方法和多閾值分割方法?；谶吘壍姆指罘椒ǖ幕舅枷刖褪歉鶕?jù)不同區(qū)域間的特征不連續(xù)性特點(diǎn)來檢測出區(qū)域間的邊緣，從而實(shí)現(xiàn)圖像分割。分割后的區(qū)域除了滿足各自的區(qū)域一致性外，還需同時滿足下面的幾個條件：1（1）區(qū)域的連通性：分割出來的圖像區(qū)域內(nèi)必須存在能夠連接任意兩個像素點(diǎn)的路徑，并且分割后的區(qū)域內(nèi)部不會存在著一些小的空洞，內(nèi)部是平整的。據(jù)我所知，除了文中特別加以標(biāo)志和致謝的地方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果，也不包含為獲得合肥工業(yè)大學(xué)或其他教育機(jī)構(gòu)的學(xué)位或證書而使用過的材料。因此需要結(jié)合其他的理論和知識對其進(jìn)行改進(jìn)，以便使得這類圖像分割方法具有更好的實(shí)效性。并用類似于基因勢函數(shù)的計(jì)算公式作為圖權(quán)公式，該公式以統(tǒng)計(jì)學(xué)的形式更為全面的反映了兩像素點(diǎn)間的相似性，同時又避免了通過手動的形式來設(shè)置控制像素點(diǎn)間相似性因素的差異敏感程度參數(shù)的不足，提高了算法的通用性。如今，基于計(jì)算機(jī)視覺的數(shù)字圖像處理方法已在許多生活和生產(chǎn)領(lǐng)域得到廣泛的應(yīng)用。條件（5）表明任意一個子區(qū)域內(nèi)的像素點(diǎn)之間的連通性。目前較為常見并行邊緣檢測方法的模板算子有 LOG 算子、Roberts 算子、Laplacian 算子、Prewitt 算子、Sobel 算子等。也就是算法的適用范圍較小，并且不容易確定出最佳的閾值，從而會造成圖像的錯誤分割，而且該算法的抗噪性也不好。聚類分割中典型的算法有模糊C均值算法 [10] 、K均值算法 [11]、分層聚類方法 [12] 和期望最大化等。同時，在面對數(shù)量龐大，各式各樣的圖像庫，我們還要主要圖像算法的實(shí)時性，因此對圖像分割算法的研究，仍然有一定的挑戰(zhàn)性。人們對圖像分割方法的研究不再局限于圖像分割處理技術(shù)的方面，與其他領(lǐng)域的圖像處理的結(jié)合將會成為圖像分割技術(shù)的另一個研究熱點(diǎn)。因此有必要把基于圖論的圖像分割方法與其他的有關(guān)圖像處理的理論和知識進(jìn)行有效的結(jié)合，以便取得更好的圖像分割效果。8第二章 圖論的基本理論知識 圖的基本概念及理論在數(shù)學(xué)領(lǐng)域，圖是離散數(shù)學(xué)的一個分支，有關(guān)圖的理論是一門實(shí)用價值很高的學(xué)科。也就是說，連接兩個頂點(diǎn) i 和 j 的邊是無方向的，先后順序是無關(guān)的，即：VV j 和 V jVi 表示的是同一條連接兩個頂點(diǎn) i 和 j 的邊，因此也可以認(rèn)為組成邊的頂點(diǎn)偶對是無序的。如圖 所示的有向圖表示為如下形式， G = G(Vex, Eag ,Weg ) ，其中Vex = {v1, v2 , v3 , v4 , v5 , v6}, Eag = {v1v2 , v2v3 , v3v4 , v4v5 , v5v6 , v6v1, v2v5 , v2v6}，Weg = {w1, w2 , w3 , w4 , w5 , w6 , w7 , w8}。如果把組成圖像的像素點(diǎn)看作是圖的頂點(diǎn)的話，那么就可以把圖像轉(zhuǎn)換一種特殊的圖的結(jié)構(gòu)，同時，在圖像中，每個像素點(diǎn)都與其周圍的像素的存在著某種關(guān)系，這也正是用像素點(diǎn)表示一幅12圖像的原因，而像素點(diǎn)間的關(guān)系就可以表示為圖中的邊。2008 年， Wenbing Tao 等人 [28]提出了一種新的基于圖譜理論的圖像閾值分割方法。該準(zhǔn)則一般是通過求解方程L0 Z 0 = d0 來實(shí)現(xiàn)的，該割集的特點(diǎn)是速度較快。不僅能在一般的圖像中取得較好的分割結(jié)果，還可以在處理視頻圖像， 3D 圖像時取得較好的優(yōu)越性 [40]；不僅可以針對灰度圖像進(jìn)行較好效果的圖像分割，也可以對彩色圖像進(jìn)行有效的分割。（ 3）對圖像的通用性有待于提高傳統(tǒng)的基于圖論的圖像分割方法在描述圖像信息間的相似性關(guān)系時，即在確定像素點(diǎn)間或區(qū)域間的相似性計(jì)算公式中，都涉及到一些參數(shù)的人為設(shè)置。雖然很多國內(nèi)外學(xué)者嘗試用很多的方法來解除這種難題，但是效果仍然是不盡理想，因此有必要把一些新的理論和思想引進(jìn)來，以便獲得較好的效果來，這也是挑戰(zhàn)這種難題的一個很好的研究領(lǐng)域 [43]。最小的 Ncut 值對應(yīng)的劃分就是圖 G 的最優(yōu)劃分。假設(shè)定義圖G中連接兩個節(jié)點(diǎn)u和v的邊權(quán)值為 w(u, v) ，對任意門限t（0tL1）就可以把圖像分為兩部分，即背景和目標(biāo)。 w(u, v) 是用來衡量節(jié)點(diǎn) u 和 v 的相似程度，為E 中元素的邊權(quán)值。因此，閾值分割是圖像分割中一類重要方法。尤其是在處理含義椒鹽噪聲或隨機(jī)噪聲、邊界不明顯、背景復(fù)雜的圖像時，基于圖論的圖像分割方法的分割效果也就無法達(dá)到理想的效果。其主要原因就是這種方法可以在進(jìn)行圖像分割時提取重要的信息，忽略不重要的信息，從而減少了數(shù)據(jù)的處理時間，使得基于圖論的圖像分割方法有著“智能”的特點(diǎn)。該割集的特點(diǎn)是速度較慢，但可以避免劃分向短邊偏釋。該方法首先運(yùn)用最短生成樹的理論來對圖像進(jìn)行粗分割，然后再用多段圖的方法多分割后的圖像進(jìn)行進(jìn)一步的分割和合成。在提取目標(biāo)時這些特征也不是都要全部考慮的，而是根據(jù)實(shí)際情況選取恰當(dāng)?shù)奶卣?。?quán)值集合是和邊集合中的元素是一一對應(yīng)的。通常情況下這些數(shù)值又稱為圖中邊的權(quán)值。在此基礎(chǔ)上提出了本課題的研究意義。這種運(yùn)用圖劃分的理論來實(shí)現(xiàn)對圖像中目標(biāo)圖像的分割方法，相對于其他的圖像分割方法，在某些方面取得了較好的圖像分割效果，因此受到越來越多國內(nèi)外學(xué)者和專家的關(guān)注。當(dāng)然這種結(jié)合的優(yōu)勢，要在有效的結(jié)合下才能顯示，僅僅把兩種算法放在一起是無法發(fā)揮這樣優(yōu)勢的。而目前大多數(shù)的圖像分割算法，由于各種原因，而沒有很好的考慮到這一點(diǎn)，因此很難取得較好的圖像分割效果。如果用距離表示兩個樣本間的相似性時，就會把特征空間劃分成若干個區(qū)域，這樣每一個區(qū)域相當(dāng)一個類別。閾值算法的優(yōu)點(diǎn)是實(shí)現(xiàn)較容易，算法簡單，特別是針對目標(biāo)和背景閾值差異較為強(qiáng)的圖像，若體現(xiàn)在灰度直方圖即有明顯的波峰和波谷的圖像，該方法的分割效果較好。串行邊緣檢測技術(shù)的優(yōu)點(diǎn)是能夠得到連續(xù)的單像素邊緣，但是它的效果對初始邊緣點(diǎn)依賴性較大，如果初始邊緣點(diǎn)的確定不恰當(dāng)?shù)脑?，可能會得到虛假邊緣，同時較少的初始邊緣點(diǎn)也有可能導(dǎo)致邊緣漏檢。條件（3）表明分割的均勻性，即同一子區(qū)域內(nèi)的像素點(diǎn)必具有某種特征上的相似性。通過人的肉眼觀察的話，這些特征有可能比較容易的看出，也有可能因?yàn)榧?xì)微的差別而觀察不出來。該方法采用MinMax Cut劃分測度作為區(qū)分目標(biāo)和背景的閾值化分割準(zhǔn)則。本文主要的研究工作如下：（ 1） 研究和分析了基于圖論的圖像分割方法和閾值化分割方法的理論及進(jìn)展，對兩者的結(jié)合的可行性進(jìn)行了探索。學(xué)位論文作者簽字：石美簽字日期：2011 年4 月29 日學(xué)位論文版權(quán)使用授權(quán)書本學(xué)位論文作者完全了解合肥工業(yè)大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，有權(quán)保留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和磁盤，允許論文被查閱或借閱。（3）區(qū)域間的差異性：不同的分割區(qū)域，特別是相鄰的區(qū)域間必須具有顯著的差異性。人們針對邊緣檢測的方法來實(shí)現(xiàn)圖像分割也研究出了很多方法，該種方法通過檢測包括不同區(qū)域的邊緣來實(shí)現(xiàn)圖像分割 [78]。具體而言就先確定某一閾值，然后把圖像中像素點(diǎn)的灰度值大于這個閾值的歸劃一類，而小于該閾值的歸劃為另一類?；趨^(qū)域的分割方法的優(yōu)點(diǎn)為：由于閾值化分割方法很少或沒有考慮到空間關(guān)系，使得在多閾值選擇上受到諸多的限制，而基于區(qū)域的分割算法則完全可以彌補(bǔ)這種不足。算法本身具有一定的針對性，而沒有不具有算法的通用性。（2） 對 多 種 圖 像 分 割 算 法 的 結(jié) 合 時 圖 像 分 割 方 法 的 另 一 個 新 的 研 究 思路，也受到人們越來越高度的重視。圖像處理中，圖像分割是最為基礎(chǔ)和重要的領(lǐng)域之一，也是低級計(jì)算機(jī)視覺中最基本最重要的研究內(nèi)容，是成功進(jìn)行圖像分析、理解與描述的關(guān)鍵技術(shù)，因?yàn)閳D像分割結(jié)果的質(zhì)量直接影響以后進(jìn)行的分析、識別和解釋的質(zhì)量。在描述圖像各像素間的相似性關(guān)系權(quán)值矩時，把基于圖像像素的權(quán)值矩陣換成基于灰度級的權(quán)值矩陣，大大節(jié)約了算法實(shí)現(xiàn)的復(fù)雜度和算法所需要的存儲空間度。 圖的分類由于出發(fā)點(diǎn)和目的不同，可以把圖分為不同的種類。而 VX 的入度是指以 VX 為終點(diǎn)的邊的數(shù)目，記為 deg i(VX ) 。圖與圖像間一一對應(yīng)的關(guān)系如圖 24 所示。基于圖論的圖像分割方法的基本原理為：將圖像看作是一個帶權(quán)圖，其每個節(jié)點(diǎn)對應(yīng)圖像的一個像素或區(qū)域，連接每兩個節(jié)點(diǎn)的邊的權(quán)值表示該兩個節(jié)點(diǎn)屬于同一區(qū)域的可能性，權(quán)值的大小與連接點(diǎn)的相似性、鄰近性以及連續(xù)性等相關(guān)。（3）MinMax Cut（最大最小割）這種割集的定義形式是 [33]： Avrcut ( A, B) =cut ( A, B)W ( A)+cut ( A, B)W (B)，其中 W ( A) =∑u∈A,v∈Aw(u, v) ，W (B) =∑u∈B ,v∈Bw(u, v)該準(zhǔn)則一般是通過求解方程 (D ? W )Z =235。這些像素間或區(qū)域間的度量關(guān)系就確保了對局部特征的處理。目前應(yīng)用最多是通過圖像的整體灰度信息來減少參與運(yùn)算的圖像信息。 基于圖論的閾值化圖像分割基于圖論的圖像分割方法是近年來圖像分割領(lǐng)域的一個新的研究熱點(diǎn)，雖然該類方法在對圖像進(jìn)行分割時，能取得較好的分割效果，但是這類方法一般都有較高的復(fù)雜性，從而使得實(shí)時性也不好。本章針對文獻(xiàn)[44]抗噪性差的問題，提出一種新的具有抑制噪聲能力的圖像分割方法。其次，采用文獻(xiàn)[44]用基于灰度值的權(quán)值矩陣代替基于圖像像素個數(shù)的權(quán)值矩陣來描述像素之間的關(guān)聯(lián)，無論在算法的時間上，還是算法的存儲空間上都得到了很好的節(jié)約。 和X分別為相應(yīng)的特征值和特征矢量?；趫D劃分的圖像分割方法通常有較高的復(fù)雜性，實(shí)時性也較差。17第三章基于 Normalized Cut 準(zhǔn)則的圖像分割方法在現(xiàn)有的基于圖論的圖像分割方法中對有噪聲污染的圖像都是通過預(yù)處理實(shí)現(xiàn)的，算法的本身不能抑制噪聲。（ 1）算法的效率有待于提高由于基于圖論的圖像分割方法在求解最優(yōu)的劃分準(zhǔn)則解時，都會無可避免的面臨 NP 難題，雖然很多基于圖論的圖像分割方法把這種求解 NP 難題轉(zhuǎn)換到求解特征方程的特征向量系統(tǒng)來實(shí)現(xiàn) [41]，比如基于 Normalize Cut 的圖像分割方法、基于 MinMax Cut 的圖像分割方法。而且效果也比較理想 [37]。 常見的幾種圖割集準(zhǔn)則（1）Minimum Cut（最小割）這種割集的定義形式 [31]是： cut( A,