基于改进的Zigzag置乱的DWT图像水印算法

摘 要：信息的隐藏和伪装技术是图像安全方面的重要研究方向。常用的置乱算法较为复杂，为了兼顾算法速度和解密的复杂性，提出使用m序列改进Zigzag变换来满足上述两个要求。由于在各种图像处理过程中，有损压缩对数字水印的生存打击较大，故使用DWT分解来满足抵抗有损压缩的攻击；同时，图像的矩阵的奇异值有很好的鲁棒性，所以为了尽可能的提高图像水印抵抗攻击的稳定性，可以把图像的SVD分解应用于DWT变换中。实验结果证明，水印是不可见的，可抵御多种攻击，具有很好的鲁棒性；并且水印提取不需要原图像参与，是盲水印方案。

关键词：数字水印 DWT 奇异值分解 Zigzag置乱

中图分类号：TP309.2 文献标识码：A 文章编号：1003-9082（2012）12-0006-04

互联网的飞速发展，使得大量的数字作品在网上传播，再加上数字作品容易复制修改，造成大量的盗版问题，打击了原作者的创作积极性。近年来数字水印的发展，一定程度上遏制了盗版问题，它通过在被保护的数字对象（如视频、音频、图像）中嵌入某些标志性的秘密信息——水印（watermark）来证明版权归属或者跟踪侵权行为。它通过一定的算法将水印直接嵌到多媒体内容中，同时不影响原内容的使用和价值，并且水印不能被人的感知系统发觉，数字水印必须很难被清除。

数字水印可以是文本，图像，一串数字，当这些水印要求保密时，可以通过将水印置乱来隐藏信息。常用的置乱方法有：Tangram算法、幻方变换、Hilbert曲线变换等等，以上算法较为复杂，计算时间较长。Zigzag置乱虽然简单，但是它本身存在一个致命的缺陷，被置乱的矩阵首端和末端总有几个元素无法移动位置，故本文提出了用m序列改进Zigzag来实现水印图像的置乱。奇异值分解（singular value decomposition，SVD）是一种特殊的矩阵变换。SVD矩阵具有许多优良特性，例如奇异值对矩阵扰动不敏感、奇异值旋转不变性、奇异值比例不变性等等。把SVD应用于图像处理中，当图像受到轻微影响时，奇异值不会发生明显变化；或者当相对较小的奇异值发生扰动时，图像不会出现较大变化。使用小波域水印方法的主要优点在于三个方面：1、在“JPEG2000”有损压缩下水印不会被去除；2、将图像编码研究中关于视觉特性的研究成果用于水印技术；3、有可能提供在压缩域中直接嵌入水印的方法。基于以上考虑，提出了Zigzag变换和SVD结合应用于DWT中。

一、Zigzag置乱

1.Zigzag描述

从矩阵左上角的元素开始（如图1），按照“之”字形的顺序提取元素。提取的元素放入一个一维数组中，再将此数组转换成矩阵。这样原矩阵就经过了Zigzag变换置乱。

图1 Zigzag变换

2.Zigzag的改进

从图1可以看出，无论经过多少次变换，置乱前和置乱后总有那么几个位置的元素无法移动。例如：使用r方式将一维数组换成矩阵的时候，可以看到第1个和第16个元素位置没移动过。而图像的置乱追求所有元素的位置都移动，越乱越好，因此单纯使用Zigzag无法满足置乱要求。

m序列是由带线性反馈的移位寄存器产生的周期最长的一种序列。由反馈移位寄存器的“和”、“异”、“或”门组成的环形计数器即可产生m序列伪随机码。伪随机序列的长度取决于移位寄存器的多少。

m序列的特征方程表示为：

知道此方程后也就知道了反馈多项式，从而求出反馈寄存器的m序列。当n=3时，特征方程为f（x）=1+x+x3，初始状态s为（1，0，0），则接下来的状态为（1，1，0）、（1，1，1）、…（1，0，1）共k=2n-1=7个二进制数，化为十进制为4、6、7、3、5、2、1。这7个数是唯一的且不重复，可以用来作为地址对经Zigzag变换后的一维数组进行置乱。首先将待置乱的一维数组分为m组，每组长度等于寄存器产生的一维数组长度k，然后将每组元素都按照移位寄存器的地址进行排序，得到的新一维数组就是所要的结果。如按上述寄存器产生的7个十进制数值排序，则新的一维数组中每组第一个元素是待置乱数组中每组元素的第4个元素，第二个元素是待置乱数组中每组元素的第6个等等。如果待置乱数组的长度不是移位寄存器十进制数个数的整数倍，则意味着待置乱数组中最后一组元素长度小于移位寄存器产生的数组长度，假设最后一组长度是a，去除寄存器数组中大于a的值，接下来再按上述方法排序。排序公式如下：

Ai（j）=Wi（mseq（j）） j=1，2，3，…，2n-1 i=1，2，3，…，m

