眼中有码,心中无码

用户头像
小眼睛聊技术
关注
发布于: 2020 年 06 月 01 日
眼中有码,心中无码



日常生活中二维码的使用已经无处不在,付款码、微信名片、健康码、乘车码……一张小小的二维码侵入到生活中的方方面面。黑白色块组成的有限区域,如何携带信息。不同应用场景下的二维码会不会重复,会不会像 IPV4 一样被耗尽?如果您对这些也有疑问,请您带着问题阅读本文。

一. 你一定没见过的二维码



二维码有很多种类,目前主流的有 PDF417码,QR码,汉信码,颜色条码,EZ码,Aztec码,QuickMark,Data Matrix 这几种。我们每天付款、点餐时使用的是 QR码,又称 Quick Response Code ,是1994年由日本人发明。



按照实现原理,二维码可以分为两类:

  • 堆叠式/行排式(原理是建立在一维条码基础之上,按需要堆积成二行或多行)

  • 矩阵式二维码(原理是在一个矩形空间通过黑、白像素在矩阵中的不同分布进行编码)



小知识:

  1. 二维码种类有很多,我们平时说的二维码是 QR码,只是二维码的一种

  2. QR码 是日本人发明的





最右下角的 QR码使我们最常见到的,本文就以 QR码切入,分析实现原理。

二. 信息是如何传递的?



二维码在代码编制上巧妙地利用构成计算机逻辑基础的“0”、“1”,使用若干个与二进制相对应的几何形体来表示文字数值信息,这些特定的几何图形按一定规律在平面(二维方向上)分布的、黑白相间的、记录数据符号信息的图形。通过扫码枪、手机 APP等识别到二维码,还原信息。非常像加密和解密的过程。

整体结构



QR码从结构上基本上可被分为定位区、功能区、数据区三部分

来源于维基百科



1. 定位区



常见的二维码,不论你是站着扫,趴着扫,跪着扫,左左右右上上下下地都能识别得到,全都是依赖这三个数据模块:

  1. 定位标志。在左上,右上,左下有三个大型的 “回” 字的黑白相间同心正方形,为QR码识别定位标志,失去其中一个会影响识别。

  2. 定时标志。用于定位,二维码如果尺寸过大,扫描时容易畸变,时序图案的作用就是防止扫描时畸变的产生;

  3. 校正标志。Version2 以上需要

2. 功能区

  1. 格式信息。存放格式化数据,表示改二维码的纠错级别,分为L、M、Q、H;

  2. 版本信息:用于 Version 7 以上,需要预留两块 3×6 的区域存放部分版本信息;

3. 数据部分

实际保存的二维码信息,和纠错码元(用于修正二维码损坏带来的错误)

版本分类



QR码设有 1 到 40 的不同版本(种类),每个版本都具备固有的码元结构(码元数)。“码元结构”是指二维码中的码元(码元是指构成QR码的方形黑白点)数。从version 1(21码元×21码元)开始,在纵向和横向各自以 4 码元为单位递增,一直到 version 40(177码元×177码元)。

来源于维基百科



三. 码,是如何生成的?



一个二维码的生成大致分为下面几步:

数据分析

  1. 确定编码的字符类型,按相应的字符集转换成符号字符;

  2. 选择纠错等级,在规格一定的条件下,纠错等级越高其真实数据的容量越小

数据编码

  1. 类似于utf8编码,给定一个字符串,然后将其编码成一串二进制数。

  2. 根据选择的编码模式和版本信息、纠错等级,生成原始信息的数据编码。

纠错编码

  1. 根据源数据编码结果可以计算得到纠错码,使用的是Reed-Solomon纠错算法

构造矩阵

  1. 根据选择的版本信息和整体结构中提到的3个部分,为矩阵格子中分别填充0和1

掩码

可能上面画出来后,黑白分布不均匀会导致存在大片的白色或黑色,造成扫描识别的困难。二维码提供了8Mask掩码图案:



我们需要拿着上面生成的图案和掩码图案做一次异或操作,这样黑白分布就会均匀。经过掩码之后的二维码,就是我们日常见到的分布均匀的二维码,至此绘制才算完成。



四. 举个例子



假设我们对字符串 “01234567” 生成一个二维码,需要以下步骤:

1. 模式选择

QR 码支持的编码模式有这些:



由于 “01234567” 都是数字,我们选择数字模式。数字模式下,需要编码的数字的个数如果不是3的倍数,会将最后剩下的 1 或 2 位数会被转成 4 或 7 bits,其它的每 3 位数字会被编成 X 个 bits,(X大小需要基于二维码的版本,没有为什么一切都在 qr code spec 中有定义)



不同版本的二维码容量不同,参考:



我们选择 version 1 ,纠错级别 H 完全足够。每个版本下,不同编码模式下需要被编码的 bits 个数如下表:



因为我们得出结论:

  1. “01234567” 选择数字模式编码

  2. 二维码选择 version 1 H

  3. 每3位数字会被编码成10个 bit,剩下的1或2位数会被转成 4 或 7 bits

2. 编码

分成 3 组,012 和 345 和 67。其中,012 转成 0000001100(10位); 345 转成 0101011001(10位); 67 转成 1000011(不足3个数,编码为 7 个 bits)



3 个二进制串起来: 0000001100 0101011001 1000011



01234567 总共是 8 个数字,8 转成二进制是 0000001000(10位),再加上我们选择的数字模式的标识符 0001 ,最后得到二进制串为:

0001 0000001000 0000001100 0101011001 1000011 0000

数字 | 8个数字 | 012 | 345 | 67 | 结束符



共45个bit,按 8个bit 一组重新排列,不是8个倍数我们还要在后面加上足够的0凑齐8个倍数:

