基于亚像素的快速响应矩阵码的图像定位算法

曹 琨，张姗姗

(河南牧业经济学院计算机应用系，河南郑州450044)

随着信息技术的迅速发展，二维码技术也得到了蓬勃发展，相对于一维码技术，其具有信息容量大、可靠性高、成本低、纠错能力强等优点，可以表示数字、字母、汉字和图像等信息，在电子商务、工业生产、物流管理以及公共安全等领域等得到了成功应用［1-3］。

根据结构，二维码分为两种:堆叠式和矩阵式。堆叠式二维码由多行一维条码堆叠而成，以PDF417为代表［4］;矩阵式二维码的符号是矩阵，信息分布在矩形内，采用像素点的黑白对信息进行描述，如快速响应矩阵(Quick Response Code，QR)［5］。1994年，日本Denso公司研制出了QR码，其不仅具有一维码和其他二维码的优点，而且具有可以表示汉字、图像、防伪性强等特点，成为当前主流的二维码［6］。2000年，我国制定了《快速响应矩阵码》国家标准，可以表示中国汉字，拓宽了QR码的应用范围［7］。在QR码实际应用中，必须对QR码进行正确识别，而 QR码的定位是 QR码识别的基础［8］。针对QR码的定位问题，国内外的研究机构和学者进行了大量、深入的探索，提出许多有效的QR码定位算法，主要分为基于轮廓查找的定位算法、基于圆角检索的定位算法和非线性定位算法3类［9］。轮廓查找的定位算法根据QR码的图像特点，搜索图像的轮廓确定QR码的位置，其对光照变化、噪声比较敏感［10］;基于圆角检索的定位算法主要包括Hough变换定位算法和图形位置定位算法［11-12］，它们利用QR码的位置探测图形来实现QR码定位的位置，但当QR码发生较大的畸变时，定位准确率比较低;非线性定位算法将QR码定位看作是一种分类问题，首先提取QR码的特征，然后采用非线性分类能力强的神经网络、支持向量机对训练样本进行学习，构建QR码的分类器，从而采用建立的分类器对待定位的QR码进行定位，但是其定位性能与分类器参数密切相关［13-14］。

针对当前QR码定位算法存在的不足，为了获得更加理想的QR码定位结果，提出一种基于亚像素的QR码定位算法，并采用仿真实验对其有效性和可靠性进行测试。实验结果表明，相于当前经典的QR码定位算法，基于亚像素的QR码定位算法不仅提高了QR码的定位精度，而且加快了QR码的定位速度，可以满足QR码的实际应用需求。

1 QR码简介

1．1 QR码的结构

QR码通常由一个正方形阵列构成，它划分为两部分:编码区域和功能图形。编码区域主要由数据码字、纠错码字、版本信息等组成;功能图形由寻像图形、分割符、定位图形和校正图形等组成，它不用于数据编码，符号四周为空白区，具体如图1所示。寻像图形包括3个位置探测图形，它们分布于QR码的3个角上，主要用于确定QR码符号图像的位置。QR码版本有40种规格，4个纠错等级，可以对7 089个数字或者4 296个字母数字进行编码，最高纠错等级为30%码字。在QR码的译码过程中，3个位置探测图形的中心坐标起着十分重要的作用［15］。

图1 QR码的符号示例

1．2 QR码的特征

在实际应用中，采集到的QR码具有如下特征:

1)采集到的QR码图像的水平与的垂直比例固定为1∶1，且图像的主体为QR码。

2)QR码一般用于商品包装，并且包括了大量与QR码无关的内容，因此QR码的图像背景十分复杂。

3)由于拍摄过程中的角度以及距离影响，得到的QR码存在一定的倾斜与畸变。

4)由于外界因素的影响，QR码图像包括一定的噪声。

2 传统QR定位算法以及存在的不足

2．1 传统QR定位算法

当前QR码定位算法基于纹理、频域和机器学算法进行定位，通常直接采用位置探测图形实现定位，以文献［15］的QR码定位算法为例，QR码定位的步骤如下:

1)采用专门QR码图像采集设备，收集QR码图像。

2)由于图像一般包含噪声数据，为此采用小波变换对QR码图像进行去噪处理，提高QR码图像的质量。

3)采用大类间类差算法对QR码图像进行二值化处理，使QR码与背景图像之间的差异尽可能大。

4)利用形态学算法消除背景图像的无用信息，便于QR码图像分割。

5)采用Max-Min差分以及相关边缘检测算法，提取QR码的目标边缘。

6)利用Hough变换定位算法寻找QR码的4条边界，对QR码的候选位置进行初步定位。

