孟少波，惠小強

(1.西安郵電大學(xué) 理學(xué)院,陜西 西安 710121；2.西安郵電大學(xué) 物聯(lián)網(wǎng)與兩化融合研究院，陜西 西安 710061)

用小波變換改進的分水嶺圖像分割算法

孟少波1，惠小強2

(1.西安郵電大學(xué) 理學(xué)院,陜西 西安 710121；2.西安郵電大學(xué) 物聯(lián)網(wǎng)與兩化融合研究院，陜西 西安 710061)

分水嶺分割方法雖然是一種有效且常用的圖像分割方法，但它容易產(chǎn)生過分割現(xiàn)象且對噪聲非常敏感。為克服這一問題，文中結(jié)合小波變換提出了一種改進的分水嶺算法。首先利用小波分解變換對形態(tài)學(xué)梯度圖像進行二層分解去噪，通過設(shè)置閾值向量對高頻小波系數(shù)進行閾值處理，重構(gòu)二維小波；利用形態(tài)學(xué)標記前景和背景的技術(shù)，結(jié)合重構(gòu)的二維小波，得到新的僅在前景和后景標記位置有極小值的分割函數(shù)。最后，在修改后的梯度圖像上進行分水嶺變換，從而取得良好的圖像分割效果。

小波變換；分水嶺圖像分割；圖像梯度；小波二層分解去噪

0 引 言

圖像分割是圖像處理的重要環(huán)節(jié)，也是圖像處理的難點之一[1]。它是指利用區(qū)域間的相似性把圖像分割成具有不同特點的區(qū)域并分離提取出目標區(qū)域的過程[2]。圖像分割結(jié)果的優(yōu)劣直接影響到后續(xù)圖像分析理解以及景物恢復(fù)問題求解的正確與否。圖像分割技術(shù)與物理學(xué)、計算機科學(xué)、醫(yī)學(xué)、光電子等學(xué)科的發(fā)展密切相關(guān)。隨著這些學(xué)科的進步，人們提出了許多結(jié)合特定理論方法和工具的分割技術(shù)。目前有上千種圖像分割算法，但尚沒有判定分割效果的通用的分割算法或評判標準[3]。分水嶺圖像分割算法是一種較常用的分割方法。

研究表明，分水嶺圖像分割算法存在3個缺點：

(1)對噪聲敏感。原因是圖像以梯度作為分割函數(shù)輸入，而原圖噪聲直接影響圖像的梯度，導(dǎo)致分割區(qū)域輪廓失真；

(2)易產(chǎn)生過分割。原因是噪聲、量化誤差以及區(qū)域內(nèi)細小紋理等會產(chǎn)生大量局部最小值，以致后續(xù)分割中出現(xiàn)大量微小的積水盆地；

(3)對比度較低的圖片容易丟失重要輪廓。原因是對比度較低時，區(qū)域邊界像素的梯度值會更低，從而引起部分輪廓丟失[4]。

近幾年，預(yù)處理、濾波、標記以及區(qū)域合并等許多改進方法被相繼提出。這些改進方法都是以減少局部最小值的產(chǎn)生為目的[5]，減少小的積水盆地從而減少過分割區(qū)域，抑制過分割。

文中針對分水嶺算法對噪聲非常敏感，且容易產(chǎn)生過分割的缺點，提出了一種利用小波變換改進的分水嶺圖像分割算法。該算法能有效地抑制過分割現(xiàn)象，對含噪圖像也能取得較好的分割效果。

1 圖像處理

1.1 圖像梯度的計算

通過對圖像進行梯度運算來實現(xiàn)邊緣信息的獲取。由于梯度圖像具有邊緣增長特征，圖像灰度在梯度方向變化率最大，這恰好可反映出圖像邊緣上的信息變化[6]。

常用圖像梯度可通過函數(shù)求導(dǎo)、中值差分、線性濾波法以及形態(tài)學(xué)方法表示[7]。

文中采用形態(tài)學(xué)方法來表示梯度。設(shè)圖像為f(x,y)，B為結(jié)構(gòu)元素，數(shù)學(xué)形態(tài)學(xué)的腐蝕和膨脹定義如下[8]：

(f?b)(x,y)=max{f(x-x',y-y')+B(x',y'):(x',y')∈B}

(1)

(f°b)(x,y)=min{f(x+x',y+y') -B(x',y'):(x',y')∈B}

(2)

f(x,y)的數(shù)學(xué)形態(tài)學(xué)梯度為：

(3)

1.2 利用小波變換對圖像進行二層分解

小波函數(shù)是對給定函數(shù)局部化的函數(shù)，它可由一個定義在有限區(qū)間的函數(shù)Ψ(x)來構(gòu)造。Ψ(x)稱為母小波(motherwavelet)或者基本小波[9]。一組小波基函數(shù){Ψa,b(x)}，可通過縮放和平移基本小波Ψ(x)來生成。

