唠唠闲话

本篇是对二维码的概括性介绍,内容包括:使用演示,二维码构成和纠错原理。


使用演示

工具由纯 Julia 编写:Julia 下载地址安装教程

打开 Julia,安装二维码工具

1
2
3
using Pkg
Pkg.add("QRCoders")
Pkg.add("QRDecoders")

基本示例

  1. 创建二维码

    1
    2
    3
    4
    5
    using QRCoders
    # 创建二维码对象
    code = QRCode("Hello World!")
    # 生成二维码矩阵
    qrcode(code)

    20221126123512

  2. 导出二维码图片

    1
    2
    3
    4
    # 直接导出
    exportqrcode("Hello world!", "hello.png")
    # 通过对象 code 导出,默认路径为 `qrcode.png`
    exportqrcode(code)
  3. 导出 GIF 动图

    1
    exportqrcode(["Hello", "Julia", "!"], "hello.gif")

    hello

  4. 指定二维码版本,纠错等级,掩码,编码模式和白框大小

    1
    code = QRCode("Hello World!", version=1, eclevel=Low(), mode=UTF8(), mask=0, width=2)
  5. 二维码解码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    using QRDecoders, QRCoders, Test
    # 解码二维码矩阵
    code = QRCode("Hello World!", width=0)
    mat = qrcode(code)
    info = qrdecode(mat)
    @test info.message == "Hello World!"
    @test info == code
    # 解码二维码图片
    exportqrcode("Hello World!", "test.png")
    info = qrdecode("test.png")
    @test info.message == "Hello World!"

二维码样式

  1. 用 Unicode 字符绘制二维码

    1
    2
    3
    using QRCoders
    unicodeplot("Hello World!") # 使用 UnicodePlots.jl 绘制
    unicodeplotbychar("Hello World!") |> println # 使用 Unicode 字符
  2. 在二维码中绘制图片,自选图片或者使用 TestImages.jl 中的图片

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    # 安装图片编辑工具
    # using Pkg; Pkg.add("TestImages"); Pkg.add("FileIO");
    # Pkg.add("ImageTransformations"); Pkg.add("ColorTypes");
    using TestImages, ImageTransformations, FileIO, ColorTypes
    # 读取图片,转化为二值图
    img = testimage("cameraman")
    code = QRCode("HELLO WORLD", version=20)
    inlen = qrwidth(code) - 2 * code.border - 15
    bitimg = .!(Bool.(round.(Gray.(imresize(img, (inlen, inlen))))))
    # 绘制二维码
    mat = imageinqrcode(code, bitimg, rate=0.9)
    # 导出二维码图片
    mat |> exportbitmat("cameraman.png")

关于样式的更多讨论参考 二维码样式计划

二维码构成

二维码的容量与版本和纠错等级有关:

  • “版本”指二维码的大小,范围为 1-40,比如版本为 k 的二维码大小为 17+4k x 17+4k
  • 二维码有四种纠错等级,从低到高分别为 LMQH,等级越高纠错码越多,二维码的容量也相越小

二维码拆解

下图是版本 7 的二维码,主要分为功能区编码区
version7

  1. 功能区,用于图像定位
    20220602230150

    • 位置探测图形,分别为左上角,右上角,左下角
    • 分隔符,包围探测图形的两段白条
    • 时序图案,水平和数值两条交错线段
    • 对齐图案,均匀分布在二维码的各个位置
    • 暗模块,紧挨着左下角的白色分隔符
  2. 编码区,包括格式数据,版本信息和编码数据

    • 格式数据:二维码纠错等级和掩码模式,共 15 比特
      20220603210934
    • 版本信息,仅在版本 ≥7 时存在,共 18 比特
      20220603091647
    • 编码数据:剩下的空位存放编码数据

编码过程

  1. 数据编码,分 Numeric, AlphanumericByteKanjiUTF-8 五种模式,根据数据类型选择最优的编码模式,编码得到若干字节数据。

  2. 纠错编码,使用 GF(256) 上的 Reed-Solomon 纠错码。限于编码特性 数据字节数 + 纠错字节数需不大于 255,将数据拆分为若干小块再分别配备纠错码,构成纠错块。

  3. 依次填充功能区,版本信息(如果版本 ≥7)和格式信息区,交织填入数据块和纠错块
    qrimg
    交织从右往左进行
    qrimgbits

  4. 施加不同掩码,分别计算罚分,选择罚分最低的二维码。使用掩码是为了尽可能避免二维码中出现容易混淆识别的图案,最极端的,可能会出现下图的这种设计。
    qr2

