基于改进遗传算法的图像边缘检测

孙海明，韩国强，郑小秋

（1.湖北汽车工业学院机械工程学院，湖北十堰 442002；2.湖北中程科技产业技术研究院有限公司，湖北 十堰 442002）

图像中灰度值跳跃的像素集合形成图像的边缘[1]。基于梯度边缘检测算子运用滤波模板与图像进行卷积常见的算子有Roberts、Sobel、Prewitt，拉普拉斯算子和坎尼算子[2-5]。上述算子在定位精度及适应性上存在局限性。因此近年来许多功能强大的智能优化算法被应用到边缘检测中[6]。遗传算法因其优秀的寻优能力被广泛讨论[7-9]。改进的天牛须算法具有良好的搜索能力，与其他算法结合克服了传统算法陷入局部最优的困境[10]，文献[7-9]中的算法与传统算法相比在运行效率和准确性上的确有所提高，但算法具有一定的适应性和针对性。该文提出了一种改进的遗传算法，将梯度变化率的最大方向作为改进遗传算法的目标函数，将改进后的天牛须算法融入传统的遗传算法，在处理图像时考虑整幅图像的最优，不再局限于领域特性的最优，运用改进后的算法处理不同图像时均能得到良好的边缘结果。

1 图像梯度

图像中像素点灰度突变的位置是边缘所在位置，检测图像边缘的一种常用方法是对图像中的灰度进行一阶微分，将微分后得到的数定义为梯度[11]。设图像中灰度函数为f(x,y)，点(x,y)处对应的梯度矢量为：

梯度的两个重要性质是：

1）梯度的方向，与函数f(x,y)的最大变化率方向一致；

2）梯度的幅值，由式（2）表示：

梯度在θ方向的变化率为：

变化率最大方向的变化幅度为:

由梯度幅值计算公式可知，边缘的方向不影响梯度的幅值。梯度相当于函数的斜率，直观表述了函数变化的大小和方向，连续函数中可通过微分求解某点的斜率，而图像是像素值组成的离散矩阵，不连续的距离求解可用差分代替微分进行计算，避免了复杂的平方、开方运算，梯度幅值可表示为：

对灰度图进行边缘检测首先要确定其分割阈值，在应用遗传算法进行图像边缘检测时，挑选出最优阈值染色体，也需要建立相应的评价指标。按照该思路并通过分析图像梯度的性质，在进行适应度函数设计时，依据灰度图像的特性，在图像灰度突变的位置把一幅图像分解出边缘轮廓。将式（4）作为目标函数，梯度幅值大于某一阈值则认为该点(x,y)为边缘点，在图像梯度变化率最大的方向进行分割阈值。

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

2.1 基于标准遗传算法的边缘检测

1）基因编码。由于图像中每个像素的灰度值在0～255 之间，因此选择二进制编码方法，将每条染色体编码为8 位二进制码。

2）初始化种群和适应度。样本的数量由像素的数量决定。样本总数被分成n个总体。每个种群包含m个样本，这些样本被再生到数组R[1,2,…,n] 和数组B[1,2,…,n] 。在数组R中放入n个种群的优化结果，并将平均适应度储存在数组B中。

3）确定染色体。染色体结构是遗传算法的核心部分。对于染色体有以下操作：

①个体选择。该文以像素为探讨目标，采用精英选择策略对个体进行更新。将当前种群中适应度最好的个体随机替换为下一代种群中适应度最差的相同数目的个体。对于图像的边缘检测，则是将遗传算法的平均适应度，即对数组B[1,…,n]所代表的样本种群之间进行特定的选拔使用。

②染色体交叉。交叉操作主要涉及群体中单个染色体上的基因片段的交叉交换，从而产生新的个体。由于像素具有二维信息，该文采用两点交点法进行交点运算。如果R[1,2,…,n]和R[j,…,n] 随机选取在一起，在x处(i≥1,j≤n,1 ≤x≤n-1)，R[i,x+1,…,n]和R[j,x+1,…,n] 互相交换相应的部件，染色体交叉过程如图1 所示。

图1 染色体交叉过程

③遗传变异。该基因通过均匀突变随机改变。在第一轮结束前，用少量随机产生的具有低概率事件的新个体替换随机选择的个体。然后更新数组R[i,…,n] 及数组B[i,…,m]，并开始运行下一代，直到获得满意的结果[12]。

2.2 基于改进遗传算法的图像边缘检测算法

遗传算法在处理图像去噪问题时，只根据个体的适应度值选择个体，可以取得较好的效果。然而，对于复杂背景下的多模态目标边界提取问题，由于缺乏考虑种群的多样性，遗传算法容易过早收敛，陷入局部最优解，导致目标边缘提取不完全或不准确。天牛须搜索优化算法是一种基于仿生原理的智能算法[13]，受到天牛觅食行为的启发，根据天牛左右触手接收到的不同食物气味的强弱不同来确定搜索方向，确定方向后，跳转到下一个位置，继续搜索，直到找到全局气味最大值点，即目标函数的最优解。BAS 搜索算法在寻优过程中只需要一个个体就可以实现全方位的搜索，不受函数形式和梯度信息的制约，在多目标优化中，各维度之间不相互干扰，降低了优化的复杂度。相比于其他优化算法不易陷入局部最优解、适用性强、过程简单、运算量小，能够更快寻找到目标函数的全局最优解。

