基于Watershed和Snake混合模型的圖像分割算法

千堃，馬銀平，韓懸

（南昌航空大學(xué)信息工程學(xué)院，南昌330063）

0 引言

分水嶺和蛇模型（主動輪廓模型）是兩種用于圖像分割的經(jīng)典算法，均有其優(yōu)缺點(diǎn)。分水嶺具有創(chuàng)建單像素寬度的封閉邊界的能力，并能夠快速的實(shí)現(xiàn)分割算法[1]。通常，分水嶺算法首先創(chuàng)建一個(gè)梯度圖像，并將圖像視為起伏地形，這樣梯度圖像的每個(gè)最小值在分割結(jié)果中都指向一個(gè)區(qū)域（或集水盆地）。分水嶺算法[2]是一種圖像分割的早期算法，為將形態(tài)學(xué)理論應(yīng)用于圖像分割的算法。近年來，這種方法被廣泛應(yīng)用于圖像分割中，得益于其不同于其他算法的優(yōu)點(diǎn)：在MATLAB仿真下算法的實(shí)現(xiàn)速度快；可以準(zhǔn)確且迅速地捕捉圖像邊緣信息；也兼具良好的輪廓線封閉性。由于分水嶺分割算法在最初的時(shí)候是用于分析和處理二值圖像，因此為了得到更加適用于圖像分割的通用模型，這便使得分水嶺的相關(guān)理論和相關(guān)算法得以建立，后期便大量應(yīng)用于對不同性質(zhì)的圖像實(shí)現(xiàn)精確分割。分水嶺算法的早期階段，由于不能克服圖像的噪聲干擾，會產(chǎn)生過分割等多種不良分割結(jié)果。改進(jìn)的層次分水嶺分割在一定程度上可以克服過分割[3]，但區(qū)域合并過程對水平參數(shù)過于敏感，即感興趣的區(qū)域?qū)ο髸杆俸喜⒌洁徲驅(qū)ο笾?，?dǎo)致分割結(jié)果不理想。Kass等人提出了活動輪廓模型被定義為能量最小化樣條[4]。隨后，基于Snake模型的改進(jìn)模型不斷涌出，常見的有GVF Snake模型[5]、Balloon Snake模型[6]、距離勢力模型[7]、T-Snake模型[8]等。Snake模型[9]通過在感興趣的目標(biāo)周圍區(qū)域布置初始輪廓曲線，建立能量泛函方程，然后曲線在自身機(jī)制能量約束以及圖像力產(chǎn)生的外力作用下，使得該輪廓曲線收斂到目標(biāo)圖像的邊緣，完成圖像的分割，是一種非常經(jīng)典的曲線演化模型。但Snake模型在實(shí)際應(yīng)用中，也有著無法忽視的缺點(diǎn)。例如，初始輪廓必須足夠接近感興趣的物體在圖像區(qū)域內(nèi)的邊界，否則無法得到真實(shí)的收斂結(jié)果。另一個(gè)問題是由于它的內(nèi)部彈性和剛性的力量使其無法收斂到凹陷區(qū)域。GVF Snake模型[10]可以收斂到凹陷區(qū)域，但當(dāng)圖像噪聲較強(qiáng)時(shí)，會產(chǎn)生錯誤的分割，進(jìn)而也不能將圖像分割出來。

因此，為了融合分水嶺變換和Snake模型的優(yōu)點(diǎn)，克服它們的缺點(diǎn)，本文首先利用形態(tài)學(xué)等相關(guān)操作，對圖像采用強(qiáng)制標(biāo)記技術(shù)解決過分割問題。然后得到改進(jìn)之后的分水嶺算法的邊緣曲線，以用于Snake模型的邊緣的初始優(yōu)化，最后采用遺傳算法進(jìn)一步提升對圖像的分割精度，最大程度地保證可以精準(zhǔn)圖像分割。

1 改進(jìn)的分水嶺算法及其優(yōu)化

1.1 傳統(tǒng)的分水嶺算法

