二维码笔记系列:

唠唠闲话

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

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

本篇内容:

二维码简介

版本和纠错等级

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

  1. 二维码版本,最小版本为 1,最大版本为 40

    版本号 二维码尺寸
    Version=1 21 x 21
    Version=2 25 x 25
    Version=k 17+4k x 17+4k
    Version=40 177 x 177
  2. 纠错等级:QR code 有 4 种纠错等级

    纠错等级 纠错能力
    Error Correction Level Error Correction Capability
    L(Low) 恢复 7% 的数据
    M(Medium) 恢复 15% 的数据
    Q(Quartile) 恢复 25% 的数据
    H(High) 恢复 30% 的数据
  3. 一般地,用 V-E 表示二维码版本信息,比如 40-L 表示版本为 40 纠错等级为 L 的二维码

基本构成

下图是版本 7 的二维码
version7

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

  1. 功能区(Function Patterns),用于图像定位

    • 三个探测图形(Position Detection Patterns),分别位于左上,左下,右上,由黑白模块交错组成,如下图
      finder
    • 包围探测图形的分隔符(Separators for Postion Detection Patterns) 围绕探测图形的一圈白色模块
    • 时序图案(Timing Patterns),水平和竖直两条线段,作为标准线,用于图像校正
    • 对齐图案(Alignment Patterns),平均分布于图像各个位置,仅当二维码版本大于 1 时存在
    • 暗模块(Dark module) 位于白色分隔符直角的右侧
  2. 示例:下图非灰色区域为功能区
    Timing-pattern

  3. 编码区(Encoding Region),用于记录二维码信息

    • 格式信息(Format Information),分布在三个角落,存放二维码格式信息(纠错等级和掩码模式)
      格式
    • 版本信息(Version Information),只有版本号大于等于 7 的二维码存在,位于左下和右上的两块 3 x 6 的区域
      版本信息
    • 编码数据和纠错数据(Data and Error Correction Codewords)为余下的深灰色区域

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

编码概述

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

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

编码步骤

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

  1. 数据分析:根据数据内容确定编码模式,常见编码模式有:

    • 数字模式(Numeric mode)
    • 数字字母模式(Alphanumeric mode)
    • 字节模式(Byte mode) 和 UTF-8 字节模式(UTF8 mode)
    • 汉字模式(Kanji mode)
    • 扩充解释模式(ECI),结构链接模式,FNC1模式等(只关注前 4 种)
  2. 数据编码:根据纠错等级和编码模式计算最小版本,并按一定规则将数据转化为二进制(规则附后)

  3. 纠错编码:用 Reed-Solomon 纠错生成纠错位,并与编码数据交织得到数据位

  4. 构造矩阵:放置功能区(角落方块,放置对齐图案,时序图案和暗模块),将数据位填入矩阵:从右下出发,Z 字上下遍历数据区,参考下图(填充需跳过功能区,版本区和格式区,下图漏掉了版本区)
    tupian

  5. 数据掩码:

    • 掩码处理是为了避免数据区出现类似定位器形状的区域,或者出现大片空白等,可能会使扫描器混淆、错乱
    • 掩码处理逆转某些模块(白色变成黑色,黑色变成白色),保留其他模块不变
      20220526101137
    • 掩码只对数据区进行 XOR 运算,不会影响功能区,格式区和版本区
    • 二维码定义以下 8 种掩码方式,按评估条件选择罚分最低的方案
      图片

解码步骤

解码是编码的逆过程,包括以下步骤:

步骤 说明
检测和定位 通过图像计算,检测二维码位置,生成二维码矩阵
数据提取与纠错 检查二维码矩阵的完整性,提取数据并纠错
数据解码 将二进制数据转化为原始数据

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

  1. 检测和定位

    • 通过功能区(探测图形,时序图案和对齐图案),确定二维码位置和形变信息(涉及图像处理,重难点!)
    • 解码版本区(若版本≥7),检查与识别到的矩阵大小是否一致
  2. 提取数据,难点在 Reed-Solomon 的纠错

    • 解码格式区,获取纠错等级和掩码模式
    • 将掩码作用于数据区,还原原始数据
    • 提取数据区,纠错后返回原始编码数据
  3. 数据解码,重点在编码规则的选择

    • 根据模式指示器,获取编码模式
    • 按编码模式将二进制数据还原为字符串数据

相关链接

知识参考:

英文经典教程:QR Code Tutorial
二维码标准文献:ISO/IEC 18004:2000
维基百科:QR Code
CSDN 教程:二维码介绍
简书:为程序员写的 Reed-Solomon 码解释
CSDN 教程:二维码的生成细节和原理
知乎:二维码练习

编解码工具:

开源 ZXing:https://github.com/zxing/zxing
二维码生成器:https://zxing.appspot.com/generator
二维码解码器:https://zxing.org/w/decode.jspx
二维码解码器-2:https://www.onlinebarcodereader.com/