二维码学习笔记(八) | 项目总结

唠唠闲话

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

使用演示

工具由纯 Julia 编写：Julia 下载地址及安装教程。

打开 Julia，安装二维码工具

1
2
3

using Pkg
Pkg.add("QRCoders")
Pkg.add("QRDecoders")

基本示例

创建二维码

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

20221126123512

导出二维码图片

# 直接导出
exportqrcode("Hello world!", "hello.png")
# 通过对象 code 导出，默认路径为 `qrcode.png`
exportqrcode(code)

导出 GIF 动图

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

hello

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

1	code = QRCode("Hello World!", version=1, eclevel=Low(), mode=UTF8(), mask=0, width=2)

二维码解码

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!"

二维码样式

用 Unicode 字符绘制二维码

1
2
3

using QRCoders
unicodeplot("Hello World!") # 使用 UnicodePlots.jl 绘制
unicodeplotbychar("Hello World!") |> println # 使用 Unicode 字符

在二维码中绘制图片，自选图片或者使用 TestImages.jl 中的图片

# 安装图片编辑工具
# 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
二维码有四种纠错等级，从低到高分别为 L，M，Q，H，等级越高纠错码越多，二维码的容量也相越小

二维码拆解

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

功能区，用于图像定位
- 位置探测图形，分别为左上角，右上角，左下角
- 分隔符，包围探测图形的两段白条
- 时序图案，水平和数值两条交错线段
- 对齐图案，均匀分布在二维码的各个位置
- 暗模块，紧挨着左下角的白色分隔符
编码区，包括格式数据，版本信息和编码数据
- 格式数据：二维码纠错等级和掩码模式，共 15 比特
- 版本信息，仅在版本 ≥7 时存在，共 18 比特
- 编码数据：剩下的空位存放编码数据

编码过程

数据编码，分 Numeric, Alphanumeric，Byte，Kanji 和 UTF-8 五种模式，根据数据类型选择最优的编码模式，编码得到若干字节数据。
纠错编码，使用 GF(256) 上的 Reed-Solomon 纠错码。限于编码特性 数据字节数 + 纠错字节数需不大于 255，将数据拆分为若干小块再分别配备纠错码，构成纠错块。
依次填充功能区，版本信息（如果版本 ≥7）和格式信息区，交织填入数据块和纠错块

交织从右往左进行
施加不同掩码，分别计算罚分，选择罚分最低的二维码。使用掩码是为了尽可能避免二维码中出现容易混淆识别的图案，最极端的，可能会出现下图的这种设计。

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

纠错原理

一个例子

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

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

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

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

现 Alice 将编码后的 $y$ 传输给 Bob

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

编码理论

上边例子采用了汉明距离为 3 的编码，一般地，设 $C$ 为汉明距离为 $d$ 的编码

编码 $C$ 能检测至多 $e\leq d-1$ 个错误
编码 $C$ 能填补至多 $e\leq d-1$ 个缺失
编码 $C$ 能纠正至多 $e\leq \lfloor\frac{d-1}{2}\rfloor$ 个错误，即 $2e\leq d-1$

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

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

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

写在最后

未来计划：

拓展二维码的样式 https://github.com/JuliaImages/QRCoders.jl/issues/33
提高解码器的检测能力 https://github.com/JuliaImages/QRDecoders.jl/issues/14

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

性能测试

当前二维码版本的性能测试，相较 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 版本

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)