基于免疫遗传算法的道路交通标志图像分割

汪宏海



基于免疫遗传算法的道路交通标志图像分割

汪宏海

（浙江旅游职业学院，浙江，杭州 311231）

针对道路交通标志图像分割的问题，提出了一种基于免疫遗传算法的实现方法。该算法利用免疫遗传机制，将图像的最佳阈值作为要求的解，设计了适合问题求解的抗体编码方式、克隆算子和免疫选择算子。仿真实验结果表明，所提算法能够有效地求得道路交通标志问题的最佳阈值。通过与传统遗传算法、改进遗传算法进行对比实验，更好地说明了本算法能够对图像分割得到较为满意的结果。

免疫遗传算法；图像分割；交通标志；阈值；收敛性

1　概述

随着物联网时代智慧城市的快速建设，智能交通系统正逐步改善着交通运输质量。道路与交通标志图像的分析和处理是智能交通应用研究领域中重要组成部分，也是所面临的图形识别难题之一。图像分割是图像分析处理的关键技术之一，其目的是将图像中的目标和背景分离开来，为后续的分类、识别和检索提供依据[1]。如何从图像中快速、准确地分割出道路交通标志就变得十分重要[1]。

传统的图像分割方法包括阈值法、边缘检测法、区域跟踪法等。其中，阈值分割方法因其实现简单、计算量小、性能较稳定而成为图像分割中最基本和应用最广泛的分割技术[1]。它特别适用于目标和背景占据不同灰度级范围的图像，不仅极大地压缩了数据量，而且也大大地简化了分析和处理步骤。但是，不同的阈值会直接导致图像分割的不同结果，因此寻找一个最佳阈值已经成为图像分割的关键点。由于此问题经过建模为NP问题，不同的研究者提出了不同的智能算法进行求解。文献[4]利用遗传算法来选取阈值，文献[5]对遗传算法进行了改进。以上方法取得了较好的结果，但遗传算法本身容易陷入局部最优。免疫遗传算法在遗传算法的基础上引入了浓度调节机制。进行选择操作时，遗传算法只利用适应度指标对个体进行评价，容易导致种群进化单一。而免疫遗传算法的选择策略变为：适应度越高，浓度越小，个体复制的概率越大；适应度越低，浓度越大，个体复制的概率越小。这样就可以有效地调节选择压力，防止种群退化，并在局部和全局搜索上表现出不俗的能力，更适合用来求解最佳阈值[6-7]。本文通过应用免疫遗传算法，为道路交通标志图像处理提供有力的技术，求得图像的最佳阈值，达到较好的效果。通过实验结果分析，本文算法优于其他遗传算法。

2 道路交通标志图像

道路与交通标志的图像分割就是根据图像中目标与背景的先验知识，对图像中的目标、背景精细标记、定位，然后将目标从背景或者伪目标中分离开来。

道路与交通标志中，物体与背景的对比较为明显，使用阈值分割技术效果就很好。对灰度图像的取阈值分割就是先确定一个处于图像灰度取值范围之中的灰度阈值，然后将图像中的各个像素的灰度值与这个阈值相比较。所有灰度值大于或者等于此阈值的像素都被判为属于物体；所有灰度值小于该阈值的像素被排除在物体之外[8]。

确定阈值是分割的关键。能确定一个合适的阈值，就可以方便地将图像分割开来。

设(,)是二维数字图像的平面坐标，道路交通标志的图像灰度级的取值范围定义：G={0,1,2,…,-1}（习惯上0代表最暗的像素点，-1代表最亮的像素点），位于坐标(,)上的像素点的灰度级表示为(,)。设∈为分割阈值，B={0,1}代表一个二值灰度级，并且0,1=G，于是函数(,)在阈值上的分割结果可以表示为两类：

即阈值将图像分为两类：

0={0,1,2,…,}

1={+1,+2,…,-1},

0与1分别代表目标与背景。

图像灰度级的概率分布为：

式中n表示的是灰度的像素数；表示的是图像的像素数；P表示的是灰度级出现的概率。

C0与C1出现的概率分别为:

C0与C1的均值分别为：

使σ2取最大值时的t就是最佳阈值：

传统的方法例如穷尽法需要遍历灰度范围内的所有的图像像素，然后再计算方差，计算量巨大，很显然这样的算法效率十分低下，并且结果也不够优秀。面对这样的问题，智能优化算法更适合用来求解，将会有快速高效的性能。