其中：a為縮放參數(shù)，用于反映特定基函數(shù)的寬度(或者叫做尺度)；b為進行平移的平移參數(shù)，用來指定沿x軸平移的位置。

A.Grossman和J.Morlet指出，連續(xù)小波變換為[10]：

(4)

小波去噪通過變換得到分解系數(shù)。設(shè)定一個閾值，對閾值兩端的系數(shù)分別進行不同的處理，然后利用處理后的小波系數(shù)重構(gòu)出消噪后的圖像[11]。文中采用MATLAB中的小波函數(shù)coif2來實現(xiàn)圖像的二層分解。

[c,l]=wavedec2(X,2,'coif2')

(5)

其中：l標記由高到低的各級長度；X表示要處理的圖像；2表示分解層數(shù)。

n=[a,b]

(6)

p=[d,e]

(7)

nc=wthcoef2('h',c,l,n,p,'s')

(8)

X'=waverec2(nc,l,'coif2')

(9)

其中，n表示尺度向量；p表示設(shè)置閾值向量；式(8)表示對高頻小波系數(shù)進行閾值處理；式(9)表示對圖像進行二維小波重構(gòu)。

小波二次分解去噪的步驟如下：

(1)用小波函數(shù)對梯度圖像進行二層分解；

(2)設(shè)置尺度向量、閾值向量，對高頻小波系數(shù)進行閾值處理；

(3)對梯度圖像進行小波重構(gòu)；

(4)第二次對高頻小波系數(shù)進行閾值處理；

(5)第二次對梯度圖像進行小波重構(gòu)。

2 分水嶺算法的改進

2.1 算法原理

分水嶺的數(shù)學(xué)定義最早出現(xiàn)在文獻[12]中：

圖像用G=(D,E,I)三項式來表示。其中，I：D→N是每個像素p∈D對應(yīng)的轉(zhuǎn)換函數(shù)，D是轉(zhuǎn)換函數(shù)所對應(yīng)的定義域，E是D×D中所有點距離的集合，I(p)是圖像的灰度值。

定義1：圖像I中閾值為h的水平集為Th={p∈D|I(p)≤h}。

設(shè)Γ?E，并且E=Rd或E=Zd，其中a，b兩點存在于Γ中，則測量距離dΓ(a,b)表示在點a和點b之間最短的可能路徑。

定義2：在Γ中，子集Bi的測量影響區(qū)域為iZΓ(Bi,B)={p∈Γ|dΓ(p,Bi)

定義4：在Γ中，集合iZΓ(B)的補集稱為SKIZ，SKIZΓ(B)=ΓiZΓ(B)。

所以SKIZ由所有距離相等(與該像素點距離最近的連通區(qū)域，至少有兩個區(qū)域都是距離最短且相等)的像素點組成。在灰度圖像I：D→N中，hmin和hmax為I的最小和最大灰度值。灰度h從hmin迭代到hmax的過程中，I的最小點區(qū)域逐漸擴大。設(shè)Xh為水平值取h時所計算出的各區(qū)域集合的聯(lián)合。水平值為h時，在閾值集合Th+1中計算側(cè)地影響區(qū)域可推導(dǎo)出Xh+1。在高灰度為h時，設(shè)MINk為所有最小區(qū)域的聯(lián)合。

在Γ中，SKIZ可以通過確定前景像素集合B來確定。定義如下的迭代式：

定義5：在集合D，Xhmax的補集就是分水嶺的區(qū)域。

watershed(f)=D/Xhmax

(10)

2.2 算法改進

分水嶺算法借鑒形態(tài)學(xué)理論而生成。在該算法中圖像被看作一個拓撲圖，灰度值I(p)的大小對應(yīng)地形的高低。水在沒有阻礙時總是朝地勢低的方向流動，在某一局部低洼處慢慢匯集，該低洼處稱為吸水盆地。吸水盆地之間的山脊稱為分水嶺。圖像梯度的方向總是從灰度大的區(qū)域指向灰度小的區(qū)域，這與水向低洼處匯集相似。故在圖像分割時可以借鑒，在灰度圖像中找出不同的灰度梯度的吸水盆地和分水嶺，它們組成的區(qū)域即為要分割的目標[4]。圖1為分水嶺示意圖。

圖1 分水嶺示意圖

在運用分水嶺分割算法時，假設(shè)待分割的圖像由目標和背景組成。由于圖像梯度能夠反映出邊緣的變化，所以低、高灰度區(qū)域能夠很好地被區(qū)分開來。圖像中的背景和目標內(nèi)部區(qū)域?qū)?yīng)梯度圖像中的低灰度區(qū)(暗區(qū)域)，目標邊緣對應(yīng)梯度圖中的高灰度區(qū)(亮區(qū)域)。梯度圖像中具有均勻低灰度值的區(qū)域為極小值區(qū)域。水面從這些極小值區(qū)域開始上漲，當不同吸水盆地中的水面升高到將要溢出時，便筑起一道堤壩(分水嶺)，最后得到由這些壩筑成的分水線，圖像分割完成。為獲得圖像的邊緣信息，通常把梯度圖像作為輸入[13]，消除分水嶺算法產(chǎn)生的過度分割可采用先驗知識去除無關(guān)邊緣信息或是修改梯度函數(shù)減少小的積水盆地[14]。后一種方法較常用：先對梯度函數(shù)進行重構(gòu)，獲得適量的區(qū)域，再對這些區(qū)域邊緣點的灰度由低到高排序，最后從低到高實現(xiàn)淹沒過程[15]。

