利用遗传算法实现数字图像分割

文章编号:100021220(2002)0720875203

　　收稿日期:2001201215　基金项目:湖北省教委重点科研项目(2000A 01020)资助　作者简介:金　聪,教授.目前主要从事图像处理、进化

计算、神经网络的数学与研究工作.彭嘉雄,教授.博士生导师.主要从事图像处理等方面的教学与研究工作.

利用遗传算法实现数字图像分割

金　聪1　彭嘉雄2

1(

华中科技大学图像信息处理与智能控制教育部重点实验室,湖北武汉430074)

2(

湖北大学数学与计算机科学学院,湖北武汉430062)

摘　要:本文将遗传算法引入数字图像分割之中.在此基础上,利用文献〔5〕提出的一种具有每个基因位交叉概率自适应变化的新交叉操作的改进型遗传算法来实现数字图像的分割.模拟结果表明,本文算法用于数字图像分割,其收敛性能远远高于文献〔2〕的传统方法和标准遗传算法.关键词:遗传算法;图像分割;收敛性能中图分类号:TN 911.73　　　　　文献标识码:A

1　引　言

在对图像的研究和应用中,人们往往仅对图像中的某些部分感兴趣.这些部分常称为目标或前景(其它部分称为背景),它们一般对应图像中特定的、具有独特性质的区域.图像分割就是把图像中的目标分成许多感兴趣的区域,并提取出感兴趣目标的技术与过程.这里所说的特性可以是灰度、颜色、纹理等,而目标可以对应单个区域,也可以对应多个区域.图像分割是自动目标识别的关键和首要步骤,也是一种基本的计算机视觉技术.,第一类是找出图像中各种物体的边缘,利用边缘信息把图像分成感兴趣区;另一类是从区内相似特征找出图像中各种物体区,显然物体区的外轮廓也就是边缘.多年来,图像分割一直得到人们的高度重视,每年都有上百篇相关的研究报告发表〔1,2〕.但它的研究进展比较缓慢,被认为是计算机视觉中的一个瓶颈.最简单、也是最常用的图像分割方法是采用对比度、边缘或灰度检测方法,它假定目标与背景相比有明显的灰度变化.这对于理想情况或背景很简单的情况是合适的,但与很多实际情况不符.采用灰度直方图统计的分割方法能使图像分割性能有所改善.本文将遗传算法〔3〕用于灰度直方图统计的图像分割中.利用遗传算法的全局随机寻优能力来获得最优分割门限,从而达到更有效地把背景与目标分割开来的目的.

2　图像阈值分割的算法描述

利用图像中各像点的特征来分割是较常用的方法.其特

征中选择最多的是灰度级.它是根据“同一种物质、细胞、粒子具有相同或相似灰度或彩色的概率最大”来进行的.因此图像中各物体的区分可用灰度级的差别来划分.

若已知图像直方图为双峰型,这时图像的直方图可看作是灰度级的概率密度函数的离散化估计.因此总的密度函数是两个单峰密度函数的混合,一个是物体峰,一个是背景峰.其混合参数正比于每一种图像灰度的面积.若已知这些灰度

的概率密度的表示式,就能按最小误差准则来确定最佳门限.

设图像的灰度范围为{0,1,...,l -1},选择门限T 将图像划分为两类:C 0:{0,1,...,T },C 1:{T +1,T +2,...,l -1}.不妨设已知图像的物体和背景为高斯型分布,其概率密度为

p 1(x )=P 12ΠΡ1

exp [-12(x -Λ1Ρ1

)2

]p 2(x )=

P 2

2ΠΡ2

exp [-

12(x -Λ2Ρ2

)2

]式中,Λ1,Λ2分别为两种灰度的均值;Ρ1,Ρ2为两种灰度分布围

绕均值的标准差;P 1,P 2为两种灰度分布的先验概率.

若图像中只包含这两种分布,则其混合概率密度为

p (x )=P 1p 1(x )+P 2p 2(x )=P 12ΠΡ1

exp [-1

2(

x -Λ1

Ρ1

)2]+

P 2

2ΠΡ2

exp [-

12(x -Λ2Ρ2

)2

]由于图像中像元的约束条件应满足:

P 1+P 2=1

则式中的混合密度有5个未知参数.若所有参数皆可知或从拟合得来,则按最小误差准则,最佳门限可以按如下方法确定.

设直方图暗区相当于背景,亮区为物体,即Λ1<Λ2,设最佳门限为T ,则使所有灰度级低于T 的像元都作为背景点考虑,而灰度级在T 以上的像元皆作为物体考虑,这样必然引起误差,把物体点错分为背景点的误差概率记为E 1(T )

=

∫T

-∞

p

2

(x )d x ,同理把背景点错分为物体点的误差概率记

