6、基于贪婪算法的Snake模型

．．１６２８－－

２０１０年１月中国医学物理学杂志Ｊａｎ．，２０１０笙；！堂墨！塑￡堕望墅！曼壁坠￡望型堕丛竺堂！型！！坚！！堡∑！！：；！：型！：！

基于贪婪算法的Ｓｎａｋｅ模型

李艳诚，李震（滨州医学院，山东烟台２６４００３）

摘要：目的：为改善经典活动轮廓模型的缺陷。方法：本文提出一种新的基于贪婪算法的活动轮廓模型，对其内部能量中加入轮廓平均长度项的控制，外部能量中加入梯度方向势能，并提出区域能量在贪婪算法中的快速求解方法。另外采用动态调整蛇点的算法，使蛇点数目能够自适应地变化。结果：通过与传统的ＧＶＦ算法分割结果比较，本文的分割效果较理想。结论：说明该方法分割准确性高并且对于用户的初始轮廓选择要求不高，具有一定的实用价值。

关键词：活动轮廓模型；贪婪算法；图像分割

中图分类号：Ｒ８ｌ文献标识码：Ａ文章编码：１００５—２０２Ｘ（２０１０）０１—１６２８—０４

ＴｈｅＳｎａｋｅＭｏｄｅｌＢａｓｅｄｏｎｔｈｅＧｒｅｅｄｙＡｌｇｏｒｉｔｈｍ

ＬＩＹａｈ—ｃｈｅｎｇ，ＬＩＺｈｅｎ

（ＢｉｎｚｈｏｕＭｅｄｉｃａｌＣｏｌｌｅｇｅ，ＹａｎｔａｉＳｈａｎｄｏｎｇ２６４００３，Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：Ｏｂｊｅｃｔｉｖｅ：ＦｏｒｉｍｐｒｏｖｉｎｇｔｈｅｉｍｐｅｒｆｅｃｔｉｏｎｏｆｔｈｅＡｃｔｉｖｅｃｏｎｔｏｕｒｍｏｄｅｌ．Ｍｅｔｈｏｄｓ：Ｔｈｉｓｐａｐｅｒｐｕｔｓｆｏｒｗａｒｄａｎｅｗａｃｔｉｖｅｃｏｎｔｏｕｒｍｏｄｅｌｂａｓｅｄｏｎｔｈｅｇｒｅｅｄｙａｌｇｏｒｉｔｈｍ．Ｔｈｅａｖｅｒａｇｅｃｏｎｔｏｕｒｌｅｎｇｔｈｔｅｒｍｉｓａｄｄｅｄｉｎｔｏｔｈｅｉｎｔｅｒｎａｌｅｎｅｒｇｙｏｆｔｈｅｍｏｄｅｌ．Ｔｈｅ

ｇｒａｄｉｅｎｔｄｉｒｅｃｔｉｏｎａｌｅｎｅｒｇｙｉｓ

ｉｎｔｒｏｄｕｃｅｄｔｏｔｈｅｅｘｔｅｒｎａｌｅｎｅｒｇｙｏｆｔｈｅｍｏｄｅｌ．Ａｆａｓｔａｌｇｏｒｉｔｈｍｉｓｉｎｔｒｏｄｕｃｅｄｔｏｓｏｌｖｅｔｈｅｍｉｎｉｍｕｍｏｆｒｅｇｉｏｎｅｎｅｒｇｙ．Ｔｈｅａｌｇｏｒｉｔｈｍｏｆａｄｄｏｒｄｅｌｅｔｅｓｎａｘｅｌａｌｓｏａｄｏｐｔｅｄｉｎｔｈｉｓｐａｐｅｒ．ＳｅｇｍｅｎｔａｔｉｏｎｏｆｔｈｅｌＶｌＲＩｂｒａｉｎｔｕｍｏｒａｒｅｓｔｕｄｉｅｄｉｎｔｈｅｅｘｐｅｒｉｍｅｎｔｓ．Ｒｅｓｕｌｔｓ：ＣｏｍｐａｒｉｎｇｔｏｔｈｅｍａｎｕａｌｓｅｇｍｅｎｔａｔｉｏｎａｎｄｔｈｅＧＶＦｓｅｇｍｅｎｔａｔｉｏｎ．ｔｈｅｍｅｔｈｏｄｉｓｂｅｔｔｅｒ．Ｃｏｎｃｌｕｓｉｏｎ：Ｔｈｅｒｅｓｕｌｔｓｏｆｅｘｐｅｒｉｍｅｎｔｓｉｎｄｉｃａｔｅｔｈａｔｔｈｅｍｏｄｅｌｉｓｎｏｎｅｓｅｎｓｉｔｉｖｅｔｏｉｍｔｉａｌｃｏｎｔｏｕｒ．Ｓｏｔｈｉｓａｌ－ｇｏｄｔｈｍｉｓｐｒａｃｔｉｃａｌ．

