射频识别(RFID)技术

快速响应矩阵码(上)

作者:陈广 日期:2019-10-11


关于二维码,我查了下资料,现在基本都在用日本的 QR 码,PDF417以及汉信码日常基本看不到。原因在于各方面来说,的确是 QR 码最为优秀。所以我准备写一篇介绍 QR 码的文章,如果是写书,可能不方便写得这么详尽,但如果是网上的文章,就可以自由发挥了。写完这篇文章,再抽取部分内容正规化,并整合其它内容形成书的第四章。为方便未来上课讲解方便,以及快速画图,我还做了一个《QR助手程序》,帮助绘制 QR 码中的各部分图形,最后演化成一个二维码绘制程序。本来并未打算要自己写二维码绘制程序的,网上有很多现成的开发包。但一方面为了让自己更熟悉二维码,另一方面,用实现一个简单的二维码绘制程序让学生参考,可以有效降低学生的学习门槛。

QR 码是日本发明的一种二维码,也是目前应用最为广泛的编码。在中国,这种编码几乎无处不在,微信支付、支付宝支付、共享单车、各种广告扫描关注等等。

QR 码的特点

  1. 存储容量大 传统的条形码只能处理 20 位左右的信息,与此相比,QR 码则可处理几十倍上百倍的信息。另外,QR 码还可以支持所有类型的数据(如:数字、英文字母、日文字母、汉字、二进制、控制码等)。一个 QR 码最多可处理 7089 个数字的巨大信息量。

  2. 占用空间小 QR 码使用纵向和横向两个方向处理数据,相同的信息量,QR 码所占空间更小。下图分别是 GS1 编码 (02)66901234000049(17)050101(37)10(10)ABC的 GS1-128 编码和 QR 码图形。我先在屏幕上绘制图形,然后使用扫码枪扫描,接下来缩小图形,直到扫码枪认不出为止。最后等比例放大,得到下面绘制面积对比。

  1. 纠错能力强 QR 码具备“纠错功能”,即使部分编码变脏或破损,也可以恢复数据。数据恢复以码字为单位(是组成内部数据的单位,在QR码的情况下,每8比特代表1码字),最多可以纠错约30%(根据变脏和破损程度的不同,也存在无法恢复的情况)。

  2. 可以从任意方向读取 QR码从360°任一方向均可快速读取。QR码中在 3 个定位图案,可以帮助QR码不受背景样式的影响,实现快速稳定的读取。传统激光扫码枪在扫描条码时,只能使用一个方向进行扫描,但如果使用的是 CCD 扫描枪,则可以从任一方向扫描条码。

QR 码的结构

一个 QR 码可以分为两个部分:功能图形和编码区域。

功能图形起到定位和校正图形的作用,数据区记录了具体的数据信息、纠错信息和版本信息。

QR 码符号版本和规格

QR 码符号共有 40 种规格,分别为版本1、版本2……版本40。版本 1 的规格为21模块×21模块,版本 2 的规格为25模块×25模块,以此类推,每一版本符号比前一版本每边增加4个模块,直到版本40(规格为177模块×177模块)。

由上图可知,版本1图形被划分为21×21个小方块,模块指的就是这些小方块,是 QR 码绘制的最小单元,在绘制 QR 码时,将存在数据的模块填充为深色,最终组成 QR 码图形。下图是版本40的模块图,由177×177个小方块组成。

寻像图形

寻像图形包括三个相同的位置探测图形,分别位于二维码左上角、右上角、左下角,每个位置探测图形由7×7个模块组成如下图所示:

符号中其他地方遇到类似图形的可能性极小,因此可以在视场中迅速地识别可能的 QR 码符号。识别组成寻像图形的三个位置探测图形,可以明确地确定视场中符号的位置和方向。下图是版本1和版本6的寻像图形,由图可知,版本号越高,寻像图形在整个图案中所占比例越小。

位置探测图形分隔符

为方便识别位置探测图形,在每个位置探测图形和编码区域之间有宽度为 1 个模块的分隔符,如下图黄色区域所示。此区域应全为空白,不能填入数据。

定位图形

水平和垂直定位图形分别为一个模块宽的一行和一列,由深色与浅色模块交替组成,其开始和结尾都是深色模块。水平和垂直定位图形分别位于第6行和第6列(行、列由0开始计数),并且避开位置探测图形。它们的作用是确定符号的密度和版本,提供决定模块坐标的基准位置。下图是绘制了定位图形后的版本1和版本6图案。