文中利用小波變換修改梯度函數(shù)減少小的積水盆地來改進分水嶺算法。通過對圖像的形態(tài)學(xué)梯度進行小波變換和二層分解去噪，設(shè)置閾值向量對高頻小波系數(shù)進行閾值處理，重構(gòu)二維小波；在重構(gòu)小波的基礎(chǔ)上利用形態(tài)學(xué)標記前景和背景的技術(shù)，得到修改后的僅在前景和后景標記位置有極小值的分割函數(shù)；最后在修改后的梯度圖像上進行分水嶺變換，得到較好的圖像分割效果。

在MATLAB中進行圖像處理時的步驟如下：

Step1：讀入數(shù)據(jù)，利用式(3)得到圖像的形態(tài)學(xué)梯度；

Step2：用式(5)對Step1得到的梯度圖像進行二層分解；

Step3：用式(6)、(7)、(8)分別設(shè)置尺度向量、閾值向量，對高頻小波系數(shù)進行閾值處理；

Step4：對圖像進行小波重構(gòu)；

Step5：繼續(xù)執(zhí)行Step3、Step4進行二次重構(gòu)；

Step6：在小波重構(gòu)的基礎(chǔ)上利用形態(tài)學(xué)標記前景和背景的技術(shù)，得到修改后的分割函數(shù)梯度；

Step7：利用式(10)對修改后的梯度函數(shù)進行分水嶺分割。

3 結(jié)果及分析

3.1 實驗數(shù)據(jù)

圖2和圖3分別是不含噪聲的Nut和Lena圖像處理結(jié)果。

從圖2觀察來看，經(jīng)過消噪后圖像邊緣信息變化更加明顯；(e)、(g)很好地將Nut圖形進行分割，較好地提取出Nut的特征，保留其重要的邊緣信息，而(f)中過分割區(qū)域數(shù)量太多，分割效果差。

圖3 Lena圖像處理結(jié)果

從圖3看出，(g)相比于(e)而言，Lena帽子的邊緣信息得到了較好的保留。為了進一步比較(e)和(g)的效果，文中分析了峰值信噪比(PSNR)值以及分割圖像的運行時間。

3.2 峰值信噪比

PSNR表示信號最大可能功率和噪聲功率的比值。由于大部分信號都有較寬的動態(tài)范圍，PSNR常用對數(shù)分貝單位來表示[16-17]。

計算公式如下：

其中：MSE指均方誤差(各數(shù)據(jù)誤差平方的平均數(shù))；In，Pn分別指原始、處理后影像第n個pixel值。

一般來說，PSNR值越大失真越少。從表1數(shù)據(jù)來看，結(jié)合Nut和Lena處理數(shù)據(jù)，文中方法失真率小于文獻[5]的結(jié)果；但是耗時多于文獻[5]的結(jié)果。下面用粒度來比較文獻[5]和文中方法。

表1 圖像處理結(jié)果對比

為了對比不同方法的效果，圖4列出了含噪的Fruit圖像處理結(jié)果。

圖4 Fruit圖像處理結(jié)果

從圖4的分割結(jié)果來看，對比(e)、(g)可以看到，雖然在對含噪圖片進行處理時效果都不是非常理想，但文中的邊緣分割效果明顯好于文獻[5]方法的分割效果，即文中方法也適用于含噪圖片的分割。

4 結(jié)束語

文中以改進分水嶺方法對噪聲敏感以及容易造成過分割的圖像為目的，采用了基于小波二次去噪的分水嶺算法。該方法通過對梯度圖像進行二次分解重構(gòu)，有效地解決了圖像分割對噪聲敏感的問題；然后再通過標記前景、背景的方法，使得吸水盆地只響應(yīng)想要探測的目標。該方法能很好地分割無噪和含噪圖片。相比一般的分水嶺方法，該方法需要對梯度圖像進行二次消噪并重構(gòu)，所以耗費時間較多。但是改進后的方法能夠較好地保留重要的目標信息，使有意義的區(qū)域能被分割出來，所以在圖像分割方面具有一定的應(yīng)用價值。

