一种改进的分裂合并图像分割算法

黄 猛 唐 琳 胡世安等

摘 要:图像分割是图像分析和目标识别中的关键技术之一。在传统图像分割方法的基础上,提出一种将改进的自适应遗传算法与合并分裂法相结合的图像分割算法。针对遗传算法运算速度低,容易陷入局部最优值、早熟收敛等缺点,在此通过对遗传操作算子的改进、适应度评价函数的科学设计以及交叉和变异概率的自适应调整来降低图像分割产生的误差。计算机仿真结果证明,该算法能够取得较好的图像分割效果。

关键词:目标识别;图像分割;自适应;遗传算法;适应度

中图分类号:TP391

图像分割是图像分析和目标识别中的关键技术之一。图像分割过程中,难免会产生一些误差。这些误差将直接影响到图像处理的效果和目标识别的准确性,如何使这些误差降到最小是图像分割的重要指标。

遗传算法作为一种概率搜索的寻优算法,因其在解决非线性问题上具有良好的适用性,在图像分析领域得到了广泛的应用。但是传统遗传算法本身也存在着┮恍┆缺陷,如早熟、局部最优解、占据较大的存储空间和运算时间,并且在实际应用中缺乏对特定知识的利用,保证不了对图像分割的计算效率和可靠性要求。为了将图像分割过程中产生的误差降至最小,本文结合传统的图像分割技术,提出一种将改进的遗传算法与合并分裂法相结合的图像分割算法,通过对交叉和变异概率的自适应调整,降低图像分割产生的误差。

1遗传算法

遗传算法( Genetic Algorithm,GA) 基于达尔文的进化论和孟德尔的自然遗传学说,是模拟遗传选择和自然淘汰的生物进化过程中一种随机搜索与全局优化算法。1975年,Holland在其专著中提出了GA的概念和方法,因其具有很强的解决问题能力和广泛的适应性,因而近年来渗透到研究与工程的各个领域,取得了良好的效果[2,3]。遗传算法利用某种编码技术将问题的解转化成为染色体的数据串,其基本思想是模拟由这些染色体数据串组成群体的进化过程。遗传算法通过有组织、随机地交换信息来重新结合那些适应性好的串,在每一代中,利用上一代结果中适应性好的位和段生成一个新的串的群体;作为额外添加,偶尔也要在串的结构中尝试用新的位和段来替代原有部分。

2 基于改进遗传算法的分裂合并图像分割算法

2.1 图像分割原理

图像分割的步骤如下:首先,将图像分割成不同的区域;其次,在分割后的相关区域中提取目标特征;再次,根据提取的目标特征以及相关的结构信息对其进行分类和识别;最后,给出对整幅图像分析结果的描述信息。在图像被分割成区域后,可以进一步从中提取目标特征,进行目标识别,例如在海洋中识别出舰船等。

图像的分割依据是根据图像的灰度、颜色、纹理和边缘等特征,把图像分成各自满足某种相似性准则或具有某种同质特征连通区域的集合。目前,图像分割已经有很多成熟的方法。本文针对图像分割中引起的较大误差,提出一种将改进的自适应遗传算法与合并分裂法相结合的图像分割算法,以有效降低图像分割过程中产生的误差。

分裂合并分割法的原理:从整个图像出发,根据图像和各区域的不均匀性,把图像或区域分裂成新的子区域;根据毗邻区域的均匀性,把毗邻的子区域合并成新的较大区域。设用R表示整个图像,用R璱表示分割成的一个图像区域;并假设同一区域R璱中的所有像素都满足某一相似性准则时,P(R璱)=玊RUE,否则㏄(R璱)=獸ALSE。当P(R璱)=玊RUE时,不再进一步分割该区域;当P(R璱)=獸ALSE时,继续将该区域分成大小相同的四个更小的象限区域。在这种分割过程中,必定存在R環的每个子区域R璲与R璴的某个子区域R璳具有相同性质,也即P(R璲∪R璳)=玊RUE,这时就可以把R璲和R璳Ш喜⒆槌尚碌那域。

2.2 图像分割的改进遗传算法实现

使用改进的自适应遗传算法实现分裂合并图像分割的方法具体如下。

2.2.1 染色体编码

假设最大图像分割区域数目为玭,则个体的染色体编码为一个整数序列,即:

I璳={r璱|i=1,2,…,n}。式中:r璱对应于一个固定位置的分区序号;k为个体编号。

2.2.2 适应度函数