为E 2(T )=

∫

+∞

-∞

p 1

(x )d x ,因此总的误差概率为

E (T )=P 2

∫T

-∞

p 2

(x )d x +P 1

∫

+∞

T

p 1

(x )d x (1)

　第23卷第7期　　2002年7月

小型微型计算机系统M I N I -M I CRO SYST E M V o l 123N o 17　

　July 2002　　

T3=arg{M in

0≤T≤l-1

E(T)}

3　图像分割的遗传算法描述

遗传算法是由美国M ich igan大学J.H.Ho lland〔4〕于1995年提出的自适应随机优化搜索算法.遗传算法的操作对象是一群二进制串(称为染色体、个体),即种群,每个染色体都对应于问题的一个解.从初始种群出发,采用基于适应值比例的选择策略在当前种群中选择个体,使用交叉和变异来产生下一代种群.如此一代代演化下去,直到满足期望的终止条件.在标准遗传算法中,选取任一个基因位作为交叉位置的概率是相等的.但等概率地选取交叉位置并在此基础上改变其相应的基因值,将不能有效地在优化空间中搜索最优解.这是因为不同基因位的改变造成个体适应度值的改变程度不同.也就是说,各个基因位的重要性不是等同的.因此,等概率地选取交叉位置必将影响遗传算法的寻优能力.本文中,我们将采用自适应确定交叉概率的方法,并将此方法应用到数字图像的分割中.

将遗传算法应用于图像分割时,算法的基本步骤如下:

Begin

1.t=o;

2.随机选择初始种群P(t);

3.计算适应度函数值f(t);

4.t=t+1;

5.如果终止条件满足则转到第8步;

6.按适应值比例的方法从P(t21)中选择P(t);

7.对P(t)进行交叉、变异操作,之后转到第3步;

8.输出最佳门限并分割图像,算法终止.

End

以下对应用改进型遗传算法进行图像分割时的一些具体设计方法做进一步的介绍.

编码方式　因为图像的灰度级在0～255之间,所以本文将染色体编码成8位二进制码.它代表某个门限值.初始种群是随机产生的,它们的适应度值往往不同.

适应度函数　采用f(T)=1

1+E(T)

作为适应度函数.这里需要注意的是,在解决实际问题的过程中,密度函数的参数往往需要用拟合法来求出p(x)参量的估计值.常用的方法是最小均方误差拟合法.由于该方法不是本文讨论的重点,这里不做进一步介绍,具体实现步骤请参见文献〔2〕.

交叉操作　为了避免选用固定交叉概率带来的弊端,我们采用自适应确定交叉概率的方法.具体方法如下:对于第t代种群,设每个i个体第个基因位的交叉概率为p(i)c(t),保留算法运行过程中产生的当前最优解X3.在每一代运行中,对于选出的父代X1和Y1,在第i个基因位做单

点交叉〔5〕可以得到两个子代X2和Y2记f i=f (X2)+f(Y2)

2

,

则对基因位i其交叉概率的修改公式为:

p(i)c(t+1)exp(

f(x3)-f i

f(x3)

)・p(i)c(t),i=1,2,…,n(2)其中n为二进制编码的长度.由此可见,交叉概率是自适应变化的.对于自适应交叉概率设计思想请参见文献〔5〕.本文中初始交叉概率取0.4.

变异操作　以一定的变异概率随机地改变一个个体某一位的值,即进行取反运算,就是1变0或0变1.本文取变异概率为0.05.

终止条件　规定最大进化代数是40.如果连续进化20代适应度值始终大于给定的阈值,即使进化代数没有达到40,算法也将终止.此时,选取适应度值最大的个体为最优分割门限.

4　实验结果及分析

我们选取L ena标准图像(512×512)来进行实验.我们用本文方法和文献〔2〕中介绍的传统方法分别对L ena标准图像(512×512)各做20次图像分割.从分割质量来看两种方法基本相同,但本文方法的分割速度却比传统方法快得多.具体结果见表1.表1中的加速比指分别用本文方法和传统方法对L ena标准图像进行20次分割所需时间的平均值的加速比.

表1　本文方法与传统方法的时间比较

平均时间加速比

本文方法0.09s

传统方法0.23s

2.556

为了比较本文所给遗传算法与标准遗传算法进行数字图像分割的能力,我们选取平均进化代数作为检验指标之一.这里所说的平均进化代数是指对于L ena标准图像(512×512)做多次分割(本文用两种遗传算法分别做20次分割)取得的进化代数的平均值作为检验指标.对于适应度值设定一阈值,本文将适应度值的阈值设定为0.01.当适应度大于此阈值则认为算法收敛.若进化代数大于40算法仍不收敛,则认为分割失败.分割结果见表2.

