一种保持拓扑结构的隐式活动轮廓图像分割方法

Vol.47　No.5

Sep　2009

一种保持拓扑结构的隐式活动轮廓

图像分割方法

柴振华,罗宏文,苗　闯,马驷良

1

1

2

1

(1.吉林大学数学研究所,长春130012;2.吉林大学电子科学与工程学院,长春130012)

摘要:提出一种保持拓扑结构的图像分割方法,通过应用一个拓扑结构的边缘检测函数替代经典的边缘检测函数,抑制了活动轮廓的拓扑结构变化.活动轮廓模型采用基于水平集

方法的隐式结构,数值离散采用加性算子(AOS)格式.结果表明,所提出的方法能有效地保持轮廓的拓扑结构,并且具有较高的计算效率.

关键词:图像分割;水平集;测地线活动轮廓;保持拓扑结构;拓扑结构;加性算子中图分类号:TP391.41　　文献标识码:A　　文章编号:16712(2009)0520981206

ATopologyPreservingSegmentationMethodfor

ImplicitActiveContourModels

CHAIZhen2hua,LUOHong2wen,MIAOChuang,MASi2liang

(1.InstituteofMathematics,JilinUniversity,Changchun130012,China;

1

1

2

1

2.CollegeofElectronicScienceandEngineering,JilinUniversity,Changchun130012,China)

Abstract:Anoveltopologypreservingsegmentationmodelwasproposed.Theproposedmodelpreventsactivecontourmodelsfromgeometricalortopologicalchangesbyusingatopologicalconstraintedgedetectorinsteadoftheclassicaledgedetector.Theimplicitschemebasedonlevelsetmethodisappliedandanadditiveoperatorsplitting(AOS)schemeisadopted.

Theresultshowsthattheproposedmethodcaneffectively

maintainthetopologyofthecontoursandcostlessadditionalcomputingtime.

Keywords:imagesegmentation;levelset;geodesicactivecontour;topologypreservation;topologicalconstraint;additiveoperatorsplitting(AOS)

图像分割就是将图像细分为构成它的子区域或对象.图像分割算法一般是基于图像亮度值梯度的

间断性以及亮度值的区域相似性而构造的.本文提出的保持拓扑结构的图像分割方法适用于基于图像梯度的隐式活动轮廓模型.活动轮廓模型

[1]

的本质是一个能量泛函的极小化模型,其中能量泛函包括

内部能量和外部能量,分别控制曲线的光滑程度以及曲线和物体边界的接近程度.此模型是非本质的,即其能量泛函依赖于曲线的参数化,而曲线的参数化并不影响曲线(物体边界)的几何形状.但由于曲线参数的正则性,因此,该模型在演化过程中不会改变曲线的拓扑结构.

隐式活动轮廓模型

[223]

求解过程中采用水平集方法

[426]

,克服了参数活动轮廓的参数依赖性,并且

使轮廓具有拓扑结构适应性,其中几何活动轮廓模型

收稿日期:2009201222.

[2]

基于主曲率驱动模型和曲线演化理论,测地线

作者简介:柴振华(1985～),男,汉族,硕士研究生,从事微分方程数值计算的研究,E2mail:chaizhenhua@gmail.com.通讯作者:罗宏文(1968～),男,汉族,博士研究生,讲师,从事计算机图形图像处理及模式识别的研究,E2mail:luohw@jlu.edu.cn.

基金项目:吉林大学“985工程”项目基金.

982　　

[3]

吉林大学学报(理学版)　　　第47卷　

活动轮廓模型以活动轮廓模型为基础,并引入测地线,将模型转化为本质的形式.隐式活动轮廓模

型的拓扑结构适应性虽然可以同时检测图像中的多个物体,但分割结果的拓扑结构具有不确定性.在某些应用领域并不需要活动轮廓具有拓扑结构适应性,而需要严格的保持轮廓的拓扑结构.例如,大脑皮层具有球形的拓扑结构,利用医学图像处理大脑皮层重构时,在重构的过程中,必须保持这一拓扑结构性质.

文献[729]提出了隐式活动轮廓模型的保持拓扑结构方法,通过引入简单点(SimplePoint)的概念,抑制非简单点处水平集函数的符号改变,以达到控制曲线拓扑结构的目的.文献[10211]以及本文提出的保持拓扑结构方法都是从几何观察出发,并在活动轮廓基础上加入由几何观察导出的拓扑结构泛函.

1　模型描述

2

