基于Snake的图像分割算法研究

摘要：图像分割算法是指从待割图像中提取出感兴趣的目标，以便进行图像分析与图像理解。Snake算法不同于传统的图像分割方法。文中详细介绍了Snake模型的数学机理及离散化方法，最后利用贪婪法实现了Snake算法，并应用与实际图像的分割。

关键词：图像分割；Snake模型；贪婪算法

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2014）13-3064-03

Abstract： Image segmentation algorithm means to be cut from the image to extract the target of interest for image analysis and image understanding. Snake algorithm differs from the traditional image segmentation methods. Paper describes in detail the mechanism and discrete mathematical method Snake model， and finally the use of law to achieve the Snake greedy algorithms， and applications and the actual image segmentation.

Key words： Image segmentation； Snake models； greedy algorithms

1 概述

图像分割就是把输入的图像进行区域划分，分割成一系列感兴趣的区域，这项工作对于人类视觉能直接轻松地完成，对机器视觉而言确是一个难题，至今还没有一种图像分割算法能处理所有的图像分割问题，只能就某个具体问题，利用对应的算法进行分割，一种方法应用于某一类图像分割可以，应用到另一类图像分割时就没有效果了。常见的图像分割方法有阈值法、边缘检测法、区域生长法、分水岭法等，这些方法都利用到图像底层信息，在像素级要素上进行处理。而Snake算法则打破了这一局限，能利用图像的高层信息，能将图像分割问题转化成数学上求能量泛函的问题，又基于微分方程，利用差分、有限元等方法将其离散化，利用计算机进行算法迭代，求解图像分割结果。

2 Snake模型机理

2.1 经典Snake模型

Kass等人提出的经典Snake模型由一组控制点组成：

[v（s）=[x（s），y（s）]] [s∈[0，1]] （2-1）

x（s）和y（s）分别表示每个控制点在图像中的坐标位置，s是以傅立叶变换形式描述边界的自变量，轮廓线的能量由内部能量和外部能量组成，基本的能量构成表示为：

[Etotal=CEInternal+EExternal=CEElastic+EBending+EExternal] （2-2）

其中：

[EElastic=12Cα（s）vs2ds] （2-3）

[EBending=12Cβ（s）vss2ds] （2-4）

[EExternal=-γ（s）?I（v（s））2] （2-5）

[EElastic]为弹性能量，[EBending]为弯曲能量，[vs]和[vss]是v（s）对于s的一阶和二阶导数[vs=dv（s）ds]，[vss=d2v（s）ds2]。一阶导数反映曲线的连续性，二阶导数反映曲线的平滑性。在活动轮廓发生形变时，弹性能量使轮廓收缩，弯曲能量抵抗变形，保持曲线平滑。[EExternal]为外部能量，也称图像力，主动轮廓模型的关键就在于如何定义外部能量，使得能量的最小化满足期望结果的图像特征。

2.2 Snake模型离散化

针对Snake能量方程（2-1）式可知，Snake总能量包含内部能量和外部能量，内部能量为弹性能量、弯曲能量、面积能量。外部能量被认为是图像能量。

假定[{V1，V2，…，Vn}]是Snake上的n个点，snake的总能量可表达为各点的能量之和。

[minEsnake=min（Ev1+Ev2+…+Evn）] （2-6）

当Snake能量最小时，各点能量也趋于相对平衡状态，即认为各点也达到能量最小化，把点[Vi]能量最小化的公式如下：