表2　本文方法与标准遗传算法的比较

本文方法标准遗传算法

平均进化代数4.327.96

平均门限值119.36120.08

分割成功次数2017

以上实验均是在P 2300A、内存为128M B的微机上实现的.由表1、表2可见,尽管本文算法与文献〔2〕的传统方法的分割质量相同,但速度却快得多.另外,在相同条件下,本文方法与标准遗传算法相比,不仅分割成功的次数有所提高,而且平均进化代数比标准遗传算法少,可以提高分割速度.由此可以说明,本文方法不仅可以用于数字图像的分割,而且可以大大提高分割的速度,具有一定的优越性.

参　考　文　献

678　　　　　　　　　小　型　微　型　计　算　机　系　统　　　　　　　2002年

1Zhangyujin .I m age Engineering (I )2I m age p rocessing and i m age

analysis 〔M 〕

.Beijing T singhua U niversity Pullish ing House ,1999

(章毓晋.图像工程(上册)图像处理和分析〔M 〕.北京.清华大学出版社.1999)

2Rongguanao .Computer i m age p rocessing 〔M 〕.Beijing T singhua U niversity Publish ing House ,2000(容观澳.计算机图像处理〔M 〕

.北京.清华大学出版社.2000)3Go ldberg .D .Genetic algo rithm s in search ,op ti m izati on and

M ach ine L earning 〔M 〕

.U SA :A ddison 2W esley Publising Company ,1988,7210,59～308

4Ho lland ,J .H .A dap tati on in natural and artificial system s 〔M 〕

.T he U niversity of M ich igan P ress ,1975.

5J incong .I mp rove genetic algo rithm and analysis of its p roperty 〔J 〕.M ini 2M icro System s ,200021(9):950～952(金聪.改进型遗传算法及其性能分析〔J 〕.小型微型计算机系统.2000.21(9):950～952)

6Fogel ,D .B .Evo luti onary computati on :tow ard a new

ph ilo sophy of m ach ine intelligence 〔M 〕

.Institute of E lectrical and E lectronics Engineers ,Inc ,N ew Yo rk ,1995:155～171

7Go ldberg ,D .E .,Sam tani ,M .P .Engineering op ti m izati on via

genetic algo rithm s 〔C 〕

.P roceeding of the N inth Conference on E lectronic Computati on ,1986,471

～482.D ig ita l I mage Segm en ta tion Ba sed on Genetic A lgor ith m

J I N 　Cong ,PEN G 　J ia 2xi ong

1(

K ey L abora tory of E d uca tion M in istry f or Im ag e P rocessing and In tellig en t Con trol ,

H uaz hong U n iversity of S cience and T echnology ,W uhan 430074,Ch ina )

2(Colleg e of M a the m a tics and Co mp u ter S cience ,H ubei U n iversity ,W uhan 430062,Ch ina )

Abstract 　In th is paper ,the classical i m age segm entati on m ethod is i m p lem ented using i m p rove genetic algo rithm ,w ho se

cro ssover p robability being adap tive changed of each gene .T he si m ulated result show that i m p rove genetic algo rithm has great advantage of convergence ti m e p roperty over classicalm ethods and classical genetic algo rithm about digital i m age segm entati on .Key words 　genetic algo rithm ;i m age segm entati on ;convergence p roperty

中国计算机学会

全国办公自动化技术及应用学术会议

征　文　通　知

中国计算机学会办公自动化专业委员会拟于2003年春在扬州召开办公自动化(O A )技术及应用学术会议,同时召开全体委员会议。现将有关事项通知如下:

一、征文范围

所有涉及OA 技术和应用的动向、研究、开发和应用成果的论文,主要包括:1.OA 现状及技术发展趋势2.网络技术与分布式系统3.OA 中的信息安全技术4.OA 开发工具和OA 语言5.工作流 数据库、数据仓库和数据挖掘技术6.OA 中的多媒体技术7.电子商务 电子政务

8.人工智能与决策分析在OA 中的应用9.其它二、来稿要求

1.理论联系实现,具有学术和应用推广价值。未被其它会议、期刊录用或发表。

2.来稿一般不得超过6000字(含图表),为了便于正式出版论文集,来稿必须附中、英文摘要、关键词及主要参考文献,注明作者姓名、工作单位、详细通讯地址(包括电子邮件地址)与作者简介。

3.欢迎电子投稿,来稿一般不退,请自留底稿。

三、来稿地址

南京东南大学计算机科学与工程系胡苏宁;邮编:210096;电话:(025)3793044;Em ail :yangm ing @seu .edu .cn 四、重要日期

征文截止日期:2002年10月15日录用通知发出日期:2002年11月20日

7

787期　　　　　　　金　聪等:利用遗传算法实现数字图像分割