QR 码(快速响应码)是 QR 码的一种。它将带有黑白标记的二进制位编码在方形两位数矩阵中以对数据进行编码。它最初是为了跟踪日本汽车制造业的零件而发明的。目前二维码有40个标准版本和4个微型版本。 QR 码中有四种数据编码方式:
QR 码有四种容错级别可供选择:
参考:Hello World! - 知乎(www.sychzs.cn)
上图为二维码的基本结构。
二维码基本上分为两部分。其中,功能模式主要包含定位信息,编码区域主要包含数据信息(包括纠错码和数据信息)。
功能模式
定位信息好像没有容错码? ? ?
安静区
这是一个空格。标准规定,QR码(Ver1-40)应被4个单位宽包围,微型QR码应被2个单位宽的区域包围,颜色相当于QR码中的白点。其中不应有任何图案或任何标记,以确保 QR 码清晰可辨。
寻找伙伴
定位标记其实是“徽”字形,位于二维码的左上角、左下角、右上角(只有三个)。用于辅助扫描软件定位二维码并变换坐标系。定位标记允许以任意角度扫描二维码,这是一维条码无法实现的。 (如果二维码是其他形状,那么需要那么多定位码??这些定位码的存在导致二维码编码信息利用率很低,而且图案看起来很复杂。需要思考仔细想想这个坐标系的定位和变换是如何实现的)。
分隔符
分隔符是一个单位宽的白点带,位于每个锚标记和编码区域之间,用于区分它们。
时序模式
正时标记是一个单位宽的黑白点交替条带,以黑色开始和结束。用于指示密度和确定坐标系。
对齐图案
修正标记仅适用于版本2及以上的QR码。校正标志用于进一步校正坐标系。修正标记的数量取决于版本。
编码模式
格式信息
格式信息存储了容错级别和数据掩码,还包含附加的自己的BCH容错代码。
版本信息
版本信息中存储版本信息
数据和纠错码字
数据和容错码存储数据的编码方式、实际码数和RS容错码。
上图为版本1的二维码图片。
将数据转换成二维码的过程:
1.数据分析:分析输入数据,根据数据决定使用哪种二维码版本。容错级别和编码方式。低版本的二维码无法编码太长的数据,包含非数字字母字符的数据必须使用扩展字符编码模式。
2.编码数据(数据编码):根据选择的编码模式将输入字符串转换为比特流,插入模式指示符(mode Indicator)和终止符(terminator),分割将比特流分解为8位字节,并添加填充字节以满足标准数据字数(需要仔细检查数据编码规则)。
3.计算纠错编码(error Correctioncoding):为步骤2中生成的码流计算容错码,并将其附加到码流中。更高版本的编码方法可能需要将数据流分成块,然后分别进行容错代码计算。
4.整理数据(结构最终消息):根据结构图拆分步骤3中得到的容错数据流。准备填充。
5.填充(模块在矩阵中的放置) :根据标准将数据和功能模式填充到矩阵中。
6.应用数据屏蔽:应用标准中的八个数据屏蔽对编码区的数据进行转换,并选择最佳的屏蔽应用。
7.填写格式和版本信息(格式和版本信息):计算格式和版本信息并填写矩阵,完成二维码。
QR 支持以下代码:
Numeric 模式(数字编码):从 0 到 9。如果要编码的数字个数不是 3 的倍数,则最后剩余的 1 或 2 位将转换为 4 或 7 位,其余每3位将转换为10、12、14位,长度取决于二维码的大小。 (如下标表3)(为什么是这个格式?变成几个Bit是什么?)
字母数字模式(字符编码):包括 0-9、大写 A 到 z(无小写)以及符号 $ % * + - 。 /:包括空格。这些字符将被映射到一个字符索引表中。如下图:(其中SP为空格,然后char为字符,Value为其索引值)编码过程是将字符成对分组,然后将其转换为下表中的45位系统,然后转换为11bits二进制。如果最后是一个人的话,就会转成6bits。编码方式和字符数需要根据不同的 Version 大小编译成 9、11、13 个二进制(如下表)
字节模式(字节编码):可以是从0-255的ISO-8859-1字符。有些二维码扫描器可以自动检测是否是UTF-8编码。
Kanji mode(日语编码):这是日语编码,也是双字节编码。同样可以用于中文编码。日文编码和汉字编码会减去一个值。例如:0X8140到0X9FFC中的字符会减去8140,0XE040到0XEBBF中的字符会减去0XC140,然后取出结果的前两位十六进制数字乘以0XC0,然后加上最后两个16。十六进制数字最终转换为13位编码。如下图所示:
下面两张表中,
以下是一些编码示例:
示例1:数字编码
在Version1大小下,纠错码级别为H,编码:01234567
1。将以上号码分为三组:012 345 67
2。将它们转换为二进制:012转换为0000001100(10位代码); 345转换为0101011001; 67 转换为 1000011(7 位)
3。将这三个二进制代码串在一起: 0000001100 0101011001 1000011
4。将位数转换为二进制(version-1-H为10bits):8位二进制为0000001000
5。在前面添加数字编码标志(格式信息)0001和步骤4的编码:0001 0000001000 00000011000101011001 1000011
示例2:字符编码
版本1尺寸中,纠错码级别为H,编码AC-42
1。从字符表中查找五个 AC-42 条目的索引 (10, 12, 41, 4, 2)
2。按两个分组: (10, 12) (41, 4) (2)
3。将每组转换成11bits二进制(这一步不是很清楚):
(10, 12) 10*45+12=462 转换为 00111001110 (11 位)
(41, 4) 41*45+4=1849 转换为 11100111001
(2)等于2,转换为000010(阶数转换为6位)
4。连接这些二进制文件: 00111001110 11100111001 111101
5。将字符数转换成二进制(version1-H位9bits):5个字符,5转换成000000101
6。在头部添加编码标识(格式信息)0010和第5步编码的编号:0010 000000101 0011100111011100111001 000010
终止符和完成符
假设我们有一个 HELLO WORLD 字符串要编码。根据上面的第二个例子,我们可以进行如下操作:
编码 | 字符数 | HELLO WORLD编码1111000110 10001011100 10110111000 10011010100 001101 |
编码 | 字符数 | HELLO WORLD的编码 | End |
0010 | 000001011 | 01100001011 01111000110 10001011100 1 011 0111000 10011010100 001101 | 0000 |
重新排列8位
如果所有代码的和不是8的倍数,我们必须在末尾添加足够的0。比如一共有78位,那么我们就得加上2个0,然后按8位分组:
00100000 01011011 00001011 01111000 11010001 01110010 11011100 01001101 01000011 010000 00
完整代码
最后,如果我们还没有达到最大位数的限制,我们必须添加一些填充字节。填充码是重复两个字节:11101100 00010001(两个字节都是8位,这两个二进制码换算成十进制分别是236和17原因???)关于每个字节的最大位数限制各版本的纠错级别请参考QR码规格表7第1章第28至32页。
假设我们需要编码的是版本1的Q纠错级别,那么最多需要104位,而我们上面只有80位,所以需要添加24位, 也。它需要 3 个填充字节,因此我们添加 3 个,因此我们得到以下编码:
00100000 01011011 00001011 01111000 11010001 01110010 11011100 01001101 01000011 01000000 1 1101100 00010001 11101100
上面的编码就是数据代码,称为Data Codewords。每8bits称为码字。我们还需要给这些数据添加纠错码信息。
纠错码
有了纠错机制,即使二维码不完整也能被扫描解析,并且有些商家可以利用二维码的中心添加解析不需要的图标。
QR 码有四种纠错级别:
纠错级别 | 可纠错容量 |
L | 7%码字 |
M | 15%码字 |
Q | 25%码字 |
H | 30% 码字 |
通过二维码给数据添加纠错码的过程,首先必须将数据代码分组为,即分为不同的块。 分组要求如下表:
表中最后两列的内容:
纠错块数(纠错块数) | 需要划分的纠错块数 |
每个块的纠错码字数(每个块的纠错码) | 每个块中的码字数,即有多少个字节 |
表底关于(c,k,r)的解释:
c | 总码字数 |
k | 数据码数 |
r | 纠错码容量 |
注:
c,k,r的关系式:
纠错码容量小于纠错码数量的一半
以上图4.1中版本5+H纠错机制为例:图中红框所示,总共需要4个块(一组上下两排各1块,每组2块)。
第一组属性:
纠错块数量=2 | 该组中有两个纠错块 |
(c,k,r)=(33,11,11) | 该组中有两个纠错块这组33个码字,其中11个数据码,11*2=22个纠错码块 |
具体示例如下表所示,由于使用二进制会使表格太大,所以转换为0~255范围内的十进制。第1组的每个块有11个数据码和22个纠错码;第2组的每个块有12个数据码和22个纠错码。
组 | 块 | 数据 | 每个块的纠错码 |
1 | 1 2 | 67 85 70 134 87 38 85 194 119 50 6 66 7 118 134 242 7 38 86 22 198 199 | 199 11 45 115 247 241 223 229 248 154 117 236 38 6 50 17 7 236 213 87 148 235 177 212 76 133 75 242 238 76 195 230 189 106 248 134 76 40 154 27 195 255 117 129 |
1 | 1 2 | 247 119 50 7 118 134 87 38 82 6 134 151 194 6 151 50 16 236 17 236 17 236 17 236 | 96 60 202 182 124 157 200 134 27 129 209 182 70 85 246 230 247 70 66 247 118 134 173 24 147 59 33 106 40 255 172 82 2 157 242 33 229 200 238 106 248 134 76 40 |
二维码的纠错码主要通过Reed-Solomon纠错算法实现
此时数据已经获取,但是无法开始绘图,因为二维码还需要交替数据和纠错码的字节。
继续以上一章给出的例子为例,给出穿插放置的过程。
上一章示例中的数据代码如下表所示:
区块数量 | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
区块1 | 67 | 85 | 70 | 134 | 87 | 38 | 85 | 194 | 119 | 50 | 6 |
区块2 | 66 | 7 | 118 | 134 | 242 | 7 | 38 | 86 | 22 | 198 | 199 |
区块3 | 247 | 119 | 50 | 7 | 118 | 134 | 87 | 38 | 82 | 6 | 134 |
区块4 | 194 | 6 | 151 | 50 | 16 | 236 | 17 | 236 | 17 | 236 | 17 |
提取每列数据:
将上面十二列的数据放在一起:67, 66, 247, 194, 85, 7, 119, 6,…, 6, 199, 134, 17, 151, 236。
纠错码如下表所示:
区块数量 | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
区块1 | 199 | 11 | 45 | 115 | 247 | 241 | 223 | 229 | 248 | 154 | 117 |
区块2 | 177 | 212 | 76 | 133 | 75 | 242 | 238 | 76 | 195 | 230 | 189 |
区块3 | 96 | 60 | 202 | 182 | 124 | 157 | 200 | 134 | 27 | 129 | 209 |
区块4 | 173 | 24 | 147 | 59 | 33 | 106 | 40 | 255 | 172 | 82 | 2 |
用同样的方法,将22列数据放在一起:199, 177, 96, 173, 11, 212, 60, 24, …, 148, 117, 118, 76, 235, 129, 134, 40。
以上部分为二维码的数据区(数据码和纠错码)
对于某些版本的二维码,上述数据区结果的长度仍然不够,需要添加最后剩余的位。例如,对于Version 5+H纠错级别QR码,需要在剩余比特的基础上增加7个比特,即需要添加7个0。参考QR Code Spec表1查询不同版本的剩余位信息,如下图5.1所示
首先在二维码的三个角上画出定位图案。定位图案与大小无关,必须是7×7的矩阵。如下图6.1所示:
xODIyMTMyOTU5OD93YXRlcm1hcmsvMi90ZXh0L2FIUjBjRG 92TDJKc2IyY3VZM05rYmk1dVpYUXZZV3BwWVc1NWFXNW5lR2xoYjNGcGJtZG9ZVzQmIzYxOy9mb250LzVhNkw1TDJUL2Z vbnRzaXplLzQwMC9maWxsL0kwSkJRa0ZDTUEMIZYxOyYj NjE7L2Rpc3NvbHZlLzcwL2dyYXZpdHkvU291dGhFYXN0/}
需要绘制对齐图案。对齐图案与大小无关,必须是5*5的矩阵。如下图:
IyMTQwMTMwNT93YX Rlcm1hcmsvMi90ZXh0L2FIUjBjRG92TDJKc2IyY3VZM05rYmk1dVpYUXZZV3BwWVc1NWFXNW5lR2xoYjNGcGJtZG9ZVzQmIzYxOy9mb250LzVhNkw1TDJUL2Zv bnRzaXplLzQwMC9ma WxsL0kwSkJRa0ZDTUEmIzYxOyYjNjE7L2Rpc3NvbHZlLzcwL2dyYXZpdHkvU291dGhFYXN0/}
对准图案图的位置请参考QR Code Spec 的表-E.1。部分内容如下图6.3所示:
(版本 2 及以上版本需要对齐图案)
下图是上表中版本8的示例。对于version8的二维码,会在几个点上出现行列值为6、24、42的对齐图案。
Xh0L2FIUjBjRG92TDJKc2IyY3VZM05rYm k1dVpYUXZZV3BwWVc1NWFXNW5lR2xoYjNGcGJtZG9ZVzQmIzYxOy9mb250LzVhNkw1TDJUL2ZvbnRzaXplLzQwMC9maWxsL0kwSkJRa0Z DTUEmIzYxOyYjNjE7L2Rpc3NvbHZlLzc wL2dyYXZpdHkvU291dGhFYXN0/}
小时图案是连接三个定位图案的两条线,如下图:
支付宝付款码如下:
格式信息如下:
格式信息分布在定位图案周围。由于定位图案具有固定的3比特数和固定的大小,因此格式信息也是固定的15bits信息。各位的位置如下:(注:图中深色模块始终出现)
15 位数据。按5bits数据位+10bits纠错位的顺序排列:
数据位占用5位:2位用于表示使用的纠错级别(纠错级别),3位用于表示使用的掩码类别 ;
纠错位占10位:主要通过BCH码计算。
为了降低扫描后图像识别的难度,最终需要将这15bits与101010000010010进行异或。因为我们原始格式信息中可能有太多的0值(例如纠错级别为00,掩码为000),使格式信息全白,这会增加分析图像的难度。
纠错级别编码如下:
格式信息示例如下:
假设纠错级别为 M(对应 00),掩码模式对应 000,5bits 数据位为 00101,10bits 纠错位为 0011011100:
那么 XOR 之前的比特序列将001010011011100
与101010000010010进行异或运算,得到最终的格式信息:100000011001110
对于版本7及以上的二维码,需要添加版本信息
版本信息附加在定位图案周围,因此大小固定为18bits。水平和垂直方向的填充方法如下图6.12所示:
18bits 的版本信息中,前 6bits 为版本号 (Version Number),后 12bits 为纠错码 (BCH Bits)。示例如下:
假设存在一个 Version 为 7 的二维码(对应 6bits 版本号为 000111),其纠错码为 110010010100;
则版本信息图案中的应填充的数据为:000111110010010100
(但凡是填充的数据,都包含纠错码)
然后就可以进行数据填充了。 填充的思想如下version3二维码所示,从二维码右下角开始,沿着红线进行填充,遇到非数据区域,则绕开或跳过。
然而这样难以理解,我们可以将其分为许多小模块,然后将许多小模块串连在一起,如下图 6.14 所示(截取自 QR Code Spec 的图 15):
小模块可以分为常规模块和非常规模块,每个模块的容量都为8.常规情况下,小模块都为宽度为2的竖直小矩阵,按照方向将8bits的码字填充在内。非常规情况下,模块会产生变形。
填充方式如上所示,图中深色区域(如 D1区域)填充数据码,白色区域(如E15区域)填充纠错码。遍历顺序依旧是从最右下角的D1区域开始,按照蛇形的方向D1→D2→…→D28→E1→E2→…→E16→剩余码)进行小模块的填充,并从右向左交替着上下移动。下面给出若干填充原则:
原则1:无论数据的填充方向是向上还是向下,常规模块(即8bits数据全在两列内)的排列顺序应该是从右向左(这个填充方向有问题吧,该是从左到右吧),如下所示:
原则2:每个码字的最高有效位(即第7个bits)应置于第一个可用位。对于向上填充的方向,最高有效位应该占据模块的右下角;向下填充的方向,最高有效位应该占据模块的右上方(排列方向就应该是从右往左啊)。
注:对于默写模块(如下图所示),如果前一个模块的右边模块的列内部结束,则该模块成为不规则模块,且与常规模块相比,原本填充方向向上时,最高位应该在右下角。此时变成左下角。
原则3:当一个模块的两列同时遇到对齐图案或时序图案的水平边界时,它将继续在图案的上方或者下方延续。
原则 4:当模块到达区域的上下边界(包括二维码的上下边界、格式信息、版本信息或分隔符)时,码字中任何剩余 bits 将填充在左边的下一列中,且填充方向反转;如下图中的两个模块遇到了二维码的上边界,则方向发生变化;
原则 5:当模块的右一列遇到对齐图案,或遇到被版本信息占据的区域时,数据位会沿着对齐图案或版本信息旁边的一列继续填充,并形成一个不规则模块。如果当前模块填充结束之前,下一个的两列都可用,则下一个码字的最高有效位应该放在单列中。
按照上述思路即可将二维码填充完毕。但是那些点并不均衡,如果出现了大面积的空白或黑块,扫描识别会十分困难,所以按照在前文 6.4 中格式信息的处理思路,对整个图像与蒙版进行蒙版操作(Masking),蒙版操作即为异或 XOR 操作。
二维码又 8 种蒙版可以使用,如下图 6.18 所示,公式也在图中说明。蒙版只会和数据区进行异或操作,不会影响与格式信息相关的功能区。
注:选择一个合适的蒙版也是有一定算法的.
蒙版图案如下图所示。
对应的产生公式与蒙版 ID 如下面的表格所示:
蒙版操作的过程与对比图如下图所示,图中最上层是没有经过蒙版操作的原始二维码,其中存在大量黑色区域,难以后续的分析识别。经过两种不同蒙版的处理,可以看到最后生成的二维码变的更加混乱,容易识别 。
蒙版操作之后,得到的二维码即为最终我们平常看到的结果。