[1]ZhangYJ.Imagesegmentation[M].Beijing：ChinaSciencePress,2001.

[2]SnyderWE,QiHairong.Machinevision[M].Cambridge,UK:CambridgeUniversityPress,2004.

[3]ZuoQ,ShiZK.Anreal-timealgorithmforlicenseplateextractionbasedonmathematicalmorphology[J].JournalofImageandGraphics,2003,8(3):281-285.

[4] 刁智華，趙春江,郭新宇,等.分水嶺算法的改進方法研究[J].計算機工程，2010,36(17):4-6.

[5] 王小鵬，羅進文.基于形態(tài)學(xué)梯度重建的分水嶺分割[J].光電子·激光，2005,16(1)：98-101.

[6]ConzalezRC,WoodsRE.Digitalimageprocessing[M].2nded.Beijing:PublishingHouseofElectronicsIndustry,2005.

[7] 夏 平，劉馨瓊，向?qū)W軍,等.基于形態(tài)學(xué)梯度的圖像邊緣檢測算法[J].計算機技術(shù)與發(fā)展，2007,17(12):107-109.

[8]DaiQY,YuYL.Akindofsegmentationmethodofvehicle-license-plateimagesbasedonwaveletandmathematicalmorphology[J].JournalofImageandGraphics,2000,5(5):411-415.

[9] 張德豐.MATLAB數(shù)字圖像處理[M].北京：電子工業(yè)出版社，2010.

[10]Kronland-MartinetR,MorletJ，GrossmannA.Analysisofsoundpatternsthroughwavelettransforms[J].InternationalJournalofPatternRecognitionandArtificialIntelligence,2012,1(2):273-302.

[11] 張光新，崔 揚，周澤魁.基于小波包分解的紋理圖像去噪[J].華南理工大學(xué)學(xué)報:自然科學(xué)版，2005,33(3):31-33.

[12]RoerdinkJ,MeijsterA.Thewatershedtransform:definitions,algorithmsandparallelizationstrategies[J].FundamentaInformaticae,2001,41:187-228.

[13] 王 宇，陳殿仁,沈美麗,等.基于形態(tài)學(xué)梯度重構(gòu)和標記提取的分水嶺圖像分割[J].中國圖象圖形學(xué)報，2008，13(11):2176-2180.

[14] 羅 玲，解 梅，陳 杉.基于多尺度形態(tài)濾波的分水嶺圖像分割方法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2004,16(2):168-173.

[15] 馮丹琴，盛秋琴，陳 凱,等.幾種常見濾波器的特性[J].光通信技術(shù)，2002,26(1):46-53.

[16] 李彥麗，金東瀚，焦秉立.幾種典型的感知視頻質(zhì)量評價模型[J].計算機工程與應(yīng)用，2002,38(13):66-68.

[17]LiGL,WangNN,ZhangQ.StudyofmovingimagequalityevaluationbaseonMPEG2system[J].JournalofTianjinUniversity,2001,34(5):573-576.

Improved Algorithm of Watershed Image Segmentation with Wavelet Transform

MENG Shao-bo1,XI Xiao-qiang2

(1.School of Science,Xi’an University of Posts and Telecommunications,Xi’an 710121,China;2.Institute of Internet of Things and IT-based Industrialization,Xi’an University of Posts and Telecommunications,Xi’an 710061,China)

Watershed segmentation method is an effective and commonly used segmentation method of image,but it is easy to cause the over segmentation and very sensitive to noise.In order to overcome this problem,a watershed algorithm based on wavelet transform is proposed in this paper.First,a method of two-layer denoising based on wavelet decomposition transform is used to the morphological gradient image,in which the high-frequency wavelet coefficients is dealt with threshold by setting the threshold vector and the 2-D wavelet is reconstructed.Then,using the technology of marking foreground and background in morphology and composing the 2-D reconstructed wavelet,a modified new segmentation function is obtained and it has only minimal value at the marked position in the foreground and background.At last,watershed transform is used to the modified gradient image and a better effect of segmentation is achieved.

wavelet transform;watershed image segmentation;image gradient;two-layer wavelet decomposition to denoise

2015-06-25

2015-09-29

時間：2016-02-18

國家自然科學(xué)基金資助項目(11475135)

孟少波(1988-),男，碩士研究生，研究方向為圖像處理及其應(yīng)用；惠小強，博士，教授，研究方向為量子信息、圖像處理等。

http://www.cnki.net/kcms/detail/61.1450.TP.20160218.1636.072.html

TP301.6

A

1673-629X(2016)03-0108-05

10.3969/j.issn.1673-629X.2016.03.026