目录:

前置知识

encode

decode

有任何问题和指导建议,可以联系我讨论:guchenhui1993@gmail.com

前置知识

• 不同码制:

  Data Matrix,MaxiCode, Aztec,QR Code, Vericode,PDF417,Ultracode,Code 49,Code 16K等

• 根据原理分类:

  堆叠式/行排式以及矩阵式。本文讲的是日常生活最常见的矩阵式QR Code.

  • 堆叠式/行排式:

  编码原理建立在一维条码基础之上，按需要堆积成二行或多行。代表的码制有:
  Code 16K、Code 49、PDF417、MicroPDF417等.

  • 矩阵式:

  在一个矩形空间通过黑、白像素在矩阵中的不同分布进行编码。有占位表示1,无占位表示0.代表的码制有:
  Code One、MaxiCode、QR Code、 Data Matrix、Han Xin Code、Grid Matrix等.

• 尺寸:

  二维码一共有40个尺寸(Version)。Version 1是21 x 21的矩阵，Version 2是 25 x25的矩阵，每增加一个version，就会增加4的尺寸，公式:(V-1)*4+21.

  看下图:

  
  

  Version 40是这样的,真是令人害怕,来五个这样的二维码即可存下《浮生六记》的闺房记乐:

  
  

• 信息容积

  • 数字:最多7089字符
  • 字母:最多4296字符
  • 8位二进制数:最多2953字符
  • 日文汉字:最多1817字符

• 格式信息:

  • 表示形式是V-E,V是前面提到的version,E是容错级别,分别是:L(7%),M(15%),Q(25%),R(35%).

• 容错：

  允许存储的二维码信息出现重复部分，级别越高，重复信息所占比例越高。

• 结构图:

• Position Detection Patterns:

三个相同的探测图形,用于定位视图和方向,位于左上角、右上角、左下角.符号中遇到类似图形的可能性极小,可以在有效识别到二维码。

• Separators:
  每个探测图形和编码区域之间有一条1单位宽度的分隔符.由白色块组成.

• Timing Pattern:
  黑白色相间交替组成的一行一列两条位于横纵的两两探测图形之间,用于确定符号的密度和版本,提供决定模块坐标的基准位置.

• Alignment Patterns:
  类似小号的探测图形,中心矩形边框变为1单位,这种校正图形的数量由version来定,大于version 1的都有该校正图形.

• Encoding region:
  包含数据码字，纠错码字，版本信息，格式信息，符号字符等数据。

• Quiet zone:
  环绕整个二维码四周的4单位宽的区域.白色.

encode

数据分析-->数据编码-->纠错编码-->构造最终数据-->构造矩阵-->打上掩码-->填充格式与版本信息

• 数据分析:

  分析输入的数据流,确定编码的字符类型，按相应的字符集转换成符号字符;选择纠错等级;如果没有指定version,会采用能表示目标信息的最小version.

  字符类型的编号(中文是1101,终止符是0000):

  各尺寸的数据组成细节:

• 数据编码

  将数据字符转换为位流，每8位一个码字，整体构成一个数据的码字序列.必要的时候需加入填充字符以填满按照版本要求的数据码字数.

  先看看不同version下数据长度对应的编码的位数约定:

  支持如下编码:

  • Numeric mode|数字编码:

    数据类型编码(4位)+数据长度编码(根据version转成10或12或14位二进制数)+从左到右,
    每3个数字为一组,转成10位二进制数,剩下不满三位的转成4或7位二进制数。

    比如1314520:

    • 131 452 0
    • --> 131(0010000011) 452(0111000100) 0(0000)
    • --> 数字长度7 -->0000000111
    • --> 由上面数据分析的图,数字的编码是0001
    • --> 0001 0000000111 0010000011 0111000100 0000 0000(结束符)

    公式B=4+C+10(D DIV 3)+R.

  • Alphanumeriv mode|字符编码:0_9,AZ,以及一些符号和空格。

    编码方式和数字编码类似,区别是以2个字符为一组,转成11位二进制数,不满2个字符的转成6位。(a,b)-->a*45+b-->binary

    公式B = 4 + C + 11(D DIV 2) + 6(D MOD 2).

  • Byte mode|字节编码:

    公式B = 4 + C + 8D.

  • Mixing mode|混合编码

    各种类型的组合编码。

  • Kanji mode|日文编码(不具体展开)
  • ECI mode|特殊字符集(不具体展开)
  • Structured Append mode|附加结构编码(不具体展开)
  • FNC1 mode|特殊工业或行业使用(不具体展开)