3 免疫遗传算法实现图像分割

3.1 免疫遗传算法

免疫算法是人工智能领域重要的应用之一，它是基于生物免疫系统基本机制，模仿了人体的免疫系统，达到解决问题的效果。具有动态性、自适应、鲁棒性强等优点，已经广泛应用在组合优化、配置寻优、人工智能等领域。免疫遗传算法是免疫算法中的一种[9]。

免疫遗传算法是针对遗传算法控制收敛不足、记忆能力差、优势遗传不够明显的问题而提出的一种更加智能的免疫算法。它的主要目的是防止种群的退化，有效地调节选择压力，避免进化单一，使得种群能够更好地保持多样性。免疫遗传算法不仅继承了遗传算法的健壮性和并行计算的优良特点，更主要的是具有免疫算法的记忆功能、学习性以及自适应性的优点，在工程和研究领域有相当大的研究价值和应用潜力[10-11]。

3.2 抗体编码

免疫算法中，抗体表示的是对应要求解问题的解，因此抗体编码就是免疫问题求解的关键技术之一，它主要是用来完成待求解问题的表示。在道路与交通标志的图像分割中，图像的灰度级在0~255之间，数值范围大小刚好是二进制数的指数值，因此单个抗体编码采用8位二进制数。假设某个抗体的编码为a= {a1, a2,…,a8}，把二进制数转为十进制数值的大小就是单个抗体的值，它表示的是某个阈值。

3.3 算法的实现

道路、交通标志图像分割的过程就是将道路、交通标志中的背景与目标分离开来[12-13]。其关键在于求解找到一个最佳阈值，使得图像的σ2最大，因此算法的目标函数为：

maxF=σ2

利用免疫遗传算法实现道路交通标志图像分割的原理流程图如图1所示：

图1 算法流程图

基于免疫遗传算法对道路交通标志图像分割求解最佳阈值的具体步骤如下：

步骤1 种群初始化。采用随机的方式产生初始抗体种群0，设置种群数=10，作为最初的候选解集。给定种群最大迭代次数gmax=50。

步骤2 计算抗体适应度。对当前群体Ak中的每一个抗体都进行适应度计算，适应度值越高的说明图像分割的效果越好，越接近最佳。

步骤3 记忆单元更新。对适应度高的抗体进行记忆存储，形成记忆种群M。

步骤4 抗体的抑制和促进。在免疫遗传算法中通过使用浓度调节机制进行个体复制，避免群体进化单一，保持种群的多样性，最后得到候选种群B。

抗体a的浓度的计算公式为：

更详细的介绍可参考文献[9]。

步骤5 交叉操作。对候选种群B执行交叉操作T形成临时群体C。

步骤6 变异操作。对种群C执行变异操作T形成新的临时群体D。

步骤7 免疫选择。对种群D注射免疫疫苗M后，对所有的抗体执行免疫选择，选择出前个个体作为优势抗体，生成下一代群体A，即最佳阈值候选解集。

步骤8 终止条件判断。当满足终止条件的时候则停止，输出适应度值最高的抗体，它所表示的是最佳阈值，得到图像分割结果；否则转到步骤2。

4 实验结果分析

为了验证本文算法对道路交通标志图像分割的性能，实验选取了道路和交通标志两种图像作为原始图像，分别使用免疫遗传算法、传统的遗传算法[4]以及混合遗传算法对图像进行分割[5]。其中实验参数中，设定种群规模为15，交叉概率为0.4，变异概率为0.1，最大迭代数为50。通过运行程序，最终得到的分割结果。

图2 道路图像分割结果

图2是道路图像分割的结果。其中，图2(a)是道路图像原始图像，图2(b)是本文算法的图像分割结果，图2(c)是传统遗传算法所得到的图像分割结果，图2(d)是改进遗传算法所得到的图像分割结果。从图中可以清晰地看出，对道路图像的分割，传统的遗传算法得到的图像边缘比较模糊，处理结果差；改进的遗传算法图像结果边缘比较清晰，能够正确的分割出道路的轮廓，但是内部没有分割；本文所用的免疫遗传算法得到的图像边缘清晰，车道线也明显，图像处理的结果较好。

图3 交通标志分割结果

