求解图像边缘检测的遗传算法

陈桂霞

摘 要： 图像边缘检测技术是图像分析处理中的关键。以Sobel边缘检测方法为基础，针对Sobel算子寻优的困难性提出了应用遗传算法进行图像边缘检测的方案。为了更好地提高遗传算法的全局收敛性能和求解精度，在遗传算法中加入了自适应机制和精英反向学习机制，从而提高了寻找最优解的效率，在一定程度上遏制了算法的早熟现象和标准遗传算法解精度较低的弱点。

关键词： 图像边缘检测； 遗传算法； Sobel算子； 反向学习

中图分类号：TP312 文献标志码：A 文章编号：1006-8228（2018）11-73-03

Abstract： Image edge detection technology is the key to image analysis and processing. Based on the Sobel edge detection method， this paper proposes an image edge detection scheme based on the genetic algorithm for the difficulty of the optimization of the Sobel operator. In order to improve the global convergence performance and the accuracy of the genetic algorithm， the adaptive mechanism and elite reverse learning mechanism are added to the genetic algorithm to improve the genetic algorithm. The efficiency of finding the optimal solution， to a certain extent， curbed the premature convergence of the algorithm and the low accuracy of standard genetic algorithm.

Key words： image edge detection； genetic algorithm； Sobel operator； reverse learning

0 引言

基于內容的图像识别和理解，是新一代网络搜索引擎的重要研究方向，而图像边缘检测技术是其中的关键，它在图像的分析处理中有着非常重要的意义。如何寻找与图像真实边缘线相对应的实际边缘，长期以来一直是数字图像处理领域的研究热点，因为边缘的特征反映了图像灰度的不连续性，它提供了一幅图像的大量有效和有价值的信息。本文以Sobel[3]边缘检测方法为基础，介绍一种改进的遗传算法图像边缘检测方法，并通过在遗传算法中加入自适应变异算子和反向学习机制来提高遗传算法的收敛能力。

1 数字图像边缘

对于一幅图像，不同区域的灰度值是不相同的，而这些不同的区域之间往往是边缘的体现，灰度值的不连续是形成图像的主要原因。这种灰度值的不连续性可通过数学方法中的求导方法检测出来。比较常见的经典边缘检测方法一般都是通过一阶导数和二阶导数的求解来检测图像边缘的灰度值。图像灰度边缘是非常复杂的，基于采取样本的原因，获得的实际图像中的边缘是有坡度的，一般可以用位置、朝向、幅度、均值、斜率这五个参数来描述。所谓边缘检测也常指通过计算获得边缘五个参数数据。基于检测原理，可以采用多种不同的方法来检测边缘，主要包括基于梯度的边缘检测算子和二阶导数算子。

2 Sobel边缘检测算子

在3×3邻域内做加权平均和差分运算，以此为基础，Sobel在另一个著名的图像边缘检测算子Prewitt基础上，提出了一个新颖的图像边缘算子—Sobel算子，其计算过程如公式1。

Sobel算子的两个卷积算子模板分别是公式2和公式3。

因为Sobel算子将加权平均引入图像的边缘描述，它充分利用图像本身的信息，对像素点上下左右的灰度值进行加权运算，依靠在图像边缘点处所到达的极值来完成图像的边缘检测。该算子对于噪声所产生的影响较小，能够给噪声产生一定的平滑作用，进一步提供了相对准确的边缘配置信息。此外，由于描述图像的信息被局部平均处理，会对图像边缘描述的准确性产生一定的影响，所以检测边缘的过程可能会产生错误信息。在对图像边缘检测的精确度要求不高的情况下，Sobel算子仍然是一种运算速度快，较为常用边缘检测算子。

3 面向图像边缘检测的遗传算法

3.1 遗传算法的编码设计

进行图像边缘检测时，由于图像的灰度值范围是0～255，可以用8位二进制数表示一个解，进而可将8位二进制串当作遗传算法中的染色体。图1表示灰度范围条形值。例如染色体11111111代表的颜色如图2所示，染色体01111101代表的颜色如图3所示，染色体00101101代表的颜色如图4所示。

3.2 适应度函数设计

依据灰度图像的特性，把一幅图像分解成背景和目标两个部分。目标和背景之间的方差值越大，表示组成图像的两部分差别越大，如果一部分背景被错分为目标或者是目标被错分为背景，则会导致两部分的差别变小。所以，类间方差最大的分割则表明错分的概率最小。

假设f（x，y）是我们想要分割的客观图像，它的灰度范围是{0，1，…，L-1}。通过阈值t，图像像素将被分为公式4和公式5两类。

C0和C1分别代表目标和背景。这类图像的平方误差在C0和C1之间，表示为公式6。

这里t是阈值，ω0（t）是图像灰度值小于阈值t的像素数量。ω1（t）是图像灰度值大于阈值t的像素数量。μ0（t）是图像灰度值小于阈值t的像素平均灰度值。μ1（t）是图像灰度值大于阈值t的像素平均灰度值，使得σ（t）2最大值的t是最佳分割阈值。

3.3 求解图像边缘检测的标准遗传算法

将种群中的染色体应用8位二进制数进行编码，一条染色体代表一个解，基于上一节描述最大类间方差法作为遗传算法的适应度函数，则求解图像边缘检测的标准遗传算法步骤如下：

算法1 标准遗传算法（GA[1]）

Step1. 利用Sobel算子逐点计算原始图像从而获取梯度图像。

Step2. 应用遗传算法求解梯度图像的最佳分割阈值。

Step2.1. 染色体初始化。在解空间内，随机生成40条染色体作为初始种群。

