二维码（QR Code）的生成原理及解析
转载自：琦小虾https://blog.csdn.net/ajianyingxiaoqinghan/article/details/78837864#comments二维码生成原理及解析代码
自从大街小巷的小商小贩都开始布满了腾讯爸爸和阿里爸爸的二维码之后，我才感觉到我大天朝共享支付的优越性。最近毕业论文写的差不多了，在入职之前多学一些东西也是好的。这里秉着好奇心，研究一下二维码的生成，并尝试性写一个二维码解析源码。
注：暂时只有二维码原理，笔者这段时间会持续研究解析代码，并随进度持续更新。
参考网址：《二维码的生成细节和原理》《QRCodeTutorial》《HelloWorld!》——知乎专栏文章《为程序员写的Reed-Solomon码解释》
一.二维码基本知识二维码另一个名称是QRCode(QuickResponseCode)，近年来在移动设备上经常使用，与传统条形码相比，可以存储更多的信息。二维码本质上是个密码算法，基本知识总结如下。首先，二维码存在40种尺寸，在官方文档中，尺寸又被命名为Version。尺寸与Version存在线性关系：Version1是21×21的矩阵，Version2是25×25的矩阵，每增加一个Version，尺寸都会增加4，故尺寸Size与Version的线性关系为：
Size=(Version−1)×4Size=(Version−1)×4Version的最大值是40，故尺寸最大值是(40-1)*4+21=177，即177x177的矩阵。
二维码结构如下图1.1所示：
图1.1二维码结构二维码的各部分都有自己的作用，基本上可被分为定位、功能数据、数据内容三部分。
定位图案：PositionDetectionPattern,定位图案：用于标记二维码矩形的大小；用三个定位图案即可标识并确定一个二维码矩形的位置和方向了；SeparatorsforPositionDetectionPatterns,定位图案分割器：用白边框将定位图案与其他区域区分；TimingPatterns,时序图案：用于定位，二维码如果尺寸过大，扫描时容易畸变，时序图案的作用就是防止扫描时畸变的产生；AlignmentPatterns,对齐图案：只有在Version2及其以上才会需要；功能数据：FormatInformation,格式信息：存在于所有尺寸中，存放格式化数据；VersionInformation,版本信息：用于Version7以上，需要预留两块3×6的区域存放部分版本信息；数据内容：剩余部分存储数据内容DataCode,数据码；ErrorCorrectionCode,纠错码；二.数据编码2.1数据编码信息二维码的数据编码信息如下图2.1,2.2中的列表所示：
图2.1模式编号指示器图2.2字符计数指示器中的位数上图2.1中，展示的是二维码支持的数据编码模式。注：其中中文编码模式为1101；
上图2.2中展示了不同版本（即不同尺寸）的二维码，单个编码对应二进制的位数。注：二维码规格说明书中，存在各式各样的编码规范表；
图2.1,2.2表格具体含义，在后面的例程中会具体讲解。
2.2数据编码形式2.2.1数字编码(NumericMode)数字编码的范围为0~9。对于数字编码，统计需要编码数字的个数是否为3的倍数：如果不是3的倍数，则剩下的1位或2位会被转为4bits或8bits（十进制转二进制），每三位数字都会被编成10bits,12bits,14bits，具体编码长度仍然需要二维码尺寸决定。
2.2.2字符编码(AlphanumericMode)字符编码的范围有：
数字0~9；大写A~Z（无小写）；几个符号$%*+-./和空格。上述字符映射为一个索引表，如下图2.3所示：
图2.3字符映射索引表图中Char表示字符，Value表示字符对应的索引值。索引表中共45种对应关系，字符编码的过程，就是将每两个字符分为一组，然后转成上图2.3的45进制，再转为11bits的二进制结果。对于落单的一个字符，则转为6bits的二进制结果。此外，根据上图2.2的设定，对不同Version的二维码使用9/11/13个二进制表示。
注：上图2.3中的SP代表空格。
2.2.3字节编码(ByteMode)可以是0-255的ISO-8859-1字符。有些二维码的扫描器可以自动检测是否是UTF-8的编码。
2.2.4日文编码(KanjiMode)日文编码同时也是双字节编码，同样也可以用于中文编码。日文与中文编码流程基本相似：
首先减去一个值；挑出差值结果的前两个16进制，乘以0xC0；加上后两个16进制位；转为13bits编码；按照日文编码集SHIFT_JIS为参照，可查询日文字符的对应编码。以“雅”与“芒”为例，转换过程如下图2.4所示：
图2.4日文编码流程展示2.2.5其他编码其他类型的编码本文中不详细说明。其中包括：
特殊字符集(ExtendedChannelInterpretationMode)：主要用于特殊的字符集，并不是所有的扫描器都支持这种编码；混合编码(StructuredAppendMode)：说明该二维码中包含了多种编码格式；特殊行业编码(FNC1Mode)：主要是给一些特殊的工业或行业用的，如GS1条形码等；2.3数据编码示例说明分别用一个数字编码与字符编码的示例，说明数据编码的过程：
2.3.1例程1：数字编码问题：对于Version1尺寸的二维码，纠错级别为H，编码为：01234567解析步骤：
将上述数字分为三组：012,345,67；查询图2.2表格内容，Version1二维码的数字编码应转换为10bits的二进制数字，故将上面三组数字转为二进制分别为：012→0000001100,345→0101011001,67→1000011；将三个二进制串连接起来：000000110001010110011000011；将数字的个数转成二进制：对于数字编码，数字长度依旧用图2.2表格中查到的10bits二进制数字来表示，数字共有8个，故数字个数的二进制形式为：8→0000001000；查询图2.1表格内容，数字编码的标志为0001，将编码标志与步骤4编码结果加到步骤3结果之前，故最终结果为：000100000010000000001100010101100110000112.3.2例程2：字符编码问题：对于Version1尺寸的二维码，纠错级别为H，编码为：AE-86解析步骤：
在图2.3的字符索引表中分别找到AE-86五个字符的索引分别为：(10,14,41,8,6)；将五个字符两两分组：(10,14)(41,8)(6)；字符编码应将字符组转换为11bits的二进制，故上述三组字符首先转为45进制后再转为二进制：(10,14)：转为45进制：10×45+14=464；再转为11bits的二进制：00111010000；(41,8)：转为45进制：41×45+8=1853；再转为11bits的二进制：11100111101；(6)：转为45进制：6；再转为6bits的二进制：000110；将步骤3中得到的三个二进制结果连接起来：0011101000011100111101000110；查询图2.2表格内容，Version1二维码的字符个数应转换为9bits的二进制数字，对于5个字符，二维码字符个数转为9bits二进制为：000000101；查询图2.1表格内容，字符编码的标志为0010，将编码标志与步骤5编码结果加到步骤4结果之前，故最终编码结果为：00100000001010011101000011100111101000110；三.结束符与补齐符对于结束符和补齐符，我们直接举例进行说明。问题：对于Version1尺寸的二维码，纠错级别为H，以笔者的英文名作为编码：CHANDLERGENG按照2.3.2字符编码例程进行分析，得到编码如下：
编码字符数CHANDLERGENG的编码00100000011010100010110100111011001010010111100101001000101011011110100000110113.1结束符在需要在对于上述字符的编码，需要在最后加上结束符。结束符为连续4个0值。加上结束符后，得到的编码如下：
编码字符数CHANDLERGENG的编码结束00100000011010100010110100111011001010010111100101001000101011011110100000110110000如果所有的编码加起来不是8的倍数，则还需要在后面加上足够的0。如上面一共有83bits，所以与8的倍数还相差两位，故在最后加上5个0，上表最终的数据变为：0010000001101010001011010011101100101001011110010100100010101101111010000011011000000000
3.2补齐符如果最后还没有达到我们最大的Bits数限制，则需要在编码最后加上补齐符(PaddingBytes)。补齐符内容是不停重复两个字节：11101100和00010001。这两个二进制转成十进制，分别为236与17，具体不知道为什么选这两个值……关于每一个Version的每一种纠错级别的最大Bits限制，可以参看QRCodeSpec的第35页到44页的Table-7一表（笔者参考的是《ISO/IEC18004》2000版），大致如下图3.1所示：
图3.1二维码纠错级别的最大Bits限制（部分）上图3.1中提到的codewords，可译为码字，一个码字是一个字节。对于Version1的H纠错级别，共需要26个码字，即104bits。现在加上用0补全的结束符，已经有了88bits，故还需要补上16bits。补齐后的编码为：
00100000011010100010110100111011001010010111100101001000101011011110100000110110000000001110110000010001
以上数据即为数据码(DataCodewords)。
四.纠错码前文提到了不同的纠错级别(ErrorCorrectionCodeLevel)。有了纠错机制，才可以使得有些二维码有了残缺也可以扫码解析出来，才可以使得二维码中心位置可以供某些商家加上对解析不必要的图标。二维码一共有四种纠错级别：
纠错水平可被修正容量L7%码字M15%码字Q25%码字H30%码字二维码对数据码加上纠错码的过程，首先要对数据码进行分组，即分成不同的块(Block)。参看如上图3.1所示QRCodeSpec的第35页到44页的Table-7中的最下方说明了分组的定义表：
图4.1二维码纠错级别说明（部分）对于表中的最后两列的内容：纠错块个数(Numberoferrorcorrectionblocks)：需要划分纠错快的个数；纠错块码字数(ErrorCorrectionCodePerBlocks)：每个块中的码字个数，即有多少个字节Bytes；表中最下面关于(c,k,r)的解释：
c：码字总个数；k：数据码个数；r：纠错码容量注：
c,k,r的关系公式：c=k+2×rc=k+2×r。纠错码容量小于纠错码个数的一般以上图4.1中的Version5+H纠错机为例：图中红色方框说明共需要4个块（上下行各一组，每组2个块）。
第一组的属性：
纠错块个数=2：该组中有两个块；(c,k,r)=(33,11,11)：该组中每个块共有33个码字，其中11个数据码，11×2=22个纠错码；第二组的属性：
纠错块个数=2：该组中有两个块；(c,k,r)=(34,12,11)：该组中每个块共有34个码字，其中12个数据码，11×2=22个纠错码；具体示例如下表所示，且由于使用二进制会使得表格过大，故转为范围在0~255的十进制。其中组1的每个块，都有11个数据码，22个纠错码；组2的每个块，都有12个数据码，22个纠错码。
组块数据每个块的纠错码1126785701348738851941195066671181342427388622198199199114511524724122322924815411723638650177236213871482351772127613375242238761952301891062481347640154271952551171292122471195071181348738826134151194615150162361723617236172369660202182124157200134271292091827085246230247706624711813417324147593310640255172822157242332292002381062481347640二维码的纠错码主要是通过里德-所罗门纠错算法(Reed-SolomonErrorCorrection)实现的。
（关于Reed-Solomon算法，现在此处占坑，回头研究了再写上去）
五.最终编码此时得到了数据，但还不能开始画图，因为二维码还需要将数据码与纠错码的各个字节交替放置。
5.1穿插放置继续以第四章中给出的示例为例，给出其穿插放置的过程。
5.1.1数据码穿插放置第四章示例中的数据码如下表所示：
块数块1678570134873885194119506块26671181342427388622198199块32471195071181348738826134块419461515016236172361723617提取每一列数据：
第一列：67,66,247,194；第二列：85,7,119,6；……第十一列：6,199,134,17；第十二列：151,236；将上述十二列的数据拼在一起：67,66,247,194,85,7,119,6,…,6,199,134,17,151,236。
纠错码如下表所示：
块数块11991145115247241223229248154117块2177212761337524223876195230189块3966020218212415720013427129209块417324147593310640255172822同样的方法，将22列数据放在一起：199,177,96,173,11,212,60,24,…,148,117,118,76,235,129,134,40。
上述部分即为二维码的数据区。
5.2剩余位(RemainderBits)对于某些Version的二维码，得到上面的数据区结果长度依旧不足，需要加上最后的剩余位。比如对于Version5+H纠错等级的二维码，剩余位需要加7bits，即加7个0。参看QRCodeSpec的Table-1一表即可查询不同Version的剩余位信息，如下图5.1所示：
图5.1不同Version的剩余位六.二维码的绘制终于讲到二维码绘制过程了，绘制的过程按照顺序对图1.1中各个重要部分依次讲解。
6.1定位图案(PositionDetectionPattern)首先在二维码的三个角上绘制定位图案。定位图案与尺寸大小无关，一定是一个7×7的矩阵。如下图6.1所示：
图6.1定位图案(PositionDetectionPattern)6.2对齐图案(AlignmentPattern)然后绘制对齐图案。对齐图案与尺寸大小无关，一定是一个5×5的矩阵。如下图6.2所示：
图6.2对齐图案(AlignmentPattern)对齐图案绘制的位置，可参看QRCodeSpec的Table-E.1一表查询，部分内容如下图6.3所示：
图6.3对齐图案位置索引表（部分）下图6.4是上述表格中Version8的一个例子，对于Version8的二维码，行列值在6,24,42的几个点都会有对齐图案。
图6.4对齐图案例程1下图6.5是最近我老妈怂恿我用支付宝抢红包时给我发来的二维码，该二维码中只有一个对齐图案，故Version应在V2——V6之间。
图6.5对齐图案例程26.3时序图案(TimingPattern)时序图案是两条连接三个定位图案的线，如下图6.6所示：
图6.6时序图案例程1依旧拿支付宝红包的二维码为例，其时序图案如图6.7所示：
图6.7时序图案例程26.4格式信息格式信息如下图6.8所示：
图6.8格式信息格式信息在定位图案周围分布，由于定位图案个数固定为3个，且大小固定，故格式信息也是一个固定15bits的信息。每个bit的位置如下图6.9所示：（注：图中的DarkModule是固定永远出现的）
图6.9格式信息位置15bits中数据，按照5bits的数据位+10bits纠错位的顺序排列：
数据位占5bits：其中2bits用于表示使用的纠错等级(ErrorCorrectionLevel)，3bits用于表示使用的蒙版(Mask)类别；纠错位占10bits：主要通过BCHCode计算；为了减少扫描后图像识别的困难，最后还需要将15bits与101010000010010做异或XOR操作。因为我们在原格式信息中可能存在太多的0值（如纠错级别为00，蒙版Mask为000），使得格式信息全部为白色，这将增加分析图像的困难。
纠错等级的编码如下图6.10的表格所示：
图6.10纠错等级编码关于蒙版图案的生成，在后文6.7中具体说明。格式信息的示例如下：
假设存在纠错等级为M（对应00），蒙版图案对应000，5bits的数据位为00101，10bits的纠错位为0011011100：则生成了在异或操作之前的bits序列为：001010011011100与101010000010010做异或XOR操作，即得到最终格式信息：100000011001110
6.5版本信息(VersionInformation)对于Version7及其以上的二维码，需要加入版本信息。如下图6.11蓝色部分所示：
图6.11版本信息版本信息依附在定位图案周围，故大小固定为18bits。水平竖直方向的填充方式如下图6.12所示：
图6.12版本信息填充方式18bits的版本信息中，前6bits为版本号(VersionNumber)，后12bits为纠错码(BCHBits)。示例如下：
假设存在一个Version为7的二维码（对应6bits版本号为000111），其纠错码为110010010100；则版本信息图案中的应填充的数据为：000111110010010100
6.6数据码与纠错码此后即可填充第五章得到的数据内容了。填充的思想如下图6.13的Version3二维码所示，从二维码的右下角开始，沿着红线进行填充，遇到非数据区域，则绕开或跳过。
图6.13二维码数据填充（原始版）然而这样难以理解，我们可以将其分为许多小模块，然后将许多小模块串连在一起，如下图6.14所示（截取自QRCodeSpec的图15）：
图6.14二维码数据填充小模块可以分为常规模块和非常规模块，每个模块的容量都为8。常规情况下，小模块都为宽度为2的竖直小矩阵，按照方向将8bits的码字填充在内。非常规情况下，模块会产生变形。填充方式上图6.14，图中深色区域（如D1区域）填充数据码，白色区域（如E15区域）填充纠错码。遍历顺序依旧从最右下角的D1区域开始，按照蛇形方向（D1→D2→…→D28→E1→E2→…→E16→剩余码）进行小模块的填充，并从右向左交替着上下移动。下面给出若干填充原则：
原则1：无论数据的填充方向是向上还是向下，常规模块（即8bits数据全在两列内）的排列顺序应是从右向左，如下图6.15所示；
图6.15常规模块内的填充方向原则2：每个码字的最高有效位（即第7个bit）应置于第一个可用位。对于向上填充的方向，最高有效位应该占据模块的右下角；向下填充的方向，最高有效位占据模块的右上方。注：对于某些模块（以下图6.17为例），如果前一个模块在右边模块的列内部结束，则该模块成为不规则模块，且与常规模块相比，原本填充方向向上时，最高位应该在右上角，此时则变为左下角；原则3：当一个模块的两列同时遇到对齐图案或时序图案的水平边界时，它将继续在图案的上方或下方延续；原则4：当模块到达区域的上下边界（包括二维码的上下边界、格式信息、版本信息或分隔符）时，码字中任何剩余bits将填充在左边的下一列中，且填充方向反转；如下图6.16中的两个模块遇到了二维码的上边界，则方向发生变化；
图6.16非常规模块填充方向的改变（举例于QRCodeSpec图13）原则5：当模块的右一列遇到对齐图案，或遇到被版本信息占据的区域时，数据位会沿着对齐图案或版本信息旁边的一列继续填充，并形成一个不规则模块。如果当前模块填充结束之前，下一个的两列都可用，则下一个码字的最高有效位应该放在单列中，如下图6.17所示：
图6.17模块单列填充6.7蒙版图案按照上述思路即可将二维码填充完毕。但是那些点并不均衡，如果出现了大面积的空白或黑块，扫描识别会十分困难，所以按照在前文6.4中格式信息的处理思路，对整个图像与蒙版进行蒙版操作(Masking)，蒙版操作即为异或XOR操作。二维码又8种蒙版可以使用，如下图6.18所示，公式也在图中说明。蒙版只会和数据区进行异或操作，不会影响与格式信息相关的功能区。注：选择一个合适的蒙版也是有一定算法的。
蒙版图案如下图6.18所示，对应的产生公式与蒙版ID如下图6.19的表格所示：
图6.18蒙版图案图6.19蒙版图案产生公式蒙版操作的过程与对比图如下图6.20所示，图中最上层是没有经过蒙版操作的原始二维码，其中存在大量黑色区域，难以后续的分析识别。经过两种不同蒙版的处理，可以看到最后生成的二维码变的更加混乱，容易识别。
图6.20蒙版操作示例蒙版操作之后，得到的二维码即为最终我们平常看到的结果。
七.源码笔者原本准备用C++与OpenCV写一个二维码解析程序，现在学了二维码的原理后，发现好难。另外网上关于二维码解析与生成的程序基本都是用Python写的，笔者又想找个合适机会学习一下Python，所以这段时间就准备从二维码入手，学习一下Python的基础～
源码及解析笔者会随学习的进度持续更新～
八.后记笔者学习完毕二维码内容后不禁感叹，二维码规则的制定当真是凝聚了多少研究者的心血。学无止境，在知识的海洋中，当真是需要抱着敬畏之心和谦卑的态度，才能体会到这片海洋的浩瀚。研究二维码的过程十分有趣，学到了不少东西，后续过程中笔者会持续更新对二维码的学习心得体会～
二维码制作软件
二维码制作软件在现在的生活中，我们的身边充满了二维码，游戏等不需要手动输入长篇网址，只需扫一下二维码即可进入，当然二维码用于营销方面也是最佳的，为了给客户提供方便就需要二维码生成器来帮忙，二维码生成软件可以将产品网址、信息等全部融入二维码中，对方只要拿出手机一扫就可以浏览到。下面就为大家带来了二维码制作软件，快来下载使用吧！
分享到：更多合集