图3是交通标志的分割结果。其中，图3(a)是原始图像，图3(b)、图2(c)和图2(d)分别是本文算法、传统遗传算法以及混合遗传算法所得到的图像分割结果。从图中可以直接的看出，传统遗传算法得到的结果中轮廓清晰，但是边缘依然比较模糊；改进遗传算法分割图像边缘清晰，但其中的立杆不明显；本文算法得到的图像结果轮廓清晰，立杆明显，处理效果较好。

对道路图像利用上面三种算法分别进行10次独立实验，给出10次独立运行结果，对结果的均值和方差进行比较，采用适应度函数评价次数来评价算法的运算量。比较结果如表1所示。

表1 阈值分割10次结果比较

由以上结果可以看出，遗传算法每次得到的最优阈值波动较大，免疫遗传算法相比较其他两种算法较为稳定。并且在得到解的同时，免疫遗传算法评价次数最少，说明计算量较小，但却可以得到较优的结果。

5 结束语

本文提出的基于免疫遗传算法求解道路交通标志图像分割的问题，把所要求的最佳阈值抗原进行求解，实验结果表明了算法的有效性。通过与多种算法所得分割图像结果进行对比可以看出，免疫遗传算法能够得到较好的图像分割最优阈值，对图像的处理效果较好。但是面对道路交通状况较为复杂的情况会对图像分割产生影响，这将是下一步继续深入研究的内容。

[1] 赵全华,高郡,赵雪梅. 结合KL距离与图像域分块的SAR图像分割[J].控制与决策,2017,43(11):1126-1130.

[2] 尹晓叶,李俊吉. 基于增强布谷鸟搜索的图像分割算法[J].控制工程,2017,32(10):116-120.

[3] Ma M, Liang J, Guo M, et al. SAR image segmentation based on Artificial Bee Colony algorithm[J].Applied Soft Computing, 2011, 11(8):5205-5214.

[4] 李婷,杜永贵. 基于云遗传算法的阈值图像分割法 微电子学与计算机[J]. 2015,12(5):389-396.

[5] 贺建峰,符增,易三莉. 基于遗传算法的灰度-梯度熵多阈值图像分割[J].计算机科学与探索,2015, 6(11):93-95.

[6] Gong M, Zhang L, Ma J, et al. Community detection in dynamic social networks based on multi-objective immune algorithm[J]. Journal of Computer Science and Technology. 2012, 27(3) :455-467.

[7] Mohanta R K, Sethi B. A Review of Genetic Algorithm application for Image Segmentation[J]. International Journal of Computer Technology and Applications. 2012, 03(02).

[8] 乔阳. 基于改进遗传算法的图像分割方法[D]. 成都：电子科技大学. 2013.

[9] Gong M, Chen X, Ma L, et al. Identification of multi-resolution network structures with multi- objective immune algorithm[J]. Soft Computing. 2013, 13(4): 1705-1717.

[10] 张向荣,骞晓雪,焦李成. 基于免疫谱聚类的图像分割[J].软件学报. 2010, 21(9):2196-2205.

[11] 林正春,王知衍,张艳青. 最优进化图像阈值分割算法[J].计算机辅助设计与图形学学报,2013,22(7):1201-1206.

ROAD TRAFFIC SIGN IMAGE SEGMENTATION BASED ON IMMUNE GENETIC ALGORITHM

WANG Hong-hai

（Tourism College of Zhejiang, Hangzhou, Zhejiang 311231, China）

To solve the problem in road traffic sign image segmentation, a image segmentation based on immune genetic algorithm was proposed. The algorithm used immune genetic mechanism and took the optimal threshold value of the image as the requirements of the solution. Antibody coding, cloning operator and immune selection operator that are suitable for solving the problem were design. The simulation results show that the proposed algorithm can effectively get the optimal threshold in the problem of road traffic signs. By comparing with the traditional genetic algorithm and the improved genetic algorithm, it better illustrates that the algorithm can obtain a satisfactory result for image segmentation.

immune genetic algorithm; image segmentation; road; traffic sign; threshold value; convergence

1674-8085(2018)01-0060-05

TP301.6

A

10.3969/j.issn.1674-8085.2018.01.013

2017-08-11；

2017-11-05

汪宏海(1977-)，男，江西樟树人，副教授，主要从事图像处理、智能算法等方面的研究(E-Mail:redsea54@163.com).