分水嶺的思想[11]是根據(jù)地形學(xué)中的思想得到的，是一種通過自上而下采用迭代思想形成區(qū)域的方法。分水嶺算法是結(jié)合地理學(xué)的圖像分割算法，將圖像整體類比為一個(gè)地貌，而圖像中像素的不同灰度值就等同于地形中的海拔值，地貌上存在的極小值及其相關(guān)區(qū)域共同構(gòu)建集水盆，集水盆的邊界便就是分水嶺，如圖1所示。利用地理學(xué)上的類比思想，從表面的局部極小值開始，然后慢慢地將圖像浸入水中，水逐漸淹沒極小值對應(yīng)的盆地，如圖1（a）。為了防止由兩個(gè)不同的極小值引起的兩個(gè)不同的集水盆的合并，便在兩條線之間建立了一個(gè)堤壩，如圖1（b）箭頭所指的位置，一旦地表完全浸沒，所建造的堤壩便是圖像的分水嶺。具體的分水嶺算法實(shí)現(xiàn)思想實(shí)現(xiàn)為：首先求出梯度圖像，隨后將其用于輸入圖像應(yīng)用到分水嶺算法，最后再根據(jù)不同情況調(diào)整參數(shù)，做不同處理。這種早期計(jì)算方法是由L.Vincent[12]提出的。梯度圖像求解公式：

其中，f(x,y)代表圖像，grad(?)為圖像的梯度算子，g(x,y)則表示圖像經(jīng)過梯度算子運(yùn)算后的輸出結(jié)果。

圖1 分水嶺的形成

1.2 改進(jìn)的分水嶺算法

本文采用形態(tài)學(xué)等相關(guān)算法，來克服分割過程中出現(xiàn)的過分割問題。算法流程如下：

（1）使用雙邊濾波去噪并保護(hù)弱邊緣區(qū)域，計(jì)算出梯度幅值圖像。

（2）對處理過的圖像進(jìn)行形態(tài)學(xué)相關(guān)處理。

（3）使用OTSU閾值分割法和灰度調(diào)整對腦腫瘤進(jìn)行前景標(biāo)記。

（4）通過距離變換的分水嶺來實(shí)現(xiàn)背景標(biāo)記。

（5）用相關(guān)函數(shù)修改梯度幅值圖像，使其只在標(biāo)記位置有局部極小值。

（6）分水嶺分割結(jié)果。

算法流程如圖2所示。

圖2 算法流程圖

采用腦腫瘤圖像為測試圖像，驗(yàn)證改進(jìn)的分水嶺算法。結(jié)果如圖3所示。

圖3 實(shí)驗(yàn)結(jié)果對比圖

2 Snake模型的優(yōu)化其傳統(tǒng)Snake模型原理與方法

2.1 傳統(tǒng)Snake模型

Kass首次提出了經(jīng)典的參數(shù)可形變模型（Snake模型）后，Snake模型就被大量學(xué)者廣泛應(yīng)用于圖像分割以及其他領(lǐng)域中。Snake模型的輪廓曲線可定義為形如v(s)=(x(s),y(s)),s∈[0,1]樣條曲線，s表示歸一化弧長參數(shù)，為平面上的坐標(biāo)點(diǎn)。能量函數(shù)約束著樣條曲線的迭代方向，最終收縮在目標(biāo)區(qū)域周圍。Snake模型輪廓曲線的能量函數(shù)可以定義如下：

由上式可知，Snake模型主要由兩部分組成，分別是內(nèi)部能量（內(nèi)部力）Eint和外部能量（外部力）Eext。在實(shí)現(xiàn)Snake模型算法的過程中，由一系列離散的點(diǎn)來控制分割區(qū)域的收束vi(i=1,2,…,N)，將公式（2）離散化后，可得到能量泛函的離散形式，如下所示：

式中，vi-vi-1代表控制點(diǎn)的一階導(dǎo)數(shù)，vi+1-2vi+vi-1代表控制點(diǎn)的二階導(dǎo)數(shù)。將能量泛函Esnake利用歐拉方程離散化求解其最小值，可得下式：

其中，v"(s)為輪廓曲線的二階導(dǎo)數(shù)，v""(s)為輪廓曲線的四階導(dǎo)數(shù)，?Eext為外部力能量梯度。該方程同時(shí)也可看作是一個(gè)能量平衡方程：

式中Fint(s)=αv"(s)-βv""(s)，F(xiàn)ext(s)=-?Eext。

為便于計(jì)算，引入時(shí)間參數(shù)t作為曲線變化的自變量，即v(s)=v(s,t)，公式（5）的解也即可通過下式求解得到：

vt(s,t)為v(s,t)對時(shí)間t求偏導(dǎo)，vt(s,t)=0，表示為曲線基本停止演化，輪廓曲線收縮到目標(biāo)的邊緣區(qū)域，完成了分割圖像。在實(shí)際操作中，為了節(jié)省資源，可以采取人工設(shè)置初始控制點(diǎn)的方式，再對能量函數(shù)進(jìn)行迭代求解。離散Snake模型收斂迭代方程為：