遗传算法中的一个个体对应一个图像分割,个体适应度的评价实际上是对该个体所描述的图像分割质量的衡量。在没有分割参照情况时,图像分割评价可以包括两方面的内容:区域一致性度量和边缘模糊性度量。

(1) 区域一致性度量

(2) 边缘模糊性度量。

前面讨论局部对比度时,只考虑两个邻接区域边界部分的模糊性。所有区域边界模糊性的综合度量其公式如下:

遗传算法中个体的适应度评价可以采用上述两种度量的综合形式,以反映个体图像在经历一系列分裂合并过程后图像的分割质量。个体的适应度F计算为┮恢滦远攘縂与边缘模糊性度量E的乘积形式,Ъ:

(1) 选择算子。

选择操作使用按比例的适应度分配方法,个体的适应度越高,其被选择的概率就越大。轮盘赌是一种常用的选择方法,其原理是:以个体的相对适应度玃,将整个赌盘分成大小不同的扇面,个体被选择的概率与该扇面的圆心角成正比。圆心角越大,该扇面被选择的可能性就越大;圆心角越小,该扇面被选择的可能性就越小。于是各个扇面的大小就决定了各个体被遗传到下一代群体中的概率。

(2) 交叉算子。

交叉操作采用改进的两点交叉法,编码序列中的基因码在交叉操作后允许重复,正是依靠产生重复基因码,图像区域才得以进一步分裂或合并。此外,如果区域r璱与其毗邻的区域r璲合并,即I璳[i]=i,I璳[j]=i,则其他已经合并到区域r璲的区域r璴也相应地合并到区域r璱,即I璳[l]=i,因此所有合并到区域r璱的区域基因码都是i。И

图2给出了交叉操作的一个示例,子个体Child的第5～10位基因继承了个体玃2,其余位的基因继承了个体玃1。而第11位被改变为玶5,第7位被改变为r7。

(3) 变异算子。

变异操作结合局部对比度设计┮恢知动态变异算子。所谓局部对比度是用来刻画区域边界信息模糊性的一种度量。

在一个分割对应的个体基因码中,变异操作分两个步骤:首先计算个体编码序列中所有基因码表示区域的局部对比度,按轮盘赌法计算一个个体编码中基因变异概率,概率的大小与其对应的区域局部对比度成正比;接下来确定区域的分裂或者合并,若某区域的基因变异概率大于预定变异概率P璵,则对该区域随机的选择发生合并或分裂。区域合并对象为与之邻接区域中相对距离u﹊j最小者,而分裂只发生在该区域已经与其他区域合并时,从其他区域分离出来。图4为一个个体变异的示例,假定第二位和第五位基因变异概率大于预定变异概率P璵,则区域r5和r7被选择决定合并或分裂。若决定r5合并,与r5相对距离最小者为r2,则r5并入r2,┑谖濯位基因码变为r2;若决定r7分裂,由于此前r7已与r11合并,这时将r7分离出来,则第7位基因码不变,第11位和12位变为r11。И

2.2.4 交叉和变异概率的自适应选择

多数情况下,种群中不同个体的适应度不尽相同,因此可以用适应度分布的离散程度来表征种群的“早熟”程度。种群在进化过程中发生“早熟”的主要表现是:种群内适应度暂时最大的一些个体相互重复或趋同,使得它们有较大的概率参与下一代的选择复制操作,且它们之间交叉后的子代也不会与父代有太大的变化,导致遗传算法寻优过程十分缓慢,降低搜索效率。因此,要正确判断一个种群是否会发生“早熟”主要看这个种群当前适应度最大的那些个体是否重复或相互趋同。基于此思想,在此给出了基于适应度分布离散程度来评价种群“早熟”程度的指标:

设第t代种群由个体X1璽,X2璽,…,X琈璽构成,适应度分别为F1璽,F2璽,…,F琈璽。种群个体的平均适应度璽=∑Mi=1F琲璽/M;最优个体适应度为F﹖玬ax;﹖玬ax代表适应度大于璽的个体平均适应度。定义F﹖玬ax与﹖玬axе间的差值:[JP]

ИЕぁ=F﹖玬ax-﹖玬ax猍JY](14)И

式中:Еぁ溆美幢碚髦秩旱摹霸缡斐潭取薄？梢钥闯,当Δ′增大时,种群趋于发散;Δ′减小时,种群趋于相同。此方法只计算F﹖玬ax与﹖玬ax的差值,不涉及适应度低于平均适应度的个体,从而避免了那些适应度较差的个体对Δ′У挠跋,更能反映种群中那些适应度较好的个体之间的趋同程度。

