阴亚芳, 张婧琪, 廖延娜

(1西安邮电大学 电子工程学院, 陕西 西安 710121； 2.西安邮电大学 理学院, 陕西 西安 710121)

小生境遗传算法在多车牌定位中的应用

阴亚芳1, 张婧琪1, 廖延娜2

(1西安邮电大学 电子工程学院, 陕西 西安 710121； 2.西安邮电大学 理学院, 陕西 西安 710121)

为了在复杂背景下对多车牌进行准确定位，提出一种基于小生境遗传算法的多车牌定位方法。利用一组一维滤波器对图像平滑处理得到图像的特征向量，建立小生境遗传算法模型，设计适应度函数，并确定小生境算法机制，实现多车牌定位。仿真实验表明，基于小生境遗传算法的多车牌定位方法能够准确地对多车牌进行定位，平均定位率达到90%以上。

车牌定位；小生境；遗传算法

车牌识别系统在智能交通系统中的应用十分广泛，随着社会的不断进步，单辆车牌照识别已经远远不能满足人们的需求，多车牌识别系统应运而生。一个完整的车牌识别系统主要由车牌定位、字符分割和字符识别三个模块组成，其中车牌定位是进行字符分割和识别的先决条件和关键步骤[1]。目前，有效的单车牌定位方法主要有灰度特性法[2]、hough变换法[3]、小波变换法[4]、数学形态学法[5]、纹理特征分析法[6]、神经网络法[7]和彩色分割法和遗传算法[8]等。但是，以上方法均无法对同一张图片中的多个车牌进行同时定位。

遗传算法(Genetic Algorithm, GA)是是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法[9]。小生境(Niche)是指自然界中生物根据物种特性的差异而群居、繁衍呈现出的一种特定的生存环境。

在小生境中，当种群中个体大量繁殖，为争夺有限的生存资源，群体中个体之间的竞争压力必然加剧，导致个体寿命和出生率降低[10]。针对这种现象，基于罚函数的排挤机制的小生境遗传算法[11]被提出，该算法先比较种群中两两个体之间的距离，若该距离在预先指定的距离L之内，则再比较两者之间的适应度大小，并对适应度较小的个体施加一个较强的罚函数，使其适应度极大降低，增加其被淘汰的概率，这样，在距离L之内只存在一个优良的个体，既维护了种群的多样性，又使得各个体之间保持一定的距离。

在GA中引入小生境技术，不但保留了GA鲁棒性强、并行性和高效性的优点，还可避免进化后期适应度高的个体大量繁殖并充斥整个解空间，导致算法停止在局部最优解上的问题，从而找到更多最优个体[12]。小生境遗传算法可以改进遗传算法等最优值找不全的问题，应用在多车牌识别领域中。

本文拟提出一种基于小生境遗传算法的多车牌定位方法,在遗传算法的基础上，添加小生境技术以保持种群的多样性，从而完成同时对多辆车车牌进行定位。

1 车牌特征提取

为了便于车辆牌照特征的提取，需要将采集到的车牌RGB图像进行灰度化和二值化处理，得到Ibin(x,y)。由于车牌字符主要呈现在水平方向，在小范围区域内呈现规律的、有一定疏密度的、黑白间隔的纹理分布,因此，通过多尺度滤波技术,采用一组反映不同疏密度的高斯差分滤波器,对图像平滑滤波来获取图像纹理特征向量[13]。

分别采用3,4,5个像素点对图像进行遍历,得到滤波模板

L1=[-1,0,1], L2=[-1,-1,1,1]/2,L3=[-1,-1,0,1,1]/2。

(1)

令车牌二值图像Ibin(x,y)分别与上述滤波模板卷积,进行车牌纹理特征提取,得滤波后的灰度图像

Ii(x,y)=Ibin(x,y)*Li(i=1,2,3),

(2)

根据车牌区域纹理特征空间分布的均匀性,使用滤波后图像的标准偏差来表示其纹理特征值,即

