分水岭分割算法研究综述

沈夏炯，吴晓洋，韩道军

（河南大学数据与知识工程研究所，河南 开封 475004）

分利用综合距离度量

分水岭分割算法研究综述

沈夏炯，吴晓洋，韩道军

（河南大学数据与知识工程研究所，河南 开封 475004）

传统分水岭分割算法存在过分割和对噪音敏感等问题，为此，研究者针对算法中前处理和后处理过程分别展开研究。介绍自上而下的模拟降水算法和自下而上的模拟泛洪算法，分析待输入梯度图像的重构处理过程、分割后区域的合并处理过程以及前后结合处理过程，归纳前、后处理及前后结合处理的分水岭分割算法改进，评价改进效果，总结并提出待解决的研究方向及解决思路。

分水岭分割；过分割；前处理；后处理；梯度重构；区域合并

DO I：10.3969/j.issn.1000-3428.2015.10.006

1 概述

分水岭分割算法建立在数学形态学的理论基础之上，模拟的是立体的地形表面，属于一种基于区域的图像分割方法［1］。在遥感领域，改进的分水岭分割算法广泛应用于遥感影像分割尤其是高分辨率遥感影像的分割［2］；在医学领域，改进的分水岭分割算法广泛应用于彩色白细胞分割、磁共振脑图像分割、组织细胞分割、乳腺癌粘连细胞分割等［3］；在智能识别领域，改进的分水岭分割算法广泛应用于图像目标识别、多目标车辆跟踪、道路识别、路面裂缝检测等［4］。

分水岭分割算法的发展趋势可以归纳如下：（1）随着遥感影像分辨率的提高，地物类型也变得更加复杂，传统的基于像元的分类技术已经不能满足需要，而分水岭分割算法对于复杂的地物能够产生较好的分割效果［5］。此外，现阶段的医学影像普遍具有信息量大且要求分割精确，分水岭分割算法可以很好地满足这一分割要求［6］。故在应用领域方面，发展趋势倾向于遥感和医学影像应用。（2）到目前为止，分水岭分割算法的改进方法有很多，但这些改进方法并不适用于所有的图像，往往是根据特定的应用背景进行改进［7］。故在使用方面，发展趋势倾向于如何根据目标图像的特征选择合适的改进方

法；（3）图像分割是图像处理中很重要的一个操作，如何评价图像分割的优良是至关重要的，一些文献也提出了一些评价标准［8］，然而目前尚没有一个完整、完善的评价机制。故在评价方面，发展趋势倾向于如何制定一个规范的评价标准来评定分割效果的优良；（4）由于大数据量图像的广泛应用以及算法因不断改进而复杂性增加，导致算法的运算效率和准确性降低［9］。故在改进方法的目标方面，发展趋势倾向于并行计算和智能计算方向。

并行计算和智能计算等新型计算模式的出现为分水岭分割算法效率的提高和过分割问题的减少提供了一种新的解决思想。并行计算是提高处理能力和计算速度的一种有效方法，目前MPI［10］和GPU［11］等并行计算技术已经在分水岭分割算法中得到应用，在图像的数据量较大时取得了不错的效果。在智能计算算法中，遗传算法［12］、粒子群算法［13］具有找到全局最优的能力，可以很好地解决分水岭分割算法中如何选择最优阈值的问题，从而使分割的结果更加精确、合理，减少了过分割现象。

Luc Vincent和Pierre Soille于1991年提出了基于淹没的分水岭分割算法。此算法使用像素队列来模拟洪水上涨过程，经过验证该算法比当时现有算法精度更高且速度更快［14］。Smet P D和Pires R L于2000年提出了基于降水的分水岭分割算法［15］。为了克服分水岭分割算法的缺点，比如容易丢失重要轮廓、过分割现象比较严重等，学者们进行了大量的研究，并提出了很多改进方法。根据分水岭分割算法的不同时段，将其改进划分为前处理改进、后处理改进和前、后结合处理改进，这些改进在一定程度上克服了过分割严重等问题，但是由于应用的广泛性，尚未从根本上解决过分割和噪声敏感等问题。本文在现有分水岭分割算法研究的基础上，对分水岭分割算法进行综述，为以后学者对该算法的研究提供支持。

2 传统的分水岭分割算法

