基于改进遗传算法的图像边缘特征提取*

乔玲玲　毛晓菊

(商丘学院计算机工程学院　商丘　476113)



基于改进遗传算法的图像边缘特征提取*

乔玲玲毛晓菊

(商丘学院计算机工程学院商丘476113)

摘要遗传算法作为一种实用、稳健的优化搜索算法，已经渗透到许多学科及工程领域，在数字图像处理中的应用亦日趋广泛。为了能够快速有效地提取出图像的边缘，对遗传算法的选择、交叉和变异算子分别进行了改进，并将其应用到图像边缘特征提取中。实验结果表明，改进遗传算法在保证有效地提取出边缘的基础上，提高了收敛性能，是一种有效的、可靠的优化算法，具有一定的实用价值。

关键词遗传算法; 边缘特征提取; 阈值; 图像分割

Class NumberTP391

1引言

在对图像的研究分析中，多数情况下只对其中的某些部分感兴趣，例如一幅遥感图像，从军事的角度可能只对机场、导弹基地、兵工厂等军事目标比较关心；而从其它的角度如环境生态方面考虑，则只对森林、湿地、草地等目标感兴趣。这些目标在图像中形成具有独特性质的区域，为了对其进行识别和分析，需要把这些区域分离出来，然后提取区域所具有的特征，进而对其识别和分类，这就是图像分割要研究的问题。在对图像分割过程中，不可避免的会存在一些误差，这些误差会影响图像处理的效果，如何使这些误差最小是使机器视觉达到实用化的重要要求。遗传算法在这些图像分割中的优化计算方面找到了用武之地。

2遗传算法描述

2.1基本思想

遗传算法类似于自然进化，通过作用于染色体上的基因寻找好的染色体来求解问题。与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始群体；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的种群，对这个新种群进行下一轮进化。遗传算法的具体描述如下：

1) 初始化群体；

2) 计算群体上每个个体的适应度值；

3) 按由个体适应度值所决定的某个规则选择将进入下一代的个体；

4) 按概率Pc进行交叉操作；

5) 按概率Pm进行突变操作；

6) 没有满足某种停止条件，则转第2)步，否则进入7)；

7) 输出种群中适应度值最优的染色体作为问题的满意解或最优解。

程序的停止条件最简单的有如下两种：完成了预先给定的进化代数则停止；种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。

2.2选择操作

选择操作也叫复制操作，根据个体的适应度函数值所度量的优、劣程度决定它在下一代是被淘汰还是被遗传。一般地说，选择将使适应度较大(优良)个体有较大的存在机会，而适应度较小(低劣)的个体继续存在的机会也较小。最常用的选择算子是基本遗传算法中的轮盘赌选择[1]和比例选择算子[2]。但对于各种不同的问题，它们并不是最合适的选择算子，因此对选择算子进行改进，采用确定式采样选择[3]。

确定式采样选择方法的基本思想是按照一种确定的方式来进行选择操作。其具体操作过程是：

1) 设群体大小为N，各个个体的适应度为Fi(i=1，2，…，N)，计算群体中各个个体在下一代群体中的期望生存数目Ni，如式(1)所示：

(1)

2.3交叉操作

遗传算法中的所谓交叉运算，是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起着关键作用，是产生新个体的主要方法。

本文采用非等概率融合单点交叉算子，该方法融合了“非等概率选择交叉位置”[4～5]和“应用逻辑操作”两种方法的优点。首先非等概率地选取交叉位置，然后对交叉位置右边的基因进行逻辑操作，产生新的后代。具体操作如下：等概率产生一个0到length-1(length为编码长度)的随机整数T，当T=0或T=1时选择第一个基因为交叉位置，否则选取第T个基因为交叉位置。然后对两个父辈个体的T十1位到length位进行逻辑操作，用“与”操作产生后代1，用“或”操作产生后代2。

2.4变异操作

遗传算法中的所谓变异运算，是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。

对变异算子的一个改进方向是根据群体的进化程度调整变异概率的值[6]，其基本思想为：当群体比较集中时，意味着它可能陷于局部极值或存在早熟现象，于是对它进行一个大变异[7]操作，独立随机地产生新的个体，以便求出全局最优值或脱离早熟现象。变异概率如公示(2)所示：

(2)

采用最大适应度Fmax、最小适应度Fmin、适应度平均值Favg这三个变量来衡量群体适应度的集中程度，然后根据适应度集中程度，决定是否采取大变异操作。同时采取最优保存策略来保证最优个体不被大的变异概率Pm破坏掉。

3基于阈值的图像边缘特征提取

本文介绍一种基于阈值的图像边缘提取方法，其原则是：设灰度图像的灰度级数目为level，则像素点的灰度级取值范围为{0，1，2，…，level-1}，设(x，y)为灰度图像中像素点的坐标，f(x,y)为该像素点的灰度级[8～9]。对于阈值t，若像素点满足下列条件之一，则认为该点为图像边缘。

1)f(x,y)≥t且f(x-1,y)

2)f(x,y)≤t且f(x-1,y)>t

3)f(x,y)≥t且f(x,y-1)

4)f(x,y)≤t且f(x,y-1)>t

这种方法具有良好的抗噪声性能，可以检测出有效的边缘[10]。判断最优阈值的方法是，检验出的边缘数目最多的阈值即为最优阈值。对于不同的阈值，可以检验出的边缘数目也不同。

4实验结果及分析

图1　阈值分割的遗传算法框图