校正图形

校正图形作为一个固定的参照图形,在图像有一定程度损坏的情况下,译码软件可以通过它同步图像模块的坐标映像。每个校正图形由5×5模块组成。如下图所示:

校正图形的数量视符号和版本号而定,版本1没有校正图形,版本2及以上均含有校正图形。校正图形的数量视 QR 码的版本号而定。下表列出了前14个版本的数据,完整数据请查看国家标准 GB/T 18284-2000 中的附录 E。

下面讲讲如何看懂中心模块的行/列坐标值。例如在版本 7 中,表中给出值 6、22 和 38。则校正图形的中心点位置行、列坐标为(6,22)(22,6)(22,22)(22.38)(38,22)(38,38)。由于坐标(6,6)(6,38)(38,6)坐标位置被位置探测图形占据,因此,这些坐标位置没有放置校正图形。说白了就是将中心模块的行/列坐标值中的每个值分别与自己及其他值组成坐标,然后删除左上、右上、左下坐标,即得出结果。

下图是版本 1 及版本 7 的校正图形:

下图是版本 15 及版本 40 的校正图形:

没有固定公式计算中心模块的行/列坐标值,但观察以上 4 张校正图形,可以发现,QR 码设计者在选择坐标值时,使得第一行和第一列校正图形正好融合进定位图形,不会使定位图形遭到破坏。

数据编码

各种用于图像识别的功能图形已经安放完毕,下一步就是对数据进行编码了。标准 QR 码可编码数据类型有四种:数字、字母数字、8位字节和 Kanji,其中 Kanji 为日文日文字符。我们国家标准 GB/T 18284-2000 增加了 QR 码的表示范围。下表是 QR 码可表示的数据类型及其相应的模式指示符。

模式 指示符 模式 指示符
ECI 0111 日文 1000
数字 0001 中文 1101
字母数字 0010 FNC1 0101(第一位置)
8位字节 0100 FNC1 1001(第二位置)
表 1:模式指示符

ECI 是什么东西,我很想搞懂,但很遗憾网上几乎没有资料,AIM ECI 规范的外文资料,需收费下载。没办法,等以后再说吧。现在只知道 AIM 是一家公司,ECI 是规范,有了这个规范,有了这个东西,可以使用二维码装载各类不同的字符集,也可使接收系统在数据被使用之前知道做哪些特定的扩展或解密处理。

FNC1 相信读过前面写的《条码技术》这篇文章中的 GS1-128 条码的都应当很熟悉,这类编码是专为 GS1 标准准备的。本文仅针对数字、字母数字、8 位字节以及 FNC1 模式进行讲解,示例程序也只实现这四种编码方式。

数字模式

数字模式只能对十进制数字 0~9 进行编码,通常的密度为 10 位表示 3 个字符。

将数字转换为位流

将要表示的数字从左边开始每三位分为一组,然后将每组数据转换为 10 位二进制(10 位二进制可表示的最大数字为 1023)。如果最后一组数字只剩两位,则使用 7 位二进制表示(7 位二进制可表示的最大数字为 127)这两个数字。如果最后一组数字只剩一位,则使用4位二进制表示最后一个数字(4 位二进制可表示的最大数字为 15)。将二进制数据连接起来并在前面加上模式指示符和字符计数指示符。

【例1】:数字01234567

  1. 分为 3 位一组:012 345 67
  2. 将每组转换为二进制: 012 -> 0000001100 345 -> 0101011001 67 -> 1000011
  3. 将二进制连接为一个序列:0000001100 0101011001 1000011

将字符计数指示符转换为二进制

字符计数指示符表示装载字符的个数,长度随不同的 QR 码版本以及模式而不同。表 2 列出了各版本及模式所对应的字符计数指示符的长度。

版本 数字模式 字母数字模式 8 位字节模式 中国汉字模式
1~9 10 9 8 8
10~26 12 11 16 10
27~40 14 13 16 12
表 2:字符计数指示符的位数

数据的数字位数为 8,查上表数字模式列,如果使用版本 1 来表示,则位数为 10。最终: 8 -> 0000001000