其中A是经置乱后的一维数组，W是水印经Zigzag置乱后的信息，mseq是寄存器数组，j是寄存器数组元素下标，i是分组下标。再把上述一维数组转换成矩阵。经改进的Zigzag置乱后可以明显看到1、16的位置变动了，结果如下：

3.水印的Zigzag置乱

设原始水印为W，置乱后得到的水印为Wa，。具体步骤如下：

a） 输入W和迭代次数m。

b） 按的Zigzag变换顺序R对水印图像矩阵W扫描，得到M×N长度的一维数组A。

c） 将一维数组遵循事先得到的m序列的顺序重新排列，得到新的一维数组Aα。

d） 按某种规则r将数字Aα恢复成M×N大小的矩阵B。并令W=B。

e） 重复b）和c）步骤m次，得到置乱后的矩阵Wa。

3.1 算法周期

其中R、r和m以及移位寄存器阶数n和初始状态s可以作为密钥使用，不同的R、r、m、n、s的组合可以产生不同的置乱算法，增加暴力解密的难度。当R、r选用如图1方式，寄存器阶数n=4时不同图片尺寸N下，Zigzag的算法、Arnold算法和BZTMS[4]算法周期如下表1：

由上表可知，改进后的Zigzag算法周期明显大于Arnold以及BZTMS的算法周期，防止暴力破解方面优于Arnold算法和BZTMS算法。

3.2 算法复杂度

根据算法描述，此算法的时间复杂度主要体现在b）、c）、d）、e）步中，其中b）步时间复杂度是O（n），c）步时间复杂度是O（n），d）步的时间复杂度是O（n2），e）步的时间复杂度是O（n3），总的时间复杂度T（n）≈2O（n）+ O（n2）+ O（n3）。与BZTMS的时间复杂度TB（n）≈O（n）+ O（n2）+ O（n3）相比只多了c）步的时间复杂度，当n趋向于无穷大时，T（n）/ TB（n）=常数。

3.3 置乱度及仿真

为了将水印信息保密，对水印信息的预处理是必不可少的。一般来说，水印信息被打乱的程度越高，其安全性就越好。下面使用128×128的lena图像进行置乱，分别使用本算法（寄存器阶数n=4）和Arnold算法。

图2 上层是本算法，下层是Arnold算法，分别置乱1次、3次、8次

从图2可以看出，本算法置乱效果明显优于Arnold算法。一般来说，图像像素点的位置离最初的位置越远，其置乱效果就越好，因此可以用像素移动前后的距离来表示置乱程度。目前还没有统一的对于置乱度的数学公式。此处使用均值和方差的比来定义置乱程度。假设A（i，j）为图像像素点，（i，j）是移动前像素点的坐标，（iα，jα）是经过m次移动后图像的坐标点，那么距离

定义为像素点的移动距离。

整幅图的移动距离的均值为：

整幅图的移动距离方差为：

用均值和方差的比来定义图像置乱程度：

像素移动的均值比较大说明图像移动得分散，像素移动的方差比较小说明图像移动的距离的变化比较集中，二者的比值越大说明图像置乱程度越高。下面通过仿真实验求lena图像（128×128）的置乱程度并和BZTMS算法比较。

表2 改进的Zigzag算法置乱程度SZ（n=4）和BZTMS算法的置乱程度SZ

从上表可以明显看出本算法明显比BZTMS算法置乱度要高。同时随着置乱次数的增加，置乱度没有规律性。具体应用时可以根据不同需要选择合适的置乱次数，这样图像的鲁棒性最好。以上的数据都是在m序列长度n=4的时候得到的，下面分析同一幅图，不同长度的m序列下的置乱度情况，仍以lena为例。

表3 不同长度n的m序列的置乱度

从上表可以m序列长度和置乱次数对置乱度没影响。因此可以放心使用不同长度的m序列，不用担心m序列太短会造成置乱效果不好。

二、图像的奇异值分解（SVD）

设M是一个m×n阶矩阵，其中元素全部属于实数域或复数域。存在一个分解

M=UΣVT

其中U是m×m阶酉矩阵；Σ是半正定m×n阶对角矩阵；而VT，即V的转置，是n×n阶矩阵。这样的分解叫做M的奇异值分解。Σ对角线上的元素是M的奇异值，为了由M唯一确定Σ，常见的做法是将奇异值由大到小排列。

这样Σ就被唯一确定了。λm是M的奇异值，且λ1>λ2>…>>λm，奇异值的个数就等于矩阵M的秩。图像的奇异值具有非常好的稳定性以及对几何失真的不变性，适合用来提高水印的鲁棒性。

三、离散小波分解（DWT）

原始图像经过一级小波分解后得到四个部分，左上为低频近似部分LL，右上为水平方向细节部分HL，左下为垂直方向细节部分LH，右下为对角线细节部分HH，如图3。可以看出，图像的主要能量集中在低频部分，所以进一步的小波分解以及嵌入水印主要是对LL子带进行的。

