基于LSB的QR码数字水印算法研究

朱本威, 万武南, 陈 运

（成都信息工程学院信息安全研究所,四川成都 610225）

0 引言

快速响应矩阵码（QR Code,QR码[1]）是二维码中的一种,具有信息容量大、可靠性高、高速全方位识读等特点。QR码被广泛应用于电子票证、火车票验证以及移动支付等领域,是当前防伪和保密技术的研究热点之一。

目前,国内外关于二维码信息隐藏技术的文献不是很多,研究对象主要是四一七条码（Portable Data File417,PDF417码）和QR码。在国内,针对PDF417码的研究较多且以空域水印为主,在国外,以研究QR码居多,以频域水印为主。牛夏牧等[2]利用变形技术对PDF417码中的各组成单元宽度加以适量的变动,采用误差累积的方式实现隐藏信息的嵌入和提取。陈峥等[3]针对PDF417码,提出了基于边界移位的隐藏信息嵌入算法。赵博等[4]提出一种基于结构微调法的水印算法,对PDF417码的组成条空进行适量的微调,将信息隐藏进二维码中。晁玉海等[5]提出一种对隐藏信息进行扩频和映射处理,根据PDF417码自身结构特点,通过微调条码中的条和空将信息隐藏的方法。Ming Sun等[6]提出两种基于离散小波变换（Discrete Wavelet Transform,DWT）变换的QR码数字水印,分别可以嵌入随机序列和图片。Jau-Ji Shen等[7]针对PDF417码提出一种称作关联水印的盲水印算法,该算法可以提高水印的嵌入容量并可将PDF417码用于数据认证。Vongpradhip S等[8]针对QR码提出一种基于离散余弦变换（Discrete Cosine T ransform,DCT）变换的数字水印算法,可以将秘密信息隐藏于DCT域的中频系数中。Suppat Rungraungsilp[9-10]针对QR码,对比了在DCT域、DWT域和离散傅里叶变换（Discrete Fourier Transform,DFT）域上的数字水印算法优缺点。

总结起来,基于二维码的数字水印可以分为空域水印和频域水印。其中,空域水印的基本思想是对二维码的深浅图形模块的边缘像素进行扩展或者缩减,利用二维码识别算法对深浅模块图形有一定的误差允许,而不会影响到二维码的正确识别的特点,实现秘密信息嵌入。频域水印的基本思想是对二维码图像进行DCT、DWT或DFT域的变换处理后,修改不同频的系数来嵌入水印。由于空域水印算法对二维码的图形结构进行了修改,而频域水印会使二维码图像变得模糊不清,导致两种算法都只适合用于打印的二维码。当采用电子文件形式保存二维码,或者二维码图像的清晰度很高并且信息容量低时,则这些算法并不太适合。

针对目前基于二维码的空域数字水印算法的研究对象以PDF417码为主,对QR码的研究较少,并且以微调图形结构的方法为主。文中将根据QR码的结构特点,结合结构微调水印算法的基本思想,采用改进的最不重要位（Least Significant Bit,LSB）算法实现一种适合QR码的脆弱数字水印算法。相对于基于图形结构微调的算法,该算法嵌入的水印具有更好的隐蔽性,同时对QR码的信息容量没有要求,能够解决目前嵌入水印的二维码不适合以电子形式保存的问题。

1 基础理论

1.1 QR码

QR码是由日本Denso公司于1994年9月研制的一种矩阵式二维码符号,除具有一维条码及其他二维码所具有的信息容量大、可靠性高、可表示汉字及图像等多种信息的优点以外,还具有高速全方位识读、有效表示汉字等特点。图1是一个版本号为2,纠错等级为L的QR码图像。

1.2 改进的LSB算法

基于LSB嵌入秘密信息的方法是信息伪装技术中最经典的一类方法,能够较易的应用于图像和语音文件中,只需要对载体文件做很小且不易被觉察的改变就能隐藏大量的秘密信息。

然而,传统的LSB算法比较简单,在信息隐藏技术领域被研究的比较透彻。在QR码中,对LSB算法的直接使用并不一定能够非常有效的提高水印嵌入的效果。