Step2.2. 交叉算子。随机选择两条染色体，以单点交叉方式交叉，交叉概率设为0.6。

Step2.3. 变异算子。对各个染色体采用均匀变异算子，执行变异。

Step2.4. 若算法符合停止条件，则输出最佳阈值并终止算法；否则跳到Step2.2执行。

Step3. 依据阈值大小，假如图像的梯度值大于或等于阈值，便可以确定该点为最初始的边缘点，该点方向就是边界点的方向，否则就是一个无边点。

3.4 遗传算法的相关改进

由于标准遗传算法容易收敛于局部最优，解精度低，所以要在标准遗传算法中引入反向学习机制。考虑到在算法的进化迭代过程中，适应度优秀的个体代表了种群的收敛和前进方向，能够更好地勘探新解，同时由于加强精英个体周围的邻域搜索，对于提高算法解的精度亦有帮助，所以针对种群的精英个体执行反向学习策略。

为了提高运算速度，设定一个概率p，产生以随机数r=random（），当r小于p时执行精英反向搜索机制，否则执行主体遗传算法。

3.5 自适应变异机制

为了更好地保护已求得的优秀解不被丢失，需要引入一种自适应变异算子。同时，为了使算法能够较好地搜索优秀个体周围较小的邻域，而对于适应度较差的个体，则搜索其较大的邻域，特引入自适应变异率，其计算方法见公式7。该机制的变异概率能够根据解的质量自适应地调整搜索区域，从而比较明显地改善算法的搜索能力。

算法2 自适应算子

Step1. 保存种群内每一个个体的适应度值。

Step2. 计算种群的适应度总和，同时将最大的适应度值保存。

Step3. 求解平均适应度值并保存到average中。

Step4. 群体内的个体执行公式7的变异机制。

算法3 改进的反向学习遗传算法（IOBLGA[1]）

Begin

初始化群體p（t）；

while（停机不满足） do

if rand（0，1）

执行精英反向学习机制；

else

执行自适应遗传算法；

endif

endwhile

end

4 仿真实验

为了验证算法的有效性，应用JAVA实现该算法，并将标准遗传算法（GA）与改进遗传算法（IOBLGA）进行图像边缘检测比较。两个算法设定的种群规模、交叉概率、迭代次数均相同。设种群规模为40，交叉概率px=0.5，种群迭代次数30，两个算法均单独运行30次，取各自的最佳效果图。

将标准遗传算法和改进遗传算法分别作用于同一幅图，分别获得边缘检测效果图。对比两个图的求解效果，发现改进遗传算法在求解过程中所获得的Sobel算子，较标准遗传算法获得的Sobel算子更逼近最优值。一些应用标准遗传算法未检测出的边缘在改进算法中有了比较好的呈现效果。

为了进一步对比两个算法进化过程中适应度的变化情况，我们绘制了图5来描述两个算法的最佳个体变化趋势。在图5中，纵轴代表灰度图像的灰度值范围，横轴代表运行的次数，以此来对比标准遗传算法和改进遗传算法运行结束后，所获得图片的灰度阈值趋近最优解的变化趋势。从图5可以看出，在标准遗传算法边缘检测中加入精英反向学习和自适应变异机制后，遗传算法所获得最优解的次数有了明显的提高，同时，求得的图像阈值的波动幅度有所降低。可见改进遗传算法在处理图像边缘检测中比标准遗传算法有了一定程度的提高。

表1展示了不同交叉率和不同变异方式下，标准遗传算法与改进遗传算法所获得最优解个数。从表中数据可以看出，在相同情况下，改进后的遗传算法所获得最优解个数高于标准遗传算法。

通过实验中多方面的对比，可以看到，改进后的遗传算法在求解图像边缘检测问题时，有了更强的寻优能力，处理图像的效果得到了一定程度的提高。

5 结束语

本文针对Sobel算子寻优的困难性提出了应用遗传算法进行图像边缘检测的方案。为了更好地提高遗传算法的全局收敛性和求解精度，在遗传算法中加入了自适应机制和精英反向学习机制，从而提高了寻找最优解的效率，也在一定程度上遏制了算法的早熟现象和标准遗传算法解精度较低的弱点。通过仿真实验中图像边缘检测效果及数据对比，我们验证出改进的遗传算法所检测出的图像边缘更加清晰，且算法的稳定性和求解精度也较传统遗传算法有了一定的提高。进一步的研究将从理论上分析该算法的收敛必然性和求解精度，并推广该算法用于解决其他相关问题，同时针对IOBLGA算法的优缺点进行多种群体智能算法的混合性研究，做到优势互补。

参考文献（References）：

[1] 王培崇.群体智能算法及其应用[M].电子工业出版社，2015.

[2] 汪慎文，丁立新.应用精英反向学习策略的混合差分演化算法[J].武汉大学学报（理学版），2013.59（2）：111-116

[3] 李敏强，寇纪淞，林丹.遗传算法的基本理论与应用[M].科学出版社，2002.

[4] 周新宇，吴志健，王晖.一种精英反向学习的差分演算算法[J].小型微型计算机系统，2013.31（10）：2129-2134

[5] 贺毅朝，王熙照，寇应展.一种具有混合编码的二进制差分演化算法[J].计算机研究与发展，2007.44（9）：1476-1484

[6] 马永杰，马义德，蒋兆远.一种快速遗传算法及其收敛性[J].系统工程与电子技术，2009.31（3）：714-718

[7] 巩敦卫，郝国生，严玉若.交互式遗传算法基于用户认知不确定性的定向变异[J].控制与决策，2010.25（1）：74-78