【正文】 45345（a）（b）（c）（d） （e）圖 210 G2 的生成過程使用最小生成樹方法分割圖像得到一個(gè)森林，森林中包含多棵最小生成樹，每棵樹是由連通節(jié)點(diǎn)構(gòu)成的集合，對(duì)應(yīng)著圖像中性質(zhì)相似的像素形成的同質(zhì)區(qū)域，一棵樹代表著分割出的一個(gè)目標(biāo)。通過最小生成樹方法可以獲得圖像的全局特征，但它存在幾個(gè)缺點(diǎn)：1. 計(jì)算量大。如果分割尺寸較大的圖像，每個(gè)像素轉(zhuǎn)變?yōu)楣?jié)點(diǎn)，節(jié)點(diǎn)間根 據(jù)一階鄰域系統(tǒng)或者二階鄰域系統(tǒng)生成邊，再將邊按權(quán)重排序后，判斷每條邊是 否屬于不同的生成子樹，計(jì)算量很大。 2. 閾值選擇不確定。最小生成樹方法不能將整幅圖像生成一棵樹，針對(duì)圖 像中的多個(gè)目標(biāo)，需要生成多棵最小生成樹，因此需要選取閾值，將邊上權(quán)重與 閾值比較，當(dāng)權(quán)重大于閾值時(shí)，停止構(gòu)造最小生成樹。如果閾值較小，構(gòu)造過程 停止太早，就會(huì)產(chǎn)生錯(cuò)誤分割的現(xiàn)象。 3．容易受噪聲和細(xì)節(jié)影響。如果在圖像中存在噪聲和細(xì)節(jié)，對(duì)應(yīng)的像素及鄰域會(huì)生成獨(dú)立的最小生成樹，成為冗余的區(qū)域，需要設(shè)定較高的閾值才能將它合并到其他區(qū)域，影響了閾值的合理選擇，降低了分割質(zhì)量。20 本章小結(jié)本章首先介紹了圖論中的基本概念（圖、加權(quán)圖、連通圖、子圖、補(bǔ)圖、割、鄰接矩陣和圖的最優(yōu)分割準(zhǔn)則）和圖像分割中的基本概念（圖像到圖的轉(zhuǎn)化，權(quán)函數(shù)，像素的鄰域系統(tǒng)和圖像的最優(yōu)分割準(zhǔn)則），然后介紹了三種常見的基于圖論的圖像分割方法，Ratio Cut 方法、Normalized Cut 方法、Isoperimetric Ratio 方法，給出了三種方法的分割思想和分割準(zhǔn)則，最后介紹了最小生成樹方法的概念和構(gòu)造過程，指出這種方法存在的的優(yōu)點(diǎn)和缺點(diǎn)。21第三章 基于數(shù)學(xué)形態(tài)學(xué)分水嶺算法數(shù)學(xué)形態(tài)學(xué)（Mathematical Morphology）誕生于 1964 年，由法國巴黎礦業(yè)學(xué)院博士生 在 指導(dǎo)下做巖相學(xué)分析時(shí)提出“擊中/擊不中變換”，建立了紋理分析器原型。1975 年，Matheron 的《隨機(jī)集和積分幾何》奠定了數(shù)學(xué)形態(tài)學(xué)基礎(chǔ)，1982 年 Serra 的《圖像分析和數(shù)學(xué)形態(tài)學(xué)》標(biāo)志著數(shù)學(xué)形態(tài)學(xué)理論趨于成熟。后來人們將數(shù)學(xué)形態(tài)學(xué)作為工具，從圖像中提取對(duì)于表達(dá)和描繪區(qū)域形狀有用的圖像分量，例如邊界、骨架、凸殼等。數(shù)學(xué)形態(tài)學(xué)的基本思想是用具有一定形態(tài)的結(jié)構(gòu)元素“探針”去量度和提取圖像中的信息，當(dāng)“探針”在圖像中不斷移動(dòng)時(shí)，可以考察圖像各部分之間的關(guān)系，從而了解圖像的結(jié)構(gòu)特征，達(dá)到對(duì)圖像分析和識(shí)別的目的。作為“探針”的結(jié)構(gòu)元素，可以攜帶形態(tài)、大小、灰度等信息。數(shù)學(xué)形態(tài)學(xué)所用的語言是集合論，集合表示圖像中的不同對(duì)象，因此它具有完備的數(shù)學(xué)基礎(chǔ)，為形態(tài)學(xué)用于圖像分析和處理、形態(tài)濾波器的特性分析和系統(tǒng)設(shè)計(jì)奠定了堅(jiān)實(shí)的基礎(chǔ)。數(shù)學(xué)形態(tài)學(xué)的算法具有天然的并行實(shí)現(xiàn)的結(jié)構(gòu)，可以提高圖像分析和處理的速度[4]。目前，數(shù)學(xué)形態(tài)學(xué)已經(jīng)成為圖像處理領(lǐng)域中的一種重要理論和方法，它可以適用于與圖像處理有關(guān)的各個(gè)方面，例如細(xì)胞顯微圖像分析，核磁共振圖像（MRI）識(shí)別，郵政信件自動(dòng)分揀，印刷電路板檢測，汽車運(yùn)動(dòng)情況監(jiān)測等。在圖像分割、特征抽取、邊界檢測、 圖像濾波、圖像增強(qiáng)等圖像處理過程中，基于數(shù)學(xué)形態(tài)學(xué)的技術(shù)和方法都發(fā)揮了重要作用，并且不斷地進(jìn)步和發(fā)展。 形態(tài)學(xué)圖像處理形態(tài)學(xué)技術(shù)可以從圖像中提取某些感興趣的特征，在圖像描繪方面也具有重要作用，成為在許多應(yīng)用領(lǐng)域中建立圖像分割方法的基礎(chǔ)。數(shù)學(xué)形態(tài)學(xué)有四種基本操作：膨脹、腐蝕、開操作和閉操作，四種操作可以組合成不同的算法，應(yīng)用在二值圖像和灰度圖像中。 基本概念集合 A與 B 的并集C ：C = A ∪ B集合 A與 B 的交集C ：C = A ∩ B22集合 A與 B 不相容： A ∩ B = ?? ?ww = ? a , a ∈ A集合 A的反射 A： A ={}集合 A平移到點(diǎn) z = ( z1 , z2 ) ，表示為( A)z ：( A) z = { c c = a + z , a ∈ A} 灰度圖像中的基本操作輸入圖像函數(shù) f ( x , y) ，結(jié)構(gòu)元素b ( x , y) 是一個(gè)子圖像函數(shù)， Z 表示實(shí)整數(shù) 集合，( x, y) 是來自 Z Z 的整數(shù)， f 和b 是對(duì)每一個(gè)( x, y) 坐標(biāo)賦以灰度值的函 數(shù)。（1）膨脹用b 對(duì)函數(shù) f 進(jìn)行膨脹，表示為 f ⊕b ，定義為：f ⊕ b ( s , t ) = max {f ( s ? x , t ? y ) ( s ? x ),(t ? y ) ∈ D f 。( x , y ) ∈ Db} （31）其中，Df 和 Db 分別是 f 和b 的定義域，在每個(gè)結(jié)構(gòu)元素的位置上，膨脹值是在跨度為b 的區(qū)間內(nèi) f 與b 之和的最大值，在用膨脹操作處理灰度圖像后，如果所有結(jié)構(gòu)元素的值為正，輸出圖像會(huì)比輸入圖像更亮。（2）腐蝕灰度腐蝕表示為 f Θb ，定義為：f Θb ( s , t ) = min {f ( s + x , t + y ) ? b ( x , y ) ( s + x ),(t + y ) ∈ D f 。( x , y ) ∈Db}（32）其中，Df 和 Db 分別是 f 和b 的定義域，平移參數(shù)( s + x) 和(t + y) 必須在 f的定義域內(nèi)，而 x 和 y 必須在b 的定義域內(nèi)。腐蝕操作是以在結(jié)構(gòu)元素形狀定義的區(qū)域中選取 ( f ?b) 最小值為基礎(chǔ)的，在用腐蝕操作處理灰度圖像后，如果所有的結(jié)構(gòu)元素都為正，輸出圖像會(huì)比輸入圖像更暗，在輸入圖像中亮的細(xì)節(jié)的面積如果比結(jié)構(gòu)元素的面積小，則亮的效果要削弱。（3）開操作用結(jié)構(gòu)元素b 對(duì)圖像 f 進(jìn)行開操作，表示為 f b ，定義為：f b = ( f Θb ) ⊕b （33）開操作先用b 對(duì) f 進(jìn)行腐蝕操作，這樣可以除去小的圖像細(xì)節(jié)，但會(huì)使圖像變暗；然后用b 對(duì)前面的結(jié)果進(jìn)行膨脹操作，這會(huì)增強(qiáng)圖像的亮度，但不會(huì)將腐蝕操作除去的部分加入圖像。在實(shí)際應(yīng)用中，開操作常用于除去較小的明亮細(xì)節(jié)，23同時(shí)相對(duì)地保持整體的灰度級(jí)和較大的明亮區(qū)域不變。（4）閉操作用結(jié)構(gòu)元素b 對(duì)圖像 f 進(jìn)行閉操作，表示為 f ?b ，定義為：f ? b = ( f ⊕ b ) Θb（34）閉操作先用b 對(duì) f 進(jìn)行膨脹操作，可以除去圖像中的暗細(xì)節(jié)，同時(shí)增加圖像的亮度；然后用b 對(duì)前面的結(jié)果進(jìn)行腐蝕，但不會(huì)將膨脹操作除去的部分重新引入圖像。在實(shí)際應(yīng)用中，閉操作常用于除去圖像中的暗細(xì)節(jié)部分，而相對(duì)地保持明亮部分不受影響。 灰度級(jí)形態(tài)學(xué)的應(yīng)用（1）邊緣檢測很多邊緣檢測算子對(duì)噪聲敏感，而且會(huì)在檢測邊緣時(shí)加強(qiáng)噪聲，基于形態(tài)梯度的邊緣檢測，和其他邊緣檢測算子一樣對(duì)噪聲敏感，但是不會(huì)加強(qiáng)噪聲?；镜男螒B(tài)梯度可定義為：g = ( f ⊕ b ) ? ( f Θb)（35）這種形態(tài)學(xué)梯度使輸入圖像中灰度級(jí)的躍變更為劇烈，不會(huì)加強(qiáng)噪聲，但可能含有噪聲，因此有另外一種梯度定義，可以對(duì)孤立的噪聲點(diǎn)不敏感：g = min{[( f ⊕ b ) ? f ],[ f ? ( f Θb)]}（36）這種梯度檢測不出理想階梯邊緣，但是檢測理想斜面邊緣效果很好。（2）粒度測定粒度測定主要是判斷圖像中顆粒的尺寸分布問題，可以逐漸從小到大使用不同的結(jié)構(gòu)元素對(duì)輸入圖像進(jìn)行開操作，因?yàn)楫?dāng)以某一特定尺寸對(duì)含有相近尺寸顆粒的圖像區(qū)域進(jìn)行開操作，處理效果最好。每次使用不同尺寸的結(jié)構(gòu)元素處理后，可以計(jì)算出與輸入圖像之間的差異，將這些差異進(jìn)行歸一化處理，得到顆粒尺寸分布直方圖。這種粒度測定對(duì)于檢測帶有某一主要類似顆粒狀的區(qū)域效果較好。除了以上的應(yīng)用，在圖像平滑處理中，形態(tài)學(xué)可以除去人為的亮或暗的因素或噪聲，對(duì)圖像進(jìn)行 tophat 變換，可以增強(qiáng)陰影細(xì)節(jié)，還有紋理分割、圖像描繪方面，形態(tài)學(xué)都成為應(yīng)用基礎(chǔ)。24 分水嶺算法 分水嶺概念分水嶺變換是一種形態(tài)學(xué)的圖像分割方法，其基本思想是將圖像看成地形表面，每個(gè)像素的值代表該點(diǎn)的海拔高度，其中包含一些局部最小值的點(diǎn)，讓水滴在某個(gè)位置落下，能夠落到一個(gè)單一最小值點(diǎn)上的位置的集合稱為這個(gè)最小值的“分水嶺”，若水滴等概率地流向不止一個(gè)這樣的最小點(diǎn)，水滴位置的集合稱為“分水線”。分水嶺算法的主要目標(biāo)是找出分水線，方法有兩種：（1）模擬降水過程。將圖像想象成 3D 地形，因?yàn)橄袼刂涤懈哂械?，地形呈現(xiàn)高低起伏的山脈和盆地的形態(tài)。模擬降水過程，當(dāng)雨滴落到山地模型上時(shí)，將沿著山坡流向谷底，雨滴所經(jīng)過的路線就是一個(gè)連通分支，而通往同一谷底的所有連通分支形成了一個(gè)匯水盆地。（2）模擬浸水過程。Beucher 和 Lantuejoul[49]最先提出了模擬浸水過程的分水嶺算法，將圖像中每個(gè)像素值看成海拔高度，在這個(gè)模型中，存在很多的盆地和山脈，將每個(gè)盆地的最低點(diǎn)打一個(gè)洞，模型慢慢浸入水中，盆地就會(huì)成為積水盆地，漲高的水漸漸漫過盆地，當(dāng)兩個(gè)盆地的水將要匯合時(shí)，為了阻止水的匯合，需要在山脈上筑起大壩，整個(gè)浸水過程在全部山脈都被水浸沒后結(jié)束。最終在圖像上形成一些輪廓線，將圖像中相似的部分包圍起來，形成分割圖像的效果。分水嶺地形模型見圖 31 所示。（a） （b）圖 31 分水嶺地形模型降水及浸水過程如圖 32 及圖 33 所示。25局部最小值圖 32 降水過程剖析圖 圖 33 浸水過程剖析圖圖 32 描述的是模擬降水過程的分水嶺算法，每個(gè)盆地由局部最小值區(qū)分，當(dāng)雨滴降落的位置是山坡時(shí)，將會(huì)沿著山坡流到谷底，如果它可以流向的盆地只有一個(gè)，降落的位置就是屬于這一個(gè)盆地的區(qū)域，如果它可以流向的盆地不止一個(gè)，降落的位置就屬于分水線。圖 33 描述的是浸水過程的分水嶺算法，首先找到所有局部最小值，在最小值位置打一個(gè)洞，將模型浸入水中，由最小值位置進(jìn)入的水形成盆地，隨著水位上升，不同盆地間的水將會(huì)匯合，在即將匯合時(shí)建立大壩。 分水嶺分割二值圖像水壩的構(gòu)造以二值圖像為基礎(chǔ)，分水嶺分割的基本過程是連續(xù)腐蝕二值圖像，主要包括三個(gè)步驟[4]：（1）產(chǎn)生距離圖一幅二值圖包括目標(biāo)和背景，若將較大的值賦予接近目標(biāo)內(nèi)部的像素就得到一幅距離圖，距離圖中各個(gè)像素的灰度與該像素到圖像或目標(biāo)邊界成比例。用形態(tài)學(xué)方法產(chǎn)生距離圖時(shí)，可以在每次腐蝕后將剩下的像素值加 1，迭代腐蝕公式為：Ak = AΘkB （37）其中，Ak 的下標(biāo)表示不同次數(shù)的迭代腐蝕。對(duì) k =1,2, m ，Am ≠ ?，m 是非空圖的最大個(gè)數(shù)。（2）計(jì)算腐蝕集合在條件 X 下用 B 對(duì) A進(jìn)行膨脹操作，記為 A ⊕ B 。 X ，定義為：A ⊕ B 。 X = ( A ⊕ B ) ∩ X（38）迭代條件膨脹記為 A ⊕{ B}。 X ，定義為：26A ⊕ { B}。 X = [[[( A ⊕ B ) ∩ X ] ⊕ B ] ∩ X ] ⊕ B（39）其中，{ B} 表示迭代地用 B 對(duì) A進(jìn)行膨脹操作，直到不再有變化。最終腐蝕指反復(fù)腐蝕一個(gè)目標(biāo)直到它消失，此時(shí)保留這之前最后一步的結(jié)果，這個(gè)結(jié)果就是目標(biāo)的種子。最終腐蝕Yi 可以定義為 Ai 中的元素，它的第一步是：U k = ( Ak +1 ⊕{ B})。 Ak（310）第二步是從 A的腐蝕中減去上述膨脹結(jié)果：Yk = Ak ?Uk（311）如果圖像中有多個(gè)目標(biāo)，可求各自Yk的并集，最終腐蝕圖像是：Y = ∪mYk（312）k =1其中， m 是腐蝕的次數(shù)。（3）生長回到原尺寸從種子開始生長回到原尺寸，但不使各區(qū)域相連。設(shè)置模板，將模板中心與包圍種子的像素重合，如果模板中的 0 和 1 與所重合區(qū)域的 0 和 1 匹配，則將該像素賦為 1，即種子區(qū)域在尺寸上增加一個(gè)像素，使用多個(gè)模板將在種子周圍增加一個(gè)像素寬的區(qū)域。這種生長步驟重復(fù)進(jìn)行到結(jié)果不再變化。分水嶺分割可以很好地保持目標(biāo)的原始形狀，在目標(biāo)之間加入的分水線比較清晰，不會(huì)出現(xiàn)間斷的問題。 分水嶺分割梯度圖像對(duì)于一幅原始圖像，先求取梯度圖像 g ( x , y) ， min 和 max 分別表示梯度最小值和最大值，梯度圖像中的局部最小值就是原始圖像中變化最小的區(qū)域，可以看成生長種子。用 M1 和 M 2 表示兩個(gè)局部最小值，C ( M1 ) 和C ( M 2