(3)

其中图片大小为m×n，滤波后图像的平均能量

(4)

由此可得车牌区域的特征描述向量

T=[σ1,σ2,σ3]。

(5)

2 车牌定位

2.1 适应度函数

基本遗传算法的适应度函数通常由当前区域的特征与模板值的距离来决定，但在实际中，由于光线和天气等因素的影响，车牌的特征往往会产生较大变化，若车牌模板选择的不好则会影响定位的结果。由于在实际中无法使用一个模板来表示所有车牌的特征，故需要重新设计一种车牌适应度函数。

根据车牌区域的纹理特征，由各种字符组成车牌与其他位置相比，纹理变化较剧烈，可以认为区域内特征向量的值越大，则越有可能是车牌区域，故将适应度设置为车牌三个纹理特征值之和，即

F=σ1+σ2+σ3。

2.2 个体的编码与相似度判断

由于实际中对车牌进行拍照的位置是固定的，因此所得车牌的大小只在很小一个范围内变化。采用二进制数对个体进行编码，分别用10位和9位二进制数表示车牌左上角的坐标x和y、用4位二进制数表示车牌的长l与宽w，其中

l∈[90, 95],w∈[35, 40]。

在排挤机制中需要判断个体的相似性。两个个体的相似程度传统上定义为对应二进制串之间的Hamming距离[14]。但是在判断车牌区域的相似性时，具有较小Hamming距离的两个车牌编码有可能差异度很大。考虑到传统Hamming距离在度量车牌相似性时的缺陷，需要重新设计车牌相似性度量方法。

根据实际情况，若两个车牌区域有重合部分，则两车牌区域是相似的，即若两车牌区域满足

|x1-x2|+|y1-y2|

(7)

则两车牌相似。

2.3 车牌定位的实现步骤

采用排挤机制的小生境遗传算法多车牌定位算法流程如图1所示。

(1) 选择操作。采用轮盘赌的方式对种群进行选择操作，适应度较高的个体被遗传到下一代群体中的概率较大，适应度较低的个体被遗传到下一代群体中的概率较小，从而达到优化种群的目的。

(2) 交叉操作。采用单点交叉的方式，即在父代染色体中随机设置一个交叉点，然后在该点互换两个配对个体的部分染色体。

(3) 变异操作。采用基本变异算子，在编码中随机选取1个或多个基因位置，并根据变异概率对这些位置的基因取反。

图1 算法流程

3 仿真结果

取种群大小M为200，交叉概率为0.9，变异概率为0.1，最大迭代次数为20。在排挤机制中，每次记录适应度最好的前5个个体，即N=5。

迭代20次后得到车牌区域的适应度变化如图2所示，其中位于上方的适应度曲线为图3中右侧车的车牌，位于下方的适应度曲线为图3中左侧车的车牌。

图2 两辆车图片适应度函数

图3 两辆车定位结果

由图2可见，不同车牌的适应度是有很大差别的，不能利用统一的适应度模板进行描述。例如若训练出的车牌模板值为[0.310，0.315，0.320]，而图3中右侧车牌特征值为[0.320, 0.324, 0.330],左侧车牌特征值为[0.300, 0.302, 0.306]。当使用传统基于模板距离的适应度函数时，两个车牌的适应度都大约为0.03，适应度非常相似，因此无法区分出多个车牌。若采用新的适应度函数，则得到如图2中所示的适应度，能够保证多个车牌的适应度有显著的差异。

对三辆车的识别结果如图4和图5所示。

图4 两辆车图片适应度函数

图5 三辆车定位结果

分别采用100幅两辆车图片和100幅三辆车图片作为测试样本，重复运行20次进行测试，统计结果如表1所示。

表1 多车牌定位系统定位结果

由于小生境遗传算法具有随机性，仿真存在一些定位不成功的现象，如车牌定位不完全(包括车牌数辆不完全和车牌区域不完全)和车牌定位错误等，所以测试次数取为20次，并利用了平均的方法计算系统的平均定位率。

