基于Watershed和Snake混合模型的图像分割算法

千堃，马银平，韩悬

（南昌航空大学信息工程学院，南昌330063）

0 引言

分水岭和蛇模型（主动轮廓模型）是两种用于图像分割的经典算法，均有其优缺点。分水岭具有创建单像素宽度的封闭边界的能力，并能够快速的实现分割算法[1]。通常，分水岭算法首先创建一个梯度图像，并将图像视为起伏地形，这样梯度图像的每个最小值在分割结果中都指向一个区域（或集水盆地）。分水岭算法[2]是一种图像分割的早期算法，为将形态学理论应用于图像分割的算法。近年来，这种方法被广泛应用于图像分割中，得益于其不同于其他算法的优点：在MATLAB仿真下算法的实现速度快；可以准确且迅速地捕捉图像边缘信息；也兼具良好的轮廓线封闭性。由于分水岭分割算法在最初的时候是用于分析和处理二值图像，因此为了得到更加适用于图像分割的通用模型，这便使得分水岭的相关理论和相关算法得以建立，后期便大量应用于对不同性质的图像实现精确分割。分水岭算法的早期阶段，由于不能克服图像的噪声干扰，会产生过分割等多种不良分割结果。改进的层次分水岭分割在一定程度上可以克服过分割[3]，但区域合并过程对水平参数过于敏感，即感兴趣的区域对象会迅速合并到邻域对象中，导致分割结果不理想。Kass等人提出了活动轮廓模型被定义为能量最小化样条[4]。随后，基于Snake模型的改进模型不断涌出，常见的有GVF Snake模型[5]、Balloon Snake模型[6]、距离势力模型[7]、T-Snake模型[8]等。Snake模型[9]通过在感兴趣的目标周围区域布置初始轮廓曲线，建立能量泛函方程，然后曲线在自身机制能量约束以及图像力产生的外力作用下，使得该轮廓曲线收敛到目标图像的边缘，完成图像的分割，是一种非常经典的曲线演化模型。但Snake模型在实际应用中，也有着无法忽视的缺点。例如，初始轮廓必须足够接近感兴趣的物体在图像区域内的边界，否则无法得到真实的收敛结果。另一个问题是由于它的内部弹性和刚性的力量使其无法收敛到凹陷区域。GVF Snake模型[10]可以收敛到凹陷区域，但当图像噪声较强时，会产生错误的分割，进而也不能将图像分割出来。

因此，为了融合分水岭变换和Snake模型的优点，克服它们的缺点，本文首先利用形态学等相关操作，对图像采用强制标记技术解决过分割问题。然后得到改进之后的分水岭算法的边缘曲线，以用于Snake模型的边缘的初始优化，最后采用遗传算法进一步提升对图像的分割精度，最大程度地保证可以精准图像分割。

1 改进的分水岭算法及其优化

1.1 传统的分水岭算法

分水岭的思想[11]是根据地形学中的思想得到的，是一种通过自上而下采用迭代思想形成区域的方法。分水岭算法是结合地理学的图像分割算法，将图像整体类比为一个地貌，而图像中像素的不同灰度值就等同于地形中的海拔值，地貌上存在的极小值及其相关区域共同构建集水盆，集水盆的边界便就是分水岭，如图1所示。利用地理学上的类比思想，从表面的局部极小值开始，然后慢慢地将图像浸入水中，水逐渐淹没极小值对应的盆地，如图1（a）。为了防止由两个不同的极小值引起的两个不同的集水盆的合并，便在两条线之间建立了一个堤坝，如图1（b）箭头所指的位置，一旦地表完全浸没，所建造的堤坝便是图像的分水岭。具体的分水岭算法实现思想实现为：首先求出梯度图像，随后将其用于输入图像应用到分水岭算法，最后再根据不同情况调整参数，做不同处理。这种早期计算方法是由L.Vincent[12]提出的。梯度图像求解公式：

其中，f(x,y)代表图像，grad(∙)为图像的梯度算子，g(x,y)则表示图像经过梯度算子运算后的输出结果。

图1 分水岭的形成

1.2 改进的分水岭算法

本文采用形态学等相关算法，来克服分割过程中出现的过分割问题。算法流程如下：

（1）使用双边滤波去噪并保护弱边缘区域，计算出梯度幅值图像。

（2）对处理过的图像进行形态学相关处理。

