基于区域分离与聚合的分水岭分割*

王 祥 罗素云

（上海工程技术大学机械与汽车工程学院 上海 201620）

1 引言

图像分割是按照某种设定的规则，将一幅待处理图像划分成为若干互不相交的、有明显边缘区分的局部区域过程，同时这也是图像处理研究领域的重要分析方法。分水岭变换则是基于数学形态学的一种图像分割算子，可将待处理图像分割成若干不重合的区域，它与传统依据边界梯度的图像分割技术（如Canny 算子和Laplace 算子）相比，分水岭算法能够获得像素宽的、连续的边界，但是它也存在着分割速度慢和过分割等问题。目前已提出了各种在分水岭变换基础上进行改进的图像分割方式，文献［1］提出一种边缘走向自适应的多尺度分水岭遥感图像分割算法，采用多尺度标记算法进行标记分水岭分割；文献［2］提出一种先求形态梯度图像的浮点活动图像，再进行分水岭变换的图像分割方法；文献［3］提出了一种基于粒子群和区域生长的改进分水岭算法；文献［4］提出了一种根据梯度图像的多尺度信息，构造相似性函数的改进的快速分水岭变换算法；文献［5］提出了一种改进的基于标记提取的分水岭算法，改进后的算法由平滑滤波、彩色梯度计算、标记提取和分水岭变换组成；文献［6］提出了一种先进行分水岭变换再用Normalized Cut 方法在区域之间进行分割，产生最终所分割的图像；文献［7］提出一种自适应梯度重建分水岭分割算法，该方法首先利用PCA技术对彩色图像降维，然后计算降维后的梯度图像并采用自适应重建算法修正梯度图像，对修正梯度图像采用分水岭变换完成对彩色待处理图像的合理分割；文献［8］提出在Normalized Cut 方法基础上利用合并-分裂方式，合并颜色纹理相似区域，并对部分区域继续做Normalized Cut分割；文献［9］提出将RGB彩色图像转化至新的彩色空间，并利用形态学开闭重构，标记后将梯度图像分水岭变换进行分割；文献［10］提出多尺度形态滤波器对输入噪声图像及滤波后的梯度图像进行平滑处理，实现消除噪声和优化待处理图像，然后快速区域合并算法优化分割。为了抑制分水岭变换的过分割问题，本文提出了一种先进行拉普拉斯滤波和区域分离与聚合再进行分水岭变换的图像分割方法。理论分析和实验结果证明了该方法的可行性。

2 预处理滤波

待分割原始灰度图像在分水岭变换之前，可以先利用二维线性空间滤波器，通过fspecial函数，选择一个合适的滤波模板w，本文选择一个大小为3×3 的拉普拉斯滤波器算子，该算子定义为∇2f(x，y)：

在x方向上，有：

在y方向上，有：

所以，依据上述公式可推算两个变量的拉普拉斯算子为

使用拉普拉斯微分算子进行图像增强的基本公式为

式（5）中的c当模板w 中心系数为正时取1，否则取-1。

本文通过拉普拉斯滤波预处理，可以将待分割图像区域边界进行锐化增强，作为最简单的各向同性微分算子，此过程具有旋转不变性，同时尽可能地保留原始灰度图像的灰度层次，较为适合本文图像分割过程。

3 区域分离与聚合

令R 表示整幅图像区域，可将分割视为把R 分为n个子区域R1，R2，··· ，Rn的处理，即：

条件1）表示分割必须完全；条件2）表示区域点必须连续；条件3）表示各个区域必须互不相交；条件4）表示区域内像素点属性相同；条件5）表示不同区域内属性不同。

选择一种属性P，对R 进行分割处理的一种规则是逐次细分成四个象限区域，测试对于局部区域Ri有P（Ri）=TRUE。从整个区域开始，如果P（R）=TRUE，我们把图像分为四象限区域。若对于每个象限区域P 为FALSE，则将该象限区域再细分为四个子象限区域，以此类推。这种特殊的分离技术可以形象地表示为四叉树的形式，即每个节点都正好有四个后代，如图1 所示（对应一个四叉树的节点的图像有时称为四分区域或四分图像）。其中，树根可以代表待处理图像，而其后每个节点可对应于四个后支节点。在这种情况下，仅进一步细分了R4。

