形态学梯度重建的改进快速分水岭算法 吴璇， 汪渤， 徐学强， 石永生 (北京理工大学 信息科学技术学院自动控制系，北京 100081） 摘 要：提出一种基于形态学梯度重建的改进快速分水岭分割算法。该方法在形态学梯度图 像基础上，利用形态学开闭重建运算对梯度图像进行重建；定义了分水岭的强度指标--落差， 基于此对快速分水岭算法进行了改进，并将此算法结合图像重建进行了仿真实验，整个分割 过程无需进行分割后的区域合并处理,降低了分割的复杂性。仿真实验证明，改进的算法无 论从消除过分割还是区域轮廓定位等性能方面，均具有较好的分割效果。 关键词：图像分割；快速分水岭变换；形态学梯度重建 中图分类号：TP391.41 文献标识码：A 基金项目：国家部委预研项目（51405030104BQ0171） Developed Watershed segmentation Based on Morphological Gradient Reconstruction WU Xuan, WANG Bo, XU Xue-qiang, SHI Yong-sheng (Department of Automatic Control, School of Information Science and Technology, Beijing Institute of Technology, Beijing 100081, China) Abstract: A method of watershed segmentation based on morphological gradient reconstructing was proposed. First，morphological gradient image was obtained. Second，opening and closing by reconstruction operators were employed to reconstruct gradient image. Then, a guide line of watershed’s strength named “fall” was defined, based on which, watershed segmentation arithmetic was developed, then we applied the developed method to the reconstructed gradient image. The whole segmentation process needed no post-segmentation which in some degree reduced the complexity of the segmentation. Results of simulation showed that the developed method can efficiently eliminate over-segmentation, and hold the position of region contours without evident bias. Keywords： image segmentation; fast watershed transform; morphological gradient reconstruction 1、引言 在对图像的研究和应用中，人们往往仅对图像中的某些部分感兴趣，它们一般对应图像 中特定的、具有独特性质的区域。为了辨识和分析目标，需要将它们分离提取出来，在此基 础上才有可能对目标进一步利用。图像分割就是指把图像分成各具特性的区域并提取出感兴 趣的目标的技术过程。它不仅得到人们广泛的重视和研究，也在实际中得到了大量的应用。 基于数学形态学理论的分水岭分割的方法，基本上克服了传统图像分割方法的缺点，是 近 年 发 展 起来 的 一 种 图像 分 割 方 法。 分 水 岭 算法 采 用 标 记法 来 具 体 实现 ， 在 此 基础 上,LucVince 和 PierreSoille 提出了一种利用先进先出(FIFO)数据结构的快速分水岭分割 算法，该算法分两个步骤进行计算:排序(Sorting)和淹没(Flooding)[3,4]。然而,由于该算法 是对图像中每一个像素点进行标注检测,因此耗费时间，加上过度分割的经典问题不能很好 解决,故而如何更好的利用分水岭变换的原理来解决图像分割的问题值得进一步探讨。 本文正是根据分水岭算法的这些特点,并结合数学形态学的开闭重建运算以及落差等概 

念,提出了新的快速分水岭算法。实验结果表明,这是一种实用可行的图像分割方法,能够快 速分割出目标的完整外轮廓，尤其对于过分割现象的抑止达到了很好的效果。 2、分水岭变换： 分水岭变换是一种基于数学形态学的图像分割算子，可将图像分解为若干个相似而互不 重叠的区域。图像分割中的分水岭变换通常是通过模拟浸水过程来实现的[3]。在分水岭变换 过程中,整幅图像被看作是一片起伏跌宕的山地模型,其中每个像素的灰度值代表该点的海 拔。在这样的地形中,既有地势很低的山谷(局部极小区域),也有高高耸立的山脊(分水岭), 还有山脊和谷底之间的或陡或缓的山坡(聚水盆地)。模拟浸水就是在各个谷底刺穿一个小孔, 然后把整个模型慢慢浸入水中,随着水位的上升,水面慢慢顺着山坡向上扩展,当到达山脊时 就会溢出,这时就在此处建筑堤坝,如此直到整个模型浸入水中,所有堤坝就成为分开各个贮 水盆地的分水岭。图 1 演示了一维模拟浸水过程。 （b）水面上升 （c）建立水坝 （d）分水岭 （a）地形图 3、改进算法 图 1 一维分水岭算法浸没模型 传统的分水岭变换存在过分割现象[5]，为了缓解该问题,突出目标的外轮廓信息,通常把 梯度图像看成是假想的地形表面，每个像素的梯度值代表该点的海拔高度，进行分水岭变换， 因而梯度函数的选择至关重要。下面先介绍几个定义： 对于梯度图像 g(x,y)和参考图像 r(x,y) (以下分别用 g 和 r 代替), 其中 B 表示圆盘状 结构元素。圆盘形结构元素满足旋转不变性,因此不会造成图像特征值的畸变。 定义 1 g 的形态学[1]测地膨胀定义为 i ⎧ ⎨ ⎩ ),(1 rg D + B i rgD ),( rB ), ⊕ ] rB ), 定义 2 g 的形态学测地腐蚀定义为 [ DMin ( [ gMin ( i B ⊕ = = ] B ( i ) .....4,3,2,1 = (1) ⎧ ⎨ ⎩ i E B E ),(1 rg + i rg ),( B [ rB EMin i ), ( Θ B ] [ rBgMin ( ), Θ ] = = ( j ) .....4,3,2,1 = (2) 以上均为迭代运算。当迭代次数达到预定值或 D =+1 i B D i B 和 E i =+1 B E i B 时,迭代过程终 止。基于测地膨胀和腐蚀的定义,形态学开和闭重建运算 ) (rec BO 和 ) (rec BC 分别定义为： 定义 3 ) O rec ( B rg ),( = ) D rec ( B [( rBg ), ο ] (3) 定义 4 C ) rec ( B rg ),( = E ) rec ( B [( rBg ), • ] (4) 其中ο和• 分别为形态学开和闭运算； BD 和 BE 分别表示形态学测地膨胀和腐蚀收敛时 的结果。将上述开和闭重建运算结合，构建形态学混和开闭重建运算，以达到同时消除梯度 

图像重阴暗细节和噪声的目的。形态学混和开闭重建运算 ) Bg 定义为： (rec g ) rec ( B = C ) rec ( B O [ ) rec ( B rrg ), ,( ] (5) 可见形态学混和开闭重建运算先采用形态学开重建运算消除梯度图像中的尺度比结构 元素小的极大值噪声和非规则干扰,随后再进行形态学闭重建运算去除比结构元素小的暗噪 声及非规则干扰，修正了区域极大值和极小值, 减少甚至消除了因细节和噪声干扰造成的分 水线位置偏移，具有准确的轮廓定位能力，减小了区域轮廓线的位置偏移，且明显改善了因 局部极小值过多造成的分水岭过分割现象。 对重建后的梯度图像进行快速分水岭变换以实现对图像的区域分割，快速分水岭算法应 用于监控方式[2]的时候，可以采用阈值标志法，其实质是利用阈值，对区域最小值有选择地 进行分水岭变换，但其有局限性。本文对原有算法进行了改进，下面先介绍改进算法所用到 的几个定义,进而提出改进算法的基本理论。 定义 5 局部极小值的势能是指假设水从该局部区域最小点向上逐渐淹没,在浸入另一 个比该局部区域最小值还低的局部区域最小值之前所能形成的最大的湖的深度。 在势能的基础上构造一个评价分水岭强度的指标——落差。落差的定义如下： 定义 6 一个分水岭点的落差是指在模拟淹没的过程中,水刚好淹没到该分水岭点灰度 级时,将该灰度值与此时所有直接被该分水岭点隔开的湖的最低点灰度值求差的最小值。 (a) 普通分水岭结果 (b) 区域 5 的势能 (c) 区域 1~5 的势能 (d) 多尺度分水岭结果 (e) 分水岭强度图 图 2 多尺度分水岭变换示意图 每一个分水岭像素对应唯一的落差值,且只与图像的梯度性质有关，落差值越小,则该分 水岭重要性越低,越容易被忽略。图 2 中,用一维信号来代替了二维图像梯度图, 在图 2a 中 得到 5 个区域最小值,从左到右依次记为 1～5，对应的局部区域称为区域 1～5，对应的 4 道分水岭依次为 d1～d4。以区域 5 为例，比区域 5 的局部区域最小值还小的局部区域只有 区域 2，在区域最小值 5 处开个洞，让水逐渐上升，根据定义，必须上升到区域 5 的势能高 度的时候，才有可能浸入区域 2 中，于是得到了区域 5 的势能如图 2b 所示。此时形成的湖 已经淹没了区域 3,4(因为区域 3,4 均比区域 5 高)。区域最小值势能 h1～h5 如图 2c 所示。 有了这一概念,我们可将多尺度分水岭算法描述为：只对势能大于某一阈值的标记过的区域 

最小值进行模拟淹没。根据设定的阈值和图 2c 所标的势能大小依次忽略区域，结果如图 2d 所示只剩下 2，5 为标记的情况，此时仅剩的分水岭 d2 体现了原波形中最为显著的变化。根 据定义 6 在分水岭 d2 对应点处画一道水平线比较此时分水岭两侧形成的两个湖的最低点灰 度值，用该点灰度减去其中较高的一个,就是 d2 点的落差 f2，如图 2e 所示落差 f1～f4,根 据落差的大小依次忽略前 3 道分水岭 d1、d3 和 d4 可以很容易获得与图 2d 所示相同的结果。 通过对采用阈值标志的快速分水岭算法的分析发现在计算中很容易得到落差值，从而可 以根据落差对算法进行改进，下面仅给出改进算法的思路。改进后的算法，能够有效的减少 因为细节和噪声干扰造成的局部极小值过多导致的分水岭过分割现象。由于改进后的算法不 影响原流程，且减少甚至消除了对过分割点的计算量，因此降低了运算复杂度。 定义：常值 WSHED 为存储的落差阈值的相反数；一个数组，记录每个现有区域隶属湖的 湖底值，同时定义一个标志位用于说明像素点所在区域的湖底值是否需要更新，算法中每增 加一个新区域，则在该数组中增加一项，置湖底初值为本区域最小灰度值，标志位初值为无 须修改；数组 Im_o[p]存储待处理像素点 p 的落差值。 循环算法：（1）对输入的梯度重建图像按照灰度级排序索引；（2）如果所有点都已经处 理，则退出，否则，将下一个灰度级所有像素点置为待处理点；（3）将所有与已处理点距离 为 1 的待处理点推入队列；（4）从队列中取出一点 p，先判断 p 的每个邻居像素点 q 是已处 理点还是待处理点：q 为待处理点，则将其推入待处理队列；q 为已处理点，则可根据对应 的 Im_o[p]的值是否小于等于 WSHED 来判断 p 是已有区域点还是分水岭点。如果 p 是已有区 域点，则 p 点在输出图像中的值标志为该已有区域号；如果 p 是分水岭点,则将 p 点邻近最 近湖底的落差值：Im_o[p]=当前灰度值-最高湖底值+WSHED；对所在的湖底值比 p 点邻近最 低湖底值高的 q 点置标志位为湖底值需要更新，记下待更新值；对 p 点重复步骤 4，直到队 列为空，则转到步骤（5）；（5）在每次处理完一个灰度级的所有像素点后按顺序更新标志位 值为待修改的点的湖底值。 4、 实验结果及分析 利用本文改进的算法进行图像分割的结果如图 3 所示。 (a) 截取原图像 (b) 分水岭分割结果 (c) 改进分水岭结果 (d) 梯度重建分水岭算法结果 图 3 图像分割实验最终结果图 图 3（a）经过分水岭分割后可以得到图 3（b），可以看出，由于监控图像中的非规则灰 度扰动和噪声，出现了过分割的现象，造成了过多的区域。采用本文提出的改进的分水岭算 法，得到图 3（c），比较图 3（b）和图 3（c），可以看出过分割的现象明显改善，能够准确 的分辨出图像中的不同的物体了，并且具有准确的轮廓的定位能力，这说明对分水岭点采用 落差这一评价指标的确可以反映原梯度图像的多尺度特性，对原始监控图像有较好的概括， 从而使过分割现象得到了较好的解决。但是对于监控对象来说，上述过程依然存在过度分割 的情况。图 3（d）选用大尺度的结构元素，从结果可见随着结构元素的选取从小到大递增， 分割的区域轮廓数目相应地单调减少，这说明本方法满足尺度的因果性，即随着结构元素地 增大，不会产生新的区域假轮廓，这一特性使得本方法非常适合于多尺度图像分割应用。 5、结论 

本文作者的创新点是：提出一种基于形态学梯度重建的改进快速分水岭图像分割方法。 该方法首先在形态学梯度图像的基础上提出了形态学开闭重建运算改进输入图像的质量，使 得分割具有准确的轮廓定位能力，有效的去除了过分割，且具有尺度因果性；接着构造了落 差的概念，通过判断点对应的落差值是否足够大于阈值来决定是否为分水岭点，解决了阈值 标志法阈值的设置和标志的提取方式至今也没有统一方法的局限性。实验结果表明落差参数 可有效地反映图像梯度的多尺度信息，并可通过改进的分水岭算法获得。无论从分割的视觉 效果还是消除过分割、区域轮廓定位及抗噪声等性能方面，本文方法均有较好的分割效果。 整个分割过程无需进行分割后的区域合并处理,降低了分割的复杂性，具有较广阔的应用范 围。 参考文献： [1] 周龙. 基于数学形态学的储粮害虫图像边缘检测算法研究[J].微计算机信息，2005， 21（4）:230~231 [2] 张利欣，吴并臻，尹怡欣，徐正光. 无线图像监控系统的研制[J]. 微计算机信息，2003， 19（8）:40~41 [3] Luc Vincent, Pierre Soille．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. [4] Job B T M, Roerdink, Arnold Meijster．The watershed Transform: definition, algorithms and parallelization strategies．IOS Press．Fundamental Information，2001, 41: 187~228. [5] Rafael C. Gonzalez.数字图像处理 (第二版) [M].阮秋琦，阮宇智，等译.北京.电子工 业出版社.1998.460~505. 本文为基金项目：国家部委预研项目（51405030104BQ0171） 作者简介：第一作者：吴璇（1983—），女，汉，江西永新人，硕士研究生，主要研究方向： 导航、制导与控制。 导师：汪渤(1963－)，男，汉，辽宁辽阳人，教授，博士生导师，主要研究方向： 导航、制导与控制。 通讯地址：姓名：吴璇； 通信地址：北京市北京理工大学 201 教研室； 邮编：100081 e-mail: feng083@126.com