4 结束语

给出了一种基于小生境遗传算法的多车牌定位方法，通过改进小生境遗传算法的适应度函数，得出一种判断车牌相似度的判定准则。相关实验结果表明，新方法可以克服传统遗传算法在进行多车牌定位时最优值寻找不全的问题，能够有效定位出图片中的多个车牌。

[1] 万燕，徐勤燕，黄蒙蒙. 复杂背景中基于纹理和颜色的车牌定位研究[J]. 计算机应用与软件，2013,30(10)：259-316.

[2] 刘濛，吴成东，樊玉泉，等. 复杂背景图像中的车牌定位算法[J]. 中国图象图形学报，2010,15(9)：1357-1362.

[3] 林俊，杨峰，林凯.Hough 变换与先验知识在车牌定位中的新应用[J].计算机与数字工程，2009，37(8)：138-140.

[4] Wang Yuhrau, Lin Wehung, Horng Shijinn. A sliding window technique for efficient license plate localization based on discrete wavelet transform[J]. Expert Systems with Applications, 2011,38:3142-3146.

[5] 李伟，朱伟良，孔祥杰,等.一种新型的基于数学形态学和颜色特征车牌定位算法[J].科技通报，2009,25 (2)：214-219.

[6] 周铁平，王庆. 一种新的汽车牌照快速定位方法[J]. 微计算机应用，2007,28(4)：343-348.

[7] 张兴会，杜升之，陈增强,等. 基于神经网络的车牌照自动识别系统[J]. 仪器仪表学报,2001,22(3)：209-230.

[8] 代悦宁，朱国晖. 基于遗传算法的LTE下行系统资源分配算法[J]. 西安邮电大学学报，2014,19(1)：50-54.

[9] 马永杰，云文霞. 遗传算法研究进展[J].计算机应用研究，2012,29(4)：1201-1210.

[10] 刘延飞. 基于小生境遗传算法的数学符号识别方法的研究[D].长春：吉林大学，2008:32-35.

[11] 谢凯. 排挤小生境遗传算法的研究与应用[M].西安:西安交通大学出版社,2002:75.

[12] 朱筱蓉，张兴华. 基于小生境遗传算法的多峰函数全局优化研究[J]. 南京工业大学学报，2006,28(3):39-43.

[13] Manjunath B S, Ma W Y. Texture Features for Browsing and Retrieval of Image Data[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1996,18(8):837-842.

[14] 刘楠. 改进的小生境遗传算法在多目标车间调度中的应用研究[D]. 大连：大连交通大学，2009:11-12.

[责任编辑:瑞金]

License plate location based on niche genetic algorithm

YIN Yafang1, ZHANG Jingqi1， LIAO Yanna2

(1.School of Electronic Engineering, Xi’an University of posts and Telecommunications, Xi’an 710121, China;2.School of Science, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

In order to locate multiple license plates in complex background accurately，a multiple license plate location method based on niche genetic algorithm is proposed. Firstly, the feature vector of the image is obtained by a different set of uni-dimensional filter. Secondly, a niche genetic algorithm model is established, a fitness function is designed, and a mechanism of niche algorithm is determined. Finally, the license plate location is achieved. Simulation results show that this license plate location method based on niche genetic algorithm can locate the license plate accurately. The average localization rate is over 90%.

multiple license plate location, niche, genetic algorithm

2014-09-22

陕西省教育厅科学研究计划资助项目(12JK0559)

阴亚芳(1966-)，女，博士，教授，从事数字信号处理及光器件研究。E-mail: yinyfxian@163.com 张婧琪(1989-)，女，硕士研究生，研究方向为图形图像与视频处理。E-mail:Zhangjqxian@163.com

10.13682/j.issn.2095-6533.2015.01.008

TP391.4

A

2095-6533(2015)01-0040-04