美文网首页
QRCode二维码编解码原理

QRCode二维码编解码原理

作者: 欧祎 | 来源:发表于2017-09-01 12:28 被阅读0次

    目录:

    前置知识
    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|字符编码:09,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信息
    • 去掉掩码,即从格式信息中得到编码区的摆位图进行异或处理消除掩码
    • 恢复数据码字和纠错码字
    • 使用纠错码字进行错误检查,并纠错
    • 解码数据码字

    相关文章

      网友评论

          本文标题:QRCode二维码编解码原理

          本文链接:https://www.haomeiwen.com/subject/rxghjxtx.html