二维码水印加密并行化嵌入及提取方法

刘永俊，秦立浩

（1.常熟理工学院计算机科学与工程学院，江苏 常熟 215500；2.东北大学计算机科学与工程学院，辽宁 沈阳 110819）

二维码水印加密并行化嵌入及提取方法

刘永俊1,2，秦立浩1

（1.常熟理工学院计算机科学与工程学院，江苏 常熟 215500；2.东北大学计算机科学与工程学院，辽宁 沈阳 110819）

提出了一种并行化LSB（Parallel Least Significant Bit）算法，实现了二维码图像水印的嵌入、提取.对待处理图像数据进行分块并利用Open MP的编译制导指令进行任务分担，实现了运算过程的并行化.该方法嵌入水印的二维码图像具有较好的防伪验证功能，而且适合以电子形式保存，并行化处理方法较传统串行算法可缩短1/3左右的时间.

图像表示；数字水印；并行化算法

二维码图像具有容量大、可靠性高、全方位识别等特点，QR码被广泛应用于电子票证、火车票验证以及移动支付等领域.因此提高二维码的安全性和处理速度显得尤为重要.在二维码中嵌入特殊的水印信息可以解决数字内容的版权保护和信息安全问题，而充分挖掘CPU多核计算性能则可以提高处理速度.李娜等［1］对当前数字水印嵌入算法作了全面的研究和综述，分析了它的发展前景以及存在的问题.Ming Sun等［2］提出两种基于离散小波变换（Discrete Wavelet Transform,DWT）的QR码数字水印，分别可以嵌入随机序列和图片.Jau-Ji Shen等［3］针对PDF417码提出一种称作关联水印的盲水印算法，该算法可以提高水印的嵌入容量并可将PDF417码用于数据认证.Vongpradhip S等［4］针对QR码提出一种基于离散余弦变换（Discrete Cosine Transform，DCT）变换的数字水印算法，可以将加密信息隐藏于DCT域的中频系数中.吕望述等［5］分析了对载体LSB替换隐写实现方法的RS攻击和如何抗RS攻击.苏亚娟［6］提出了将矩阵编码引入LSB替换，在保证一定峰值信噪比的前提下使得嵌入量提升了一倍.朱本威等［7］提出了基于改进的LSB的空域二维码水印嵌入算法，解决了电子形式数字水印的保存问题.

1 LSB水印嵌入/提取算法概述

1.1 基本思想

LSB（Least Singificant Bit）算法的基本原理是根据数字图像可分解为8个位平面图，改变最低位平面对原有图像的影响非常小.在二维码图像中，通过修改最低的几位就能达到隐藏大量信息的目的.

QR二维码的图像是由N*N个深色或者浅色的模块组成.在嵌入水印之前，先对二维码的灰度图像进行二值化处理，处理过程是遍历每一个像素点，设定一个阈值，对于小于等于阈值的像素，将其RGB分量都置0，也就是变成黑色，对于大于阈值的像素，将其RGB分量都置255，也就是变成白色.这样，原来的深色模块就为黑色，浅色模块就为白色.最后用RGB分量图构造成一个三维数组图像.选择其中的黑色模块进行LSB修改，这样能减少人眼对图像发生的变化产生明显的差异感.

图1 二维码中水印嵌入段示意图

在二维码图像上的像素按行排列时，若连续若干行中行与行间像素值相同，则这若干行模块处于同一层，如图1所示行与行处于不同层.上一层的下边界即为两层交界处，也就是嵌入行.从深色、浅色模块组成上，深色模块处于上一层，浅色模块处于下一层，深浅模块交界处是指深色模块下边界.两层交界处中的深浅模块交界处是嵌入段（用灰色阴影描出）.

在非位置探测区域寻找具体嵌入位置包含两条规则：一是嵌入行处于两层交界处；二是嵌入行中深浅模块交界处为嵌入段.

找到嵌入位置后嵌入水印，水印采用一组伪随机序列构成，在水印信息嵌入的过程中，每次从序列中提取2 bit大小的信息，然后根据表1方式改变对应像素最低位的值.其编码规则如表1所示.

