标记分水岭算法及区域合并的遥感图像分割_陈波

第2期,总第72期国 土 资 源 遥 感No. 2, 2007
2007年6月15日REMOTE SENSING FOR LAND & RESOURCESJun., 2007
标记分水岭算法及区域合并的遥感图像分割
陈波1, 2,张友静2,陈亮1, 2
(1.河海大学水资源环境学院,南京 210098; 2.河海大学水文水资源与水利工程科学国家重点实
验室,南京 210098)
摘要:传统的分水岭算法通常对梯度图像进行无标记分割,其结果是容易造成过度分割。本文采用了一种基于标
记的分水岭算法,首先,利用Sobel边缘算子对原遥感图像进行梯度重建,获得梯度幅值图像,同时计算待分割区域
的周长、面积和形态因子,并对其进行标记;然后,利用距离函数图标定种子法和等值线跟踪法获得初始分割图像;
最后,利用改进的区域合并方法获得最终的分割结果。实验结果表明了该方法的有效性。
关键词:遥感图像;标记;分水岭算法;分割;区域合并
中图分类号: TP 75 文献标识码: A 文章编号: 1001-070X(2007)02-0035-04
0 引言
分水岭算法是一种数学形态学的图像分割方
法[1],广泛应用于医学图像处理[2]和视频处理[3]等
领域。传统分水岭算法能够准确定位边缘,具有运
算简单、易于并行化处理等优点,但同时也存在一些
缺陷:1对图像中的噪声极为敏感。由于输入图像
往往是梯度图像,原始图像中的噪声能直接影响图
像的梯度,易于造成分割的轮廓偏移;o易于产生
过分割。由于受噪声和平坦区域内部细密纹理的影
响,传统算法检测的局部极值过多,在后续分割中出
现大量的细小区域;?对低对比度图像的计算易丢
失重要轮廓。在这种情况下,区域边界像素的梯度
值较低,目标的重要轮廓容易丢失。
基于标记的分水岭算法采用具有不同优先级的
队列和先进先出的数据结构来实现,其优先级由像
素取值决定,相同优先级的像素,先放入队列的先处
理,不同优先级的像素,高优先级的像素优先处理。
处理时,先将梯度值较小的点按大小排序放入队列
中,其中,低梯度值对应于高优先级,然后依次从队
列中取出一个种子像素,同时判断其相邻像素是否
已标记,如果未标记,则置为与该种子像素同样的标
记,并按该相邻像素的值放入对应的优先级队列中,
如果已标记,则不做处理。如此处理,直至所有的队
列为空,即得到对于参考图像的区域表示,再将所有
的区域边界像素取出,就得到空间分割结果。该算
法可以起到连接不同形态大区域、消灭小区域和抑
制过度分割的作用。据此,本文针对SPOT5多光谱
遥感图像,提出了一种基于距离变换图搜索种子点
的分水岭算法及改进区域合并的遥感图像分割方
法。
1 分割方法
1.1 梯度幅值计算及区域增长算法
遥感图像的梯度计算有多种方