式中，A是五角帶狀矩陣，主要有由α和β兩個(gè)系數(shù)所確定的，I為單位矩陣，γ為步長，F(xiàn)x和Fy分別為外力在x方向和y方向上的偏導(dǎo)數(shù)。通過迭代計(jì)算，可求得演化曲線的最終位置。

為了便于提供一種客觀、可重復(fù)、易使用的分割方法，本文在MATLAB環(huán)境下開發(fā)了一個(gè)GUI軟件平臺，在搭建的GUI界面下，對同一副杯蓋圖像采用Snake模型分割，但初始輪廓不同，迭代相同的次數(shù)N=125，最終迭代結(jié)果如圖4（c）和圖5（c）所示。由迭代結(jié)果可以看出，初始輪廓距離目標(biāo)邊緣越近，獲取的目標(biāo)輪廓越精確。由于Snake模型對初始位置敏感，需手動獲取初始位置點(diǎn)，且對初始位置的獲取具有不確定性，因此本文將結(jié)合分水嶺算法的優(yōu)點(diǎn)，解決Snake模型存在的這一問題，通過改進(jìn)的分水嶺算法對Snake模型的初始輪廓作進(jìn)一步優(yōu)化。

圖4 第一組實(shí)驗(yàn)（α=0.4,β=0.2）

圖5 第二組實(shí)驗(yàn)（α=0.4,β=0.2）

2.2 Snake模型初始輪廓的優(yōu)化

本節(jié)將利用改進(jìn)的分水嶺算法解決Snake模型對初始輪廓線位置敏感的問題，并通過遺傳算法[12-13]優(yōu)化分割結(jié)果，從而實(shí)現(xiàn)精確分割。初始輪廓優(yōu)化算法主要步驟如下：

（1）對圖像采用OTSU閾值分割法自動求出閾值w進(jìn)行分割，得到每個(gè)像素點(diǎn)的灰度fb(x,y)定義為：

（2）用形態(tài)結(jié)構(gòu)元素對（1）得到的結(jié)果圖像作形態(tài)學(xué)開運(yùn)算，得到標(biāo)記函數(shù)為：

此函數(shù)的作用是將標(biāo)記部分的值記為0，非標(biāo)記部分值記為1。

（3）對梯度函數(shù)g用圖像fm(x,y)進(jìn)行強(qiáng)制最小值操作，得到待分割圖像：

該表達(dá)式的含義為，當(dāng)(x,y)為標(biāo)記點(diǎn)時(shí)，fm(x,y)的值為0，對應(yīng)的fmin(x,y)值也為0，反之，當(dāng)(x,y)不是標(biāo)記點(diǎn)時(shí)，fmin(x,y)的值就為梯度函數(shù)g(x,y)。

（4）對fmin(x,y)進(jìn)行分水嶺變換，圖像的區(qū)域邊界便是離散的點(diǎn)：V={V1,V2,…,VL}，V的中點(diǎn)Vi=(Xi,Yi),i={1,2,…,L}是分水嶺變換后確定為分水嶺的點(diǎn)的子集。

將分水嶺變換得到的輪廓線作為Snake模型的初始輪廓線[14-15]，但Snake模型存在對噪聲敏感，模型能量函數(shù)易陷入局部極小值且分水嶺算法分割后得到的輪廓線光滑性較差。因此需要利用遺傳算法進(jìn)行全局優(yōu)化。

2.3 遺傳算法優(yōu)化Snake模型

（1）初始種群的構(gòu)造

在演化好的Snake模型上，其輪廓線由N個(gè)離散點(diǎn){v0,v1,…,vn-1}構(gòu)成，在vi處Snake曲線的法線上，按一定間隔取點(diǎn)，隨機(jī)選中所取得點(diǎn)（i=0,1,...,N-1，這N個(gè)點(diǎn)可視為一個(gè)染色體，重復(fù)M次取點(diǎn)操作，便可得到M個(gè)染色體組成的一個(gè)種群，每一條染色體包含的節(jié)點(diǎn)個(gè)數(shù)都相同。

（2）適應(yīng)度函數(shù)

將Snake能量函數(shù)作為目標(biāo)函數(shù)：

其 中，λ∈[0,1],vi=(xi,yi),i=1,2,…,N代 表 了Snake模型曲線上的各個(gè)離散點(diǎn)。為了使Snake模型的分割結(jié)果更加接近真實(shí)邊界以及輪廓曲線更加光滑，在此增加一項(xiàng)外部能量。

最后可將適應(yīng)度函數(shù)定義為：

其中M'足夠大，保證M'-E>0。在選取的初始種群和適應(yīng)度函數(shù)的基礎(chǔ)上，對種群進(jìn)行變異、交叉、選擇等基本遺傳算法操作，隨后進(jìn)行最優(yōu)迭代，直到得到最優(yōu)的分割結(jié)果。

