基于纹理与灰度协同进化的图像分割算法

󰀁

2009年1月

文章编号:1001-9081(2009)01-00-03

计算机应用

JournalofComputerApplications

󰀁

Vo.l29No.1Jan.2009

基于纹理与灰度协同进化的图像分割算法

袁宝峰,吴乐华,曾󰀁伟

(重庆通信学院信号与信息处理实验室,重庆400035)

(yuanbaofeng330@sina.com)

摘󰀁要:为了获得更好的分割效果,成功地将局部二值模式(LBP)纹理模型和灰度特征纳入到合作型协同进化算法(Co󰀁CEA)框架中,并实现了图像分割。该方法首先分别对LBP纹理模型和灰度特征进行编码,然后运用Co󰀁CEA

进行进化操作,最后通过本文提出的联合适应度函数确定分割区域。实验结果表明该方法在分割质量上效果明显,并有效地降低了时间复杂度。

关键词:局部二值模式(LBP);合作型协同进化算法(Co󰀁CEA);联合适应度函数

中图分类号:TP391.4󰀁󰀁文献标志码:A

Imagesegmentationalgorithmbasedon

coevolutionwithtextureandgrayscale

YUANBao󰀁feng,WULe󰀁hua,ZENGWei

(SignalandInformationProcessingLaboratory,ChongqingCommunicationInstitute,Chongqing400035,China)

Abstract:Toobtainbettersegmentationeffect,LocalBinaryPatterns(LBP)andgray󰀁scalecharacteristicswerebroughtintotheframeworkofCooperativeCoevolutionaryAlgorithm(Co󰀁CEA)successfullyinthispaper.LBPandgray󰀁scale

characteristicswerefirstlyencoded,andthenevolutionoperationwascarriedoutusingCo󰀁CEA,Finally,thedivisionofregionwasfixedbytheunitedfitnessfunction.Resultshowsthatthismethodhasverygoodeffectinimprovingthequalityofsegmentationandloweringthetimecomplexity.

Keywords:LocalBinaryPatterns(LBP);CooperativeCoevolutionaryAlgorithm(Co󰀁CEA);unitedfitnessfunction

0󰀁引言

图像分割是图像处理中的一项重要任务,分割质量的好坏直接影响后续工作的开展。大量研究人员对该问题提出了许多解决方法,其中具有代表性的是文献[1]的阐述。尽管如此,到目前为止还没有一种通用的方法,也没有一个判断分割是否成功的客观标准,因此图像分割被认为是计算机视觉中的一个瓶颈问题[2]。

基于纹理的分割算法已被广泛运用于医学图像分析、工业检测、文档分割、图像检索等方面。纹理分割关键在于提取图像的特征,文献[3]比较了8种纹理特征,并指出联合几种方法中最优的纹理特征可以提高纹理分类总体性能。文献[4-5]提出的局部二值模式(LocalBinaryPattern,LBP)具有灰度不变性和旋转不变性,且计算复杂度低,在工业可视化检测,图像检索,人脸识别方面都得到了广泛的应用。

󰀁融合纹理与灰度信息,结合其他分类方法将提高图像的分割质量。文献[6]提出了一种基于神经网络的纹理和灰度信息融合方法,取得了较好的分割效果。受该方法的启发,本文将LBP纹理模型和图像灰度特征相融合,运用合作型协同进化算法[7](CooperativeCoevolutionaryAlgorithm,Co󰀁CEA)进行进化操作,最终得到分割区域。实验结果表明本文提出的分割方法在保证分割效果的同时,也有效地降低了时间复杂度。

1󰀁基于LBP纹理模型的图像分割

在基于纹理的图像分割方法中,寻找一种能够准确表示图像纹理特征的纹理模型是该方法的首要任务。LBP纹理模型是近年来纹理模型研究的一个热点。1.1󰀁LBP纹理模型

与常用的纹理模型一样,LBP也是一种点样本估计方法,点的纹理通过该点与其周围的点进行某种运算得到。文献[4-5]定义为T=t(gc,g0,󰀂,gP-1),其中gc代表待处理的点。g0,󰀂,gP-1为gc周围区域中采样点的灰度值,如果坐标不是整数位置的采样点,可以通过双线性插值得到。具体定义为:

T=t(gc,g0,󰀂,gP-1)

T=t(s(g0-gc),󰀂,s(gP-1-gc))其中:s(x)=

1,󰀁x 01,󰀁x<0

(1)

LBP中的计算区域可由半径R和等间隔采样点数P来确定,此时就可以得到LBPP,R纹理模型:

P-1

LBPP,R=

!

s(gi-gc)2i

(2)

i=0

由式(2)可知,不同的P和R将对应不同的局部二值模式。如果P增大,将对应高分辨率的LBP纹理,同时LBP的计算复杂度会快速增加。综合有效性和可行性,本文采用LBP8,1纹理模型表示图像,如图1所示。

󰀁󰀁收稿日期:2008-07-08;修回日期:2008-09-14。󰀁󰀁基金项目:重庆市自然科学基金资助项目(CSTC2007BB2105)。

