高形变二维码识别算法设计与实现

于继明,徐 楠,陈 硕

(1.金陵科技学院智能科学与控制工程学院,江苏 南京 211169; 2.江苏省信息分析工程实验室,江苏 南京 211169)

高形变二维码识别算法设计与实现

于继明1,2,徐 楠1,2,陈 硕1

(1.金陵科技学院智能科学与控制工程学院,江苏 南京 211169; 2.江苏省信息分析工程实验室,江苏 南京 211169)

针对QR(Quick Response)二维码在高偏离拍摄角度下难以识别的问题,设计一种在高偏离拍摄角度下正确识别的算法。该算法通过对图像二值化处理、形态学处理、边缘检测、Hough变换和射影几何变换5个步骤,实现对图像的高准确率识别,使用java语言环境和移动终端的android环境下对算法进行仿真与算法验证,并实现了通过扫描或读取二维码图像来写入、查找信息等操作。

QR二维码;图像识别算法;线性形变

各种各样的二维码自诞生开始迅速成为了信息技术领域最实用和有效的成果之一,已经渗透到人民生活和国民经济的各个领域中。不论在商品零售、制造业等领域,还是在供应链管理、电子商务和现代物流等各个环节,二维码已经扮演了不可或缺的重要角色[1]。为了实现对二维码的识别,人们使用图像采集设备(如数码相机、激光扫描器、面阵CCD等成像设备),得到含有二维码的图像,然后经过定位(预处理、定位、角度纠正和特征值提取)、分割和解码3个步骤实现对二维码的识别。现在广泛使用的二维码识别算法具有快速识别的特性,但对于高偏离拍摄角度的识别,这些算法不能快速有效地得出解码结果。当偏离角度较大、焦距较小时,图形的形变不仅仅只是普通的缩放,还会是旋转形变或仿射形变了。因此,研究与设计高形变角度下的二维码图形识别算法具有重要的意义。

1 QR二维码介绍及常用算法

1.1 QR二维码原理

QR二维码是Denso Wave于1994年在丰田公司发明,是一种矩阵式的二维码符号。QR二维码不仅具有识别扫描速度快、信息容量较大、可靠性较高、成本较低的特性,它还可表示汉字及图像等多种文字信息,并且其保密防伪性强,使用也很方便。诞生初期主要在中、日、韩地区发展,后迅速传至欧美地区。QR二维码符号共有40种版本规格,分别为版本1-40。版本1的规格为21×21个模块,版本2为25×25个模块,以此类推,每1版本符号总是比前1版本每边增加4个模块,一直到版本40,版本40的规格为177 ×177个模块。图1为版本2的示意图(25×25个模块)。

二维码的编码过程包括:1)数据采样计算,确定待编码信息的符号类型(包括中文、英文等),按照相应的字符集编码规则分别转换成对应字符或数字。2)选择一个纠错等级L到H,一般情况下,纠错等级越高其真实数据的容量越小。3)数据编码,将所有的数据字符转换为位流,每8位一个码字成为一组,所有数据最终转化的整体构成一个数据的码字序列。4)纠错编码,将码字序列分块,并根据纠错等级和分块的码字,产生对应的纠错码字,并把纠错码字加入到数据码字序列的后面。5)构造最终数据阵列,按次序放入分块中,按规定把数据分块,将码字模块、定位图像、探测图形、分隔符依次放入矩阵中。

图1 版本2的QR码Fig.1 QR code for version 2

1.2 QR二维码识别中的基本算法

1.2.1 图像二值化算法 图像二值化是指用通过研究图像的灰度分布来研究灰度图像的一种图像数据处理手段,设定某一阈值或为若干区域设定若干阈值,将灰度图像的每个像素点划分成大于阈值的像素点集、小于阈值的像素点集两个部分。每个像素点的值要么是0,要么是255。二值化操作之后,图像将呈现出鲜明的黑白效果。