Ｋｅｙｗｏｒｄｓ：ａｃｔｉｖｅｃｏｎｔｏｕｒｍｏｄｅｌ；ｔｈｅｇｒｅｅｄｙａｌｇｏｒｉｔｈｍ；ｉｍａｇｅｓｓｅｇｍｅｎｔａｔｉｏｎ

前言

Ｓｎａｋｅ模型是一种有效的图像分割和运动跟踪方法，特别适合于医学图像中复杂组织结构的处理，不过，经典Ｓｎａｋｅ模型有其缺陷，如对初始位置敏感、可能收敛到局部极值甚至发散、不能处理轮廓曲线的拓扑变化等等．因此本文提出一种新的基于贪婪算法的Ｓｎａｋｅ模型。

１内部能量的改进

活动轮廓模型的内部能量起着保持活动轮廓光滑性和拓扑性的作用。传统的内部能量定义为轮廓连续能和轮廓曲率的线性组合，轮廓连续能一般为轮廓

收稿日期：２００９一０８—２４

作者简介：李艳诚。女，讲师，硕士研究生。Ｔｅｌ：１３５５３１００４２３．０５３５—４３８２６５ｌ；Ｅ－ｍａｉｌ：ｌｙｃｈ７９＠１２６．ｃｏｍ。．曲线的一阶导数积分，曲率项一般为轮廓曲线的二阶导数积分，如下式所示：

‰（ｒ（ｓ））＝㈧ｒ．（。）阻＋㈨ｒ－（。）ｌ２ｄｓ（１）在实际应用中，很容易出现相邻控制点汇聚在一起的情况，无法得到物体正确的轮廓，如图１所示。图１（ａ）为初始轮廓，图１（ｂ）为最终迭代的结果，可以看到Ｕ型区域上部凹进去的地方控制出现了汇聚的情况。

为解决控制点收敛的问题，文献【１１在连续能项中加入了轮廓平均长度的控制，轮廓长度计算如下：

拓蟛危：（ｆ：（石Ⅶ）ｚ叫㈩：）ｆ１出）２（２）如控制点的个数为Ｍ，则轮廓平均长度ｃ为：

ｃ＝学（３）

中国医学物理学杂志

一１６２９一第２７卷第１期２０１０年１月

（ａ）初始轮廓

（ａ）Ｉｎｉｔｉａｌｃｏｎｔｏｕｒ

圈１Ｆｉｇ．１Ｉｂｌ最终结果（ｂ）Ｒｅｓｕｌｔｓ

最后．将内部能量计算式修改为：

％（ｒ（川吲－ｆ：Ｉ｜＾）１２－ｃｌ２出

＋（１一位）Ｉ。ｌｒ（ｓ）Ｉｄｓ（４）由式（４）可以看出，在加入了轮廓平均长度的控制后，内部能量中的连续能项在能量最小化时，控制点之间的距离便会趋向于轮廓的平均长度。使用修改后的内部能量，可以避免能量最小化迭代过程中相邻控制点的汇聚。从而能够更加准确的提取物体的轮廓。

２外部能量的改进

外部能量函数的设计决定着模型是否能找到感兴趣物体的真实轮廓。

２．１传统梯度势能

传统的活动轮廓模型外部能量定义为图像的负梯度脚：

《。＝一ＩＶｌ（ｘ，ｙ）Ｉ‘（５）或者图像经过高斯函数滤波后的负梯度：

吒一ｌＶ（Ｇ，（ｘ，ｙ）幸，（戈∥））Ｉ．（６）其中，Ｇ。（石，），）是方差为盯的二维高斯函数，Ｖ为梯度算子。因此，在图像梯度最大的地方活动轮廓模型的外部能量取得最小值。正如文献【目中所指出，传统的梯度势能仅仅采用了梯度的模，而忽视了梯度的方向，因此当感兴趣物体边缘和图像中其它物体距离较近时，活动轮廓可能停留在错误的边缘上。

２．２梯度方向势能