Jessica Fridrich[11]最早提出将矩阵编码应用到基于LSB替换的信息伪装系统中以提高水印的嵌入效率。苏亚娟[12]提出一种空域信息的隐藏算法,将矩阵编码引入空域水印算法中,有效提高水印嵌入效率。

使用矩阵编码的LSB算法能够做到在2k-1位LSB中只需要修改一位LSB,就可以表示一个k bit大小的数据。

对于计算机中的一张彩色图像,其每一个像素点是由R（红）、G（绿）、B（蓝）3个分量组成,每个分量分别占用8 bit的数据大小,也就是说每个分量拥有256级灰阶。根据LSB的思想,水印的嵌入位置选择像素点RGB分量的最低位。那么,一个像素点就可以提供至少3位可替换的LSB,根据矩阵编码思想,即表明一个像素点可以表示至少2 bit大小的信息。

QR码图像是一种二值图,图像中深色和浅色的模块图形,在实验中用黑色和白色像素表示。如果对白色像素的LSB进行修改,一般情况下会引起明显变化,为了减少人眼的对图像发生的变化产生明显的差异感,选择修改黑色像素的LSB值。黑色像素的原始RGB值及修改最低位之后的RGB值如表1所示。

图1 版本号是2的QR码图形

表1 黑色像素RGB分量的值

运用矩阵编码的方式,设k=2,则2k-1=3,定义操作如下:

其中a1表示R的最低位,a2表示G的最低位,a3表示B的最低位,x1表示2 bit信息中的高一位,x2表示2 bit信息中的低一位。分别修改RGB 3个分量的LSB值,得到的计算结果如表2所示。

表2 RGB分量最低位的矩阵编码结果

表3 黑色像素 RGB分量的矩阵编码结果

从表2中可以看出,只需要修改像素RGB分量的3个最低位的其中一位,就可以嵌入1个2 bit大小的信息。针对QR码图像,需要修改黑色像素点的LSB值,黑色像素点的RGB值是#000000。于是,对黑色像素进行处理,得到的对应结果如表3,其中RGB分量用8位二进制表示,X1X 2表示得到的编码信息。根据此表,在进行具体的水印嵌入操作时,根据水印信息,修改对应像素的RGB分量的最低位。反之,在进行具体的水印提取操作时,根据像素信息,得到对应像素的水印信息。

2 适用于QR码的数字水印算法

2.1 水印嵌入算法

设QR码的一个模块图形的大小为 M*M,其中M 为模块的长度（高度）,单位是像素。每2 bit的水印信息嵌入的位置是QR码图形中除去位置探测图形以外的若干个满足下方是白色模块图形的黑色模块图形的下边界像素,像素个数为n*M,n为连续模块的个数,即表示通过修改 n*M 个像素的LSB值嵌入2 bit信息,如图2所示,左边是含有水印的QR码,右边是水印嵌入位置的展示图。

QR码图像是由N*N个深色或者浅色的模块图形组成,实验中是黑色和白色模块。根据QR码的特点,读取QR码图像中连续的两行像素的像素值,如果两行像素不同,则说明是第1行像素属于上一层（行）的模块图形,第2行的像素属于下一层（行）的模块图形。图3是QR码水印嵌入算法的步骤描述。

图2 水印位置

表4 水印算法的条件描述

依据此特点,文中的嵌入水印算法描述如下:

（1）从QR码图像的第1行像素开始,读取连续两行像素的像素值,如果相同,则向下移动一行,继续读取连续两行像素的像素值。以此类推,当读取到两行像素,不相同时,则进入步骤（2）。

（2）若从步骤（1）进入（2）,则从左到右,读取当前两行像素中,第1行像素的每一个像素点,当该行像素中某一个像素点满足条件a或者条件b时,见表4,则记录该像素点的坐标（XS,YS）,进入步骤（3）,否则继续读取第1行中的下一个像素。若从步骤（4）进入（2）,则从步骤（4）所在的坐标位置开始,继续寻找新的坐标（XS,YS）,然后进入步骤（3）。

（3）从步骤（2）中读取的像素点的位置开始,继续读取第1行中后面的像素,当寻找到某一个像素点满足条件c或者条件d时,见表4,则记录该像素点的坐标（XE,YE）,并进入步骤（4）,否则继续读取第1行的下一个像素点。