图1 四叉树模型示意图

如果只采用分离的方式处理，只会得到具有相同属性的相邻区域。然而通过聚合与分离的改进方式，可以克服这个弊端。前提是满足上述提出分割约束条件1）～5），则仅要求聚合其组合像素满足属性P 的相邻区域。也就是说，两个相邻的区域Ri和 Rj仅当P(Ri∪Rj)=TRUE时才能聚合。

上述过程可以总结如下：

1）将满足条件的P（R）i=FALSE 的任何区域Ri分离为四个不相交的象限区域。

2）当不能进一步分离时，聚合满足条件P(Ri∪Rj)=TRUE的任意两个相邻区域Ri和Rj。

3）当不能进一步聚合分区域时，停止分离与聚合操作。

算法终止条件是规定不能再执行分裂的最小四象限区尺寸。

4 分水岭变换

分水岭可以形象成为山脊，通过山脊的不同方向的水系来形成集水盆地。集水盆地在地理上是指把水排入河流或水库的区域。分水岭变换则是类比于这些概念，推广到灰度图像处理过程中，以期解决图像分割问题。

图2 分水岭示意图

理解分水岭变换时要求把灰度图像视为一个拓扑表面，表面中f（x，y）的值被理解为高度。例如，图2（a）中的简单图像形象化为图2（b）中的三维表面。假设雨水流淌在该表面区域，就会流入到两个积水盆地中心，而正好处在脊线上的雨水会等概率地流向两侧。分水岭变换则是需要找到灰度图像的积水区域和脊线，在进行图像分割时，重点在于完成起始图像转换，转换后图像中的集水盆地就是要提取的区域。

分水岭变换是一种基于区域和建立在数学形态学理论基础之上的算法，但存在着对图像中噪声极其敏感而产生过分割和对低对比度图像易丢失重要轮廓的缺点，主要有以下两种算法：

1）自下而上式模拟泛洪的算法。

2）自上而下式模拟降水的算法。

4.1 模拟泛洪的算法

此类算法是从模仿高低不平的地势环境，洪水从各个区域极小值点开始水位上溢，地势较低各区域将逐渐充满积水。洪水上涨至各区域的边缘，各低地势点溢出的洪水便会交集。若在洪水交集的边缘筑坝分割洪水，此时被分割的区域就形成了一个集合，这个集合区域就是图像的一个分割区域，区域边界处筑起的防水坝就称为分水岭，这种模拟过程就叫做泛洪。模拟泛洪的分水岭算法的工作原理如图3所示。

4.2 模拟降水的算法

模仿降水分割算法模拟：地势不平的区域上，雨水会沿着地势表面向下流淌，同一凹陷区域上雨水最终会流向相同局部最低地势点，那么可以称这样的雨水落点属于同一区域，这个凹陷区域为同区域，而山顶上的雨水流入四周地势的概率是相同的。可想而知，雨水流向趋势一致的落点形成一个区域即为图像的一个分割区域，山顶点连接而成这个区域的边界，即是分水岭。模拟降水分水岭算法的工作原理如图4所示。

图3 模拟泛洪示意图

图4 模拟降水示意图

4.3 分水岭分割算法

本文采用的分水岭分割方法如下所示。

记M1，M2，…，MR是待处理图像g（x，y）局部区域极小值坐标集。记C（Mi）是区域极小值Mi相对应的雨水流势相同坐标集合（任何集水盆地中的点都形成一个连通分量）。符号min 和max 将用于表示g（x，y）的最小值和最大值。最后，令T［n］表示满足g（s，t）＜n的坐标（s，t）的集合，即：