[E（Vi）=min0

式（2-7）中的winsize为搜索窗口的大小，[Vi]代表第[i]个Snake点或其位置。[Vi，j]为第[i]个Snake点在搜索窗口中[j]处的点，[j]的范围在除去Snake点所在位置搜索窗所有点。[Econt（Vi，j）]、[Ecurv（Vi，j）]、[Eimg（Vi，j）]分别对应于弹性内部能量（continuity）、弯曲内部能量（curvature）、图像外部能量（image）（有时还包括约束（constraint）能量）。[α]、[β]、[γ]为相应的权值。

三个能量对应的离散化公式如下：

[Econt（Vi，j）=|d-|Vi，j-Vi-1||max0

每个点都会被连续的弹性能量牵引到前继点，而远离后继点，如果没有控制将收敛于图像轮廓强边缘附近，因而，点与点之间应该有一个距离对曲线运动较好，式（2-8）中的[d]为snake点间的平均距离，接近平均距离的Snake点能量值较小，这样Snake点分布较为均匀。[d]可求为：

[d=1Ni=0N-1|Vi-Vi-1|] （2-9）

式（2-10）和（2-11）为图像的曲线能和图像能。它调节Snake中像素的强度，即归一化Snake的外部能量，使其不致于因像素灰度差别，而产生太大外部能量差异。其中[I（Vi，j）]为第[i]个Snake点对应窗口中[j]位置的灰度值，[minGray]、[maxGray]为窗口中最小和最大的灰度值。

[Eimg（Vi，j）=minGray-I（Vi，j）maxGray-minGray] （2-10）

[Ecurv（Vi，j）=|Vi-1-2Vi，j+VI+1|2max0

该点处真实强度为式（2-10）所示，如果[maxGray-minGray]小于指定的门限值，则将[minGray]设置为[minGray=maxGray-门限值]，这就是归一化处理。

3 算法实现

3.1贪婪算法的描述

贪婪算法，假定曲线上其他各点均处在最佳位置，计算当前控制点的能量时，与其它各点均不相关，当计算出了当前控制点的下一个被趋向的位置时，就更新其位置。具体为：

1） 打开图像，对图像绘制初始轮廓。

2） 初始化参数，开始处理。

3） 计算Snake轮廓线上各点之间的距离平均值。

4） 通过循环，计算点的邻域中具有最小能量的点temp，将控制点更新成点temp。

5） 计算弹性能量，弯曲能量，图像外部能量，并归一化各点曲率能量。

6） 进行自适应判定是否增加、删除点。

7） 判定收敛条件，如果满足条件结束程序，否则程序转入（3）。

其中，算法步骤（6）的自适应判断准则为：

当2个相邻顶点之间的距离大于某个预定的门限，或当2个相邻顶点的中间点明显不是边缘点或当曲率大于某个预定的门限时，在这2个顶点中间增加1个新的顶点。

当2个相邻顶点的距离小于某个预定的门限时，这样的2个顶点用它们的中间点代替。当3个相邻顶点距离较近且几乎成一条直线时，去除这3个相邻顶点的第1个顶点。

算法步骤（7）采用的收敛的判断准则是：

当总能量不再改变或出现周期性波动或达到设定的迭代次数时，认为算法收敛。在能量最小化过程中的每一次循环中，在每一个顶点的邻域范围内搜索能量极小点来替换原来的顶点。

3.2分割实验

分割实验主要考察初始位置、Snake模型参数对图像分割影响。

考察24位真彩图片“香蕉”的分割：

1） 分割条件：规定参数轮廓线的弹性系数=0.5，抗弯曲的系数=0，Gaussian函数标准方差=3。红色为初始轮廓线，蓝色为分割结果。

2） 在不同初始轮廓曲线条件下Snake模型的分割效果，如图1所示：

图1 香蕉在不同初始轮廓下的分割效果

图1（a）、图（b）对应一组分割对应的分割，红色初始轮廓把“香蕉”图片全部内部，由于有灰色光影的影响，图像未能正确分割；

图1（c）、图（d）对应一组分割对应的分割，红色初始轮廓跨越了“香蕉”图片，图像未能正确分割；

图1（e）、图（f）对应一组分割对应的分割，红色初始轮廓接近“香蕉”图片，图像正确分割。

3） 结论：由上图可见初始位置，不同分割的效果，大相径庭。

第二个实验考察Snake参数对分割性能的影响。

限于篇幅，我们对如图2像进行反复实验，得到较满意的分割效果：

图2 多次实验后满意的结果

图3 多次实验不容易得到满意效果

总结经验，得到以下结论：

1） 一般轮廓线的弹性系数α，刚性系数β被设置为常值，因为β是二阶的平方后的系数，对分割影响较小，实际处理时，令β为零。

2） 对于轮廓线的弹性系数α取值过于偏小时，轮廓线通常被噪声吸引，不能正确分割，轮廓线极不光滑；当弹性系数α取值过于偏大时，轮廓线也过于光滑，不能准确分割目标的凹角与突角。

3） 考察Gaussian函数标准方差σ，当σ 值增大时，有效 Gaussian 势能力的分布范围也相应地扩大，并且 Snake 模型的分割结果受噪声的影响相应地减弱，但是，当σ 的取值过于大时，Snake 模型的最终轮廓线可能会偏离目标边界。一般情况下取值为3～8。

4） 深凹一类的图像，需要设置好初始曲线，如果只简单勾画初始曲线，会导致图像分割失败，曲线不易深入深凹区域。

4 总结

Snake模型能利用图像高层信息，能正确分割图像，但是有一些约束即，1）图像的初始位置离图像的真实边界很近，2）初始曲线不要放在同一介质的图像的内部。

Snake算法有待学者进一步研究与改进。

参考文献：

[1] （美）冈萨雷斯等著. 阮秋琦等译.数字图像处理（第二版）[M].北京：电子工业出版社，2007.

[2] Williams D J，Shah M.A Fast algorithm for active contours and curvature estimation[J].CVGIP： Image Understanding，1992，55（1）：14-26.

[d=1Ni=0N-1|Vi-Vi-1|] （2-9）

式（2-10）和（2-11）为图像的曲线能和图像能。它调节Snake中像素的强度，即归一化Snake的外部能量，使其不致于因像素灰度差别，而产生太大外部能量差异。其中[I（Vi，j）]为第[i]个Snake点对应窗口中[j]位置的灰度值，[minGray]、[maxGray]为窗口中最小和最大的灰度值。

[Eimg（Vi，j）=minGray-I（Vi，j）maxGray-minGray] （2-10）

[Ecurv（Vi，j）=|Vi-1-2Vi，j+VI+1|2max0

该点处真实强度为式（2-10）所示，如果[maxGray-minGray]小于指定的门限值，则将[minGray]设置为[minGray=maxGray-门限值]，这就是归一化处理。

3 算法实现

3.1贪婪算法的描述

贪婪算法，假定曲线上其他各点均处在最佳位置，计算当前控制点的能量时，与其它各点均不相关，当计算出了当前控制点的下一个被趋向的位置时，就更新其位置。具体为：

1） 打开图像，对图像绘制初始轮廓。

2） 初始化参数，开始处理。

3） 计算Snake轮廓线上各点之间的距离平均值。

4） 通过循环，计算点的邻域中具有最小能量的点temp，将控制点更新成点temp。

5） 计算弹性能量，弯曲能量，图像外部能量，并归一化各点曲率能量。

6） 进行自适应判定是否增加、删除点。

7） 判定收敛条件，如果满足条件结束程序，否则程序转入（3）。

其中，算法步骤（6）的自适应判断准则为：

当2个相邻顶点之间的距离大于某个预定的门限，或当2个相邻顶点的中间点明显不是边缘点或当曲率大于某个预定的门限时，在这2个顶点中间增加1个新的顶点。

当2个相邻顶点的距离小于某个预定的门限时，这样的2个顶点用它们的中间点代替。当3个相邻顶点距离较近且几乎成一条直线时，去除这3个相邻顶点的第1个顶点。

算法步骤（7）采用的收敛的判断准则是：

当总能量不再改变或出现周期性波动或达到设定的迭代次数时，认为算法收敛。在能量最小化过程中的每一次循环中，在每一个顶点的邻域范围内搜索能量极小点来替换原来的顶点。

3.2分割实验

分割实验主要考察初始位置、Snake模型参数对图像分割影响。

考察24位真彩图片“香蕉”的分割：

1） 分割条件：规定参数轮廓线的弹性系数=0.5，抗弯曲的系数=0，Gaussian函数标准方差=3。红色为初始轮廓线，蓝色为分割结果。

2） 在不同初始轮廓曲线条件下Snake模型的分割效果，如图1所示：

图1 香蕉在不同初始轮廓下的分割效果

图1（a）、图（b）对应一组分割对应的分割，红色初始轮廓把“香蕉”图片全部内部，由于有灰色光影的影响，图像未能正确分割；

图1（c）、图（d）对应一组分割对应的分割，红色初始轮廓跨越了“香蕉”图片，图像未能正确分割；

图1（e）、图（f）对应一组分割对应的分割，红色初始轮廓接近“香蕉”图片，图像正确分割。

3） 结论：由上图可见初始位置，不同分割的效果，大相径庭。

第二个实验考察Snake参数对分割性能的影响。

限于篇幅，我们对如图2像进行反复实验，得到较满意的分割效果：

图2 多次实验后满意的结果

图3 多次实验不容易得到满意效果

总结经验，得到以下结论：

1） 一般轮廓线的弹性系数α，刚性系数β被设置为常值，因为β是二阶的平方后的系数，对分割影响较小，实际处理时，令β为零。

2） 对于轮廓线的弹性系数α取值过于偏小时，轮廓线通常被噪声吸引，不能正确分割，轮廓线极不光滑；当弹性系数α取值过于偏大时，轮廓线也过于光滑，不能准确分割目标的凹角与突角。

3） 考察Gaussian函数标准方差σ，当σ 值增大时，有效 Gaussian 势能力的分布范围也相应地扩大，并且 Snake 模型的分割结果受噪声的影响相应地减弱，但是，当σ 的取值过于大时，Snake 模型的最终轮廓线可能会偏离目标边界。一般情况下取值为3～8。

4） 深凹一类的图像，需要设置好初始曲线，如果只简单勾画初始曲线，会导致图像分割失败，曲线不易深入深凹区域。

4 总结

Snake模型能利用图像高层信息，能正确分割图像，但是有一些约束即，1）图像的初始位置离图像的真实边界很近，2）初始曲线不要放在同一介质的图像的内部。

Snake算法有待学者进一步研究与改进。

参考文献：

[1] （美）冈萨雷斯等著. 阮秋琦等译.数字图像处理（第二版）[M].北京：电子工业出版社，2007.

[2] Williams D J，Shah M.A Fast algorithm for active contours and curvature estimation[J].CVGIP： Image Understanding，1992，55（1）：14-26.

[d=1Ni=0N-1|Vi-Vi-1|] （2-9）

式（2-10）和（2-11）为图像的曲线能和图像能。它调节Snake中像素的强度，即归一化Snake的外部能量，使其不致于因像素灰度差别，而产生太大外部能量差异。其中[I（Vi，j）]为第[i]个Snake点对应窗口中[j]位置的灰度值，[minGray]、[maxGray]为窗口中最小和最大的灰度值。

[Eimg（Vi，j）=minGray-I（Vi，j）maxGray-minGray] （2-10）

[Ecurv（Vi，j）=|Vi-1-2Vi，j+VI+1|2max0

该点处真实强度为式（2-10）所示，如果[maxGray-minGray]小于指定的门限值，则将[minGray]设置为[minGray=maxGray-门限值]，这就是归一化处理。

3 算法实现

3.1贪婪算法的描述

贪婪算法，假定曲线上其他各点均处在最佳位置，计算当前控制点的能量时，与其它各点均不相关，当计算出了当前控制点的下一个被趋向的位置时，就更新其位置。具体为：

1） 打开图像，对图像绘制初始轮廓。

2） 初始化参数，开始处理。

3） 计算Snake轮廓线上各点之间的距离平均值。

4） 通过循环，计算点的邻域中具有最小能量的点temp，将控制点更新成点temp。

5） 计算弹性能量，弯曲能量，图像外部能量，并归一化各点曲率能量。

6） 进行自适应判定是否增加、删除点。

7） 判定收敛条件，如果满足条件结束程序，否则程序转入（3）。

其中，算法步骤（6）的自适应判断准则为：

当2个相邻顶点之间的距离大于某个预定的门限，或当2个相邻顶点的中间点明显不是边缘点或当曲率大于某个预定的门限时，在这2个顶点中间增加1个新的顶点。

当2个相邻顶点的距离小于某个预定的门限时，这样的2个顶点用它们的中间点代替。当3个相邻顶点距离较近且几乎成一条直线时，去除这3个相邻顶点的第1个顶点。

算法步骤（7）采用的收敛的判断准则是：

当总能量不再改变或出现周期性波动或达到设定的迭代次数时，认为算法收敛。在能量最小化过程中的每一次循环中，在每一个顶点的邻域范围内搜索能量极小点来替换原来的顶点。

3.2分割实验

分割实验主要考察初始位置、Snake模型参数对图像分割影响。

考察24位真彩图片“香蕉”的分割：

1） 分割条件：规定参数轮廓线的弹性系数=0.5，抗弯曲的系数=0，Gaussian函数标准方差=3。红色为初始轮廓线，蓝色为分割结果。

2） 在不同初始轮廓曲线条件下Snake模型的分割效果，如图1所示：

图1 香蕉在不同初始轮廓下的分割效果

图1（a）、图（b）对应一组分割对应的分割，红色初始轮廓把“香蕉”图片全部内部，由于有灰色光影的影响，图像未能正确分割；

图1（c）、图（d）对应一组分割对应的分割，红色初始轮廓跨越了“香蕉”图片，图像未能正确分割；

图1（e）、图（f）对应一组分割对应的分割，红色初始轮廓接近“香蕉”图片，图像正确分割。

3） 结论：由上图可见初始位置，不同分割的效果，大相径庭。

第二个实验考察Snake参数对分割性能的影响。

限于篇幅，我们对如图2像进行反复实验，得到较满意的分割效果：

图2 多次实验后满意的结果

图3 多次实验不容易得到满意效果

总结经验，得到以下结论：

1） 一般轮廓线的弹性系数α，刚性系数β被设置为常值，因为β是二阶的平方后的系数，对分割影响较小，实际处理时，令β为零。

2） 对于轮廓线的弹性系数α取值过于偏小时，轮廓线通常被噪声吸引，不能正确分割，轮廓线极不光滑；当弹性系数α取值过于偏大时，轮廓线也过于光滑，不能准确分割目标的凹角与突角。

3） 考察Gaussian函数标准方差σ，当σ 值增大时，有效 Gaussian 势能力的分布范围也相应地扩大，并且 Snake 模型的分割结果受噪声的影响相应地减弱，但是，当σ 的取值过于大时，Snake 模型的最终轮廓线可能会偏离目标边界。一般情况下取值为3～8。

4） 深凹一类的图像，需要设置好初始曲线，如果只简单勾画初始曲线，会导致图像分割失败，曲线不易深入深凹区域。

4 总结

Snake模型能利用图像高层信息，能正确分割图像，但是有一些约束即，1）图像的初始位置离图像的真实边界很近，2）初始曲线不要放在同一介质的图像的内部。

Snake算法有待学者进一步研究与改进。

参考文献：

[1] （美）冈萨雷斯等著. 阮秋琦等译.数字图像处理（第二版）[M].北京：电子工业出版社，2007.

[2] Williams D J，Shah M.A Fast algorithm for active contours and curvature estimation[J].CVGIP： Image Understanding，1992，55（1）：14-26.