基于最小生成樹的圖像分割方法研究

1、 目 錄摘 要.I Abstract.III 第一章 緒論 (11.1課題研究的背景和意義 (11.2國內(nèi)外研究現(xiàn)狀 (21.2.1 邊界檢測和邊緣連接 (21.2.2 基于區(qū)域的分割 (31.2.3 結(jié)合特定理論工具的分割技術(shù) (41.3本文的主要工作及創(chuàng)新點(diǎn) (71.4本文的組織 (7第二章 基于圖論的圖像分割方法 (92.1基本理論概念 (92.1.1 圖的分割 (92.1.2 圖像的分割 (112.1.3 彩色空間分割 (132.2三種基于圖論的圖像分割方法 (142.2.1 Ratio Cut 分割法 (142.2.2 Normalized Cut方法 (152.2.3 Isoper

2、imetric Ratio 方法 (162.3最小生成樹分割方法 (182.3.1 最小生成樹概念 (182.3.2 構(gòu)造最小生成樹 (192.4本章小結(jié) (21第三章 基于數(shù)學(xué)形態(tài)學(xué)分水嶺算法 (223.1形態(tài)學(xué)圖像處理 (223.1.1 基本概念 (223.1.2 灰度圖像中的基本操作 (233.1.3 灰度級形態(tài)學(xué)的應(yīng)用 (243.2分水嶺算法 (253.2.1 分水嶺概念 (253.2.2 分水嶺分割二值圖像 (263.2.3 分水嶺分割梯度圖像 (273.2.4 控制分水嶺過分割方法 (283.3本章小結(jié) (30第四章 基于分水嶺的最小生成樹圖像分割方法 (314.1圖像預(yù)處理 (3

3、14.1.1 顏色空間變換 (314.1.2 求取梯度圖像 (32方法 (344.2基于分水嶺的最小生成樹圖像分割方法K VW4.2.1 方法背景 (344.2.2 Vincent分水嶺算法 (344.2.3 最小生成樹合并區(qū)域 (37方法 (424.2.4 K VW4.3實(shí)驗(yàn)分析 (444.4本章小結(jié) (46第五章 總結(jié)與展望 (4775.1已完成的工作 (475.2進(jìn)一步的研究工作 (47參考文獻(xiàn) (49致 謝 (52攻讀碩士學(xué)位期間發(fā)表的論文和參與的項(xiàng)目 (53基于最小生成樹的圖像分割方法研究摘 要圖像處理廣泛應(yīng)用在醫(yī)學(xué)圖像、遙感云圖、指紋識別、人臉檢測、地質(zhì)勘探等領(lǐng)域。圖像分割是圖像處

4、理過程中的一個(gè)關(guān)鍵步驟,為圖像檢索、圖像分析提供有效的信息,使更高層次的圖像處理成為可能。常見的圖像分割方法歸納為基于邊界檢測和邊緣連接的方法、基于區(qū)域的分割方法和結(jié)合特定理論工具的分割方法三大類。近幾年,將圖論方法與其他方法結(jié)合,使圖像分割轉(zhuǎn)變?yōu)樽顑?yōu)化問題,成為國內(nèi)外圖像分割領(lǐng)域研究的熱點(diǎn)。本文詳細(xì)闡述了基于圖論的圖像分割方法,在分析最小生成樹方法的概念、原理的基礎(chǔ)上,針對Kruskal算法無法根據(jù)新生成區(qū)域修改加權(quán)區(qū)域鄰接圖的不足,提出一種改進(jìn)的Kruskal算法:區(qū)域合并后,重新計(jì)算新區(qū)域與相鄰區(qū)域的權(quán)重,修改WRAG和邊的排列順序。改進(jìn)算法使WRAG更接近原圖像的特征。為了降低Krus

5、kal算法中節(jié)點(diǎn)和邊的數(shù)目,在介紹了分水嶺算法的思想、基本模型和主要缺陷后,將基于數(shù)學(xué)形態(tài)學(xué)的分水嶺方法引入最小生成樹方法中,方法。首先,利用分水嶺方法對梯度圖像預(yù)分割,生成的過度分割提出K VW區(qū)域轉(zhuǎn)化為無向圖中的節(jié)點(diǎn),相鄰區(qū)域間的差異轉(zhuǎn)化為邊的權(quán)重,構(gòu)造加權(quán)區(qū)域鄰接圖(WRAG,再利用改進(jìn)的Kruskal算法,結(jié)合Deepthi Narayan提出的合并準(zhǔn)則,通過區(qū)域內(nèi)部差異函數(shù)、閾值函數(shù),比較區(qū)域內(nèi)部差異和外部差異,利用圖像自身信息,將符合合并準(zhǔn)則的區(qū)域進(jìn)行合并操作?；诜炙畮X的最小生成樹方法既能消除分水嶺的過度分割現(xiàn)象,又能降低邊的數(shù)目,獲得圖像的全局特征,保持較好的區(qū)域一致性。方法的

6、分割效果。最后,本文通過對多幅彩色圖像的對比實(shí)驗(yàn),驗(yàn)證K VW實(shí)驗(yàn)表明:對于前景、背景對比明顯,區(qū)域內(nèi)部特征變化緩慢,區(qū)域邊緣部分特征變化劇烈的彩色圖像,本文的方法分割效果較好,具有較強(qiáng)的適用性和較高的實(shí)用價(jià)值。對于包含較多噪聲和細(xì)節(jié)的彩色圖像,分割結(jié)果會(huì)存在冗余區(qū)域和錯(cuò)誤邊界的現(xiàn)象,需要進(jìn)一步改進(jìn)。關(guān)鍵詞:圖像分割;最小生成樹;分水嶺;圖論; Kruskal算法中圖分類號: TP391.4Research of image segmentation based on minimum spanningtreeAbstractImage processing is widely used in

7、medical images, remote sensing images, fingerprint identification, face detection, geological exploration and other fields. As a critical step in the image processing,image segmentation can provide effective information for image retrieval and image analysis, make it possible to a high level of imag

8、e processing. Common methods of image segmentation can be summarized as follow: methods based on boundary detection and edge linking, methods based on region, methods based on special theory. In recent years, the combining of graph theory with other methods is becoming a hot spot in the both domesti

9、c and foreign research field.This paper describes the image segmentation methods based on graph theory in detail. After the analysis of concepts and theories, an improved Kruskal-Minimum spanning tree algorithm is proposed, which can update the weighted region adjacency graph (WRAG. In this algorith

10、m, recalculating weights of the new region and its adjacent regions must be done after a merging, as well as changing WRAG and sorting edges. The WRAG of improved algorithm is much closer to the characteristics of the original image.The Watershed algorithm is introduced of its concepts, theories and

11、 flaws. In order to reduce the number of nodes and edges, this paper proposes a new method, named K VWmethod, combining Vincent-Watershed with Kruskal-Minimum spanning tree algorithm. Firstly, presegmentation on the gradient image is completed by the Watershed algorithm, obtaining a large number of

12、small regions. Then calculating the weights and constructing the WRAG. The nodes represent small regions, the edges between nodes represent the relationship between regions. Secondly, with Deepthi Narayan-merging criteria, the modified Kruskal algorithm can obtain better region similarity, by compar

13、ing regional differences between the internal and external information of the image own. The K VWmethod can not only eliminate the phenomenon of over segmentation, but also reduce the number of edges.By contrast experiments on series of color images, analyzing the advantages ofthe K VWmethod. The re

14、sults show that the proposed method of segmentation has good performance and strong applicability for color images, in which, there are intense contrasting of prospects and backgrounds. Its internal characterstics of regions change slowly and external characterstics of regional edges chage rapidly.

15、To those color images, which containing more noise and details, the segmentation results of method will include redundant reginons and incorrect borderline. It needs K VWfurther improvement.Key words: Image segmentation;Minimum spanning tree;Watershed;Graph theory;Kruskal algorithmClassification: TP

16、391.4第一章 緒論1.1課題研究的背景和意義視覺是人類最高級的感知手段,從視覺系統(tǒng)中能夠獲得大量的圖像信息。隨著計(jì)算機(jī)及其相關(guān)學(xué)科的發(fā)展,成像機(jī)器可覆蓋從伽馬射線到無線電波的幾乎全部電磁波譜,因此數(shù)字圖像處理的對象包括超聲波、電子顯微鏡及計(jì)算機(jī)等產(chǎn)生的圖像。為了從這些獲取的圖像中提取有用的信息,人們需要對圖像進(jìn)行分析,檢測其中感興趣的目標(biāo),獲得它們的詳細(xì)信息,建立圖像的客觀描述。在圖像自動(dòng)模式識別和場景分析之前,圖像分割成為圖像處理過程中的關(guān)鍵步驟。圖像分割是利用圖像的某些特性,如灰度、顏色、紋理、形狀等,將圖像分割成若干個(gè)子區(qū)域或?qū)ο?使同一區(qū)域內(nèi)的像素間具有一致性1。圖像分割的程度取決

17、于要解決的問題,若感興趣的對象已經(jīng)分離出來,就停止分割,否則會(huì)出現(xiàn)過度分割的小區(qū)域;如果分割不夠,目標(biāo)中就會(huì)包含冗余部分,兩種分割效果都不符合人類視覺特性。因此,精確的圖像分割為圖像檢索、圖像分析提供有效的信息,使更高層次的圖像處理成為可能。圖像處理已在很多領(lǐng)域得到廣泛應(yīng)用,包括醫(yī)學(xué)圖像、遙感云圖、交通圖像分析、指紋識別、人臉檢測、地質(zhì)勘探等:(1生物醫(yī)學(xué)工程方面。20世紀(jì)后期發(fā)展起來的現(xiàn)代醫(yī)學(xué)影像技術(shù),可以借助各種成像設(shè)備,獲得X光圖像、CT圖像、核磁共振圖像(MRI、超聲圖像及各種內(nèi)窺鏡圖像等。通過圖像處理,將病源的位置及形狀部分提取出來,對病理組織的特征參數(shù)進(jìn)行測量與統(tǒng)計(jì),可以幫助醫(yī)生分

18、析病情,做出正確的臨床診斷,制定放射、化學(xué)、外科等治療方案。(2航空航天技術(shù)方面。當(dāng)遙感衛(wèi)星經(jīng)過地面上空時(shí),星載可見光照相機(jī)等遙感儀器,能獲得大量對地觀測照片,傳送給地面處理中心進(jìn)行分析。遙感衛(wèi)星圖像可廣泛應(yīng)用于科學(xué)研究和工農(nóng)業(yè)生產(chǎn)領(lǐng)域,包括國土普查、石油勘探、鐵路選線、海洋海岸測繪、地圖測繪、目標(biāo)點(diǎn)定位、地質(zhì)調(diào)查、電站選址、地震預(yù)報(bào)、草原及林區(qū)普查、歷史文物考古等。1(3社會(huì)安全與管理方面。人臉識別、指紋識別、掌形識別等通過對人臉、指紋、掌形的動(dòng)態(tài)或靜態(tài)圖像序列的分析,提取出有效信息,通過對比庫“辨認(rèn)”或“確認(rèn)”身份,幫助公安部門刑事偵查,加強(qiáng)情報(bào)系統(tǒng)和安全部門的入口控制,也可以對銀行、公司

19、、公共場合的視頻監(jiān)控圖像進(jìn)行目標(biāo)識別。汽車牌照自動(dòng)識別技術(shù)能夠用于高速公路自動(dòng)超速監(jiān)管、港口和機(jī)場停車場管理、公路和橋梁自動(dòng)收費(fèi)系統(tǒng)等。(4工業(yè)和工程方面。過程自動(dòng)控制方面如裝配線中精密零件表面缺陷檢測,印刷電路板瑕疵檢查,郵政信件的自動(dòng)分揀等。在有毒及放射性環(huán)境中識別工件及物體的形狀和排列狀態(tài)等。目前研究的具備視覺、聽覺和觸覺功能的智能機(jī)器人涉及到機(jī)器視覺,圖像處理技術(shù)提供了讓機(jī)器模仿生物,感知物體的基礎(chǔ),從而能夠在環(huán)境中發(fā)現(xiàn)目標(biāo)。幾十年來,各相關(guān)學(xué)科的迅猛發(fā)展,對圖像處理的要求越來越高,使得圖像處理的研究更加深入和廣泛。自20世紀(jì)70年代圖像分割出現(xiàn)后,很多研究人員為之付出了巨大的努力,至

20、今己有許多種分割方法。由于不同種類的圖像,在不同應(yīng)用場合下需要提取不同的圖像特征,現(xiàn)有的分割方法在通用性方面和精度方面都有很大的提高余地,所以人們還在努力研究能夠普遍適用、準(zhǔn)確率高的分割算法。對圖像分割的深入研究不僅會(huì)推動(dòng)數(shù)字圖像處理的發(fā)展,而且會(huì)推動(dòng)模式識別、計(jì)算機(jī)視覺、人工智能等計(jì)算機(jī)分支學(xué)科的發(fā)展。1.2 國內(nèi)外研究現(xiàn)狀最早的圖像分割研究對象是灰度圖像,隨著計(jì)算機(jī)及其相關(guān)技術(shù)的發(fā)展,彩色圖像越來越多,應(yīng)用于彩色圖像的分割技術(shù)成為研究的熱點(diǎn)。圖像分割方法種類繁多,目前已有上千種方法,近年又出現(xiàn)了許多新思路和新方法,大致可以歸納為基于邊界檢測和邊緣連接的方法、基于區(qū)域的分割方法和結(jié)合特定理論

21、工具的分割方法三大類:1.2.1邊界檢測和邊緣連接邊緣檢測方法是灰度圖像分割中廣泛使用的一種方法,以各種微分算子為基礎(chǔ),結(jié)合門限、平滑等手段,利用邊界的梯度變化性質(zhì)檢測不同區(qū)域的邊緣。這些年人們提出了很多的模板2,如一階Robert算子,Sobel算子,Prewitt算子和Canny算子,二階Laplacian算子。這些模板只能在小尺度內(nèi)濾波,對于邊界明顯和噪聲低的圖像,能夠獲得較好的分割效果,對于邊緣復(fù)雜的圖像,容易受到偽輪廓線或邊界空白的干擾,無法保證得到閉合的邊界,分割效果不理想。為此, Rosenfele提出了多尺度3邊緣檢測的思想,利用小尺度濾波定位邊緣,利用大尺度濾波抑制噪聲,結(jié)合

22、不同尺度的信息最終決定邊緣點(diǎn)。后來,經(jīng)過Marr、Hildretch、Witkin等人的完善逐步形成了一套理論。1.2.2 基于區(qū)域的分割基于區(qū)域的分割方法根據(jù)同一區(qū)域內(nèi)的像素特性相似,不同區(qū)域間的像素特性相異的準(zhǔn)則,將圖像中的像素進(jìn)行分類。常見的有特征空間聚類和區(qū)域生長兩種方法4:特征空間聚類是將特征空間中的點(diǎn)進(jìn)行聚類,每個(gè)類代表圖像中的一個(gè)區(qū)域,類內(nèi)相似度較高,類間相似度較低。這種方法易于實(shí)現(xiàn),缺點(diǎn)是不易找到最佳聚類特征。常見的聚類方法有K-means算法5、模糊ISODATA算法6和高斯混合密度降解(GMDD算法7。K-means算法可以通過試探法確定類的數(shù)目,判別準(zhǔn)則通?；诜指詈箢悆?nèi)

23、和類間特征值的散布圖,因此要求類內(nèi)接近而類間差別大。ISODATA算法是在K-means算法的基礎(chǔ)上發(fā)展的,算法運(yùn)行時(shí)需要預(yù)先定義聚類的數(shù)目,通常先根據(jù)經(jīng)驗(yàn)取稍大的值,然后通過合并距離較近的聚類得到最后的聚類數(shù)目。GMDD算法是一種基于穩(wěn)健統(tǒng)計(jì)理論的層次聚類方法,通過優(yōu)化算法獲得特征空間中與預(yù)先假設(shè)最符的特征分布,逐步分離特征空間,直到特征空間全部降解為一組特征模式的混合密度分布集。GMDD方法中的特征類別不受限制,參數(shù)估計(jì)與初始狀態(tài)無關(guān),抗干擾能力強(qiáng)。區(qū)域生長是一種根據(jù)事先定義的準(zhǔn)則將像素或子區(qū)域聚合成更大區(qū)域的過程。它的基本思想是給每個(gè)分割區(qū)域找一個(gè)種子像素作為生長的起點(diǎn),然后將種子像素周

24、圍的相似像素合并到種子區(qū)域。通常根據(jù)像素間的連通性和相鄰性,選取生長準(zhǔn)則,當(dāng)沒有像素滿足加入某個(gè)區(qū)域的條件時(shí),停止區(qū)域生長。區(qū)域生長方法存在一些缺點(diǎn):1. 只能近似分割,分割結(jié)果不精確;2. 分割結(jié)果與種子點(diǎn)的選擇有關(guān);3. 容易受到噪聲影響。黃力明8提出一種基于微粒群算法的區(qū)域生長圖像分割方法,利用微粒群較強(qiáng)的搜索能力搜索像素種子點(diǎn),克服了傳統(tǒng)區(qū)域生長方法不能自動(dòng)選擇種子且容易導(dǎo)致過分割的局限性。1.2.3 結(jié)合特定理論工具的分割技術(shù)1.2.3.1基于數(shù)學(xué)形態(tài)學(xué)的分割方法數(shù)學(xué)形態(tài)學(xué)誕生于1964年,1982年Serra將它引入圖像處理,90年代人們開始深入研究使用數(shù)學(xué)形態(tài)學(xué)分割圖像?；跀?shù)學(xué)

25、形態(tài)學(xué)分割方法的基本思想是用一定形態(tài)的結(jié)構(gòu)元素度量和提取圖像中的對應(yīng)形狀,達(dá)到對圖像分析和識別的目的。1991年Vincent與Solille9提出一種模擬浸水過程的分水嶺算法,通過筑造大壩阻止不同盆地間的匯水,大壩在圖像上形成輪廓線,包圍性質(zhì)相似的像素。分水嶺算法容易受到噪聲和細(xì)節(jié)影響,產(chǎn)生過度分割現(xiàn)象。2000年黃風(fēng)崗等10提出一種柔性形態(tài)學(xué)邊緣檢測算子,將柔性形態(tài)變換運(yùn)用到邊緣檢測,既保留了經(jīng)典形態(tài)算子的優(yōu)良特性,又獲得一定程度的魯棒性。1.2.3.2 基于模糊數(shù)學(xué)的分割方法1965年,著名控制論專家L.A.Zadeh首先提出模糊集的概念,創(chuàng)立了模糊數(shù)學(xué),逐步形成了一套嚴(yán)格的數(shù)學(xué)方法,用

26、來描述帶有模糊不確定性的現(xiàn)象和事物。1979年Rosenfeld首次把模糊數(shù)學(xué)引入到圖像處理中后,人們不斷提出新的分割方法,特別是應(yīng)用在醫(yī)學(xué)圖像分析中?；谀：龜?shù)學(xué)的分割方法,每個(gè)像素由歸屬值表達(dá)屬于某個(gè)區(qū)域或者某個(gè)邊的度,這種方法常與其他方法結(jié)合使用。1996年Udupa11等人提出了基于模糊連通度的區(qū)域增長算法,通過比較圖像中所有點(diǎn)與目標(biāo)和背景種子點(diǎn)的連通度大小來進(jìn)行目標(biāo)和背景的分割。Clark等人12提出模糊C-均值(FCM聚類算法,通過對目標(biāo)函數(shù)的迭代優(yōu)化實(shí)現(xiàn)集合劃分,可以表示各個(gè)像素屬于不同類別的程度。1.2.3.3基于遺傳算法的分割方法遺傳算法是基于進(jìn)化論中自然選擇機(jī)制的、并行的、

27、統(tǒng)計(jì)的隨機(jī)化搜索方法。1975年由Holland提出,80年代Goldberg完成了遺傳算法的基本框架。它以編碼空間代替問題的參數(shù)空間,以適應(yīng)度函數(shù)為評價(jià)依據(jù),以編碼群體為進(jìn)化基礎(chǔ),以對群體中個(gè)體位串遺傳操作實(shí)現(xiàn)選擇和遺傳機(jī)制,通過對群體進(jìn)行復(fù)制、交叉、變異完成搜索過程。遺傳算法具有全局搜索能力,為函數(shù)優(yōu)化提供了一個(gè)有效的途徑和通用框架,通常將它與其他方法結(jié)合使用。文獻(xiàn)13將它與C-均值方法結(jié)合,避免聚類方法陷入局部最小值,又可盡快達(dá)到最優(yōu),文獻(xiàn)14將它與模糊集合論結(jié)合,可以提高分割的魯棒性。2000年薛景浩等15提出了一種基于閾值曲面的二維遺傳算法,采用基于閾值曲面的二維染色體編碼方式,使用

28、Hopfield 網(wǎng)絡(luò)的能量函數(shù)形式,結(jié)合圖像最優(yōu)分割準(zhǔn)則構(gòu)造適應(yīng)度函數(shù)。算法強(qiáng)調(diào)相鄰像素點(diǎn)的等同性,適于消除成塊出現(xiàn)的突發(fā)噪聲,但在分割含有隨機(jī)噪聲的圖像時(shí),因?yàn)榛叶惹娴碾S機(jī)尖銳凹凸而產(chǎn)生誤差。1.2.3.4基于活動(dòng)輪廓模型的分割方法活動(dòng)輪廓模型主要包括參數(shù)活動(dòng)輪廓模型和幾何活動(dòng)輪廓模型。1987年Kass等人16提出參數(shù)活動(dòng)輪廓模型(Snake模型,基本思想是在圖像邊界附近定義一條帶有能量的閉合曲線,由于受到曲線自身內(nèi)力和圖像數(shù)據(jù)所構(gòu)造的外力作用,閉合曲線向著能量最小的方向演化,最后收斂于圖像的邊界。該模型有三個(gè)缺點(diǎn):1. 對初始曲線的位置比較敏感;2. 由于能量泛函的非凸性,曲線在演化

29、過程中容易陷入局部極小值點(diǎn);3. 曲線的拓?fù)浣Y(jié)構(gòu)在演化過程中不會(huì)發(fā)生改變。1989年Axel等人17在模型中增加氣球力,使變形曲線作為一個(gè)整體膨脹或收縮,1998年Xu18提出使用梯度向量流代替模型中的梯度場,Amini19提出了基于動(dòng)態(tài)規(guī)劃的Snake算法來求解全局最優(yōu)曲線,Williams20提出結(jié)合貪婪算法,加快了Snake模型求解最優(yōu)曲線的速度。幾何活動(dòng)輪廓模型經(jīng)歷了從曲線的曲率運(yùn)動(dòng),到測地線幾何變形模型,再到引入面積約束項(xiàng)的過程。Osher和Sethian21提出的基于水平集(level set理論的幾何活動(dòng)輪廓模型,通過一個(gè)高維函數(shù)曲面來表達(dá)低維的演化曲線或曲面,將演化方程轉(zhuǎn)化為高

30、維水平集函數(shù)的演化偏微分方程,避免了變形曲線或曲面的參數(shù)化過程,解決了通過曲線拓?fù)浣Y(jié)構(gòu)的變化分割多個(gè)目標(biāo)的問題,能夠表示任意復(fù)雜形狀的目標(biāo)邊界。Caselles等22提出的測地線活動(dòng)輪廓模型,能夠同時(shí)檢測多個(gè)目標(biāo)的邊界,對凹陷區(qū)域也能有效分割。Siddiqi23在測地主動(dòng)輪廓線模型上,增加了一個(gè)面積約束項(xiàng),提高了變形曲線跨越圖像邊緣較小縫隙的能力,但對較大縫隙,仍無法跨越。1.2.3.5基于人工神經(jīng)網(wǎng)絡(luò)的分割方法基于人工神經(jīng)網(wǎng)絡(luò)方法的主要思想是將圖像映射為一個(gè)神經(jīng)網(wǎng)絡(luò),每個(gè)像素點(diǎn)是一個(gè)神經(jīng)元,通過動(dòng)態(tài)方程引導(dǎo)神經(jīng)元的狀態(tài)向最低能量方向變化,提取圖像邊緣。這種方法的優(yōu)點(diǎn)是具有高度的并行性,快速的

31、計(jì)算能力,較強(qiáng)的魯棒性和抗干擾能力。能夠很好地解決圖像噪聲、組織不均勻、生物形態(tài)的多變性等問題,適用于斷層掃描(CT圖像和核磁共振(MRI圖像。缺點(diǎn)是事先需要很長的學(xué)習(xí)過程訓(xùn)練神經(jīng)網(wǎng)絡(luò),初始化可能影響分割結(jié)果。Huang24提出利用最小化一個(gè)合適能量函數(shù)的Hopfield神經(jīng)網(wǎng)絡(luò)進(jìn)行灰度圖像分割,Ong等25提出基于Kohonen自組織網(wǎng)絡(luò)(SOM的兩步分層神經(jīng)網(wǎng)絡(luò)用于彩色圖像分割,應(yīng)駿等26提出結(jié)合馬爾算子特性的神經(jīng)網(wǎng)絡(luò),能夠提高對邊緣檢測的整體性能。1.2.3.6基于圖論的分割方法基于圖論的分割方法是將圖像映射為無向圖,無向圖中的節(jié)點(diǎn)表示像素,節(jié)點(diǎn)間的邊表示像素間的關(guān)系,邊的權(quán)重表示像素間

32、的差異或相似度,利用圖論中的相關(guān)知識進(jìn)行圖像分割?；趫D論的圖像分割方法可以分為基于最小生成樹的方法、最小化/最大流方法、譜方法等。1971年,Zahn27提出了基于最小生成樹的圖像分割方法,使用固定閾值進(jìn)行分類,對于像素特征變化劇烈但屬于同一目標(biāo)的區(qū)域,分割效果不好。1997年Shi和Malik28提出了歸一化切割方法,將計(jì)算最優(yōu)值問題轉(zhuǎn)化為求解矩陣的特征值和特征向量,克服了偏向劃分單個(gè)節(jié)點(diǎn)的缺陷。2004年Felzenszwalb29提出了通過比較區(qū)域間和區(qū)域內(nèi)的特征差來判定區(qū)域邊界的方法,能夠獲得全局特征。1.2.3.7 其他方法隨著成像設(shè)備和技術(shù)的發(fā)展,圖像顏色從灰度圖像向彩色圖像發(fā)展

33、,圖像種類從2-D圖像向高維圖像發(fā)展,包括3-D圖像,立體圖像,多光譜圖像及多視場圖像等,分割的對象也從靜止圖像向運(yùn)動(dòng)圖像發(fā)展,序列圖像中運(yùn)動(dòng)目標(biāo)的分割,視頻圖像的時(shí)間切割技術(shù)成為新的研究領(lǐng)域。因此圖像分割技術(shù)更多地與其它學(xué)科相聯(lián)系,除了使用人工智能、神經(jīng)網(wǎng)絡(luò)、遺傳算法、模糊數(shù)學(xué)外,還可以結(jié)合統(tǒng)計(jì)學(xué)、信息論、小波變換等理論。隨著各學(xué)科新理論和新方法的提出,人們也試著將其應(yīng)用到圖像分割中,例如利用馬爾可夫隨機(jī)場30、布朗鏈31、專家系統(tǒng)32等?？傊?找到一種精確度高,抗噪能力強(qiáng),運(yùn)算速度快,適用于各種類型圖像的分割方法是較為困難的,但它正是新的圖像分割方法層出不窮的動(dòng)力。1.3本文的主要工作及創(chuàng)

34、新點(diǎn)本文的主要工作:(1說明了課題的選取背景和意義,回顧了國內(nèi)外圖像分割的研究和發(fā)展現(xiàn)狀。(2詳細(xì)闡述了基于圖論的圖像分割方法,包括圖的分割,圖像到圖的轉(zhuǎn)化和圖像的分割準(zhǔn)則,重點(diǎn)介紹了最小生成樹分割方法,針對Kruskal算法不能根據(jù)新生成區(qū)域修改鄰接圖的缺點(diǎn),提出一種改進(jìn)的Kruskal算法。(3介紹了基于數(shù)學(xué)形態(tài)學(xué)分水嶺算法,包括基本概念,灰度圖像中四個(gè)基本操作以及灰度級形態(tài)學(xué)的應(yīng)用,然后介紹了分水嶺算法的思想,基本模型和主要缺陷,針對分水嶺方法產(chǎn)生的過度分割現(xiàn)象,將最小生成樹與分水嶺方法結(jié)方法,實(shí)驗(yàn)驗(yàn)證該方法對彩色圖像的分割效果。合,提出K VW本文的創(chuàng)新點(diǎn):(1提出一種改進(jìn)的Krusk

35、al算法。原Kruskal算法構(gòu)造最小生成樹,邊的數(shù)目固定為m,合并兩個(gè)區(qū)域后,沒有更新WRAG。改進(jìn)的Kruskal算法,在區(qū)域合并后,重新計(jì)算新區(qū)域與相鄰區(qū)域的權(quán)重,修改WRAG和邊的排列順序,減少了邊的數(shù)目,使WRAG更接近原圖特征。方法。(2提出基于分水嶺的最小生成樹方法(K VW使用分水嶺方法對圖像預(yù)分割,生成的過度分割區(qū)域轉(zhuǎn)化為無向圖中節(jié)點(diǎn)和邊的關(guān)系,構(gòu)造區(qū)域鄰接圖(WRAG,利用最小生成樹方法改進(jìn)的Kruskal 算法,將符合合并準(zhǔn)則的區(qū)域進(jìn)行合并,能夠消除分水嶺的過度分割現(xiàn)象,獲取圖像的全局特征。1.4本文的組織論文共分五章,各章的主要內(nèi)容如下:第一章緒論,介紹了圖像分割的研究

36、背景和意義,當(dāng)前國內(nèi)外的研究現(xiàn)狀,論文的創(chuàng)新點(diǎn)和組織結(jié)構(gòu)。第二章基于圖論的圖像分割方法,首先介紹了圖論中的幾個(gè)重要概念,包括圖的分割,圖像到圖的轉(zhuǎn)化和圖像的分割準(zhǔn)則,然后介紹了三種常用的基于圖論的圖像分割方法的分割準(zhǔn)則,重點(diǎn)介紹了最小生成樹方法的概念和構(gòu)造過程,指出這種方法存在的的優(yōu)點(diǎn)和缺點(diǎn)。第三章基于數(shù)學(xué)形態(tài)學(xué)分水嶺算法,首先介紹了形態(tài)學(xué)中幾個(gè)基本概念,灰度圖像中四個(gè)基本操作以及灰度級形態(tài)學(xué)的應(yīng)用,然后介紹了分水嶺算法的思想,基本模型和主要缺陷和控制分水嶺過分割的常用方法。第四章基于分水嶺的最小生成樹圖像分割方法,首先介紹了圖像分割前的預(yù)處理過程,包括顏色空間轉(zhuǎn)換和求取梯度圖像,然后介紹了經(jīng)

37、典的Vincent分水嶺算法,給出了它的主要步驟和偽代碼,分析了Kruskal算法存在的缺點(diǎn),并做方法,通過實(shí)了相應(yīng)的改進(jìn)。將分水嶺與最小生成樹方法結(jié)合,提出了K VW驗(yàn)進(jìn)行驗(yàn)證。第五章總結(jié)與展望,總結(jié)了本文的主要工作,指出以后需要進(jìn)一步完善的地方。第二章 基于圖論的圖像分割方法圖論起源于著名的柯尼斯堡七橋問題。1736年歐拉用抽象分析法將這個(gè)問題轉(zhuǎn)化為一個(gè)圖論問題:用點(diǎn)代替每塊陸地,用連接相應(yīng)兩點(diǎn)的一條線代替橋。歐拉證明了這個(gè)問題無解,并且給出了對于一個(gè)特定圖以某種方式走遍的判定法則。從19世紀(jì)中葉到20世紀(jì)中葉,圖論問題大量出現(xiàn),如漢密爾頓圖問題、四色猜想等。這些問題的出現(xiàn)進(jìn)一步促進(jìn)了圖論

38、的發(fā)展。1847年,克希霍夫(Kirchhoff 用圖論分析電網(wǎng)絡(luò),這是最早一個(gè)應(yīng)用于工程科學(xué)的例子。隨著計(jì)算機(jī)科學(xué)的迅猛發(fā)展,在現(xiàn)實(shí)生活中的許多問題,如交通網(wǎng)絡(luò)問題,運(yùn)輸?shù)膬?yōu)化問題,社會(huì)學(xué)中某類關(guān)系的研究,都可以用圖論進(jìn)行研究和處理。圖論在計(jì)算機(jī)領(lǐng)域中,諸如算法、語言、數(shù)據(jù)庫、網(wǎng)絡(luò)理論、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、人工智能等方面都有廣泛應(yīng)用。近年來基于圖論的圖像分割技術(shù)是國際圖像分割領(lǐng)域中一個(gè)新的研究熱點(diǎn)。該方法將圖像映射為帶權(quán)無向圖,將像素視為節(jié)點(diǎn),利用某種準(zhǔn)則得到圖像的最佳分割,將圖像分割問題轉(zhuǎn)化為最優(yōu)化問題。2.1基本理論概念2.1.1 圖的分割2.1.1.1 圖、加權(quán)圖和連通圖圖是由若干給定

39、的頂點(diǎn)及連接兩頂點(diǎn)的邊所構(gòu)成的一種拓?fù)鋱D形,用頂點(diǎn)代表事物,用連接兩頂點(diǎn)的邊代表相應(yīng)兩個(gè)事物間的關(guān)系。若用符號G 代表圖,則(,G V E =,其中V 代表頂點(diǎn)的集合,E 代表邊的集合,每條邊對應(yīng)著兩個(gè)相關(guān)的頂點(diǎn)。對E 中的每條邊e ,賦給一個(gè)實(shí)數(shù)(w e ,稱為邊e 的權(quán),每個(gè)邊都賦有權(quán)的圖稱為加權(quán)圖。權(quán)在不同的問題中會(huì)有不同的含義,可以表示距離、費(fèi)用、時(shí)間、電阻等。在無向圖G 中,如果從頂點(diǎn)u 到頂點(diǎn)v 有路徑,則稱u 和v 是連通的。如果圖中任意兩個(gè)頂點(diǎn)u 和v 都是連通的,則稱圖G 是連通圖,否則稱為非連通圖。2.1.1.2 子圖、補(bǔ)圖和割兩個(gè)圖(,G V E =和(,G V E =,

40、若V 是V 的子集,E 是E 的子集,則稱G 為G 的子圖。給定一個(gè)圖G ,由G 中所有節(jié)點(diǎn)和所有能使G 成為完全圖的添加邊組成的圖,稱為圖G 相對于完全圖的補(bǔ)圖(Complement ,或簡稱為G 的補(bǔ)圖。若(,G V E =為連通圖,邊集E E 1,使圖G 刪除了1E 的所有邊后,所得到的子圖是非連通圖,而刪除了1E 的任何真子集后所得到的子圖仍是連通圖,則稱1E 是G 的一個(gè)邊割集(Edge Cutest 。若某一條邊構(gòu)成一個(gè)邊割集,則稱該邊為割邊(Cut Edge ,割邊的集合叫做割集(Cut Set ,割集的權(quán)值之和稱作割(Cut 。2.1.1.3 鄰接矩陣鄰接矩陣(Adjacenc

41、y Matrix 是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)(E V G ,=為無向圖。其中12(,n V v v v = ,那么n n ×鄰接矩陣A =ij a ,其中:1,(,0,(,i j ij i j v v E a v v E = 或 (2-1例如圖2-1中G 的鄰接矩陣如圖2-2所示。 圖2-1 G 圖2-2 G 的鄰接矩陣 如果G 為加權(quán)圖,則將1ij a =改為(,ij a w i j =。例如圖2-3中G 的鄰接矩陣如圖2-4所示。 圖2-3 G 圖2-4 G 的鄰接矩陣2.1.1.4 圖的最優(yōu)分割準(zhǔn)則令圖(,G V E =,G 被劃分為A 和B 兩部分,且有A B V =,

42、A B =,頂點(diǎn)間邊上的權(quán)為(,w u v ,將圖G 劃分為A 、B 兩部分的代價(jià)函數(shù)為:,(,(,u A v B cut A B w u v = (2-2使得式(2-2值最小的劃分準(zhǔn)則稱為最小割集準(zhǔn)則。常見的割集準(zhǔn)則有歸一化切割(Normalized Cut 28、最小切割(Minimum Cut 33、平均切割(Average Cut 34、比例切割(Ratio Cut 35、等周切割(Isoperimetric Cut 36、最小最大切割(Min-max Cut 37、前景切割(ForgoundCut 38、嵌套切割(Nested Cut 39。最優(yōu)分割準(zhǔn)則的實(shí)現(xiàn)一般有兩種方式:將最優(yōu)準(zhǔn)

43、則轉(zhuǎn)化為求解矩陣方程;使用所定義的準(zhǔn)則直接進(jìn)行圖縮減。2.1.2圖像的分割圖像分割是將人們感興趣的具有同質(zhì)特性的目標(biāo)區(qū)域提取出來的過程,在分割過程中可以使用像素的灰度、顏色、紋理等特性。在圖像處理早期階段,因?yàn)閳D像主要是灰度圖像,所以發(fā)展起來的圖像分割技術(shù)也針對灰度圖像,隨著成像設(shè)備技術(shù)的發(fā)展,彩色圖像成為主要的處理對象,原來的技術(shù)不能直接應(yīng)用在彩色圖像上,需要根據(jù)圖像中的多種信息來進(jìn)行分割。2.1.2.1圖像到圖的轉(zhuǎn)化將圖像映射到加權(quán)圖(Weighted Graph ,用圖G 中的頂點(diǎn)i v V 表示圖像中的像素,用圖的邊ij e 表示像素之間的相鄰關(guān)系,邊上的權(quán)重ij w 表示像素特征之間

44、的差異或相似性。2.1.2.2權(quán)函數(shù)權(quán)函數(shù)一般定義為兩個(gè)節(jié)點(diǎn)之間的相似度,常見的權(quán)函數(shù)有如下形式:2222222|exp(,|(,exp(0,i j i j i j X I X X F F X X r w i j otherwise <=× (2-3 對于灰度圖像,i F 和j F 分別表示像素i 和j 的灰度值,i X 和j X 分別為像素i 和j 的空間坐標(biāo),I 為灰度高斯函數(shù)的標(biāo)準(zhǔn)方差,X 為空間距離高斯函數(shù)的標(biāo)準(zhǔn)方差,r 為兩像素之間的有效距離。這種權(quán)值函數(shù)的定義,考慮到空間距離,對于灰度圖像計(jì)算量很大,對于彩色圖像計(jì)算量更大。在不考慮空間距離的鄰域系統(tǒng)中,可以簡單地把

45、權(quán)函數(shù)定義為相鄰像素特征之間的絕對差值:(,|i j w i j F F = (2-4對于灰度圖像,i F 的值為像素的灰度值,對于RGB 顏色空間的彩色圖像,i F 可以是R 、G 、B 中的任意顏色分量,或者是其組合;對于HSI 顏色空間,i F 可以是H 、S 、I 的組合,或者是H 和S 的組合。還有其它一些利用圖像的灰度、顏色、紋理、距離、形狀、運(yùn)動(dòng)等信息構(gòu)造權(quán)函數(shù)的方法,但是對于不同的圖像,選擇一種信息還是幾種信息的組合,分割圖像的效果可能是不同的。2.1.2.3 鄰域系統(tǒng)鄰域系統(tǒng)定義了像素間的相鄰關(guān)系,一階鄰域系統(tǒng)為4連通結(jié)構(gòu),二階鄰域系統(tǒng)為8連通結(jié)構(gòu),一般圖像分割算法使用二階鄰

46、域系統(tǒng),如果為了減少運(yùn)算量,可以使用4連通結(jié)構(gòu),但是分割效果不如8連通結(jié)構(gòu)。如圖2-5為4連通結(jié)構(gòu),像素p 的坐標(biāo)為(,x y ,它的4連通鄰域坐標(biāo)分別為(,1x y 、(,1x y +、(1,x y 、(1,x y +,如果p 位于圖像的邊界,則p 的某一鄰域像素位于圖像的外部。 圖2-5 p 的4連通鄰域 圖2-6 p 的8連通鄰域如圖2-6為8連通結(jié)構(gòu),p 的另外4個(gè)連通鄰域坐標(biāo)分別為(1,1x y 、(1,1x y +、(1,1x y +、(1,1x y +,如果p 位于圖像的邊界,則p 的某些鄰域像素位于圖像的外部。2.1.2.4圖像的最佳分割將圖像分割為多個(gè)小區(qū)域時(shí),對圖像分割效果

47、的好壞,沒有絕對的客觀評價(jià)準(zhǔn)則,使用不同的圖像,不同的分割原則和方法,得到的效果可能互有好壞,無法找到通用的方法適用于所有的圖像。除了從方法的時(shí)間復(fù)雜度、空間復(fù)雜度、抗噪性等客觀指標(biāo)分析外,一般是基于人類的視覺系統(tǒng),對人的視覺系統(tǒng)看到的結(jié)果進(jìn)行評價(jià),即分割結(jié)果是否將我們感興趣的目標(biāo)區(qū)域(前景和背景區(qū)域精確分割開,是否存在錯(cuò)誤分割、過分割或者欠分割。各種算法分割出的區(qū)域與人類視覺判斷的分割區(qū)域之間會(huì)有3種誤差:一種是分割后的圖像中存在冗余區(qū)域;一種是應(yīng)分割開的區(qū)域未被分割;另一種是分割算法沒有正確給出邊界。在基于圖論的圖像分割方法中,可以明確地規(guī)定圖像分割的準(zhǔn)則,將圖分割成多個(gè)子集,子集內(nèi)頂點(diǎn)間

48、關(guān)系緊密,而子集間頂點(diǎn)的關(guān)系松散。若使用分割函數(shù),可以設(shè)一幅圖像為一個(gè)帶權(quán)無向圖(,G V E W =,像素集當(dāng)做節(jié)點(diǎn)集V ,邊緣集當(dāng)做邊集E ,像素間的連接權(quán)為(,w i j 。將圖像二分為集合A 、B 的代價(jià)函數(shù)為,(,(,i A j B cut A B w i j =,對于一幅圖像,使得(,cut A B 函數(shù)最小的劃分即圖像的最佳分割,這種分割準(zhǔn)則應(yīng)對某類圖像具有可靠的一致性或穩(wěn)定性,相鄰區(qū)域之間的邊界應(yīng)是完整和精確定位的。2.1.3彩色空間分割2.1.3.1 RGB 向量空間分割RGB 顏色空間是一種立方體空間結(jié)構(gòu)模型,用Red 、Green 、Blue 三個(gè)基本分量表示顏色,不同的

49、顏色處在立方體上或者其內(nèi)部。使用RGB 彩色向量空間分割圖像的方法直觀,給定一個(gè)感興趣的彩色點(diǎn)樣品集,可以得到一個(gè)彩色平均估計(jì),這種彩色是希望分割的彩色。令這個(gè)平均彩色用RGB 向量來表示,分割的目的是將給定圖像中的每個(gè)RGB 像素分類,因此需要設(shè)置相似性度量。最簡單的度量之一是歐氏距離,令z 代表RGB 空間中的任意一點(diǎn),如果它們之間的距離小于特定的閾值0D ,則稱與z 是相似的,與z 之間的歐氏距離為:1122222(,(T R R G G B B D a z a z a z =+z z z ( (2-5 其中,下標(biāo),R G B 表示向量與z 的RGB 分量。 2.1.3.2 HSI 向量

50、空間分割如果只在單獨(dú)的平面上分割一幅彩色圖像,可以選擇HSI 顏色空間,它是接近人對顏色視覺感知的一種彩色空間。色調(diào)(Hue 反映顏色的類別,區(qū)分不同顏色的特征屬性。飽和度(Saturation 表示顏色接近光譜色的程度,反映顏色的純度。強(qiáng)度(Intensity 表示顏色明暗的程度,主要受光源強(qiáng)弱影響。HSI 三個(gè)分量間的相關(guān)性比RGB 三個(gè)分量間的小,而人眼對H 、S 、I 變化的區(qū)分能力比對R ,G 、B 的強(qiáng)。在HSI 空間中彩色圖像的每個(gè)均勻性彩色區(qū)域都對應(yīng)一個(gè)相對一致的色調(diào),這使色調(diào)能夠用來進(jìn)行獨(dú)立于陰影的彩色區(qū)域分割。因此HSI (色調(diào)、飽和度和強(qiáng)度顏色空間模型可從攜帶的彩色信息中

51、消去強(qiáng)度分量的影響,使HSI 模型成為開發(fā)基于彩色描述的圖像處理方法的理想工具。2.2三種基于圖論的圖像分割方法基于圖論的圖像分割,使劃分的兩個(gè)子圖內(nèi)部相似度最大,子圖間的相似度最小,盡量避免出現(xiàn)分割粗糙現(xiàn)象或者過度分割現(xiàn)象。Ratio Cut 方法直接使用定義準(zhǔn)則進(jìn)行圖縮減,而Normalized Cut 方法結(jié)合譜方法,求解矩陣方程。2.2.1 Ratio Cut 分割法Ratio Cut 35是Wang Song 提出的具有穩(wěn)定的邊權(quán)函數(shù)的圖割模型,定義了一個(gè)新的代價(jià)函數(shù),并給出尋找最小比例割的執(zhí)行算法。在構(gòu)建的圖G 中,賦給每條邊(,u v 兩個(gè)權(quán)重1(,0w u v >和2(,

52、0w u v >,1(,w u v 為第一邊權(quán)重,表示兩個(gè)區(qū)域之間的相似度;2(,w u v 為第二邊權(quán)重,表示(U u 與(U v 之間邊的數(shù)目;12(,(,w u v w u v 為邊權(quán)重比率,如果2(,w u v =1,邊權(quán)重比率表示的就是兩個(gè)區(qū)域間每條邊在單位長度上的平均一致性。定義第一邊界代價(jià)函數(shù)和第二邊界代價(jià)函數(shù)分別為:11,(,(,(,u A v B u v E c A B w u v = (2-6 22,(,(,(,u A v B u v E c A B w u v =(2-7一般地,1(,c A B 用來描述圖G 中兩區(qū)域A 和B 間的相似度,2(,c A B 描述區(qū)域

53、A 和B 間邊界的長度。定義第一環(huán)路代價(jià)函數(shù)和第二環(huán)路代價(jià)函數(shù)為:11(,(,u v C c C w u v = (2-8 22(,(,u v C c C w u v =(2-9該算法的關(guān)鍵是找到一個(gè)最小的比率切割迭代執(zhí)行分割,切割比率代價(jià)函數(shù)為:12(,(,(,c A B Rcut A B c A B = (2-10 只要使(,Rcut A B 達(dá)到最小,兩分割區(qū)域A 、B 間邊界的平均差別將達(dá)到最大。Wang Song 指出,找到圖像對應(yīng)圖的最小比例割是個(gè)NP 完全問題,而且隨著圖中頂點(diǎn)數(shù)目的增多,求解耗時(shí)將會(huì)大幅增加。所以,在無法直接求取最小比例割的情況下,將計(jì)算最優(yōu)的Rcut 值問題在

54、其對應(yīng)的無向圈中做了簡化:最小比率切割縮減到最小比率環(huán)路;最小比率環(huán)路縮減到負(fù)代價(jià)簡單環(huán)路;負(fù)代價(jià)簡單環(huán)路縮減到最小代價(jià)理想匹配。一個(gè)圖的最小代價(jià)理想匹配比較容易找到,求解Rcut 值的問題也就迎刃而解。Ratio Cut 方法允許圖像的周界被切割,保證二分產(chǎn)生的部分是連續(xù)的,并且不會(huì)產(chǎn)生邊界長度的偏差,可以避免劃分向短邊偏移。但是,即使采用近似求解,計(jì)算量還是很大,運(yùn)算速度較慢。2.2.2 Normalized Cut 方法J. Shi 和J.Malik 28提出了 Normalized Cut 方法,定義分割準(zhǔn)則:(,(,(,(,(,cut A B cut A B Rcut A B ass

55、oc A V assoc B V =+ (2-11 其中,(,(,u A v V assoc A V w u v =,表示A 中所有節(jié)點(diǎn)和V 中所有節(jié)點(diǎn)連接邊的權(quán)值之和,(,assoc B V 含義類同。Normalized Cut 分割原則與譜方法結(jié)合,需將計(jì)算最優(yōu)值問題轉(zhuǎn)化為求解矩陣特征值和特征向量問題。設(shè)(,G V E =,其鄰接矩陣定義為(uv A G a =,若u 和v 相鄰,則1uv a =,若u 和v 不相鄰,則0uv a =。度對角矩陣為(:u D G diag d u V =,其中u d 是頂點(diǎn)u 的度。則圖G 的Laplacian 矩陣定義為:(L G D G A G =

56、(2-12 令|n V =,x 是一個(gè)n 的指示向量,1i x =表示節(jié)點(diǎn)i 在A 中,1i x =表示節(jié)點(diǎn)i 在B 中,令W 為n n ×對稱矩陣, 且,(,i j W i j w =,(,i j d w i j =,D 為對角矩陣且(,i D i i d =,0/i i ix ik d d >=,I 為全1的1n ×向量,則: (1(1(1(1(44(1T T T T x D W x x D W x Ncut x kI DI k I DI+=+ (2-13 若令1k b k =+,(1(12x b x y +=,則 (min T y T y D W y Ncut

57、x y Dy= (1,y i b ,0T y DI = (2-14 其中1表示元素全為1的1N ×向量,如果y 的取值限制為實(shí)數(shù),那么求解最優(yōu)值問題相當(dāng)于一個(gè)求解一般的特征值問題:(D W y Dy = (2-15 用y 作指示向量,使用特征方程的第二個(gè)最小的特征值所對應(yīng)的特征向量作為問題的解,這個(gè)特征向量稱為Fiedler 向量,由Fielder 最先用來分割圖,它代表最佳劃分圖的一個(gè)解。在向量y 中選擇一個(gè)分割值,使y 中大于該數(shù)的部分所對應(yīng)的節(jié)點(diǎn)在A 中,其余在B 中,并且采用遞歸算法以相同的方式對分割得到的子圖進(jìn)一步進(jìn)行劃分,直到滿足終止條件。由于(,assoc A V 表示A 中所有節(jié)點(diǎn)和V 中所有節(jié)點(diǎn)連接邊的權(quán)值之和,當(dāng)A 中只包含一個(gè)節(jié)點(diǎn)時(shí),(,assoc A V 的值很小,即計(jì)算Ncut 時(shí)有一個(gè)分母很小,這不符合