【正文】 分水嶺分割梯度圖像對于一幅原始圖像，先求取梯度圖像 g ( x , y) ， min 和 max 分別表示梯度最小值和最大值，梯度圖像中的局部最小值就是原始圖像中變化最小的區(qū)域，可以看成生長種子。這種生長步驟重復(fù)進行到結(jié)果不再變化。（3）生長回到原尺寸從種子開始生長回到原尺寸，但不使各區(qū)域相連。最終腐蝕Yi 可以定義為 Ai 中的元素，它的第一步是：U k = ( Ak +1 ⊕{ B})。 X = [[[( A ⊕ B ) ∩ X ] ⊕ B ] ∩ X ] ⊕ B（39）其中，{ B} 表示迭代地用 B 對 A進行膨脹操作，直到不再有變化。 X = ( A ⊕ B ) ∩ X（38）迭代條件膨脹記為 A ⊕{ B}。（2）計算腐蝕集合在條件 X 下用 B 對 A進行膨脹操作，記為 A ⊕ B 。用形態(tài)學(xué)方法產(chǎn)生距離圖時，可以在每次腐蝕后將剩下的像素值加 1，迭代腐蝕公式為：Ak = AΘkB （37）其中，Ak 的下標表示不同次數(shù)的迭代腐蝕。圖 33 描述的是浸水過程的分水嶺算法，首先找到所有局部最小值，在最小值位置打一個洞，將模型浸入水中，由最小值位置進入的水形成盆地，隨著水位上升，不同盆地間的水將會匯合，在即將匯合時建立大壩。（a） （b）圖 31 分水嶺地形模型降水及浸水過程如圖 32 及圖 33 所示。最終在圖像上形成一些輪廓線，將圖像中相似的部分包圍起來，形成分割圖像的效果。（2）模擬浸水過程。將圖像想象成 3D 地形，因為像素值有高有低，地形呈現(xiàn)高低起伏的山脈和盆地的形態(tài)。24 分水嶺算法 分水嶺概念分水嶺變換是一種形態(tài)學(xué)的圖像分割方法，其基本思想是將圖像看成地形表面，每個像素的值代表該點的海拔高度，其中包含一些局部最小值的點，讓水滴在某個位置落下，能夠落到一個單一最小值點上的位置的集合稱為這個最小值的“分水嶺”，若水滴等概率地流向不止一個這樣的最小點，水滴位置的集合稱為“分水線”。這種粒度測定對于檢測帶有某一主要類似顆粒狀的區(qū)域效果較好。（2）粒度測定粒度測定主要是判斷圖像中顆粒的尺寸分布問題，可以逐漸從小到大使用不同的結(jié)構(gòu)元素對輸入圖像進行開操作，因為當以某一特定尺寸對含有相近尺寸顆粒的圖像區(qū)域進行開操作，處理效果最好。 灰度級形態(tài)學(xué)的應(yīng)用（1）邊緣檢測很多邊緣檢測算子對噪聲敏感，而且會在檢測邊緣時加強噪聲，基于形態(tài)梯度的邊緣檢測，和其他邊緣檢測算子一樣對噪聲敏感，但是不會加強噪聲。（4）閉操作用結(jié)構(gòu)元素b 對圖像 f 進行閉操作，表示為 f ?b ，定義為：f ? b = ( f ⊕ b ) Θb（34）閉操作先用b 對 f 進行膨脹操作，可以除去圖像中的暗細節(jié)，同時增加圖像的亮度；然后用b 對前面的結(jié)果進行腐蝕，但不會將膨脹操作除去的部分重新引入圖像。（3）開操作用結(jié)構(gòu)元素b 對圖像 f 進行開操作，表示為 f b ，定義為：f b = ( f Θb ) ⊕b （33）開操作先用b 對 f 進行腐蝕操作，這樣可以除去小的圖像細節(jié)，但會使圖像變暗；然后用b 對前面的結(jié)果進行膨脹操作，這會增強圖像的亮度，但不會將腐蝕操作除去的部分加入圖像。( x , y ) ∈Db}（32）其中，Df 和 Db 分別是 f 和b 的定義域，平移參數(shù)( s + x) 和(t + y) 必須在 f的定義域內(nèi)，而 x 和 y 必須在b 的定義域內(nèi)。( x , y ) ∈ Db} （31）其中，Df 和 Db 分別是 f 和b 的定義域，在每個結(jié)構(gòu)元素的位置上，膨脹值是在跨度為b 的區(qū)間內(nèi) f 與b 之和的最大值，在用膨脹操作處理灰度圖像后，如果所有結(jié)構(gòu)元素的值為正，輸出圖像會比輸入圖像更亮。 基本概念集合 A與 B 的并集C ：C = A ∪ B集合 A與 B 的交集C ：C = A ∩ B22集合 A與 B 不相容： A ∩ B = ?? ?ww = ? a , a ∈ A集合 A的反射 A： A ={}集合 A平移到點 z = ( z1 , z2 ) ，表示為( A)z ：( A) z = { c c = a + z , a ∈ A} 灰度圖像中的基本操作輸入圖像函數(shù) f ( x , y) ，結(jié)構(gòu)元素b ( x , y) 是一個子圖像函數(shù)， Z 表示實整數(shù) 集合，( x, y) 是來自 Z Z 的整數(shù)， f 和b 是對每一個( x, y) 坐標賦以灰度值的函 數(shù)。 形態(tài)學(xué)圖像處理形態(tài)學(xué)技術(shù)可以從圖像中提取某些感興趣的特征，在圖像描繪方面也具有重要作用，成為在許多應(yīng)用領(lǐng)域中建立圖像分割方法的基礎(chǔ)。目前，數(shù)學(xué)形態(tài)學(xué)已經(jīng)成為圖像處理領(lǐng)域中的一種重要理論和方法，它可以適用于與圖像處理有關(guān)的各個方面，例如細胞顯微圖像分析，核磁共振圖像（MRI）識別，郵政信件自動分揀，印刷電路板檢測，汽車運動情況監(jiān)測等。數(shù)學(xué)形態(tài)學(xué)所用的語言是集合論，集合表示圖像中的不同對象，因此它具有完備的數(shù)學(xué)基礎(chǔ)，為形態(tài)學(xué)用于圖像分析和處理、形態(tài)濾波器的特性分析和系統(tǒng)設(shè)計奠定了堅實的基礎(chǔ)。數(shù)學(xué)形態(tài)學(xué)的基本思想是用具有一定形態(tài)的結(jié)構(gòu)元素“探針”去量度和提取圖像中的信息，當“探針”在圖像中不斷移動時，可以考察圖像各部分之間的關(guān)系，從而了解圖像的結(jié)構(gòu)特征，達到對圖像分析和識別的目的。1975 年，Matheron 的《隨機集和積分幾何》奠定了數(shù)學(xué)形態(tài)學(xué)基礎(chǔ)，1982 年 Serra 的《圖像分析和數(shù)學(xué)形態(tài)學(xué)》標志著數(shù)學(xué)形態(tài)學(xué)理論趨于成熟。20 本章小結(jié)本章首先介紹了圖論中的基本概念（圖、加權(quán)圖、連通圖、子圖、補圖、割、鄰接矩陣和圖的最優(yōu)分割準則）和圖像分割中的基本概念（圖像到圖的轉(zhuǎn)化，權(quán)函數(shù)，像素的鄰域系統(tǒng)和圖像的最優(yōu)分割準則），然后介紹了三種常見的基于圖論的圖像分割方法，Ratio Cut 方法、Normalized Cut 方法、Isoperimetric Ratio 方法，給出了三種方法的分割思想和分割準則，最后介紹了最小生成樹方法的概念和構(gòu)造過程，指出這種方法存在的的優(yōu)點和缺點。 3．容易受噪聲和細節(jié)影響。最小生成樹方法不能將整幅圖像生成一棵樹，針對圖 像中的多個目標，需要生成多棵最小生成樹，因此需要選取閾值，將邊上權(quán)重與 閾值比較，當權(quán)重大于閾值時，停止構(gòu)造最小生成樹。如果分割尺寸較大的圖像，每個像素轉(zhuǎn)變?yōu)楣?jié)點，節(jié)點間根 據(jù)一階鄰域系統(tǒng)或者二階鄰域系統(tǒng)生成邊，再將邊按權(quán)重排序后，判斷每條邊是 否屬于不同的生成子樹，計算量很大。121221223334545345（a）（b）（c）（d） （e）圖 210 G2 的生成過程使用最小生成樹方法分割圖像得到一個森林，森林中包含多棵最小生成樹，每棵樹是由連通節(jié)點構(gòu)成的集合，對應(yīng)著圖像中性質(zhì)相似的像素形成的同質(zhì)區(qū)域，一棵樹代表著分割出的一個目標。算法步驟：Step1：設(shè)T = (V , E’)為所求的最小生成樹，V 為頂點集合，E’初始值為空；Step2：把圖G 的邊按權(quán)重由小到大非降序排列， 即讓 w( e1 ) ≤ w( e2 ) ≤ ≤ w( em ) ， m 為邊的數(shù)目；Step3：選取權(quán)重最小邊，如果邊的兩個頂點分屬于不同的生成子樹，則將兩棵子樹合成一棵；Step4：如果邊的兩個頂點屬于相同的生成子樹，則放棄該邊；Step5：重復(fù)步驟 3，直到T 中含有 n ?1條邊為止。當選取一條邊時，若它的頂點分屬不同的集合，則表明此邊連通了兩個不同的連通分量，因每個連通分量無回路，加入這條邊后仍不會產(chǎn)生回路，可以保留這條邊，將它頂點所在的兩個集合合并為一個。Kruskal 算法的關(guān)鍵在于判斷要加入的邊與生成樹中已存在的邊是否形成回路，可以將頂點劃分到不同的集合中，每個集合中的頂點表示一個無回路的連通分量。不同方法使用不同的策略，按權(quán)重選擇特定的邊構(gòu)造最小生成樹，文本采用 Kruskal 算法。 構(gòu)造最小生成樹求解加權(quán)無向圖最小生成樹問題的方法有避圈法、破圈法、Sollin 算法、Dijkstra 算法等。無論G有多少棵生成樹，最小生成樹只能是圖 43 所示的G2 。 G1 和G2都包含五個頂點和四條邊，所有頂點連通且沒有回路，符合生成樹的概念，但是只有G2 是G 的最小生成樹。w(T ) = ∑ w(u , v)（220）( u , v ) ?T其中，w(T ) 表示一顆生成樹的權(quán)重，(u , v) 是G 中的一條邊，w(u , v) 是(u , v)上的權(quán)重，最小生成樹即 w(T ) 值最小的生成樹。同一個圖可以有不同的生成樹，但是 n 個頂點的連通圖的生成樹必定含有 n ?1條邊。最小生成樹分割方法能夠獲取圖像的全局特征，不僅分割效果好，算法簡單，而且計算速度快，可以使用很多成熟的圖論理論和算法進行圖像分割。文獻[46]提出一種新的圖論聚類，建立顯性集與標準單形的二次極17值間的關(guān)系,[47]構(gòu)造 P 矩陣,對 P 矩陣進行遞歸投影,使 P 矩陣顯示類別信息，既不需要事先定義門限，也不需要聚類數(shù)量的先驗知識,可以自動生成多類劃分。有實驗表明，Isoperimetric Ratio 切割方法在遞歸次數(shù)、算法穩(wěn)定性、抗噪性和圖像分割質(zhì)量方面，都比 Normalized Cut 方法優(yōu)良，不但大幅降低了算法的復(fù)雜性，而且適用于大尺度圖像的分割，分割速度較快。Isoperimetric Ratio 切割方法的目的是在| ?S |和VolS 之間找到一個使 hG 最小的平衡點，但是求解等周集問題是一個 NP 問題，需將它轉(zhuǎn)換成可以線性方程求解的最優(yōu)化問題。inf 表示S下確界，在有限頂點的圖中，可以使用最小值代替下確界。由于 assoc ( A, V ) 表示 A 中所有節(jié)點和V 中所有節(jié)點連接邊的權(quán)值之和，當 A中只包含一個節(jié)點時， assoc ( A, V ) 的值很小，即計算 Ncut 時有一個分母很小，這不符合計算最小 Ncut 值的要求，因此不會出現(xiàn)偏向單個節(jié)點的劃分，但是當類間重疊較大時，容易出現(xiàn)歪斜劃分。則圖G 的 Laplacian 矩陣定義為:L (G ) = D (G ) ? A(G)（212）令 n =| V |， x 是一個 n 的指示向量， xi =1 表示節(jié)點i 在 A中， xi= ?1表示節(jié)點i 在 B 中，令W 為 n n 對稱矩陣， 且W (i , j ) = wi , j ，d i = ∑w(i , j) ，D 為j對角矩陣且 D(i , i ) = di ， k = ∑ d i/ ∑di ， I 為全 1 的 n 1向量，則：xi 0iNcut ( x) =(1 + x)T ( D ? W )(1 + x )+ (1 ? x )T ( D ? W )(1 ? x)（213）4 kI T DI4(1 ? k ) I T DI若令b =k， y = (1 + x ) ? b (1 ? x) ，則1+ k2Ncut ( x) = miny T ( D ?W ) y（ y (i ) ∈{1, ?b}，y T DI = 0 ）（214）yy T Dy其中 1 表示元素全為 1 的 N 1向量，如果 y 的取值限制為實數(shù)，那么求解最優(yōu)值問題相當于一個求解一般的特征值問題：( D ? W ) y = λDy（215）用 y 作指示向量，使用特征方程的第二個最小的特征值所對應(yīng)的特征向量作為問題的解，這個特征向量稱為 Fiedler 向量，由 Fielder 最先用來分割圖，它代表最佳劃分圖的一個解。設(shè) G = (V , E) ，其鄰接矩陣定義為 A(G ) = ( auv ) ，若u 和v 相鄰，則 auv =1， 若 u 和v 不相鄰，則 auv = 0 。 Normalized Cut 方法J. Shi 和 [28]提出了 Normalized Cut 方法，定義分割準則:Rcut ( A, B) =cut ( A, B )+cut ( A, B)(211）assoc ( A, V )assoc ( B , V )其中 assoc ( A, V ) = ∑ w(u , v) ，表示 A 中所有