（计算机软件与理论专业论文）qr+code识别算法及其在手机上的应用.pdf

o fm a s t e ri nc o m p u t e rs o f t w a r ea n dt h e o r y q r c o d er e c o g n i t i o n a l g o r i t h m so n s m a r t p h o n e b ys u nl e i s u p e r v i s o r ：a s s i s t a n tp r o f e s s o rw a n gj i a n n o r t h e a s t e r nu n i v e r s i t y d e c e m b e r2 0 0 7 56m 2 jjji4m 8iiii-舢y -i l j 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示诚挚 的谢意。 学位论文作者签名： w 需 签字日期2 7 伊飞勿i u 。， 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名：否则视为同意) 学位论文作者签名：导师签名： 签字日期：签字日期： r i 东北大学硕士学位论文摘要 q r c o d e 识别算法及其在手机上的应用 摘要 本文主要论述q r c o d e 二维条码的译码过程，对采集到的图像进行灰度化、中值 滤波、二值化处理，然后根据条码标准所定义的数据编码程序对解析出来的数据进行 重组，经过纠错处理最终得到原始信息数据。以及条码识别在手机上的具体应用，如 短信、w a p 、名片识别等。 手机拍摄的图片受拍摄时的光线强度、角度及拍摄时q r c o d e 图片本身是否弯曲、 噪声等影响，拍摄出的图片有的很模糊，有的还发生了不同程度的变形；同时由于手 机本身的处理能力较弱，内存也较小，所以对拍摄后识别的图片的预处理要求很高， 预处理的好坏直接影响到后面的识别，同时也对识别算法本身的时间、空间复杂度要 求很高。 针对上述的问题，得到识别图像后，对图像的预处理首先采用了灰度化技术，不 仅降低了存储空间，而且便于使用灰度直方图进行相关的处理；然后采用了中值滤波 技术，中值滤波容易去除孤立点，线的噪声同时保持图象的边缘；最后采用了局部阈 值的二值化算法，这些预处理很好的解决了模糊图像的问题。在识别算法中采用了自 适应的网格采样算法，该算法根据采集图像的具体形状做出独立于图像的数据采样网 格矩阵，根据网格交叉点坐标对图像进行数据采样，很好地解决了图像变形问题。 关键词：数字图像处理；q rc o d e ；纠错码；手机应用 一i i r j 一 东北大学硕士学位论文 a b s tr a c t a p p l i c a t i o no fq r c o d e r e c o g n i t i o na l g o r i t h m so n s m a r t p h o n e a b s t r a c t t h i sa r t i c l em a i n l yd e s c r i b e st h ep r o c e s so fr e c o g n i s i n gq r c o d ei m a g ea n dm a k i n g i m a g eg r a ys c a l e ，m e d i a nf i l t e r , b i n a r yi m a g e t h e nb a r c o d er e c o g n i t i o na l g o r i t h mp r o c e s st h e i m a g eg o tf r o ms m a r t p h o n ea n dr e s t o r e t h ed a t af r o mi m a g em a t r i xa c c o r d i n gt ot h e s p e c i f i c a t i o no fq rc o d e a n dt h i sa r t i c l ea l s od e s c r i b e st h ea p p l i c a t i o no fr e c o g n i z i n gq r c o d ei m a g eo ns m a r t p h o n e ，s u c ha sm e s s a g e ，w a pa n dv c a r dr e c o g n i t i o n t h ei m a g e sw h i c hc a p t u r e df r o ms m a r t p h o n ea r ei n f l u e n c e db yb l a m e ds h o o t i n g e n v i r o n m e n t ，s h o o t i n ga n g l e ，c u r li m a g ea n dn o i s ef r o mc a m e r a s o m eo ft h e ma r eab i tt i l t e d o rb l u r r e d a n o t h e rr e s t r i c t i o ni ss e tb ys m a r t p h o n e st h e m s e l v e s ，f o rt h o s eh a n d s e td e v i c e s h a v ev e r yl o wc o m p u t i n ga b i l i t ya n dh a v es t r i c td e m a n do nm e m o r yu s a g e s ot h e yr e q u i r e m g hq u a l i t yp r e p r o c e s s o u rb a r c o d er e c o g n i t i o na l g o r i t h mr e q u i r e ss m a l lt i m ec o m p l e x i t y a n ds m a l ls t o r a g ec o m p l e x i t y b a s e do na b o v ep r o b l e m s ，w ea d o p tg r a ys c a l et e c h n o l o g ya f t e rw eg e tc a p t u r et h ei m a g e a n dt h i st e c h n o l o g yn o to n l yr e d u c e ss t o r a g es p a c eb u ta l s oi sc o n v e n i e n tf o rh i s t o g r a m t e c h n o l o g y a n dt h e nw ea d o p tm e d i a nf i l t e rt e c h n o l o g y , i ti se a s yt ow i p eo f fi s o l a t e dp o i n t ， n o i s eo fl i n ea n dc a nk e e pt h ee d g eo ft h ei m a g e a tl a s tw ea d o pl o c a lb i n a r yi m a g e a l g o r i t h ma n dt h e s ep r e p r o c e s ss o l v et h ep r o b l e mo fb l u r r e di m a g e b a s e do na b o v ep r o b l e m s ， t h ei m p l e m e n t a t i o nm e t h o dd e s c r i b e di nt h i sa r t i c l eu t i l i z e sm e t h o d sf o rn o i s ec l e a n i n ga n d i m a g ec o r r e c t i n g b e c a u s et h eb a rc o d es y m b o l sa r ep r i n t e da st w oc o l o ri m a g e sa n dt h em a i n n o i s ei n f l u e n c eq u a l i t yo fi m a g ei sc a l l e ds a l t p e p p e rn o i s e ，a p p l y i n gm e d i a nf i l t e rg i v e s s m i s f y i n gr e s u l t f o ri m a g et h r e s h o l d ，b e c a u s ei m a g e sg o tf r o mc a m e r ai sv e r yb l u r r y ； t h r e s h o l dm e t h o db a s e do nl o c a lt h r e s h o l dv a l u es a t i s f i e dt h ed e m a n do fn e x ti m a g e p r o c e s s i n gr e q u e s t ，n l ei m p l e m e n t a t i o nm e t h o dd e s c r i b e di nt h i sa r t i c l eu t i l i z e sag r i ds a m p l i n gm e t h o df o r q r c o d ei m a g ed a t as a m p l i n g ，t h i sm e t h o d m a k e sas a m p l i n g g r i da c c o r d i n g t ot h e c o n f i g u r a t i o no fi m a g e ，b u i l dag r i dm a t r i xi n d e p e n d e n to fi m a g ei t s e l f , t h et e s tr e s u l ts h o w si t i sap r o p e rw a yt os a m p l i n gd a t af r o mq r c o d ei m a g e k e y w o r d s ：d i g i t a li m a g ep r o c e s s i n g ；q rc o d e ；e r r o rc o r r e c t i o nc o d e ；a p p l i c a t i o n i i i 一 【-i d 。j 一 东北大学硕士学位论文 目录 目录 独创性声明i 摘要i i a b s t r a c t i i i 第一章绪论1 1 1 研究背景1 1 1 1 二维条码的技术特点。1 1 1 2 二维条码在手机上的应用3 1 2 研究内容3 1 3应用前景4 第二章q rc o d e 二维条码综述7 2 1 二维条码的起源7 2 2 各类二维条码简介8 2 3 各类二维条码简介1 1 2 3 1q rc o d e 的组成1 1 2 3 2q rc o d e 的编码原理。1 4 第三章q rc o d e 图像预处理1 9 3 1 图像处理简介1 9 3 2 图像的灰度化2 0 3 3 图像二值化2 0 3 4 中值滤波2 2 第四章q rc o d e 解码2 3 4 1q r c o d e 译码基本流程2 3 4 2 图像定位2 4 4 3 图像采样2 6 4 3 1 版本1 符号网格采样2 6 4 3 2 版本2 以及更高版本的符号网格采样2 7 4 4 消除掩模2 9 4 5 解读码字序列31 4 6b c h 纠错码3 2 4 7r e e d s o l o m o n 纠错码3 3 一一 东北大学硕士学位论文 目录 第五章系统功能实现及比较3 5 5 1 系统总体设计3 5 5 2 功能模块实现方法及比较3 7 5 2 1 图像预处理模块3 7 5 2 2 数据读取模块4 0 第六章二维条码识别在手机上的应用4 3 6 1 手机开发环境简介4 3 6 1 1s y m b i a n 简介。4 3 6 1 2 手机硬件资源4 3 6 1 3 手机软件基础知识4 4 6 1 4s y m b i a no s 和p c 操作系统的差异3 5 1 4 6 6 2 手机条码识别的前景4 6 6 3 手机上的应用4 7 6 3 1 控制c a m e r a 。4 7 6 3 2w a p 功能5 0 6 3 3 短信功能5 0 6 3 4v c a r d 自动添加地址薄功能5 2 第七章结论5 5 7 1 总结。5 5 7 2 未来研究方向展望5 5 参考文献5 7 蜀c谢。5 9 一v 一 东北大学硕士学位论文 第一章绪论 第一章绪论弟一早珀t 匕 随着移动通信，嵌入式技术和社会信息化的发展，手机的功能越来越强大，从最初的 通话功能发展为目前的包括静态照片拍摄、动态视频捕获等数据量很大的多媒体应用。 条码技术更是随处可见，从商品标签到图书标示几乎无处不在。二维条码的出现把条码 应用推向了更广阔的天地，从一维条码只能“标示”物品n - 维条码能“描述”物品不 仅仅是技术上的进步，而且条码技术在手机上的应用也进一步扩大的条码应用的范围， 同时也给多媒体智能手机增加了一项实用的新功能。 1 1 研究背景 近几年来，随着信息领域自动识别技术的发展，用条码符号表示更多信息的要求与 日俱增。传统条码( 即一维条码) 技术自出现以来，得到人们普遍的关注，发展速度十 分迅速，信息自动识别技术的发展更加促进了条码技术在各行业的应用。目前条码技术 的应用已经从原来的交通运输、商业、医疗卫生、制造业、金融业、仓储业等行业发展 到人的身份识别、电子名片等应用。在欧美和日韩，条码技术与电子商务领域的结合得 到了广泛的应用，通过手机扫描商品的二维条码进行交易。 传统的一维条码具有信息密度低、信息容量小、没有纠错能力、表示汉字十分困难， 保密防伪性差，不能进行有效加密，必须依赖数据库等缺点。本文主要讲述q rc o d e ( q u i c kr e s p o n s ec o d e ，快速响应矩阵码) 二维条码识别算法及其在手机上的设计与具 体实现。 1 1 1 二维条码的技术特点 二维条码在不同行业的各种应用与二维条码本身所具有的特点是分不开的，以下简 单介绍一下二维条码的一些特点【1 1 。 ( 1 ) 存储密度高 因为一维条码是在一个方向进行信息存储，而二维条码利用水平、垂直两个方向进 行信息存储，如图1 1 所示，所以二维条码的存储密度是一维条码信息存储密度的几 十到几百倍，如表1 1 所示。 东北大学硕士学位论文 第一章绪论 铂喘工黧 c = i i ! ! i 11 11 1 , ! i 1 1 1 1i l l i l i l ll l l l l c o n t a i n sd a l z 图1 1q rc o d e 及一维条码数据存储方式比较 f i g 1 1c o m p a r i s o nb e t w e d a t ar e p r e s e n t a t i o no fq rc o d ea n ds i n g l eb a rc o d e 从上面的信息可知，在表示相同数据信息的情况下二维条码所占用面积仅为一维条 码的1 1 ，而在面积相同的情况下二维条码表示信息的容量为一维条码的8 4 倍。 表1 1 一维条码和二维条码存储密度比较 t a b l e1 1c o m p a r i s o nb e t w e e nd a t ad e n s i t yo fs i n g l eb a rc o d ea n d2d i m e n s i o n a lb a rc o d e ( 2 ) 有很强的纠错能力 因为二维条码表示的信息量比较大，从而导致在印刷和扫描识别是容易导致错误， 所以二维条码引入了纠错技术，对不同程度的污损、扭曲变形等图片( 如图1 2 ) 能够正 确识别，但一维条码不具备纠错功能，只是简单地存储数据。 攀鬻鬻鬻鬻 图1 2 污损变形的q r c o d e 图片 f i g 1 2d i r t ya n dt i l t e dq rc o d ei m a g e s ( 3 ) 可表示多种图像及文字信息 二维条码能够存储图片信息及包括数字、数字字符、a s c i i 字符集等多种信息，也 支持汉字和日文，如图1 3 所示，对于一维条码，即使是字符集最大的c o d e1 2 8 码也 只能表示1 2 8 个a s c i i 字符。 一2 一 东北大学硕士学位论文第一章绪论 qr 一f i 衰溪字 力、各耄劲率丧( 3 5 ) 式( 3 5 ) 表明$ 点的中值仅与窗口前后各点的中值有关，以为序列葺的中值。 若把式( 3 5 ) 中，中值滤波的概念推广到二维，并利用某种形式的二维窗口( 则可对 二维中值滤波做如下定义) ： 设 _ ，( f ，_ ，) 1 2 ) 表示数字图像各点的灰度值，滤波窗口为a ，y u 为窗口是a 在点 的中值，则 = 施魏) = 施电，( r , s ) e a , i ，歹， ( 3 6 ) 上式为窗口为a 的x 。点的中值表达式，二维中值滤波的窗口可以取方形，也可以 取近似圆形或十字形。 在第5 章中将对中值滤波的算法和各个方法优缺点的比较有详细的介绍。 一2 2 1嗣黝芍脍lik【e 结 的 化 值 二 b 盘日局出看可较比的 东北大学硕士学位论文 第四章q rc o d e 解码 第四章q rc o d e 解码 q rc o d e 解码是其编码的逆过程。在开始解码前首先对预处理后的q rc o d e 图像在 视场中进行定位，根据q rc o d e 图像的具体位置对其进行采样处理，采样的结果是从图 像采集设备采集到的以像素为单位的q rc o d e 图片提取以模块为单位描述的q rc o d e 图片矩阵，矩阵中1 表示白色模块，0 位黑色模块。因为从q rc o d e 符号的编码过程可 知，输入数据与其对应的纠错码都是以模块为单位组装到q rc o d e 符号图形中的。我们 可从解码后的图像矩阵中提取数据流，并对数据流进行分块对每块纠错最终得到原始的 输入数据。 4 1q r c o d e 译码基本流程 从识读一个q r 码符号到输出数据字符的译码步骤是编码程序的逆过程，下图为译 码的流程【2 0 1 。 ( 1 ) 根据探测图形特征确定3 个位置探测图形中心位置。 ( 2 ) 识读格式信息，按需要去除掩模图形并完成对格式信息模块的纠错，识别纠错 等级与掩模图形参考。 ( 3 ) 通过版本信息和模块宽度，确定探测图形位置，根据版本号、模块宽度、校正 图形中心点划网格。 ( 4 ) 用掩模图形( 掩模图形参考已经从格式信息中得到) 对编码区域的位图进行异 或处理，消除掩模。 ( 5 ) 根据模块排列规则，识读符号字符，恢复信息的数据与纠错码子。 ( 6 ) 用与纠错等级信息相对应的纠错码子检测错误，如果发现错误，则进行纠错。 ( 7 ) 根据模式指示符和字符计数指示符将数据码子划分成多个部分。 ( 8 ) 最后，按照使用的模式进行译码，得出数据字符并输出结果。 一2 3 东北大学硕士学位论文第四章o rc o d e 解码 ，、 ( 开始 ) i 确定位置痴n 图形位置 ， l 确定校正图形中心位置 上 划网格 上 消除掩模 。 上 恢复数据和错误码子 图4 1q r c o d e 识别基本流程 f i g 4 1t h ec h a r to fq rc o d er e c o g n i t i o n 4 2 图像定位 位于q rc o d e 图片三个角上的位置探测图形( 如图4 2 ) 用于定位q rc o d e 图片的 位置，称为位置探测图形。 一2 4 东北大学硕士学位论文第四章q rc o d e 解码 位置探 测图形 图4 2 位置探测图形在q r c o d e 符号中的位置 f i g 4 2t h ed e t e c tl o c a t i o no ff i g u r ei nq rc o d ef i g u r e 确定位置探测图形，q r 码中的3 探测图形有以下特征： 每一位置探测图形的模块序列由一个深色一浅色一深色一浅色一深色次序构成，各 个相同颜色模块宽度的比例是1 ：1 ：3 ：1 ：l 。对这个译码算法，每一元素宽度的允许偏差为 0 5 ( 即单个模块的方块的尺寸允许范围为0 5 - - - 1 5 ，3 个模块宽度的方块的宽度允许尺 度范围为2 5 - - - 3 5 ) ，根据这个特征来确定探测图形位置。 确定位置探测图形的具体步骤【2 l j ： ( 1 ) 在x 轴方向探测q r 码中的每个象素，由于探测图形中相同颜色模块宽度比例 为l ：1 ：3 ：1 ：1 ，在q r 码中不存在满足这个特征的图形。在探测的时候，如果遇到的象素 和上一个象素颜色相同，则把这个象素的个数+ 1 并把象素个数存储；如果遇到的象素 与上一个象素颜色不同，重新开始计算这个相同严格象素的个数。当象素值不等于边界 值时进行检查，如果数组中数据满足1 ：1 ：3 ：1 ：l 说明找到一条，记录后继续扫描，直到整 个图形扫描结束。 ( 2 ) 在y 轴方向探测q r 码中的每个象素，由于探测图形中相同颜色模块宽度比例 为1 ：1 ：3 ：l ：l ，在q r 码中不存在满足这个特征的图形。在探测的时候，如果遇到的象素 和上一个象素颜色相同，则把这个象素的个数+ l 并把象素个数存储；如果遇到的象素 与上一个象素颜色不同，重新开始计算这个相同严格象素的个数。当象素值不等于边界 值时进行检查，如果数组中数据满足1 ：1 ：3 ：1 ：1 说明找到一条，记录后继续扫描，直到结 束。 ( 3 ) 在x 轴和y 轴方向分别找到2 组3 条符合1 ：1 ：3 ：1 ：1 线，3 条中的中间的那条线 就是要找的通过位置探测图形中心的线，2 组中的两条线的交点就是位置探测图形的中 企 。 一2 5 东北大学硕士学位论文 第四章q rc o d e 解码 l ：i ： 3 ：l ：1 忖f _ 1 州 乜3 梗块 b i5 模块 c - 7 模块 图4 3 位置探测图形的构成及扫描线的比例 f i g 4 3t h es t r u c t u r eo fd e t e c t i n gl o c a t i o nf i g u r e 4 3 图像采样 ( 1 ) 确定距离d ，是左上角位置探测图形中心位置与右上角位置探测图形中心位置 之间的距离；确定两个探测图形的宽度，和 ( 2 ) 计算符号的名义模块宽度尺寸x x = ( + ) 1 4 ( 4 1 ) ( 3 ) 初步确定符号的版本v y = k d x ) 一1 0 4 ( 4 2 ) 图4 4 位置探测图形参数 f i g 4 4t h ep a r a m e t e ro fd e t e c t i n gl o c m i o nf i g u r e 4 3 1 版本1 符号网格采样 ( 1 ) 重新确定定位图形中，深色和浅色模块的中心点的水平平均间距x 即水平方向 上模块的大小。用类似的方法，计算左边定位图形中，深色与浅色模块的中心点的垂直 平均间距y 即垂直方向上模块的大小。 ( 2 ) 建立一个取样网格： 一2 6 东北大学硕士学位论文第四章q rc o d e 解码 穿过上部定位图形的水平线，以及与之平行以y 值为垂直间距的水平线，在水 平参考线之上形成6 条与之平行的水平线，水平参考线下方与之平行的水平线的数量由 符号版本决定。 通过左边定位图形的垂直线，以及与之平行的以x 值为水平间距的垂直线，在 垂直参考线左边形成与之平行的6 条垂直线。 4 3 2 版本2 以及更高版本的符号网格采样 根据确定出的版本信息，确定该版本具有的校正图形的个数，由每一校正图形的中 心坐标来确定采样网格。 p m , 一p l p o r p 事 p t p 图4 5 位置探测图形与校正图形 f i g 4 5d e t e c t i n gl o c a t i o nf i g u r ea n dr e v i s ef i g u r e ( 1 ) 左上角位置探测图形( 如图4 4 ) 的宽度w w 除以7 ，计算模块尺寸c p 沈 c p u l = 7( 4 3 ) ( 2 ) 根据左上角位置探测图形p 沈，p 说和p 隙的中心的坐标以及c p 观初步确定校 正图形p ，和p ，的中心坐标。 ( 3 ) 由于校正图形的中心模块为黑色，中心模块四周均为白色模块这个特征。从上 面确定的中心坐标的像素开始扫描，看是否符合校正图形特征，如符合则确定为校正图 形中心，从而确定实际的校正图形中心坐标x ；和y ；( 如图4 6 ) 。 盯酬 图4 6 校正图形 f i g 4 6r e v i s ef i g u r e ( 4 ) 根据左上角位置探测图形p u l 的中心坐标和在上面得到的校正图形t p 和p ：的 一2 7 东北大学硕士学位论文第四章q rc o d e 解码 实际中心坐标值，估计校正图形p ，的中心坐标。 ( 5 ) 按照3 中同样的步骤找到校正图形p ，的实际中心坐标。 ( 6 ) 确定lx 和l y ，l r 是指校正图形p2 和p3 两中心之间的距离( 如图4 7 ) ，lr 是 指校正图形p - 和p s 两中心之间的距离。用校正图形的以定义的间距除l x 和ly 获得位 于符号左上角区域下边的模块节距c pr 值。 c p x2l xl a p h 4 ) c b = l r l a p ( 4 5 ) 其中，a p 是校正图形中心的模块间距。 以同样方式，找出l x 和ly ，l x 是左上部位置探测图形p u l 与校正图形p 的中 心坐标之间的水平距离。l ，是左上部位置探测图形p u l 的中心坐标与校正图形pz 的 中心坐标的垂直距离。有下面给出的公式计算符号左上角区域中上边的模块节距c p x 和左边的节距c p y 值。 c p x = l x ( e 列坐标一列坐标) ( 4 6 ) q = l ，。( 最行坐标一行坐标)( 4 7 ) p 3k 图4 7 符号的左上区域 p l f i g 4 7s y m b o lo f t o pl e f ta r e a ( 7 ) 依据代表符号左上区的每一边的模块节距值c p 、c p y 、c p x 和c p y ，确定 覆盖符号的左上区的采样网格。 ( 8 ) 在同样的方式下，确定符号右上区( 被右上角位置探测图形p ，校正图形p 。p ， 和p 。所覆盖) 和符号左下区( 被左下区位置探测图形p d l ，校正图形p ：p3 和p ，覆盖) 的采样网格。 一2 8 东北大学硕士学位论文 第四章q rc o d e 解码 ( 9 ) 对校正图形p6 ( 如图4 8 ) ，由校正图形p ，、p 。和p ，的间距，穿过校正图形 p ，和p 。，p ，和p ；的中心的导向直线以及这些图形的中心坐标值得到的模块间距c p ， 和c p y 值，估计它的初步的中心坐标。 ( 1 0 ) 重复步骤5 至8 ，确定符号右下区的采样网格。 ( 1 1 ) 用同样原则确定符号为覆盖区的采样网格。 根据以上算法图像网格采样分两步，第一步，绘制网格，采用自适应网格技术实现 对变形、走样图像的网格化从而提高采样的精确度。第二步，根据网格交叉点所在的象 素点的值，得到以0 ，1 表示的q rc o d e 图像矩阵。 h 卜f f f 、1r 吖 。jj k r1r 1 u l p k 。 如 图4 8 符号的右下区域 f i g 4 8s y m b o lo ft o pl e f ta r e a 4 4 消除掩模 q r 码中的功能模型有这自己的特征，为了在非功能模块中不出现同样的特征即大 量的黑色模块不聚集，大量的白色模块不聚集，而采用了掩模操作。即编码结束后和所 选择的掩模图形进行异或操作【2 2 1 。 掩模步骤： ( 1 ) 掩模不用于功能图形，只和非功能模块进行掩模操作。 一2 9 东北大学硕士学位论文第四章q rc o d e 解码 o u 一 1 ， 名 ， 警露曩豳 j 5 矗 z 4 ；1 3 ；1 2 i l l ：l o ：9 _ b 7 ：6 ：s ：4 3 ：1 f ll 薹 8 l ， 1 q 、 _ l 卫 l 意 、 l j 1 4 选择得分量f 燃桌 图4 1 0q rc o d e 符号的掩模过程 f i g 4 1 0t h ep r o c e s so f y a n m o i nq rc o d ei m a g e ( 4 ) 选择得分最低的图形。 掩模过程如图4 1 0 所示： 一3 0 东北大学硕士学位论文第四章q rc o d e 解码 l 还原为原始数据 1 2 1 回 l l 回 图4 11q rc o d e 符号的消除掩模过程 f i g 4 11t h ep r o c e s so fr e - y a n m oi nq rc o d ei m a g e 消除掩模是掩模的逆向过程，根据格式信息中得到的掩模图形，用掩模图形对得到 的位图进行异或( x o r ) ，得到原始的数据图形。 4 5 解读码字序列 构造最终的码字序列步骤：( 数据码字加上纠错码字，必要时加上剩余码字) ( 1 ) 根据版本何纠错等级将数据码字序列分为n 块。 ( 2 ) 对每一块，计算相应块的纠错码字。 ( 3 ) 一次将每一块的数据何纠错码字装配成最终的序列：数据块1 的码字1 ，数据 块2 的码字l ，数据块3 的码字1 ，以此类推至数据块n 1 的最后一个码字，数据块n 的最后一个码字；随后，纠错块l 的码字1 ，纠错块2 的码字l ，以此类推至纠错块 n - 1 的最后一个码字，纠错块n 的最后一个码字。q r 码符号所包含的数据和纠错块通常 正好填满符号的码字容量，而在某些版本中，需要3 、4 或7 个剩余位，添加在最终的 信息位流中正好填满编码区域的模块数。 在块序列中，最短的数据块应在序列的最前面，所有的数据码字应放在第一个纠错 码字的前面。 版本5 - h 的符号由4 个数据块和4 个纠错块组成，前两个块分别包括1 1 个数据码 字和2 2 个纠错码字，第3 、4 个块分别包括1 2 个数据码字和2 2 个纠错码字。在此符号 中，字符的布置如下表所示的纵向顺序即d 1 ，d 1 2 ，d 2 3 ，d 3 5 ，d 2 ，d 1 3 ，d 2 4 ，d 3 6 ，d 1 1 ， 一3 】一 ； 懿h 善 东北大学硕士学位论文 第四章q rc o d e 解码 d 2 2 ，d 3 3 ，d 4 5 ，d 3 4 ，d 4 6 ，e 1 ，e 2 3 ，e 4 5 ，e 6 7 ，e 2 ，e 2 4 ，e 4 6 ，e 6 8 ，e 2 2 ，e 4 4 ，e 6 6 ，e 8 8 表4 1 版本5 h 符号中字符的布置 t a b l e4 1t h ec h a r a c t e rc o l l o c a t i o no f v e r s i o n5 一h 符号字符的布置： 在q r 码符号的编码区域中，符号字符一个模块款的纵列从符号右下角开始布置， 并自右向左，且交替地从下向上或从上向下安排。现面给出了符号字符以及字符中位的 布置原则。 为序列在纵列中的布置位从右到左，向上或向下英语符号字符的布置方向一致 每个码字的最高位( 表示为位7 ) 应放在第一个可用的模块位置，随后的位放在下 一个模块的位置。如果布置的方向是向上的，则最高位占用规则符号字符的右下角的模 块，不值得方向详细视为由上焦，如果先前的字符结束于右侧的模跨纵列，最高为可能 占据不规则符号字符的左下角模块的位置。 如果符号字符的两个模块纵列同时遇到校正图形或定位图形的水平便捷，可以 在图形的上面或下面继续不是，如同编码区域是连续的一样。 如果遇到符号字符区域的上或下边界( 即符号的边缘、格式信息、版本信息或分 隔符) ，码字中剩余的位应改变方向放在左侧的纵列中。 如果符号字符的右侧模块序列遇到校正图形或版本信息占用的区域，位的布置 形成不规则排列的不好字符，沿着相邻校正图形或版本信息的耽搁模块纵列延伸。如果 字符在可用于下一个字符的两列纵列之前结束，则下一个符号字符的首位放在耽搁纵列 中。 4 6b c h 纠错码 b c h ( 1 5 ，5 ) 码用于纠错。以数据位串为系数的多项式除以生成多项式g ( x ) = x l o - i x 8 + x s + x 4 + x 2 + x + 1 除，所得剩余多项式的系数串应追加到数据位串上形成( 1 5 ，5 ) b c h 码字符串。最后通过用1 0 1 0 1 0 0 0 0 0 1 0 0 1 0 对数据传进行易或( x o r ) 运算进行掩模，来 保证掩模图形和纠错等级的任意组合的格式信息位图不全为0 t 2 3 1 。 如：纠错等级m ：掩模图形参考1 0 1 二进制字符串：0 0 1 0 1 3 2 东北大学硕士学位论文第四章q rc o d e 解码 生成多项式： x 2 + 1 将次数升至( 1 5 - - 5 ) z 1 2 + x 1 0 被g ( x ) 除后：= ( x 1 0 + x 8 + x 5 + x 4 + x 2 + x + 1 ) x 2 + ( x 7 + x 6 + x 4 + z 3 + x 2 ) 把上面剩余多项式的系数字符串附加至格式信息数据串。 0 0 1 0 1 + 0 0 1 1 0 1 1 1 0 0 - - 0 0 1 0 1 0 0 1 1 0 1 1 1 0 0 用掩模通行进行x o r 运算：1 0 1 0 1 0 0 0 0 0 1 0 0 1 0 结果： 1 0 0 0 0 0 0 1 1 0 0 11 l o 用掩模图形的位序列1 0 1 0 1 0 0 0 0 0 1 0 0 1 0 对格式信息位序列进行x o r 运算，就出格 式信息模块的掩模。 r - ( r 0 ，r l ，r 2 ，r 1 4 )( 4 8 ) 即： r ( x ) = r o + r l x + r e x 2 + + r 1 4 x 1 4 ( 4 9 ) 其中：r i ( i _ 0 1 4 ) 是0 或1 。 计算伴随多项式： 找伴随多项式s i s i = r ( a ) = r o + r l c t + r 2 c t 2 + + r 1 4 0 t 1 4( 4 1 0 ) s 3 = r ( t x 3 ) = r o + r l a 3 + r 2 a 6 + + r 1 4 扩2 ( 4 1 1 ) s s = r ( o t 5 ) = r o + r l q 5 + r 2 a l o + + r 1 4 a 7 0( 4 12 ) 其中：0 【是g f ( 2 4 ) 上的基元。 找错误位置 s f + 盯f = 0 s 3 + $ 2 0 - 1 + s l 仃2 + 盯3 20 s5 + s4 仃1 + s 3 盯2 + s2 盯3 20 其中，s2 = s l2 ，s4 = s2 2 ( 4 1 3 ) ( 4 1 4 ) ( 4 1 5 ) 用上述公式对每一错误位置计算变量仃，( i = 1 3 ) 。然后用变量盯。替代下面的多项 式的变量并逐个替代g f ( 24 ) 上的元素。 仃( x ) = x 3 + 盯l x2 + 仃2 x + 盯3 ( 4 1 6 ) 即可找出错出现在元素旺，的第j 个位上( 从第0 位开始计数) ，此时0 【，满足盯( o t j ) = 0 。对每一错误位置上的位值取反来纠错。 4 7r e e d s o l o m o n 纠错码 以版本1 一m 符号为例，对该符号来说，域g f ( 2 8 ) 上的( 2 6 ，1 6 ，4 ) r e e d s o l o m o n 码 用于纠错。假设符号解除掩模后的码字是1 2 4 2 5 】： 一3 3 东北大学硕士学位论文 第四章q rc o d e 解码 r ( x ) = r o + r l x + r 2x 2 + 竹2 5x 2 5 ( 4 1 7 ) 其中：r i ( i = o 1 4 ) 是0 或1 。 ( 1 ) 计算伴随多项式 找伴随多项式s ； s 0 2r ( a ) 2r o + r l + r 2 + 竹2 5 ( 4 1 8 ) s i = r ( a ) = r o + r l 叶r 2 a 2 + + r 2 5 1 2 2 5 ( 4 19 ) s 7 = 脚7 ) = r o + r l c 【7 + r 2 伐1 4 + + r 2 5 0 【1 7 5( 4 2 0 ) 其中：a 是g f ( 2 8 1 上的基元。 ( 2 ) 找错误位置 soc r 4 一s ic r 3 + s 2c r 2 - s3q + s42 0 ( 4 2 1 ) s 1 仃4 一s2 仃3 + s3 盯2 一s4 盯l + s5 = 0( 4 2 2 ) s2 仃4 一s3 盯3 + s4 仃2 - s5 盯l + s6 = 0 ( 4 2 3 ) s3 仃4 - s4 仃3 + s 5 仃2 - s6 盯l + s7 = 0( 4 2 4 ) 用上面的公式，找每一错误位置的变量q ( i = l 一4 ) ，然后，用变量吼( i = l 4 ) 替代