7)根据3个位置探测图形来确定QR码的位置和方向，实现QR码的候选位置精确定位。

2．2 存在的不足

随着QR码的应用领域的不断增加，由于外界环境以及一些不可克服的因素影响，采集的QR码图像的分辨率低，而且QR码存在倾斜、畸变、几何失真，导致QR码的3个位置探测图形的水平与垂直比例不能满足1∶1的关系，同时黑白块的比不符合3∶1∶1的关系，这样使QR码的定位失败，难以实现精确定位。具体如图2所示。

图2 采集的不同QR图像

3 本文的QR码定位算法

3．1 QR码图像的灰度化处理

随着电子器件的不断成熟，现在图像采集的设备得到QR码图像均为彩色图像，彩色图像包含的信息理大，需要存储空间较大，影响QR码图像定位的效率，而在实际QR码的有效信息是黑白的，因此，为了加快QR码定位的速度，对彩色QR码图像进行灰度化处理，当前灰度化处理方法很多，本文采用加权平均值法进行QR码图像灰度化。利用人眼对各个颜色分量的敏感程度不一样，将各个分量赋予一定的权值，取3个分量的加权平均作为灰度图像相应像素的灰度值，模型化表示如下

对图3a中的彩色QR码图像进行灰色度化，得到的结果如图3b所示。

图3 采集的不同QR图像

3．2 QR码图像的去噪处理

小波是函数空间L2(R)中，满足所谓的“容许条件”的函数，对任意信号函数f(t)∈L2(R)，连续小波变换定义为

离散小波变换中时间仍为连续变量，将尺度参数和平移参数离散化，得到分析小波

离散小波变换定义为

小波分析最主要的特点是自动变焦、多尺度分析，被称为数学分析的“显微镜”，因此利用小波变换实现频率选择和多尺度分解，可起到抑制背景噪声，消除散焦影响和增强目标的作用，信号的分解公式为

式(5)为低频信号的分解过程，第i级低频信号Ai，k分解得第i+1级离散低频信号Ai+1，k，h为低通滤波器;式(6)为高频信号的分解过程，第i级高频信号 Di，k分解得第 i+1级离散高频信号Di+1，k，g为高通滤波器。利用小波变换去除高频噪声保留低频信号。

3．3 边缘点粗定位

首先采用Otsu阈值分割算法对图像的QR码进行分割，设一幅图像的QR码灰度值范围为0～L，定义灰度为i的像素个数为ni，像素总数为N，则必有

假设存在一个阈值T，图像函数f(x，y)中的像素被T分为 C1和C2类，即

式中:fmin和fmax分别为图像f(x，y)中灰度的最小值与最大值。

那么C1部分的分布概率p1、灰度均值μ1和方差计算如下

采用相同的方式计出C2的分布概率p2，灰度均值μ2，方差，定义类间方差和类内方差，有

阈值T1将QR码像分成两类D1和D2，两类的灰度均值μ1和μ2，两类的相对距离值d

找出使两类的相对距离d最大的阈值Th，即为最优分割阈值，从而将QR码图像从背景中分割出来。

3．4 亚像素的精确定位

QR码的图像的周围具有一定的空白区域，它们与3个位置探测图形具有边缘效应，因此采用亚像素的精确定位步骤如下:

1)对左上角顶点位置坐标，以及左下角和右上角的顶点位置坐标。

2)根据QR码四周为空白区，通过右上角顶点和左下角顶点的边界扫描线确定右下角的顶点位置坐标。

3)通过逐个找描述QR码的亚像素点实现QR码的精确定位。

3．5 本文QR码定位算法的工作步骤

1)对图像进行灰度化，去噪声等预处理操作。

2)采用Otsu阈值分割算法对图像中的QR码进行粗定位。

3)对粗定位结果进行几何校正与旋转。

4)采用亚像素对3个位置探测图形的中心和方向进行确定，从而实现图像中的QR码进行精定位。

综合上述可知，本文提出的QR码图像的定位算法工作流程如图4所示。

4 仿真实验

4．1 仿真环境

为了测试本文提出的QR码定位算法的有效性和优越性，在 Intel 4核 2.8 GHz CPU，内存为 4 Gbyte，Windows XP Professional操作系统，采用VC++实现仿真实验。为了实验结果更具说服力，选择文献［16］的QR码定位算法进行对比实验，采用不同字符数量和不同分辨率的图像集对它们的定位正确率进行对比分析。

图4 本文QR码定位算法的工作流程

4．2 结果与分析

4.2.1 定位结果的视觉效果比较