法,一般是利用
梯度算子在各通道上进行操作,然后通过线性组合
得到梯度幅值。本文在RGB彩色空间,利用3像元
@3像元的Sobel梯度算子[4]在各波段上进行操作,
然后通过简单的线性组合得到梯度幅值。由Sobel
算子得到的梯度幅值图像依然存在着很多干扰信
息,可以通过采用特殊的区域增长算法去除,其主要
步骤为:
首先,由于梯度幅值图像在对象的边缘处有较
高的像素值,因此,以Sobel检测的梯度边缘图像像
素点为搜索起始点,采用8向链码对各波段图像进
行区域跟踪。
其次,将得到的链码转化为线段编码。线段编
码是一种比较常用的区域描述方法,其思想是将区
域看作由若干条线段组成,每条线段以起始点与终
点坐标来表示。
然后,利用前面得到的链码以及线段编码计算
出各个分割区域的周长、面积和形态因子。其计算
公式为
F =L2/4PS (1)
式中,F为形态因子; L为链码长度; S为区域
像素个数。
收稿日期:2006-10-12;修订日期:2007-01-22国 土 资 源 遥 感2007年
最后,依据周长、面积以及形态因子对区域图像
进行颜色填充。填充的目的主要是使已经被标注的
边缘像素不再参加边缘跟踪,加快算法的计算速度。
1.2 标记分水岭算法
分水岭算法的基本思想是根据水面浸没地形的
过程提出来的,如图1所示。它是一种基于数学形态
学的图像分割算子,可将图像分解为若干个相似而互
不重叠的区域。其完整的描述见参考文献[5]。
图1 水面浸没地形
传统的分水岭算法通常对梯度图像进行无标记
分割,其缺陷是容易造成较严重的过分割。解决办
法通常是对待分割区域进行标记,本文采用的标记
方法是依据距离变换图搜索种子点[6]:
首先,对1. 1节中得到的区域图像进行距离变
换,得到一系列层层嵌套的封闭等值线图[7]。
其次,根据距离函数局部最大值点确定种子点。
在同一区域可能得到多个种子点,这时需要对种子
点采取种子合并的后处理过程。方法是看同一区域
的两个种子点之间的距离是否大于两者中距离值较
大的那个,如果小于这个值,就只留下距离值较大的
种子点。如此处理之后,每个区域就只有一个种子
点,即种子点的个数就是区域的个数。
最后,依据距离函数等值线确定分割点,进行图
像分割。由距离变换图可知,对于连通的区域,其分
水线也是连通的。设置一个探针,由种子点出发沿
等值线向外作环形运动,确定集水盆地,结果受两个
条件限制:一是探针运动在原始集合内,二是等值
线互不粘连。进而可以确定分割点。
2 区域合并
目前,尽管对图像分割已经进行了大量研究,并
提出了各种各样的算法,但因为绝大多数分割算法
都是针

对一个具体问题而提出的,还没有一种适合
于所有图像的分割算法,分水岭算法也存在一定的
过分割现象。目前,对区域合并算法研究较多的还
是区域灰度的相似性,但是,有时候区域目标不一定
是以均值亮度的形式来区别于背景的,因为它很可
能是以纹理的方式提供关于区域平滑、稀疏、周期或
准周期的描述。因此,本文提出了一种改进的区域
合并方法,该方法采用了一种新的数据结构来描述
区域邻接图,同时有效考虑到区域的纹理特征对区
域相似度的影响。在合并区域的过程中,面积较小
的区域,由于形状描述不准确,以灰度相似度为主;
面积较大的区域,应该尽量保证合并后的区域和原
来的两个区域有相似的灰度和几何形状,以纹理对
比度为主。
2.1 区域相似性度量
区域相似度是区域合并方法的一个非常重要的
概念,它直接影响区域合并的顺序和合并的次数等,
从而直接影响合并的结果。本文以灰度相似度和纹
理对比度作为区域相似性度量指标。
2. 1. 1 灰度相似度
设Ri和Rj是两个相邻的区域,且Ri面积小于
Rj面积。紧性定义为[8]
comp = (region_border_length)2/(4Pregion_area)
(2)
式中,region_border_length为区域边界长度; re-
gion_area为区域面积。可见,紧性取值范围为[1,
+])。
区域灰度相似度为
sim =XTiXTj+Xi+2+Xj+2(3)
式中,Xi、Xj分别代表两相邻区域向量;XTi、XTj
分别代表向量Xi、Xj的共轭向量;+Xi+2代表向
量的范数。
灰度相似度sim取值范围为(-1, 1)。对面积
较小区域,如果紧性接近1,则它的形状接近圆,而
紧性非常好的区域一般认为是独立区域,除非它与
某个相邻区域之间灰度相似度非常大才进行合并;
如果紧性接近],则说明这个区域非常松散,很有可
能从属于它相邻的某个大区域,此时合并对灰度相
似的要求相对降低。
2. 1. 2 纹理对比度
一般来说,我们可以认为纹理由许多相互接近
的、相互编制的元素构成,并具有周期性。所谓测量
一个目标的纹理,就是找出像素中像素灰度级的特
殊排列特性,以表示纹理在目标内的有效变化。在
这里,我们在共生矩阵的基础上定义纹理对比度
Wc,以检测两个相邻区域内的纹理一致性。
设S是目标区域R中具有特定空间联系的像
素对的集合,基于共生矩阵P,我们可以计算两个相
邻区域的纹理对比度,即
Wc=Eg1Eg1|g1-g2|P(g1,g2) (4)
式中,P(g1,g2)为共生矩阵P中各元素取值,
表示相应位置算子的联合灰度分布。
#36#第2期陈波,等: 标记分水岭算法及区域合并的遥感图像分割
2.2 改进的区域合并方法
传统基于区域邻接图( Region Adjacency
Graph,RAG)的合并方法采用区域邻接图(RAG)来
表示图像[9]。结构中,图像G为无向图,由两个集

