【正文】 節(jié)點和V 中所有節(jié)點連接邊的u∈ A , v∈V權值之和， assoc ( B , V ) 含義類同。Ratio Cut 方法允許圖像的周界被切割，保證二分產生的部分是連續(xù)的，并且不會產生邊界長度的偏差，可以避免劃分向短邊偏移。所以，在無法直接求取最小比例割的情況下，將計算最優(yōu)的 Rcut 值問題在其對應的無向圈中做了簡化：最小比率切割縮減到最小比率環(huán)路；最小比率環(huán)路縮減到負代價簡單環(huán)路；負代價簡單環(huán)路縮減到最小代價理想匹配。定義第一環(huán)路代價函數(shù)和第二環(huán)路代價函數(shù)為：14c1 (C ) = ∑ w1 (u , v)（28）( u , v )∈Cc2 (C ) = ∑ w2 (u , v)（29）( u , v )∈C該算法的關鍵是找到一個最小的比率切割迭代執(zhí)行分割，切割比率代價函數(shù)為：Rcut ( A, B) =c1( A, B)（210）c ( A, B)2只要使 Rcut ( A, B) 達到最小，兩分割區(qū)域 A 、B 間邊界的平均差別將達到最大。在構建的圖 G 中，賦給每條邊 (u , v) 兩個權重 w1 (u , v) 0 和 w2 (u , v) 0 ，w1 (u , v) 為第一邊權重，表示兩個區(qū)域之間的相似度； w2 (u , v) 為第二邊權重，表w (u , v)示U (u) 與U ( v) 之間邊的數(shù)目； w1 (u , v) 為邊權重比率，如果 w2 (u , v) =1，邊權重2比率表示的就是兩個區(qū)域間每條邊在單位長度上的平均一致性。Ratio Cut 方法直接使用定義準則進行圖縮減，而 Normalized Cut 方法結合譜方法，求解矩陣方程。因此 HSI（色調、飽和度和強度）顏色空間模型可從攜帶的彩色信息中消去強度分量的影響，使 HSI 模型成為開發(fā)基于彩色描述的圖像處理方法的理想工具。HSI 三個分量間的相關性比 RGB 三個分量間的小，而人眼對 H、S、I 變化的區(qū)分能力比對 R，G、B 的強。飽和度（Saturation）表示顏色接近光譜色的程度，反映顏色的純度。 HSI 向量空間分割13如果只在單獨的平面上分割一幅彩色圖像，可以選擇 HSI 顏色空間，它是接近人對顏色視覺感知的一種彩色空間。令這個平均彩色用 RGB 向量α來表示，分割的目的是將給定圖像中的每個 RGB 像素分類，因此需要設置相似性度量。 彩色空間分割 RGB 向量空間分割RGB 顏色空間是一種立方體空間結構模型，用 Red、Green、Blue 三個基本分量表示顏色，不同的顏色處在立方體上或者其內部。若使用分割函數(shù)，可以設一幅圖像為一個帶權無向圖G = (V , E , W ) ，像素集當做節(jié)點集V ，邊緣集當做邊集 E ，像素間的連接權為 w(i , j) 。各種算法分割出的區(qū)域與人類視覺判斷的分割區(qū)域之間會有 3 種誤差：一種是分割后的圖像中存在冗余區(qū)域；一種是應分割開的區(qū)域未被分割；另一種是分割算法沒有正確給出邊界。 圖像的最佳分割12將圖像分割為多個小區(qū)域時，對圖像分割效果的好壞，沒有絕對的客觀評價準則，使用不同的圖像，不同的分割原則和方法，得到的效果可能互有好壞，無法找到通用的方法適用于所有的圖像。如圖 25 為 4 連通結構，像素 p 的坐標為( x, y) ，它的 4 連通鄰域坐標分別為 ( x , y ?1) 、 ( x , y +1) 、 ( x ?1, y) 、 ( x +1, y) ，如果 p 位于圖像的邊界，則 p 的某一鄰域像素位于圖像的外部。還有其它一些利用圖像的灰度、顏色、紋理、距離、形狀、運動等信息構造權函數(shù)的方法，但是對于不同的圖像，選擇一種信息還是幾種信息的組合，分割圖像的效果可能是不同的。這種權值函數(shù)的定義，考慮到空間距離，對于灰度圖像計算量很大，對于彩色圖像計算量更大。 圖像到圖的轉化將圖像映射到加權圖（Weighted Graph），用圖G 中的頂點vi V 表示圖像中的像素，用圖的邊eij 表示像素之間的相鄰關系，邊上的權重 wij 表示像素特征之間的差異或相似性。 圖像的分割圖像分割是將人們感興趣的具有同質特性的目標區(qū)域提取出來的過程，在分割過程中可以使用像素的灰度、顏色、紋理等特性。常見的割集準則有歸一化切割（Normalized Cut）[28]、最小切割（MinimumCut）[33]、平均切割（Average Cut）[34]、比例切割（Ratio Cut）[35]、等周切割（Isoperimetric Cut） [36]、最小最大切割（Minmax Cut）[37]、前景切割（ForgoundCut）[38]、嵌套切割（Nested Cut）[39]。例如圖 23 中G’的鄰接矩陣 如圖 24 所示。其中V = ( v1 , v2 , ,vn ) ，那么 n n 鄰接矩陣 A =[ aij ]，其中：1,( v , v) Eaiji j=( vi , v j ) E(21)0 或∞,例如圖 21 中G 的鄰接矩陣如圖 22 所示。 鄰接矩陣鄰接矩陣（Adjacency Matrix）是表示頂點之間相鄰關系的矩陣。若G = (V , E) 為連通圖，邊集 E1 ? E ，使圖G 刪除了 E1 的所有邊后，所得到的子圖是非連通圖，而刪除了 E1 的任何真子集后所得到的子圖仍是連通圖，則稱 E1 是G 的一個邊割集（Edge Cutest）。 子圖、補圖和割兩個圖G = (V , E) 和G’= (V ’,E’)，若V’是V 的子集， E’是 E 的子集，則9稱G’為G 的子圖。在無向圖G 中，如果從頂點u 到頂點v 有路徑，則稱u 和v 是連通的。對 E 中的每條邊e ，賦給一個實數(shù) w( e) ，稱為邊e 的權，每個邊都賦有權的圖稱為加權圖。 基本理論概念 圖的分割 圖、加權圖和連通圖圖是由若干給定的頂點及連接兩頂點的邊所構成的一種拓撲圖形，用頂點代表事物，用連接兩頂點的邊代表相應兩個事物間的關系。近年來基于圖論的圖像分割技術是國際圖像分割領域中一個新的研究熱點。隨著計算機科學的迅猛發(fā)展，在現(xiàn)實生活中的許多問題，如交通網絡問題，運輸?shù)膬?yōu)化問題，社會學中某類關系的研究，都可以用圖論進行研究和處理。這些問題的出現(xiàn)進一步促進了圖論的發(fā)展。歐拉證明了這個問題無解，并且給出了對于一個特定圖以某種方式走遍的判定法則。8第二章 基于圖論的圖像分割方法圖論起源于著名的柯尼斯堡七橋問題。將分水嶺與最小生成樹方法結合，提出了 K ?VW 方法，通過實驗進行驗證。第三章基于數(shù)學形態(tài)學分水嶺算法，首先介紹了形態(tài)學中幾個基本概念，灰度圖像中四個基本操作以及灰度級形態(tài)學的應用，然后介紹了分水嶺算法的思想，基本模型和主要缺陷和控制分水嶺過分割的常用方法。 本文的組織論文共分五章，各章的主要內容如下：第一章緒論，介紹了圖像分割的研究背景和意義，當前國內外的研究現(xiàn)狀，論文的創(chuàng)新點和組織結構。（2）提出基于分水嶺的最小生成樹方法（ K ?VW 方法）。原 Kruskal 算法構造最小生成樹，邊的數(shù)目固定為 m ，合并兩個區(qū)域后，沒有更新 WRAG。（3）介紹了基于數(shù)學形態(tài)學分水嶺算法，包括基本概念，灰度圖像中四個基本操作以及灰度級形態(tài)學的應用，然后介紹了分水嶺算法的思想，基本模型和主要缺陷，針對分水嶺方法產生的過度分割現(xiàn)象，將最小生成樹與分水嶺方法結合，提出 K ?VW 方法，實驗驗證該方法對彩色圖像的分割效果。6 本文的主要工作及創(chuàng)新點本文的主要工作：（1）說明了課題的選取背景和意義，回顧了國內外圖像分割的研究和發(fā)展現(xiàn)狀。隨著各學科新理論和新方法的提出，人們也試著將其應用到圖像分割中，例如利用馬爾可夫隨機場[30]、布朗鏈[31]、專家系統(tǒng)[32]等。 其他方法隨著成像設備和技術的發(fā)展，圖像顏色從灰度圖像向彩色圖像發(fā)展，圖像種類從 2D 圖像向高維圖像發(fā)展，包括 3D 圖像，立體圖像，多光譜圖像及多視場圖像等，分割的對象也從靜止圖像向運動圖像發(fā)展，序列圖像中運動目標的分割，視頻圖像的時間切割技術成為新的研究領域。1997 年 Shi 和 Malik[28]提出了歸一化切割方法，將計算最優(yōu)值問題轉化為求解矩陣的特征值和特征向量，克服了偏向劃分單個節(jié)點的缺陷。基于圖論的圖像分割方法可以分為基于最小生成樹的方法、最小化/最大流方法、譜方法等。Huang[24]提出利用最小化一個合適能量函數(shù)的 Hopfield 神經網絡進行灰度圖像分割，Ong 等[25]提出基于 Kohonen 自組織網絡（SOM）的兩步分層神經網絡用于彩色圖像分割，應駿等[26]提出結合馬爾算子特性的神經網絡，能夠提高對邊緣檢測的整體性能。能夠很好地解決圖像噪聲、組織不均勻、生物形態(tài)的多變性等問題，適用于斷層掃描（CT）圖像和核磁共振（MRI）圖像。 基于人工神經網絡的分割方法5基于人工神經網絡方法的主要思想是將圖像映射為一個神經網絡，每個像素點是一個神經元，通過動態(tài)方程引導神經元的狀態(tài)向最低能量方向變化，提取圖像邊緣。Caselles 等[22]提出的測地線活動輪廓模型，能夠同時檢測多個目標的邊界，對凹陷區(qū)域也能有效分割。幾何活動輪廓模型經歷了從曲線的曲率運動，到測地線幾何變形模型，再到引入面積約束項的過程。該模型有三個缺點：1. 對初始曲線的位置比較敏感； 2. 由于能量泛函的非凸性，曲線在演化過程中容易陷入局部極小值點； 3. 曲線的拓撲結構在演化過程中不會發(fā)生改變。 基于活動輪廓模型的分割方法活動輪廓模型主要包括參數(shù)活動輪廓模型和幾何活動輪廓模型。2000 年薛景浩等[15]提出了一種基于閾值曲面的二維遺傳算法，采用基于閾值曲面的二維染色體編碼方式，使用 Hopfield網絡的能量函數(shù)形式，結合圖像最優(yōu)分割準則構造適應度函數(shù)。遺傳算法具有全局搜索能力，為函數(shù)優(yōu)化提供了一個有效的途徑和通用框架，通常將它與其他方法結合使用。1975 年由 Holland 提出，80 年代 Goldberg 完成了遺傳算法的基本框架。Clark 等人[12]提出模糊 C均值（FCM）聚類算法，通過對目標函數(shù)的迭代優(yōu)化實現(xiàn)集合劃分，可以表示各個像素屬于不同類別的程度?；谀：龜?shù)學的分割方法，每個像素由歸屬值表達屬于某個區(qū)域或者某個邊的度，這種方法常與其他方法結合使用。 基于模糊數(shù)學的分割方法1965 年，著名控制論專家 首先提出模糊集的概念，創(chuàng)立了模糊數(shù)學，逐步形成了一套嚴格的數(shù)學方法，用來描述帶有模糊不確定性的現(xiàn)象和事物。分水嶺算法容易受到噪聲和細節(jié)影響，產生過度分割現(xiàn)象?；跀?shù)學形態(tài)學分割方法的基本思想是用一定形態(tài)的結構元素度量和提取圖像中的對應形狀，達到對圖像分析和識別的目的。 黃力明[8]提出一種基于微粒群算法的區(qū)域生長圖像分割方法，利用微粒群較3強的搜索能力搜索像素種子點，克服了傳統(tǒng)區(qū)域生長方法不能自動選擇種子且容易導致過分割的局限性。通常根據(jù)像素間的連通性和相鄰性，選取生長準則，當沒有像素滿足加入某個區(qū)域的條件時，停止區(qū)域生長。區(qū)域生長是一種根據(jù)事先定義的準則將像素或子區(qū)域聚合成更大區(qū)域的過程。GMDD 算法是一種基于穩(wěn)健統(tǒng)計理論的層次聚類方法，通過優(yōu)化算法獲得特征空間中與預先假設最符的特征分布，逐步分離特征空間，直到特征空間全部降解為一組特征模式的混合密度分布集。Kmeans 算法可以通過試探法確定類的數(shù)目，判別準則通?；诜指詈箢悆群皖愰g特征值的散布圖，因此要求類內接近而類間差別大。這種方法易于實現(xiàn)，缺點是不易找到最佳聚類特征。 基于區(qū)域的分割基于區(qū)域的分割方法根據(jù)同一區(qū)域內的像素特性相似，不同區(qū)域間的像素特性相異的準則，將圖像中的像素進行分類。為此，Rosenfele 提出了多尺度[3]邊緣檢測的思想，利用小尺度濾波定位邊緣，利用大尺度濾波抑制噪聲，結合不同尺度的信息最終決定邊緣點。這些年人們提出了很多的模板[2]，如一階 Robert 算子，Sobel 算子，Prewitt 算子和Canny 算子，二階 Laplacian 算子。 國內外研究現(xiàn)狀最早的圖像分割研究對象是灰度圖像，隨著計算機及其相關技術的發(fā)展，彩色圖像越來越多，應用于彩色圖像的分割技術成為研究的熱點。由于不同種類的圖像，在不同應用場合下需要提取不同的圖像特征，現(xiàn)有的分割方法在通用性方面和精度方面