基于遗传算法的二维QR码图像识别

1、第26卷第4期2005年12月大连铁道学院学报JOURNAL OF DAL I A N RA I L WAY I N STI T UTE Vol .26No .4Dec .2005文章编号:100021670(20050420047205基于遗传算法的二维QR 码图像识别谷晓琳,黄明,戚海英(大连交通大学电气信息学院,辽宁大连1160283摘要:基元识别是二维码图像识别中的一个关键问题,提出了基于遗传算法的QR 码识别方法.首先建立QR 码待识别模式模型,据此进行遗传算法,通过实例进行图像识别.该方法抓住了QR 码基元的重要特征,利用改进遗传算法,可以提高QR 码图像的识别效率.关键词:遗传算

2、法;二维码;QR 码;图像识别中图分类号:TP391.41文献标识码:A22D i m en si ona l Bar Code Recogn iti on Ba sed on Geneti c A lgor ithm sG U Xiao 2lin,HUANG M ing,Q I Hai 2yin(School of Electric &I nf or mati on,Dalian J iaot ong University,Dalian 116028,China Abstract:Funda mental recogniti on is a main p r oble m in th

3、e 22D i m ensi onal bar codes .A QR Code identify p r oble m based on genetic algorithm s is p r oposed by the p r ocess of the esfablishment of QR Code pattern recogniti on model,operati on of G A and i m age recogniti on .This method gras p s the i m portant characteristic of the QR Code,and i m p

4、 r ove the efficiency of QR Code recogniti on greatly .Key words:genetic algorithm s;22di m ensi onal bar codes;QR code;i m age identifyQR 码(Quick Res ponse Code 是由日本Dens o 公司于1994年9月研制的一种矩阵二维码符号,它除具有一维条码及其它二维条码所具有的信息容量大、可靠性高、可表示汉字及图像多种文字信息、保密防伪性强等优点外还具有超高速响应、全方位识读、可离线应用的便携式数据库、能够有效地表示数字字母、汉字、图像等特点1

5、,2.QR Code 码的尺寸小于相同密度的P DF417条码,专有的汉字模式更加图1QR 码的例子图2QR 码的构造适合我国应用.图1就是一个QR Code 码的例子.目前,QR 码的识别多是使用扫描器,其应用就被很大程度地限制于硬件.现在数码拍摄设备正在逐渐普及,数码相机、摄像头随处可见,如果使用这样的通用设备拍摄包含QR 码的图像,再通过软件对图像进行识别,就能够让QR 码的特点得到更多的发挥和应用.问题就在软件如何进行QR 码的识别.这就归结于图像分析中的基元识别.图像分析和处理是计算机视觉中的一个热点研究领域,受到日益广泛的关注,而图像基元的识别和提取是图像分析的重要任务.通常将简单

6、的模式图形如三角形、矩形、圆等称为基元.从图象中识别和提3收稿日期:2005204220作者简介:谷晓琳(1978-,女,助教,硕士148大连铁道学院学报第26卷取基元一般采用Hough变换方法.Hough变换方法的优点是对局部缺损的不敏感性及对随机噪声的鲁棒性.缺点是空间和时间开销很高,特别是在检测多参数复杂基元时效率很低.近年来,通过代价函数全局优化来提取基元的方法如模拟退火法、遗传算法等得到了新发展.因此,本文提出了基于遗传算法的QR码图像识别,目的在于提高软件识别QR码的识别率,拓宽QR码的使用范围,降低QR码的使用门槛.1QR码识别的问题1.1QR码的构造特征一个QR码称为一个符号,

7、QR码中每一个颜色点称为模块.从版本1到版本40,符号的规格分别是21×21个模块到177×177个模块,其间每一规格在每条边增加4个模块.以版本1为例,符号的构造如图2所示,图中黑白颜色的模块是QR码的位置检测部分,其余模块是数据和校验部分.符号中左上、右上和左下角的8×8个模块是固定的,不随版本变化.1.2QR码图像的约束分析拍摄下来的QR码图像总结起来有以下几个特征:(1由于拍摄设备的不同,拍摄的图像通常情况下是宽度大于等于高度的矩形.(2拍摄的时候有人主观的参与,保证了图像的主体是QR码,并且会完全容纳QR码.(3QR码在图像中的位置不固定.(4拍摄的角度

8、和距离不同,图像中的QR码会有旋转、放大和拉伸.1.3识别QR码的主要问题QR码的识别首先要确定符号在图像中的位置,就是图像中固定部分的识别问题,然后再进行数据的读取.只要识别出检测部分,读取就不是难事.所以将符号中的检测部分整体作为一个待识别模式,对其进行识别就是要解决的主要问题.2模式识别问题的模型建立定义QR码版本为v,用于检测识别的模块数为N,则:N=6433+1+(21+43(v-1-1632(v1,40,整数(1将QR码符号的位置检测模块的集合视为一个待识别模式,一个模块视为一个点,则待识别模式的点序列P的描述为:P=p(x1,y1,p(x2,y2,p(x N,y N(2其中,(x

9、i,y i为相对于模式原点也就是QR码符号的重心(x0,y0的坐标,p(为相应的灰度值,将模式放大M倍,旋转并将模式原点移至(xc,y c,则点序列P变为Q:Q=p(x31,y31,p(x32,y32,p(x3N,y3N(3 其中x3jy3j =Mco s-sinsincosx jy j+x cy c,(j=1,2,N(4从图像中取得点序列Q中相应的灰度值,与点序列P的相应点灰度值比较,满足p(x3j,y3j=p(x j, y j(j=1,2,N的点个数计为n b,设图像中点序列与待识别模式的匹配率为R,则:R=n bN,R0,1(5R越大识别程度越高,由此QR码识别问题转化为四维空间(x c

10、,y c,M,内求匹配率R的最大值问题.这个问题适合使用遗传算法求解.第4期谷晓琳等:基于遗传算法的二维QR码图像识别493遗传算法用于识别3.1算法思想遗传算法在理论上能从概率的意义上以随机的方式寻求到问题的最优解;但实践表明,遗传算法也会出现一些不尽人意的问题,如早熟收敛、局部寻优能力差等.本文使用基于机器学习的改进遗传算法,首先将原点坐标、放大倍数和旋转角度作为一个染色体的组成部分,随机得到多个人色体作为初始种群,并判断其适应值得到部分较优解并保存,从较优解中抽取部分个体作为下一代初始种群的一部分,其余个体随机产生,这样既保证了初始种群的多样化,同时也使初始种群保持了较高的平均适值,使得

11、优化迭代次数大大减小.引入了静态繁殖理论,在进行交叉和变异操作后,将新生成的子代染色体适值和父代进行比较,如果子代染色体适值高于父代,则利用子代染色体替代父代染色体,否则保留父代染色体,保留父代中的优异个体,防止进化操作对优异个体性状的破坏,从而有效地防止了较优解的丢失.当得到最优解或者达到设定的进化代数时迭代结束.3.2算法的描述3.2.1编码策略对于上述四维空间(xc,y c,M,求匹配率R的最大值问题,定义遗传算法的个体I k(k=1,2,3,的基因型Gk为5:G k=(x ck,y ck,M k,k(6其中,xck 、yck、Mk和k分别为xc,y c,M和意义相同的表现型.G k可视

12、为四维空间中的一点对应于表现型Hk5为:H k=h k1(x3k1,y3k1,h k2(x3k2,y3k2,h kN(x3kN,y3kN(7其中,x3k jy3k j =M kco sk-sinksinkco skx k jy k j+x cky ck,(j=1,2,N(8根据图像的物理约束特征,确定表现型的取值范围及相互间映射关系如下:定义图像的宽度为w,高度为h,由约束1知:wh,定义图像中QR码符号边长为u,由约束2知:uh,因为图像的主题是QR码,取u34h,所以x c38h,w-38h,y c38h,58h.因为表现型x ck和yck为二进制编码,为了克服二进制编码存在较大Hamm

13、ing距离和连续函数离散化时有精度映射误差等问题,扩大xck 和yck的取值范围:xck0,127,yck0,63.则x方向的偏移步长ex =w-34h128,y方向的偏移步长e y=h256.所以基因中的表现型同图像中的实际值之间的关系如下:xc =38h+e x(1+x ck,y c=38h+e y(1+y ck.定义图像中QR码符号面积为s,s916h2,h2,设定面积变化的最小值为116h2,则可以确定放大倍数M的表现型Mk 的取值范围为:Mk0,7,则M=916+116h2M k.由于拍摄时主观因素的参与,所以假设旋转角度以45度为单位,所以:=45k,k0,7到此可以确定染色体Gk

14、编码的总长度为19位,具体如下: 50大连铁道学院学报第26卷3.2.2适应度定义个体的适应度用匹配率作为评价依据.由于前面定义的QR码符号中的点在图像中有多个像素,图像在拍摄过程中有略微的拉伸,旋转角度上也不能绝对地在45k的角度上,所以不能以点所包含的像素100%匹配来评价.解决这个问题的办法是设定点中75%的像素匹配就认为该点匹配,即f(x3k j, y3k j=1,否则f(x3k j,y3k j=0.因此,个体I k的适应度可按下式计算:f(I k=Nj=1f(x3k j,y3k jN3.2.3遗传操作通过三个基本操作:选择、交叉和变异来完成对染色体位串的修改,以得到最优解.而标准遗传

15、算法要花费大量的时间才能收敛到最优解,因此,有必要对其进行修改.(1交叉操作,本文采用所求解的特定问题的知识来改进,具体操作:当进行交叉操作的两个候选解的适值低于最优解库中的平均值(,实施标准的单点交叉;当两个候选解其中任一适值大于时,交叉参数从两候选解的位置(xck 、yck、放大倍数(M k及旋转角度(k的平均值中选择,再对该对候选解的适值函数加权.(2变异操作,对于最优解库中小部分可能解保持不变,以保证不丢失最佳可能解;剩下一小部分通过其解的参数上(位置、放大倍数、旋转角度加上一小的常数实现轻微变化,该操作对应于以靠近最优解附近的局部极值.最后的可能解的变异按如下步骤实现:小的随机扰动值

16、加到位置参数,大范围的随机扰动加到旋转角度、放大倍数和模型已证实的参数上,变异后的可能解代替以前可能解跳出局部最优解.一旦可能解已收敛到接近最优解,则逐步减少变异操作概率.3.2.4收敛准则给出以下两个条件作为收敛准则:(1进化代数达到一个给定的上界T;(2连续10代没有新的最小点出现,则随机选择新的个体加入进化,如连续两次未出现新最小点,则进化结束.3.2.5算法步骤步骤1:随机搜索获得初始种群;步骤2:计算适应值,并判断算法收敛准则是否满足.如“满足”则转步骤5;步骤3:若算法收敛准则不满足,进行遗传操作.应用静态繁殖理论,判断子代染色体的适值是否高于父代,如果“是”,则用子代替代父代,否

17、则保留父代;步骤4:判断是否最优解,是,得到最优解,转步骤5;否则,转步骤3;步骤5:输出结果.4实验结果及分析为了验证本算法的有效性,识别设置的参数有:种群大小为20,选择操作淘汰比例为40%,变异率为1%,终止世代数120.针对旋转的QR Code图片(图3进行识别,在70代后收敛到最优解,而使用随机搜索很难得到最优解,参见图4.从实算结果可知,在图像中进行QR码基元提取的遗传算法,在噪音干扰下,仍保持良好的自适应性.在同时识别和提取多个基元时,该问题演变为多模态函数优化问题,需要引用分享机制,对适应度函数做适当的改进.第4期谷晓琳等:基于遗传算法的二维QR码图像识别51图3旋转的QR C

18、ode图4QR码识别的实算结果5结语实例数据分析可知,对于旋转、放大等QR码,应用改进的遗传算法来识别,且能在较短时间内快速识别,即得到最优解,效率得到明显的改进.总体上说,本课题目前还是一个全新的概念,将其完全实现并付诸于商业化,还需要更进一步的研究、开发.参考文献:1P AVL I D I S T,S WARTZ J,WANG Y P.Funda mentals of bar code inf or mati on theoryJ.IEEE Comp u te r,1990,23(4:74286.2P AVL I D I S T,S WARTZ J,WANG Y P.I nfor mati on encoding with t w o2di m ensi onal bar codesJ.IEEE Comp u te r,199