张道德 UCAS
第1题 PatchWork 算法
Bender等提出了著名的Patchwork算法，这是一种统计算法，即在一个载体图像中嵌入具有特定统计特性的水印。
1.1算法介绍
假设算法针对256级线性量化系统，其初始值为0，所有亮度等级均匀分布，且个个采样点相互独立。
ab?。在图像中随机选出两点A和B。设A的亮度为a，B的亮度为b，令S?如果大量重复上述过程，则S的期望应为0。但是这并不代表在某一特定条件下S究竟取值多少。这是因为在这种处理中，S的方差是相当高的。S的方差?s2则是反应S的样本围绕其期望值变化的紧密情况。因为a,b是相互独立的，可以用下式计算：
22 ?s2??a??b对于均匀分布的有
(255?0)22?a??5418.75
12从而S的标准差为?s2?104。在高斯聚类情况下，一次单独的迭代意义不大。但是，如果我们执行上述过程多次，则会出现不同的情形。如果将这个过程重复n次，ai、bi和Si 是a、b和S的第i次迭代值，定义Sn??i?1Si??i?1(ai?bi)，则Sn的期望值为0，标准差约为n?104。
对于一幅图像，按照上面的方法计算S10000，如果其偏差高于标准差，则可以在很大程度上确定这并非偶然。
'事实上，当n很大时，下面提到的Sn将呈高斯分布，使得依据偏离值?S'的
nnn少数几倍数值即可以高置信度地指出图像已经人为的修改，也就是嵌入了水印。具体步骤如下：
? 一个密钥利用k和伪随即数发生器来选择数据对(ai,bi)。该密钥和随机数发生器的模型仅为收发双方拥有，解码器需要按照和编码器相同的顺序和位置来选择数据对；
? 将补丁ai处的亮度值提高?，?的一般取值为256的1%~5%之间； ? 将补丁bi处的亮度值降低同样的值?； ? 重复上述步骤n次（n的典型值为10000）。 相应的解码过程只需要两步：
? （1）对编码后的图像，用同样的密钥k和伪随机数发生器来选择数据对
(ai,bi)； ? （2）计算Sn'??i?1(ai??)?(bi??)?2n??i?1(ai?bi)
nn当n的值很大时，有E(Sn')?2n?。
在不知道密钥k的情况下，随机选取像素对，假设它们是独立同分布的，就有E(Sn')?0。这就表明，只有水印嵌入者可以对水印进行正确检测，攻击者无法判定图像中是否含有水印。
1.2 编程实现与分析
1.2.1 Patchwork算法的程序实现与分析
在实验过程中，我们选取n?10000，则标准差Sn?104?10000?10400。我们选取标准差Sn的1.5倍作为阀值 threshold=15600，即
'? 图像中含有水印 if S?threshold?n ?'?? 图像中不含水印 if Sn?threshold首先，我们在原始图像 “elain.bmp” 中运用Patchwork算法嵌入水印，原始图像与嵌入水印后的图像如下图：
图1.1 原始图像与嵌入水印后的图像
在肉眼的观察下，嵌入水印后的图像与原始图像没有什么区别。
'在已知密钥的情况下，计算原始图像的Sn和水印图像Sn，判断是否有水印。结论如下表：
结论 Sn 1416 含有水印 S'n 101266 '在不知密钥的情况下，计算水印图像Sn，判断是否有水印。结论如下表：
结论 S'n 不含有水印 -5217 1.2.2 程序代码
%************************************************************************************
Patchwork水印算法
'①在已知密钥的情况下，计算原始图像的Sn和水印图像Sn的函数
function [Sn]=KnownKey(ImgName,key1,key2)
%在已知密钥的情况下，计算原始图像的Sn 和水印图像的S’n Sn=0;
ImgMatrix=double(imread(ImgName)); %读入bmp位图,存入矩阵ImgMatrix中
[rowNum,colNum]=size(ImgMatrix); %rowNum 图像矩阵的行数；colNum 图像矩阵的列数
rng(key1) % 恢复生成器设置（密钥）
RandomNumber3=randi([0,rowNum*colNum-1],10000,1); %产生一系列[0，rowNum*colNum-1]之间的随机数1；
rng(key2) % 恢复生成器设置（密钥）
RandomNumber4=randi([0,rowNum*colNum-1],10000,1); %产生一系列[0，rowNum*colNum-1]之间的随机数2； for i=1:10000
Sn=Sn+ImgMatrix(floor(RandomNumber3(i)/512)+1,mod(RandomNumber3(i),512)+1)...
-ImgMatrix(floor(RandomNumber4(i)/512)+1,mod(RandomNumber4(i),512)+1); end
%************************************************************************************
'②在不知密钥的情况下，计算水印图像Sn的函数
function [Sn]=UnknownKey(ImgName)
%在未知密钥的情况下，计算水印图像的S’n Sn=0;
ImgMatrix=double(imread(ImgName)); %读入bmp位图,存入矩阵ImgMatrix中
[rowNum,colNum]=size(ImgMatrix); %rowNum 图像矩阵的行数；colNum 图像矩阵的列数
RandomNumber3=randi([0,rowNum*colNum-1],10000,1); %产生一系列[0，rowNum*colNum-1]之间的随机数1；
RandomNumber4=randi([0,rowNum*colNum-1],10000,1); %产生一系列[0，rowNum*colNum-1]之间的随机数2； for i=1:10000