图3 lena图像一级小波分解各分量系数重构

四、水印的嵌入与提取

本算法中，选用lena图像作为载体A，大小为512×512。peppers图片作为水印W，其大小为128×128。

1.水印的嵌入算法

1.1读入原始Lena图像A，并用haar小波将A进行一级离散小波分解变换，产生LL、LH、HL、HH四个子带。

1.2读入水印图像，并进行m次改进的Zigzag变换，这里取m序列长度n=4，m=10次，R和r的组合方式如图1，得到置乱后的水印W’。

1.3将LL子带进行奇异值分解，获得LL子带的奇异矩阵S以及正交矩阵U和V。

1.4利用加性原则，将置乱后的水印W’嵌入到奇异矩阵S中，得到含有水印的奇异矩阵S’。嵌入算法如下：

S’=S+αW’

其中α是嵌入强度因子。

1.5对S’在进行一次SVD分解，获得奇异矩阵S’’、正交矩阵U’和V’。

1.6利用修改后的子带LL奇异矩阵S’’获得嵌入水印后的子带LL’。

LL’=U×S’’×VT

1.7将上一步得到的子带LL’和第一步得到的子带HL、LH、HH系数进行离散小波反变换，最终得到含有水印的载体图像A’。

2.水印的提取

水印的提取是水印嵌入的反变换，具体做法如下：

2.1将含水印的图像A’进行二维离散小波变换，得到LL’、HL’、LH’、HH’四个子带。

2.2对LL’进行SVD分解，得到S’’。

2.3在S’’上运用SN=U’S’’V’T。

2.4提取置乱后的水印信息：

W1=（S’’-S）/α

2.5按照改进的Zigzag置乱的逆变换恢复水印信息，具体变换是嵌入算法⑵中的逆推。

五、实验结果及分析

仿真实验选用lena（512×512）的图像做为原始载体，peppers（128×128）做为嵌入水印，m序列长度n=4。攻击类型选用JPEG压缩、锐化、中值滤波、高斯/椒盐噪声、旋转、1/4 剪切，并用相关系数NC作为参数判断提取的水印和原始水印是否一致。结果如下：

表4 各种攻击下的相关系数

从上图可以知道，本算法对于常见的攻击具有很好的鲁棒性；甚至在5%压缩的情况下，原始图像已经可以明显看到变形，但是水印仍然可以安全提取，被破坏的程度非常的小。

六、结论

在本文中，针对Zigzag变换的缺点提出了使用m序列进行改进，并用改进后的变换和BTZMS（也是对Zigzag的改进）对比，通过仿真可以得出本算法具有容易实现、周期大、时间复杂度低的优点，其置乱效果较好。同时应用SVD分解，并将水印嵌入到奇异值矩阵中，然后再嵌入到小波分解的低频系数。经过置乱、SVD分解和DWT分解的三重作用，明显提高了水印的鲁棒性和安全性。但是，本算法也有不足的地方，SVD分解嵌入中单纯嵌入到奇异值矩阵的左上角，并没有对嵌入位置进行优化，在小波系数嵌入中同样也没有考虑系数选择的问题，这是以后工作需要注意的。

参考文献

[1]黄兴，张敏瑞.图像置乱程度的研究[J].武汉大学学报（信息科学版）.2008，5： 465-468.

[2]刘钺. 图像置乱的相对置乱度评价方法[J]. 计算机工程与设计.2010，6： 1382-1386.

[3]吴玲玲，张建伟，葛琪. Arnold变换及其逆变换[J]. 微计算机信息.2010，14：206-208.

[4]冀汶莉，张敏瑞，靳玉萍等.基于Zigzag 变换的数字图像置乱算法的研究[J].计算机应用与软件.2009，26（3）： 71-73.

[5]柏森，曹长休.图像置乱程度研究[C].全国第三届信息隐藏学术研讨会论文集.西安： 西安电子科技大学， 2001： 75-81.

[6]宁启智，王涛，张文才. 基于Arnold置乱的图像数字水印算法研究[J].软件导刊.2012，1：144-145

[7]Colle Franco Del，Gomez Juan Carlos. A DWT-SVD based perceptual image fidelity metric for watermaking schemes[C]. Signal Processing and Multimedia Applications （SIGMAP）， Proceedings of the 2010 International Conference on.2010：187-192.

[8]Xianzhen Jin.A digital watermarking algorithm based on wavelet transform and arnold[C].Computer Science and Service System，2011 International Conference on.2011：3806-3809.

[9]刘艳华.基于matlab的移位寄存器法m序列的产生[J].科技视界，2012，2：99-100.

作者简介：张进（1988-）男，湖南湘潭人，硕士研究生，主要研究方向为数字水印应用。

王玲（1962-）女，湖南长沙人，教授，博士生导师，主要研究方向为现代通信与网络技术、信息安全技术、语音图像传输处理技术。