󰀁󰀁作者简介:袁宝峰(1985-),男,重庆人,助教,硕士研究生,主要研究方向:模式识别、图像处理;󰀁吴乐华(1965-),女,浙江诸暨人,教授,主要研究方向:模式识别、图像通信;󰀁曾伟(1984-),男,湖南岳阳人,硕士研究生,主要研究方向:图像处理与识别。第1期袁宝峰等:基于纹理与灰度协同进化的图像分割算法󰀁󰀁󰀁55󰀁

式(2)定义的LBP纹理模型只具有灰度不变性,为了使其具有旋转不变性,文献[5]对其进行改进,得到同时具有灰度不变性和旋转不变性的LBP8,1∀纹理模型:

LBP8,1∀=其中:

U(LBP8,1∀)=

s(g7-gc)-s(g0-gc)+

P=17P=07

法找到二者的最佳结合点,达到了很好的分割效果。本文同样将融合纹理与灰度信息,运用Co󰀁CEA找到二者的最佳结合点。

2.1󰀁合作型协同进化算法(Co󰀁CEA)

!

s(gP-gc)2P,󰀁U(LBP8,1∀)#其他

2

(3)

Co󰀁CEA是一种改进型进化算法。它在一定程度上克服了传统进化算法中的不足,而且能对所求问题进行合理划分,有效跳出局部最优点,因此被广泛运用于函数优化[9]、车间调度[10]等实际问题。

Co󰀁CEA的基本思想是:将待求问题分解成多个子部分并分别编码,形成多个子群,各子种群进化。问题的完整解集由每个子种群的代表个体组成,一个子种群中的个体,要通过和其他子种群中个体相互作用来获取适应值。2.2󰀁联合适应度函数的确立

根据本文算法的特点,本算法的联合适应度函数由两部分组成:一是灰度适应度函数,二是纹理适应度函数。根据Ostu法的原理,在灰度直方图和LBP纹理直方图中都可以找

ll

到一个点,使图像在使用各自分割方法后的类间方差fitH,fitW

9,

!

s(gP-gc)-s(gP-1-gc)

(4)

按照式(3)所定义的LBP8,1纹理模型,其中有9种出现频率最高的模式,对应为模式0~8,其他模式统称为异常模式9。由于异常模式没有固定的图像特征,所以一般只分析模式0~8。结合图像,设待运算点左上方的点为序号0点,按顺时针依次编号。

图2表示了LBP8,1∀的9种常用模式0~8,实心点表示该点的值为1,空心点表示该点的值为0。

达到最大,则此时联合适应度函数也最大。

最终的联合适应度函数为:

ll

fitl=a∃fitH+b∃fitW

(5)

ll

其中:fitH是灰度适应度函数,fitW是纹理适应度函数,l表示进

化的次数。a,b分别是各自的贡献系数,在本文算法中,a=0.5,b=0.5。2.3󰀁本文算法的提出

本文提出的算法是在融合灰度和纹理信息的基础上,运用Co󰀁CEA得到二者的最佳结合点,从而实现图像分割。算法的具体步骤如下:

第1步󰀁待分割的图像为f(x,y),(x,y)为图像中的像素坐标;f(x,y)的灰度直方图为h(i),i为图像的灰度级;利用LBP纹理模型将f(x,y)纹理化得到纹理图像fLBP(x,y)。

第2步󰀁对灰度阈值和LBP纹理阈值分别进行编码,得到Hlj,Wlj,由于灰度值和LBP值都是在0~255,所以Hlj,Wlj都是8位二进制编码;然后把子编码合成为混合编码矩阵A=[Hlj,Wlj],其中l为进化次数,j为子群的个体(在本算法中j=1,󰀂,8)。

第3步󰀁对第2步中得到混合编码矩阵进行进化操作,

1.2󰀁LBP纹理模型用于图像分割

与基于灰度阈值的图像分割类似,一幅图像在经LBP纹理模型处理后,各个像素点所表示的就是该点的LBP值,于是就可以用LBP直方图来表示该图像中LBP值的分布。由于一幅图像的纹理区域的LBP值具有很强的相似性,非纹理区域LBP值与其有很大的差异,所以LBP直方图也会呈现双峰特性。借鉴Ostu法,选取合适的分割LBP门限,就会很好地分割出图像中的纹理区域和非纹理区域分割开。

[8]

操作算子包括复制算子、交换算子、变异算子。复制采用文献[11]提出的轮盘方式选择复制对象,复制概率pr=0.2,交换概率pc=0.5,突变概率pm=0.08。

第4步󰀁根据联合适应度函数,计算第3步中得到新编码的适应度fit(l,j),j=1,󰀂,8。并找出fit(l,j)max,如果l>100或者|fit(l,j)mean-fit(l,j)max|<󰀁,(fit(l,j)mean为第l代中所有个体的平均联合适应度,󰀁为一个容错系数,在本算法中,󰀁=10)则停止进化,把各自得到分割图像相互叠加即得到最后的分割图像,如果不满足结束条件,则返回第3步。