分水岭分割算法早期来源于地理学，将图像模拟或想象成为一个地形图，地形图的山脊即为图像的分水岭。源于此思想，产生了著名的2种分水岭分割算法：自上而下的模拟降水算法和自下而上的模拟泛洪算法。

自上而下的模拟降水算法原理如下：

（1）将图像理解成为一个如图1所示的地形图。

图1 自上而下的模拟降水模型

（2）水滴从上向下降落，如果某些水滴最终落到地形图中的同一个盆地，则说明这些水滴落入地形图中对应的点属于同一个区域，如果某些水滴落入相邻2个盆地的概率是相近的，则说明这些水滴落入地形图中对应的点属于分水岭。

自上而下的模拟降水过程是一个递归过程。定义如下：

其中，式（1）是递归过程的初始条件，设 Xhmax是灰度值中最大值的像素点。式（2）是一个递归过程，h表示灰度值的范围，从 hmax开始递归。Pχh为像素点Xh所属的盆地，Dχh为像素点Xh的邻域，X（h）deepest为像素点Xh邻域中最陡方向的点即Xh-1。每次递归过程，就是找到Xh-1并标记其所属的盆地。最后，若某像素点同时属于 2个以上盆地的点，即为分水岭中的点。

自下而上的模拟泛洪算法原理如下：

（1）将图像理解成为一个如图2所示的地形图。

图2 自下而上模拟泛洪模型

（2）水从地形图的最低部分开始向上涨水，当2个盆地的水交汇的时候建立起一个大坝将各个区域隔开，建立起的大坝就被称为分水岭。

自下而上的模拟泛洪过程是一个递归过程。定义如下：

其中，式（3）属于递归过程的初始条件。Xhmin是图像I中灰度值为最小值的像素点；式（4）是一个递归过程。h表示灰度值的范围，hmin为灰度值范围最小值，hmax为灰度值范围最大值。Xh+1是灰度值即海拔高度为h+1上的所有像素点。minh+1表示此点属于新产生盆地最小值点，即在h+1此海拔高度有产生了新的盆地；Xh∩Xh+1表示Xh+1点与Xh点相交，Cχh为Xh点所在的盆地，故Cχh（Xh∩Xh+1）为Xh+1点与Xh点同在一个盆地 Cχh的点。通过此递归过程，将图像I中的所有像素点划分盆地，最后，若某像素点同时属于2个以上盆地的点，即为分水岭中的点。

自上而下的模拟降水算法和自下而上的模拟泛洪算法都是将图像理解成为地形图，并分别从地形图的上和下开始算法的执行。通常自下而上的模拟泛洪算法在研究过程中被使用得居多，但根据上述对2种算法的分析来看，2种算法可以取得相同的效果。

3 改进的分水岭分割算法

3.1 改进方法归纳

众多学者在对分水岭分割算法进行改进的过程中对传统部分改进较小，多数是在分水岭分割前或分割后进行改进。因此，根据图3中对分水岭分割算法改进的时机，将其改进划分为前处理、后处理和前、后结合处理，图3中上面的虚线框为前处理，下面的虚线框为后处理。

图3 基于处理过程的改进方式

传统的分水岭分割算法虽然取得了良好的效果，然而针对具体的环境遇到了诸如过分割、对噪声敏感等问题。后来的众多学者根据自身的研究需要提出了不少的改进分水岭分割算法，根据领域可以划分为智能识别、医学、遥感等。根据分水岭分割算法的过程可以将其归纳为在传统分水岭分割算法之前进行处理、传统分水岭分割算法之后进行处理和将两者结合起来，从而来满足自身的研究需要。在这里将在传统分水岭分割算法之前进行处理称为“前处理”，将在传统分水岭分割之后进行处理称为“后处理”，将在传统分水岭分割之前和分割之后同时结合起来进行处理称为“前、后结合处理”。前处理的方法有预处理滤波、标记、小波变换、扩展最小变换、形态学开闭重构技术、对比度增强、距离变换、中值滤波等；后处理的方法有空间聚类、异质性最小区域合并、距离度量区域合并等；前、后结合处理的方法就是将以上前处理和后处理的方法结合使用。

3.2 前处理