几何学上来看，T［n］是g（x，y）中位于平面g（s，t）=n 下方的点的坐标的集合。从模拟泛洪的过程来看，水位从min+1 到max+1 逐渐上升，图像就会逐渐被水淹没。在像素值等于n 时，分水岭算法必须统计被淹没像素点数量。理论上，算法将处在g（x，y）=n 平面以下的 T［n］中的坐标区分为黑色点集，其他坐标就区分为白色点集。在像素值平面增加到n 时向下观察x-y 平面，就会得到T［n］二值图像，图像中的黑色点集就是平面g（x，y）=n 之下的区域。

记Cn（Mi）为集水区域中与淹没阶段n 的最小值Mi相对应的点坐标集，则Cn（Mi）可以看成由式（7）给出的二值图像：

换句话说，如果（x，y）∈ C（Mi）和（x，y）∈ T［n］进行“与”逻辑运算，则在位置（x，y）处有Cn（Mi）=1，否则Cn（Mi）=0，可以理解成在淹没像素值n 时只需要使用“与”（AND）算子将T［n］中的二值图像提取出来即可。

继而，记C［n］表示在淹没像素值n时集水区域的“并”：

然后，记C［max+1］表示集水区域的“并”：

执行算法时，不会替换Cn（Mi）和T［n］中的元素，淹没像素值n 增大时，Cn（Mi）和T［n］中的元素的数量要么增加，要么保持相同。简言之，C［n-1］其实就是C［n］的子集。根据式（7）和式（8）可以得出，C［n］是T［n］的子集，C［n-1］也就属于 T［n］。由此可以得出结论，T［n］的一个连通分量包含C［n-1］中的每一个连通分量。

分水线算法初始化条件为C［min+1］=T［min+1］，依次进行递归处理，通过C［n-1］计算得到C［n］。通过 C［n-1］计算 C［n］的过程：记 Q 表示 T［n］中的连通分量集合，对于每个连通分量q∈Q［n］，有如下三种可能性：

1）q∩C[n-1]为空集。

2）q∩C[n-1]包含C［n-1］的一个连通分量。

3）q∩C[n-1]包含C［n-1］的一个以上的连通分量。

通过C［n-1］构建C［n］的过程取决于上述三个条件之一。新的极小值出现时，可能性1）就会发生，此时连通分量 q 并入C［n-1］中形成 C［n］。可能性2）中q位于某些局部最小值的集水区域，此时q 并入C［n-1］中形成C［n］。当全部以及部分分割两个以上集水区域山脊线出现时，可能性3）发生。继续淹没会导致集水区域水位聚合。所以，需要在q 内构筑一个水坝（如果涉及多个集水盆地，则要构筑多个水坝）以阻止集水区域间的水位聚合。

本文是在预处理拉普拉斯滤波和区域分离与聚合的基础上进行的，并具有一定的可操作性和可行性。区域分离与聚合后的图片能提前划分小范围区域，对后续分水岭变换有一个预分割的作用。

5 实验结果与分析

为了检验本文提出的改进分水岭变换算法，本文作者在Windows 7 操作系统下，实验软件为Matlab R2017 的实验条件下，进行Matlab 编程仿真验证了多组图片，实验结果如下。

由以上 A 组、B 组、C 组和 D 组的原始灰度图像、传统分水岭分割图像和本文提出改进分水岭分割图像可以分析得到结论：本文提出的改进分水岭变换算法图像分割可以很大程度上减轻传统分水岭图像分割的过分割现象，图像分割的准确性得到明显的提高。

图5 A组分割效果对比图

图6 B组分割效果对比图

图7 C组分割效果对比图

图8 D组分割效果对比图

6 结语

本文在对分水岭变换算法进行深入研究的基础上，提出一种基于区域分离与聚合的改进分水岭变换分割算法。实验结果表明，本文所采取的改进分水岭变换图像分割能一定程度上弱化过分割现象，能够取得更好的图像分割效果。但是，本文提及算法并不能解决低对比度图像易丢失重要轮廓等问题。因此，本文提及算法对于抑制图像过分割现象具有一定的实际应用价值。