基于最大连通区域的QR码提取和校正方法

龙清清，宋夫华

LONG Qingqing , SONG Fuhua

中国计量学院 机电工程学院,杭州 310018

College of Mechanical and Electrical Engineering, China Jiliang University, Hangzhou 310018,China

1 引言

QR(Quick Response) 码[1]是由日本Denso公司于1994年9月研制的一种矩阵式二维条码，也是最早可以对中文汉字进行编码的条码。由其具有比一维条码信息密度高，容量大，全方位识读，保密防伪性强，纠错能力强，超高速响应，可离线应用的便携式数据库等的优点，因此近年来在国内外得到了快速发展并广泛应用于身份验证，物流管理，安全防伪，票务流通，电子商务等诸多领域[2]，其符号如图1所示。

目前，使用数码拍摄设备识别 QR码日益兴盛，通常将拍摄包含QR码的图像使用软件对图像进行识别[3]，问题在于软件如何对QR码进行识别，则需考虑以下几个因素：

⑴ 拍摄设备本身分辨率大小影响图像质量

⑵ QR码在图像中的位置不固定且处于各种不同的背景中

⑶ 拍摄角度，距离以及光照的不同会使QR码有旋转，放大，拉伸或扭曲等变形

因此 QR码的识别首先要确定符号在图像中的位置，将符号从背景中提取出来，再进行几何失真校正并使用译码规则读取数据。而传统的提取方法是根据QR码的编码规则采用寻像图形的黑白模块比例(即1:1:3:1:1)来定位QR码，由于此种提取方法依赖寻像图形，当寻像图形有破损、污渍和光照不均等噪声时，此时的定位效果就会受到很大的影响，因此本文采用最大连通区域来快速定位目标区域。

图1 QR码符号

2 QR码的提取和校正

QR码的提取[4]是二维条码识别过程中最基本的步骤，它是指将QR码区域从实际图像的背景中分割开来，然后以提取后的图像单独做研究的方法。由于拍照所获得的图像不可避免的会引入噪声，则需对提取的区域进行滤噪和几何失真校正。其步骤如图2所示：

图2 QR码提取和校正步骤

2.1 QR码的提取

由图2可知QR码的提取分为三个步骤。第一步是边缘检测[5]，其基本思想是：首先利用边缘增强算子突出图像中的局部边缘，然后定义像素的边缘强度，通过设置阈值的方法提取边缘点集。由于 sobel算子对灰度渐变和噪声较多的图像处理效果较好，因此此处采用sobel算子检测。

第二步是卷积滤波，其基本思想是：通过卷积核围绕自己的核心元素顺时针转180度，移动卷积核的中心元素，使它位于输入图像待处理像素的正上方，在旋转后的卷积核中，将输入图像的像素值作为权重对应相乘，然后将上一步各个结果的和作为该输入像素对应的输出像素。设卷积核矩阵有M ×N个元素，每个元素的值分别是Ki,j，当卷积核的中心(cm,cn)位于图像矩阵的(x,y)位置（像素灰度值为gy,x）时，则经过卷积滤波后，该像素的灰度值将变为：

本文以火车票为例，如图3(a)所示，通过卷积滤波得到结果如图3(b)所示。

第三步是采用本文提出的最大连通区域算法来标记QR码的最大连通区域。区域标记是指把唯一的标号赋给图像各像素区域，但相同像素值根据邻域数不同而被区别标记为不同的区域。而区域连通是指在一副二值图像中，任意一点加上其n个邻域点，按照从上到下且从左到右的顺序，以非0则为连通区域的规则且从1开始整数递增顺序标记各连通区域。在二维图像中有 4邻域与 8邻域，三维图像中则有6,16,26邻域，如何求标记的所有区域中最大连通区域，本文采用最简单也最自然的区域属性法：面积。它由区域包含的像素个数给出。为了得到区域的实际大小，需要考虑每个像素的实际面积，如式（2）所示的矩阵及其8连通区域。

针对实际图像采用上下左右以及其45度角方向的8邻域进行标记。由于QR码是由多个正方形小模块所组成的一个正方形阵列，当存在偏斜或凸起时呈四边形，因此总可用求得的最大连通区域的最值行与最值列构成正方形，将此正方形区域放大，即可快速锁定 QR码所在区域，如图 3(c)所示。

2.2 QR码的校正

QR码的校正分为四个步骤。第一步先对所获得的 QR码区域使用亮度调节以消除光照不均，此外，在滤噪过程中由于中值滤波在一定条件下可以克服线性滤波器如最小均方滤波和均值滤波等导致的图像细节模糊，能够在消除噪声的同时保护图像的边缘，因此采用3*3的方形中值滤波窗口效果比较好。其中二维序列{Xij}中值滤波表达式如式（3）所示，其中A为滤波窗口：

第二步是通过闭运算来凸显最大连通区域的轮廓。先膨胀后腐蚀的过程称为闭运算，它具有填充物体内细小空洞，连接邻近物体，在不明显改变物体面积的情况下平滑其边界的作用。图像X关于结构元素S的闭运算记为X·S,闭运算定义为：

闭运算对于结构的平移不具有不变性，闭运算是一种递增变换，它是正向扩张运算，即：

由于QR码本身是正方形，因此采用正方形形态学算子做闭运算较好。

