1、1基于改进的 Zigzag 置乱的 DWT 图像水印算法摘 要：信息的隐藏和伪装技术是图像安全方面的重要研究方向。常用的置乱算法较为复杂，为了兼顾算法速度和解密的复杂性，提出使用 m 序列改进 Zigzag 变换来满足上述两个要求。由于在各种图像处理过程中，有损压缩对数字水印的生存打击较大，故使用 DWT 分解来满足抵抗有损压缩的攻击；同时，图像的矩阵的奇异值有很好的鲁棒性，所以为了尽可能的提高图像水印抵抗攻击的稳定性，可以把图像的 SVD 分解应用于 DWT 变换中。实验结果证明，水印是不可见的，可抵御多种攻击，具有很好的鲁棒性；并且水印提取不需要原图像参与，是盲水印方案。 关键词：数字水印
2、 DWT 奇异值分解 Zigzag 置乱 中图分类号：TP309.2 文献标识码：A 文章编号：1003-9082（2012）12-0006-04 互联网的飞速发展，使得大量的数字作品在网上传播，再加上数字作品容易复制修改，造成大量的盗版问题，打击了原作者的创作积极性。近年来数字水印的发展，一定程度上遏制了盗版问题，它通过在被保护的数字对象（如视频、音频、图像）中嵌入某些标志性的秘密信息水印（watermark）来证明版权归属或者跟踪侵权行为。它通过一定的算法将水印直接嵌到多媒体内容中，同时不影响原内容的使用和价值，并且水印不能被人的感知系统发觉，数字水印必须很难被清除。 数字水印可以是文本，
3、图像，一串数字，当这些水印要求保密时，2可以通过将水印置乱来隐藏信息。常用的置乱方法有：Tangram 算法、幻方变换、Hilbert 曲线变换等等，以上算法较为复杂，计算时间较长。Zigzag 置乱虽然简单，但是它本身存在一个致命的缺陷，被置乱的矩阵首端和末端总有几个元素无法移动位置，故本文提出了用 m 序列改进Zigzag 来实现水印图像的置乱。奇异值分解（singular value decomposition，SVD）是一种特殊的矩阵变换。SVD 矩阵具有许多优良特性，例如奇异值对矩阵扰动不敏感、奇异值旋转不变性、奇异值比例不变性等等。把 SVD 应用于图像处理中，当图像受到轻微影响时
4、，奇异值不会发生明显变化；或者当相对较小的奇异值发生扰动时，图像不会出现较大变化。使用小波域水印方法的主要优点在于三个方面：1、在“JPEG2000”有损压缩下水印不会被去除；2、将图像编码研究中关于视觉特性的研究成果用于水印技术；3、有可能提供在压缩域中直接嵌入水印的方法。基于以上考虑，提出了 Zigzag 变换和 SVD 结合应用于 DWT 中。一、Zigzag 置乱 1.Zigzag 描述 从矩阵左上角的元素开始（如图 1） ，按照“之”字形的顺序提取元素。提取的元素放入一个一维数组中，再将此数组转换成矩阵。这样原矩阵就经过了 Zigzag 变换置乱。 图 1 Zigzag 变换 2.Z
5、igzag 的改进 从图 1 可以看出，无论经过多少次变换，置乱前和置乱后总有那么3几个位置的元素无法移动。例如：使用 r 方式将一维数组换成矩阵的时候，可以看到第 1 个和第 16 个元素位置没移动过。而图像的置乱追求所有元素的位置都移动，越乱越好，因此单纯使用 Zigzag 无法满足置乱要求。 m 序列是由带线性反馈的移位寄存器产生的周期最长的一种序列。由反馈移位寄存器的“和” 、 “异” 、 “或”门组成的环形计数器即可产生 m序列伪随机码。伪随机序列的长度取决于移位寄存器的多少。 m 序列的特征方程表示为： 知道此方程后也就知道了反馈多项式，从而求出反馈寄存器的 m 序列。当 n=3
6、时，特征方程为 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 个元素，第二个元素是待置乱数组
7、中每组元素的第 6 个等等。如果待置乱数组的长度不是移位寄存器十进制数个数的整数倍，则意味着待置乱数组中最后一组元素长度小于移位寄存器产生的数组长度，假设最后一组长度是 a，去除寄存器数组中大于 a 的值，接下来再按上述方法排序。排序公式如下： 4Ai（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.水印的 Zigz
8、ag 置乱 设原始水印为 W，置乱后得到的水印为 Wa， 。具体步骤如下： a） 输入 W 和迭代次数 m。 b） 按的 Zigzag 变换顺序 R 对水印图像矩阵 W 扫描，得到 MN 长度的一维数组 A。 c） 将一维数组遵循事先得到的 m 序列的顺序重新排列，得到新的一维数组 A。 d） 按某种规则 r 将数字 A 恢复成 MN 大小的矩阵 B。并令W=B。 e） 重复 b）和 c）步骤 m 次，得到置乱后的矩阵 Wa。 3.1 算法周期 其中 R、r 和 m 以及移位寄存器阶数 n 和初始状态 s 可以作为密钥使用，不同的 R、r、m、n、s 的组合可以产生不同的置乱算法，增加暴力解密
9、的难度。当 R、r 选用如图 1 方式，寄存器阶数 n=4 时不同图片尺寸N 下，Zigzag 的算法、Arnold 算法和 BZTMS4算法周期如下表 1： 由上表可知，改进后的 Zigzag 算法周期明显大于 Arnold 以及 BZTMS 的算法周期，防止暴力破解方面优于 Arnold 算法和 BZTMS 算法。 53.2 算法复杂度 根据算法描述，此算法的时间复杂度主要体现在 b） 、c） 、d） 、e）步中，其中 b）步时间复杂度是 O（n） ，c）步时间复杂度是 O（n） ，d）步的时间复杂度是 O（n2） ，e）步的时间复杂度是 O（n3） ，总的时间复杂度 T（n）2O（n）+
10、 O（n2）+ O（n3） 。与 BZTMS 的时间复杂度TB（n）O（n）+ O（n2）+ O（n3）相比只多了 c）步的时间复杂度，当 n 趋向于无穷大时，T（n）/ TB（n）=常数。 3.3 置乱度及仿真 为了将水印信息保密，对水印信息的预处理是必不可少的。一般来说，水印信息被打乱的程度越高，其安全性就越好。下面使用 128128的 lena 图像进行置乱，分别使用本算法（寄存器阶数 n=4）和 Arnold 算法。 图 2 上层是本算法，下层是 Arnold 算法，分别置乱 1 次、3 次、8次 从图 2 可以看出，本算法置乱效果明显优于 Arnold 算法。一般来说，图像像素点的位
11、置离最初的位置越远，其置乱效果就越好，因此可以用像素移动前后的距离来表示置乱程度。目前还没有统一的对于置乱度的数学公式。此处使用均值和方差的比来定义置乱程度。假设 A（i，j）为图像像素点， （i，j）是移动前像素点的坐标， （i，j）是经过 m 次移动后图像的坐标点，那么距离 定义为像素点的移动距离。 整幅图的移动距离的均值为： 6整幅图的移动距离方差为： 用均值和方差的比来定义图像置乱程度： 像素移动的均值比较大说明图像移动得分散，像素移动的方差比较小说明图像移动的距离的变化比较集中，二者的比值越大说明图像置乱程度越高。下面通过仿真实验求 lena 图像（128128）的置乱程度并和BZT
12、MS 算法比较。 表 2 改进的 Zigzag 算法置乱程度 SZ（n=4）和 BZTMS 算法的置乱程度 SZ 从上表可以明显看出本算法明显比 BZTMS 算法置乱度要高。同时随着置乱次数的增加，置乱度没有规律性。具体应用时可以根据不同需要选择合适的置乱次数，这样图像的鲁棒性最好。以上的数据都是在 m 序列长度 n=4 的时候得到的，下面分析同一幅图，不同长度的 m 序列下的置乱度情况，仍以 lena 为例。 表 3 不同长度 n 的 m 序列的置乱度 从上表可以 m 序列长度和置乱次数对置乱度没影响。因此可以放心使用不同长度的 m 序列，不用担心 m 序列太短会造成置乱效果不好。 二、图像
13、的奇异值分解（SVD） 设 M 是一个 mn 阶矩阵，其中元素全部属于实数域或复数域。存在一个分解 M=UVT 其中 U 是 mm 阶酉矩阵； 是半正定 mn 阶对角矩阵；而 VT，即V 的转置，是 nn 阶矩阵。这样的分解叫做 M 的奇异值分解。 对角线7上的元素是 M 的奇异值，为了由 M 唯一确定 ，常见的做法是将奇异值由大到小排列。 这样 就被唯一确定了。m 是 M 的奇异值，且12m，奇异值的个数就等于矩阵 M 的秩。图像的奇异值具有非常好的稳定性以及对几何失真的不变性，适合用来提高水印的鲁棒性。三、离散小波分解（DWT） 原始图像经过一级小波分解后得到四个部分，左上为低频近似部分L
14、L，右上为水平方向细节部分 HL，左下为垂直方向细节部分 LH，右下为对角线细节部分 HH，如图 3。可以看出，图像的主要能量集中在低频部分，所以进一步的小波分解以及嵌入水印主要是对 LL 子带进行的。 图 3 lena 图像一级小波分解各分量系数重构 四、水印的嵌入与提取 本算法中，选用 lena 图像作为载体 A，大小为 512512。peppers图片作为水印 W，其大小为 128128。 1.水印的嵌入算法 1.1 读入原始 Lena 图像 A，并用 haar 小波将 A 进行一级离散小波分解变换，产生 LL、LH、HL、HH 四个子带。 1.2 读入水印图像，并进行 m 次改进的 Z
15、igzag 变换，这里取 m 序列长度 n=4，m=10 次，R 和 r 的组合方式如图 1，得到置乱后的水印 W。 1.3 将 LL 子带进行奇异值分解，获得 LL 子带的奇异矩阵 S 以及正交矩阵 U 和 V。 81.4 利用加性原则，将置乱后的水印 W嵌入到奇异矩阵 S 中，得到含有水印的奇异矩阵 S。嵌入算法如下： S=S+W 其中 是嵌入强度因子。 1.5 对 S在进行一次 SVD 分解，获得奇异矩阵 S、正交矩阵 U和 V。 1.6 利用修改后的子带 LL 奇异矩阵 S获得嵌入水印后的子带 LL。LL=US VT 1.7 将上一步得到的子带 LL和第一步得到的子带 HL、LH、HH
16、 系数进行离散小波反变换，最终得到含有水印的载体图像 A。 2.水印的提取 水印的提取是水印嵌入的反变换，具体做法如下： 2.1 将含水印的图像 A进行二维离散小波变换，得到 LL、HL 、LH、HH四个子带。 2.2 对 LL进行 SVD 分解，得到 S。 2.3 在 S上运用 SN=USVT。 2.4 提取置乱后的水印信息： W1=（S -S）/ 2.5 按照改进的 Zigzag 置乱的逆变换恢复水印信息，具体变换是嵌入算法中的逆推。 五、实验结果及分析 9仿真实验选用 lena（512512）的图像做为原始载体，peppers（128128）做为嵌入水印，m 序列长度 n=4。攻击类型选
17、用JPEG 压缩、锐化、中值滤波、高斯/椒盐噪声、旋转、1/4 剪切，并用相关系数 NC 作为参数判断提取的水印和原始水印是否一致。结果如下： 表 4 各种攻击下的相关系数 从上图可以知道，本算法对于常见的攻击具有很好的鲁棒性；甚至在 5%压缩的情况下，原始图像已经可以明显看到变形，但是水印仍然可以安全提取，被破坏的程度非常的小。 六、结论 在本文中，针对 Zigzag 变换的缺点提出了使用 m 序列进行改进，并用改进后的变换和 BTZMS（也是对 Zigzag 的改进）对比，通过仿真可以得出本算法具有容易实现、周期大、时间复杂度低的优点，其置乱效果较好。同时应用 SVD 分解，并将水印嵌入到
18、奇异值矩阵中，然后再嵌入到小波分解的低频系数。经过置乱、SVD 分解和 DWT 分解的三重作用，明显提高了水印的鲁棒性和安全性。但是，本算法也有不足的地方，SVD 分解嵌入中单纯嵌入到奇异值矩阵的左上角，并没有对嵌入位置进行优化，在小波系数嵌入中同样也没有考虑系数选择的问题，这是以后工作需要注意的。 参考文献 1黄兴，张敏瑞.图像置乱程度的研究J.武汉大学学报（信息科学版）.2008，5： 465-468. 2刘钺. 图像置乱的相对置乱度评价方法J. 计算机工程与设计.102010，6： 1382-1386. 3吴玲玲，张建伟，葛琪. Arnold 变换及其逆变换J. 微计算机信息.2010，
19、14：206-208. 4冀汶莉，张敏瑞，靳玉萍等.基于 Zigzag 变换的数字图像置乱算法的研究J.计算机应用与软件.2009，26（3）： 71-73. 5柏森，曹长休.图像置乱程度研究C.全国第三届信息隐藏学术研讨会论文集.西安： 西安电子科技大学， 2001： 75-81. 6宁启智，王涛，张文才. 基于 Arnold 置乱的图像数字水印算法研究J.软件导刊.2012，1：144-145 7Colle Franco Del，Gomez Juan Carlos. A DWT-SVD based perceptual image fidelity metric for watermaki
20、ng schemesC. Signal Processing and Multimedia Applications （SIGMAP） ， Proceedings of the 2010 International Conference on.2010：187-192. 8Xianzhen Jin.A digital watermarking algorithm based on wavelet transform and arnoldC.Computer Science and Service System，2011 International Conference on.2011：3806-3809. 9刘艳华.基于 matlab 的移位寄存器法 m 序列的产生J.科技视界，2012，2：99-100. 作者简介：张进（1988-）男，湖南湘潭人，硕士研究生，主要研究方向为数字水印应用。 王玲（1962-）女，湖南长沙人，教授，博士生导师，主要研究方向