令I:Ω→R为一给定图像的亮度函数,Ω得曲线C为物体的边界.Caselles等人

J(C)=

[3]

提出一种求如下泛函最小值的方式来确定曲线C:

(q)dq=C′

C

0

g(C(q))

∫

1

g(x)ds,∫

(1.1)

其中

g(x)=

11+󰃝I(x)

2

.(1.2)

理想情况下,在物体的边界上󰃝I→∞,g→0.因此,g越小表明曲线越接近于物体的真实边界,当

g充分小时,曲线将定位到物体的边界.

计算式(1.1)的Euler2Lagrange方程并利用最速下降法,可得到如下参数曲线演化方程:

5C)N,=(κg-〈󰃝g,N〉

5t

其中N为曲线的单位外法向量,κ为曲线C的曲率.

用水平集函数<:Ω→R隐式的表示曲线C,即

C={x;<(x)=0}.

(1.3)

利用水平集方法将式(1.3)转化为隐式水平集演化方程,并加入气球力项,得

5<=󰃝󰃝<󰃝<

+μ󰃝(1.4)

加入气球力的作用是加速收敛,适应拓扑结构的变化.当气球力系数μ>0时,加速曲线收缩;当μ<0时,气球力使曲线膨胀,将曲线从物体的内部拉至外部边界.虽然当气球力消失,即气球力系数μ=0时,会保持拓扑结构,但收敛速度会变得异常缓慢.

方程(1.4)的求解由于采用了水平集方法,迭代过程中需要保持水平集函数<为零水平集

C={x;<(x)=0}的近似符号距离函数,即

dist(x,C),x在曲线C的外部,x在曲线C上,x在曲线C的内部.

(1.5)

<(x)≈

0,

-dist(x,C),

　　与文献[10211]的方法类似,本文提出的方法也是基于几何观察.以下设闭曲线C的水平集函数<为符号距离函数,定义集合

3

C={x∈Ω;存在两点x1,x2∈C,x1≠x2,使得dist(x,x1)=dist(x,x2)=dist(x,C)}.易见集合C非空.由曲线C的连续性可知,集合C是Ω5<(x0)5<(x0)15<(x1)5<(x2)15<(x1)5<(x2)3

=,　=,　x0∈C.++5x25y25x5x5y5y

3

3

3

3

2

　第5期　　　　　　柴振华,等:一种保持拓扑结构的隐式活动轮廓图像分割方法　　　983

图1　当曲线的拓扑结构将要改变时曲线的几何特征

Fig.1　Geometricalcharacteristicsofcurvesduringthechangeofthetopologyofthecontour

3

　　对于x0∈C,至少存在两点x1,x2,使得

dist(x0,x1)=dist(x0,x2)=dist(x0,C).

假设点x0与曲线C充分接近,则点x1,x2也充分接近.当曲线将要合并、或将要具有公共点时,即曲线的拓扑结构将发生变化时,

〈󰃝<(x1),󰃝<(x2)〉∆-1,

这等价于

1(󰃝<(x1)+󰃝<(x2))∆0,󰃝<(x0)=23

即󰃝<(x0)∆0.而对于任意的xC,有

󰃝<(x)=1.因此,可以用󰃝<的值控制曲线C拓扑结构的变化.

基于以上讨论,本文提出以下保持拓扑结构的水平集演化模型:

5<󰃝<+μG(x),

=󰃝G(x)=Ts,r(x)g(x),

Ts,r(x)=min{H(󰃝<(y)

y-x-s)},

(1.7)

H是一维Heaviside函数,r,μ,s为参数,s∈(0,1)用于分离将要发生拓扑结构变化的点和普通点.当

(1.6)

󰃝<(y)≥s时,y为普通点,

H(󰃝<(y)

-s)=1.-s)=0,