（3）使用OTSU阈值分割法和灰度调整对脑肿瘤进行前景标记。

（4）通过距离变换的分水岭来实现背景标记。

（5）用相关函数修改梯度幅值图像，使其只在标记位置有局部极小值。

（6）分水岭分割结果。

算法流程如图2所示。

图2 算法流程图

采用脑肿瘤图像为测试图像，验证改进的分水岭算法。结果如图3所示。

图3 实验结果对比图

2 Snake模型的优化其传统Snake模型原理与方法

2.1 传统Snake模型

Kass首次提出了经典的参数可形变模型（Snake模型）后，Snake模型就被大量学者广泛应用于图像分割以及其他领域中。Snake模型的轮廓曲线可定义为形如v(s)=(x(s),y(s)),s∈[0,1]样条曲线，s表示归一化弧长参数，为平面上的坐标点。能量函数约束着样条曲线的迭代方向，最终收缩在目标区域周围。Snake模型轮廓曲线的能量函数可以定义如下：

由上式可知，Snake模型主要由两部分组成，分别是内部能量（内部力）Eint和外部能量（外部力）Eext。在实现Snake模型算法的过程中，由一系列离散的点来控制分割区域的收束vi(i=1,2,…,N)，将公式（2）离散化后，可得到能量泛函的离散形式，如下所示：

式中，vi-vi-1代表控制点的一阶导数，vi+1-2vi+vi-1代表控制点的二阶导数。将能量泛函Esnake利用欧拉方程离散化求解其最小值，可得下式：

其中，v"(s)为轮廓曲线的二阶导数，v""(s)为轮廓曲线的四阶导数，∇Eext为外部力能量梯度。该方程同时也可看作是一个能量平衡方程：

式中Fint(s)=αv"(s)-βv""(s)，Fext(s)=-∇Eext。

为便于计算，引入时间参数t作为曲线变化的自变量，即v(s)=v(s,t)，公式（5）的解也即可通过下式求解得到：

vt(s,t)为v(s,t)对时间t求偏导，vt(s,t)=0，表示为曲线基本停止演化，轮廓曲线收缩到目标的边缘区域，完成了分割图像。在实际操作中，为了节省资源，可以采取人工设置初始控制点的方式，再对能量函数进行迭代求解。离散Snake模型收敛迭代方程为：

式中，A是五角带状矩阵，主要有由α和β两个系数所确定的，I为单位矩阵，γ为步长，Fx和Fy分别为外力在x方向和y方向上的偏导数。通过迭代计算，可求得演化曲线的最终位置。

为了便于提供一种客观、可重复、易使用的分割方法，本文在MATLAB环境下开发了一个GUI软件平台，在搭建的GUI界面下，对同一副杯盖图像采用Snake模型分割，但初始轮廓不同，迭代相同的次数N=125，最终迭代结果如图4（c）和图5（c）所示。由迭代结果可以看出，初始轮廓距离目标边缘越近，获取的目标轮廓越精确。由于Snake模型对初始位置敏感，需手动获取初始位置点，且对初始位置的获取具有不确定性，因此本文将结合分水岭算法的优点，解决Snake模型存在的这一问题，通过改进的分水岭算法对Snake模型的初始轮廓作进一步优化。

图4 第一组实验（α=0.4,β=0.2）

图5 第二组实验（α=0.4,β=0.2）

2.2 Snake模型初始轮廓的优化

本节将利用改进的分水岭算法解决Snake模型对初始轮廓线位置敏感的问题，并通过遗传算法[12-13]优化分割结果，从而实现精确分割。初始轮廓优化算法主要步骤如下：

（1）对图像采用OTSU阈值分割法自动求出阈值w进行分割，得到每个像素点的灰度fb(x,y)定义为：

（2）用形态结构元素对（1）得到的结果图像作形态学开运算，得到标记函数为：

此函数的作用是将标记部分的值记为0，非标记部分值记为1。

（3）对梯度函数g用图像fm(x,y)进行强制最小值操作，得到待分割图像：

该表达式的含义为，当(x,y)为标记点时，fm(x,y)的值为0，对应的fmin(x,y)值也为0，反之，当(x,y)不是标记点时，fmin(x,y)的值就为梯度函数g(x,y)。

（4）对fmin(x,y)进行分水岭变换，图像的区域边界便是离散的点：V={V1,V2,…,VL}，V的中点Vi=(Xi,Yi),i={1,2,…,L}是分水岭变换后确定为分水岭的点的子集。

