QR二维码编、解码原理.ppt

二二维码基基础-QR（Quick Response）码2I.QR码的编码码的编码II.QR码的解码码的解码 纲纲 要要3数据信息及数据信息的数据信息及数据信息的纠错码纠错码包含版本信息，只有版本包含版本信息，只有版本740的符号有版本信息，的符号有版本信息，其余版本全为其余版本全为0 每个QR码符号由名义上的正方形模块构成，组成一个正方形阵列，它由编码区域和包括寻象图形、分隔符、定位图形和校正图形在内的功能图形组成。功能图形不能用于数据编码。符号的四周由空白区包围。下图为QR码版本7符号的结构图。迅速地识别可能的迅速地识别可能的QR码码符号，明确地确定视场符号，明确地确定视场中符号的位置和方向中符号的位置和方向作用是确定符号的密度和作用是确定符号的密度和版本，提供决定模块坐标版本，提供决定模块坐标的基准位置。的基准位置。补正补正QR码的歪斜。码的歪斜。包含符号所使用的纠错包含符号所使用的纠错等级和掩模图形信息。等级和掩模图形信息。编码编码编码：编码：QR码符号的结构码符号的结构41.数据分析2.数据编码3.纠错编码4.构造最终信息5.在矩阵中布置模块 6.掩模7.格式和版本信息确定要进行编码的字符类型，选择所需的版本信息和纠错等级。确定要进行编码的字符类型，选择所需的版本信息和纠错等级。采用既定规则，数据字符转换为位流，加必要符号，后将位流转换为码字。采用既定规则，数据字符转换为位流，加必要符号，后将位流转换为码字。生成纠错码字加到数据码字后。生成纠错码字加到数据码字后。按规则将每一块中置入数据和纠错码字，必要时加剩余位。按规则将每一块中置入数据和纠错码字，必要时加剩余位。将寻像图形、分隔符、矫正图形与码字，按规则排列，放入二维码矩阵。将寻像图形、分隔符、矫正图形与码字，按规则排列，放入二维码矩阵。用八种掩模图形依次对符号的编码区域的位图进行掩模处理，评价所得到用八种掩模图形依次对符号的编码区域的位图进行掩模处理，评价所得到的的8种结果，选择最优的一种。种结果，选择最优的一种。生成版本信息（如果需要）和格式信息，构成符号。生成版本信息（如果需要）和格式信息，构成符号。编码编码编码：编码：QR码的编码流程码的编码流程51.数据分析数据分析：确定要进行编码的字符类型，选择所需的版本信息和纠错等级确定要进行编码的字符类型，选择所需的版本信息和纠错等级编码编码例：对数字例：对数字0123456789012345（16个数字字符）进行编码，生成个数字字符）进行编码，生成QR码。码。1.扩充解释（ECI）模式，数字模式，字母数字模式，8位字节模式，中国汉字模式，日本汉字模式，混合模式，结构链接模式，FNCI模式2.62.数据编码数据编码：采用既定规则，数据字符转换为位流，加必要符号，后将位流转换为码字采用既定规则，数据字符转换为位流，加必要符号，后将位流转换为码字编码编码例：对数字例：对数字0123456789012345（16个数字字符）进行编码，生成个数字字符）进行编码，生成QR码。码。1)分为分为3位一组：位一组：012 345 678 901 234 52)将每组转换为二进制：将每组转换为二进制：0120000001100 3450101011001 6781010100110 9011110000101 2340011101010 501013)将二进制数连接为一个序列：将二进制数连接为一个序列：0000001100 0101011001 1010100110 1110000101 0011101010 01014)将字符计数指示符转换为二进制（查表知版本将字符计数指示符转换为二进制（查表知版本1-H为为10位）：位）：字符数为：1600000100005)加入模式指示符加入模式指示符0001（查表）以及字符计数指示符的二进制数据：（查表）以及字符计数指示符的二进制数据：0001 0000010000 0000001100 0101011001 1010100110 1110000101 0011101010 01016）数字模式中位流的长度计算公式：）数字模式中位流的长度计算公式：B=4+C+10（D DIV 3）+R=4+10+50+4=6872.数据编码数据编码：采用既定规则，数据字符转换为位流，加必要符号，后将位流转换为码字采用既定规则，数据字符转换为位流，加必要符号，后将位流转换为码字编码编码例：对数字例：对数字0123456789012345（16个数字字符）进行编码，生成个数字字符）进行编码，生成QR码。码。7）添加终止符：）添加终止符：查表可知版本1-H的数据位数应为72，故需添加终止符序列0000，此时数据位流为72位，满足版本要求。8）填充位和填充码字：）填充位和填充码字：本例中，数据位流长度为72位，满足数据容量要求，无需添加填充位和填充码字。9）位流到码字的转换：）位流到码字的转换：所得的数据位流将被分为一个个码字，所有的码字长度都是8位。综上，所得到的数据码字序列为：综上，所得到的数据码字序列为：00010000 01000000 00001100 01010110 01101010 01101110 00010100 11101010 01010000（共9个码字）83.纠错编码纠错编码：生成纠错码字加到数据码字后生成纠错码字加到数据码字后编码编码例：对数字例：对数字0123456789012345（16个数字字符）进行编码，生成个数字字符）进行编码，生成QR码。码。编码码字矩阵编码码字矩阵校验矩阵校验矩阵编码码字多项式：编码码字多项式：前前9位为数据码字位为数据码字 后后17位为纠错码字位为纠错码字93.纠错编码纠错编码：生成纠错码字加到数据码字后生成纠错码字加到数据码字后编码编码例：对数字例：对数字0123456789012345（16个数字字符）进行编码，生成个数字字符）进行编码，生成QR码。码。定义：在任何定义：在任何q阶伽罗华域阶伽罗华域GF（q）中都能找到一个）中都能找到一个，能用它的幂次表示，能用它的幂次表示q-1个非零元个非零元素。素。QR码的纠错码生成是通过码的纠错码生成是通过GF（28）来进行的，来进行的，GF（28）中的元素组成一个循环群：中的元素组成一个循环群：（1，1，254)，其中其中255=0=1，则称，则称是是GF（28）的本原域元素。的本原域元素。0 254 可用可用0000 0001 1111 1111 来表示来表示同时，同时，为为P（X）=0的根。其中，的根。其中，P（X）是以）是以GF（28）上上8次首一既约多项式，以次首一既约多项式，以P(X)为模的多项式剩余类环构成为模的多项式剩余类环构成28阶伽罗华域。阶伽罗华域。本例中，本原多项式为本例中，本原多项式为P(X)=X8+X4+X3+X2+1。用用i模模P（）可以得到域元素和二进制比特串的对照表（如图）。）可以得到域元素和二进制比特串的对照表（如图）。103.纠错编码纠错编码：生成纠错码字加到数据码字后生成纠错码字加到数据码字后编码编码例：对数字例：对数字0123456789012345（16个数字字符）进行编码，生成个数字字符）进行编码，生成QR码。码。113.纠错编码纠错编码：生成纠错码字加到数据码字后生成纠错码字加到数据码字后编码编码例：对数字例：对数字0123456789012345（16个数字字符）进行编码，生成个数字字符）进行编码，生成QR码。码。(c,k,r):c=码字总数码字总数k=数据码字数数据码字数r=纠错容量纠错容量 纠错容量小于纠错码字数的纠错容量小于纠错码字数的一半，以减少错误译码的可能一半，以减少错误译码的可能性性生成多项式：生成多项式：g(x)=(x-0)(x-1)(x-n-1)=(x-0)(x-1)(x-16)其中其中n为生成多项式的次数，为生成多项式的次数，也就是纠错码字数。本例中，也就是纠错码字数。本例中，纠错码字数为纠错码字数为17，生成多项式，生成多项式如图所示。如图所示。12（i=0,1,2,，16）3.纠错编码纠错编码：生成纠错码字加到数据码字后生成纠错码字加到数据码字后编码编码例：对数字例：对数字0123456789012345（16个数字字符）进行编码，生成个数字字符）进行编码，生成QR码。码。数据码字的多项式形式为数据码字的多项式形式为：d(x)=d0+d1x+d2x2+d8x8（有9个数据码字）生成多项式为：生成多项式为：g(x)=编码后的表达式为：编码后的表达式为：纠错码字多项式其中，纠错码字是数据码字被纠错码多项式其中，纠错码字是数据码字被纠错码多项式g(x)除得的余数。除得的余数。纠错码多项式求出后，将系数纠错码多项式求出后，将系数i按对照表转换为位流，加到数据位流后面，即可求出整个按对照表转换为位流，加到数据位流后面，即可求出整个编码数据位流。编码数据位流。C（X）C(i)=0=g(x)q(x)（数据码字多项式）（纠错码字多项式）132024/5/21 周二13144.构造最终信息构造最终信息：按规则将每一块中置入数据和纠错码字，必要时加剩余位按规则将每一块中置入数据和纠错码字，必要时加剩余位编码编码例：对数字例：对数字0123456789012345（16个数字字符）进行编码，生成个数字字符）进行编码，生成QR码。码。按如下步骤构造最终的码字序列（数据码字加上纠错码字，必要时加上剩余码字）。1）根据版本和纠错等级将数据码字序列分为n块。2）对每一块，计算相应块的纠错码字。3）依次将每一块的数据和纠错码字装配成最终的序列：数据块1的码字1；数据块2的码字1；数据块3的码字1；以此类推至数据块n-1的最后的码字；数据块n的最后的码字；随后，纠错块1的码字1，纠错块2的码字1，以此类推至纠错块n-1的最后的码字；纠错块n的最后的码字。查表可知，本例中查表可知，本例中1-H版本的数据码字序列为版本的数据码字序列为1块，不需要分开，故无需构造最终信息。块，不需要分开，故无需构造最终信息。155.在矩阵中布置模块在矩阵中布置模块：将寻像图形、分隔符、校正图形与码字，按规则排列，放入二维码矩阵将寻像图形、分隔符、校正图形与码字，按规则排列，放入二维码矩阵编码编码例：对数字例：对数字0123456789012345（16个数字字符）进行编码，生成个数字字符）进行编码，生成QR码。码。图形表示：图形表示：00010000排列规则排列规则 数据码字数据码字9个，纠错码字个，纠错码字17个，共个，共26个码字，就是个码字，就是26块码字区。块码字区。将码字，寻像图形，分隔符，校正图形按规则排列，放入二维码中即可将码字，寻像图形，分隔符，校正图形按规则排列，放入二维码中即可16掩模图形参考条件000(i+j)mod 2=0001i mod 2=0010j mod 3=0011(i+j)mod 3=0100(i div 2)+(j div 3)mod 2=0101(i j)mod 2+(i j)mod 3=0110(i j)mod 2+(i j)mod 3)mod 2=0111(i j)mod 3+(i+j)mod 2)mod 2=06.掩模掩模：依次对符号的编码区域的位图进行掩模处理，评价所得结果，选择最优一种。依次对符号的编码区域的位图进行掩模处理，评价所得结果，选择最优一种。编码编码例：对数字例：对数字0123456789012345（16个数字字符）进行编码，生成个数字字符）进行编码，生成QR码。码。为了QR码阅读的可靠性，最好均衡地安排深色与浅色模块。应尽可能避免位置探测图形的位图1011101出现在符号的其他区域。为了满足上述条件，应按以下步骤进行掩模。1)掩模不用于功能图形2)用多个矩阵图形连续地对已知的编码区域的模块图形（格式信息和版本信息除外）进行XOR操作。XOR操作将模块图形依次放在每个掩模图形上，并将对应于掩模图形的深色模块的模块取反（浅色变成深色，或相反）。3)对每个结果图形的不合要求的部分记分，以评估这些结果。4)选择得分最低的图形。版本版本1符号的所有的掩模图形，用掩模图形参符号的所有的掩模图形，用掩模图形参考考000到到111的掩模结果。的掩模结果。177.格式和版本信息格式和版本信息：生成版本信息（如果需要）和格式信息，构成符号生成版本信息（如果需要）和格式信息，构成符号编码编码例：对数字例：对数字0123456789012345（16个数字字符）进行编码，生成个数字字符）进行编码，生成QR码。码。格式信息为格式信息为15位，其中有位，其中有5个数据位，个数据位，10个是用个是用BCH（15，5）编码计算得到的纠错位。）编码计算得到的纠错位。其中，数据位的第其中，数据位的第1,2位是符号的纠错等级，第位是符号的纠错等级，第3到第到第5位是掩模图形参考。位是掩模图形参考。格式信息掩模是与格式信息掩模是与101010000010010进行进行XOR异或运算。异或运算。本例中纠错等级为本例中纠错等级为H，查表知，二进制指示符为，查表知，二进制指示符为10。掩模图形参考根据上页结果确定。掩模图形参考根据上页结果确定。版本信息为版本信息为18位，其中，位，其中，6位数据位，位数据位，12位通过位通过BCH（18,6）编码计算出的纠错位。）编码计算出的纠错位。只有版本只有版本7到版本到版本40的符号包含版本信息，没有任何版本信息的结果全为的符号包含版本信息，没有任何版本信息的结果全为0。纠错等级二进制指示符L01M00Q11H1018解码解码1.计算伴随多项式的值。计算伴随多项式的值。2.求错误位置多项式。求错误位置多项式。3.求错误位置多项式的根。求错误位置多项式的根。4.求错误值并对码字进行错误求错误值并对码字进行错误纠正。纠正。图像处理方法图像处理方法解码：解码：QR码的解码流程码的解码流程19解码解码编码后的表达式为：=C25X25+C24X24+C1X1+C0=q(x)g(x)C（X）例：例：以版本以版本1-M为例，为例，GF（28）上有码字）上有码字26个，其中纠错码字个，其中纠错码字10个，可纠正个，可纠正4个码字。个码字。1.计算伴随多项式的值计算伴随多项式的值=ea1a1+ea2a2+ea3a3+ea4a4=ea1+ea2+ea3+ea4=ea1（7）a1+ea2（7）a2+ea3（7）a3+ea4（7）a4 若若Si0(i=0,1,2,3,4,5,6,7),则接受到的码字无错误。则接受到的码字无错误。若若Si0(i=0,1,2,3,4,5,6,7)，则接收到的码字有误，需先，则接收到的码字有误，需先找出错误码字位置找出错误码字位置，再，再算出错误算出错误值值，最后，最后进行纠错进行纠错，得到正确码字。，得到正确码字。20解码解码例：例：以版本以版本1-M为例，为例，GF（28）上有码字）上有码字26个，其中纠错码字个，其中纠错码字10个，可纠正个，可纠正4个码字。个码字。令ai为错位码字的位置（ai=0-25）。找到错误码字位置ai 即可算出错误码字eai。故需先求出1,2,3,4。得到多项式(z)。将-ai依次带入(z)，使(z)=0的项即为所求。2.找出错误码字位置找出错误码字位置是一个相对于是一个相对于的值，不是一个绝对值。有的值，不是一个绝对值。有4个错误和有个错误和有5个错误的个错误的 值是不一样的。值是不一样的。21解码解码例：例：以版本以版本1-M为例，为例，GF（28）上有码字）上有码字26个，其中纠错码字个，其中纠错码字10个，可纠正个，可纠正4个码字。个码字。同理可得：2.找出错误码字位置找出错误码字位置22解码解码例：例：以版本以版本1-M为例，为例，GF（28）上有码字）上有码字26个，其中纠错码字个，其中纠错码字10个，可纠正个，可纠正4个码字。个码字。2.找出错误码字位置找出错误码字位置根据上式，确定错误位置矩阵为：根据上式，确定错误位置矩阵为：将将-ai依次带入依次带入(z)，使，使(z)=0的项即为所求（只要是错误的的项即为所求（只要是错误的-ai带入后，结果都为带入后，结果都为0）。）。ai即为错误码字位置，接下来用错误码字位置找到错误值进行纠错。（注：若即为错误码字位置，接下来用错误码字位置找到错误值进行纠错。（注：若 ai 的个数的个数多余多余4个，则无法进行纠错。）个，则无法进行纠错。）解此矩阵，即可求出解此矩阵，即可求出1,2,3,4。(z)即可求出：即可求出：23解码解码例：例：以版本以版本1-M为例，为例，GF（28）上有码字）上有码字26个，其中纠错码字个，其中纠错码字10个，可纠正个，可纠正4个码字。个码字。3.找出错误值找出错误值上式中上式中a1,a2,a3,a4已知，求得错误值已知，求得错误值ea1,ea2,ea3,ea4即可进行纠错。即可进行纠错。24解码解码例：例：以版本以版本1-M为例，为例，GF（28）上有码字）上有码字26个，其中纠错码字个，其中纠错码字10个，可纠正个，可纠正4个码字。个码字。4.纠错纠错 将4个错误值与其错误位置对应的码字值进行异或运算，得到纠错后的码字值，完成错误纠正。假设：假设：从二维条码符号图像中还原出的一个错误码字值从二维条码符号图像中还原出的一个错误码字值 ri=1101 0001计算得出的错误值是计算得出的错误值是 ei=0000 0110用用 ，ci即为正确的数据码字值。即为正确的数据码字值。25谢谢大家谢谢大家!262024/5/21 周二26