加入模式指示符及字符计数指示符

查表 1 ,数字模式的指示符为 0001。以【模式指示符 + 字符计数指示符 + 数字位流】的方式连接数据最终位流为:

0001 0000001000 0000001100 0101011001 1000011

接下来再做一个例子加深理解:

【例2】: 数字0123456789012345

  1. 分为 3 位一组:012 345 678 901 234 5

  2. 将每组转换为二进制: 012 -> 0000001100 345 -> 0101011001 678 -> 1010100110 901 -> 1110000101 234 -> 0011101010 5 -> 0101

  3. 将二进制连接为一个序列: 0000001100 0101011001 1010100110 1110000101 0011101010 0101

  4. 数字位数为 16,使用版本 1 表示,位数为 10。最终: 16 -> 0000010000

  5. 加上数字模式的指示符 0001 最终位流为: 0001 0000010000 0000001100 0101011001 1010100110 1110000101 0011101010 0101

字母数字模式

字母数字模式对 45 个字符的字符集进行编码,即:10 个数字 0~9,26 个大写字母 A~Z,以及 9 个符号 SP、$、%、*、+、-、.、/。通常情况下,两个输入字符用 11 位表示。下表是 45 个字符及其编码:

字符 字符 字符 字符 字符
0 0 9 9 I 18 R 27 SP 36
1 1 A 10 J 19 S 28 $ 37
2 2 B 11 K 20 T 29 % 38
3 3 C 12 L 21 U 30 * 39
4 4 D 13 M 22 V 31 + 40
5 5 E 14 N 23 W 32 - 41
6 6 F 15 O 24 X 33 . 42
7 7 G 16 P 25 Y 34 / 43
8 8 H 17 Q 26 Z 35 : 44

要完整表示 45 个字符中的一个,需要至 6 个位的二进制数字($2^6=64$),那么每两个字符需要占用 12 个位的空间。QR 码使用了另一种编码方法,将表示两个字符压缩为使用 11 个位的空间。

将输入的数字分为两个字符一组,将左边的字符的值乘以 45 与第二个字符的值相加,将所得的结果转换为 11 位二进制数。最大字符组为::(44×45+44=2024,而$2^{11}=2048$)。如果输入的数据的字符不是 2 的倍数,将最后一个字符编码为 6 位二进制数。将所得的二进制数连接起来并在前面加上模式指示符和字符计数指示符,得到最终编码。

【例 3】: 数据AC-42,QR 码版本号 1:

  1. 根据表 5 查出字符的值:AC-42 -> (10,12,41,4,2)
  2. 将结果分为 2 个一组:(10,12)(41,4)(2)
  3. 将每组数据转换为 11 位二进制数: (10,12) -> 10×45+12=462 -> 00111001110 (41,4) -> 41×45+4=1849 -> 11100111001 (2) -> 2 -> 000010
  4. 二进制数据顺次连接得到数据位流: 00111001110 11100111001 000010
  5. 字符数为 5,查表2,使用 9 位二进制数表示。将字符计数指示符转换为二进制, 5 -> 000000101
  6. 查表 1,模式指示符为 0010。以【模式指示符 + 字符计数指示符 + 数字位流】的方式连接数据最终位流为: 0010 000000101 00111001110 11100111001 000010

8 位字节模式

在 8 位字节模式中,一个 8 位码字直接表示一个输入数据字符的 ASCII 字符值(ASCII 译码表请查这里)。即密度为每个字符 8 位。将二进制数据连接起来并在前面加上模式指示符和字符计数指示符,得到最终编码。

【例 4】: 数据Ab>Cd,QR 码版本号 1:

  1. 在 ASCII表中查出各字符的值,并转换为 8 位二进制: A -> 65 -> 01000001 b -> 98 -> 01100010 > -> 62 -> 00111110 C -> 67 -> 01000011 d -> 100 -> 01100100
  2. 二进制数据顺次连接得到数据位流:01000001 01100010 00111110 01000011 01100100
  3. 字符数为 5,查表2,使用 8 位二进制数表示。将字符计数指示符转换为二进制, 5 -> 00000101
  4. 查表 1,模式指示符为 0100。以【模式指示符 + 字符计数指示符 + 数字位流】的方式连接数据最终位流为: 0100 00000101 01000001 01100010 00111110 01000011 01100100

