转载自&＃xff1a;琦小虾
https://blog.csdn.net/ajianyingxiaoqinghan/article/details/78837864#comments
二维码生成原理及解析代码

自从大街小巷的小商小贩都开始布满了腾讯爸爸和阿里爸爸的二维码之后&＃xff0c;我才感觉到我大天朝共享支付的优越性。最近毕业论文写的差不多了&＃xff0c;在入职之前多学一些东西也是好的。这里秉着好奇心&＃xff0c;研究一下二维码的生成&＃xff0c;并尝试性写一个二维码解析源码。

注&＃xff1a;暂时只有二维码原理&＃xff0c;笔者这段时间会持续研究解析代码&＃xff0c;并随进度持续更新。

参考网址&＃xff1a;
《二维码的生成细节和原理》
《QR Code Tutorial》
《Hello World!》—— 知乎专栏文章
《为程序员写的Reed-Solomon码解释》

一. 二维码基本知识

二维码另一个名称是QR Code(Quick Response Code)&＃xff0c;近年来在移动设备上经常使用&＃xff0c;与传统条形码相比&＃xff0c;可以存储更多的信息。二维码本质上是个密码算法&＃xff0c;基本知识总结如下。
首先&＃xff0c;二维码存在 40 种尺寸&＃xff0c;在官方文档中&＃xff0c;尺寸又被命名为 Version。尺寸与 Version 存在线性关系&＃xff1a;Version 1 是 21×21 的矩阵&＃xff0c;Version 2 是 25×25 的矩阵&＃xff0c;每增加一个 Version&＃xff0c;尺寸都会增加 4&＃xff0c;故尺寸 Size 与 Version 的线性关系为&＃xff1a;

Version 的最大值是 40&＃xff0c;故尺寸最大值是(40-1)*4&＃43;21 &＃61; 177&＃xff0c;即 177 x 177 的矩阵。

二维码结构如下图 1.1 所示&＃xff1a;

图6.7 时序图案例程 2

6.4 格式信息

格式信息如下图 6.8 所示&＃xff1a;

图6.8 格式信息

格式信息在定位图案周围分布&＃xff0c;由于定位图案个数固定为 3 个&＃xff0c;且大小固定&＃xff0c;故格式信息也是一个固定 15bits 的信息。每个 bit 的位置如下图 6.9 所示&＃xff1a;&＃xff08;注&＃xff1a;图中的 Dark Module 是固定永远出现的&＃xff09;

图6.9 格式信息位置

15bits 中数据&＃xff0c;按照 5bits 的数据位 &＃43; 10bits 纠错位的顺序排列&＃xff1a;

• 数据位占 5bits&＃xff1a;其中 2bits 用于表示使用的纠错等级 (Error Correction Level)&＃xff0c;3bits 用于表示使用的蒙版 (Mask) 类别&＃xff1b;
• 纠错位占 10bits&＃xff1a;主要通过 BCH Code 计算&＃xff1b;

为了减少扫描后图像识别的困难&＃xff0c;最后还需要将 15bits 与 101010000010010 做异或 XOR 操作。因为我们在原格式信息中可能存在太多的 0 值&＃xff08;如纠错级别为 00&＃xff0c;蒙版 Mask 为 000&＃xff09;&＃xff0c;使得格式信息全部为白色&＃xff0c;这将增加分析图像的困难。

纠错等级的编码如下图 6.10 的表格所示&＃xff1a;

图6.10 纠错等级编码

关于蒙版图案的生成&＃xff0c;在后文 6.7 中具体说明。格式信息的示例如下&＃xff1a;

假设存在纠错等级为 M&＃xff08;对应 00&＃xff09;&＃xff0c;蒙版图案对应 000&＃xff0c;5bits 的数据位为 00101&＃xff0c;10bits 的纠错位为 0011011100&＃xff1a;
则生成了在异或操作之前的 bits 序列为&＃xff1a;001010011011100
与 101010000010010 做异或 XOR 操作&＃xff0c;即得到最终格式信息&＃xff1a;100000011001110

6.5 版本信息 (Version Information)

对于 Version 7 及其以上的二维码&＃xff0c;需要加入版本信息。如下图 6.11 蓝色部分所示&＃xff1a;

图6.11 版本信息

版本信息依附在定位图案周围&＃xff0c;故大小固定为 18bits。水平竖直方向的填充方式如下图 6.12 所示&＃xff1a;

图6.12 版本信息填充方式

18bits 的版本信息中&＃xff0c;前 6bits 为版本号 (Version Number)&＃xff0c;后 12bits 为纠错码 (BCH Bits)。示例如下&＃xff1a;

假设存在一个 Version 为 7 的二维码&＃xff08;对应 6bits 版本号为 000111&＃xff09;&＃xff0c;其纠错码为 110010010100&＃xff1b;
则版本信息图案中的应填充的数据为&＃xff1a;000111110010010100

6.6 数据码与纠错码

此后即可填充第五章得到的数据内容了。填充的思想如下图 6.13 的 Version 3 二维码所示&＃xff0c;从二维码的右下角开始&＃xff0c;沿着红线进行填充&＃xff0c;遇到非数据区域&＃xff0c;则绕开或跳过。

图6.13 二维码数据填充&＃xff08;原始版&＃xff09;

然而这样难以理解&＃xff0c;我们可以将其分为许多小模块&＃xff0c;然后将许多小模块串连在一起&＃xff0c;如下图 6.14 所示&＃xff08;截取自 QR Code Spec 的图 15&＃xff09;&＃xff1a;

图6.14 二维码数据填充

