二维码位流长度最小化算法  

Minimization of bit stream length of QR codes

作　　者：袁泰凌 徐昆 Yuan Tailing;Xu Kun(Department of Computer Science and Technology,Tsinghua University,Beijing100084,China;Key Laboratory of Pervasive Computing,Ministry of Education,Bejing100084,China)

机构地区：[1]清华大学计算机科学与技术系,北京100084 [2]普适计算教育部重点实验室,北京100084

出　　处：《中国图象图形学报》2022年第8期2356-2367,共12页Journal of Image and Graphics

基　　金：国家自然科学基金项目(61822204,61521002)。

摘　　要：目的 快速响应矩阵码(quick response code, QR code)简称二维码,是一种由深色和浅色模块组成的正方形符号。给定输入数据,不同编码算法可能输出不同的位流。位流长度决定了二维码的版本,进而决定了二维码每条边上的模块数量。减小二维码的版本能够在不减小模块大小的前提下节省面积,或者在不改变面积的前提下增大模块大小。为了减小二维码面积、提高二维码识读率,本文提出了位流长度最小化算法。方法 首先,根据二维码位流可以分段切换编码模式的特点,归纳了6种编码状态;然后,根据二维码位流编码标准推导了状态转移关系,从而将位流长度最小化问题转换成动态规划问题;最后,通过求解动态规划问题,计算出最短位流。针对统一资源定位符(uniform resource locator, URL)类型数据,利用其部分字段对大小写不敏感、部分字段可以转义的性质,提出了统一资源定位符的最短位流计算算法,进一步缩短位流。结果 本文构建了一个测试集,包含603个编码了非URL数据的二维码,以及1 679个编码了URL数据的二维码。实验结果表明,本文算法与二维码标准相比,对于非URL测试集,位流长度减小的二维码占比9.1%,版本减小的二维码占比1.2%;对于URL测试集,位流长度减小的二维码占比98.4%,版本减小的二维码占比31.7%。结论 二维码位流长度最小化算法输出的位流长度最短,输出的二维码版本最小,能在兼容标准二维码解码器且不影响纠错能力的前提下提升二维码的数据容量。同时,本文算法运行速度快,易于使用,没有需要调节的参数。Objective Quick response code(QR code) is a kind of widely used 2 D barcode nowadays. A QR code is a square symbol consisting of dark and light modules. There is a great need to accommodate more data in the target area or encode the same input data in a smaller area. The input data is first encoded into a bit stream. Different encoding algorithms may output different bit streams via assigned input data. The length of bit stream determines the version of a QR code, and the version determines the amount of modules per side. A QR code with a smaller version takes a smaller area without the size of modules changing, or has a larger module size without changing the area. The bit stream consists of one or multiple segments, and the encoding mode of each segment is chosen from three modes separately, i.e., numeric mode, alphanumeric mode and byte mode. The numeric mode can only encode digits, and every 3 digits are encoded into 10 bits. The alphanumeric mode can encode digits, upper case letters, and 9 kinds of punctuations, and every 2 characters are encoded into 11 bits. The byte mode can encode any kind of binary data, but each byte is encoded into 8 bits. Compared to using a single mode to encode the overall input data, different modes interchange may result in a shorter bit stream. But different modes switching leads to redundancy on bit stream length. Method The key to minimizing the version of QR code is to minimize the length of bit stream. The minimization should balance the redundancy of data encoding and the mode switching efficiency. The QR code specification gives “optimization of bit stream length” in annex. However, the illustration has proposed that the optimization method may not output the minimum bit stream. The demonstration has mentioned algorithms as below. The first algorithm is called “minimization algorithm”, which converts the minimization of bit stream length to a dynamic programming problem. The algorithm can output the bit stream with minimum length by resolving the dynamic programmi

关 键 词：二维码 快速响应矩阵码 二维码编码 动态规划 统一资源定位符(URL) 

分 类 号：TP391.4[自动化与计算机技术—计算机应用技术]