基于Patchwork算法的数字水印嵌入技术
第三章 Patchwork数字水印
3.1 Patchwork算法的概述
“Patchwork”一词原指一种用各种颜色和形状的碎布片拼接而成的布料，它形象地说明了该算法的核心思想，即在图像域上通过大量的模式冗余来实现鲁棒数字水印。Patchwork算法是一种数据量较小、能见度很低、鲁棒性很强的数字水印算法，其生成的水印能够抗图像剪裁、模糊化和色彩抖动。
以隐藏1bit数据为例，Patchwork算法首先通过伪随机数生成器产生两个随机数序列，分别按图像的尺寸进行缩放，成为随机点坐标序列。然后将其中一个坐标序列对应的像素亮度值降低，同时升高另一坐标序列对应的像素亮度。
由于亮度变化的幅度很小，而且随机散布，并不集中，所以不会明显影响图像质量。所选取的伪随机数生成器的种子就是算法的密钥。
3.2 Patchwork算法方法描述
假设算法针对256级线性量化系统，其初始值为0，所有亮度等级均匀分布，各点相互独立。算法叙述如下。
在图像中随机选出两点A和B。设A的亮度为a，B的亮度为b，令
S?a?b
（3-1）
如果大量重复上述过程，则S的期望应为0。但是这并不代表在某一特定条件下S究竟取值多少。这是因为在这种处理中，S的方差是相当高的。S的方差?s2则是反应S的样本围绕其期望值变化的紧密情况。因为a,b是相互独立的，可以用下式计算。
22?s2??a??b
（3-2）
对于均匀分布的有
(255?0)2???5418.75
（3-3）12
2a从而S的标准差为?s2?104。在高斯聚类情况下，一次单独的迭代意义不大。但是，如果我们执行上述过程多次，则会出现不同的情形。如果将这个过程重复次
16
ai,bi和
基于Patchwork算法的数字水印嵌入技术
Si是a,b和S的第i次迭代值，定义Sn如下所示
（1） 一个密钥利用k和伪随即数发生器来选择数据对(ai,bi)。该密钥和随机数发生器的模型仅为收发双方拥有，解码器需要按照和编码器相同的顺序和位置来选择数据对；
（2） 将补丁ai处的亮度值提高?，?的一般取值为256的1%~5%之间； （3） 将补丁bi处的亮度值降低同样的值?； （4） 重复上述步骤n次（n的典型值为10000）。 相应的解码过程只需要两步：
（1）对编码后的图像，用同样的密钥k和伪随机数发生器来选择数据对(ai,bi)； （2）计算s'n
S'n??(ai??)?(bi??)?2n???(ai?bi)i?1i?1nn
（3-4）
当n的值很大时，有E(S'n)?2n?
在不知道密钥k的情况下，随机选取像素对，假设它们是独立同分布的，就有E(S'n)?0 这就表明，只有水印嵌入者可以对水印进行正确检测，攻击者无法判定图像中是否含有水印。
17
基于Patchwork算法的数字水印嵌入技术
第四章 程序设计
4.1 算法的伪C代码描述
Patchwork的水印嵌入算法的具体描述如下： 随机选择N对像素点(ai，bi) lum（）=像素点亮度值 for (i=1;i<=N:i++) (lum（ai），lum（bi）)
=( lum（ai）+1，lum（bi）-1)；
上述算法基于一个基本的假设：给一个值足够大的n值，对于根据伪随机数生成器生成序列选取的图像像素对(ai，bi)，所有像素点ai的亮度平均值与所有像素点bi的亮度平均值非常接近。
当对图像按Patchwork算法嵌入水印后，使得所有像素点ai的亮度平均值增加1，而所有像素点bi的亮度平均值减少1。在水印被嵌入后，这些像素点的亮度变化是能够被准确检测到的。这个假设是必要的且在水印嵌入和检测过程中可得到证实。 水印的检测算法与秘密信息的提取算法不同，不要求原始图像的参与，而仅根据待测图像来鉴别。其思想为：接受者计算n个i值的（lum（ai）-lum（bi））如果这些亮度值之和sum接近于2的整数倍，则此水印可被检测出；但如果这些亮度值的和接近于0，则此水印不能被检测出。根据经验选取一个适当的阀值?来决定数值的近似程度。
算法的伪C代码描述为： int k; float δ ;
for (i=1;i<=N;i++)
sum+=( lum（ai）-lum（bi）);
if ( sum?2k?? ) /*此和值足够接近于2k*/ 存在水印； else
不存在水印；
18
基于Patchwork算法的数字水印嵌入技术
用伪随机置换策略选取足够多的像素点，然后取其前一半构成像素集合{ai},另一半构成像素集合{bi}。标准的Patchwork水印检测算法中，主要的判定式是：
sum?2k??
（4-1）
该式的实际意义是说两组经过调整的像素平均亮度差值应非常接近于2度。本身应该是个比较小的数，但在理论上不应该小于原始图像未加水印前的平均亮度差值。只有当假定原始图像未加水印前的平均亮度差值为0时，才可以无限的将?取小以保证在水印检测中不出现将无水印的图像判断为有水印的图像这一错误。但在实际操作中，这样一来的直接结果就是导致了在水印检测中发生将有水印的图像判断为无水印的图像错误的概率大大增加。所以调整判断方法为
quantity?i?1(ai?bi)?1?lum??
（4-2）
quantity下表对于未加水印的原始lena图像在不同种子控制下{ai}与{bi}的平均亮度差。可以看到，在未加水印前，图像像素的平均亮度差远小于1度（1度=1\\128=0.0078）。在检测中，可以定义判定阀值为0.002?0.005。
表3-1 lena图像在不同种子控制下{ai}与{bi}的平均亮度差 种子key1、key2、key3 {ai}与{bi}的平均亮度差 1983 2001 27 110 806 1121 3253 8734 119 572 421 11 5608 112 413 0.0016581 0.00029515 0.00131 0.00074515 0.0021371 任何基于改变图像像素点位置的攻击都会使水印难以被检测出来。旋转、剪切尺度改变将会毁灭水印，任何基于改变像素点值的攻击很可能也会摧毁水印。所以，嵌入Patchwork水印的图像将容易受到各种综合攻击的影响。为了增加水印的鲁棒性，将像素对扩展为小块的像素区域（如8×8图像块），增加一个区域中的所有像素点的亮度值，相应减少对应区域中所有像素点的亮度值。
19
基于Patchwork算法的数字水印嵌入技术
4.2 试验程序
Patchwork算法的基本原理在上一节已经介绍过了，下面就是基于Patchwork算法的数字水印嵌入及检测的程序。
1.patchwork水印的嵌入 %original为原始图像 %goalfile为保存的结果 %key1、key2、key3为序列密钥 %scale为调整亮度的度数，默认为1
function [psnr,w]=patchwork(original,goalfile,key1,key2,key3,scale) %默认的对亮度的调整为1度 if nargin==5 ascale=1; else
ascale=scale; end
%读取图像信息，并提取亮度分量 image=imread(original); image=double(image)/256; YUV=rgb2ycbcr(image); bright=YUV(:,:,1); %定义两组像素点的个数 [m,n]=size(bright); quantity=floor(m*n/8);
%调用伪随机置换函数，确定信息隐藏位
[row,col]=hashreplacement(bright,2*quantity,key1,key2,key3); %调整亮度
degree=ascale/128; for i=1:quantity
bright(row(i),col(i))=bright(row(i),col(i))+degree;
20