1.2.2 边缘检测算法 物体的边缘是指以局部特征不连续性出现的部分,是区分不同区域的重要参数。传统的边缘检测(如一介边缘算子)利用了边缘是图像灰度变化最剧烈的特点,对图像各个像素点求导数或者二阶导数来确定边缘点集。常用的边缘提取梯度算子有:Robert算子,Sobel算子,Prewitt算子等[2]。

边缘检测算法是基础的图像分割算法,是进行各种几何变换、特征提取的首要工作,边缘检测算法为各种图像分割需求提供了较好的支持,对于本身就是黑白图像、灰度又不是很连续的二维码图像而言,上述算法均能够取得非常好的边缘检测效果。从边缘检测的时间复杂度上看,每一种边缘检测算法都具有较好的时间效率和空间效率,在进行图像处理时,边缘检测算法一般不会成为影响整个程序运行速度的瓶颈。

2 高偏离角度的二维码识别算法设计

从识别算法的角度,二维码识别算法应当满足以下需求:1)二维码图像的高效二值化处理;2)能够有效地定位到二维码所在的大概区域,排除与识别信息无关的图像区域;3)能够实现对任意拍摄角度的图像的正则复原操作,复原结果应当尽量减小与原图像的误差;4)将复原的图像使用二维码转码包进行转码。识别过程见图2。

2.1 二值化处理算法设计

在二值化处理过程中,针对QR二维码的特性,采用最大类间方差的方法处理。首先获取原图像的灰度直方图,数学描述为记录灰度为i的像素点的数目为ci(i= 0,1,2,...255)。对某一阈值T,将原图像分为两类(背景与前景),计算阈值T下的类间方差值,类间方差计算公式为

其中,

让阈值T在灰度可行域内变化,使得方差σ(T)最大的T为最优解。该算法描述如下:

1)计算原图像的灰度直方图,记为ci(i=0,1,2,...255),灰度阈值迭代初始值为T=0,阈值初值为σ0=-1,最佳阈值初值记为T0=0。

2)按照式(1)计算给定阈值T下的类间方差σ(T),若σ(T)＞σ0,则将T0值设为T。

3)若T未达到灰度上限,则T增加灰度值,返回2);否则执行下一步。

经过上述3步,得到T0即为最佳阈值。

图2 识别算法流程Fig.2 The procedure of recognition algorithm

2.2 图像形态学渲染

为了使二维码区域能够凸显出来,需要二维码区域进行一次腐蚀、膨胀的操作。QR二维码的编码规则具有均匀分布的特点,可以各个像素点的周围圆周点集作为膨胀因子,获得较好的膨胀效果;本算法取对前景点集A以B作为膨胀元素,膨胀操作为[2]

1)取定半径参数R0,角度离散尺度初始迭代角度α=0;

2)由X=R0cos(α)和Y=R0sin(α)计算点(X,Y),把该点加入到B中;

3)角度α增加一个离散尺度,返回2)继续计算,直到离散尺度值全部迭代完毕。

2.3 边缘检测算法

为了纠正偏离角度的图片,需对原图像进行射影几何变换。取4个点(任意3点不共线)的坐标值,使用最为简单的一阶边缘算子来计算边缘。某点的梯度E(x,y)定义为

按照式(3)进行迭代,对每个像素点的梯度判断是否为0确定边缘点集。

2.4 Hough变换算法

根据边缘检测算法取得边缘后,只能够以直线相交的方法来计算4个顶点。应用Hough变换,可将边缘点集映射到直线参数空间,通过计算参数空间的极值取得直线的参数坐标值。

2)对边缘点集中的每一个点P(x,y),带入ρ=x cosθ+y sinθ,步长为中离散变化,得到180个点;

3)将步骤2)得到的点全部四舍五入取整数,绘制到参数空间中。

在实际处理图像时,每条直线在图像中可能凸显的并不明显,有可能出现两对比较相近的参数表示的实际上是同一直线,为解决这一问题,在选择了某个极大值对应的参数后,应当屏蔽这些点。实际操作时将屏蔽点的值设为小于0来做屏蔽处理。

