两种分水岭分割法的比较

任智格

【摘 要】本文通过介绍分水岭的数学意义、 BCUCHER基于有向箭头的有序算法与基于形态学滤波预处理和形态学梯度重建的分水岭图像分割方法，并比较了他们的计算复杂性，且在MATLAB的环境下进行了验证知第二种方法在图像分割中的应用较好，降底了时间复杂度。

【关键词】分水岭；有序算法；计算复杂性；时间复杂度

分水岭分割方法的基本思想是：假设在每个区域最小值的位置上打一个洞并且让水以均匀的上升速率从洞中涌出，从低到高淹没整个地形。当处在不同的汇聚盆地中的水将要聚合在一起时，修建的大坝将阻止聚合，水将只能到达大坝的顶部处于水线之上的程度。这些大坝的边界对应于分水岭的分割线。在求解图像问题方面，关键概念是将初始图像变成另一幅图像，在变换后的图像中，汇水盆地就是我们想要识别的对象或区域。

数学描述：令，，…，为表示图像的局部最小值点的坐标的集合。它属于一幅典型的梯度图像。令为一个点的坐标的集合，这些点位于与局部最小值相联系的汇水盆地内。符号min和max代表的最小值和最大值。最后，令表示坐标的集合，其中，即：

（3-1）

在几何上，是中的点的坐标集合，集合中的点均位于平面的下方。随着水位以整数量从到不断增加，图像中的地形会被水漫过。在水位漫过地形的过程中的每一阶段，算法都需要知道处在水位之下的点的数目。从概念上来说，假设中的坐标处在平面之下，并被“标记”为黑色，所有其他的坐标被标记为白色。然后，当我们在水位以任意增量增加的时候，从上向下观察平面，会看到一幅二值图像。在图像中黑色点对应于函数中低于平面的点。这种解释对于理解下面的讨论很有帮助。

令表示汇水盆地中点的坐标的集合。这个盆地与在第阶段被淹没的最小值有关。参考前一段的讨论，也可以被看作由下式给出的二值图像

（3-2）

换句话说，如果且则在位置有。否则。对于这个结果几何上的解释是很简单的。我们只需在水溢出的第个阶段使用“与（AND）”算子将中的二值图像分离出来即可。是与局部最小值相联系的集合。令表示在第个阶段汇水盆地被水淹没的部分的合集：

（3-3）

然后令为所有汇水盆地的合集：

（3-4）

可以看出处于和中的元素在算法执行期间是不会被替换的，而且这两个集合中的元素的数目与保持同步增长。因此，是集合的子集。根据式（3-2）和（3-3），是的子集，所以也是的子集。从这个结论我们可以得出重要的结果：中的每个连通分量都恰好是的一个连通分量。

找寻分水线的算法开始时设定。然后算法进入递归调用，假设在第步时，已经构造了。根据求得的过程如下：

令表示中连通分量的集合。然后，对于每个连通分量，有下列三种可能性[2]：（1）为空；（2）包含中的一个连通分量；（3）包含多于一个的连通分量。

根据构造取决于这3个条件。当遇到一个新的最小值时，符合条件（1）时，则将并入构成。当位于某些局部最小值构成的汇水盆地中时，符合条件（2），此时将合并到构成。当遇到全部或部分分离两个或更多汇水盆地的山脊线的时候，符合条件（3）。进一步的注水会导致不同盆地的水聚合在一起，从而使水位趋于一致。因此，必须在内建立一座水坝（如果涉及多个盆地就要建立多座水坝）以阻止盆地内的水溢出。当用个1的结构元素膨胀并且需要将这种膨胀限制在内时，一条一个像素宽度的水坝是能构造出来的。

通过使用与中存在的灰度级值相对应的值，可以改善算法效率；根据的直方图，可以确定这些值及其最小值和最大值。

1.第一种方法[1]

BCUCHER还提出了一种基于有向箭头的有序算法。算法有三个主要步骤：首先，找到图像中的区域最小值像素点（这些像素的领接像素的灰度值都不小于当前像素的灰度值）。然后，对于每一对像素，如果的灰度值严格大于，那么用一个箭头从指向，如图1.这样就可以用一种简洁的方式表示像素的领接的情况。最后，对区域最小值标记编号，并根据第二步中的箭头将这个标记值进行扩展。这种算法比前面的算法计算的速度快，但计算的结果也不是十分的精确。

图1

上述的这种方法存在几个问题：第一，运算量巨大，都必须连续的对整幅图像进行连续的多次扫描，非常的消耗时间。第二，迭代次数很不确定，并且每一次迭代都可能会对全图进行扫描，这样迭代次数可能十分巨大。所以此方法对图像处理的运算效率是非常低的。

2.第二种算法[3]

一种基于形态学滤波预处理和形态学梯度重建的分水岭图像分割方法。首先通过形态学滤波对图像进行滤波预处理，再求取图像的形态学梯度，之后对梯度图像进行开闭滤波重建。在简化梯度图像的同时，保持了轮廓分水线的准确定位，消除了产生过分割现象的根源，最后对重建后的梯度图像运用基于标记约束的分水岭算法进行分割。

分割过程可描述为：（1）对待分割图像进行形态学滤波；（2）计算滤波后图像的形态学梯度；（3）对梯度图像进行重建；（4）对重建后的梯度图像进行基于标记约束的分水岭 变换。

3.实例分析

用Matlab分割图像的结果是：

可以看出过分割得到了更好的抑制，同时边缘定位也比较准确，分割精度有了很大的改善，降底了算法的时间复杂度，所用时间比前一种方法少。

4.结论

本文通过介绍分水岭的数学意义，论述BCUCHER的基于有向箭头的有序算法与基于形态学滤波预处理和形态学梯度重建的分水岭图像分割方法，并对这两种算法进行了计算复杂性的比较，且在MATLAB的环境下进行了验证，得出的结论是：第二种方法在图像分割中的应用较好，降底了时间复杂度。但这两种方法都有可能产生过分割的情况，现在还不能找到避免此情况的方法，这有待我们进一步发展。

参考文献：

[1]吴海波.基于分水岭和水平集方法的图像分割算法研究[OL].（2012-02-27）.http：//www.doc88.com/p-846684201742.html.

[2]于庆刚.基于小波变换和分水岭算法的图像分割算法的研究[OL].（2012-04-07）.http：//www.doc88.com/p-084413955276.html.

[3]姬宝金，吕建平.基于梯度重建与形态学分水岭算法的图像分割[J].通信技术，2009，42（5）：99-102.