二维码识别与检测算法的研究与实现

天津科技大学 2014 届本科生毕业设计1二维码识别与检测算法的研究与实现RESEARCH AND IMPLEMENTATION OF TWO-DEIMENSIONAL CODE RECOGNITION AND DETECTION ALGORITHM专 业： 网 络 工 程姓 名： 王旭迎指导教师姓名： 申请学位级别： 学 士论文提交日期： 2014 年 6 月 3 日学位授予单位： 天 津 科 技 大 学天津科技大学 2014 届本科生毕业设计2摘 要当今社会信息逐步网格化，计算机技术飞速发展，人们接触到的信息传递媒介越来越多。从传统老式的纸质媒介，到现在丰富多彩的电子媒介。新型条形码技术的出现，立即在人们的生活中占据了重要的地位。条码技术发展的早期只拥有具有横向存储数据能力的一维条形码，虽然其在一定程度上解决了工业和商业领域的部分问题，但作为数字传递的媒介其完整的应用需要借助网格和数据库来支撑，这样的数据容量局限则阻碍了它的普及。由此，二维码相关技术应运而生。它按照一定的规律，在平面的黑白相间的图形中，用特定的几何图形记录数据符号信息。二维条形码具有特殊的横向纵向双向存储能力，使人们摆脱了借助大量设备情况下传递信息的弊端，最有力的解决了数据容量问题。本文研究的二维码的识别技术与检测算法是用 C#程序语言编写的，其中引用了 ZXing 可实现多种格式 1D/2D 条码图像处理库，并运用了 Visual Studio 2012 作为开发工具。ZXing 库针对不同格式的条码先采取相同的图像处理，如翻转、定位等，与此同时也针对不同型号条码各自特点制定了不同的算法进行解码。本文主要针对 QRcode 进行识别，经研究发现 QRcode 采用了里德所罗门算法进行编码，里德所罗门是一种带有容错机制的编码方法。该设计实现了QRcode 的旋转图形校正、利用位置探测图形进行定位、格式信息确定类型、版本信息确定级别，最终实现整个二维码的解码识别，我更针对其算法实现了编码功能，可随意制作自己想要的 QRcode。首先要解了二维码在生活各个领域的应用，更加深入的学习二维码数据容量大、可靠性高、可支持多种纠错级别的特征。可以针对国际标准文件所包含的“ISO/IEC 15416 信息技术- 条码印刷质量次测试规范”条文，更好的将二维码的便利特征应用到工业印刷检测中去。研究明白二维码的解码编码原理后，可以更好的将其拓广到社会的工业和商业界。关键词： 二维码的识别与检测； Reed-Solomon 里德所罗门纠错算法； QRCode 二维条形码天津科技大学 2014 届本科生毕业设计3ABSTRACTAlong with the modern society of information grid, the computer technology high speed increase, people come into contact with the media of information transmission is more and more. From the traditional paper media old, to now rich and colorful electronic media. The new bar code technology, immediately occupied an important position in peoples daily life. The early development of bar code technology has only one-dimensional bar code with transverse data storage capacity, although it solves some problems of industrial and commercial fields in a certain extent, but as a digital transmission media used the complete needs the help of grid and data to support, data capacity limitation of this kind of hindered its popularization. Thus, emerge as the times require two-dimensional code technology. It according to certain rules, in the plane of the black and white graphics, with specific geometric figures recorded data symbol information. Two-dimensional bar code with transverse longitudinal bidirectional storage capacity special, make people get rid of disadvantages of large equipment by means of transmission of information under the condition of the most powerful, to solve the problem of data capacity.This paper studies the two-dimensional code recognition and detection algorithm is to use the C# programming language, which cited ZXing can achieve a variety of formats of 1D/2D barcode image processing library, and uses Visual Studio.NET2012 as development tool. The ZXing library for different formats of bar code image processing to take the same, such as turning, positioning, at the same time, according to their characteristics of different types of bar code made different algorithms for decoding. This paper mainly recognition for QRcode, the study found that QRcode uses Reed Salomon algorithm code, Reed Salomon is a fault tolerant mechanism coding method. The design and implementation of the rotating graphics QRcode correction, detect image positioning, the position determination level type, version information format information, realize the decoding the two-dimensional code recognition, I according to the algorithm of the encoding function, can make you want to QRcode.Keywords: Identification and detection of two-dimensional code ; Reed Solomon correction algorithm ; QRCode two-dimensional bar code天津科技大学 2014 届本科生毕业设计4目 录第一章 绪论1第一节 条码技术第二节 条码的种类第二章 二维码第一节 二维码的起源和简介第二节 二维码技术的研究现状第三节 一维码与二维码的比较第三章 QR Code 技术简介第一节 QR 码相关简介第二节 QR 码的结构第三节 QR 码的图形定位与扫描第四节 QR 码的码制规范第五节 QR 码的特征第六节 QR 码的实际应用第四章 Reed-Solomon 算法基础第一节 RS 纠错译码的概念第二节 伽罗华域的简介第三节 循环码的简介天津科技大学 2014 届本科生毕业设计5第五章 QR Code 的识别算法及原理第一节 QR Code 的编码过程第二节 QR Code 的译码原理第三节 QR Code 解码中的关键问题第六章 QR Code 识别系统的实现第一节 设计平台的相关介绍第二节 QR 编码的程序设计第三节 QR 解码的程序设计第七章 总结与展望第一节 总结第二节 展望参考文献致谢天津科技大学 2014 届本科生毕业设计6第一章 绪论在我们的生活中随处可见计算机信息系统，高新的网络技术已深入到了各行各业领域组织结构，尤其是在商业、工业等方面，发挥了有效的控制与极大的协调作用，必然成为我们生活中不可或缺的一部分。比如公司企业的相关管理阶层需要及时获得相关最新动态，就必须缩短相对信息接收处理周期，这也就要求我们必须解决所获有用信息输入问题。通过采用高效高能的传感技术输入所获信息，能够令人为输入的数据速度与机器处理信息速度相匹配，这才是管理信息所要达到的高效处理必选方式。经过这十几年的实践应用，条码技术不断发展和完善起来，现如今已成为人们工作生产和点滴生活中使用最为普遍最为广泛的自动识别技术。我们所熟知的条码技术是在通信技术、计算机技术和编解码技术基础之上发展起来的综合性科学技术。大众所了解的条码现在已种类繁多，最广泛的分类就是一维码和二维码。由于一维条码具有横向存储数据能力，并且需要借助大型网络和数据库提供支撑，狭小的数据容量局限，无法使之满足实际应用的需求，由此便产生了二维码，在一维条码的基础上逐渐发展起来。其纠错能力强、可防伪、数据存储量大、安全可靠性高、保密性强、成本低、高密度等特点，更是慢慢替代了一维条码的使用，并受到了人们的广泛关注。二维条码的使用，极大地提高了工作效率，实现了高速数据采集和信息处理。本章节主要对条码技术的发展进行简要阐述，介绍其发展背景和前沿技术。初步了解二维码的基本知识、定义、分类以及国内外研究现状。第一节 条码技术背景与发展计算机信息系统已经全面普及到各个行业领域的组织结构中，发挥了它强大的控制协调功能，节省了很大一部分人力物力。而条码识别技术是将计算机技术、通信技术、光电技术、最重要的是条码理论为一体的自动识别技术。他的出现更加充分发挥了机器的高效性，提高了人们的工作效率。因此，自条码技术问世以来，已在商品流通、银行系统、公司信息管理、广告宣传等众多领域得到极大的应用，已然是当今被大众最为接受的识别技术之一，而在未来的发展趋势下，条码技术也必将在前沿技术中占有一席地位。条码技术的定义是条形码自动识别技术（barcode auto-identification tech）的简称。它采用的是二进制数机器语言，基本数据单元是图像处理中的黑白色“0”和“1” ，将数据单元随机的进行不规则排列组合，从而形成只有 0 和 1 的二进制，数据码流。这类数据流再按照相关的体系规则转换成其他我们常见的图形符号。条码技术可以利用符号编码，实现数据采集，在此基础上还能够自天津科技大学 2014 届本科生毕业设计7动识别，将所获取的信息录入，存储信息等多项功能于一身。我们肉眼可以轻松地从复杂的环境中分辨出这些特殊符号的位置，通过相关扫描识别设备得到翻译解码，从而获取图像背后真正携带的数据信息。条码技术作为一种能够实现数据输入和信息自动读取的手段，很大程度的解决了纯人工对处理大量信息录入的问题，大大增强了管理系统的实效性。根据市场的需求，促成了条码的发展与逐步完善，这都与科学信息化的普及息息相关。除了国际上的统一标准 ISO/IEC18004，很多国家都分别推出了条码的规范化标准，将其应用到实际的工业生产中去，在货物存储、销售和国际运输等众多方面，都凸显了其对信息的高效管理。第二节 条码的种类条码作为存储数据的一种新形式，与其他自动识别技术相同，可针对各种不同的工作环境需要，可以产生完全不同的数十种编码类型。在我们熟知的类型中，常见的有 Coda bar 码、标准 25 码、ITF25 码、Code39 码、Matrix25 码、EAN-13 码、 Code39EMS 等。【Coda bar 码】也称为库德巴码，最主要用来表示医疗卫生、血库、照相馆以及图书情报和物资等自动识别领域。如图所示：图 1-1 Code bar 条码【标准 25 码】图 1-2 标准 25 码天津科技大学 2014 届本科生毕业设计8【ITF 25 条码】一般的条码只有竖条表示数据内容，而交叉 25 码的条与空均表示信息。它有两种单元宽度，每个字符有五个单元组成，两个宽单元三个窄单元。组成一个交叉 25 条码符的个数必须为偶数，出现奇数个的时候则会自动在条码左侧用 0 补位使之变为偶数。条表示奇数位，空则表示偶数位字符。该条码包括的字符集是 0-9。如图所示：图 1-3 ITF25 条码【Code39 码】标准 39 码可以表示数字也可表示字母，在工业、图书馆以及票证的机械化管理应用最为广泛。如图所示：图 1-4 Code39 码【Matrix 25 条码】该条码有一定的限制，只能表示数字 0-9。当采用ITF25 的起始终止符，以及 Matrix25 的编码规范时，则会生成具有特殊意义的中国邮政码。如图所示：图 1-5 Matrix25 条码【EAN 码】是电子数据交换 EDI 的基础，也是目前世界上使用最为广泛的一种商品条码，由国际物品编码协会定制。EAN 码又分为 EAN-13 和 EAN-8 两个版本，日常商品包装上均可见。如图所示：天津科技大学 2014 届本科生毕业设计9图 1-6 EAN-13图 1-7 EAN-8以上介绍的各种不同码制的条码，统称为一维条码。一维条码只具有横向存储数据的能力，也就是通过水平方向来表示数据，纵向的条与空都不表示信息。一维码最大的限制就是数据存储量太小，只能标识商品，不能对产品具体信息进行描述。一维码作为新型电子媒介，必须借助大型网格和数据库为其提供支撑，若在无后台或者受网络限制，人们将无法获取相关内容。为此，人们开始研究，若可以在条码的纵向也能够存储信息，则必然可以增大信息密度，扩大数据包含量。所以，在水平一维的基础上，人们尝试在纵向增加一维，由此，二维码技术应运而生。天津科技大学 2014 届本科生毕业设计10第二章 二维码人们经过多年的努力和深入研究，终于将二维码这种全新自动识别技术广泛应用在了生活各方面。我们可以在证件、追踪、货存盘点等各行各业接触到二维码的应用。二维码的核心技术包括图像预处理、编解码算法、纠错控制技术以及加密技术。第一节 二维码的起源和简介二维码在结构上与一维码相似，都是通过二进制的机器语言“0”和“1”构成，通过深浅两色不同模块组成的图形。理论上讲，通过数学意义上的码词（码词，一种用条空单元所构成的阵列）构成特殊的几何图形，用来表示并存储有用信息。二维码作为一种新型记载信息的载体，它区别于以往老式的电磁信号，采用图形作为载体，从而记录并保存信息。二维码将完全暴露的图形镶嵌在特殊介质中来携带信息。二维码之所以现在如此普及，其最大的优势就是抛弃了强大后台的支持，以最便携式的方式传载丰富的信息，突破了一维码所不能承载的容量限制。它所能够携带的信息量是一维码的几十倍，可以包含工业中产品的生产日期以及厂家信息的功能。与此同时，这样的结构也利于厂家进行商品的防伪标识。基于一维码的发展，二维码是在横、纵两个方向上进行编码与解码的。分布在在二维方向上的黑白图形，记录了数据的符号信息，这正构成了二维码大容量储存和加密机制编码的特点，扩展了它在生活中的应用范围。二维码分为行排式(Stacked Bar Code)和矩阵式(Matrix Bar Code)两种二维条码。行排式也可称为堆积式二维条码或层排式二维条码，它基于一维条码的编码原理，按需堆积成两行或者多行。并且在校验原理和识读方式上的特点也从一维码上继承下来。设备与印刷均与一维条码兼容，随着行数的增加则需要对其进行判定，译码算法和所用软件完全区别与一维码。最为熟知的是：CODE49、PDF417矩阵式则可称为棋盘式二维条码，我们可以看到通过黑白像素在矩形空间中进行不同分布进行的编码。在相应的位置上，可以用方点或者圆点来表示二进制“1” ，点未出现的地方表示“0” ，用点的随意排列组合确定所包含的不同意义。结合了计算机图像处理和组合编码原理，生成了这种新型图形符号的矩天津科技大学 2014 届本科生毕业设计11阵式二维条码码制。最具代表性的矩阵式条码有：QRCode、Data Matrix、Aztec纠错能力是二位码独有的特点。要知道，在真正的生活应用中，复杂多变的外界环境，条码的保存、使用以及运输过程中不可避免的会造成损坏，必然会在识读上造成一定的影响。而二维码的这一特点则使它即使被污染或者整体被损毁一半后，也能够使所携带的信息得到还原，对于一维码来说则不具有此特点。一维码，总是通过本来拥有的校验位来对其译码的正确性进行辨别判断，利用纵向上的条与空的延伸来提供冗余信息。符号表示时，可以明显的看到在条码下方有可供人眼识读的文字标示符。在二维码的图像上一般没有提供人工识别的文字标识，若想要保证在各种状况下二维码都可以得到正确的译码，这就要求设备能够针对编码出现的错误进行自动检测和纠正，通过译码还原得到正确的数据信息。与其他常见的传统数据存储方式相比较，比如我们最常接触到的磁卡、光卡以及 IC 卡，条码在存储方式（包括一维码和二维码）上则具有抗磁力、抗静电的突出优势。对于二维码而言，射频识别系统 RFID 技术是其最大的挑战。二维码技术最大的优势就是基于一维条码技术上，成本很低，而对于 RFID 的推广最大的瓶颈不仅仅在于识读设备是否高端，其芯片的高成本、时不时发出发出识频信号来确定用户所在位置，这不利于保护用户个人隐私则成为它的致命伤。1 第三节 二维码技术研究现状目前，国内外最重视、并且迅速发展的技术就是二维码。自日本 1999 年最初提出二维码技术发展至今，二维码的出现从很大方面改善了人们的生活，提供了极大的便利，促进了现代科技的现代化发展。国外对二维码的研究始于上世纪 80 年代末期，1991 年美国 Symbol 公司，最早提出了 PDF417(便携式数据文件二维码)。与此同时，国际组织也制定了二维条码标准，许多国际组织都分别设有二维码标准制定委员会。这些部门的设立就是为了完成对不同条码的标准化工作。在亚洲，尤其是日韩两国，手机二维码技术已发展到了十分成熟的阶段。在日本，有百分之九十的手机都已经具备了二维码识别功能。在所有的报刊上，基本都印有二维码的标志。人们只要对图像进行拍照扫描，即可获取上网时才能得到的最新信息，如新闻时讯和商场打折信息。由于国外很早就掌握了先进的科学技术，并且较早的最该技术进行研究，正如我们所见，在加拿大、德国等国家，这项技术已应用在了电子凭证类业务、货物管理、增值业务甚至是海关税务以及政府部门报等领域。二维码电子凭证类业务切实应用到消费者市场中，则是对该技术最大的普及。节省了物流费用天津科技大学 2014 届本科生毕业设计12不说，还实现了商品的实时追踪。2007 年，二维码移动票务业务被推广到了日本航空公司。而最贴近生活应用的就是工业生产中的自动化管理。直到上世纪 90 年代国内才开始对二维码技术的研究。在我国，智能手机的普遍率很低，手机像素也极为有限，一定程度上阻碍了二维码的发展。即使经过长时间的市场孕育，但依旧与国际脱节。研究初期，我国只能对国外的技术规范进行采纳翻译，甚至直接将国外的标准作为国家标准。直到 2000 年，我国基于日本研究的 QR 码，颁布了 GB/T 18284 国家快速响应矩阵码标准。虽然我国追随了国际水平也制定了相关准则，但由于国内识读设备依旧无法与国外匹敌，在强大的专利制度下，我们只有通过交付大量专利费用，才能获取代理权。在 2006 年，我国着重于推出了具有自主知识产权的网格矩阵码二维码制标准。2007 年，我国技术人员推出了汉信码，弥补了国外无法支持记录汉字的缺点。从此，证明了我们国人的自主创新能力，并且研究出了能够满足结合本国实际需要的技术标准，使该技术得到了进一步发展。目前，二维码的制码技术已经基本成熟，如果想要充分利用起来，就必须对其所涵盖的信息进行有效的识别。目前。二维码识读的最大难度就在于：1. 二维码的识别最重要的就是对其算法的研究，必须掌握对图形算法的解析，才能还原图像背后所携带的有效信息。这也是我毕业设计所研究的重点。2. 想要获取高质量的二维码图像，这也就对图像采集技术提出了更高的要求。据统计，国际上所能达到的现状是，在实验室设备允许的条件下，在 0.8个像素下对图像特征点进行判断处理。而 2004 年的“中国自动识别技术展览会”上，王寅君（PDF417 创始人）曾声称，国内的识别算法已经可以处理 1.8 个像素。23. 在机器的处理速度和可靠性研究上也有很高的要求。比如，我们总是在超市购买商品时出现产品条形码无法识别出的现象，而针对一维条码，我们可以通过手工输入完成。但二维码携带了大量信息，是无法通过人工进行识读的。第四节 一维码与二维码的比较随着科学技术的提高，二维码在一维条码的基础上逐渐发展起来，二者有很多相似的地方，但也存在一定的差异。相比于一维码，二维码有了很大的改进。下面就针对不同方面的特性将二者进行比较。表 2-1 一维码与二维码的区别条码类型信息密度与容量纠错能力携带信息用途 后台依赖性设备要求一维条 密度低， 可以通 垂直方 一般用 若想要 线扫描天津科技大学 2014 届本科生毕业设计13码 容量小 过校验字符进行错误校验，但不具有纠错能力向不携带任何信息，只有水平方向来对商品进行标识得到完整的应用就必须借助通信网格和数据库为其提供支撑器识读，比如光笔、线阵 CCD、激光枪二维条码密度高，容量大不仅仅具有错误校验更具有强大的纠错能力，可根据需求来设置不同的纠错级别在一维条码横向的基础上，添加了纵向信息，从而导致了可携带信息容量增大除了最基本的对物品描述，还可用于电子凭证类业务、货物管理、增值业务摆脱了对大型数据库和通讯网络的依赖，可以便携的单独应用采用先扫描器对行排式二维码进行多次扫描；而针对矩阵式二维码却只能用图像扫描器进行识读经过上述表格的对比，我们了解了一维码和二维码在属性上的区别，而在工作流程上，而这也存在着很大的区别。很明显的可以看出二维码要比一维码简洁得多。因为它摆脱了必须有强大后台支持的弊端。Comment PK1: 3天津科技大学 2014届本科生毕业设计14两 步 走 一 步 走一 维 码设 备 扫 描 识 别获 取 数 据 ， 在 电 脑 中 检 索在 庞 大 的 数 据 库 中 查 找 匹配 项输 出 需 要 的 信 息二 维 码设 备 扫 描 识 别通 过 解 析 得 到 条 码 原 信息 ， 输 入 电 脑 检 索图 2-1 一维码与二维码的工作流程第三章 QR Code 技术简介第一节 QR码相关简介快速识别矩阵二维码,简称为 QR码(Quick Response)，最早是由日本 Denso Wave公司针对亚洲汉文化环境在 1994年 9月专门研制出来的，意为快速反应，发明者的意图正是希望使携带的内容被快速破解。为在国内得到广泛普及，我国在 2000年颁布了针对快速识别矩阵二维码的国家标准。QR 码是一种支持高速读取的矩阵式二维码，并且支持汉字编码，符合亚洲人汉字的使用习惯，在我国电子商务、海报宣传等领域都得到了广泛的应用。第二节 QR 码的结构正如我们所见，QR 码均为正方形，并且只存在黑白两种颜色。除右下角之外，在正方形的其余三个角都印有三个像“回”字形的小正方形图案。正是这3个小图标，帮助了扫描程序对图像进行准确的定位，改善了一维条码必须对准才能识别的弊端。使用户无论在何种角度进行图片拍摄，都能进行识读，使信息能够给准确解码。二维码的符号结构如下图所见：QR码符号都是由正方形模块组成的阵列，这其中包括编码区域和功能图形区域。功能图形区域包括寻象图形、定位图形、分隔符和校正图形。而功能图形是不能用于数据编码的，整体 QR码符号由空白区包围。天津科技大学 2014 届本科生毕业设计15图 3-1 QR 码的基本结构图图 3-2 QR 码结构中符号注释图 3-3 版本 1 和版本 2 的 QR 码天津科技大学 2014 届本科生毕业设计16图 3-4 版本 6 的 QR 码在看到 QR 码的基本结构之后，我们还需进行细致的了解每个符号的意义，在普通的图形中，每个小图形都有着它不同作用：1. 位置探测图形：是用来对二维码进行定位的。一个完整的 QR 码必然包含三个“回”字形的探测图形。通过这三个特征图形，将就可以确定整个条码的位置与方向。对于每个 QR Code 位置都是固定的，只是大小规格均不同存在差异；由于 QR 码只包含黑白两色，这些间隔的举行快很容易就可以被图像检测出来。2. 校正图形：由于条码的尺寸各不相同，校正图形数量上也会不同。从版本2 以上才会存在校正图形。校正图形是为了处理 QR 码在不平坦的界面上打印，或者由于设备读取时造成的图像畸变时的形状矫正，确定矩阵符号位置，并且同步模块的坐标。3. 定位图形：垂直和水平方向上的图形分别为模块的列与行，那些黑白间隔的小格子如同坐标轴，仿佛定义了网格。其作用就是确定符号版本与密度，提供决定基准位置的坐标。4. 格式信息：含有码字所使用过的各种纠错等级和掩模图形。二维码含有 4种纠错级别，分别是 L、M、Q、H 级。这个区域可以用来进行译码。5. 数据区域：每 8bit 编码一个字节6. 版本信息：暗示了编码指定的版本，也就是指二维码的规格。而在版本 1-6 中是不含有该条特征的。对于 QR 码来说，它则包含 40 种版本，也即是40 个矩阵，从 21x21 到 177x1777. 纠错码字和数据：在该区域中，包含了二维码携带的所有信息，并且专门Comment PK2: 2天津科技大学 2014届本科生毕业设计17用 RS纠错来修正在二维码受损失造成的错误8. 分隔符：上文我们曾说到过，QR 码包含编码区域和功能图形，通过分隔符就可以把分隔开来。分隔符由一个模块宽度构成，并且全部都为浅色模块在综合了以上特征图形后，就真正地完成了二维码的编制，获得而知矩阵进行编码译码。第二节 QR码的图形定位与扫描QR码图形中的三个回型位置探测图形，在条码未发生旋转时，分别位于整个符号的左上、左下和右下角（如图 3-1）图 3-5 位置探测图形而如图所示，我们不难发现可以讲这三个图形视为 3个同心的重叠正方形，分别由 7x7深色模块、5x5 浅色模块还有 3x3深色模块组成。它们之间的宽度比例为 1:1:3:1:1（如图 3-6）图 3-6 探测图形的比例示意图不难发现，这种复合 1:1:3:1:1比例宽度的特征图形在整张图片的其他部位出现的可能性极低，这也就可以讲这种特征作为 QR码的扫描定位特征。故当扫描线被黑白双色有规律的被截成 1:1:3:1:1的时候，就可以认定扫描线穿过了 QR码的定位图形。可考虑到我们设备所获取的图像，不一定是标准的，也就是会存在旋转倾斜的现象。但 QR码的探测图形无论是否发生旋转，都符合上述比例特征。图 3-7 扫描特征天津科技大学 2014 届本科生毕业设计18根据 的国家标准，在扫描的时候参考方法如下：1) 从水平 X 方向上逐行扫描A） 固定纵坐标 Y，在水平方向上画一条横线用于逐行扫描。当扫描线出现1:1:3:1:1 的比例是，则认为穿过了定位图形。而在实际检测中，我们必须考虑生活中各种外界因素所导致的偏差问题，也就是必须允许 0.5 误差的存在。当为 1 的比例系数时，可以存在 0.5-1.5 的偏差；为 3 的比例系数时，可存在 2.5-3.5 的偏差B） 当扫描线穿过定位图形的时候，还应记录下与图形边缘相交的首末交点 A和 B，并且将线段 AB 称作扫描线段并保存。图 3-8 扫描线段示意图2) 在纵向 Y 上逐列扫描，与水平扫描方法相同第四节 QR 码的码制规范QR 码实际上在码制上有严格的规范，这些标准则规定了 QR 码的各项符号要求。下面就通过表格简要的介绍一下 QR 码特有的一些图形符号和属性。表 3-1 QR 码制的要求数字型（阿拉伯数字 0-9）字母型（数字 0-9；字母 A-Z;99 个其他字符：$、+、*、-、.、：、%、/、空格）8bit 字节型：JIS8 位字符集中国汉字（双字节字符表示的字符集）编码字符集日本汉字（JIS 字符集）符号规格 21x21 模块-177x177 模块（版本 1-40，并且每个版本符号每边增加 4 个模块）数据表示法 深色模块表示二进制“1” ，浅色模块表示二进制“0”数字数据：7089 字符字母数据：4296 字符每个数据类型的容量（最大规格字符版本 40-L 级）8bit 字节数据：2953 字符Comment PK3: 1天津科技大学 2014届本科生毕业设计19日本汉字：1817 字符双字节中国汉字：221008 字符数据表示法 深色表示二进制“1” ，浅色表示二进制“0”L级 7%M级 15%Q级 15%4种纠错等级以及可恢复码字比例H级 30%符号类型 矩阵独立定位功能 是结构链接 一组信息通过最多 16个 QR Code码符编写掩模 能够令符号中深浅的模块比例接近1：1 降低相邻模块排列的译码困难扩充解释 通过该方法令符号可以用来表示缺省字符以外的有用数据第五节 QR 码的特征QR码优越于其他条码的地方在于一下几点：1.编码范围广泛：可涵盖签名、图像、文字和指纹等一系列可数字化的信息，通过自己的编码形式表现出来2.信息容量极大：突破其他二维码的限制，可容纳 1850字母，2710 数字甚至是 500多汉字3.成本很低，制作简单，持久耐用4.可靠性极高：由于纠错能力的存在致使它的错误率比普通条码要低很多，误码率几乎不会超过千万分之一它除了保密防伪性强、识读设备便捷的众多优点之外，更具备一下特点： 1.360全方位识读特点：417 条码是将一维码符号的行排高度阶段来实现的，很难实现全方位识读，方位角也仅限于10，而这一特征（超高速识读）则使 QR Code码一下子优于 PDF 417条码2.超高速识读特点：QRCode 是 Quick Response Code的缩写，也就是快速反应的意思。在识读 QR码时，首先通过 QR码特有的位置探测图形来锁定位置，整个识读过程很短。正是该特点，才使它区别于熟知的 PDF 417条码、Data Matrix二维码。所以在工业自动化生产线上应用最广泛的就是 QR code天津科技大学 2014 届本科生毕业设计203.支持中国汉字和日本汉字：QR Code 码采用了特定的数据压缩模式来表示中文和日文，仅仅使用 13bit 就可以表示一个汉字。这使它表示汉字时的效率明显提高了 20%第六节 QR 码的实际应用QR 码技术除了能够存储更多的信息之外，还能对文字、以及 URL 网址和其他类型的数据进行加密工作。自最初日本最先开始使用 QR 码，立即在亚洲掀起了流行巨浪，日后美国也开始大量投入使用，德国也引进该技术多年。现在，它已经不是现代市场的新鲜事物，但在传递印刷品多余信息的应用上却越来越普及。QR 码在各种印刷产品的外包装上随处可见，并且十分引人注目。在面向大众时，数字和网络印刷企业以及平台都是需要从 QR 码技术中慢慢借鉴的。丰富多彩的二维码图形信息都潜藏在代码后。市面上所流行的传统条码都只是对数字进行随机组合，而我们现在运用最多的 QR 码则可以将网址、电话信息、邮件、以及最基本的文字都转变成代码。比如，通过摄像头扫描条码，将存储的信息解码识读。在更多的平台上，我们发现通过二维码来携带用户的个人信息作为名片，就比如微信平台推出的扫一扫，人们通过扫描个人二维码图片即可搜寻添加对方为好友；或者将人们所想要表达的短信内容通过编码隐藏到二维码中去，这样也极大的发挥了保密性。总结归来就是他的自动化文字传输功能。数位内容下载功能，听上去距离我们很遥远，其实则不然，他反而使我们生活中最贴近最常用的一项。我们通常在游戏或者视频影像中看到，通过手机扫描二维码即可下载游戏或者分享到其他平台。通过对二维码的解码就可以轻而易举的连接到网址链接，下载数位内容。如果要说最高端最先进的应用就要说身份鉴别和商务贸易了。大多数公司都希望能够更好地利用 QR 码高效防伪机制，也就将商品的条码特征与交易平台做了链接，用户付款成功后系统则会发回 QR 码进行身份验证，这项功能大多数存在于贩卖机等。某些企业它提供的商品确认服务，将 QR 码与验证中心相连接，除了核对商品资料是否完善，也为消费者提供了生产履历。这样，消费者就可以掌握商品资讯，避免伪造品带来的不必要损失，加大了防伪保护措施。截至 12 年年底，美国威廉姆斯科网络公司，经过市场调查发现，越有三千一百万德国人现拥有智能手机。换句话而言，也就是有更多的人群正在拥有存取 QR 码的能力。根据数字统计，如今消费者对 QR 码是广为好评。这也足以证明，QR 码在市场营销学中的极大潜力。第四章 Reed-Solomon 算法介绍QRcode 采用的就是里德所罗门算法来进行编码的。Reed-Solomon 是含有容错机制的算法。这种算法最大的体现就是用设备进行扫描时，不需要对二维码天津科技大学 2014 届本科生毕业设计21进行逐比特位读取，也就是实现了二维码即使被损坏或者摄入图像不完整的情况下也可以顺利读取的特征。里德所罗门算法有两个极为重要的特点。首先，它是一种可以在最终编码时看到原有信息的显式系统码。其次，不同的 Reed-Solomon 编码可以进行“异或”运算。如果将两个完全不同的编码所得到的解析结果进行异或运算后，我们将发现得到了一个全新的里德所罗门编码。换句话说，这个全新的编码的原码也就是原来两种原码异或的结果。第一节 RS 纠错译码在识读二维码的时候，经常因为原始数据中掺杂着错误信息而导致译码产生错误。所以，在将有用信息按照相对应的码制规则转化为机器可以识别的矩阵之后，还应该在其后加入必要的纠错码块，确保了恢复编码原始信息时能够顺利转化。而在 QR 码中采用的就是 RS 纠错码。首先要了解的概念是 RS 纠错编码，这是指一种在数据编码中加入冗余数据的编码方法。里德所罗门码，可以简称为 RS 码，它是一种特殊的非二进制循环BCH 纠错码。最早的时候由 Irving S.Reed 和 Gustave Solomon 共同发明的纠正编码随机错误的方法。RS 编码被广泛应用在了 DVD 以及多信道传输数据中。它极高的可靠性可以使自身在复杂多变的环境中，有效地处理连续的多个突发错误。RS 码是以伽罗华域的元素作为自己的系数的（n-k）次多项式，并且将此多项式表示为：（4-1） 是指 GF 伽罗华域中的本原元当 RS 的存在长度为 n=q-1 时，就可以根据 2V 个校验位来纠正可能存在的V 个错误，其中的 V 和 q 都是随机的整数。所以不论是对分散的错误还是突发性误差都能够做到很好地纠错效果。本文所设计的识别系统就是采用了 RS 纠错译码作为算法基础。这种循环码具有极强的纠正能力，利用该方法个根据不同的纠错级别可以达到 30%的纠错率。想要好好研究 Reed-Solomon 码就必须先了解伽罗华域还有循环码的概念。第二节 伽罗华域的简介早在 1770 年，法国数学家伽罗华，改进了拉格朗日算法，并且在前人阿贝尔的基础上提出了这种全新的理论伽罗华域（Galois Field，GF） 。伽罗华域是一个有限域，在域中能够进行“加法”和“乘法”两种运算在该理论中提出了一个全新的概念域，每个域包含了每个对应方程的全部根。域所对应的是群，也就是说，方程根的域与群是一一对应的。而仅当群为可解群的时候，次方程式才是可解的。天津科技大学 2014 届本科生毕业设计22伽罗华域也会被称为有限域，在域中必须满足加和乘两种运算法则。如果 是 的本原域内元素，那么 中的所有元素都可以表示为 的幂形式，对于本原元 则必须满足的条件是 ，那么伽罗华域的所有元素就是常见的伽罗华域包括三种：(1)GF（2）：在这个域中只包含 0/1 两种元素，故被称为二元域。对于该域的加法运算是模二运算(XOR 运算)，还有最普通的乘法。(2)GF（p）：包含 0-p-1 种元素，故被称作 P 元域，在 P 阶的域中进行加和乘运算，二元域则是 p 元域中的特例。(3)GF（ ）是在 P 元域的 M 次幂扩域构成的，故被称作扩域。首先定义m 次幂多项式 P（x） ，令 P（）=0，求得 的各次幂，直至次幂，使之满足 ，这些数据 则构成了 域的所有元素。群具有单位元素性还有封闭性，则域中元素均可用 的元素和表示。里德所罗门码就是在 基础上的，也就是在 GF(2)M 次扩域中进行比特异或运算，从而获得二进制的一个序列。如果代表原始数据的多项式是（4-2）那么通过 RS 纠错码之后就会变为 ，等式的前部分是原始信息部分，后者则是纠错编码部分，后者的作用主要是作为冗余数据，便于纠错检查。第三节 循环码的简介在 RS 纠错码中我们初步接触到了循环码的概念。它是一种线性的分组码，任何一组允许码在循环移位后得到的依旧是允许码组，这就是循环码的最大特点。循环码（n，k）生成的多项式一般表示为 G（x） ，从等式（4-3）中可以看出，循环码的多项式 d 的幂次为（n-k） 。m(x)是一个含有 K 个码元的待编码信息组，在添加了（n-k）个校验元之后再将信息传送上去。一般来说，用多项式 r(x)来表示校验元，那么最终的数据码字多项式可表示为（4-4）天津科技大学 2014 届本科生毕业设计23或者（4-5）循环码也具有很强的纠错能力，特别是针对突发性错误十分管用。想要解码循环码，要在接收端开始就检查错误，检查到突发性错误的地方纠错。用原生成 G（x）多项式除以接受码字 R（x） ，结果如果可以被整除，则说明接收的数据不存在错误；如果不能整除存在余项，则说明数据码字传输过程中出现了误差，需要进行纠错。那么，纠错的基本步骤如下：(1) 用原多项式 G(x)除以接收端的 R(x)R(x)=T(x)+E(x) （4-6）余式结果用 r(x)表示。(2) 根据余式 r(x)得到错误样本 E（x） ，由此锁定在传输数据时存在错误的位置信息。(3) 通过 R(x)和 E(x)将纠后的原码 T(x)目前最有效最广泛的循环码就是 BCH 码。我们常见的设计系统中，通常是给定随机纠正错误数作为条件，从而确定生成多项式，这样来达到抗干扰性的要求。但这种做法也存在了很大的局限性，我们下面要介绍的 BCH 码则克服了这项问题。对于大于等于 3 的正整数 m 还有 t(t hints)Mode mode = chooseMode(content, encoding); /选择编码模式Version version = chooseVersion(bitsNeeded, ecLevel); /选择版本信息Version.ECBlocks ecBlocks = version.getECBlocksForLevel(ecLevel);/纠错模块qrCode.MaskPattern = maskPattern;/掩模格式QRCode qrCode = new QRCodeECLevel = ecLevel, Mode = mode,Version = version;public ErrorCorrectionLevel ErrorCorrection/纠错水平模块public string CharacterSet/特征模块设置public bool DisableECI/无效 ECI 符号天津科技大学 2014 届本科生毕业设计42号图像我们已经了解了编码的整个过程就是将字符串到 Bitmap 为徒的一个转换，那么具体的流程如下图 6-3：输 入 接 口待 编 码 字 符 串按 字 符 集 解 码字 符 串数 据 字 节 数 组按 模 式 生 成 数据 比 特 流生 成 纠 错 码构 成 码 字 序 列码 字 字 节 数 组放 置 模 块数 据 字 节 矩 阵生 成 符 号 图 像8位 位 图输 出 接 口纠 错 块 码 字字 节 数 组添 加 终 止 符 及填 充 码 字数 据 流 比 特 数 组数 据 码 字 字 节 数 组图 6-3 编码数据流的转换过程二、 界面功能左侧文本框 EncoderImage 显示经过编码后的 QR 码，右面 Content 文本框输入想要进行编码的文字内容，Encode 按钮进行编码，结果显示在左侧文本框内，Save 按钮则会将编码后