当󰃝<(y)H(󰃝<(y)

对于在y的邻域y-xTs,r(x)=0,　　G(x)=0,

模型将在此邻域内停止演化.

由于在曲线的演化过程中只有曲线邻近的点会影响曲线的演化,因而不必在全局加入保持拓扑结构的,而只需在每次迭代曲线的一个窄带范围内保持曲线的拓扑结构.因此,可将T(x)替换为具

(x),从而可得如下保持拓扑结构水平集的演化模型:有窄带形式的T′

5<󰃝<+μG′(x),(1.8)=󰃝(x)=T′G′s,r,l(x)g(x),

(1.9)Ts,′=1-max{H(s-󰃝<(y))}・H(<(x)+l)H(l-<(x)),r,l(x)

y-xl为窄带的宽度,参数s,r的意义同式(1.6).

984　　吉林大学学报(理学版)　　　第47卷　

此方法不仅适用于测地线活动轮廓模型,同时也适用于几何活动轮廓模型,相应的演化方程为

5<󰃝<+μ(1.10)=G(x)󰃝对于方程(1.6)和(1.8)的离散,采用AOS加性算子格式.该数值格式为半隐格式,克

服了显格式对时间步长的,在没有气球力的情况下是无条件稳定的,且可以实现并行计算,并且该格式的计算复杂度和存储需求都是线性的.

3

对于到曲线两端距离相等的点xij∈C,有

5<(xij)15<(x1)5<(x2)1-+

(δ=≈=δ󰁡x5x225x5x5<(xij)15<(x1)5<(x2)1-+

(δ=≈=δ󰁡y5y225y5y

+-+-其中δ󰁡󰁡向后和中心差分算子.因而无需特别处理,在全x,δx,δx,δy,δy,δy分别为x和y方向的向前、局用中心差分近似󰃝<即可.

对于函数Ts,r,Ts,′r,l的离散,可先对max和min内的函数进行离散,再对离散矩阵使用最大或最小滤波器进行一次滤波即可得到离散的Ts,r,Ts,′r,l.为简化,用向量的形式(通过将相应矩阵的行或列串联而成)表示图像和离散的函数,<∈R,其中M,N分别为行数和列数.

按照文献[13]的AOS加性算子格式,可得相应的离散问题:

-1

τ1n+1n2n

(<+τμ(2.1)<=G󰃝±n

其中G=gTs,r,Ts,r可对相应的离散函数用最小滤波器滤波得到.Al(<)中的元素ap,q,l定义如下:Nl(p)表示p点在l方向上的相邻元素,

2n

q∈Nl(p),󰃝󰃝<󰃝<+

M×N

[12214]

G

p

G

n

q

ap,q,l(<)=n

-󰃝<

np

r∈Nl(p)

∑

2󰃝+

p

󰃝n,

q=p,

(2.2)

r

0,其他.

易见,矩阵I-

τ2h

2

Al(u),l∈{x,y}为严格三对角占优矩阵,相应的迭代问题可以采用具有线性复杂度

n

的Thamas算法.

由于气球力项的双曲特性,因此对其中的梯度可采用迎风格式:

-n

=M,μ≤0,󰃝󰃝󰃝0.其中,

M=N=

(2.3)

min(Dx-n

-n22

+max(Dx+

n

+n2

+min(Dy-n

-n22

+max(Dy+

n

+n2

22

　　求解过程中采用了水平集方法,为了保证迭代的稳定,需要周期性的将水平集函数<重新初始化

[526]

为符号距离函数.

3　实验结果

下面利用本文提出的方法对一些人工图像进行分割,并与测地线活动轮廓模型(没有保持拓扑结

　第5期　　　　　　柴振华,等:一种保持拓扑结构的隐式活动轮廓图像分割方法　　　985

构)进行了比较.

图2和图3是对同一幅人工图像的分割结果.图2是本文中方法的分割结果,图3是测地线活动轮廓模型的分割结果,其中参数h=1,τ=0.5,μ=0.4,r=1,s=0.5,图像大小为100×100,CPU时间对比列于表1.

图2　应用本文提出的保持拓扑结构方法对一个包含两个物体的人工图像的分割过程　

Fig.2　Segmentationofsyntheticimagewithtwodisksviaproposedtopologypreservingmethod

图3　应用传统的测地线活动轮廓模型(无保持拓扑结构的)对一个包含两个物体的人工图像的分割过程

Fig.3　Segmentationofthesyntheticimagewithtwodisksviaclassicgeodesicactivecontour

(withouttopologicalconstraint)

表1　本文提出的保持拓扑结构方法与传统的测地线活动轮廓模型所用的CPU时间/s

Table1　ComparisonoftheproposedmethodandclassicgeodesicactivecontourinCPUtimes/s

迭代次数本文提出的方法传统的测地线活动轮廓模型

503.562.9638

1006.93235.8679

15010.45708.6668

20014.148811.4714

25017.482514.2870

　　比较图2和图3可见,利用本文提出的方法在分割过程中曲线并没有为两个的圆,而是被强制的保持与初始轮廓一致的拓扑结构,而测地线活动轮廓模型并没有这一特性.由表1可见,加入本文提出的保持拓扑结构方法,并没有过多的消耗CPU时间.图4是另一个强制保持拓扑结构的例子,原始图像为一个环,图像大小为100×100.初始轮廓为环中的一个圆,其中参数h=1,τ=0.5,μ=-0.5,r=2,s=0.5.由图4可见,由于保持拓扑结构的特性,环的轮廓没有成为两个的圆而是一条连续的封闭曲线.

图4　应用本文提出的保持拓扑结构方法对一个环形图像的分割过程　

Fig.4　Segmentationofatorusviaproposedtopologypreservingmethod

综上可见,本文提出的保持拓扑结构方法保持了原有活动轮廓的优点,与其他的保持拓扑结构方

法相比,本文提出的方法没有引入新的泛函,而是直接改进模型中的边缘检测函数,用一个拓扑结构的边缘检测函数替代经典的边缘检测函数控制拓扑结构的变化.其演化模型与测地线活动轮

[7,9,11]

986　　吉林大学学报(理学版)　　　第47卷　

廓模型一致,拓扑结构控制的边缘检测函数形式简单,便于计算.模型的离散采用AOS加性算子格式,计算效率有很大提高.本文提出的方法与传统的测地线活动轮廓相比,有效地保持了轮廓的拓扑结构,执行时消耗的时间相差不大,并没有过多的消耗CPU时间,计算效率较高.

参考

[1]　KassM,WitkinA,TerzopoulosD.

3212331.

[2]　CasellesV.GeometricModelsforActiveContours[J].ICIP,1995,3:9212.

[3]　CasellesV,KimmelR,SapiroG.GeodesicActiveContours[J].ICCV,1997,22(1):61279.[4]　OsherS,SethianJA.

FrontsPropagatingwithCurvature2dependentSpeed:AlgorithmsBasedonHamilton2Jacobi

Formulations[J].JournalofComputationalPhysics,1988,79:12249.

[5]　SethianJA.LevelSetMethodsandFastMarchingMethods:EvolvingInterfacesinComputationalGeometry,Fluid

Mechanics,ComputerVision,andMaterialsScience[M].Cambrise:CambridgeUniversityPress,1998.

[6]　OsherSJ,FedkiwRP.LevelSetMethodsandDynamicImplicitSurfaces[M].Berlin:Springer,2002.

[7]　HANXiao,XUChen2yang,Braga2NetoU,etal.TopologyCorrectioninBrainCortexSegmentationUsingaMultiscale,

Graph2basedAlgorithm[J].IEEETransactionsonMedicalImaging,2002,21(2):1092121.

[8]　Braga2NetoU,HANXiao,XUChen2yang,etal.ATopologyPreservingGeometricDeformableModelandItsApplica2

tioninBrainCorticalSurfaceReconstructioninGeometricLevelSetMethodsinImaging,Vision,andGraphics[M].Berlin:Springer2Verlag,2003.

[9]　HANXiao,XUChen2yang,PrinceJL.ATopologyPreservingLevelSetMethodforGeometricDeformableModels[J].

IEEETransactionsonPatternAnalysisandMachineIntelligence,2003,25(6):7552768.

[10]　AlexandrovO,SantosaF.ATopology2preservingLevelSetMethodforShapeOptimization[J].JComputPhys,2005,

204(1):1212130.

[11]　LeGuyaderC,VeseLA.Self2repellingSnakesforTopology2preservingSegmentationModels[J].IEEETransactionson

ImageProcessing,2008,17(5):7672779.

[12]　WeickertJ,RomenyBMTH,ViergeverMA.EfficientandReliableSchemesforNonlinearDiffusionFiltering[J].

IEEETransImageProc,1998,7(3):3982410.

[13]　WeickertJ,HarrRomenyB.FastMethodsforImplicitActiveContourModels[C]//GeometricLevelSetMethodsin

Imaging,Vision,andGraphics.NewYork:Springer,2003:43257.

[14]　LUOHong2wen,MASi2liang,MIAOLi2gang.AnImplicitAlgorithmforImageSegmentationBasedonGeodesicActive

Contours[J].JournalofJilinUniversity:ScienceEdition,2007,45(5):8192821.(罗宏文,马驷良,苗利刚.一种

文献

IntJComputerVision,1988,1(4):

Snakes:ActiveContourModels[J].

基于测地线模型图像分割的隐式算法[J].吉林大学学报:理学版,2007,45(5):8192821.)