在这里，本文的控制参数如下：群体规模N为20，交叉概率为0.85，变异概率为0.01。遗传算法运行代数为30代，当算法执行到最大代数或经过10代未进化(群体的最高适应度未发生变化)，就认为得到了最优阈值，跳出遗传运算，得到图像的边缘提取结果。算法的流程图如图1所示。

本文对美女图像进行实验，实验结果如图2和图3所示。

图2　美女图像

图3　GA

选用遗传算法对于某一优化问题寻优收敛所需的平均进化次数作为检验指标。所谓平均进化次数是指，对于某一目标函数重复地做寻优试验而得到的进化次数的平均值。

每次试验结果可能不同，因此本文对于图像的分割法进行了30次试验。取其平均值作为检验指标。得到表1所示的试验数据。

表1　美女图像的性能指标

从表1可以看出，穷尽法得到的边缘是实际最优解。GA收敛到最优解的能力比较强，得到的阈值很接近最优解。

5结语

本文以遗传算法的未收敛次数和平均进化次数两个评价指标为参考，将遗传算法应用于图像的边缘特征提取中，试验结果表明，遗传算法在保证有效地提取出边缘的基础上，提高了收敛性能。本文虽然对遗传算法的理论及其在图像的边缘特征提取中的应用作了一些有益的研究，但无论是遗传算法理论本身还是其在图像边缘特征提取中的应用和研究都有待进一步探讨和完善。因此进一步的研究遗传算法以及遗传算法和其它方法的结合及其在图像边缘特征提取中的应用，将对数字图像的智能信息处理有一定的影响。

参 考 文 献

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

LI Minqiang, KOU Jisong, LIN Dan, et al. The basic theory and application of genetic algorithm[M]. Beijing: Science Press,2002:512-557.

[2] 郭东伟,周春光,刘大有.遗传算法取代时间的分析[J].计算机研究和发展,2001,38(10):1211-1216.

GUO Dongwei, ZHOU Chunguang, LIU Dayou. Analysis of Takeover Time for Genetic Algorithms[J]. Journal of Computer Research & Development,2001,38(10):1211-1216.

[3] 王永良,陈辉,万群,等.空间谱估计理论与算法[M].北京:清华大学出版社,2004:78-102.

WANG Yongliang, CHEN Hui, WAN Qun, et al. Spatial Spectral Estimation Theory And Algorithm[M]. Beijing: Tsinghua University Press,2004:78-102.

[4] 章坷,刘贵忠.交叉位置非等概率选取的遗传算法[J].信息与控制,1997,26(1):53-60.

ZHANG Ke, LIU Guizhong. Selecting Crossover Site With Unequal Probability In Genetic Algorithms[J]. Information and Control,1997,26(1):53-60.

[5] M. Srinivas, L. M. Patnaik. Adaptive probabilities of crossover and Mutation in Genetic Algorithm[J]. IEEE Transactions On Systems, Man and Cybernetics,1994,24(4):656-667.

[6] 高艳霞,刘峰,王道洪.改进型遗传算法及其应用研究[J].上海大学学报,2004,10(suppl):249-253.

GAO Yanxia, LIU Feng, WANG Daohong. Modified Genetic Algorithm and Its Application[J]. Journal of Shanghai University,2004,10(suppl):249-253.

[7] 马均水,刘贵忠,贾玉兰.改进遗传算法搜索性能的大变异操[J].控制理论与应用,1998,15(3):404-408.

MAO Junshui, LIU Guizhong, JIA Yulan. Improved Genetic Algorithm on Search of Big Mutation Operation[J]. Control Theory and Applications,1998,15(3):404-408.

[8] 吴谨,李娟,刘成云,等.基于最大熵的灰度阈值选取方法[J].武汉科技大学学报:自然科学版,2004,27(1):58-60.

WU Jin, LI Juan, LIU Chengyun, et al. A Method for Gray2Level Threshold Selection Based on Maximum Entropy[J]. J. of Wuhan Uni. of Sci. & Tech.,2004,27(1):58-60.

[9] Lee S U, Chung S Y, Park R H. A comparative study of global thresholding Techniques for segmentation Computer Vision[J]. Graphics and Image Processing,1990,52:171-190.

[10] R. Kohler. A segmention system based on thresholding[J]. Computer Vision, Graphics and Image Processing,1981,15:319-338.

收稿日期:2016年1月12日,修回日期:2016年2月28日

作者简介:乔玲玲,女,硕士研究生,讲师,研究方向：图像处理，物联网。毛晓菊,女,讲师,研究方向：计算机网络，图形图像。

中图分类号TP391

DOI:10.3969/j.issn.1672-9722.2016.07.035

Edge Feature Abstract of Image Based on Improved Genetic Algorithm

QIAO LinglingMAO Xiaoju

(Department of Computer, Shangqiu University, Shangqiu476113)

AbstractAs a kind of practical and sane optimum searching algorithm, the genetic algorithms has already permeated into many disciplines and project fields, whose application in digital image processing is also extensive day by day. In order to quickly and efficiently extract the edge of the image, in this paper, the selection, crossover and mutation operator of genetic algorithm are improved, and it is applied to extract the edge of the image. The experimental results show that improved gentic algorithm can detect satisfactory edges as well as improve convergence, which is a kind of efficient and reliable optimization arithmetic, having some applied value.

Key Wordsgenetic algorithm, edge feature abstract, threshold, image segmentation