如果采用未经前处理的图像直接进行分水岭分割会由于图像本身的噪声及量化误差影响，而产生大量的小区域即人眼看不到或者理论上不想存在的小区域，即过分割问题。传统分水岭分割算法输入数据为图像梯度，如果对图像梯度进行处理后，再进行分水岭分割，将会出现更好的分割效果，故学者们对输入图像梯度之前进行了大量的研究，用来滤除图像噪音从而将梯度图重建，这样再进行传统的分水岭分割就会尽量避免原有的缺点。

文献［16］提出了一种基于开闭运算和距离变换的分水岭分割算法，利用开运算f·b=（fΘb）⊕b，闭运算f·b=（f⊕b）Θb，距离计算等方法实现了梯度重构，克服了传统算法的过分割问题。

文献［17］提出了一种对比度增强的改进分水岭分割算法，该算法采用随机概率方法Pr［P→q］=来提高图像的对比度，从而降低了图像噪音对分割所产生的影像，较好地解决了过分割问题。

文献［18］提出了一种新的基于低通滤波的标记提取方法，用来对要输入的原始梯度图像进行梯度重构，从而再进行分水岭分割，该方法有效地去除了分割结果在地物边缘处仍会存在破碎多边形的情况。

文献［20］提出了采用混合开闭重构运算：

3.3 后处理

在改进的分水岭分割算法中，由于其算法特性，通常分割结果都是封闭的区域，因此为了解决过分割的问题，在后处理部分，往往采用各种方法及规则，消除那些理论上不应该存在的微小局部区域。

文献［21］提出了一种基于K-means聚类的改进分水岭算法，该算法定义为分割

以后区域i和区域j之间的相似度，其中，Mij为区域i和区域j之间的平均强度差，Bij为区域i和区域j之间的强度差异，通过将相似度 Cij与阈值Tc进行比较，确定哪些区域之间进行合并，进而解决了传统分水岭算法的过分割严重的问题。

文献［22］提出了利用区域之间的综合差异性f=wspectralhspectral+（1-wspectral）hshape进行区域合并的方法，确保区域之间的异质性最小，抑制了图像的过分割，获得了理想的分割结果，其中，wspectral为光谱差异性度量准则在综合准则中所占的权值；hspectral为光谱的差异性度量准则；hshape为形状的差异性度量准则。

在实际应用过程中，单独进行后处理研究的较少，通常在进行后处理研究工作时，都与前处理的研究工作结合起来，从而获得更好的分割效果。

3.4 前后结合处理

在分水岭分割算法改进的过程中，很多学者发现不是单一的一种改进就可以达到需要的研究结果，因此，很多学者将前处理和后处理结合起来进行研究和改进，并且取得了不错的处理效果。

文献［23］提出了在前处理部分首先基于相位一致思想分析、提取梯度信息。相位一致计算式如下：

然后利用扩展最小变换E=EM（G，h）标记局部最小区域，其中h为高度阈值，G为相位一致梯度图像，E为二值图像。利用强制最小技术修改相位一致梯度图像，从而获得重建后的梯度图像，利用前处理部分获得了地物准确边界。

在后处理部分，首先进行属性特征聚类即依次对光谱与纹理聚类，在对纹理和光谱进行初步分类后，进行空间关系分析，判定聚类后不确定对象的类别属性，合并区域，通过后处理部分表达了各类地物的真实面貌，从而进行了合理的区域合并，保证了分割结果的准确性。

文献［24］提出了在前处理部分利用改进的基于边缘信赖度的各向异性扩散算法对图像进行处理，其中，E，S，W，N为计算梯度的4个方向；传导函数PDir是梯度▽DirIχ，y的函数。前处理部分，在去除噪声的同时，良好的保持了图像的边缘信息。然而经过分水岭分割后的图像仍然存在大量的分割区域，因此在后处理部分，杨家红等人提出了自动种子区域增长算法，将种子区域与邻接区域中颜色特征相同的区域合并起来，又利用小区域消解算法将区域尺寸低于设定阈值的区域合并到最相似的区域中去，从而使过分割问题得到了改进。

文献［25］提出了在前处理部分利用高斯低通滤波减少图像噪声和暗纹理细节的影响；利用形态学扩展最小变换技术设定阈值参数，消除小于阈值的局部极小值，从而减少过分割的区域。在后处理部

分利用综合距离度量

