第二章 QR码编码与解码的理论研究
13
（1）数据分析
首先对输入的数据流进行分析，确定编码字符的类型。QR码可以支持对多种不同的数据模式进行编码，包括数字、字母和中国汉字等。分析数据的目的是为了能够对不同的数据模式进行高效的编码。同时根据需要选择相应的纠错等级来提高符号的可靠性。在没有预先设置所要采用的符号版本的情况下，默认选择与数据相适应的最小版本。 （2）数据编码
按照所选择模式的编码标准，将数据字符转换为位流。同时在数据位流前面加上模式指示符，在数据位流之后加上终止符，将产生的位流分为每8 位一个码字，必要时加入填充字符以确保填满按照版本所要求的数据字数。
数据编码举例。当输入数据为：01234567，数字模式。按如下步骤编码： 1)分为3位一组：012//345//67；
2)转换二进制：012--0000001100，345----0101011001，67—1000011； 3)连接得到一个序列：000000110001010110011000011； 4)字符数为8个，得到字符指示符(长度为10位)：8--0000001000；
5)加入模式指示符0001，字符计数指示符0000001000和终止符0000得到最终序列：0001 0000001000 0000001100 01010110011000011 0000。 （3）纠错编码
纠错编码[10]即为根据需要将码字序列分块，生成相对应的纠错码字，一并加入到相应的数据码字序列的后面。QR码的编码采用Reed．Solomon错误控制码来实现纠错功能，纠错面积高，可同时纠正突发错误和随机错误，使得符号在局部污损甚至缺失时仍然可以被正确解码。RS纠错算法可以纠正两种类型的错误：拒读错误(错误码字的位置已知)和替代错误(错误码字的位置未知)。可纠正的替代和拒读错误的数量如下式所示：
e?2t?d?p式(2-1)
式中：e表示拒读错误数；t表示替代错误数；d表示纠错码字数；P表示错误检测码字数。
纠错具体步骤如下：
1)依据版本和纠错等级，将数据码字分成块，分别计算每一块的纠错码；
14 二维码的研究与应用
2)构造降幂的多项式h(x)，多项式的系数为分块后得到的数据码字。第一个数据码字为多项式中幂次最高项的系数，而最后一个码字为幂次最低项的系数；
3)多项式h(x)除纠错码后生成的多项式g(x)的余数就是纠错码。余数的幂次最高项为第一个纠错码字，幂次最低项就是最后一个纠错码字。
x8?x4?x3?x2?x?1的伽罗毕域GF(28)内进行纠错码的运算是在本原多项式：
的。其中加减法为逐比特的异或运算，乘除法为幂指数的模255加减法。 （4）构造数据码字和纠错码字
当所有数据块的纠错码字都生成后，只需要把纠错码字添加到数据码字后 面即可形成最终位流序列。在块序列中，所有的数据码字置于第一个纠错码字 之前。通常情况下数据块和纠错块之和刚好可以填满符号的码字容量，而在某 些版本中，则需要在最终的信息位流末尾添加3，4或7个剩余位。 （5）置入功能模块和码字模块
寻像图形、分隔符、定位图形、校正图形和码字模块一同放到矩阵当中。其中
每个8位码字，按2个模块的宽度从符号的右下角开始蛇形排列。位序列从右到左，从最高位到最低位按模块的排列方向排列。图2.6为一个版本为2的符号字符布置，图2.7和图2.8为其中部分模块的位的序列。
图2.6 版本2-M符号的符号字符布置
第二章 QR码编码与解码的理论研究
15
向上 向下
0 2 4 5
1 3 5 7 6 7 4 2 0 5 3 1 图2.7 向上或向下的规则字符的位的布置
由向上变成向下 由向上变为向下 2 0 3 1 4 6 5 7 0 1 2 4 6 3 5 7
图2.8 布置方向改变的符号字符位布置示例
（6）加入掩模
掩模的目的[11]尽可能避免与位置探测图形相同或者相似的图形出现在符号的
其他区域。掩模的本质就是对符号进行异或(XOR)操作，并对根据相应的规则 对异或后的结果图形记分，最后选择得分最低的图形。掩模过程如图2.9所示。
图2.9 掩模过程
16 二维码的研究与应用
（7）格式与版本信息
格式信息由5位数据位和10位纠错位组成，与掩模图形101010000010010进行异或运算后，所得结果填入相应位置。版本信息由6位数据位和12位纠错位组成，同样放入符号的相应位置。
2.2 QR码解码理论
QR码解码过程就是对图片所包含信息的识读过程，二维码的解码过程可分为图像预处理、条码定位及纠错译码等几个主要步骤。参考国家质量技术监督局发布的 QR 码的参考译码方法如下：
（1） 定位并获取符号图像。深色与浅色模块识别为“ 0”与“1”的阵列。
（2）识读格式信息（如果需要，去除掩模图形并完成对格式信息模块的纠错，识别纠错等级与掩模图形参考。）
（3） 识读版本信息，确定符号的版本。
（4）用掩模图形掩模图形参考已经从格式信息中得出对编码区的位图进行异或处理消除掩模。
（5）根据模块排列规则，识读符号字符，恢复信息的数据与纠错码字。 （6）用与纠错级别信息相对应的纠错码字检测错误，如果发现错误，立即纠错。 （7） 根据模式指示符和字符计数指示符将数据码字划分成多个部分。 （8）最后，按照使用的模式译码得出数据字符并输出结果。 2.2.1 QR的图像预处理
图像的预处理在解码过程中是不可或缺的。它将解决图像存在的失真，歪斜，缺损，以及QR 码图像背景中常常存在与识别条码无关的噪声等问题。预处理流程如下图2.2.1所示。
采集RGB图像灰度化二值化定位仿射变换 图2.10 预处理的基本步骤
第二章 QR码编码与解码的理论研究
17
采集和处理二维条码图像的方式有扫描式和摄像式两种。由于QR码是矩阵式二维条码，所以采集和识读QR码图像只能采用摄像式方式。摄像式图片采集方式又分电荷耦合元件(CCD)和互补金属氧化物半导体(CMOS)两种。CCD采集方式的图像质量高，感光速度快，但硬件开销较大，图像采集成本较高。近年来随着半导体技术的快速发展，CMOS的性价比日益提高，正在逐步占领市场。采集二维条码图像时，首先，通过光学透镜把二维条码图像成像在图像采集传感器上，然后，通过模一数转换或者直接数字化图像采集传感器上的图像，最后采用数字图像处理技术提取和识别数字图像。面向小型嵌入式设备的应用时，如手机、PDA等，还应该考虑图像处理的速度是否满足实时性要求，检测和处理QR码的效率是制约QR码识别系统应用范围的关键。本文所用数据全部是采用摄像式方式采集的包含背景的QR码彩色图像，然后，进行灰度化处理。由于光照条件复杂，灰度化后的图像背景的像素值往往变化较大，QR码符号图像与背景常常不具有很好的分离性。由于检测和识别的是图像中的QR码，所以，在检测和识别QR码之前，需要对图像进行预处理，突出QR码符号图像。QR码图像预处理的步骤如下：
（1）读取含有QR码的灰度图像，若为彩色图像，则先进行图像灰度化处理； （2）采用适当的滤波方法平滑灰度图像，去除部分噪声； （3）利用适当的二值化算法，二值化灰度图像；
（4）检测QR码图像的边缘，并使用Hough变换求出图像的倾斜角度； （5）根据求出的倾斜角度，使用双线性插值法校正倾斜的图像； （6）寻找深色／浅色模块的比符合为：1：1：3：1：1的位置探测图形。 嵌入式系统所采集的图像为彩色RGB格式图像。由于彩色图像包含有大量的颜色信息，在存储和处理上的运算量和开销很大，故先对采集的图像进行灰度化处理。典型的RGB图像灰度化的处理算法有：分量法、最大值法、平均值法、加权平均值法。其中分量法是将RGB中分某个分量当成灰度值，最大值法是将RGB分量中最大值当成灰度值，平均值法是将RGB的值取平均当成灰度值。由于人眼对绿色的敏感最高，对蓝色敏感最低，因此本文采用下式对RGB三分量进行加权平均能得到较合理的灰度图像：
F(x,y)?0.3*R(x,y)?0.59*G(x,y)?0.11*B(x,y) 式(2-2)