Hough变换结束后,为了能够在射影变换中使得4个交点与4个正则目标点一一对应,需要求解4线在图像面内的交点以及交点的时钟顺序。求交点的算法步骤如下:

1)对4条直线的参数两两运算,记录图像内交点,可得到4个交点;

择其他点替换p3点,直到M1·M2＜0为止;

2.5 射影变换算法

应用式(4),对于平面上的4个点,求解射影变换距离H,对于目标平面(正则)上的每一个点是否为图像平面的前景点,如果是,就将目标平面这一点设置为前景点,否则设置为背景点。应用本步骤可对图像进行校正。

3 模块设计与仿真实现

3.1 模块关系图

本算法在Eclipse环境实现,根据图2流程,设计模块之间调用关系见图3。

图3 模块调用关系Fig.3 Module call

其中,Binary实现二值化功能,Edge Search实现边缘检测功能,Hough实现Hough变换。

3.2 算法仿真结果

为了验证算法的正确性,取得普通形变二维码图形与高度形变图形进行识别比较。正常情况下,普通形变时图形的识别结果见图4。

图4 变通形变识别测试结果Fig.4 The recognition test results of flexible deformation

当获取的图形高度形变时,如图5所示,采用本算法流程,得到较理想结果,如图6所示。

图5 高度形变图像Fig.5 Highly deformed image

图6 高度形变图像识别结果Fig.6 The recognition results of highly deformed image

通过实例测试可以看出,对高度形变的图像,高形变二维码识别算法具有良好的识别结果,能够完成传统识别算法难以完成的识别工作,提高了识别准确率与识别能力。

4 结 语

传统二维码识别算法能够在一个比较小的偏离角度下正确识别,但是对高度形变图形,却难以正确识别。本算法对QR二维码设计了识别过程,对图像处理算法给出了实现原理,并编码进行算法实现,验证算法的正确性与识别能力。实验结果显示,使用本算法对非仿射变换的线性射影进行变换,能够弥补识别率低的缺陷,实现更高的识别能力。

[1]中国物品编码中心.二维条码技术与应用[M].北京:中国计量出版社,2007

[2]Rafael C.Gonzalez.数字图像处理[M].阮秋琦,译.2版.北京:电子工业出版社,2007

[3]吴朝福.计算机视觉中的数学方法[M].北京:电子工业出版社,2011

[4]肖翔,刘晓明,王云柯.QR码图像的矫正与定位方法研究[J].计算机科学,2007,23(2):18-20

[5]谷晓琳,黄明,戚海英.基于遗传算法的二维QR码图像识别[J].大连铁道学院学报,2005,12(3):35-38

[6]刘宁钟,杨静宇.基于傅里叶变换的二维条码识别[J].中国图像图形学报,2011,18(2):45-46

(责任编辑:马金玉)

A Recognition Algorithm for Highly Deformed Two-Dimensional Code

YU Ji-ming1,2,XU Nan1,2,CHEN Shuo
(1.Jingling Institute of Technology,Nanjing 211169,China; 2.The Information Analysis Engineering Laboratory of Jiangsu Province,Nanjing 211169,China)

A recognition algorithm at a highly deviated shooting angle is proposed,which can solve the puzzle of identification for QR(Quick Response)two-dimensional code in case of high-angle shooting deviation from itself.The image can be recognized with high accuracy through the method with five procedures to process the image,i.e.,binarization processing, morphological processing,edge detection,Hough transformation and projective geometry transformation.Then the algorithm has been simulated and evaluated by using java language environment and android mobile terminal.By scanning or reading two-dimensional code image,the identification function can be realized with the algorithm.

QR two-dimensional code;image recognition algorithm;linear deformation

TP393

A

1672-755X(2014)03-0014-05

2014-09-11

金陵科技学院博士启动基金“基于物联网应用的智能校园路灯系统研究”;金陵科技学院2013年省级大学生科技创新项目“智能苗床系统研究”(201313573010)

于继明(1976-),男,河南省罗山人,副教授,博士,CCF会员(E200038613M),主要从事物联网应用技术研究。