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

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)新點 (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實驗分析 (444.4本章小結(jié) (46第五章 總結(jié)與展望 (4775.1已完成的工作 (475.2進一步的研究工作 (47參考文獻 (49致 謝 (52攻讀碩士學(xué)位期間發(fā)表的論文和參與的項目 (53基于最小生成樹的圖像分割方法研究摘 要圖像處理廣泛應(yīng)用在醫(yī)學(xué)圖像、遙感云圖、指紋識別、人臉檢測、地質(zhì)勘探等領(lǐng)域。圖像分割是圖像處

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

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

6、分割效果。最后,本文通過對多幅彩色圖像的對比實驗,驗證K VW實驗表明:對于前景、背景對比明顯,區(qū)域內(nèi)部特征變化緩慢,區(qū)域邊緣部分特征變化劇烈的彩色圖像,本文的方法分割效果較好,具有較強的適用性和較高的實用價值。對于包含較多噪聲和細節(jié)的彩色圖像,分割結(jié)果會存在冗余區(qū)域和錯誤邊界的現(xià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)中能夠獲得大量的圖像信息。隨著計算機及其相關(guān)學(xué)科的發(fā)展,成像機器可覆蓋從伽馬射線到無線電波的幾乎全部電磁波譜,因此數(shù)字圖像處理的對象包括超聲波、電子顯微鏡及計算機等產(chǎn)生的圖像。為了從這些獲取的圖像中提取有用的信息,人們需要對圖像進行分析,檢測其中感興趣的目標,獲得它們的詳細信息,建立圖像的客觀描述。在圖像自動模式識別和場景分析之前,圖像分割成為圖像處理過程中的關(guān)鍵步驟。圖像分割是利用圖像的某些特性,如灰度、顏色、紋理、形狀等,將圖像分割成若干個子區(qū)域或?qū)ο?使同一區(qū)域內(nèi)的像素間具有一致性1。圖像分割的程度取決

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

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

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

20、今己有許多種分割方法。由于不同種類的圖像,在不同應(yīng)用場合下需要提取不同的圖像特征,現(xiàn)有的分割方法在通用性方面和精度方面都有很大的提高余地,所以人們還在努力研究能夠普遍適用、準確率高的分割算法。對圖像分割的深入研究不僅會推動數(shù)字圖像處理的發(fā)展,而且會推動模式識別、計算機視覺、人工智能等計算機分支學(xué)科的發(fā)展。1.2 國內(nèi)外研究現(xiàn)狀最早的圖像分割研究對象是灰度圖像,隨著計算機及其相關(guān)技術(shù)的發(fā)展,彩色圖像越來越多,應(yīng)用于彩色圖像的分割技術(shù)成為研究的熱點。圖像分割方法種類繁多,目前已有上千種方法,近年又出現(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、不同尺度的信息最終決定邊緣點。后來,經(jīng)過Marr、Hildretch、Witkin等人的完善逐步形成了一套理論。1.2.2 基于區(qū)域的分割基于區(qū)域的分割方法根據(jù)同一區(qū)域內(nèi)的像素特性相似,不同區(qū)域間的像素特性相異的準則,將圖像中的像素進行分類。常見的有特征空間聚類和區(qū)域生長兩種方法4:特征空間聚類是將特征空間中的點進行聚類,每個類代表圖像中的一個區(qū)域,類內(nèi)相似度較高,類間相似度較低。這種方法易于實現(xiàn),缺點是不易找到最佳聚類特征。常見的聚類方法有K-means算法5、模糊ISODATA算法6和高斯混合密度降解(GMDD算法7。K-means算法可以通過試探法確定類的數(shù)目,判別準則通?；诜指詈箢悆?nèi)

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

24、圍的相似像素合并到種子區(qū)域。通常根據(jù)像素間的連通性和相鄰性,選取生長準則,當(dāng)沒有像素滿足加入某個區(qū)域的條件時,停止區(qū)域生長。區(qū)域生長方法存在一些缺點:1. 只能近似分割,分割結(jié)果不精確;2. 分割結(jié)果與種子點的選擇有關(guān);3. 容易受到噪聲影響。黃力明8提出一種基于微粒群算法的區(qū)域生長圖像分割方法,利用微粒群較強的搜索能力搜索像素種子點,克服了傳統(tǒng)區(qū)域生長方法不能自動選擇種子且容易導(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)形狀,達到對圖像分析和識別的目的。1991年Vincent與Solille9提出一種模擬浸水過程的分水嶺算法,通過筑造大壩阻止不同盆地間的匯水,大壩在圖像上形成輪廓線,包圍性質(zhì)相似的像素。分水嶺算法容易受到噪聲和細節(jié)影響,產(chǎn)生過度分割現(xiàn)象。2000年黃風(fēng)崗等10提出一種柔性形態(tài)學(xué)邊緣檢測算子,將柔性形態(tài)變換運用到邊緣檢測,既保留了經(jīng)典形態(tài)算子的優(yōu)良特性,又獲得一定程度的魯棒性。1.2.3.2 基于模糊數(shù)學(xué)的分割方法1965年,著名控制論專家L.A.Zadeh首先提出模糊集的概念,創(chuàng)立了模糊數(shù)學(xué),逐步形成了一套嚴格的數(shù)學(xué)方法,用

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

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

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

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

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

31、計算能力,較強的魯棒性和抗干擾能力。能夠很好地解決圖像噪聲、組織不均勻、生物形態(tài)的多變性等問題,適用于斷層掃描(CT圖像和核磁共振(MRI圖像。缺點是事先需要很長的學(xué)習(xí)過程訓(xùn)練神經(jīng)網(wǎng)絡(luò),初始化可能影響分割結(jié)果。Huang24提出利用最小化一個合適能量函數(shù)的Hopfield神經(jīng)網(wǎng)絡(luò)進行灰度圖像分割,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é)點表示像素,節(jié)點間的邊表示像素間的關(guān)系,邊的權(quán)重表示像素間

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

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

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

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

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

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

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

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

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

41、y Matrix 是表示頂點之間相鄰關(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)分割準則令圖(,G V E =,G 被劃分為A 和B 兩部分,且有A B V =,

42、A B =,頂點間邊上的權(quán)為(,w u v ,將圖G 劃分為A 、B 兩部分的代價函數(shù)為:,(,(,u A v B cut A B w u v = (2-2使得式(2-2值最小的劃分準則稱為最小割集準則。常見的割集準則有歸一化切割(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)分割準則的實現(xiàn)一般有兩種方式:將最優(yōu)準

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

44、的差異或相似性。2.1.2.2權(quán)函數(shù)權(quán)函數(shù)一般定義為兩個節(jié)點之間的相似度,常見的權(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 的空間坐標,I 為灰度高斯函數(shù)的標準方差,X 為空間距離高斯函數(shù)的標準方差,r 為兩像素之間的有效距離。這種權(quán)值函數(shù)的定義,考慮到空間距離,對于灰度圖像計算量很大,對于彩色圖像計算量更大。在不考慮空間距離的鄰域系統(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 的組合。還有其它一些利用圖像的灰度、顏色、紋理、距離、形狀、運動等信息構(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),如果為了減少運算量,可以使用4連通結(jié)構(gòu),但是分割效果不如8連通結(jié)構(gòu)。如圖2-5為4連通結(jié)構(gòu),像素p 的坐標為(,x y ,它的4連通鄰域坐標分別為(,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個連通鄰域坐標分別為(1,1x y 、(1,1x y +、(1,1x y +、(1,1x y +,如果p 位于圖像的邊界,則p 的某些鄰域像素位于圖像的外部。2.1.2.4圖像的最佳分割將圖像分割為多個小區(qū)域時,對圖像分割效果

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

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

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

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

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

52、0w u v >,1(,w u v 為第一邊權(quán)重,表示兩個區(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)重比率表示的就是兩個區(qū)域間每條邊在單位長度上的平均一致性。定義第一邊界代價函數(shù)和第二邊界代價函數(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)路代價函數(shù)和第二環(huán)路代價函數(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)鍵是找到一個最小的比率切割迭代執(zhí)行分割,切割比率代價函數(shù)為:12(,(,(,c A B Rcut A B c A B = (2-10 只要使(,Rcut A B 達到最小,兩分割區(qū)域A 、B 間邊界的平均差別將達到最大。Wang Song 指出,找到圖像對應(yīng)圖的最小比例割是個NP 完全問題,而且隨著圖中頂點數(shù)目的增多,求解耗時將會大幅增加。所以,在無法直接求取最小比例割的情況下,將計算最優(yōu)的Rcut 值問題在

54、其對應(yīng)的無向圈中做了簡化:最小比率切割縮減到最小比率環(huán)路;最小比率環(huán)路縮減到負代價簡單環(huán)路;負代價簡單環(huán)路縮減到最小代價理想匹配。一個圖的最小代價理想匹配比較容易找到,求解Rcut 值的問題也就迎刃而解。Ratio Cut 方法允許圖像的周界被切割,保證二分產(chǎn)生的部分是連續(xù)的,并且不會產(chǎn)生邊界長度的偏差,可以避免劃分向短邊偏移。但是,即使采用近似求解,計算量還是很大,運算速度較慢。2.2.2 Normalized Cut 方法J. Shi 和J.Malik 28提出了 Normalized Cut 方法,定義分割準則:(,(,(,(,(,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é)點和V 中所有節(jié)點連接邊的權(quán)值之和,(,assoc B V 含義類同。Normalized Cut 分割原則與譜方法結(jié)合,需將計算最優(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 是頂點u 的度。則圖G 的Laplacian 矩陣定義為:(L G D G A G =

56、(2-12 令|n V =,x 是一個n 的指示向量,1i x =表示節(jié)點i 在A 中,1i x =表示節(jié)點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ù),那么求解最優(yōu)值問題相當(dāng)于一個求解一般的特征值問題:(D W y Dy = (2-15 用y 作指示向量,使用特征方程的第二個最小的特征值所對應(yīng)的特征向量作為問題的解,這個特征向量稱為Fiedler 向量,由Fielder 最先用來分割圖,它代表最佳劃分圖的一個解。在向量y 中選擇一個分割值,使y 中大于該數(shù)的部分所對應(yīng)的節(jié)點在A 中,其余在B 中,并且采用遞歸算法以相同的方式對分割得到的子圖進一步進行劃分,直到滿足終止條件。由于(,assoc A V 表示A 中所有節(jié)點和V 中所有節(jié)點連接邊的權(quán)值之和,當(dāng)A 中只包含一個節(jié)點時,(,assoc A V 的值很小,即計算Ncut 時有一個分母很小,這不符合