（4）将待嵌入的水印信息依顺序取出2 bit大小的信息,并根据表3,选择对应需要修改的LSB值,修改坐标（XS,YS）到坐标（XE,YE）上的连续n*M 个像素的LSB值。至此,完成一次大小为2 bit的水印嵌入。然后转入步骤（2）,继续寻找该行剩余的水印嵌入位置。当此行像素读取完成,进入步骤（1）,继续寻找可嵌入水印的像素,直到完成所有水印的嵌入。

2.2 水印提取算法

由于嵌入水印的QR码和原始的QR码不同,所以如果依旧采用读取两行像素的方式,并不能正确的找到含有水印的像素点。

此时,要寻找到正确的水印信息,需要读取连续的3行像素,当这3行像素满足第2行和第3行的像素相同,而第1行与第2行、第3行的像素不同时,读取到的第1行像素就包含了要找的水印像素点。图4是QR码水印提取算法的步骤描述。

水印提取算法描述如下:

（1）从QR码图像的第1行像素开始,读取连续3行像素的像素值,当满足第2行和第3行的像素相同,而第1行与第2行、第3行的像素不同时,进入步骤（2）,否则向下移动一行继续读取连续3行的像素值,以此类推。

（2）若从步骤（1）进入,则从左到右,读取当前第1行中的每一个像素,当第1行中某一个像素点是黑色像素并且满足条件a或者条件b时,或者当第1行中某一个像素点为非黑白色像素并且满足条件a或者条件b时,条件描述见表4,则记录该像素点的坐标（XS,YS）,进入步骤（3）,否则继续读取第1行的下一个像素。若从步骤（4）进入,则继续步骤（4）的坐标位置,继续寻找新的坐标（XS,YS）。

（3）接着步骤（2）中读取的像素点位置,继续读取第1行中后面的像素值,当寻找到某一个像素点是黑色像素点并且满足条件c或者满足条件d时,或者是非黑白色像素点并且满足条件c或者条件d时,见表4,则记录该像素点的坐标（XE,YE）,并进入步骤（4）,否则继续读取第1行的下一个像素。

（4）读取坐标（XS,YS）到坐标（XE,YE）上的连续n*M个像素的LSB值,比较选择出n*M 个像素中重复最多的LSB值。根据表3,输出对应的水印信息。然后转入步骤（2）,继续寻找该行剩余的水印。当本行像素读取完成,进入步骤（1）,读取下面的3行连续像素,直到完成所有水印信息的提取。

图3 水印嵌入算法步骤描述

图4 水印提取算法步骤描述

3 实验和结论

3.1 对比结构微调的水印算法

目前,大多数基于二维码的数字水印算法都是在不影响识读的条件下,通过适量的修改二维码的图形结构,嵌入水印信息。以PDF417为例,有通过修改条和空的宽度嵌入水印的算法[2-5],如图5所示。另外也有修改两行条码中某一行的高度来嵌入水印的算法[13]。而针对QR码,有通过扩展点阵模块的左右侧和上下侧的边缘宽度嵌入水印信息[14],如图6所示。

图5 修改PDF417的条和空的宽度和高度的水印算法效果图

图6 修改QR码的黑色模块边缘像素的水印算法效果图

图5中,针对PDF417码,从上至下的第1个图形不含水印,第2个图形是纵向修改边缘像素,第3个图形是横向修改边缘像素。图6中的上方图形是无水印的QR码,下方图形是修改深浅模块的边缘像素的QR码。

3.2 含有水印的QR码的识别和水印提取实验

图7 无水印QR码和含水印QR码

根据QR码识别的原理,识别算法会选择图像像素RGB值的最大值和最小值的中值作为阈值,使用该阈值将图像划分为一系列深色和浅色的模块。因对QR码像素LSB的修改不会影响到阈值的正确选择,从而不会影响到QR码的正确识别。图7是水印算法的实现效果图,（a）图是不含水印的QR码,（b）图是含有水印的QR码。

图8 一次实验的工作流程

算法稳定性实验,流程如下:

（1）产生一段随机长度和随机内容的文本T1。

（2）将文本T1编码为QR码图形Q1。

（3）计算Q1的水印容量大小。