解码是编码的逆过程,步骤包括:定位图片,读取格式区,施加掩码还原,提取编码数据,纠错数据,解码得到原始字符串,主要难点在于定位纠错

纠错原理

一个例子

在数据传输过程可能会出现一些错误,比如把 1 传成了 0 或者丢失了某个位置数据。纠错码主要有三个作用:检测错误,补充缺失和纠正错误。

纠错本质上引入了更大的空间来表达一个小的数据集,冗余信息提高了数据的容错能力。我们通过一个例子来说明这个过程。

假设 Alice 要传输 x{0,1}x\in\{0,1\} 给 Bob,为了增加容错率,Alice 采用了下边的编码模式

x=0y=000x=1y=111\begin{aligned} x = 0 \quad &\rightarrow &\quad y=000 \\ x = 1 \quad &\rightarrow &\quad y=111 \end{aligned}

现 Alice 将编码后的 yy 传输给 Bob

  • 纠错:假设传输过程至多产生 1 比特错误,比如 000010000\rightarrow 010,显然 Bob 能将 010010 解码为 00,进而纠正错误
  • 检错:假设传输过程至多产生 2 比特错误,比如 000110000\rightarrow 110,尽管 Bob 不能确定原始信息是 00 还是 11,但他能判断传输过程是否出现错误
  • 补缺:假设传输过程丢失了 2 比特,比如 0000000\rightarrow 0**,显然 Bob 能根据剩下的信息补全得到 000000

编码理论

上边例子采用了汉明距离为 3 的编码,一般地,设 CC 为汉明距离为 dd 的编码

  • 编码 CC 能检测至多 ed1e\leq d-1 个错误
  • 编码 CC 能填补至多 ed1e\leq d-1 个缺失
  • 编码 CC 能纠正至多 ed12e\leq \lfloor\frac{d-1}{2}\rfloor 个错误,即 2ed12e\leq d-1

汉明距离指将一个编码转换为另一个编码所需要改变的位数,比如 000010000\rightarrow 010 的汉明距离为 1,000110000\rightarrow 110 的汉明距离为 2。我们通过图像理解这个定理,原始信息是一个个圆点,我们用更大的空间表达这些圆点,汉明距离是圆点之间的最小距离,当发生错误在距离的一半以内时,我们总能纠正错误
20220504115713

此外,ReedSolomon 编码是最常用的纠错编码之一,其满足编码设计的几个指标:

  • 较强的错误处理能力
  • 尽量小的冗余信息
  • 存在高效的编解码算法

写在最后

未来计划:

限于个人时间精力,目前这两方面还有很多工作没做,欢迎大家提出宝贵意见,帮助完善这个包。

性能测试

当前二维码版本的性能测试,相较 1.0.0 版本使用 UInt8 代替 Int64

repo release-version QR-version cost
QRCode.jl 0.2.0 1 4.040 ms (175888 allocations: 8.43 MiB)
QRCoders.jl 1.0.0 1 149.392 μs (370 allocations: 32.28 KiB)
QRCoders.jl 1.4.0 1 134.559 μs (268 allocations: 17.50 KiB)
QRCode.jl 0.2.0 40 509.677 ms (19128212 allocations: 922.52 MiB)
QRCoders.jl 1.0.0 40 21.700 ms (29459 allocations: 4.84 MiB)
QRCoders.jl 1.4.0 40 17.276 ms (15281 allocations: 1.07 MiB)

测试使用的 Julia 版本

1
2
3
4
5
6
7
8
Julia Version 1.7.2
Commit bf53498635 (2022-02-06 15:21 UTC)
Platform Info:
OS: Linux (x86_64-pc-linux-gnu)
CPU: Intel(R) Core(TM) i5-1035G1 CPU @ 1.00GHz
WORD_SIZE: 64
LIBM: libopenlibm
LLVM: libLLVM-12.0.1 (ORCJIT, icelake-client)