本文算法与文献［16］算法的QR码定位结果如图5和图6所示。对图5和图6进行的结果进行比较，可以清楚看出，本文算法的定位结果更优，可以对QR码实现准确定位，对比结果初步证明了本文算法的有效性和优越性。

图5 本文算法的QR码定位结果

图6 文献［16］算法的QR码定位结果

4.2.2 算法的识别正确比较

为了客观、准确全面衡量本文算法的性能，分别采用不同字符数量QR码图像和不同分辨率的QR码图像进行测试，本文算法与文献［16］算法对QR图像集定位正确率分别如图7a和7b所示。从图7a可知，随着随字符数量的增加，文献［16］算法的QR码的定位正确率出现大幅度的波动，而且呈单调递减趋势，而本文算法与字符数量变化的关系不太大，QR码定位正确率的变化比较平衡，而且不是呈现明显的递减趋势;从图7b可以看出，随分辨率的增大，本文算法与文献［16］算法的QR码定位正确率也不是呈单调递增趋势，而是呈波动性的递增趋势，但是在相同条件下，本文算法的QR码定位正确率要高于文献［16］算法，结果表明，本文算法较好地解决了当前QR码定位算法存在的不足，提高了QR码定位的准确性，定位结果更加可靠。

图7 本文算法与对比算法的QR码定位正确率对比

4.2.3 不同算法的定位效率对比

在实际应用中，QR码的定位速度是评价定位算法的重要指标，本文采用平均定位时间作为定位速度的评价标准，本文算法与文献［16］算法对图书QR码和火车票QR码的实验结果如图8所示。从图8可知，相对于文献［16］算法，本文算法的平均定位时间最短，提高了QR码定位的效率，可以满足QR码定位的在线需求，具有更高的实际应用价值。

图8 本文算法与对比算法的QR码定位效率对比

5 结束语

针对当前QR码定位算法的不足，以获得更高的QR码定位正确率为目标，提出一种基于亚像素的QR码图像定位算法，并通过具体的仿真实验对算法的性能进行测试。实验结果表明，相对于当前经典的QR码定位算法，基于亚像素的QR码图像定位算法提高了QR码的定位正确率，而且加快了QR码的定位速度，证明了本文算法的有效性，具有一定于实际的应用价值。

［1］李媛，李红星，张益农.二维编解码技术研究与应用［J］.北京联合大学学报:自然科学版，2007，21(4):10-14.

［2］刘云龙，吕韬，曾晋，等.基于android手机的加密QR二维码识别系统［J］.软件，2012，33(4):34-36.

［3］张文爱，吕韬.物料数据加密QR码识别系统的实现［J］.电子技术应用，2012，38(4):117-119.

［4］解龙，杜艳平，程明智，等.基于加密QR二维码的商品包装防伪技术［J］.北京印刷学院学报，2013(4):16-20.

［5］杨佳丽，高美凤.一种QR码的预处理方法［J］.计算机工程，2011，37(2):218-220.

［6］刘家昕，刘家朋，赵宇明.基于边缘增强的二维码区域快速检测定位方法［J］. 计算机工程，2012，38(12):136-138.

［7］刘宁钟，苏军，孙涵.工业控制环境中QR Code的检测和识别算法［J］. 电子学报，2011，39(10):2459-2463.

［8］阳建华，郑莹娜.一种复杂条件下的QR码图像预处理算法［J］.科学技术与工程，2014，14(2):1671-1815.

［9］陈二阳.QR条码图像识别及解码技术的实现［J］.电视技术，2013，37(7):16-19.

［10］熊用，汪鲁才.基于相关匹配的QR码识别方法［J］.仪器仪表学报，2011，32(3):571-576.

［11］陈杰.QR码图像预处理技术研究［J］.温州大学学报:自然科学版，2010，31(6):16-23.

［12］余强，裴颂文，吴百锋，等.基于圆检测的二维条码定位方法［J］. 计算机应用与软件，2008，25(12):109-112.

［13］陈威兵，杨高波，冯璐.一种QR码识别的低复杂度图像预处理方法［J］.湖南大学学报:自然科学版，2012，39(10):93-97.

［14］卫晋伟，戴曙光，穆平安.基于形态学和Hough变换的QR码矫正与定位方法［J］.电脑与信息技术，2010，18(6):32-36.

［15］孙明，傅隆生，杨信廷，等.用于QR码自动识读的图像分析方法［J］. 电子科技大学学报，2009，38(6):1017-1020.

［16］肖翔，刘晓明，王云柯.QR码图像的矫正与定位方法研究［J］.计算机科学，2007，34(11):217-219.