2󰀁基于纹理与灰度协同进化的图像分割

基于灰度阈值的分割方法的优势在于分割图像的背景和前景;而基于纹理模型则更擅长于分割出图像的纹理区域。但是如果一幅图像既有纹理区域,又要求很好地表现背景和前景,此时两者的结合将是解决该问题的一个很好的方法。在文献[6]中,作者融合纹理与灰度信息,运用神经网络的方3󰀁实验结果󰀁

本文仿真实验平台为Matlab7.0.1,计算机的配置为Pentium4CPU2.40GHZ,内存为512MB。

本文给出了两幅既有背景和前景又具有一定纹理特征的图像(Woman图和Baboo图)的分割结果,分割效果分别如󰀁56󰀁󰀁󰀁

图3和图4所示。

计算机应用

运行时间上来看,本算法的时间复杂度也较低。

第29卷

从图3可以明显看出,基于灰度阈值的分割方法能把Woman的脸部轮廓分割开,基于纹理的分割方法可以将Woman的头发和衣服的纹理特征表现出来,那么二者的结合就可以综合以上两种优势。图4(b)将Baboo面部分割得比较清楚,但是Baboo的毛发纹理却表现得不是很明显,图4(c)弥补了这一缺点,但是又失去了面部轮廓,而图4(d)既突出了轮廓又表现了纹理。

表1是对两幅实验图像进化结果的数据分析:Woman图在进化中一直未满足停止进化的条件,所以达到最大进化次数100次,其中复制27次,交换62次,变异2次。因为三种遗传算子都是随机的,所以三者之和小于或等于100。Baboo图在进化中满足了停止条件,故进化次数为67次。此外,从

表1󰀁本文算法的进化结果分析表

图像名称WomanBaboo

进化次数10067

复制次数

2716

交换次数

6237

变异次数

21

总时间/s0.6880.500

平均时间/s0.00680.0075

󰀁󰀁图5是两幅实验图像在进化过程中的方差变化图,图中三条曲线分别是联合平均方差、纹理平均方差、灰度平均方差的变化趋势。三条曲线在进化过程中不断地震荡,但最终还是达到一个较优的值,这也反映了进化算法的特点。

寻找一种更好的纹理模型也是算法的改进方向。参考文献:

[1]󰀁PALNR,PALSK.Areviewonimagesegmentationtechniques

[J].PatternRecognition,1993,26(9):1277-1294.

[2]󰀁BHANUB,LEES,MINGJ.Adaptiveimagesegmentationusinga

geneticalgorithm[J].

IEEETransactiononSystem,Man,andCy󰀁

bernetics,1995,5(12):13-1565.

[3]󰀁SIGNHM,SINGHS.Spatialtextureanalysis:acomparativestudy

[C]//16thInternationalConferenceonPatternRecognition.[S.l]:IEEEPress.,2002,1:676-679.

[4]󰀁OJALAT,PIETIKAIANENM.Unsupervisedtexturesegmentation

usingfeaturedistribution[J].(1999):477-486

[5]󰀁OJALAT,PIETIKAIANENM,MAENPAAT.Multiresolution

grayscaleandrotationinvarianttextureclassificationwithlocalbinarypatterns[J].IEEETransactiononPatternAnalysisandMachineIn󰀁telligence,2002,24(7):971-987.

[6]󰀁刘宁宁,田捷,胡志刚,等.基于神经网络的纹理和灰度信息融合

方法[J].软件学报,1999,6(5):575-579.

[7]󰀁POTTERMA,deJONGKA.Cooperativecoevelution:anarchitec󰀁

tureforevolvingcoadaptedsubcomponents[J].EvlutionaryCompu󰀁tation,2000,8(1):1-29.

[8]󰀁OSTUNA.Thresholdselectionmethodfromgray-Levelhisto󰀁

grams[J].IEEETransactionOnSystem,Man,1979,9(1):62-66.

[9]󰀁IORIOA,LIXIAO󰀁DONG.ParametercontrolwithinaCo󰀁Operative

Co󰀁Evolutionarygeneticalgorithm[A]//Proceedingsofthe7thIn󰀁ternationalConferenceonParallelProblemSolvingfromNature.London:Springer󰀁Verlag,2002:247-256.

[10]ERIKSSONR,OLSSONB.Cooperativecoevolutionininventory

controloptimization[C]//Proceedingofthe3rdInternationalCon󰀁ferenceonArtificalNeuralNetworksandGeneticAlgorithms.Nor󰀁wich:[s.n.],1997:583-587.

[11]HOLLANDJH.Adaptationinnaturalandartificialsystems[M].

AnnArbor:UniversityofMichiganPress,1975.andCybernetics,

PatternRecognition,

1999,

32

图5󰀁实验图像的方差在进化过程中的变化

4󰀁结语

针对一类既需要提取目标轮廓又需表现纹理特征的图像,本文成功地将纹理与灰度信息纳入到Co󰀁CEA框架中,并实现了图像分割。实验仿真结果表明该方法有着良好的可行性和有效性。

下一步的工作是找到更为合理的联合适应度函数,另外