文献［2］在前处理部分提出最佳小波分解尺度选择方法，利用：

计算各尺度下局部方差均值，最终取得最佳分解尺度即最小局部方差均值对应的尺度，此时梯度幅值对地物刻画最为准确，其中（χ，y）为第 χ行，第y列对应的梯度值，m，n为采样模板长宽，为第k种地物局部方差均值，为模板内梯度均值，l为第k种地物的样本数量。然后又提出灰度相关性引导的多层标记提取方法，得到最终的标记图。在后处理部分采取光谱、纹理、面积、空间相邻关系等多约束策略进行区域合并，使区域合并更加准确。

4 结束语

分水岭分割算法有很多的改进方法，由于分水岭分割算法的改进多数是对分水岭分割之前进行预处理或者是对分水岭分割之后进行区域合并，还有将预处理和区域合并结合起来进行算法的改进，因此本文根据算法的过程将改进的分水岭分割算法进行归纳，介绍了前处理、后处理和前、后结合处理的划分方法。虽然这些改进方法取得了较好的效果，但是分水岭分割算法还存在需要进一步改进的一些方向，如由于图像分辨率的提高、图像纹理的复杂性及图像应用领域的更新，过分割问题仍需进一步研究；由于图像容量的不断增加，对分水岭分割算法进行并行研究，从而获得更高的效率和更好的效果，并且解决内存溢出等问题也是未来的研究方向。

［1］ Bieniek A，Moga A.An Efficient Watershed Algorithm Based on Connected Components［J］.Pattern Recognition，2000，33（6）：907-916.

［2］ 陈 杰，邓 敏，肖鹏峰，等.利用小波变换的高分辨率多光谱遥感图像多尺度分水岭分割［J］.遥感学报，2011，15（5）：908-926.

［3］ 张红民，王一博.一种改进的细胞图像分水岭分割方法［J］.重庆理工大学学报：自然科学，2012，26（11）：59-62.

［4］ 黎 蔚，高 璐.基于改进的分水岭算法的路面裂缝检测［J］.计算机工程与应用，2013，49（20）：263-266.

［5］ Su B，Noguchi N.Discrimination of Land Use Patterns in Remote Sensing Image Data Using Minimum Distance Algorithm and Watershed Algorithm［J］.Engineering in Agriculture，Environment and Food，2013，6（2）：48-53.

［6］ Zanaty E A，Afifi A.A Watershed Approach for Improving Medical Image Segmentation［J］.Computer Methods in Biomechanics and Biomedical Engineering，2013，16（12）：1262-1272.

［7］ Narkhede H P.Review of Image Segmentation Techniques［J］.International Journal of Science and Modern Engineering，2013，1（8）：54-61.

［8］ Nguyen K，Peng B，Li T，et al.Online Evaluation System of Image Segmentation［J］.Advances in Intelligent System s and Computing，2014，279：527-536.

［9］ Li Deren，Zhang Guifeng，Wu Zhaocong，et al.An Edge Em bedded Marker-based Watershed Algorithm for High Spatial Resolution Remote Sensing Image Segmentation［J］.IEEE Transactions on Image Processing，2010，19（10）：2781-2787.

［10］ Hu Yingshuai，Wu Suping.Parallelization Research on Watershed Algorithm［C］//Proceedings of International Conference on Automatic Control and Artificial Intelligence.［S.l.］：IET，2012：1524-1527.

［11］ Quesada-Barriuso P，Heras D B，Arguello F.Efficient GPU Asynchronous Implementation of a Watershed Algorithm Based on Cellular Automata［C］//Proceedings of the 10th International Symposium on Parallel and Distributed Processing with Applications.Washington D.C.，USA：IEEE Press，2012：79-86.

［12］ Maru D，Shah B.Image Segmentation Techniques and Genetic Algorithm［J］.International Journal of Advanced Research in Computer Engineering&Technology，2013，2（4）：1483-1487.

［13］ Deng Tingquan，Li Yanchao.An Improved Watershed Image Segmentation Algorithm Combining with a New Entropy Evaluation Criterion［C］//Proceedings of International Society for Optics Engineering.［S.l.］：Society of Photo-optical Instrumentation Engineers，2013：197-208.

［14］ Vincent L，Soille P.Watersheds in Digital Spaces：An Efficient Algorithm Based on Immersion Simulations［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1991，13（6）：583-598.