3 實(shí)驗(yàn)結(jié)果和評價(jià)

為了對上述改進(jìn)算法的驗(yàn)證，本文隨機(jī)選取了三幅特征不同的圖片作為本文的驗(yàn)證圖，分別為圓、復(fù)雜的腦腫瘤圖像和五角星圖像，見圖6。本文實(shí)驗(yàn)驗(yàn)證的平臺為Windows 7下的MATLAB R2014a軟件，三組實(shí)驗(yàn)中參數(shù)的取值為：彈性力系數(shù)：α=0.4，剛性力系數(shù)：β=0.2，步長：γ=1，傳統(tǒng)的Snake模型分割算法迭代次數(shù)：N1=200，本文改進(jìn)的分割算法迭代次數(shù)：N2=50，種群大小：M=50，交叉概率：Pc=0.1，變異概率：Pm=0.02。

圖6 實(shí)驗(yàn)驗(yàn)證用圖

3.1 實(shí)驗(yàn)1仿真結(jié)果及分析

對于較規(guī)則的圓形圖，從圖7（b）可看出，傳統(tǒng)Snake模型的收斂效果也不是很理想；用改進(jìn)的分水嶺算法結(jié)合Snake模型后，便可以得到較好的分割結(jié)果，仿真結(jié)果如圖7（d）；用遺傳算法優(yōu)化上一步的結(jié)果，能夠得到如圖7（e）所示的分割圖。

3.2 實(shí)驗(yàn)2仿真結(jié)果及分析

對于較復(fù)雜的醫(yī)學(xué)圖像圖8（a）而言，當(dāng)初始輪廓線不在目標(biāo)邊緣附近時(shí)，傳統(tǒng)的Snake模型無法收斂到目標(biāo)邊緣，如圖8（b）；結(jié)合分水嶺算法后的結(jié)果如圖8（d），可以看出分割精度大大改善；再進(jìn)一步優(yōu)化后的結(jié)果更為理想，如圖8（e）。

3.3 實(shí)驗(yàn)3仿真結(jié)果及分析

傳統(tǒng)的Snake模型對于不規(guī)則圖像的分割效果很不理想，如圖9（b）；結(jié)合分水嶺后的分割結(jié)果有了大大的改進(jìn)，但對于拐角點(diǎn)處的部分，收斂效果也不是很理想，如圖9（d）；最后使用遺傳算法優(yōu)化，分割效果有了較好的改進(jìn)，如圖9（e）。

為了對三種模型的分割效果有個(gè)直觀的認(rèn)識，引入TP（精度）、FP（誤檢率）、FN（漏檢率）以及平均分割時(shí)間t對分割結(jié)果進(jìn)行定量評估，評估結(jié)果如表1所示。從表中數(shù)據(jù)可以看出，本文所提出的混合模型分割算法，與Snake模型、改進(jìn)的分水嶺模型相比，具有更高的分割精度和更低的漏檢率、誤檢率。

圖7 圓仿真結(jié)果

圖8 腦腫瘤仿真結(jié)果

圖9 五角星仿真結(jié)果

表1 三種模型的分割結(jié)果對比

4 結(jié)語

分水嶺算法可以提供精確的單像素寬度的閉合輪廓，但其主要難點(diǎn)是過度分割。Snake模型可以動態(tài)得確定目標(biāo)邊界區(qū)域，但其存在著捕獲范圍窄，收斂性差的問題。分水嶺算法可以為Snake模型的演化提供初始輪廓，引導(dǎo)Snake模型向著目標(biāo)邊界移動。因此，結(jié)合Snake模型和分水嶺算法的優(yōu)缺點(diǎn)，使其互補(bǔ)，經(jīng)過不斷改進(jìn)，得到最優(yōu)的混合算法。本文提出的混合邊界檢測算法驗(yàn)證了兩種算法結(jié)合的好處：第一，提高了傳統(tǒng)Snake模型的捕獲范圍和緩解了Snake模型對初始輪廓敏感以及不能收斂到凹陷區(qū)域的缺點(diǎn)。第二，通過利用遺傳算法進(jìn)行優(yōu)化，提高了分割的精度，傾向于生成精確的目標(biāo)輪廓；第三，混合算法迭代次數(shù)少，因?yàn)榉炙畮X輪廓已經(jīng)在感興趣目標(biāo)的附近位置。但加入了遺傳算法的優(yōu)化后，會使得分割時(shí)間過長，還需要進(jìn)一步研究以解決這一步問題。