混合模式

之前在学习 Code 128 编码时大家应该还记得,为了达到符号长度最小的目的,Code 128 条码支持混合编码的方式。QR 码也支持以混合方式进行编码。其基本结构为【模式指示符 + 字符计数指示符 + 数据】,其后紧跟下一段的指示符开始另一段。下图为有 n 段数据的结构。

由于 GS1 标准仅支持 ASCII 码,这里只针对数字模式、字母数字模式、8 位字节模式的混合编码进行讨论。以下是针对上述模式的编码规则,完整编码规则请参考 GB/T 18284-2000 的附录 H。

位流长度最优化的编码规则

下列是形成最短位流的算法的基础。在方括号中的字符数如[5,7,9]分别用于版本 1~9,10~26 和版本 27~40。

  1. 选择初始模式
    • 如果初始输入数据是在 8 位字节的二进制字符的专有子集中,选择 8 位字节模式;
    • 如果初始输入数据是在字母数字字符集的专有子集中,并且如果字符个数少于[6,7,8],其后紧跟 8 位字节专有子集中的数据,那么选择 8 位字节模式,否则选择字母数据模式;
    • 如果初始数据是数字,并且如果数字个数少于[4,4,5],其后紧跟 8 位字节字符集专有子集中的数据,那么选择 8 位字节模式,否则如果少于[6,7,8]后随字母数字字符集的专有子集中的数据,那么选择字母数字模式,否则选择数字模式。
  2. 在 8 位字节模式中
    • 如果有不少于[6,8,9]的数字字符序列出现在来自 8 位字节二进制字符集的专有子集的多个数据前,那么转至数字模式;
    • 如果有字母数字字符集的专有子集的不少于[11,15,16]的字符序列出现在来自 8 位字节二进制字符集的专有子集的数据前,那么转至字母数字模式。
  3. 在字母数字模式中
    • 如果有 8 位字节字符集的专有子集的一个或多个字符出现,转至 8 位字节模式;
    • 如果有不少于[13,15,17]的数字字符数据序列在来自字母数字字符集的专有子集的数据前出现,转至数字模式。
  4. 在数字模式中
    • 如果有一个或多个来自 8 位字节的专有子集中的字符出现,转至 8 位字节模式;
    • 如果有一个或多个字母数字的专有子集中的字符出现,转至字母数字模式。

编者注:上述规则摘抄至 GB/T 18284-2000,最后一句是有问题或者不完善的。如果在数字模式中出现字符Aabcd,因为A属于字母数字字符集,而abcd只属于 8 位字节字符集。此时按最后一句话,需先转换为字母数字模式,加入字符A,然后马上又转换为 8 位字节模式。很显然,这样做浪费了空间。由于字母数字字符集是 8 位字节字符集的子集,正确的做法应当是转换为 8 位字节模式,然后加入字符Aabcd

【例 5】:数据123456ABC123,QR 码版本号 1:

  1. 根据编码规则,首先应选择数字模式作为初始模式:0001
  2. 加入字符计数指示符:6 -> 0000000110
  3. 加入 123 编码:123 -> 0001111011
  4. 加入 456 编码:456 -> 0111001000
  5. 根据编码规则,转换为字母数字模式:0010
  6. 加入字符计数指示符:6 -> 000000110
  7. 加入 AB 编码:(10,11) -> 10×45+11=461 -> 00111001101
  8. 加入 C1 编码:(12,1) -> 12×45+1=541 -> 01000011101
  9. 加入 23 编码:(2,3) -> 2×45+3=93 -> 00001011101

将以上生成的二进制数据从上至下连接,生成最终位流。

FNC1 模式

FNC1 模式有两种模式指示符,用于标识按特定的行业或应用格式化信息的符号。FNC1 在第一位置时支持 GS1 标准,FNC1 在第二位置时支持按 AIM 认可的特定行业或者特定应用规范格式化信息。由于 AIM 查不到资料,这里只介绍 FNC1 第一位置模式,即模式指示符为:0101。

在 GS1-128 中,FNC1 用于数据段分隔,而 QR 码中没有专用的 FNC1 字符,在字母数字模式中用 % 字符代替,如果在数据中也有 % 符号出现,则 应按 %% 进行编码。在 8 位字节模式中用字符 GS(ASCII 值 29)代替。

