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

孟少波，惠小強

(1.西安郵電大學 理學院,陜西 西安 710121；2.西安郵電大學 物聯網與兩化融合研究院，陜西 西安 710061)

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

孟少波1，惠小強2

(1.西安郵電大學 理學院,陜西 西安 710121；2.西安郵電大學 物聯網與兩化融合研究院，陜西 西安 710061)

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

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

0 引 言

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

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

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

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

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

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

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

1 圖像處理

1.1 圖像梯度的計算

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

常用圖像梯度可通過函數求導、中值差分、線性濾波法以及形態學方法表示[7]。

文中采用形態學方法來表示梯度。設圖像為f(x,y)，B為結構元素，數學形態學的腐蝕和膨脹定義如下[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)的數學形態學梯度為：

(3)

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

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

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

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

(4)

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

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

(5)

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

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表示設置閾值向量；式(8)表示對高頻小波系數進行閾值處理；式(9)表示對圖像進行二維小波重構。

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

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

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

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

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

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

2 分水嶺算法的改進

2.1 算法原理

分水嶺的數學定義最早出現在文獻[12]中：

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

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

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

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

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

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

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

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

watershed(f)=D/Xhmax

(10)

2.2 算法改進

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

圖1 分水嶺示意圖

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

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

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

Step1：讀入數據，利用式(3)得到圖像的形態學梯度；

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

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

Step4：對圖像進行小波重構；

Step5：繼續執行Step3、Step4進行二次重構；

Step6：在小波重構的基礎上利用形態學標記前景和背景的技術，得到修改后的分割函數梯度；

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

3 結果及分析

3.1 實驗數據

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

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

圖3 Lena圖像處理結果

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

3.2 峰值信噪比

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

計算公式如下：

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

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

表1 圖像處理結果對比

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

圖4 Fruit圖像處理結果

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

4 結束語

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

[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] 王小鵬，羅進文.基于形態學梯度重建的分水嶺分割[J].光電子·激光，2005,16(1)：98-101.

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

[7] 夏 平，劉馨瓊，向學軍,等.基于形態學梯度的圖像邊緣檢測算法[J].計算機技術與發展，2007,17(12):107-109.

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

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

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

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

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

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

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

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

[16] 李彥麗，金東瀚，焦秉立.幾種典型的感知視頻質量評價模型[J].計算機工程與應用，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

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

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

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