基于游程编码的QR码图像识别

侯阿临， 冯 源， 焦松林， 郭云飞， 王乐乐

（1.长春工业大学计算机科学与工程学院，吉林长春 130012; 2.长春大学计算机科学技术学院，吉林长春 130021）

0 引 言

近几年，随着世界经济的迅猛发展，条形码的应用越来越广泛。特别是在票据条码印刷、食品药品条码印刷方面一维条码越来越难以满足要求。一维条码由于对计算机网络、后台数据库过分依赖而很难进行深入的推广应用。QR码即快速反应的意思，来自英文“Quick Response”的缩写[1]。QR码比传统的条码能存储更多的信息，不再需要像扫描传统条码一样直线对准扫描器。使用红外光增强摄像头取代了这方面的工作，直接对相机采集到的图像中QR码图像进行软件识别，所以降低了对反射角度的要求。然而QR码作为二维条码的一种，它具有高密度、大容量纠错能力强等特点，能高效地体现出汉字的特点，因此在我国有广泛的应用前景[2]。在实际应用中要对QR码图像进行采集、存储、识别、检测等工作，其中的过程引入一定规模的噪声，使之应用有了一定的限制，尤其给图像的识别造成了一定的难度。二维条码的识别是集机器视觉和模式识别、图像处理技术于一体的智能系统，是一个重要的研究课题。我们对QR码图像识别的预处理技术进行深入研究，通过改进滤波技术、增加定位块检测和定位校正等关键技术，有效提高二维条码译码的实用性、可靠性。

文中以工业相机采集的QR码图像为例，讨论QR码的图像处理与识别方法。

1 QR码的图像处理

QR码是由日本Denso公司于1994年9月研制的一种矩阵二维条码符号，每个QR码符号由正方形模块组成的一个正方形阵列构成，由编码区域和包括寻像图形、定位图形和校正图形等功能图形组成，其符号大小由版本决定。QR码符号共有40种版本，分别为版本1、版本2…版本40[3]。版本l的规格为21模块×21模块，版本2的规格为25模块×25模块，依此类推，每一版本比前一版本每一边增加4个模块，直到版本40，其规格为177模块×177模块（模块指每一个黑色或白色小正方形）[4]。

每个QR码都是由正方形模块组成的一个正方形阵列构成，分为编码区和功能区，功能区不能用于数据编码，符号的周围为空白区[5]。QR码的结构如图1所示。

图1 QR码结构

1.1 QR码图像处理的软件流程图

在过去的几年里，学者们对QR码已经进行了很多研究，但是在速度上的提高不是很大。文中根据QR码图形特点，结合图像的定位方法，提出一种快速检测QR码的算法。

QR码图像处理流程主要包括图像的寻像图形检测、图像定位以及识别图像，如图2所示。

图2 QR码图像处理流程

1.2 图像的采集

QR码图像如图3所示。

图3 QR码图像

在图像处理过程中，图像的采集是首要的步骤。文中采用工业用单色摄像头对QR码图像进行采集，采集到QR码图像为二维灰度图像，见图3（a）。

1.3 图像的二值化

图像的二值化关键在于阈值的选取。二值化阈值方法主要有直方图双峰法、微分直方图法、最大类间方差法。在文中的QR码识别系统中，采集原图像后，做出直方图，再将直方图经过平滑后，呈现出明显的双峰特性[6]。这样，使用简单的直方图双峰法就可以快速地确定图像的二值化阈值，处理结果见图3（b）。

1.4 游程编码——形成图形组件

游程编码是将信源符号中的相同字符转换成一个计数字段，再加上一个重复字符标志。这种方法对于二值图像最为有效，所以在这里采用游程编码这种方法。将图像转化为一串串由黑白相间的像素组成的码流，相邻行的码流间有关联的码流划分为同一个组件，从头扫描图像，这样扫描下去，有关联即为同一组件，这样就把整个图像的所有组成图形显示出来，而且速度较快。

1.5 滤波