考虑到固定步长的BAS算法每次搜索距离不变，而图像中的梯度幅值一直在变化，搜索时可能遗漏掉重要的像素点，导致后期搜索误差不断放大，尤其弱边缘和复杂边缘会被忽略，影响边缘检测的精度。

为了解决上述问题，该文结合了一种改进的BAS 算法[14-16]。该算法通过改变步长参数来改变搜索步长，首先用较大的步长来确定搜索方向的近似范围,再缩小参数进行精细搜索，最终找出最优解。这种变步长的办法不仅提高了边缘信息的精度还提高了运算的速度。

算法中涉及到的主要公式参数包含：随机初始解x=rands(S,1)，x为(S,1)内的随机初始值，问题维度S，天牛一次移动步长l，变步长参数E，参数衰变因子t随迭代次数的增长而呈线性递减t∈(0,1)，天牛两须间距离d0，迭代次数n。

天牛须朝向的随机变量为：

天牛左须坐标表达式为：

天牛右须坐标表达式为:

计算天牛须接收的气味强度（即函数适应度值）为：

采用改进的变步长法计算天牛下一步要走的位置为：

终止条件为判别梯度变化率方向和天牛位置坐标与初始位置时相比差值是否满足在设定范围内，如果是，则终止计算；如果没有，则继续循环。图像像素的坐标值为迭代结束后的适应度函数值，满足目标函数式（4）的解为图像的边缘点。首先，对图像进行遗传运算。在达到预先设定的收敛条件后，将遗传算法的局部最优解转化为天牛须搜索的初始位置，然后进行天牛须搜索操作，最后显示图像的边缘信息。

算法的基本步骤如下（i表示当前迭代次数，T表示最大迭代次数，设置为100）：

1）对图像进行简单处理，为算法中各参数设定初始值；

2）对像素点灰度值进行染色体编码，由设定的种群大小随机产生初始种群；

3）由式（3）推算种群中各个体的梯度变化率，计算个体的适应度值；

4）执行选择、交叉和变异操作来产生下一代种群；

5）使用天牛须寻求指引新一代种群中参与交叉操作的父代交叉点位置发生移动，更新子代，提升种群多样性；

6）若i＜T，则i′=i+1，转步骤3），否则中止迭代；

7）算法结束，输出种群中的最优解，即检测到的图像边缘。

算法流程图如图2 所示。

3 实验结果与分析

为了验证算法的普适性，分别对像素点、lena像、汽车外形（图3）进行了实验仿真，直观地体现出改进算法性能上的提升，将两组不同的图像分别进行基于遗传算法的边缘检测和改进算法的边缘检测处理，从图像的边缘完整度来看，可以清晰地看出改进后的算法对多种形态下的图像边缘检测结果都有很好的提升效果，边缘更加完整。图3 是检测后的结果图，分别从像素和整体边缘进行对比。从图3几组对比图能清晰地看出，改进后的算法对多种形态下的图像边缘检测结果都有很好的提升效果，达到了对算法改进的目的。

图3 图像边缘检测结果

为了进一步比较两种算法在进化过程中适应性的变化，图4 中描述了两种算法在运行完成后的性能释放。从图4 可以看出，利用天牛须搜索算法引导遗传算法中交叉点位置的移动方向，改进的算法获得最优解的次数明显提高，且图像阈值的波动范围减小。由此可见，改进的遗传算法在图像边缘检测方面优于标准遗传算法。

图4 最优解趋势图

表1 显示了改进后的边缘检测算法在其迭代100 次后相对于改进之前在不同交叉率下的最优解和收敛时间。数据显示，改进遗传算法得到的最优解数量要高于标准遗传算法，收敛时间也有所提高。

表1 改进前后迭代100次获得最优解个数对比

通过多次实验对不同的图片进行边缘检测且分析实验数据，可以看出改进后的遗传算法在进行图像边缘检测时寻优能力得到增强，且处理不同的图像时均有良好的效果。

4 结论

针对传统梯度算子对图像边缘检测满意度不高的问题，提出将遗传算法应用于图像边缘检测，将梯度变化率作为目标函数进行求解，且针对遗传算法应用在复杂图像背景时容易出现局部最优解，提出了应用改进的天牛须搜索算法优化遗传算法。实验表明，在不同的图像场景下均能获得更加连续、清晰的边缘。与已有的图像边缘检测算法相比，改进后的算法不仅减少了收敛时间，且改进算法应用在同一图片边缘检测时，获得最优解个数的次数显著提高，使边缘准确性得到了提高，验证了该算法具有较高的可行性和鲁棒性。