00010000 00100000 00001100 01010110 01100001 10000000



共 48个bit,还没有达到我们最大的 bits 数限制,则需要在编码最后加上补齐符(Padding Bytes),我们选择的是 version 1 的 H 级别,容量是 72 bits ,现在只有 48 个 bits,还差24个bits ,需要补齐。Padding Bytes就是重复补充这两个 bytes 11101100 和 00010001 ,补充完整为:



00010000 00100000 00001100 01010110 01100001 10000000 11101100 00010001 11101100



上面的编码就是数据码了,叫 Data Codewords,每一个8 bits 叫一个 codeword ,我们还要对这些数据码加上纠错信息。

3. 纠错编码

有了纠错编码,才可以使得有些二维码有了残缺、污损也可以尽量扫码解析出来;才可以使得二维码中心位置可以供某些商家加上对解析不必要的图标





我们选择的是级别 H,参考纠错码分组定义:



  • 纠错块个数(Number of error correction blocks):需要划分纠错块的个数;

  • 纠错块码字数(Error Correction Code Per Blocks):每个块中的码字个数,即有多少个字节 Bytes;



(26,9,8)表示在version 1 H 中,总共26个 codewords ,其中 9 个为原始数据码,17个为纠错码,其中每个纠错码占 8 个 bits



我们假设计算(计算方法)好的纠错码共 17 个 codewords,分别是 E1,E2,E3 …… E17

4. 最终编码

原始的Data Codewords ,一共包含 9 个codewords:

00010000 00100000 00001100 01010110 01100001 10000000 11101100 00010001 11101100

我们分别命名为:D1, D2, D3……D9

源码和纠错码,最终形成的数据为:D1 D2 D3 D3 D3 D3 D3 D3 D3 E1 E2 E3 …… E17

5. 构造矩阵

有了编码,我们就可以画图像了。

首先根据 version 确定矩阵整体大小,我们是version 1 ,因此是 21 * 21 的矩阵。

接下来在左上、左下、右上三个位置填充定位标志。

填充校验方块,确定校正标志,填充格式信息,填充版本信息

最后填充数据和纠错码,从二维码的右下角开始,沿着红线填充我们数据编码的每一个bit1表示黑色,0表示白色,遇到非数据区绕开或跳过。如图示:







6. 掩码



这样下来,我们的图就填好了。但是,也许那些点并不均衡,如果出现大面积的空白或黑块,扫描识别会很困难。所以,我们还要做 Masking 操作。QR 有8个 Mask 可以使用,每种 Mask 的图示和算法,参考第三part中掩码小节中的图。



mask 就是和上面生成的图做 XOR 操作,且只会和数据区进行 XOR ,不会影响功能区。



我们需要拿着上面生成的图案和掩码图案做一次异或操作,这样黑白分布就会均匀很多!具体选择哪一个掩码图案呢?也是有一个灰常复杂的计算方案,大体步骤是分别将原始图案和每一个掩码图案做异或,然后按照一套规则来计算均匀程度,最终选择最均匀的那个。参考 Data Masking深度探索二维码原理及其应用

五. 用完了该咋办?





这是微信后台下载的本公众号名片,采用 37 * 37 规格的矩阵 (相信我,为了数清楚,小眼睛已瞎)。以这个矩阵为例:



3个定位区大小都是7 * 7,所以在这个矩阵上可用的格子数量是 37 * 37 - 3 * 7 * 7 = 1222 个。考虑到上半篇幅我们提到的掩码,占位之类的,假设只有 1000 个格子可用。每个格子或是黑或是白,只有 0 或 1 两种选择,1000 个格子组合下来是 2 ^ 1000,表示成 10 进制数字是(不用费工夫算了,计算器算不出来,写程序搞出来的):



10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376



这仅仅是理论值,再去掉全黑全白和其他不能用的情况,仍然是一个超级大的数。37 * 37 只是version 5 ,上半篇幅我们提到了 QR 码有40个 version 。因此二维码用完,存在理论上的可能性,不过你我一定是等不到那天了。即便是真到了用完的一天,参考 IPV4 升 IPV6 的方案可以继续扩大尺寸。

六. 会不会重复?



二维码作为信息的载体,只要是信息是一致的那么生成的二维码就会重复。现实场景中,每个 APP 或者每个企业在内部环境下是可以保证信息的唯一性,因此我们生成的二维码是唯一的。微信二维码的唯一性是在微信系统之内的唯一。二维码上的黑白点排列并不是随机无意义的,而是原始二进制代码,代表某种意义,而不同的人的二维码要代表的事是不同的,所以不会有重复的。

其他

现在市面上出现了彩色二维码,或者不规则二维码。这个和本文讲述的生成过程并不冲突。彩色二维码被摄像头扫描,采集到图像后不是直接进行解析的,程序会对二维码进行裁剪处理,去噪处理,灰度处理等。而所谓灰度处理,就是把图片处理成灰度图片,灰度图像也称为“黑白”图像。最终图片会转成只有 “0” 和 “1” 的矩阵。



参考

QR Code 官网

维基百科

Data Masking

深度探索二维码原理及其应用

关注我



如果您在微信阅读,请您点击链接 关注我 ,如果您在 PC 上阅读请扫码关注我,欢迎与我交流随时指出错误



发布于: 2020 年 06 月 01 日 阅读数: 296
用户头像

小眼睛聊技术

关注

欢迎关注公众号“小眼睛聊技术” 2018.11.12 加入

互联网老兵,关注产品、技术、管理

评论 (1 条评论)

发布
用户头像
二维码牵扯到的事儿,挺多
2020 年 06 月 01 日 17:11
回复
没有更多了
眼中有码,心中无码