孟少波，惠小强

(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