［15］ de Smet P，Pires R L.Implementation and Analysis of an Optimized Rainfalling Watershed Algorithm［C］// Proceedings of International Society for Optical Engineering.［S.l.］：Society of Photo-optical Instrumentation Engineers，2000：759-766.

［16］ Zhao Yuqian，Liu Jianxin，Li Huifen，et al.Improved Watershed Algorithm for Dowels Image Segmentation［C］//Proceedings of the 7th World Congress on Intelligent Control and Automation.Chongqing，China：［s.n.］.2008：7644-7648.

［17］ Khiyal M S H，Khan A，Bibi A.Modified Watershed Algorithm for Segmentation of 2D Images［J］.Issues in Informing Science&Information Technology，2009，6：877-886.

［18］ 尹高飞，肖鹏峰，冯学智.基于改进标记的高分辨率遥感图像分水岭分割方法［J］.遥感信息，2010，2：13-18.

［19］ 安素珍，王茂芝，张 涛，等.形态梯度重构的标记分水岭高光谱影像分割［J］.四川理工学院学报：自然科学版，2012，25（4）：59-63.

［20］ 江 怡，梅小明，邓 敏，等.一种结合形态滤波和标记分水岭变换的遥感图像分割方法［J］.地理与地理信息科学，2013，29（2）：17-21.

［21］ Ng H P，Ong S H，Foong K W C，et al.Medical Image Segmentation Using K-means Clustering and Improved Watershed Algorithm［C］//Proceedings of IEEE Southwest Symposium on Image Analysis and Interpretation. Washington D.C.，USA：IEEE Press，2006：61-65.

［22］ 林 卉，刘 培，夏俊士，等.基于分水岭变换的遥感影像面向对象多尺度分割算法研究［J］.测绘通报，2011，（10）：17-19.

［23］ 陈 杰，邓 敏，肖鹏峰，等.基于分水岭变换与空间聚类的高分辨率遥感影像面向对象分类［J］.遥感技术与应用，2010，25（5）：597-603.

［24］ 杨家红，刘 杰，钟坚成，等.结合分水岭与自动种子区域生长的彩色图像分割算法［J］.中国图象图形学报，2010，15（1）：63-68.

［25］ 余旺盛，侯志强，宋建军.基于标记分水岭和区域合并的彩色图像分割［J］.电子学报，2011，39（5）：1007-1012.

编辑 金胡考

Survey of Research on Watershed Segmentation Algorithms

SHEN Xiajiong，WU Xiaoyang，HAN Daojun
（Institute of Data and Know ledge Engineering，Henan University，Kaifeng 475004，China）

Researchers have made some related studies aiming at problem s of over-segmentation and noise sensitive in the pre-processing and post-processing of traditional watershed segmentation algorithms.A t first，this paper makes a detailed introduction on two classical algorithm s，that is，superincumbent simulation rainfall algorithm and bottom-up simulation flooding algorithm.Followed，three processes are proposed.The first is input gradient image reconstitution processing before the traditional watershed segmentation algorithm，the second is the merge application of region which is partitioned after traditional watershed segmentation algorithm，and the last is the combined processing before and after traditional watershed segmentation algorithm.Then it concludes and analyzes the effect of the improvement of watershed segmentation algorithms in the pre-processing，post-processing and their combined processing.Finally，it makes a conclusion and brings up some research directions to be resolved and basic solving ideas.

watershed segmentation；over-segmentation；pre-processing；post-processing；gradient reconstitution；region merging

沈夏炯，吴晓洋，韩道军.分水岭分割算法研究综述［J］.计算机工程，2015，41（10）：26-30.

英文引用格式：Shen Xiajiong，Wu Xiaoyang，Han Daojun.Survey of Research on Watershed Segmentation Algorithms［J］. Computer Engineering，2015，41（10）：26-30.

1000-3428（2015）10-0026-05

A

TP312

国家自然科学基金资助项目（61272545）；河南省科技攻关计划基金资助项目（142102210390）。

沈夏炯（1963-），男，教授、博士，主研方向：空间数据处理；吴晓洋（通讯作者），硕士研究生；韩道军，副教授、博士。

2014-09-22

2014-11-21E-m ail：L-W-T-G@163.com