由于传统梯度势能的上述缺陷，文献【４】提出了一种包含梯度方向的势能：

‰＝１?ＶＩ（ｘ．ｙ）（７）式中ｍ为活动轮廓在第ｉ个控制点的单位内法向量，Ｖ，为梯度向量。新的梯度方向势能便是法向量与梯度向量点乘的负数。因此，当图像梯度方向与轮廓内法向量方向相同时式（７）取得最小值。２．３基于区域的外部能量

基于梯度及梯度方向的外部能量形式有两个共同的缺点，一是容易受到噪声的干扰，简单的梯度运算将造成大量的伪边界，从而无法得到准确的轮廓；二是要求初始轮廓十分接近于感兴趣区域的真实轮廓，如果初始轮廓离真实轮廓较远，梯度势能便无法将活动轮廓吸引到真实的边缘上。

基于图像统计特征的区域能量受噪声干扰较小，其原理为假设图像中包含两个主要区域，分别是感兴趣物体和背景区域．两部分区域像素有着不同的概率分布。当然两区域的假设也很容易推广到多个不同分布区域的情况。文献１４］假设物体和背景为均值和方差都不相同的高斯分布，根据似然函数设计区域能量为：

瓯咖一。ｌｏｇＰｎ（ｍ））一（ｃ．１０９Ｐ，，（ｍ）））（８）

。

ＪＥＲ

＼ｌ—Ｒｆ其中ｃ为Ｂ＋（，（ｓ））在整个图像上的求和：

Ｃ－∑ｌｏｇＰＲ?（ｍ））（９）

ｆ舭

由于Ｃ与轮廓的位置尢关，１５１此司以从就萤幽数

中去掉，则将式（８）改写为：

瓯广，酗（群错）㈣，

９

ｌ∈月１月、‘、ｏ，，』

两部分区域的概率密度函数分别为：驰㈥）＝石１万唧（警）（１１）删州＝丽１唧（警）（１２）

将式（１１）和式（１２）代入式（１０）中，整理得到区域能量的详细表诀式为．

瓯两＝∑

’

ＪＥＲ

（虿１－２一寺），㈠一２（嚣一等２卜，

＋薏一等Ｈ唱（嚣）（１３）

计算区域能量需要对活动轮廓所包括的整个区域进行求和运算，在活动轮廓模型能量极小化过程中，需要不断计算模型的区域能量，这是一个相当费时的过程。使用由Ｗｉｌｌｉａｍｓ提出的贪婪算法［５１来迭代求解活动轮廓模型的能量极小值，并在贪婪算法中计算区域能量的快速方法。

３贪婪算法

贪婪算法的主要思想是只考虑单个活动轮廓控制点在其邻域内的能量变化，而不考虑轮廓上其它控

．．１６３０—－

中国医学物理学杂志第２７卷第ｌ期２０１０年１月制点所带来的影响。每次迭代中根据能量最小化原则

顺序调整每个控制点的位置，直到控制点的位置不再

发生变化。

在本文所采用的贪婪算法中，活动轮廓模型的能

量函数定义如下：

避。帆＋（１１８峨咖（１４）

其中内部能量的离散形式为：

１２．２

％铂№一州‘一ｃｌ《ｌ一∞１０１—２ｒｆ乜ｔ（１５）

外部能量按照式（７）与式（１３）计算，每次迭代之前，都需要根据轮廓的位置来更新两部分区域的均值和方差。采用式（１３）计算区域能量时，需要对活动轮廓所包围的整个区域进行求和计算，也就是对整个区域计算面积分，并且在寻找当前控制点在其邻域中的最小能量时．对于邻域中的每个像素都需要进行同样的计算，这将耗费大量的时间。

３．１区域能量的快速算法

观察在某一控制点的邻域内能量最小点时，相邻两备选点的区域能量求和范围，如图２（ａ）所示。从图２（ａ）中可以看出，在计算相邻两备选点Ａ和Ｂ的区域能量时存在重复计算的区域，因此省略重复部分将大大提高计算的速度。

实际计算中，为得到准确轮廓，一般要求相邻两控制点的间距小于某个较小的常数（在我们的试验中设定控制点间距在８－－一１６个像素之间）。因此可以采用相邻三个控制点所围成的三角形区域来计算一点的区域积分，从而避免复杂的判断和求交运算。如图２（ｂ）所示，当Ｂ点和相邻两控制点所围成的三角区域ＢＣＦ是整个ＲＯＩ区域中“凸出来”的部分时，三角形ＢＣＦ上的区域积分对整个Ｉ的Ｉ区域积分的贡献是“正”的．即

