一种改进的活动轮廓线最优化算法.doc

一种改进的活动轮廓线最优化算法
摘要：kass活动轮廓曲线传统最优化算法的数字实现中涉及到时间步长的选取。时间步长选取较短，避免了曲线收敛过程中的震荡问题，但增加了收敛时间；时间步长选取较长，又导致震荡问题的产生。文章提出一种变时间步长的方法，使时间步长在优化的过程中从大到小变化，较好地解决了固定时间步长收敛时间和震荡的问题，实验结果表明了该方法的有效性。
关键词：活动轮廓线；最优化算法；时间步长
活动轮廓模型是一种有效的图像分割、目标跟踪方法，这种方法已成功地用于物体识别、计算机视觉、计算机图形和生物医学图像处理领域。基于活动轮廓的图像分割实质上就是用活动轮廓逼近物体的边缘，此过程可以通过曲线的能量最小化来实现，外部能量使活动轮廓向物体边缘运动、内部能量保持活动轮廓的光滑性和拓扑性，当能量最小时，活动轮廓收敛到所要检测的物体边缘。由于这种方法同时考虑了几何约束和与图像数据、轮廓形状有关的能量最小等约束条件，所以能得到令人满意的分割效果。
对于传统的参数活动轮廓模型的能量最小化算法，即活动轮廓线最优化算法，kass等人通过离散化的欧拉方程不断迭代得到收敛解。对于迭代过程的时间步长如果选取过大，将会导致方程在迭代求解的过程出现震荡现象，严重的可能导致曲线越过理想收敛点而收敛于其他的区域；如果时间步长选取过小，虽然解决了曲线的震荡问题，但将会导致收敛的时间变长。
针对时间步长选取碰到的问题，本文提出一种变时间步长的方法。在曲线演化的过程中，根据曲线的运动方向变化，动态地调整时间步长，较好地解决了曲线收敛时间和震荡的问题。
一、活动轮廓
活动轮廓本质上是一能量最小化的样条曲线v(s)=(x(s),y(s))，在内部能量（内力）和外部能量（外力）作用下变形，外部能量使活动轮廓向着物体边缘运动，而内部能量保持活动轮廓的光滑性和拓扑性，当能量达到最小时，活动轮廓收敛到所要检测的物体边缘。模型的能量定义为：
e=eint+eext①
其中eint是由于模型拉伸、弯曲而产生的内能，提供平滑性约束，通常定义为：
eint＝）ds②
eint的第一项是弹性势能，反抗轮廓曲线的拉伸，第二项是弯曲势能，抵制轮廓模型的弯曲变形。α表示曲线的弹性系数，β表示曲线的硬度（或刚性）系数。
eext是与图像特征有关的外部能量，以便活动轮廓被吸引到图像某些特征点处，如边缘，通常eext取：
eext＝p(v)ds （p(v)=-｜｜▽i(v)｜｜2）③
③式中，i是图像的灰度。
由②、③可知，e的最小对应于灰度梯度最大，此时的活动轮廓就是物体边缘。
能量函数取得极小值的必要条件是满足欧拉-拉格朗日方程：
-（αv′）″+（βv″）″+▽p(v)＝0④
二、能量最小化的数字实现
假定f（v）=(f1(v)，f2(v))=-p(v)+…为图像力和其他外力的合力，则上述公式为
-（αv′）′+（βv″）″＝f（v） ⑤
将公式变为空间步长（步长为h）的后向有限差分：
（αi(vi-vi-1)-ai+1(vi+1-vi)）+（vi-2-2vi-1+vi）-2（vi-1-2vi+vi+1）+（vi+2-2vi+1+vi）-（f1（vi），f2（vi））=0⑥
其中，vi=v(ih)，αi=α，βi=β。
上式可以写成矩阵形式：
av=f⑦
其中，a是一个五对角循环矩阵，v和f第i个分量分别代表点vi和vi的力f(vi)。
为了能找到方程的解，引入时间因素，将方程变换为另一种形式：
γivi=aαi+bβi=fi⑧
其中，vi(t)=[xi(t)，yi(t)]，αi(t)为弹性力（αi(t)=2xi(t)-xi-1(t)-xi+1(t)），βi(t)为弯曲力（βi(t)=2αi(t)-αi-1(t)-αi+1(t)），fi(t)为外力，vi(t)为曲线在节点i的速度，γi为阻尼系数。
经过整理：
xi(t+δt)=xi(t)-（aαi(t)+bβi(t)-fi(t)）⑨
迭代公式⑨式可以很方便地通过编程实现。但实现的过程，涉及到对时间步长δt的选取，如果想加快曲线的收敛，则需要适当加大δt的值，但如果将δt选取过大，将会使曲线在单步迭代的过程中出现跨度过大而越过平衡点的情况，严重的导致曲线收敛于伪平衡点。上述震荡过程的示意图如图1所示，由于δt选取较大，导致曲线收敛于伪平衡点。为了克服上述问题，我们提出一种改进的活动轮廓线实现算法，能兼顾曲线迭代求解过程中收敛速度和震荡的问题。
三、改进的活动轮廓线实现方法
针对第二部分在活动轮廓线实现过程中碰到的问题，我们的改进实现方法如下：
第一步是给定曲线的初始位置v(0)。
第二步是选取较大的时间步长δt，利用迭代式进行计算，求得第n步的迭代结果v(nδt)。
第三步是判断曲线是否收敛到给定的阈值，如是，则停止；否，则转入第四步。
第四步是计算第n+1步曲线的运动方向，如果曲线的运动方向反向，则将曲线回退到第n-1步，并且将时间步长δt变为δt/2，重新计算第n步的迭代结果v(nδt)。然后转入第三步。
经过不断地跟踪曲线在运动过程中的方向，我们可以动态改变时间步长δt，将使曲线由于时间步长过长而越过平衡点时，回到上一步改用较小的步长重新前进，并最终收敛到平衡点。经过这种方式，将使收敛的时间大为减少。
四、实验结果
如何快速将能量最小化，是衡量活动曲线性能的重要指标。我们通过2个例子分别比较活动曲线的传统解法和改进后解法的分割速度。
图2为一粒石子的图像，使用传统的能量最小化（即固定时间步长）算法，迭代到6161次时，收敛到最优解。当采用变时间步长求解时，迭代需要进行的次数为1523次。节约大约4倍的时间。
图3为一幅噪声严重的块状图形，使用传统算法和改进算法的迭代次数分别为4300和943次。
五、结论
基于分析传统活动曲线的数值实现过程，提出了一种改进的变时间步长的实现算法，该算法能根据曲线的运动方向动态地调整时间步长，能使曲线在最初的运动过程取较大的时间步长，减少曲线的收敛时间。理论分析和实验结果表明，该实现算法能明显提高活动曲线的收敛速度。
参考文献：
1.刘涛.活动轮廓模型研究及其在目标跟踪中的应用[d].山东大学,2006.
2.周昌雄.基于活动轮廓模型的图像分割方法研究[d].南京航空航天大学,2005.
3.timmcinerney,demetriterzopoulos.t-snakes:topologyadaptivesnakes[j].medicalimageanalysis,2000(4).