二维码学习笔记(一) | 二维码概述

二维码笔记系列：

唠唠闲话

二维码英文名称为 QR Code(Quick Response Code)，是一个近几年来移动设备上超流行的一种编码方式，它比传统的 Bar Code 条形码能存更多的信息，也能表示更多的数据类型。二维码的出现，让我们的生活更加便捷，比如扫码登录，扫码支付，扫描骑车等等。

系列笔记将对二维码的理论知识进行总结，希望能够帮助大家更好的理解二维码的编码过程，笔记动机源于个人对编码理论的兴趣，以及今年参与的 OSPP-JuliaImages-项目。

本篇内容：

二维码的存储容量与其大小和纠错等级有关。二维码最小为 21 x 21，最大为 177 x 177，其大小也被称为“Version”，版本越高，能存储的信息也越多。

纠错等级：QR code 有 4 种纠错等级

纠错等级	纠错能力
Error Correction Level	Error Correction Capability
L(Low)	恢复 7% 的数据
M(Medium)	恢复 15% 的数据
Q(Quartile)	恢复 25% 的数据
H(High)	恢复 30% 的数据

下图是版本 7 的二维码
version7

其中深灰色区域存储二维码数据，其他区域用于图像定位以及记录版本信息等。具体地，非数据区域由以下几部分构成

功能区(Function Patterns)，用于图像定位
- 三个探测图形(Position Detection Patterns)，分别位于左上，左下，右上，由黑白模块交错组成，如下图
- 包围探测图形的分隔符(Separators for Postion Detection Patterns) 围绕探测图形的一圈白色模块
- 时序图案(Timing Patterns)，水平和竖直两条线段，作为标准线，用于图像校正
- 对齐图案(Alignment Patterns)，平均分布于图像各个位置，仅当二维码版本大于 1 时存在
- 暗模块(Dark module) 位于白色分隔符直角的右侧
示例：下图非灰色区域为功能区
编码区(Encoding Region)，用于记录二维码信息
- 格式信息(Format Information)，分布在三个角落，存放二维码格式信息（纠错等级和掩码模式）
- 版本信息(Version Information)，只有版本号大于等于 7 的二维码存在，位于左下和右上的两块 3 x 6 的区域
- 编码数据和纠错数据(Data and Error Correction Codewords)为余下的深灰色区域

注：二维码的三个编码区均具有一定的纠错能力，但当错误超过纠错上限时，二维码将无法识别。比如下图将版本信息置为白色，即使数据区域没有错误，二维码也无法识别。
qrcode-impact

总的来说，二维码拆分为功能区(探测图形，分隔符，时序图案，对齐图案和暗模块)和编码区(格式区(掩码+纠错)，版本区和数据区(编码+纠错))，按以下步骤填入二维码矩阵：

步骤	描述
数据分析	确定编码模式，纠错等级，版本
数据编码	将数据转换为二进制
纠错编码	生成纠错码并与原始数据交织构成数据区
构建二维码矩阵	将功能区和数据区填入矩阵
版本和掩码	将版本数据(若≥7)填入版本区；计算最佳掩码并处理数据区；最后将格式数据填入格式区

下边对编码步骤做进一步解释。

数据分析：根据数据内容确定编码模式，常见编码模式有：
- 数字模式(Numeric mode)
- 数字字母模式(Alphanumeric mode)
- 字节模式(Byte mode) 和 UTF-8 字节模式(UTF8 mode)
- 汉字模式(Kanji mode)
- 扩充解释模式(ECI)，结构链接模式，FNC1模式等（只关注前 4 种）
数据编码：根据纠错等级和编码模式计算最小版本，并按一定规则将数据转化为二进制（规则附后）
纠错编码：用 Reed-Solomon 纠错生成纠错位，并与编码数据交织得到数据位
构造矩阵：放置功能区(角落方块，放置对齐图案，时序图案和暗模块)，将数据位填入矩阵：从右下出发，Z 字上下遍历数据区，参考下图（填充需跳过功能区，版本区和格式区，下图漏掉了版本区）
数据掩码：
- 掩码处理是为了避免数据区出现类似定位器形状的区域，或者出现大片空白等，可能会使扫描器混淆、错乱
- 掩码处理逆转某些模块（白色变成黑色，黑色变成白色），保留其他模块不变
- 掩码只对数据区进行 XOR 运算，不会影响功能区，格式区和版本区
- 二维码定义以下 8 种掩码方式，按评估条件选择罚分最低的方案

解码是编码的逆过程，包括以下步骤：

下边对解码步骤做进一步解释。

检测和定位
- 通过功能区(探测图形，时序图案和对齐图案)，确定二维码位置和形变信息（涉及图像处理，重难点！）
- 解码版本区(若版本≥7)，检查与识别到的矩阵大小是否一致
提取数据，难点在 Reed-Solomon 的纠错
- 解码格式区，获取纠错等级和掩码模式
- 将掩码作用于数据区，还原原始数据
- 提取数据区，纠错后返回原始编码数据
数据解码，重点在编码规则的选择
- 根据模式指示器，获取编码模式
- 按编码模式将二进制数据还原为字符串数据