合V和E组成,即:G=(V,E)。V是有限的非空的
顶点集合,在图像中表示各个区域; E是两相邻区
域顶点偶对的边界集合。
为提高区域合并的速度并改善区域合并效果,
本文采用了一种新的数据结构来描述区域邻接图,
表述为G=(R,S,C)。其中,R类似于传统RAG中
的V,但采用了一种不同的方式,即利用二维动态数
组来描述各区域节点。之所以采用二维动态数组,
是考虑到每个区域节点的邻接区域(邻居)的数目
是变化的,并且随着区域合并的进行,新区域的邻居
数目可能会增加,为每一个区域申请足够空间的做
法无疑会增加空间上的开销,并且也难以保证不会
发生溢出。S类似于通常的RAG中的E,E中的每
一个元素对应一个相邻接的区域对。不过,我们并
不对E排序,主要是考虑到经过合并之后被合并的
区域的相关链接都将成为虚假链接(死链接),那些每
一次合并新生成的链接加入到E中所需的排序环节
也将被省去,并且合并代价很大的链接将不会发生相
关的合并。C是一个记录合并代价或区域相似度的
矩阵,矩阵的行号和列号分别对应区域的标识号,矩
阵中的每一个元素记录了行号和列号所对应的区域
合并代价。基于此方法,每一次合并总是将合并代价
最小的两个相邻区域(最相似的两个相邻区域)进行
合并,合并代价以区域相似度来衡量(见上文),区域
合并的具体流程如图2所示。
图2 区域合并流程
3 实验结果及分析
为验证本方法的有效性,采用南京市SPOT-5
卫星影像(插页彩片8)进行实验,像幅为198像素
@211像素。整个算法在Matlab软件下编程实现。
从传统分水岭算法分割结果图(插页彩片9)可
以看出,由于受噪声和平坦区域内部细密纹理的影
响,分割中出现了大量的细小区域,如河流中的水体
被分割成许多大大小小的区域,即使水质一样的区
域也被分割成若干小区域。但对于道路而言,传统
分水岭算法的分割效果相对较好。
基于标记的分水岭算法(插页彩片10)相对于
传统分水岭算法分割精度有所提高,而且有效地抑
制了过度分割现象。但道路的分割精度有所下降,
许多细小的道路被分割成周围相邻的其它地物,其
连续性也有所降低。
从经过区域合并后的分割结果(插页彩片11)
可以看出,在图像中能很好地分辨出目标,并且由于
对初始分割结果进行了后处理,使得一些小的分割
区域能很好地合并,其结果可以用来直接提取感兴
趣的目标。
本文采用像素数量误差准则来评价分割方法[10]。
假定待分割图中有一个方形的区域,它与参考的分割
图(标号图像)进行叠置后的结果如图3所示。
图3 分割评价原理示意图
假定Si为区域i的面积,则区域n被正确分割
的面积Si

