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

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