安卓系统下的二维码生成与识别方法研究-广电信息科学与工程毕业论文

编号： 毕业设计说明书 题目： 安卓系统下的二维码生成安卓系统下的二维码生成 与识别方法研究与识别方法研究 学院：电子工程与自动化学院 专业：光电信息科学与工程 学生姓名：李朝庭 学号：1300820112 指导教师：陈元枝 职称：教授 题目类型：题目类型：理论研究实验研究工程设计工程技术研究软件开发 2017 年 5 月 31 日 桂林电子科技大学毕业设计（论文）报告用纸 摘要 二维码能存储大量的数据信息，具有识别速度快、准确率高等许多优点，其应用载 体广泛， 使得这种技术在自动化领域中的应用变得日益广泛。 其中， 快速矩阵响应码 （简 称 QR 码）属于二维码的一种，它是人们生活中接触最多的二维码。目前 QR 码的生成 和识别很多都是在 PC 平台上完成，而且在手机上也应用广泛。随着 Android 智能设备 的迅速普及，为了使这一技术适应当今“大数据”信息爆炸时代的脚步，研究如何在 Android 系统下对二维码的生成与识别的这一技术别变得尤其重要。 本文结合了目前 QR 码的生成与识别理论标准的基础上，学习相关条码标准生成与识别步骤，在安卓开发平 环境下设计了 QR 码的生成与识别的相应算法，完成从输入数据到生成与其对应的二维 码以及对设备中的二维码图片进行解码并还原出其中编码信息，学习了 Android 系统下 QR 码的生成与识别方法。 关键词：关键词：快速矩阵响应码；生成；识别；二维码算法；安卓系统 桂林电子科技大学毕业设计（论文）报告用纸 Abstract The two-dimension code can stored a lot of information, it works fast and use widely in this days, many advantages of high accuracy makes this kind of carrier things at information ,and playing an important role in the field of automation. Among them, the fast matrix response code (QR codes) is a type of the two-dimension code and it is the most widelly type of he two-dimension code in peoples lives. But the QR codes generation and recognition are bouth base on the PC platform completely now, and use in cellphone verey popullar. This status can lead a resulting that it can not adapt to the year of “big data“ information explosion . However, with the rapid development of Android smart devices, it is important to learn how to build an application about QR codes in an Android platform. This passage will state something theory abou based on the analysis of the current problems existing in the QR code generation and recognition, study the steps of generation and recognition.In finally, this passage according to the relevant barcode standard flat in the Android to design the QR code generation and recognition algorithm, work out an image from the input to generate the corresponding QR code and decoding an image from device by the function of the coded information.In a word ,it sdudies the Android system under the QR code generation and recognition process and methods. Key words: QR Code; Generation; Recognition; Algorithm; Android system 桂林电子科技大学毕业设计（论文）报告用纸 目录 1绪论1 1.1 国内外研究背景1 1.2 本论文的工作内容1 2二维码的描述.2 2.1 QR 码的基本性质.2 2.2 QR 码的结构.2 3编码过程.4 3.1 数据编码的生成5 3.1.1 数据分析与编码.5 3.1.2 纠错码的生成.8 3.1.3 构造最终序列.10 3.2 整个符号的生成10 3.2.1 功能模板的布置与掩模处理.10 3.2.2 添加格式与版本信息.13 3.2.3 编码区与功能区的整合.15 4解码过程.17 4.1 解码流程17 4.2 解码具体过程18 4.2.1 检测定位符及读取版本信息.18 4.2.2 确定采样网格和校正图形.20 4.2.3 去除掩模与信息纠错恢复.22 5安卓系统上实现编码解码24 5.1 安卓系统概述与环境搭建24 5.2 系统框架与界面设计26 5.3 实现二维码的生成28 5.3.1 编码输入的数据.28 5.3.2 数据位流的转换与纠错码的生成.32 5.3.3 掩模处理与最终序列图形的布置.33 5.4 实现二维码的识别33 5.4.1 图像预处理.33 桂林电子科技大学毕业设计（论文）报告用纸 5.4.2 格式信息的读取.34 5.4.3 消除掩模与错误检查.35 5.4.4 字符的译码输出.35 5.5 其它功能36 5.5.1 历史记录的保存.36 5.5.2 摄像头扫描二维码.37 5.6 最终实现效果39 谢辞.44 参考文献45 附录 2QR 码的掩膜图形.50 附录 3APP 界面51 桂林电子科技大学毕业设计（论文）报告用纸 第 1 页 共 51 页 1绪论 1.1 国内外研究背景 国外对二维码相关生成与识别技术的研究于上世纪 80 年代开始，对于这种符号的 编码技术， 目前已经推出多种不同类型的码制1。 在二维码各种参数的标准化的研究中， 美国标准化协会以及国际自动识别制造商协会在十几年前已经公布了许多项关于这种 技术的不同标准2。其中 QR 码是二维码其中的一种，以其独特的优势，目前它的应用 已经在各个国家发展迅速3。 但是， 我国对这方面技术的研究大约在上世纪 90 年代才开 始，与其它西方国家特别是与日韩等国相比，我国在二维码相关技术的的研究应用远远 相对落后。在我国，制约着二维码发展的因素除了得不到各大运营商的相关支持之外， 还存在技术、统一指标、运营模式等因素的制约4。 目前， 国内 QR 码的生成和识别大部分是在 Windows 平台下完成的， 而且手持式移 动设备上的二维码生成识别软件一般都存在识别速度慢、 效率低、 精确率不高等特点5。 所以，研究如何在手持设备系统上对二维码的生成与识的技术别变得尤其重要。本文结 合 QR 码生成以及识别理论和步骤，学习了如何提高输入的各种类型数据的编码方式， 对各种数据进行分类编码，以及如何提高编码效率与解码效率等问题。学习了如何按照 国家快速响应矩阵码的标准设计出相关的生成与识别算法，并在 Windows 环境下利用 发工具开发一款基于 Android 系统下的 QR 码生成与识别软件，实现对 QR 码进行生成 与识别操作。 1.2 本论文的工作内容 本设计主要目的是学习二维码的编码解码原理， 学习安卓系统以及在该系统下如何 设计相应的算法来实现编码解码功能。论文首先介绍了 QR 码的基本结构与相关特性参 数以及它的研究、发展状况以及相关编码以及解码理论，然后根据理论在安卓系统平台 上设计了一款能够生成 QR 码的 APP，本次设计的 APP 基于安卓手机平台实现，能够 在各种环境下生成与识别相应的 QR 码。 本文分为六大章节： 第 1 章介绍了 QR 码的相关背景以及本设计相关的工作内容； 第 2 章阐述了 QR 码的基本结构与相关特性参数； 第 3 章阐述了 QR 码的编码原理以及编码的步骤； 第 4 章阐述了如何从一张具有 QR 码信息的图片中识别出对应信息的过程； 第 5 章阐述了在安卓系统下实现了编码解码的算法以及最终的编码解码效果； 第 6 章是对本设计的简要总结以及关未来的一些展望。 桂林电子科技大学毕业设计（论文）报告用纸 第 2 页 共 51 页 2二维码的描述 2.1 QR 码的基本性质 QR 码是一种分布在平面上特殊的二维矩阵符号，它用一个黑色模块的点表征二进 制中的数字“1”，白色模块的点表征二进制数字“0”。许许多多黑白相间的点组成了 一段段位流，位流字节的信息一般用 16 进制数来表示。它有 40 个不同的版本，其中版 本最低的是 2121 个黑白相间的点。从版本 1版本 40，每个版本模块边长的点数比 前一版本多出 4 个，直至最大版本为 177177 个模块点。它能表示的编码字符有： 数字型（09）； 字母数字型（09，全部大写字母以及 9 个特殊的标点符号）； 八位字节型（ASCII 字符集）； 中国汉字字符型（GB2312 字符集）。 除此之外，即使二维码受到损坏、遮挡等仍能还原其全部信息。QR 码支持 4 种纠 错等级，按照容错率从低到高分别表示为 L、M、Q 和 H。在不同的纠错等级情况下， 每种情况可恢复编码字符的比例大约是 7%、15%、25%和 30%6。 为了在识别的时候提高效率，QR 码还加入了固有的掩模。掩模处理可以让二维码 矩阵中黑色与白色模块分布的个数比接近 1:1，也使得二维码更加美观。 2.2 QR 码的结构 QR 码是由许多长宽一样的正方形小块构成一个大的点矩阵，这个矩阵主要由编码 区域以及功能区域构成。编码区包含了 QR 码的格式、版本以及数据和纠错码字等。功 能图形区的结构由位置寻像图形、定位图形、校正图形以及分隔符一起的各种特殊的图 形单元组成的区域，这个区不用于实际数据的表示。编码区和功能区的周围还有 4 个模 块宽度的空白区，整个 QR 码的结构如图 2.1 所示： 图 2.1 QR 码的基本结构 桂林电子科技大学毕业设计（论文）报告用纸 第 3 页 共 51 页 功能图形区不含任何实际的编码数据，其作用是辅助编码区实现码字的识别。功能 区中的寻像图形由 3 个一样的位置探测图形构成，它们分别安放在 QR 码的左上角、左 下角以及右上角，它用于找出 QR 码矩阵在一幅图像中的具体位置。每一个位置探测图 形模块如图 2.2 所示，它可以当作是由 3 个同心正方形构成的一个小矩阵，这 3 个同心 正方形分别为外围的 77 个黑色模块、中间的 55 个白色模块、里面的 33 个黑色 模块，每个同心正方形大小的比例为 1：1：3：1：1。由于掩模的作用，QR 码中其它 位置遇到一样的图形的可能性非常小， 利用这一特点可以在整张图片中迅速地识别可能 的 QR 码位置探测图形。经过探测 QR 码中这三个同样的图形可以快速地确定一幅图片 中 QR 码的位置以及方向。 在每个探测图形与编码区之间存在大小为 1 个点的白色间隔， 使探测图形区与编码区互相分开，以免在定位时产生不必要的干扰。 图 2.2 QR 码位置探测图形的结构 除了位置探测图形，QR 码编码区中还存在定位图形。它分为垂直定位图形和水平 定位图形这两部分，而且它的宽度随着版本数目的变高而增大。这两部分分别为尺寸为 1 且由黑色块与白色块混合组成的行或列，其始端和末端都是黑色模块。如图 2.1 所示， 水平部分定位图形在编码区上端的两个位置探测图形之间， 垂直方向的定位图形处于编 码区左端的两个位置探测图形的中间。 为了高效、迅速地在复杂的环境中搜索到需要的 QR 码信息，编码区中还加入了校 正图形。每个校正图形与一个位置探测图形的中心类似，它由 3 个同心的正方形边框组 成，分别是 55 个黑色的小正方形、33 个白色的小正方形以及处在中央的一个黑色 模块（如图 2.1 所示）。它的个数也是由编码的版本而定，版本 2 及以上的 QR 码具有 一定个数的校正图形7，它的具体个数以及位置参见国家标准GB/T 182842000中 的附录 E。 数据编码区编码了全部数据编码字内容，如图 2-1 所示。它由编码内容、纠错编码、 版本信息以及格式符号等模块组成。数据内容和纠错码字由用户输入的字符串决定，数 据内容是按照输入数据类型的不同，然后经过特定的编码方式得到的一长串二进制位 流。纠错码字可以看作是数据内容的备份，它也是由特定的算法得到的一系列的二进制 位流，主要用来检查和纠错数据内容中发生错误的信息段。 桂林电子科技大学毕业设计（论文）报告用纸 第 4 页 共 51 页 3编码过程 整个 QR 码的编码包括功能图形区的编码和数据编码区的编码。功能区的编码是为 了引导 QR 码识别设备来识别数据编码区的编码内容，功能区本身不包含任何与编码内 容的数据，它存储的数据主要包含了位置探测图形的编码信息、分隔符和定位图形的编 码的编码信息等。数据编码区则包含了 QR 码全部的数据内容，它里面的内容主要是版 本信息的编码、格式信息的编码、数据的编码以及纠错码字的编码等。 编码的流程如图 3.1 所示： 图 3.1 QR 编码流程图 数据分析是对得获取的字符串类型进行分析处理， 根据不同的类型采取不同的编码 步骤。数据编码是根据数据分析得到的结果来对不同类型的输入数据进行二进制编码， 得到一个由 0 和 1 组成（对应实际的黑白模块）的二进制位流。 纠错编码与构造码字块实现了对 QR 码的自我纠错功能，它核心算法依靠了 R-S 前 向纠错编码。其实际意义是当识别到残缺或遮挡的 QR 码时能够通过纠错功能一字不漏 地恢复原有的编码信息。 掩模处理使得编码时不让黑色块和白色块过于密集地集中在一片区域上，提高了 QR 码的可靠性。 QR 码的格式信息与版本信息是译码时必须依靠的内容，只有在编码区适当的位置 加入正确的解码信息才能快速、高效地对二维码进行译码。格式信息与版本信息对解码 非常重要，所以必须保证它们能够准确地读取，因而它们在添加时必须考虑各种妨碍自 身读取的因素，所以它们都在整个编码区域出现两次，以此保证读取的准确性。 桂林电子科技大学毕业设计（论文）报告用纸 第 5 页 共 51 页 3.1 数据编码的生成 二维码的数据编码包含了输入字符串的全部信息，生成步骤分为数据分析、数据编 码、纠错码字序列的生成和构造信息等几个基本的操作。 3.1.1 数据分析与编码 QR 码为了增加在不同情况下表示的字符数量，将输入的数据流分为了几个类型。 在进行数据编码之前，首先应该分析所输入字符串数据的类型，不同的字符类型按照不 同的编码方式进行编码， 这样可以高效地将输入的数据字符串转换为最小长度的二进制 位流，从而节省编码空间。 在输入字符串中，字符串的类型可分为从全为数字的字符串、全为数字加大写字母 字的符串、全为汉字的字符串等等模式。从数字到汉字，每种模式中单个字符的编码所 需的二进制的位数（也就是数据量）逐渐增加8。所以，在实际 QR 码的编码中可以通 过改变不同模式使数据的位流长度变得更短。由于随着 QR 码版本变大，能存储的数据 容量并不是线性连续地增加， 所以有时候不需要在任何情况下都要达到很高的编码转换 效率。下面是各个模式编码的主要特点： 数字模式： 得到的字符串全部是 10 进制的数字 09 时就为数字模式， 它的表示采用对应二进 制数表示 3 个实际的数字字符，二进制数的长度为 10 位。 字母数字模式： 包括了 45 个字符集的编码值，即包含数字 09，26 个大写字母 AZ 以及 9 个常 见字符。通常，输入的每两个字符用一组二进制数来编码，二进制数的长度为 11 位。 8 位字节模式： 它能表示全部的 ASCII 字符集（ASCII 值为 00HEXFFHEX 之间的字符），编码 时直接用 8 位二进制位流表示每个字符。如果使用 28 位二进制这种模式，它可以直 接编码全部的汉字、大小写英文字母和一些特定的字符。 根据输入的数据对应不同数据编码模式，可将数据按照对应的模式转换为一个位 流，在位流之前在加上一个或多个不同的模式段来标明这个数据串的编码模式。这样， 识别时就能按照不同的模式识别出不同的编码字符集。 模式段的编码从位流指定符的最 高位开始，以位流指定符的最低位结束。 剩下位流中其余部分的每一段均由一个 4 位的位流构成， 这个 4 位二进制编码由编 码位流、长度个数信息以及模式信息这几部分的位流组成。每个模式段的开始都是具体 编码指示符表示的最高位，最后以数据位流表示的最低位终止。每个模式对应的指示符 的表示和不同模式下 QR 码的字符计数的表示如表 3.1 和表 3.2 所示： 桂林电子科技大学毕业设计（论文）报告用纸 第 6 页 共 51 页 表 3.1 模式指示符 模式对应的二进制表示 ECI0111 数字0001 字母数字0010 8 位字节0100 终止符0000 表 3.2 不同模式的字符计数指示符长度（位） 版本数字模式字母数字模式8 位字节模式 191098 1026121116 2740141316 为了方便解码时确定信息位结束的位置，整个编码信息的位流的结束需要由一个特 殊的终止符“0000”表来示，当 QR 码编码后数据位流所余的位数为 0 时，它可以省略 掉，不够 4 位时，这个终止符会被适当地缩短成 1、2 或者 3 位。需要注意的是，终止 符自身并不表示某个模式的指示符，它仅仅用于表示位流的终止。 经过数据分析之后，就可以根据输入字符串的类型按照不同的模式进行数据编码， 按照 QR 码本身的规定，不同的编码模式对应不同的编码方法，在一定程度上节约了编 码所需的位数（也就是 QR 码黑色块与白色块的个数），这样可以更有利于加快 QR 码 的生成与识别速度。 如果输入的字符串全部是数字，则按数字模式进行编码。方法是将输入字符串（这 个字符串必须全部为阿拉伯数字）的每 3 个数分成 1 组，然后将每组的 3 个数看成一个 由个位、十位和百位组成的 3 位自然数，再将这 3 个 10 进制数编码为 10 位的二进制位 流来构造编码信息。如果字符串中字符的数量不是 3 的倍数，编码后会剩余 1 或 2 位， 剩余的这 1 或 2 位也要继续编码为对应的位流。如果还剩下 1 个，那么将它转换成 4 位 二进位流，如果剩余 2 位，那么将它转换成 7 位二进位流。全部转换后，将这些一片片 二进制数据连接起来形成一长串的数据流， 然后在这个数据流前面加上字符个数信息和 模式指示符即可完成对纯数字的编码。数字模式中位流的长度计算公式为： (3-1) 其中： B=总字节位流的位数； C=字符个数信息的位数； D=输入数据的字符个数； R：当 D/3=0 时，R 为 0；当 D/3=1 时，R 为 4；当 D/3=2 时，R 为 7。 如果输入的每个字符都属于表 3.3 中的字符，则按字母数字模式进行编码。首先， 按照表中各个字符与值的对应关系，得到每个输入的字符对应固定的数值，这个数的值 为 044 之间任意整数，如表 3.3 所示： RDCB)3/(104 桂林电子科技大学毕业设计（论文）报告用纸 第 7 页 共 51 页 表 3.3 字母数字模式编码/译码表 得到对应的整数值后，将这一串整数值分为每两个一组，然后用 11 位二进制位流 编码每组的两个数据。编码方法是将每组的第一个值乘以 45 与第二个值相加，然后得 到它们的和，再将这个和转换为 11 位的二进制数即可。如果输入字符串的个数不为 2 的整数倍， 那么编码后会剩下一个数据， 需要将剩余的这个字符转换为 6 位的位流信息。 最后，与数字编码模式一样，将这些二进制数据连接起来形成数据流，然后在这个数据 流前面加上字符个数信息和模式指示符。 在此模式中，字符个数信息有 9、11 或 13 位，如表 3.2 所示。数据字符个数信息编 码为位流信息后，也要增添到模式指示符的后面。 最后得到字母数字模式的编码的长度： (3-2) 其中： B=总字节位流的位数； C=字符个数信息的位数； D=输入数据的字符个数； E 是剩余的位，为 D 除以 2 后的余数（0 或 1） 。 如果输入的每个字符属于上面两种模式之外， 则按8位字节的方式进行位流的转换。 在这个模式里面，一个编码位的 ASCII 字符值直接由一个 8 位的位流表示，它能表示所 有的字符（包括汉字），编码的格式为每 8 位二进制数表示每个字符，其编码空间消耗 大于前面的两种编码方法。ASCII 具体字符的值可在其它文献中参考对应的ASCII 字 符集编码/译码表。 与前两种模式相比，八位字节模式的编码比较简单，它直接将每个字符对应的二进 制信息连接起来形成数据流， 并在前面加上字符个数信息和模式指示符即可。 不同的是， 这个方法的编码位数是用 8 位或 16 位表示。最后，也需要将得到的字符个数编码为 8 位或 16 位位流信息才能放在编码位流序列之前，或者模式指示符的后面。 除了以上这 3 种编码，QR 码还支持独有的汉字模式、混合模式和 FNC1 模式的编 码。混合模式和 FNC1 模式的存在是为了解决编码密度的问题，其基本思想是在编码过 程中充分利用模式进行混合编码，专业来讲就是位流长度的优化。在生成时要根据具体 EDCB6)2/(114 桂林电子科技大学毕业设计（论文）报告用纸 第 8 页 共 51 页 输入的字符串选择最好的模式，对于可以采用不止一种模式来表示的数据编码，在编码 之前必须进行模式的选择与判断。在生成数据流的过程中也可以进行不通模式的切换。 对于一段已经给定的字符串， 表示每个数据字符的最小长度的方案并不一定是最佳 的编码方案。如果要求压缩比率更高，则需要考虑改变模式所添加的位数（这个位数包 括了字符个数信息和增加的模式指示符）。倘若使码字数最小化，也要使整个 QR 码的 区域全部充满表示的位流，添加的数据来自特殊的填充信息。 混合模式具体的编码方法是先得到每一段数据编码模式， 然后根据每种模式进行分 段编码。这种方法的表示格式分为 3 部分：模式指示符+字符数量+具体位流，其后接着 下一部分的编码，如表 3.4 所示： 表 3.4 混合模式数据格式 段 1段 2段 n 模式指 示符 1 字符个 数信息数据 模式指 示符 2 字符个 数信息数据 模式指 示符 n 字符个 数信息数据 因为混合模式编码效率的提升不是很明显，而且采用 8 字节能编码全部的汉字，本 设计在设计源码时对混合模式没有进行进一步的实现。 3.1.2 纠错码的生成 QR 码很容易在使用途中受到污染、涂刮等形式的损坏，这将直接影响 QR 码的识 别，所以使用好的误差检测和校正算法显得尤为重要。目前，使用最广泛的纠错算法是 R-S（Reed Solomon）前向纠错控制码算法。作为一种重要的循环码，它是各种纠错码 中纠错性能最强大编码之一，这个纠错码可以用来纠正最多 30%的错误。然而，R-S 编 码以及解码的过程复杂， 本文对 R-S 序列算法在二维码中的实现这方面的学习不是很深 入。 在编码位流的结束位置增添 R-S 编码算法编码得到一长串纠错码字， 可以让二维码 在遇上涂刮或者污染时能够顺利地完成解码。 在实际的生成过程中采取 4 个梯度的纠错 编码来对数据编码进行纠错化处理，这 4 个梯度对应了 4 个纠错等级，分别用 L、Q、 M 和 H 来表示。 在生成之前， 用户应根据实际的需要选择不同的纠错等级来生成 QR 码。 从 L 到 H 这几个等级中，它们所对应的的纠错和检测的纠错容量容量不断增加，当然， 这会必然增加最终编码位流的长度，也就是增加了 QR 码的版本。在不同情况下，应按 照如下的因素考虑纠错等级的使用： 1.实际 QR 码的识别质量的需求，质量需求越低，纠错等级就越苛刻； 2.在识别时第一次扫描成功的概率； 3.扫描失败后第二次扫描的几率。 在实际应用中，最低的纠错率等级“L”的编码的纠错容量在 7%左右，它在比较适 用于要求使用表示给定程度字符串的生成最小的编码尺寸或者对质量要求比较高的 QR 桂林电子科技大学毕业设计（论文）报告用纸 第 9 页 共 51 页 码的情况。中等纠错等级“M”可以看作是一个比较合适的等级，这种纠错率生成后具 有较小的尺寸和较好的可靠性。纠错等级“Q”为拥有比较高的可靠性的等级，它适用 于那些比较重要的 QR 码的生成而且生成图片质量差的场景中，纠错等级“H”是纠错 率最高的容错编码方式，它可以实现接近 30%左右错误信息的恢复。 采用纠错码字可以实现还原的错误有两种： 一个是拒读错误， 另一个是替代错误9。 对于出错位置是确定的错误归为拒读错误， 发生错误位置是不确定的错误类型归为替代 错误。当识别到一个无法解码的信息位时，这种状态就是拒读错误，而替代错误指的是 错误地将原来固有的位流错误地还原成另一个码字的情况。 如果在实际中存在不确定的 因素破坏了 QR 码中某一部分，使得原来的深色的点变成了浅色的点或者白色的模块变 成了黑色的模块，那么在识别时必定会造成位流 0 和 1 的误判，从而造成解码的信息与 编码的字符不一样，这就属于替代错误。这样的数据替代错误的纠正需要 2 倍的纠错码 字来实现，它们之间的数量关系如下： (3-3) 其中： e=拒读错误数； t=替代错误数； d=纠错码字数； p 为错误检测码字数。 当二维码的版本为 1 且纠错等级为 L 时，p 为 3；当版本为 1 纠错等级为 M 时或者 版本为 2 纠错等级为 L 时，p 为 2；当版本为 1 纠错等级为 H 时、版本为 1 纠错等级为 Q 或者版本为 3 纠错等级为 L 时，p 为 1；其余情况的 p 都为 0。在实际纠错的应用中， 如果 p 大于 0（为 1、2 或 3）时，将有 p 个码字当作错误检测信息，这是为了防止数据 本身错误的数量大于纠错码字传输的数据量。还有，e 不能比 d/2 大。 根据实际的 QR 码纠错等级和版本，将输入的数据字符串分为一个或多个的块，运 用纠错算法对每一块进行纠错编码处理。如果某一 QR 码实际输入字符串的编码长度不 符合当前版本所能容纳的字符串编码长度， 那么就需要在编码串后面补上剩余位使得整 个编码区域都存在编码信息，补上的位均为 0。纠错码字就是利用纠错码对应的系数多 项式来除以数据码字得到的余数信息，不同的纠错码字将得到成不同的纠错码多项式。 上面所述的各种纠错等级下数据的纠错比率只是一个近似值。比如 QR 码的版本为 6，纠错等级设为 H 时，编码总共需要 172 位，纠错码字使用 112 位（数据码字是余下 的 60 位）。其中的 112 个纠错码字可纠错 112 个拒读错误或者 112/2=56 个替代错误， 那么得到这种二维码的实际纠错百分比就是 56/172=32.6%，这并不是纠错率为“H”所 规定的 30%的纠错容量比率。 pdte2 桂林电子科技大学毕业设计（论文）报告用纸 第 10 页 共 51 页 3.1.3 构造最终序列 因为在版本数以及纠错等级确定的情况下所能编码的字数是确定的， 所以最终编码 位流中码字的数目应等于相应的版本和错误校正级别下所能编码的字数。 但实际的输入 的字符串长度并不一定符合，为了解决这个问题，应先根据具体的纠错等级和版本将输 入的数据字符串序列分为 n 个小块，对每小块分别构造成相应的纠错码字，最后按照顺 序将纠错码字和每一块的数据装配成最终的位流。 装配的规则是在位流的最前面位流数 据块 1 的编码信息， 然后接上数据块 2 的码字信息直至 n 个数据块的末尾码字的信息。 接着，加上纠错块 n 码字的全部信息。所有数据块的内容加上纠错码块的内容必须要刚 好填满整个 QR 码的编码区。但是大多数情况下输入的字符串往往不能正好地匹配上编 码区的长度，这就需要在编码末尾添加一定长度的剩余位，剩余位全部是 0，长度为 3、 4 或 7 个。这样，得到的编码数据的长度与编码区域位流的长度一样。 在拼接最终的序列块的时候， 序列的最前面应存放最短的编码块之后才能编码相应 的纠错码字块，换句话说，就是第一个纠错码字的前面应编码所有的数据码字。 3.2 整个符号的生成 3.2.1 功能模板的布置与掩模处理 根据实际要求的容错等级和输入的编码字符串， 通过判断字符串的长度以及计算对 应的纠错码字的长度，就得到所需编码输入字符串的 QR 码版本。每一个版本对应不同 的空白正方形区域，版本越高，区域的规模越大。这些空白的区域包括了寻像符号、定 位符号、分隔模块以及校正图形，它们分别放置在固定的区域上。在没完成编码之前， 版本信息模块和格式信息模块的编码暂时是空白的， 而且它们不同的版本对应模板的长 宽都是不一样的，版本为 2 的 QR 码模块的摆放如图 3.2 所示： 图 3.2 版本 2 的 QR 码符号字符摆放 将输入字符串生成的序列位流按照一定的格式分为若干个 8 位的二进制信息块后， 每块信息块又可分为不同的形状， 每一块按照一定的原则编码到 QR 码的数据编码区中， 并且按照一定的顺序摆放。具体的的布置原则为： 第一个码字块从编码区的右下角开始摆放，第二个码字块在第一个的上面，当码字 块排到编码区的顶部或者底部时，便扭转放置的方向向下一列进行交替进行排列，直至 桂林电子科技大学毕业设计（论文）报告用纸 第 11 页 共 51 页 数据码字块与纠错码字块全部放置完毕（如图 3.2 中码字块的顺序所示）。 每一个码字块中的最高位（位 7）放在块中第 1 个位置，次高位放在第 2 个位置， 直至放满全部位置。位置的序号从小到大左右排列，如果下一个码字块在前一个码字块 上面，则块中最高位位于右下角。反之，块中最高的位放置在右上角，如图 3.3 所示： 图 3.3 QR 码符号字符的摆放 3.在每一小块位流的排列时如果遇到定位图形或者校正图形某个边界时，编码区是 可看作是连续的，直接绕过图形的上边界或下边界继续摆放。 4.如果遇到整个二维码的边界、格式位流、版本位流或分隔模块的交界处时。按照 图 3-4 所示，将码字中没有摆放的位需要改变方向摆放在左侧的纵列中。 图 3.4 方向改变的符号字符位置 5.如果数据位流的右端遇到版本信息或者校正符号固定的位置时，位流的位置要沿 着相邻占用的区域延伸形成不规则排列的符号字符。 如果前一个字符块已经放置完 8 个 信息位时位流还没越过占用区域， 则下一个字符块的首位继续单列摆放。 如图 3.5 所示： 图 3.5 临近校正图形的位置布置 除了上面所述的规则之外，还有一种相对简单的模块布置方法，这种方法也能得到 一样的结果。将输入的数据码字块信息和纠错块信息看作是一个很长的位流，然后从这 个位流的最高位开始按照两个模块宽的纵列开始交替地布置，方向是从右到左、向上或 者向下的方向。这样就可以轻松地越过一些固定的占用区域，然后在 QR 码编码区的顶 部或底部相应地改变方向。 桂林电子科技大学毕业设计（论文）报告用纸 第 12 页 共 51 页 当整个编码区的容量不能正好分为 8 位符号字符的整数倍时， 也需要在编码末尾添 加一定长度的剩余位，剩余位的长度为 3、4 或 7 个。添加掩模之前，这些剩余位的值 全都是“0”。 为了增加 QR 码识别读取时的可靠性，应该防止编码时黑色块和白色块过于密集地 集中在一片区域上，那就需要编码时均匀地在编码区上合理地摆放每一个黑白信息位， 而且还要避免出现类似其它功能图形的黑白块， 特别是行或者列的黑白块以 1011101 这 种形式出现，那就与位置探测图形的行和列一致（见图 2.2），这肯定会造成在解码识 别时对位流的误判。 这种问题的一个非常有效的解决办法就是对整个编码区进行掩模操作， 利用一定规 则的模板对原有编码区进行异或运算操作， 好处是可以使得这些黑白块过于密集地集中 在某一片区域上。缺点是在识别时需要去除掩模模板，增加了运算量，但是对于某些色 块特别集中的情况来说，掩模处理并非得不偿失。所以，无论编码时色块是否集中都应 该进行统一的掩模操作。 具体的掩模步骤与原则为： 不能对功能图形进行掩模操作（包括寻像块、校正符、分隔符、定位符等）。 采用某个位流对数据位流和纠错位流的存放区间（版本位流和格式位流除外）进行 异或操作，掩模模板的大小必须和被掩模的数据信息区域的大小一致，使得数据码块和 纠错码块的编码区域能够比较均匀地分布黑色块和白色块。 异或操作指的是掩模模板对 数据信息区域上每一点的运算， 运算规则是当数据区域的色块与掩模模板的色块相同时 （两个模块都是黑色或者白色）结果得到白色模块，色块不同时结果为黑色块。 为了得出最好的掩模效果，掩模的模板应不止一个。根据计算每一次掩模后的色块 密集度以及对功能图形影响的程度赋予一个评分， 根据评分的大小选择最好的掩模效果 的模板来使用。 每一个掩模的模板的生成都有一定的规则，各种掩模生成的办法如表 3.5 所示，其 中 i 和 j 分别代表模块的行和列位置。具体生成的掩模图案见附录 3。 表 3.5 掩模图形的生成条件 桂林电子科技大学毕业设计（论文）报告用纸 第 13 页 共 51 页 按照以上几个原则，得到的掩模过程如图 3.6 所示： 图 3.6 QR 码符号的掩模过程 在运用全部的掩模模板对未掩模的 QR 码进行一一掩模操作之后，需要选出掩模效 果最好的掩模图形。具体选择办法是对每一次掩模过程进行计分操作，以便对每一个结 果进行评估， 评估是采用权重的方式对每种掩模结果进行计分。 评分标准如表 3.6 所示， N1 到 N4 为每种情况所占权重的值（N1、N2 为 3，N3 为 40，N4 为 10），i 为模块中 相邻的色块相同的点数大于 5 的次数，k 表示黑色块占总色块的比率与 50%之差。 表 3.6 掩模结果的计分标准 特 征评价条件分数 行/列相邻模块的颜色相同模块数=(5+i)N1+i 一样颜色模块的数量块尺寸=mnN2(m-1)(n-1) 在行/列中出现 1:1:3:1:1 的图形N3 整个 QR 码中黑色块的比率50(5K)%50(5(K+1)%N4K 经过上表的规则计算处理后，掩模效果会得到一个具体的数值。这个数值代表着掩 模结果的评价，它越大说明在进行的这次掩模过程中符合表 3.6 中所述的特征数量多， 总体表现为掩模的质量差。为了使 QR 码的阅读识别具有一定的可靠性，最后应采用得 分最小的一个掩模条件用于 QR 码的最终掩模。虽然掩模操作仅对数据码块与纠错码块 的编码区域有效，但是掩模的评价是采取了整个 QR 码的有效区域来计算的。 3.2.2 添加格式与版本信息 二维码中的格式信息表示为 15 位的连续位流，实际的格式位占用了其中前 5 位。 由于纠错的需要， 余下的 10 位是经过纠错算法编码计算得到的具有纠错功能的序列位。 前 5 位中，QR 码的纠错等级用前两个位表示，这两个位的 4 个值分别表示着不同的纠 错等级，如表 3.7 所示。位流的 35 位用来表示掩模图形对应的 8 个值，具体值见表 3.5。 桂林电子科技大学毕业设计（论文）报告用纸 第 14 页 共 51 页 表 3.7 式信息中纠错等级的表示 纠错等级LMQH 对应二进制01001110 具有纠错功能的 10 个序列位是为了防止扫描格式信息出错时提供纠错的功能。识 别完前 5 位格式信息后， 需要根据后 10 位提供的信息检测识别到的格式信息是否正确。 这 10 位纠错位的计算过程是以原来 5 位格式信息的数据为基础， 建立一个系数多项式， 然后被一个固定的多项式 H(x)=x10+x8+x5+x4+x2+x+1 所除， 结果会得到一个剩余多项式。 将这个剩余多项式的 10 个系数追加到前 5 位格式信息上形成 15 位二进制字符串。 与数 据编码区一样，格式信息的位流也要进行掩模处理。掩模统一采用“101010000010010” 这个二进制字符串模板对格式编码的 15 位进行异或处理，这样可以使得纠错信息与掩 模信息相加成的 15 位编码位流不都是 0。 例如：纠错等级为 M（二进制 00），掩模版本为 101 的（二进制 101）格式信息的 计算过程如下： 合成到的二进制串为：00101 对应多项式表示：x 2+1 提升多项式次幂：x 12+x10 被 H(x)除后等于：(x 7+x6+x4+x3+x2)+(x10+x8+x5+x4+x2+x+1)x2 得到前面的系数为：0011011100 附加到格式信息后面：00101+0011011100001010011011100 异或运算结果：101010000010010 XOR 001010011011100 100000011001110 计算得到的结果 100000011001110 就是上面格式信息最终的结果， 将此结果直接放 入格式信息区即可。格式信息在 QR 码的位置是固定的，而且它的准确解码对整个 QR 码编码区数据的解码十分重要。为了防止实际不确定性因素的干扰，它的信息在 QR 码 的格式编码区出现两次。15 个格式信息位对应的位置如图 3.8 所示： 图 3.8 格式信息各个位在 QR 码中的位置 版本信息只出现在版本 7 以上的 QR 码的编码区中， 剩下的版本信息全部用 0 表示。 在低版本的 QR 码中识别得到的版本信息全为 0，所以不需对版本信息作掩模处理。版 桂林电子科技大学毕业设计（论文）报告用纸 第 15 页 共 51 页 本信息的表示为 18 位二进制数，实际的版本信息位占据了其中前 6 位。由于纠错的需 要，剩下的 12 位也是经过纠错算法编码计算得到的具有纠错功能的序列位。 12 位纠错序列的计算过程类似格式信息后 10 位纠错位的计算过程，以原来 6 位版 本信息的数据为基建立一个系数多项式，然后用 H(x)=x12+x11+x10+x9+x8+x5+x2+1 来除 它，得到一个系数多项式。将这个剩余多项式的 12 个系数追加到前 6 位格式信息上形 成 18 位二进制字符串。 例如：版本 7 的版本信息位流计算过程如下： “7”的二进制串：000111 对应多项式表示：x 2+x+1 提升多项式次幂：x 14+x13+x12 被 H(x)除后等于：(x 11+x10+x7+x4+x2)+(x12+x11+x10+x9+x8+x5+x2+1)x2 得到前面的系数为：110010010100 附加到版本信息后面：000111+110010010100000111110010010100 得到的版本信息位流被放置在 QR 码编码区中版本信息的编码位置，这个位置是固 定的。而且它的准确解码也是对整个 QR 码的解码十分重要，为了防止干扰，它在 QR 码的格式编码区中也出现两次。 包括数据位和纠错位的 18 位版本信息被编入 36 个格 子的版本信息编码区中，版本信息各个位对应的位置如图 3.9 所示.根据图 2.1 可知，图 3.9 中左边 6 行3 列的版本信息位流被编入整个 QR 码左下角位置探测图形的上面， 图 中右边 3 行6 列的信息将编入右上角位置探测图形的左边，而且紧靠着各自对应的分 隔符。 图 3.9 版本信息的模块位置布置 3.2.3 编码区与功能区的整合 经过对编码区和功能区分别进行了编码操作后， 就可以将这两个区域的内容整合起 来形成最终的 QR 码。 按照国家标准，在 QR 码的编码区和功能区之外的周围应留有一段空白区，便于识 别，空白区的宽度尺寸为 4 个模块。加上 4 个模块的空白区后，从用户输入一段字符串 到生成 QR 码整个流程到此结束。 除此之外，QR 码还有一个功能，就是支持结构链接。结构链接可以将一个复杂的 二维码转换为很多（最多达 16 个）小的 QR 码，识别时根据固定的链接方法的对每个 小的 QR 码进行一一识别，然后分别对每小段 QR 码的信息拼接起来，这样就形成了最 桂林电子科技大学毕业设计（论文）报告用纸 第 16 页 共 51 页 终的复杂的信息。 结构链接使得 QR 码能表示的信息容量大大提高，特别是对复杂信息的表示。其缺 点是识别时比较耗时，而且其中一个小 QR 码识别失败会导致整个信息的连接失败。 由于结构链接需要涉及的技术问题较为深入， 它在具体的编码时除了有对应的模式 指示符，还有序列号指示符，奇偶性数据的计算等一系列的复杂过程。而且有明显的优 缺点，目前国内外暂时也没有对 QR 码结构链接编码的统一规定，本设计还没有对 QR 码的结构链接进行深入的学习。 桂林电子科技大学毕业设计（论文）报告用纸 第 17 页 共 51 页 4解码过程 4.1 解码流程 编码就是为了解码，解码可当作是编码的逆向操作10。编码是按照一定的步骤将输 入的一串字符生成一个二维码矩阵，解码则根据编码了 QR 码信息的一幅图或者一个矩 阵来读取相应的编码数据。解码流程如图 4.1 所示： 图 4.1 解码流程图 解码之前应对输入的图像矩阵进行预处理。 然后对预处理后的矩阵根据 3 个位置探 测符号得到二维码在图片矩阵中的方位以及编码格式区的边沿。 去除边沿以外不必要的 信息后得到了整个编码区的图像信息， 预处理后就能开始对图片进行每个模块进行 0 与 1 的采样操作了。 桂林电子科技大学毕业设计（论文）报告用纸 第 18 页 共 51 页 识别黑白模块是对只含编码信息的图像矩阵进行映射处理，映射结果将得到只由 0 和 1 组成的原始数组，这个数组的数据应与生成时最终位流数组的数据是一样的。通过 这个数组，可以能读出相应的格式、版本以及掩模的模板信息。 根据读到的这些信息我们对原始数组进行掩模的消除后就得到了数据码字和纠错 码字，然后利用纠错码字来逐一检查数据码字的错误，这样就能还原没有错误的数据码 字。最后，对纠错后的数据码字按照不同的模式来译码就能解码出相应的字符串。 4.2 解码具体过程 按照编码理论的逆过程对这个数组进行格式、版本等信息进行恢复，根据恢复得到 的格式信息里面的版本数和掩模图形的代码对数据码字块和纠错码