编者注:个人感觉,这个设计方式相比 GS1-128 来说,并不太合理。即使数据只是纯数字,但只要在其中需要分段,安置 FNC1 ,就必须转为字母数字模式,如果后面还有足够多的数字,还得再次转回来。这样做的成本太高了。数字模式,还有部分未使用的编码,应当有自已的 FNC1,即使这个编码占据 10 个位,还是合算的。

【例 6】: 数据(02)66901234000049(17)050101(37)10(10)ABC,QR 码版本号 1:

首先分析数据中的 AI:(02)表示物流单元内贸易项目,长度固定;(17)表示有效期,长度固定;(37)表示物流单元内贸易项目数量,长度不固定,需在此 AI 最后加入 FNC1;(10)表示批号,长度不固定,它为最后一个 AI,无需加入 FNC1 标志。最终编码变为:

(02)66901234000049(17)050101(37)10<FNC1>(10)ABC

编码过程:

  1. 将 FNC1 第一位置作为初始模式:0101
  2. 根据位流长度最优化的编码规则,加入数字模式指示符:0001
  3. 加入字符计数指示符:28 -> 0000011100
  4. 加入 026 编码:026 -> 0000011010
  5. 加入 690 编码:690 -> 1010110010
  6. 加入 123 编码:123 -> 0001111011
  7. 加入 400 编码:400 -> 0110010000
  8. 加入 004 编码:004 -> 0000000100
  9. 加入 917 编码:917 -> 1110010101
  10. 加入 050 编码:050 -> 0000110010
  11. 加入 101 编码:101 -> 0001100101
  12. 加入 371 编码:371 -> 0101110011
  13. 加入 0 编码:0 -> 0000
  14. 根据编码规则,转换为字母数字模式:0010
  15. 加入字符计数指示符:6 -> 000000110
  16. 加入 %1 编码:(38,1) -> 38×45+1=1711 -> 11010101111
  17. 加入 0A 编码:(0,10) -> 0×45+10=10 -> 00000001010
  18. 加入 BC 编码:(11,12) -> 11×45+12=507 -> 00111111011

将以上生成的二进制数据从上至下连接,生成最终位流。

终止符

符号的数据结尾由紧跟在最后一个模式段后面的终止符序列 0000 表示,当数据位流数量正好填满符号容量时,它可以省略,或者当符号所余的容量不足 4 位时它可以截短。

位流到码字的转换

每个模式段的位流需要按顺序连接在一起,最后添加终止符,除非数据位流正好填满符号容量。所得的数据位流将被分为一个个码字;所有码字长度都是 8 位,如果位流长度最后一个码字不足 8 位,则用二进制值为 0 的填充位填充至 8 位,填充位应加在数据位流最后 1 位(最低位)的后面。说白了就是将位流进行 8 位对齐。

【例 1 续 1】:

我们以【例 1】最终生成的数据位流为例说明上述过程。

  1. 【例 1】最终生成的数据位流:00010000001000000000110001010110011000011
  2. 加入终止符 0000,(现在符号容量足够,不用考虑容量不足的情况): 000100000010000000001100010101100110000110000
  3. 将数据位流划分为码字,这里在每 8 个位后加一个逗号表示: 00010000,00100000,00001100,01010110,01100001,10000
  4. 我们发现最后一个码字只有 5 位数字,不足 8 位,补 3 个零,最终数据变为: 00010000,00100000,00001100,01010110,01100001,10000000

最终【例 1】生成的数据使用了 6 个码字。

接下来就要查表了,下表列出了各个版本 QR 码的码字容量,这里只列出一小部分,完整表格请参考 GB/T 18284-2000。

注意表格中的红框部分,由于只使用了 6 个码字,我们完全可以选择最高纠错等级 H。所以最终选择为:版本 1 的 H 纠错等级 QR 码。在此等级中可放置 9 个码字,还剩余 3 个码字是不能放空的,需要交替填充码字 11101100 和 00010001,直至填满整个 9 个码字。

  1. 将空位填满至 9 个码字,最终数据变为: 00010000,00100000,00001100,01010110,01100001,10000000,11101100,00010001,11101100

好!上半场结束,图多,还是分两篇写吧。下半场内容就比较抽象了。

;

© 2018 - IOT小分队文章发布系统 v0.3