1.2 水印嵌入方法

1）遍历二维码图像的每两行像素，如果第一行像素的像素值不同于第二行像素的像素值，则第一行可能为嵌入水印行，进入步骤2）；

2）在可能嵌入水印行排除位置探测区的像素.并开始判断起始位，起始位判断规则是：如果该像素点为黑色且满足条件a（如图2所示，点左边和左下角像素点为黑色，下边像素点为白色），或者该像素点为黑色且满足条件b（如图3所示，左边像素点为白色，下边像素点为白色），则记录此像素坐标为水印起始位并进入步骤3），否则判断下一像素点；

3）从水印起始位像素坐标的后一位开始进行结束位判断，所述结束位判断为：如果该像素点为黑色且满足条件c（如图4所示，点右边像素点和右下角像素点为黑色，下边像素点为白色），或者该像素点为黑色且满足条件d（如图5所示，点右边像素点为白色，下边像素点为白色），则记录此像素坐标为水印结束位并进入步骤4），否则判断下一像素点；

4）顺序提取水印信息的2 bit大小的信息，按前述设定编码规则，改变水印起始位到水印结束位的每个像素RGB分量的最低位，如果水印结束位是该行最后一个像素，返回步骤1），找寻嵌入行；否则返回步骤2）从水印结束位对应像素点开始进行起始位判断，直至所有水印信息嵌入完毕.

图2 条件a示意图

图3 条件b示意图

图4 条件c示意图

图5 条件d示意图

1.3 水印提取方法

1）将嵌入水印的二维码图像分离成RGB分量图，遍历图像，读取连续的3行像素，如果3行像素满足第二行像素的像素值和第三行像素的像素值相同，且第一行像素的像素值和第二行像素、第三行像素的像素值都不同，则第一行为可能包含水印行，进入步骤2），否则继续读取下面连续的3行像素查找可能包含水印行；

2）在可能包含水印行，排除位置探测区域，并从第一像素点开始进行起始位判断，起始位判断为：如果该像素点为黑色且满足条件a，或者该像素点为黑色且满足条件b，或者该像素点为非黑非白且满足条件a，或者该像素点为非黑非白且满足条件b，则记录此像素坐标为水印起始位并进入步骤3），否则判断该可能包含水印行的下一像素点直到找到水印起始位；

3）从水印起始位的像素坐标的后一位开始进行结束位判断，结束位判断规则是：如果该像素点为黑色且满足条件c，或者该像素点为黑色且满足条件d，或者该像素点为非黑非白且满足条件a，或者该像素点为非黑非白且满足条件b，则记录此像素坐标为水印结束位并进入步骤4），否则判断下一像素点直至找到水印结束位；

4）提取从水印起始位至水印结束位之间的每个像素的RGB分量的最后一位，嵌入水印时，每一段的水印都是相同的，但由于会受到噪声的影响，在提取的时候，只保留出现频率最高的那个数据，按设定编码规则，复原水印信息.完成该行的水印提取后，返回步骤1）直到提取出全部水印.

2 PLSB水印嵌入/提取算法

图6 Parallel结构示意图

图7 PLSB结构示意图

图8 PLSB数据结构示意图

在手机等嵌入式设备多核CPU普及后为算法并行化提供了可行性，为进一步充分挖掘多核CPU的计算性能，提高水印算法速度，提出了一种二维码水印加密并行化快速嵌入及提取方法，使其适合于并行化处理.

上述二维码水印加密并行化快速嵌入以及提取方法的并行设计主要采用以下两种方式：

1）Parallel：如图6所示，将待处理数据分成4份，各自分配给4个线程去完成寻找提取段任务（S）和提取水印任务（E）.

2）PLSB：如图7所示，将待处理数据分成4份，各自分配给4个线程去完成寻找提取段任务（S），然后以模块宽度为单元统计出总单元数n并均分给4个线程（即所谓负载均衡）去完成提取水印任务（E）.负载均衡方法如图8中数据结构图所示，s表示提取段起点列下标，e表示提取段终止点列下标，n来表示模块单元数.假设共有k个提取段，则：