将分水岭变换得到的轮廓线作为Snake模型的初始轮廓线[14-15]，但Snake模型存在对噪声敏感，模型能量函数易陷入局部极小值且分水岭算法分割后得到的轮廓线光滑性较差。因此需要利用遗传算法进行全局优化。

2.3 遗传算法优化Snake模型

（1）初始种群的构造

在演化好的Snake模型上，其轮廓线由N个离散点{v0,v1,…,vn-1}构成，在vi处Snake曲线的法线上，按一定间隔取点，随机选中所取得点（i=0,1,...,N-1，这N个点可视为一个染色体，重复M次取点操作，便可得到M个染色体组成的一个种群，每一条染色体包含的节点个数都相同。

（2）适应度函数

将Snake能量函数作为目标函数：

其 中，λ∈[0,1],vi=(xi,yi),i=1,2,…,N代 表 了Snake模型曲线上的各个离散点。为了使Snake模型的分割结果更加接近真实边界以及轮廓曲线更加光滑，在此增加一项外部能量。

最后可将适应度函数定义为：

其中M'足够大，保证M'-E>0。在选取的初始种群和适应度函数的基础上，对种群进行变异、交叉、选择等基本遗传算法操作，随后进行最优迭代，直到得到最优的分割结果。

3 实验结果和评价

为了对上述改进算法的验证，本文随机选取了三幅特征不同的图片作为本文的验证图，分别为圆、复杂的脑肿瘤图像和五角星图像，见图6。本文实验验证的平台为Windows 7下的MATLAB R2014a软件，三组实验中参数的取值为：弹性力系数：α=0.4，刚性力系数：β=0.2，步长：γ=1，传统的Snake模型分割算法迭代次数：N1=200，本文改进的分割算法迭代次数：N2=50，种群大小：M=50，交叉概率：Pc=0.1，变异概率：Pm=0.02。

图6 实验验证用图

3.1 实验1仿真结果及分析

对于较规则的圆形图，从图7（b）可看出，传统Snake模型的收敛效果也不是很理想；用改进的分水岭算法结合Snake模型后，便可以得到较好的分割结果，仿真结果如图7（d）；用遗传算法优化上一步的结果，能够得到如图7（e）所示的分割图。

3.2 实验2仿真结果及分析

对于较复杂的医学图像图8（a）而言，当初始轮廓线不在目标边缘附近时，传统的Snake模型无法收敛到目标边缘，如图8（b）；结合分水岭算法后的结果如图8（d），可以看出分割精度大大改善；再进一步优化后的结果更为理想，如图8（e）。

3.3 实验3仿真结果及分析

传统的Snake模型对于不规则图像的分割效果很不理想，如图9（b）；结合分水岭后的分割结果有了大大的改进，但对于拐角点处的部分，收敛效果也不是很理想，如图9（d）；最后使用遗传算法优化，分割效果有了较好的改进，如图9（e）。

为了对三种模型的分割效果有个直观的认识，引入TP（精度）、FP（误检率）、FN（漏检率）以及平均分割时间t对分割结果进行定量评估，评估结果如表1所示。从表中数据可以看出，本文所提出的混合模型分割算法，与Snake模型、改进的分水岭模型相比，具有更高的分割精度和更低的漏检率、误检率。

图7 圆仿真结果

图8 脑肿瘤仿真结果

图9 五角星仿真结果

表1 三种模型的分割结果对比

4 结语

分水岭算法可以提供精确的单像素宽度的闭合轮廓，但其主要难点是过度分割。Snake模型可以动态得确定目标边界区域，但其存在着捕获范围窄，收敛性差的问题。分水岭算法可以为Snake模型的演化提供初始轮廓，引导Snake模型向着目标边界移动。因此，结合Snake模型和分水岭算法的优缺点，使其互补，经过不断改进，得到最优的混合算法。本文提出的混合边界检测算法验证了两种算法结合的好处：第一，提高了传统Snake模型的捕获范围和缓解了Snake模型对初始轮廓敏感以及不能收敛到凹陷区域的缺点。第二，通过利用遗传算法进行优化，提高了分割的精度，倾向于生成精确的目标轮廓；第三，混合算法迭代次数少，因为分水岭轮廓已经在感兴趣目标的附近位置。但加入了遗传算法的优化后，会使得分割时间过长，还需要进一步研究以解决这一步问题。