（4）产生一个满足Q1水印容量的随机水印信息W（二进制信息）。（5）向Q1中嵌入水印信息W得到含有水印的QR码图形Q2。

（6）识读Q2得到T2,并与原始编码内容T1对比,记录对比结果。

（7）从含有水印的QR码图形Q2中提取水印信息WR。

（8）比较W和WR,记录对比结果。

（9）重复10000次步骤（1）～（8）的试验,并计算QR码的识别正确率和水印嵌入和提取的正确率。

图8是步骤（1）～（8）的一次完整实验的工作流程。实验中QR码图像的大小为500*500像素,文件格式为BMP,纠错级别随机。随机文本T包含英文字母、数字和常用标点符号。重复试验的次数为10000次,最后记录实验结果并计算正确率。实验最终得到的数据是QR码的识别正确率为100%,嵌入和提取水印的正确率为100%。该实验表明,水印算法非常稳定,嵌入的水印不会影响到QR码的正确识别,并且水印信息的嵌入和提取不受水印内容和QR码载体图像的影响。

3.3 结论

提出了一种适用于QR码的脆弱水印算法,该算法运用一种改进的LSB算法嵌入水印信息,保证水印信息不会改变QR码的图形结构,并确保嵌入的水印信息不会影响到QR码的正确识别。与现有的利用误差特性进行信息隐藏的算法相比,该算法极大程度增强了数字水印的隐蔽性,提高了水印信息的嵌入量。同时算法不会受到QR码的容量限制,并且能够解决目前嵌入水印的二维码不适合电子文件形式保存的问题,可以将嵌入水印的QR码广泛应用于终端设备对电子票的防伪及验证。

致谢:感谢成都市科技攻关项目（10GGYB368GX023）;成都信息工程学院自然科学基金项目（CSRF2001）对本文的资助。

[1] 中国物品编码中心.二维条码技术与应用[M].北京:中国计量出版社,2007:324-325.

[2] 牛夏牧,黄文军.基于二维条码的信息隐藏技术[J].中山大学学报（自然科学版）,2004,43（S2）:21-25.

[3] 陈峥,姚宇红.一种基于二维图形码的数字水印技术[J].计算机应用,2006,26（8）:1998-2000.

[4] 赵博,黄进.基于PDF417条码的信息隐藏方法[J].计算机工程与设计,2007,28（19）:4806-4809.

[5] 晁玉海,刘连山.基于PDF417条码的信息隐藏算法[J].计算机工程,2010,9:131-133.

[6] Ming Sun,Jibo Si,Shuhuai Zhang.Research on embedding and extracting methods for digital watermarks applied to QR code images[J].New Zealand Journal of Agricultural Research,2007,50（5）:861-867.

[7] Jau-Ji Shen,Po-Wei Hsu.A Fragile Associative Watermarking on 2D Barcode for Data Authentication[J].International Journal of Network Security,2008,7（3）:301-309.

[8] Vongpradhip S,Rungraungsilp S.QR code using invisible watermarking in frequency domain[J].ICT and Knowledge Engineering（ICT&Knowledge Engineering）,2012:47-52.

[9] Suppat Rungraungsilp,Mahasak Ketcham,Pruch Surakote.Data Hiding Method for QR Code Based on Watermark by comparing DCT with DWT Domain[J].International Conference on Computer and Communication Technologies（ICCCT′2012）,2012:149-153.

[10] Suppat Rungraungsilp,Mahasak Ketcham,Pruch Surakote.Data Hiding Method for QR Code Based on Watermark by compare DCT with DFT Domain[J].International Conference on Computer and Communication Technologies（ICCCT′2012）,2012:144-148.

[11] Jessica Fridrich,Miroslav Goljan,Rui Du.Detecting LSB steganography in color and gray-scale images[J].IEEE Computer Society,2001,10:22-28.

[12] 苏亚娟.基于矩阵编码的空域信息隐藏算法[J].计算机工程与设计,2009,30（23）:5344-5347.

[13] 魏伟光.二维条码空间域数字水印嵌入方法研究[J].北方工业大学学报,2010,（3）:131-133.

[14] 孙丙,高美凤.基于QR码的数字水印算法研究[J].计算机与现代化,2011（11）:74-77.