基于Gzip压缩算法的彩色QR码生成与识别方法*

陈元枝 ，邓 艳 ，史绍亮 ，姜文英

（1.桂林电子科技大学 电子工程与自动化学院，广西 桂林 541004；2.中国科技开发院广西分院，广西 南宁 530022）

0 引言

传统的黑白条码由于其较强的解码鲁棒性和储存容量，迅速成为自动识别领域的重要分支，国内外学者为了提高条形码的数据容量进行了大量的研究。在一个有限的空间内增加信息密度的需求促进了彩色条码的发展。ColorCode[1]首次使用颜色信息来提高数据容量，但ColorCode仅作为后台数据库的索引，不属于信息携带型的条码。内存码[2](Paper Memory，PM)通过同一空间位置叠加多层QR码来提高数据容量，但对解码软件颜色识别的要求过高。高容量的彩色条码[3](High Capacity Color Barcode，HCCB)通过编码 4色或8色的三角形符号集来提高数据容量，但HCCB码扫描的鲁棒性较差，缺乏明确的模式来支持检测和定位过程。移动多彩色符合码(Mobile Multi-Colour Composite，MMCC)[4]将编码颜色增加为10种，数据容量增加至黑白QR码的4倍，但MMCC码无法正确解码褶皱或边缘弯曲的失真符号。Bulan[5]利用半色调点的方向模型在同一空间位置嵌入2种或3种不同颜色的独立数据，再根据RGB和CMYK颜色空间光谱的互补特性将不同颜色的数据分离，数据容量为黑白QR码的2倍或3倍。高容量的彩色二维条码(High Capacity Colored Two Dimensional Codes，HCC2D)[6]在黑白 QR码的基础上，利用 Zxing[7]和 Libqrencode[8]两个开源的库实现了4色、8色和16色的彩色 QR码，数据容量分别为黑白QR码的2倍、3倍和4倍。

现存的彩色码一般通过增加编码颜色种类或在同一空间位置叠加多层彩色码来提高数据容量，却很少有彩色码利用无损压缩算法来提高数据容量。本文在Gzip压缩算法的基础上设计了一种彩色QR码的生成和识别方法，通过增加编码颜色种类和Gzip压缩算法来提高数据容量。实验证明了4色和16色QR码在数据容量和计算复杂度方面的优越性。

1 彩色QR码的生成与识别

1.1 彩色QR码的设计思路

每个模块可容纳的比特数取决于使用的编码颜色种类，用4种颜色编码信息时，一个颜色模块可容纳2 bit，用8种颜色编码信息时，一个颜色模块可容纳3 bit。以此类推，当编码颜色数为2k种时，每个颜色模块可容纳kbit，即码字总数、剩余位、数据码字数、纠错码字数、纠错的块数等均变为黑白QR码的k倍。

1.2 彩色QR码寻像图形的定位

彩色QR码解码过程中，检测并定位寻像图形是最开始也是最关键的步骤。检测寻像图形时，隔行遍历彩色QR码图像，先在水平方向上统计彩色QR码图像中5种颜色的相对宽度比例是否为1:1:3:1:1，此处比例允许小于50%的偏差；满足上述比例条件后，再垂直检测彩色QR码图像中5种颜色的相对宽度比例是否为1:1:3:1:1，此处比例允许小于40%的偏差；满足上述两个比例条件后，再次检测水平方向上彩色QR码图像中5种颜色的相对宽度比例是否为1:1:3:1:1，此处比例允许小于20%的偏差。偏差的存在主要是为了检测扭曲、变形等失真的彩色QR码。

1.3 彩色QR码编码

彩色QR码的主要编码过程如下：(1)输入待编码数据，生成源数据信息流；(2)用Gzip压缩算法对源数据信息流进行压缩；(3)根据黑白QR码的编码规则进行数据分析，形成数据码字流；(4)根据数据码字流的字节数，利用最小尺寸原则初始化彩色 QR码；(5)在步骤(3)和步骤(4)的基础上，用理德-所罗门码(Reed-Solomon,RS)算法对数据码字流进行分块纠错，形成纠错码字流；(6)将纠错码字流添加到数据码字序列后，构成总码字流；(7)填充寻像图形、分隔符、定位图形和校正图形区域；(8)填充格式信息和版本信息区域；(9)用默认的掩膜图形参考000对编码区域的模块图形进行掩膜；(10)根据黑白QR码符号字符的排列规则，在步骤(8)和步骤(9)的基础上填充数据码字和纠错码字区域；(11)根据预先设定的颜色映射表，将彩色QR码保存为PNG格式。

