一种全局最优的非匀质图像分割算法
收稿日期:2010 04 09
基金项目:国家自然科学基金资助项目(60672128)
作者简介:刘建磊(1981-),男,西安电子科技大学博士研究生,E m ai:l ji an l e ili u @m ai.l x i d i https://www.sodocs.net/doc/1c12812094.html, .cn .
do:i 10.3969/.j issn .1001 2400.2011.02.012
一种全局最优的非匀质图像分割算法
刘建磊1,2
,冯大政
2
(1.西安电子科技大学计算机学院,陕西西安 710071;
2.西安电子科技大学雷达信号处理国家重点实验室,陕西西安 710071)
摘要:为了解决传统几何活动轮廓模型不能自适应地分割非匀质图像的问题,提出了一种全局优化的非匀质图像分割算法.首先,利用图像经过高斯滤波器滤波后的梯度信息定义了一个新的图像分割能量函数.然后,利用水平集方法扩展该能量函数的定义域,以使该能量函数具有全局最优解.为避免水平集函数的重新初始化过程,在能量函数中引入了一个水平集函数约束项.最后,通过最小化该能量函数,建立水平集函数演化的偏微分方程.对水平集演化方程数值求解,实现对非匀质图像的分割.实验结果表明,该算法不但能自适应地确定曲线演化方向,而且能有效地分割非匀质图像.关键词:图像分割;几何活动轮廓模型;全局梯度;水平集
中图分类号:TP391 文献标识码:A 文章编号:1001 2400(2011)02 0066 06
Non ho m ogenous i m age seg m entati on w ith global opti m ization
LIU J ianlei 1,2
,FENG Dazheng
2
(1.Schoo l o f Computer Sc i ence and T echno l ogy ,X i d ian U n i v .,X i an 710071,China ;2.N ati ona l Lab .o f R adar S i gnal Processing ,X i dian U niv .,X i an 710071,Ch i na)
A bstrac t : In orde r to so l ve the prob l em tha t the trad iti ona l g eom etr i c active contour mode l can not adapti ve l y
segm en t a non hom og enous i m age ,a g l oba l opti m iza ti on non hom og enous i m age segmentation a l gor ith m i s proposed .F irstl y ,a ne w energy functi on i s defi ned by i m porti ng grad i ent i nfo r ma ti on on the inho m ogeneous i m age wh i ch is filtered by t he G auss i an filter .T hen ,t he dom ai n o f the ene rgy f unction is ex tended by t he l eve l set m ethod .T hus ,t he energy functi on has t he so l ution of g l obal opti m ization .W e i ntroduce a lev el set f uncti on contro l ter m f o r avo i ding t he re i nitializati on procedure of t he l eve l set functi on .F i na ll y,a partial difference equation o f the leve l set f unc tion evolve m ent i s derived by m i n i m i zing the energy f unc tion .T he non hom og enous i m age segmentation is i m ple m ented by the num erical so l uti on o f the parti a l d ifference equation .Exper i m enta l resu lts s how tha t the proposed a l gor ith m not on l y can auto m aticall y deter m i ne t he evo l vem ent o rien tati on of the ac ti ve con t our cure ,but a l so can e ffecti ve l y seg m ent non homogenous i m ages .K ey W ords :
i m age segm entati on ;geo m etric acti ve contou r mode;l g l oba l grad i ent ;l eve l set
近年来,基于水平集方法
[1 2]
的几何活动轮廓模型被广泛地应用于图像分割领域,并得到了较好的实验
结果,因此该模型受到国内外学者的广泛关注[3 4]
.基于边界的几何活动轮廓模型
[5 7]
和基于区域的几何活
动轮廓模型[8 9]
是其中两类典型的模型.基于边界的几何活动轮廓模型利用局部梯度信息控制着活动轮廓曲
线的演化速度和方向,其中较有代表性的是文献[7]提出的水平集接力模型.该模型能有效地分割非匀质图像(非匀质图像就是含有多个灰度级目标的图像),其缺点是不具有全局最优性,活动轮廓曲线不能自适应地调整演化方向.基于区域的几何活动轮廓模型利用全局灰度信息,使活动轮廓曲线停止在目标边界处.其
中的经典方法是由Chan 等[8]
提出的C V 模型.该模型具有全局最优性,能自适应地调整曲线演化方向,并能有效分割匀质图像,但不能有效分割非匀质图像.针对以上两种模型的优缺点,笔者在分析非匀质图像梯
2011年4月第38卷 第2期
西安电子科技大学学报(自然科学版)JOURNAL OF X I D I AN UN IVERS ITY
Apr .2011
Vo.l 38 N o .2
度特征的基础上,提出了一种具有全局最优的非匀质图像分割算法.
1 全局最优的非匀质图像分割模型
1 1 图像分割能量函数的定义
假设给定图像u 0是近似分段常数函数,并包含有N -1个目标,其灰度值分别为u 1,u 2, ,u N -1,背景的灰度值为u N .假设C 0是所有目标边界的并集.因为u 0是近似的分段常数函数,所以包含在图像中的这些具有不同灰度级的目标都具有相同的梯度特征:目标边界处的像素点的梯度值不为零,目标区域内的像素点的梯度值都等于零(如图1所示).根据以上分析,提出了用于图像分割的能量函数为
E (C )
=
I (C)
u 0(x,y )-c 1
2
d x d y +
O (C )
u 0(x,y )-c 2
2
d x d y ,
u 0(x ,y )= G (x ,y )*u 0(x,y ) ,
(1)
图1 多灰度级图像与它的梯度图像
其中,I (C )和O (C )分别代表演化曲线C 的内部和外部区域;c 1是C 的内部区域像素点梯度值取绝对值后的平均梯度值;c 2是C 的外部区域像素点梯度值取绝对值后的平均梯度值;G (x ,y )是尺度参数为 的高斯函数; G (x,y )*u 0(x,y )是高斯函数与图像卷积后的梯度,图像与高斯函数卷积的目的是平滑图像中的噪声.当曲线C =C 0时,C 内外部所有像素点的梯度值都等于零,式(1)也达到了最小值零.因此通过最小化式(1)所示的能量函数就可以实现非
匀质图像的分割.
在式(1)的基础上,再加上曲线C 的长度项L (C )构成如下能量函数:
F (c 1,c 2,C )= L (C )+ 1
I (C)
u 0(x,y )-c 1
2
d x d y + 2
O (C )
u 0(x,y )-c 2
2
d x d y ,
u 0(x,y )=
G (x,y )*u 0(x,y ) ,
(2)
其中, 0, 1>0, 2>0为固定常数.图像分割问题转化为求解式(2)的最小值问题.当式(2)达到最小值时,就可以得到分割图像.1 2 能量函数定义域的扩展
为了使式(2)具有全局最优性,需要把它的定义域扩展到图像的定义域 .用水平集函数 (x,y )表示该能量函数,其中零水平集代表曲线C, (x,y )满足关系式:
C ={(x,y ) : (x,y )=0
} ,
I (C )={(x,y ) : (x,y )>0} ,O (C )={(x ,y ) : (x ,y )<0} .
(3)
分别定义H eav iside 函数H (z )和D irac 函数 (z)为
H (z )=1 ,z 0 ,
0 ,z <0 ; (z )=
d d z H (z ) .(4)
利用式(3)和式(4)定义的函数,式(2)可以写为
F (c 1,c 2, )=
( (x,y )) (x,y )d x d y + 1
u 0(x,y )-c 12
H ( (x ,y ))d x d y +
2
u 0
(x,y )
-c 2
2
(1-H ( (x,y )))d x d y ,
u 0(x ,y )= G (x ,y )*u 0(x,y ) .
(5)
从式(5)和式(2)的对比中可以看出,用水平集函数表示的能量函数的定义域扩展到了图像的全局数据 .这样就可以利用全局梯度信息驱使零水平集向着目标边界处演化.全局梯度信息的使用,一方面保证了全局优化性能,使文中算法能自适应地确定活动曲线的演化方向;另一方面使得文中算法仅利用一条活动轮廓曲
67
第2期 刘建磊等:一种全局最优的非匀质图像分割算法
线就能正确分割含有多灰度级目标的非匀质图像.
在演化水平集函数 (x,y )的过程中,为了保证最终分割结果的稳定性,每次更新水平集函数后,都要将其重新初始化为符号距离函数.这个过程不仅计算量大而且容易使零水平集定位不准确.为了提高文中算法的实时性和分割结果的稳定性,在能量函数中引入了可以避免水平集函数重新初始化的水平集函数约束项
[7]
:
P ( )=
1
2
( -1)2
d x d y .
引入水平集函数约束项后的能量函数可写为如下形式:
F (c 1,c 2, )=
( (x ,y )) (x ,y )d x d y + 1
u 0
(x,y )-c 1
2
H ( (x,y ))d x d y +
2
u 0
(x ,y )
-c 2
2
(1-H ( (x ,y )))d x d y +
12( (x,y )
-1)2
d x d y , u 0(x,y )= G (x,y )*u 0(x,y ) .
(6)
1 3 能量函数的最小化
由于式(6)中含有3个变量c 1、c 2和 ,因此最小化该能量函数要分两步进行.首先保持水平集函数 (x,y )的值不变,最小化式(6)得到c 1和c 2的值.
c 1( )=
u 0(x,y )H ( (x,y ))d x d y
H ( (x,y ))d x d y ,
c 2( )=
u 0(x,y )(1-H ( (x,y )))d x d y
(1-H ( (x ,y )))d x d
y
.(7)
然后固定c 1和c 2的值,利用梯度下降流法计算式(6)关于水平集函数 (x,y )的欧拉 拉格朗日方程:
t =[ ( )-1]d iv
+d i v ( )+ ( )[ 2( u 0(x,y )-c 2)2
- 1( u 0
(x ,y )-c 1)2
] .(8)
2 数值计算方法
在式(6)中含有H eav iside 函数,所以只有当水平集函数 (x ,y )的符号发生改变时才能改变能量函数的值.这样就容易出现能量函数收敛到极小值的情况.为了稳定地得到全局最优解,可用规则化非紧支的H eav isi d e 函数H (z )=
1+(2 )arctan (z )
2和规则化的D irac 函数 (z)=1
( (1+z 2
))分别代
替H (z )和 (z).由于H (z )是单调递增函数,因此自变量在定义域上任意一点的变化都会改变函数H (z )的值,从而会引起式(6)的改变.替换后的欧拉 拉格朗日方程为
t =[ ( )-1]d iv
+d iv ( )+ ( )[ 2( u 0(x,y )-c 2)2
- 1( u 0(x,y )-c 1)2
] .
(9)
边界条件为:在区域边界 上满足( ( ) )( n)=0
, n 是 在边界的法线导数;在区域内, (0,x,y )= (x,y ).
采用有限差分法实现式(9)的数值求解.设h 为空间步长;(x i ,y j )=(ih,jh),1 i ,j M,为格点坐标; t 为时间步长; n
i ,j = (n t ,x i ,y j )是 (t ,x ,y )的近似,这里有n 0, 0
= 0,并设
x
- i ,j = i ,j - i-1,j , x
+ i ,j = i+1,j - i,j , y
- i ,j = i ,j - i ,j -1 , y
+ i ,j = i ,j+1- i,j , x 0 i,j =( i+1,j - i-1,j )
2 , y
0 i,j =( i ,j+1- i,j-1)
2 .
这样式(9)可以写为
68
西安电子科技大学学报(自然科学版) 第38卷
n+1i ,j - n
i,j
t
=[ ( n
i,j )-1]1h 2 x
- x + n+1
i ,j
( x
+ n
i ,j )
2
h 2
+( y
0 n
i,j )
2
h
2
1/2
+
y
- y
+
n+1
i ,j ( x 0 n
i ,j )
2
h 2
+( y
+ n
i,j )
2h
2
1/2
+
1
h
2 x -( x
+ n +1
i,j )+ y
-( y
+ n+1
i,j )
+
( n i,j )
2( u 0(x ,y )-c 2( n
))2
- 1( u 0
(x,y )-c 1( n
))2
.
文中算法主要是通过迭代方法驱使水平集函数进化的,其主要步骤如下:
(1)初始水平集函数为符号距离函数;(2)利用式(7)计算c 1和c 2的值;
(3)求解式(9)所示的偏微分方程,得到 n+1
;
(4)判断水平集函数值是否稳定,如果已达到稳定状态停止迭代,抽出水平集函数中的零水平集完成图像分割;否则令n =n +1,重复(2)~(4)的过程.
从式(7)和式(9)可以分别看出,c 1和c 2的值定义在整幅图像的定义域内,具有全局特征;偏微分方程所涉及的图像梯度函数 u 0(x,y )的定义域也是全图数据.因此,文中算法可以实现全局优化.另外,用规则化非紧支的H eav isi d e 函数和规则化的D irac 函数分别代替H eav iside 函数和D irac 函数,防止了能量函数收敛到极小值情况的出现.所以文中算法具有全局最优性.
3 实验结果与分析
实验环境为CPU 3 0GH z ,内存为1GB ,程序开发环境为M atlab7.1.文中算法的实验参数的取值: = 1= 2=1
,时间步长 t =0 5,活动曲线被初始化为符号距离函数时,位于曲线内部像素点的符号取正值,外部的取负值.图像尺寸都为128 128(像素).
图2 非匀质嵌套图像分割结果
图2给出了文中算法、文献[7]的算法和文献[8]的算法对非匀质嵌套图像的分割结果对比.图2(a)分别为初始活动轮廓曲线在不同位置的原始图像;图2(b)为文中算法对应的分割结果;图2(c)为文献[7]的
69
第2期 刘建磊等:一种全局最优的非匀质图像分割算法
算法对应的分割结果;图2(d)为文献[8]的算法对应的分割结果.从分割结果可以看出,无论初始活动轮廓曲线在任何位置,文中算法都能得到满意的分割结果.文献[7]算法的分割结果对活动轮廓曲线初始位置比较敏感.只有活动轮廓曲线包含所有目标时,才能得到满意的分割结果.文献[8]的算法虽然对活动轮廓曲线的初始位置不敏感,但都只检测到最外面的两层边缘,漏检了最内层的边缘
.
图3 非匀质自然图像分割结果对比
图3给出了文中算法、文献[7]的算法和文献[8]的算法对非匀质自然图像的分割结果对比.为了使文献[7]的算法能得到最优的分割结果,在实验中把初始轮廓曲线置于能包含所有目标的位置.从分割结果可以看出,对文中算法和文献[7]的算法都比文献[8]的算法具有更好的分割结果.对于边缘都比较明显的非匀质自然图像(图3(a)中的前两幅图像),文中算法和文献[7]的算法的分割性能差别不大,都能得到满意的分割结果.对于含有弱边缘的非匀质自然图像(图3(a)中的第3幅图像),文中算法比文献[7]的算法具有更优的分割性能.
为了精确客观评价文中算法的分割性能,采用正确率、平均绝对距离[10]
(M ean Absolute D istance ,MAD )和计算时间这3个评价准则分别对文中算法、文献[7]的算法和文献[8]的算法进行量化评价.在实验中初始活动轮廓曲线完全包围所有目标,这样可以降低初始条件对文献[7]算法分割结果的影响.设P 为分割得到的目标轮廓线,H 为正确的目标轮廓线,正确率和P 与H 的平均绝对距离分别定义如下:正确率p 等于P 和H 重合的像素个数/
H 所含有的像素个数;平均绝对距离
e(P,
H )=
1
2
1n
n
i=1
d (p i ,H )+
1
m
m
i=1
d (h i ,P ),其中P ={p 1,p 2, ,p n },是分割得到的目标轮廓线上点的坐标,
H ={h 1,h 2, ,h m }是正确的目标轮廓线上点的坐标,d (p i ,H )表示点p i 到轮廓线H 上最近邻点的距离:d (p i ,H )=m in j h j -p i .
表1给出了文中算法、文献[7]的算法和文献[8]的算法分别对20幅非匀质合成图像进行分割的评价结果.表1中的数据是分割性能评价结果的平均值.
从上述实验结果可以看出,文中算法同时具有如下两个优点:(1)具有全局最优性,能根据图像信息自
70
西安电子科技大学学报(自然科学版) 第38卷
适应地调整活动轮廓曲线的演化方向.(2)能有效分割非匀质图像.另外,文中算法的计算效率高于文献[7 8]的算法.这主要是因为,文献[7]的算法中基于局部梯度信息的停止速度函数的函数值等于1,这一条件在图像中很难满足,从而降低了该算法的分割速度;文献[8]的算法需要不断地重新初始化水平集函数为符号距离函数,这一过程降低了该算法的运算效率.而文中算法并没有利用梯度信息去定义停止速度函数,而是利用全局梯度信息驱使水平集函数的进化,这使得文中算法与文献[7]的算法相比具有较快的分割速度.另外,文中算法的水平集函数约束项避免了水平集函数的重新初始化过程,提高了算法的实时性.
表1 3种分割算法的评价结果
算法图像类型平均绝对距离/像素
计算时间/s 正确率/%文献[8]的算法非匀质合成图像3 68110 6968 34文献[7]的算法非匀质合成图像1 04511 5290 82文中算法
非匀质合成图像
0 562
9 47
98 84
4 结束语
根据非匀质图像所具有的梯度特征,提出了一种全局最优的非匀质图像分割算法.利用全局梯度信息驱使隐含在水平集函数中的活动轮廓曲线向目标边界演化,并最终使活动轮廓曲线停止在目标边界处,从而完成图像分割.实验结果表明,文中算法不但能自适应地调整活动轮廓曲线的演化方向,而且对非匀质图像的分割具有更好的鲁棒性.参考文献:
[1]M oha m ed B S ,Am arM,Is m a il B A.E ffec tive L eve l Set I m age Seg m entation w ith a K erne l Induced D ata T er m [J].I EEE T rans on I m age P rocess i ng ,2010,19(1):220 231.
[2]O li v ier B ,D en is F,Ph ilippe T,e t a.l V ar i a tiona l B Spli ne L ev el Se t :a L i near F ilter i ng Approach fo r Fast D efor m ab le M ode l Evo l uti on[J].
I EEE T rans on I m age P rocessing ,2009,18(6):1179 1191.
[3]X i e X H.A ctive Contouring Based on G rad i entV ector Interacti on and Constra i ned L evel Set D iffusi on[J].IEEE T rans on I m ag e P rocessi ng ,2010,19(1):154 164.
[4]
汪凯斌,俞卞章,王琦,等.无需反复初始化的活动围道纹理分割方法[J].西安电子科技大学学报,2008,35(3):542 545.W ang K a i bin ,Yu B i anz hang ,W ang Q ,i eta.l T ex t ure I m age Seg m entati on U s i ng the w ithout R e i n iti a lization G eodesic A cti v e Contour M ode l[J].Journa l o f X i dian U niversity ,2008,35(3):542 545.[5]M allad iR,Se t h i an J ,V emur i B .Shape M ode ling w i th F ront P ropaga tion :a L eve l Set A pproach [J].
IEEE T rans on P attern
Ana l ys i s andM achine Inte lli gence ,1995,17(2):158 175.
[6]Casell es V,Catte F ,Coll T et a.l A G eom etr i c M ode l for A cti ve Contours i n I m age P rocessi ng [J].N u m erische M athe m ati k ,1993,66(1):1 31.
[7]
王斌,高新波.基于水平集接力的图像自动分割方法[J].软件学报,2009,20(5):1185 1193.
W ang B i n ,G ao X i nbo .A utom ati c I mage Segmentation M ethod U si ng Sequentia lL eve l Set[J].Journal of Soft w are ,2009,20(5):1185 1193.[8]Chan T F,V ese L A.A ctive Contours w it hout Edges[J].I EEE T rans on I m age P rocessing ,2001,10(2):266 277.
[9]
L ankton S ,T annenbau m A.Lo ca li zing R eg ion Based A cti ve Contours [J].I EEE T rans on I m age P rocessi ng ,2008,17(11):2029 2039.
[10]M i k i c I ,K ruc i nski S ,T hom as J D.Seg m entation and T rack i ng in E chocard i ographic Sequences :A ctive Con t ours Gu i ded by
Op tica l F l ow E sti m ates[J].IEEE T rans on M ed ica l I m ag i ng ,1998,17(2):274 284.
(编辑:齐淑娟)
71
第2期 刘建磊等:一种全局最优的非匀质图像分割算法