在数学领域中已经有多种比较成熟的最大流/最小割算法[9],成为图割方法的应用基础。
式(2)中第一项P( )=Ω(|Ñ |-1)2dxdy为惩罚项,用来保持水
平集函数为符号距离函数。后两项为外部能量项,在能量最小化过程中用以驱动轮廓线向目标边界运动。其中δ为Dirac方
1程,H为Heaviside方程。停止函数被定义为g=1+|ÑGσ*I|是基于边缘梯度信息的。
2.2GCBAC算法
Boykov等人首次将图割理论引入计算机视觉领域时[10],
提出了一种基于能量最小化进行目标分割的交互式方法。NingXu等人[6]依此为基础提出了GCBAC算法:给定一条初始轮廓线,以该线为轴膨胀得到一个环状窄带区域(FixedContourNeighborhood,FCN)。然后运用节点同一化(nodeidentification)算法将窄带的内外边界线分别化为网络的源点和汇点。最后运用图割得到位于该窄带内的使能量函数最小的新轮廓线。不断重复该过程,轮廓线将逐步逼近目标边界。
由于将计算的像素缩小到一个“窄带”内,所以其时间复杂度降低到Ο(n1.2)内,其中n为窄带内像素个数。并且易知,如果窄带宽度设置较宽,可减少迭代次数,但每次图割时间变长。如果窄带宽度设置较窄,每次图割时间减少,但迭代次数将增大。
1.3演化/时间比
不同的水平集模型在数值实现上都是一个迭代过程。随
着迭代的进行,轮廓线逐步趋向于目标边界。显然,随着迭代次数的增加,一方面,轮廓线更加接近目标边界。另一方面,也不断重复着大量的计算。尤其当轮廓线越靠近目标边界时,每一次迭代(演化)仅使轮廓线做很小的移动,但耗用了相同的迭代时间。
设DSi表示第i(i=123)次演化后轮廓线内部面积的变化值。ti表示第i次演化所用时间。因为随着迭代的进行,
DSi
轮廓线越来越靠近目标边界而趋于稳定,故有:lim=0。i®¥i图1中实验验证了这一点。
在图1(a)中,蓝色线是演化200次时轮廓线位置,红色线是演化300次时轮廓线位置。容易看出从第200次到300次进行了100次演化,但轮廓线移动已经很小。图(b)记录了每次迭代后相对于上一次迭代轮廓线内部面积的变化(两次迭代间像素数的变化)。从中也可以看出从第200次迭代开始,轮廓线的变化已经小于1.272。图(c)记录了每次迭代所用时间,可以看出300次迭代中每次迭代所用时间基本相同。
3本文方法
通过以上分析,水平集方法的优点是能适应曲线的拓扑
变化以及凹形目标。但其计算量大和需要多次迭代的缺点阻碍了它的应用。GCBAC算法由于将计算范围缩小到窄带内,所以计算效率高。但它不能深入到目标凹陷部分,并且如果窄带过宽,将得不到正确的分割结果。因此,本文将图割算法引入到水平集迭代中,有效提高了水平集的分割效率。
3.1算法设计
本文算法的思想是:首先在目标内部和外部分别输入两
2图割理论2.1原理
图割(GraphCuts)是以图论为理论基础,作为一种全局最优方法,近年来在计算机视觉领域得到了广泛应用。图割方法解决计算机视觉问题的一般框架是:
(1)根据能量最小化模型构造能量函数,从而将视觉问题转化为能量函数最小化问题。
(2)根据图像构造网络,使能量与网络的割相对应,从而将能量最小化问题转化为网络最小割问题。
(3)根据最大流/最小割定理,将网络最小割问题转化为最大流问题。
(4)通过求解最大流问题,求得图的最小割,从而获得视觉问题的解。
80面积变化率(/像素差/迭代

)706050403020100
50
100
条初始轮廓线Li和Lo,设定阈值α。对Li和Lo分别建立水平集函数 i和 o,分别进行演化,Li向外膨胀,Lo向内收缩。在演化过程中对能量大的水平集增加驱动力,使两条轮廓线相互靠拢。当轮廓线的变化小于α时,说明Li和Lo都已经靠近在目标边界,此时结束水平集演化,得到演化曲线L′i和L′o。然后运用节点同一化算法[6]将L′i和L′o化为网络的源点
和汇点,运用一次GCBAC图割算法,得到最终分割曲线L。
算法流程为:
步骤1初始化轮廓线Li和Lo,以及阈值α。
步骤2建立相应的水平集函数 i和 o,对Li和Lo进行演化。
步骤3如果Li和Lo的变化不小于阈值α,则重复步骤2。否则,转至步骤4。
0.0200.0180.016时间/s0.0140.0120.0100.008
150200
迭代次数
250300
0.006
050100
150200迭代次数
250300
(a)曲线演化200、300


次位置
图1
(b)曲线所围面积的变化
水平集演化中曲线的变化与所用时间的关系图
(c)迭代时间
Cmueniergadplain 计算机工程 与应用 optEgnei Apitsrnnco 一 种结合图割与双水平集的图像分割方法 杨建功, 汪西莉 YANGingngⅥ,G l Jao.ANXii 陕西师范大学 计算机...
融合形状先验的向量CV模型图像分割算法_王万玉_杨建功_汪西莉_数学_自然科学_...一种结合图割与双水平集的图像分割方法[J].计算机工程与应用.2012,48 (3)...
融合形状先验的向量CV模型图像分割算法_王万玉_杨建功_汪西莉_数学_自然科学_...一种结合图割与双水平集的图像分割方法[J].计算机工程与应用.2012,48 (3)...
热门文档