1.4 彩色QR码解码

彩色QR码的主要解码过程如下：(1)加载并遍历PNG格式的彩色QR码图像，获得每个像素点的RGB值；(2)用寻像图形的定位算法检测3个位置探测图形，若成功检测到寻像图形，则进入步骤(3)，否则进入步骤(11)；(3)返回3个位置探测图形中心点的坐标值，若存在校正图形，则返回校正图形中心点的坐标值；(4)利用寻像图形和校正图形中心点的坐标，进行透视变换，栅格化彩色QR码的颜色模块；(5)根据预先设定的颜色映射表，识读格式信息和版本信息；(6)去除掩膜，恢复数据码字序列和纠错码字序列；(7)用RS算法进行错误检查，若发现错误，则进入步骤(8)；否则进入步骤(9)；(8)用 RS算法分块纠错；(9)将数据解压缩，恢复源数据信息流；(10)根据模式指示符和字符计数指示符，进行数据码字译码，恢复编码数据；(11)结束本次解码。

2 仿真实验

文章中的实验是基于C#版Zxing库进行的，测试QR码的数据容量时，数字模式采用的数据集为“0123456789”共10个数字，字母数字模式采用的数据集为26个大写字母，8位字节模式采用的数据集为26个小写字母，中国汉字采用的数据集为GB2312第16区的94个汉字。该仿真实验主要分析比较了2色、4色和16色QR码数据容量和计算复杂度。

2.1 数据容量

增加彩色条码的数据容量主要有两种方式：(1)增加颜色块的密度；(2)增加颜色种类。这两种方法都有其局限性。当颜色块的密度超过相机分辨率的极限以后，相邻的颜色块就无法区分了；而当颜色种类过多时，某种颜色可由多种颜色混叠得到。相邻颜色块之间的颜色混叠改变了原始颜色块的颜色，因此颜色聚类的方法在存在颜色混叠时效果不佳。为了提高彩色条码单位面积的信息嵌入率和解码鲁棒性，本文设计的彩色QR码不进行偏色处理，提高数据容量主要通过Gzip的压缩算法。

图1列出了数字模式、字母数字模式、8位字节模式和中国汉字模式2色、4色和16色QR码压缩前后数据容量的曲线图。由图1可知，压缩后2色、4色、16色QR码分别从版本8、版本5、版本3开始有值，这是因为Gzip在寻找匹配串时利用哈希表来减小压缩时间，Gzip的最小匹配长度为3 B，如果匹配串小于3 B的话，使用（匹配长度，相隔距离）对进行替换，不但没有压缩，反而还会增大[9]。而随着编码颜色的增加，单位面积的数据嵌入率逐渐提高，而Gzip的最大匹配长度是恒定的，所以16色QR码仅需3个版本就足以容纳哈希表的表头。从图1的曲线趋势可看出，随着版本号逐渐增加，数据容量增加的速度显著提高，且随着编码颜色的增加，压缩算法的优势会更加明显。

图1 QR码压缩前后的数据容量

表1 黑白QR码和彩色QR码版本40-L压缩前后的数据容量

由表1可知，Gzip的压缩算法是本文提高数据容量最有效、最直接的方法。当编码颜色分别为4种、16种时，压缩前4色、16色QR码的数据容量为黑白QR码的2倍、4倍。采用Gzip压缩算法后，中国汉字模式2色、4色、16色的数据容量分别为 85 081、191 775、405 149，与之对应的压缩比分别为 46.82、52.77、55.74。8位字节模式2色、4色、16色的数据容量分别为 199 189、412 035、839 210，与之对应的压缩比分别为 67.45、69.77、71.05。充分说明了该压缩算法的有效性，且随着编码颜色的增多，压缩比逐渐增大，即彩色QR码的数据容量逐渐增加。

由表 2可知，常见黑白二维码（Data Matrix、PDF417、QR码）中QR码的数据容量最大，而关涛[10]设计的 4色、8色、16色彩色DM码的数据容量分别是黑白DM码的2倍、3倍、4倍，16色DM码跟黑白QR码相比较，字母数字模式的容量扩充倍数最大，为黑白QR码的2.17倍，袁远松[11]设计的6色DM码采取汉字的编码长度与使用频率成反比的编码规则，使得中国汉字的数据容量高于16色DM码，但压缩比例最大的中国汉字模式的数据容量也仅为黑白QR码的1.76倍。HCCB码由于利用调色板来纠正彩色码的偏色问题，调色板作为彩色码的组成部分却不能用来编码数据信息，因此4色、8色的HCCB码的数据容量略小于黑白QR码的2倍、3倍。10色MMCC码的数据容量也仅为黑白QR码的4倍。4色、8色、16色的HCC2D码的数据容量分别是黑白QR码的2倍、3倍、4倍。而本文经过GZIP压缩算法后4色QR码的数据容量与黑白QR码相比较，数字模式、字母数字模式、8位字节模式、中国汉字模式的数据容量分别扩充了 58.38倍、95.83倍、139.53倍、105.54倍。16色QR码的数据容量与黑白QR码相比较，数字模式、字母数字模式、8位字节模式、中国汉字模式的数据容量分别扩充了118.57倍、195.16倍、284.19倍、222.98倍。