ＥＲｏｌ２ＥｃＢ味＋ＥＢｃＦＱｑ相反。当三角形区域ＢＣＦ是ＲＯＩ区域中“凹下去”的部分时，如图２（Ｃ）所示，ＢＣＦ上的区域积分对整个ＲＯＩ的区域积分的贡献是“负”的。即

ＥＲｏＩ＝ＥｃＤ盯一Ｅ８ｃＦ０１７）有了上面的判断，便可以根据当前控制点与相邻两控制点围成的三角形区域的面积分相对大小来求解区域能量的局部极小值，从而有效的减少了区域能量的计算量。

３．２模型的动态收缩与生长

加入区域能量后的活动轮廓模型其初始轮廓可以远离ＲＯＩ的真实边界，因此在贪婪算法的迭代过程中，轮廓可能发生较大的形变，需要动态的删除和添加控制点来保证轮廓的准确性。每次迭代完成之后，一次计算每两个控制点之间的距离，如果其大于某个

∞∞∞，

圈２区域面积分的快速算法讨论（ａ）计算

区域面积分时的重复部分（ｂＪ三角区域ＲＯＩ

中凸出的部分（ｃ）三角区域为ＲＯＩ中凹陷的部分

ＦｉｇｓＦａｓｔａｌ酗ｒｉｔｈｍｆｏｒｔｈｅｒｅｇｉｏｎａｌａｒａ．ａｓｕｂ

预先设定好的值，则在这两点连线的中点增加一个控制点。如果小于某个值，则删除第一个控制点。这样使蛇点始终能够很好的描述目标形状，保证了稳定跟踪。

利用贪婪算法求解ｓｎａｋｅ模型能量极小值的具体算法流程如图３所示。

４实验结果与分析

图４（ａ）为从一序列图像中任选的１幅脑部ＭＲＩ原图，目的是将脑ＭＲＪ图中的肿瘤区域精确分割出来。如图中箭头所示，肿瘤左下边和呈现强边缘特性

圈３贪婪算法流程圈

Ｈ９３Ｇｒｅｅｄｙａｌｇｏｄｔｈｍ

中国医学物理学杂志第２７卷第１期２０１０年１月

．．１６３１一

（ａ）原圈（ａＪＯｒｉｇｉｎａｌ

【ｂ）初始轮廓１

（ｂ）Ｉｎｉｔｉａｌｃｏｎｔｏｕｒ１

冒４

（ａ）Ｇ、，Ｆ分割结果

（ａ）ＳｅｇｍｅｎｔａｔｉｏｎｒｅｓｕｌｔｓｏｆｔｈｅＧＶＦ

圈５

的其他组织相邻，肿瘤右上边呈现弱边缘特性，导致该区域与周围介质有相互渗透现象，边界信息不明显。给原图两个不同的初始轮廓，分别采用ＧＶＦ的方法和本文的改进算法进行肿瘤区域的提取。

比较图５（ａ）和５（ｂ）的分割结果可以看出，ＧＶＦ的方法虽然可以收敛到图像的边缘，但是该模型易收敛于其他组织的边界或特征接近的其他组织纹理，边缘明显发生偏离；而本文算法在不同初始轮廓下均能得到较为理想的分割效果，具有较好的准确性和稳定性，故本算法对于用户的初始轮廓选择要求不高，对临床诊断和治疗具有一定的指导作用。

（ｃ）初始轮廓２

（ｃ）Ｉｎｉｔｉａｌｃｏｎｔｏｕｒ２

（ｂ）本文算法分割结果

（ｂ）Ｓｅｇｍｅｎｔａｔｉｏｎｒｅｓｕｌｔｓｏｆｔｈｅａｌｇｏｒｉｔｈｍ

参考文献：

【ｌ】ＭＪａｃｏｂ’Ｔ．Ｂｌｕ，Ｍ．Ｕｎｓｅｒ．ＥｆｆｉｃｉｅｎｔａｎｄＡｌｇｏｒｉｔｈｍｓｆｏｒＰａｒａｍｅｔｒｉｃＳｎａｋｅｓ阴．ＩＥＥＥＴｒａｍ．Ｉｍａｇｅ，Ｐｒｏｃ，２００４，１３（９）：１２３１－１２４４．