选择合适的遗传算子执行概率,是遗传算法能否收敛到最优解的关键之一[9]。在传统的遗传算法中,交叉概率玃璫、变异概率玃璵等控制参数与种群进化过程无关,从始至终都保持定值。近年来的研究表明,控制参数对系统性能有重要的影响。交叉概率玃璫的高低将决定解群体的更新和搜索速度的快慢。玃璫太大会使算法的探测能力越强,越容易探测到新的优良个体,增加算法的收敛速度;玃璫太小会使搜索停滞不前。变异对于保持解群体结构的多样性,防止算法“早熟”是一种重要手段:变异概率玃璵太小时,难以产生新的基因块;┆玃璵太大又会使遗传算法变成随机搜索,从而失去其优良特性。

由此可知,交叉概率和变异概率对于遗传算法的收敛性能都有重要的影响。

用不变的控制参数来控制遗传进化,很容易导致“早熟”,降低算法的搜索效率。目前,调整遗传算法中控制参数较好的方法是动态自适应技术,其基本思想是使玃璫,玃璵在进化过程中根据种群的实际情况,随机调整大小[5]。

具体做法为:当种群趋于收敛时,减小玃璫,增大玃璵,即降低交叉的概率,提高变异的概率,以保持种群的多样性,避免“早熟”;当种群个体发散时,增大玃璫,减小玃璵,即提高交叉的概率,降低变异的概率,使种群趋于收敛,增加算法的收敛速度。

根据前述评价种群“早熟”程度的指标Δ′,给出自适应调整遗传算法控制参数的策略,使得交叉概率玃璫、变异概率玃璵在进化过程中随着Δ′的变化而改变,该策略数学公式为:

式中:k1,k2>0。由于Δ′始终大于或等于0,所以玃璫取值范围在[0.5,1]之间,玃璵的取值范围在[0,0.5]之间。从上式可见,在进化过程中,玃璫,玃璵根据Δ′取值的不同而动态地自适应调整:当种群个体趋于离散(即Δ′变大)时,玃璫增大,玃璵减小,种群开发优良个体能力增强;当种群个体趋于收敛(即Δ′变小)时,玃璫减小,玃璵增大,种群产生新个体能力增强。

3 图像分割仿真试验

图5给出了一幅军舰图片的分割过程,原图是大小为256×256的灰度图像,使用上述算法对其进行分割测试。种群大小为60,交叉和变异概率自适应调整系数玨1=2.0,k2=4.0,预定分割区域最小和最大面积α,β分别取5,20。图5为挑选出若干代中最佳个体对应的分割结果,大约到200代后达到比较好的分割效果。[LL]

4 结 语

对传统图像分割算法进行了改进和扩充,提出了┮恢知将改进的自适应遗传算法与合并分裂法相结合的图像分割算法。通过对每代种群“早熟”程度的判断,实现对交叉和变异概率的自适应调整;基于启发式知识来设计允许基因重复的交叉算子,对标准遗传算子进行改进;并使用区域一致性度量和边缘模糊性度量作为算法的适应度函数,符合图像分割的实际情况。仿真结果证明,该算法能够在较短的时间内实现对原始图像的分割,并取得较好的分割效果。

参 考 文 献

[1]唐国新,陈雄,袁杨.基于改进遗传算法的机器人路径规划[J].计算机工程与设计,2007,28(18):4 446[CD*2]4 449.

[2]李敏强,寇纪淞.遗传算法的基本理论与应用[M].北京:科学出版社,2002.

[3]Holland J H.Adaptation in Natural and Artificial Systems:An Introductory Analysis with Applications to Biology,Control and Artificial Intelligence[M].MA:MIT Press,1992.

[4]李俊山,李旭辉.数字图像处理[M].北京:清华大学出版社,2007.

[5]王小平,曹立明.遗传算法[CD2]理论、应用与软件实现[M].西安:西安交通大学出版社,2002.

[6]Mat Buckland.游戏编程中的人工智能技术[M].吴祖增,沙鹰,译.北京:清华大学出版社,2006.

[7]云庆夏,黄光球,王战权.遗传算法和遗传规划[M].北京:冶金工业出版社,1997.

[8]李丽.基于遗传算法的舰船航行路径规划技术研究[D].哈尔滨:哈尔滨工程大学,2006.

[JP2][9]Grefenstette J J.Lamrckian Learning in Multiagent Environments[A].Proceedings of the Fourth International Conference on Genetic Algorithms[C].San Mateo,CA,1991:303[CD*2]310.[JP]

作者简介 黄 猛 男,1977年出生,江苏徐州人,工程师。研究方向为算法分析、通信工程。