表2 多种二维码最大数据容量比较

由此可见，本文设计的彩色QR码的数据容量与同类型的彩色码相比，数据容量有明显的优势，且随着颜色种类的增多，数据容量方面的优势会更加明显。

2.2 计算复杂度

彩色条码相同的颜色模块在不同光照下呈现的颜色不一样，主流的彩色条码为了解决偏色问题，将包含所有编码颜色的调色板嵌入到条码本身，并假定调色板和颜色模块在不同光照下的颜色变化是相对一致的，解码时将每一个颜色模块与调色板中的颜色相比较，将欧式距离最小的颜色值视为最终解码的颜色值，因此计算复杂度大幅增加。当调色板出现损毁、调色板和颜色模块处于不均匀的光照下时，均会导致解码失败。

为了降低计算复杂度，提高数据容量和解码正确率，本文设计的彩色QR码不进行偏色处理。将编码后的彩色QR码保存为PNG格式，无损压缩的图片格式才能确保遍历彩色QR码时，精确识别每一个颜色模块的RGB值，也正是因为如此，编码颜色可以任意选取，才能利用Gzip的无损压缩算法来提高数据容量。主流的彩色码为了支持纸质档的扫描，将编码后的彩色码保存为JPEG的有损压缩格式，而压缩算法在量化过程中会造成颜色信息的丢失，导致解码鲁棒性大幅降低。

3 总结

本文设计的彩色QR码通过增加编码颜色和Gzip的压缩算法来提高数据容量，实验表明，16色QR码数字模式、字母数字模式、8位字节模式、中国汉字模式的数据容量分别为黑白QR码的118.57倍、195.16倍、284.19倍、222.98倍，数据容量跟同类型的彩色码相比有明显的优势，且编码颜色可以任意选取，解码鲁棒性不会随着环境光照的变化而降低，省去了主流彩色码的颜色纠正步骤，因此计算量大幅降低。

[1]CHEOL-HO C，EUN-DONG S，NAM-KYU L，et al．Machine readable code image and method of encoding and decoding the same：United States，7020327[P].2002-03-07.

[2]ONODA T，MIWA K.Hierarchised two-dimensional code，creation method thereof，and read method thereof[J].Available at Japan Patent Office，2005，213336.

[3]Microsoft Research.High Capacity Color Barcodes.[EB/OL].(2007-03-19)[2010-5-15].http：//research.microsoft.com/projects/hccb/.

[4]KATO H，TAN K T，CHAI D.Novel colour selection scheme for 2D barcode[C].Proceedings of the 2009 Inter national Symposium on Intelligent Signal Processing and Communication Systems(ISPACS 2009).Kanazawa，2009：529-532.

[5]BULAN O，MONGA V，SHARMA G.High capacity color barcodes using dot orientation and color separability[C].Proceedings of SPIE on Media Forensics and Security.San Jose，2009：725417.

[6]QUERINI M，GRILLO A，LENTINI A，et al.2D color barcodes for mobile phones[J].International Journal of Computer Science and Applications(IJCSA)，2011，8(1)：136-155.

[7]CROSSING Z.Multi-format 1d/2d barcode image processing library with clients for android[EB/OL].[2012-03-21].http：//code.google.com/p/zxing/.

[8]FUKUCHI K.Libqrencode，a c library for encoding data in a qr code symbol[EB/OL].[2010-10-18].http：//megaui.net/fukuchi/works/qrencode/.

[9]汤维.32位压缩程序在64位平台上优化的研究与实现[D].西安：西安电子科技大学，2006.

[10]关涛.彩色Data Matrix条码的设计以及若干问题的研究[D].北京：清华大学，2007.

[11]贾华国，袁远松，刘志.一种面向汉字的高压缩比彩色二维条码的设计与实现[J].浙江工业大学学报，2010，38(05)：561-565.