【２】Ｍ．Ｋａｓｓ，Ａ．Ｗｉｔｌｄｎ，Ｄ．Ｔｅ＝ｏｐｏｕｌａｓ．Ｓｎａｋｅｓ：ＡｃｔｉｖＣｏｎｔｏｕｒｏｄｄｓ田．Ｉｍ’１Ｊ．Ｃｏｍｐ．Ｖｉｓ．１９８７，１（４）：３２１—３３１．

【３】Ｈ．Ｐａｒｋ，Ｔ．Ｓｃｈｏｅｐｆｌｉｎ，Ｙ，Ｋｉｍ．ＡｃｔｉｖｅｃｏｎｔｏｕｒｍｏｄｅｌｗｉｔｈＧｒａｄｉｅｎｔＤｉｒｅｃｔｉｏｎａｌＩｎｆｏｒｍａｔｉｏｎ：ＤｉｒｅｃｔｉｏｎａｌＳｎａｋｅ田．ＩＥＥＥＴｒａｍ．Ｃｉｒｃｕｉｔｓｓｙｓｔ．ＶｉｄｅｏＴｅｃｈ０１．２００１，１１：２５２－２５６．

【３】Ｖ．Ｃｈａｌａｍ，Ｗ．ＣｏｓｔａｓＹ．Ｋｉｍ，ＩｎｔｅｇｒａｔｉｎｇＲｅｇｉｏｎＧｒｏｗｉｎｇａｎｄＥｄｇｅＤｅ—ｔｅｃｔｉｏｎＵｓｉｎｇＲｅｇｕｌａｆｉｚａｔｉｏｎ【Ｃ】．ＩｎＰｒｏｃｅｄｄｉｎｇｓｏｆｔｈｅＳＰＩＥＣｏｄｅｒ－ｅｎｃｅｏｌｌＭｄｅｄｉｃａｌＩｍａｇｉｎｇ．ＳＰＩＥ。１９９５．

【４】Ｃ，Ｃｈｅｓｎａｕｄ，Ｐ．Ｒｅｆｒｅｇｉｅｒ，Ｖ．Ｂｏｕｌｅｔ．ＳｔａｔｉｓｔｉｃａｌＲｅｇｉｏｎＳｎａｋｅ－ＢａｓｅｄＳｅｇ－ｍｅｎｔａｔｉｏｎＡｓａｐｔｅｒｔｏＤｉｆｆｅｒｅｎｔＰｈｙｓｉｃａｌＮｏｉｓｅＭｏｄｅｌｓ［Ｊ］．ＩＥＥＥＴｒａｍ．ＰａｔｔｅｒｎＡｎａｌ．ＭｃａｈｉｎｅＩｎｔｅｌｌ．１９９９．２１（Ｉ１１：１１４５－１１５７．

【５１ＤＪ．Ｗｉｍａｌ璐，Ｍ，Ｓｈａｈ，ＡＦａｓｔＡｌｇｏｒｉｔｈｍｆｏｒＡｃｔｉｖｅＣｏｎｔｏｕｒｓａｎｄＣｕｒｖａ－ｔｕｒｅ

Ｅｓｔｉｍａｔｉｏｎ册．ＣＶＧＩＰ：Ｉｍａｇ．Ｕｎｄｅｒ，１９９２，５５（１）：１４－２６．

基于贪婪算法的Snake模型

作者：李艳诚， 李震， LI Yan-cheng， LI Zhen

作者单位：滨州医学院,山东,烟台,264003

刊名：

中国医学物理学杂志

英文刊名：CHINESE JOURNAL OF MEDICAL PHYSICS

年，卷(期)：2010,27(1)

参考文献(6条)

1.D J Williams;M Shah;A Fast Algorithm for Active Contours and Curvature Estimation 1992(01)

2.C Chesnaud;P Refregier;V Boulet Statistical Region Snake-Based Segmentation Asapter to Different Physical Noise Models[外文期刊] 1999(11)

3.V Chalana;W Costa;Y Kim Integrating Region Growing and Edge Detection Using Regularization 1995

4.H Park;T Schoepflin;Y Kim Active contour model with Gradient Directional Information:Directional Snake 2001

5.M Kass;A Wikin;D Terzopoulas Snakes:ActivContour odels[外文期刊] 1987(04)

6.M Jacob;T Blu;M Unser Efficient and Algorithms for Parametric Snakes[外文期刊] 2004(09)

本文链接：https://www.wendangku.net/doc/6c18800328.html,/Periodical_zgyxwlxzz201001015.aspx