8bit重排:接下来会对二进制比特流按照8位重排,编码总位数如果不是8的倍数,需要在末尾补0.

补齐码:每个字码是8位,重排补0以后,如果字码的长度没有到达该version的容量,需要在后面加上补齐码。
具体姿势是不断重复11101100和00010001这两个码字。

• 纠错编码

  为了能被纠错算法处理,将解析出的码字序列分块。然后把纠错码字拼到数据码字后面。有上文提到的L,M,Q,H四种纠错级别.

  • 纠错算法:

    可纠正两种类型的错误,拒读错误(错误码字的位置已知)和替代错误(错误码字的位置未知).拒读错误是没有扫描到或者无法译码的字符,替代错误是错误译码的字符。一个替代错误需要两个纠错码字来纠正。

    这里有个公式：e + 2t <= d - p

    e:拒读错误数 t:替代错误数 d:纠错码字数 p:错误译码保护码字

    主要通过里德-所罗门纠错算法 来实现。
    涉及到伽罗瓦域中的多项式算法等数学理论。这边还需要深入学习。写个//TODO_NEXT_TIME

    官方的除法电路图示是这样的:

• 构造最终数据信息

  将数据码字的块和纠错码字的块以行列交织的方式排列。

  经过上一步计算出纠错码以后得到类似这样的结果:

  左边是数据码字,右边是纠错码字。然后按列排列成:

  D1, D12, D23, D35, D2, D13, D24, D36, ... D11, D22, D33, D45, D34, D46, E1, E23, E45, E67, E2, E24, E46, E68, ... E22, E44, E66, E88.

• 构造矩阵

  将码字模块以及探测图形、分隔符、定位图形、校正图形填充到矩阵相应位置中。具体位置如图:

  以及校验图形的位置:

  QR Code中,符号字符以2个单位宽的纵列从符号的右下角开始布置,并且自右向左,自底向上。每个码字最高位应放在第一个可用的位置,中途遇到障碍就跳过,在障碍物上面或者下面继续填充。

  
  
  
  

• 打上掩码

  为了可靠性,使用掩码图形让矩阵中的黑白色块比例接近1:1并均匀分布,尽可能避免探测图形出现在别的区域.所以每个二维码咋一看,都是一模一样。

  有几点需要说明

  • 不会影响功能区(Function Patterns)
  • 对编码区域(Encoding Region)进行XOR运算(按照掩码的黑色部分颜色取反)
  • 对结果图不符合人意的部分计分
  • 评估后选择最佳的掩码(分数最低的那个)

  关于掩码方案优劣的评分标准(N1=3, N2=3, N3=40, N4=10):

  
  

  掩码标识码:

  八种掩码:

  
  

  大致步骤如下:

  
  

• 填充格式与版本信息

  • 生成格式和版本信息填入矩阵相应的区域上。

    • 格式信息:格式信息15位,5个数据位10个纠错位。数据位中前两位是纠错等级:

    第三到第五位是掩码标识。然后根据纠错算法算出10位纠错码,加载五位数据位后面。

    • 版本信息:版本信息18位,6位数据位12位纠错位。version 7~40时才有版本信息,没有任何版本信息的结果全是0,不用对版本信息做掩码。

decode

encode的逆向流程:

• 定位并获取图形,根据黑白色块转成0,1组成的数组,确定一个阈值,用该值将图像转化为一系列深色和浅色像素
• 识别格式信息
• 识别version信息
• 去掉掩码,即从格式信息中得到编码区的摆位图进行异或处理消除掩码
• 恢复数据码字和纠错码字
• 使用纠错码字进行错误检查,并纠错
• 解码数据码字