做QR码图像的直方图，即x轴方向投影，将边缘处投影点数小于整幅图像像素点数1%的部分用滤波器滤除掉，以得到一幅去噪后的图像，便于下一步定位寻像图形。

1.6 位置探测图形

图形本身的特征信息有一种包含关系在里面，图形中心小块与整个寻像图形之比为9∶49，将符合此特征的区域确定为寻像图形。找到寻像图形以后，按此规则继续找到余下的2个寻像图形，3个寻像图形位置的确定就完成了整个QR码图像的定位，根据校正图形和定位图形建立取样网格[7]。A点为左结合点，B点为右结合点，两点间的距离一定。

位置探测图形如图4所示。

图4 位置探测图形扫描

2 QR码的解码

由于在QR码符号中可能存在污损，导致数据读取错误，因此在译码前，对得到的数据需进行纠错，有了纠错，大大提高了QR码的可识读性。通常QR码采用 Reed2 Solomon对数据进行纠错。Reed2 Solomon码是一种扩展的非二进制BCH码，在伽罗华域中进行运算[8]。

QR码解码基本流程大致有以下几个步骤:

1）识读格式。先进行格式的提取，再提取版本信息，最后提取识别纠错等级和掩模图形。

2）去掩模。用掩模图形对矩阵中的编码区域进行异或处理[9]。

3）码字提取。从数据矩阵中，按照数据模板的排列方式，将0，1数据提取出来，得到数据码字流和纠错码字流，便于下一步进行RS纠错。

4）RS纠错。确定符号码字，并根据符号版本和纠错等级需求，将码字序列重新按块排列。应用检测和纠错译码程序，纠正替代错误与拒读错误，直到规定的纠错容量。接着重新组配数据块序列，恢复原始信息的位流，并将数据流分成若干块，对每一段译码[10]。二进制译码算法只需要找出错误位置，在这里主要使用BM迭代算法，迭代过程表见表1。

表1 迭代过程表

以下举例说明此算法。

表1中σ（i）为错误位置多项式，di为i+1与i步之间的差值，Li为σ（i）的次数。BM算法能够快速根据伴随多项式s求出错误位置多项式。当位置多项式根为α5，α14，那么说明发生错误位置为α14，α5，即错误发生在x14和x5上面。

5）数据解码:对纠错后的数据按照使用的模式信息进行解码，得出数据字符并输出结果。

QR码图像识别如图5所示。

图5 QR码图像识别

3 结 语

通过对图像的滤波、二值化、编码等进行图像预处理，将游程编码方法用于二值化的图像，进行QR码图像中组件图形的选取，从实质上解决了图像处理的速度问题，也提高了图像处理的质量，正是由于速度的提高，使其在工程现场的应用成为可能，在条形码检测领域具有实用价值。

[1] Daniel Walsh，Adrian E Raftery.Accurate and efficient curve detection in images:the importance sampling Hough transform[J].Pattern Recognition，2002，35（7）:1421-1431.

[2] 陈媛媛，施鹏飞.二维条形码的识别及应用[J].测控技术，2006，25（12）:17-19.

[3] 万菁.二维条码的编解码及系统实现[D]:[硕士学位论文].上海:上海交通大学，2007.

[4] 王新梅，肖国镇.纠错码原理与方法[M].西安:西安电子科技大学出版社，2001.

[5] 国家质量技术监督局.快速响应矩阵码 GB/T 18284-2000[S].北京:中国标准出版社，2001.

[6] 章毓晋.图像处理与分析[M].北京:清华大学出版社，1999.

[7] 刘东，高西全.QR码图像处理及识别算法的研究[J].信息技术，2004，28（1）:61-62.

[8] 叶情贵，刘宇怀.RS码纠错算法的软件实现[J].华东师范大学学报:自然科学版，2005（4）:98-101.

[9] 尚晓航.网络系统管理:WINDOWS 2003篇[M].北京:人民邮电出版社，2006.

[10] 张球英.二维条码-QR code研究及应用[D]:[硕士学位论文].石家庄:华北工学院，2003.