最后一个嵌入单元数即为嵌入单元数的总和，则：

如图7所示，将数据均分给4个线程的处理（以4核CPU为例）.

3 实验效果及分析

3.1 软件使用具体操作步骤及显示

1）点击“打开图片”按钮选择待处理图片，被选图片图会在按钮上方显示，然后点击“水印嵌入”按钮，嵌入水印后的图片在按钮上方显示，如图9所示.

2）点击“检测”按钮能够看到被嵌入到图片中的数字水印，如图10所示.

3.2 PLSB性能比较

分别采用串行方法（Loop）、未均衡负载的并行方法（parallel）、PLSB方法连续处理100张图片作性能比较，如图11所示.该方法嵌入水印的二维码图像不仅具有较好的防伪验证功能而且适合以电子形式保存，并行化处理方法时间花销较传统串行算法节省1/3左右.

图9 实验主界面

4 总结与展望

二维码应用的普及，使如手机病毒、恶意程序、钓鱼网站等通过二维码传播的潜在风险也在加大.本文提出的PLSB方法，使得二维码图像具有较好的防伪验证功能而且适合以电子形式保存，并行化处理方法时间花销较传统串行算法节省1/3左右.

在利用二维码实现图书馆藏地点导航和导向标识系统、基于视觉的移动机器人自主导航等应用中都对二维码的解码速度提出了较高的要求，可见基于二维码加密的并行算法研究存在着广阔的应用前景.

图10 水印检测信息显示界面

图11 3种方法运行时间比较

［1］李娜，王洪君，李士锋.频域数字水印研究［J］.信息技术与信息化，2005，25（3）：43-44.

［2］SUN M,SI J B,ZHANG S H.Research on embedding and ex tracing methods for digital watermarks applied to QR code images［J］.New Zealand Journal of Agricultural Research,2007,50(5):861-867.

［3］SHEN J J,HSU P W.A Fragile Associative Watermarking on 2D Barcode for Data Authentication［J］.International Journal of Network Security,2008,7(3):301-309.

［4］VONGPRADHIP S,RUNGRAUNGSILP S.QR code using invisible watermarking in frequency domain［J］.ICT and Knowledge Engineering(ICT&Know ledge Engineering),2012,12(6):47-52.

［5］吕述望，陈庆元，刘振华，等.对RS攻击的分析及抗RS攻击的隐写算法［J］.中山大学学报（自然科学版），2004，43（3）：5-9.

［6］苏亚娟.基于矩阵编码的空域信息隐藏算法［J］.计算机工程与设计，2009，30（23）：5344-5347.

［7］朱本威.基于LSB的QR码数字水印算法研究［J］.成都信息工程学院学报，2012，27（6）：541-547.

A Parallel Embedding and Extracting Method of Watermarking Encryption in the QR Code

LIU Yongjun1,2,QIN Lihao1
(1.School of Computer Science and Engineering,Changshu Institute of Technology,Changshu 215500; 2.School of Computer Science and Engineering,Dongbei University,Shenyang 110819,China)

A Parallel Least Significant Bit(PLSB)algorithm is proposed,which realizes the embedding and extracting of the QR code watermark.The image data is divided into blocks and the tasks are shared by the compiling and guiding instruction of Open MP,which realizes the parallelization of computing process.The QR code image embedded in the watermark method has a better security verification function and is suitable for saving in the electronic form.The time cost of the parallel processing method is about 1/3 less than that of the traditional serial algorithm.

the representation of the image;digital watermarking;parallel algorithm

TP391.41

A

1008-2794（2017）02-0039-04

2016-12-07

江苏省高校自然科学基金项目“微纳米光学图像特征分析及多维度测量”（15KJB520001）

刘永俊，副教授，博士研究生，研究方向：人工智能与智能系统，高性能并行计算，E-mail:yongjun1981@126.com．