c为Sn。其中,Sn=max(Sa,Sb,Sc,Sd)。累
积待分割图中各区域被正确分割的面积,并除以分
割图的总面积,便可以得到待分割图像的正确分割
百分数(FCSP),即
FCSP =E
n
i=1
Sic/E
n
i=1
Si(5)
为考察分割方法对不同类别地物分割的有效
性,可根据Sn在参考分类图中的类别进行分类汇
总,以便得到各个类别的正确分割百分数。
本文根据专家目视解译结果,将测试图像中的
地物按照土地使用性质分为6类:建筑物、道路、农
田、绿地(包括公园绿地和林地)、水体和其它。在
ArcGIS 9. 0下对各类地物数字化获得参考分割图,
然后利用像素数量误差准则评价各类地物的分割精
度。各类地物的分割精度比较见图4。
从图4可以看出,较传统分水岭算法,本方法在
对各类地物的分割精度上有了一定提高,过度分割
现象得到了较好地抑制,各类地物分割的平均精度
按从高到低依次为水体(84. 9% )、农田(83. 2% )、
#37#国 土 资 源 遥 感2007年
图4 各类地物分割精度的比较
绿地(82. 7% )、其它(80. 6% )、建筑(79. 1% )及道
路(76. 5% ),其中绿地的分割精度提高幅度最大,
其根本原因在于本方法整合了遥感影像的光谱特征
和纹理特征;但道路的分割精度相对于传统分水岭
算法有所降低,这主要是由于道路往往处于两类地
物的交叉区域,受其周边地物的影响,在区域合并时
容易将其合并到其它地物中。
4 结论
实验结果表明,基于标记的分水岭算法在分割
效果和分割精度等方面都优于传统的分水岭算法;
初始分割后的区域通过改进的区域合并算法也得到
了较好地合并,降低了过度分割。
(1)本方法分割阈值的选择是通过多次试验取
平均值所得,由于阈值的选择直接影响到分割结
果,如何自适应地选择阈值是下一步研究的方向。
另外,在进行等值线区域分割时,分割点的位置未
能与原始图像的梯度信息进行融合,这也是需要改
进的方面。
(2)本方法中道路的分割精度相对于传统算法
有所降低,如何加入有利于提高其精度的因子,是本
文算法需要进一步研究的地方。
参考文献
[1] VincentL, SoilleP. Watersheds inDigitalSpaces:AnEfficientA-l
gorithm Based on Immersion Simulations[J]. IEEE Transaction on
Pattern Analysis and Machine Intelligence, 1991, 13(6): 583 -
598.
[2] GrauV,MewesAu,j AlcanizM. ImprovedWatershedTransform for
Medical Image Segmentation Using Prior Information[ J]. IEEE
Transaction onMedical Imaging, 2004, 23(4): 447-458.
[3] Chen Shao-y,i Huang Yu-wen, CHEN Liang-gee. Predictive
Watershed: A FastWatershed Algorithm for Video Segmentation
[J]. IEEE Transaction on Circuits and Systems forVideoTechno-l
ogy, 2003, 13(5): 453-461.
[4] 刘永学,李满春,毛亮.基于边缘的多光谱遥感图像分割方法
[J].遥感

学报, 2006, 10(3): 351-352.
[5] 马丽红,张宇,邓健平.基于形态开闭滤波二值标记和纹理特
征合并的分水岭算法[J].中国图象图形学报, 2003, (1): 77-
79.
[6] Yang Fa-guo, JiangTian-z.i Cell Image SegmentationwithKer-
nelBasedDynamicClustering and an EllipsoidalCellShapeModel
[J]. Journal ofBiomedical Information, 2001, (34): 67-73.
[7] Ju Cun-yong,CaiTi-jiu, Feng Zhong-ke. Automatic Segmen-
tation ofHigh-resolution Remote Sensing Image Based onMathe-
maticalMorphology[J].EngineeringVillage, 2005, 27: 84-87.
[8] Chaira T, RayA K. FuzzyApproach forColorRegion Extraction
[J]. Pattern Recognition Letters, 2003, 24(12): 1943-1950.
[9] Bow S T. Pattern Recognition and Image Preprocessing[M].New
York:Academic Press, Inc, 1992.
[10]陈秋晓,陈述彭,周成虎.基于局域同质性梯度的遥感图像分
割方法及其评价[J].遥感学报, 2006, 10(3): 360-362.
SEGMENTATION OF THE REMOTE SENSING IMAGE
BASED ON METHOD OF LABELING WATERSHED
ALGORITHM AND REGIONAL MERGING
CHEN Bo1, 2, ZHANG You-jing2, CHEN Liang1, 2
(1.WaterResource andEenvironmentCollege ofHohai University,Nanjing210098, China;2.StateKey Laboratory ofHy-
drology-WaterResources andHydraulicEngineering ofHohaiUniversity,Nanjing210098, China)
Abstract:Segmentation ofgradient images in the traditionalwatershed algorithm usually has nomarkers, which is
likely to cause excessive segmentation. This paper presents a watershed algorithm based on the labe.l Firs,t the
gradient images are obtained through the reconstruction ofgradientby using Sobel operator and, at the same time,
the perimeter, area andmorphology factors of the region are computed and labeled. Then, the initial image ofseg-
mentation is acquired by using themethod ofdistance function icon for determining the seeds and the technique of
isoline tracking. Finally, the last resultof segmentation is obtained by using an improvedmethod of regionalmer-
ging. The experimental result shows the effectiveness of themethod.
Key words:Remote sensing image; Labe;l Watershed algorithm; Segmentation; Regionmerging
第一作者简介:陈波(1982-),男,河海大学硕士研究生,从事地理信息系统与遥感研究。
(责任编辑:刁淑娟)
#38#