在对图像二值化时，其阈值的选取方法有全局阈值和局部阈值法，通过实验对比得出使用 Ostu最大类间方差法效果较好。它的基本思想是将图像的直方图在某一阈值处分割成两组，以暂定的阈值使用循环遍历法使被分成的两组间方差最大来确定阈值。效果如图3(d)所示。

图3 火车票QR码的提取及检测结果

第三步是利用Hough变换[6]检测最大连通区域的四条边线。Hough变换的原理是利用图像全局特性将边缘像素连接起来组成区域封闭边界，其具体算法如下：

直线y=mx+b可用极坐标表示为ρ=xcos(θ)+ysin(θ)，其中(θ,ρ)定义了一个从原点到线上最近点的向量，这个向量与该直线垂直。同理将图像空间中的每一点(xi,yi)映射到Hough空间中的一组累加器A(θi,ρi)，满足上式的每一点，将使对应的所有累加器中的值加 1，如果图像包含一条直线，则有一个对应的累加器会出现局部最大值；通过检测Hough空间中的局部最大值，可以确定与该条直线对应的一对参数(θ,ρ)，从而把该直线检测出来。如图4(a)所示的位于直线b=mx+y上的三个点，将其映射到b-m参数空间则为经过同一点的三条直线，如图4(b)所示。

图4 Hough变换的图像空间与参数空间

图5所示为使用Hough变换检测火车票最大连通区域里四条边所对应的峰值点。

最后一步是图像的几何变换。它指将图像几何操作后，内部结构比例等发生变化，但整体布局与形状没有改变。在二维图像中，变换形式有仿射，投影，自定义函数等方式。在文献[7]中运用Hough变换检测到的最长直线的倾角来校正图像，然而对于受损为四边形的图像校正效果是很差的。本文采用投影变换[8]的方法对图像进行几何变换，投影变换是将一种地图投影点的坐标变换为另一种地图投影点坐标的过程。由于投影变换需要四对控制点，本文以Hough变换检测到的四边形的四个交点为控制点，选取左上角控制点为基点，以任意两点距离为边长构造正方形并取其四个顶点作为校正后图形的顶点，进而得到两个空间的映射关系，完成坐标值的变换。其中可将控制点坐标变换表示为：

其中(x',y')为变换后的坐标值，k1,.....k8为变换矩阵。相应位置的灰度值则使用双线性插值[9]恢复，若变换后的某点(x',y')在原图中对应(x,y)位置处的四邻域坐标为：

其相应灰度值为：

则(x',y')处的灰度值可用式(7)表示，其图形关系见图6所示。

通过坐标变换和双线性插值变换的结果如图7所示：

图6 双线性插值示意图

图7 最大连通区域的校正图像

3 实验结果及分析

为了验证本算法的有效性，本文使用800万像素的三星手机和130万像素的联想手机在不同角度，不同光照，不同背景下拍摄的共90张质量不同的QR码进行了实验，在内存为4G的pc机上使用matlab仿真[10]，实验结果显示其提取平均用时在200ms内，校正平均用时在300ms内。总耗时在500ms内，识别效率可达81%，其识别速度和效率较高，统计结果如表1所示。

表1 不同像素手机QR码识别时间

通过实验得出，不同像素的手机拍摄的QR码所进行的识别效率各有不同，高像素的识别效率可达 91%，其提取和校正总平均用时在540ms左右，而低像素的识别效率却只有 70%，但提取和校正平均用时却在420ms左右。实验结果表明本文提出的算法能够快速有效定位QR码区域，同时也说明了高像素手机能够提高识读效率。

4 结论

本文研究了快速响应码的提取和校正方法，针对受到背景干扰，形变的QR码，提出了一种基于最大连通区域的快速提取方法，并借助QR码本身结构的特性使用投影变换对QR码进行了校正。通过大量实验表明，本文提出的QR码图像提取与校正方法能够快速定位条码区域，解决了QR码受到背景干扰以及自身形变难于定位和校正的问题，满足了实际应用的需要。

[1]中国物品编码中心,QR码技术与应用.北京,中国计量学院出社,2007:188-225.

[2]许统,手机QR码在国内的发展及应用,四川师范大学图书馆,2011,19(3):63-69

[3]Satoshi Ono,Shigeru Nakayama,Two-Dimensional Barcode Decoration Based on Real-Coded Genetic Algorithm.IEEE Evolutionary Computation,2008,1068-1073

[4]Yu Fang,Yue Peng,The Design And Implementation Of Two-Dimensional Barcode Identification In Smartphone.IEEE Computer Application and System Modeling,2010,635-637

[5]Milan Sonka,Vaclav Hlavac,Roger Boyle 图像处理,分析与机器视觉(第三版).北京,清华大学出版社,79-175,470-493

[6]刘桂雄,申柏华,冯云庆,等,基于改进的Hough变换图像分割方法.光学精密工程,2002.10(3):258-260

[7]武莎莎,姚敏,赵敏,基于Hough变换的二维条码图像倾斜校正研究.淮阳工学院学报,2002.10(3):55-56

[8]刘慧娟,一种快速响应码图像的分割和校正方法.电子测量与仪器学报,2006.20(1):34-35

[9]刘宁忠,杨静宁,基于投影算法的二维条码识别.计算机工程,2002.28(9):32-34

[10]杨杰,数字图像处理及MATLAB实现.北京,电子工业出版社, 2010:47-169.