小模块可以分为常规模块和非常规模块&＃xff0c;每个模块的容量都为 8。常规情况下&＃xff0c;小模块都为宽度为 2 的竖直小矩阵&＃xff0c;按照方向将 8bits 的码字填充在内。非常规情况下&＃xff0c;模块会产生变形。
填充方式上图 6.14&＃xff0c;图中深色区域&＃xff08;如 D1 区域&＃xff09;填充数据码&＃xff0c;白色区域&＃xff08;如 E15 区域&＃xff09;填充纠错码。遍历顺序依旧从最右下角的 D1 区域开始&＃xff0c;按照蛇形方向&＃xff08;D1→D2→…→D28→E1→E2→…→E16→剩余码&＃xff09;进行小模块的填充&＃xff0c;并从右向左交替着上下移动。下面给出若干填充原则&＃xff1a;

原则 1&＃xff1a;无论数据的填充方向是向上还是向下&＃xff0c;常规模块&＃xff08;即 8bits 数据全在两列内&＃xff09;的排列顺序应是从右向左&＃xff0c;如下图 6.15所示&＃xff1b;

图6.15 常规模块内的填充方向

原则 2&＃xff1a;每个码字的最高有效位&＃xff08;即第7个bit&＃xff09;应置于第一个可用位。对于向上填充的方向&＃xff0c;最高有效位应该占据模块的右下角&＃xff1b;向下填充的方向&＃xff0c;最高有效位占据模块的右上方。
注&＃xff1a;对于某些模块&＃xff08;以下图 6.17 为例&＃xff09;&＃xff0c;如果前一个模块在右边模块的列内部结束&＃xff0c;则该模块成为不规则模块&＃xff0c;且与常规模块相比&＃xff0c;原本填充方向向上时&＃xff0c;最高位应该在右上角&＃xff0c;此时则变为左下角&＃xff1b;
原则 3&＃xff1a;当一个模块的两列同时遇到对齐图案或时序图案的水平边界时&＃xff0c;它将继续在图案的上方或下方延续&＃xff1b;
原则 4&＃xff1a;当模块到达区域的上下边界&＃xff08;包括二维码的上下边界、格式信息、版本信息或分隔符&＃xff09;时&＃xff0c;码字中任何剩余 bits 将填充在左边的下一列中&＃xff0c;且填充方向反转&＃xff1b;如下图 6.16 中的两个模块遇到了二维码的上边界&＃xff0c;则方向发生变化&＃xff1b;

图6.16 非常规模块填充方向的改变&＃xff08;举例于 QR Code Spec 图 13&＃xff09;

原则 5&＃xff1a;当模块的右一列遇到对齐图案&＃xff0c;或遇到被版本信息占据的区域时&＃xff0c;数据位会沿着对齐图案或版本信息旁边的一列继续填充&＃xff0c;并形成一个不规则模块。如果当前模块填充结束之前&＃xff0c;下一个的两列都可用&＃xff0c;则下一个码字的最高有效位应该放在单列中&＃xff0c;如下图 6.17 所示&＃xff1a;

图6.17 模块单列填充

6.7 蒙版图案

按照上述思路即可将二维码填充完毕。但是那些点并不均衡&＃xff0c;如果出现了大面积的空白或黑块&＃xff0c;扫描识别会十分困难&＃xff0c;所以按照在前文 6.4 中格式信息的处理思路&＃xff0c;对整个图像与蒙版进行蒙版操作(Masking)&＃xff0c;蒙版操作即为异或 XOR 操作。
二维码又 8 种蒙版可以使用&＃xff0c;如下图 6.18 所示&＃xff0c;公式也在图中说明。蒙版只会和数据区进行异或操作&＃xff0c;不会影响与格式信息相关的功能区。
注&＃xff1a;选择一个合适的蒙版也是有一定算法的。

蒙版图案如下图 6.18 所示&＃xff0c;对应的产生公式与蒙版 ID 如下图 6.19 的表格所示&＃xff1a;

图6.18 蒙版图案

图6.19 蒙版图案产生公式

蒙版操作的过程与对比图如下图 6.20 所示&＃xff0c;图中最上层是没有经过蒙版操作的原始二维码&＃xff0c;其中存在大量黑色区域&＃xff0c;难以后续的分析识别。经过两种不同蒙版的处理&＃xff0c;可以看到最后生成的二维码变的更加混乱&＃xff0c;容易识别。

图6.20 蒙版操作示例

蒙版操作之后&＃xff0c;得到的二维码即为最终我们平常看到的结果。

七. 源码

笔者原本准备用 C&＃43;&＃43; 与 OpenCV 写一个二维码解析程序&＃xff0c;现在学了二维码的原理后&＃xff0c;发现好难。另外网上关于二维码解析与生成的程序基本都是用 Python 写的&＃xff0c;笔者又想找个合适机会学习一下 Python&＃xff0c;所以这段时间就准备从二维码入手&＃xff0c;学习一下 Python 的基础&＃xff5e;

源码及解析笔者会随学习的进度持续更新&＃xff5e;

八. 后记

笔者学习完毕二维码内容后不禁感叹&＃xff0c;二维码规则的制定当真是凝聚了多少研究者的心血。学无止境&＃xff0c;在知识的海洋中&＃xff0c;当真是需要抱着敬畏之心和谦卑的态度&＃xff0c;才能体会到这片海洋的浩瀚。
研究二维码的过程十分有趣&＃xff0c;学到了不少东西&＃xff0c;后续过程中笔者会持续更新对二维码的学习心得体会&＃xff5e;