中南民族大学 计算机科学学院 基于完全互补码与量子进化算法的数字水印方案——蒋天发 牟群刚

1、基于完全互补码与量子进化算法的数字水印方案蒋天发，牟群刚（中南民族大学 计算机科学学院，武汉 430074）摘 要 基于传统数字水印算法有嵌入信息量小、嵌入与提取的定位精确度低以及实现速度慢等特点，人们找到了一种比较有效的优化方案量子遗传算法，而量子进化算法在实际应用中容易出现收敛慢、早熟等现象。本文提出了一种基于完全互补码(CCC)和新量子进化算法(QEA)相结合的数字水印方案，该方案借鉴量子理论保证收敛较快的同时兼顾了种群多样性从而克服早熟的发生。经实验结果验证可知，该方案具有快速、灵敏、健壮性以及计算复杂度低等优点，同时在收敛性和种群多样性之间求得平衡，达到了全局优化的效果。关键词 完全

2、互补码；量子进化算法；量子旋转门；数字水印Digital Watermarking Scheme Based on Complete Complementary Code and Quantum Evolutionary AlgorithmJiang Tianfa，Mou Qungang（School of Computer Science，South-Central University for Nationalities，Wuhan 430074，China）Abstract Base on limitation in small embed information,lower accur

3、ate locate of embedding and extraction and tardiness running in traditional digital watermarking algorithm. Some people present an optimized scheme :quantum evolutionary algorithm.but there are some shortcomings such as slow convergence and precocity in practical application of quantum evolutionary

4、algorithm.This paper proposed a Complete Complementary Code(CCC) and Quantum Evolutionary Algorithm(QEA) based digital watermarking scheme to embed a watermark generated by CCC method from watermark image into the original image.We take the advantage of in quantum theory our proposed scheme to guara

5、ntee fast convergency while keeping the population diversity and overcome the occurrence of premature convergence.The experiment shows that proposed scheme is fast than traditionary watermarking algorithm,and more sensitive,lower computational complexity.And at the same time,we pursue the balance po

6、sition between convergence and population diversity to achieve global optimization.Keywords Complete Complementary Code；Quantum Evolutionary Algorithm；Quantum Rotation Gate(QRG)；Digital watermarking1 引言数字水印12，是指将特定的信息嵌入数字信号中，数字信号可能是音频、图片或是视频等。若要拷贝有数字水印的信号，所嵌入的信息也会一并被拷贝。数字水印可分为浮现式和隐藏式两种，前者是可被看见的水印，其所

7、包含的信息可在观看图片或视频时同时被看见或形成干扰。一般来说，浮现式的水印通常包含版权拥有者的名称或标志，如电视台在画面角落所放置的标志，就是浮现式水印的一种。隐藏式的水印是以数字数据的方式加入音频、图片或视频中，但在一般的状况下无法被看见。隐藏式水印的重要应用之一是保护版权，期望能借此避免或阻止数字媒体未经授权的复制和拷贝。人们将水印定义为经过电信号微小改变来嵌入响应信号信息的实现过程。水印有着各种各样的应用，如身份鉴定、所有权认证、确保真实性、广播监听、事物跟踪、版权管理与设备管理3。实例应用如：智能车牌识别系统中消除图像干扰的方法4，用于地图册的保护5，盲数字水印保护版权6等等。水印可以

8、基于空域和频/转换域分类。不同的转换技术在水印方面都有了一定得应用，如在空域上，人们可以直接“操纵”图像的像素值。而在频域上，可以将变换系数嵌入到宿主图像中。目前，已有一系列的基于扩频算法的数字水印技术定义。如Prasad,M.V.N.K的一篇数字水印算法论文7就使用了CCC7并将其嵌入到原始的图像之中，其中可以看出CCC方法要比使用其他扩频序列如m序列和黄金序列等算法更加有效。目前，CCC和QEA8910都不算什么新鲜技术，然而，将QEA思想应用在数字水印方面的文章是屈指可数的，即使像基于量子进化算法的快速水印算法也存在许多不足之处，文章只是对当前水印速度上进行了优化而没有考虑量子进化算法的

9、局限性，即没有实现快速收敛和防止过早成熟等操作。基于以上论述，本文在介绍了CCC和QEA的原理之后，就将二者有机结合起来形成一种新的数字水印方案，在方案中不但从分发挥量子进化算法的速度上对传统算法有优化性能的优势，同时还对量子进化算法本身用于水印方面的不足之处加以权衡，最后，在量子进化算法的收敛速度和种群多样性之间追求平衡，以达到全局优化的效果。本文余下部分结构组织为：第2部分简单介绍了CCC和QEA基本概念后对水印嵌入过程进行了详细论述以及流程图；第3部分给出水印提取过程；第4部分为模拟实验结果，第5部分得出实验结论。2 水印嵌入本文所提方案算法在水印上使用了具有可再生性、唯一性和不可逆操作

10、等性质(正式CCC的这些性质，此处才选择了CCC而没选择其他变换技术)的CCC技术，而在嵌入水印过程中应用量子进化算法来选择水印嵌入点，以便将用稀疏矩阵表示的CCC码嵌入到宿主图像中。2.1 CCC与QEA简介2.1.1 CCC一般用序列的相关函数来定义补码。序列。L为序列总长，则可以将Sm的非周期自相关函数11定义为 (1)如果Sn的长度也为L，序列Sm和Sn的非周期互相关函数则为 (2)定义 如果一对长度均为L的序列An=(a1,a2,.,an)和Bn=(b1,b2,.,bn)，按照上面自相关函数，其对应的自相关函数为：， (3)对任意k若满足： (4)则认为An和Bn是一对互补码。同理，

11、设An,Bn和,是两个长度均为n的两对互补码，如果也满足上述自相关函数，则可以说这两对序列构成了完全互补码序列。可以将CCC定义为一组m序列自动互补码，其中的任意一对都是交叉互补码。在信号处理过程中，互相关是一种确定给定的波形是否是完全相同的或者说并非是基于应用到其中的时间滞后函数的方法。在长时间的持续信号中，这种方法通常用来搜索更短的信号。自相关就是同自身的信号相关联，在空间领域中，任何数字图像的内容都能用一数组元素来表示。相同数组的副本可视为其相关函数。自相关过程要丢弃相位信息，只返回其指数，因此是一个不可逆的操作。2.1.2 QEA目前，量子进化算法已然成为了学术领域的只能计算中重要的一

12、员，量子进化算法主要针对实际问题进行优化处理，它是量子计算和进化算法相结合的产物。在量子计算中，信息的最小单位是量子比特，量子比特同经典二进制单位比特相比，量子比特不仅可以表示二进制能表达的二进制基态和，还可以表示这两个基态的任意叠加状态。单个量子比特状态可表示为：，其中，复数和表示满足归一化条件的基态概率幅，即表示测量值为0的概率，表示测量值为1的概率910。2.2 水印嵌入具体过程在小波域中利用人类视觉系统可视门限值将宿主图像的小波系数量化为量子比特序列，将从水印图像中提取出来的CCC存入一个稀疏矩阵里，通过量子进化算法找到最佳嵌入点并将提取并存入稀疏矩阵的CCC嵌入到宿主图像中。详细嵌入

13、步骤如下：2.2.1 提取CCC任何大小为64×64像素的灰度图像都可以作为水印图像，在空域上，水印图像的一维扫描结果存入数组序列。Matlab中的CCC码由函数normxcorr2()产生，该函数适用于任何给定信号/图像的归一化互相关处理，因此，相同的数组将插入到该函数中以便获取CCC，这也是一个不可逆的操作，显然，不同的水印图像会生成不同的CCC码。 （1）上述公式中，m和n分别表示水印中一行和一列所含元素的个数。结式矩阵将会以一个随机的位置映射为一个新的512×512的稀疏矩阵（SM）。2.2.2 DWT对将要嵌入水印的宿主图像进行离散小波变换(DWT)12，根据小波

14、系数的零树结构1314性质提取原图特征并选择出重要的小波系数。2.2.3 QEA对重要的小波系数进行量子初始化编码，利用量子进化算法找出最佳信息嵌入位置同时将位置信息存入密钥稀疏矩阵(KSM)。以下是量子进化算法具体内容： 量子染色体QEA中，用量子比特编码的染色体称为量子染色体910，如果当前种群进化到第t代，则此时的量子种群可以表示为，n为种群大小为进化到第t代是第i个个体的染色体表达(初始种群需要按照一定规则进行构造)，其具体形式为： (5)其中m表示染色体长度，即量子比特的个数。采用量子比特编码时，一条染色体表达了多个态的叠加。如，一个具有3个量子比特的量子染色体： (6)量子比特染色

15、体q就表示了问题解空间000,001,010,011,100,101,110,111的叠加形式:(7)即上述解空间的解出现的概率依次为1/12,1/4,1/24,1/8,1/12,1/4,1/24,1/8。这里，只有3个量子比特的量子染色体有解空间的8个解信息，而传统进化算法中3个比特位只有最多3个解信息，显然，采用量子比特编码更好地维护了种群的多样性。而和是在不断变化(该变化由后面描述的量子旋转门引起)的，当概率靠近0或者1时，量子染色体就因种群多样性的减少而逐渐收敛为某一种单一状态了，形成问题解空间的确定解，算法收敛。 QEABegin Initialize population Q(t)

16、 using wavelet coefficient above mentioned in detail step 2,initialize value of generation t=0; Test each individual of Q(t),and get status P(t); Evaluate fitness of P(t); Write down best fitness individual and its value of fitness,and find worst individuals; While NOT END doBegint=t+1;test populati

17、on Q(t-1),and get status P(t);evaluate fitness of P(t);update Q(t) using quantum gate G(t),and get child population Q(t+1);write down best fitness individual and its value of fitness;End Output best fitness individuals;End以上描述可知，QEA同EA相比，仅仅是增加了产生P(t)和进化Q(t)这两步。由Q(t)产生P(t)过程为：在第t代中，每个长度为m的二进制解是利用量子比特

18、幅度进行选择得到的，在二进制情况下产生过程为：随机产生一个0,1闭区间的浮点数，如果该数值大于，则相应位取0，否则为1；更新Q(t)过程中： 原理上可以采用交叉、变异、随机产生概率幅值以及运用合适的举证运算产生量子变换门来实现，由于概率归一化条件等，这里采用利用了酉矩阵进行变换操作的量子旋转门来更新Q(t)，依靠量子旋转门的旋转角度表示量子染色体的变异。 量子旋转门常用的旋转门变换910：， (8)其中为旋转角，为了对每一位量子比特进行更新，可以利用此旋转门变换可设计出一种量子旋转门变换(即量子变异，用来加速收敛)：即 (9)式中旋转角由给出，表示当前变量的收敛方向(正向收敛，逆向收敛或者无需

19、收敛)，则表示收敛步长，控制收敛速度，二者的值均可在如下表中查询到，即量子旋转门的旋转角是由以下表格对应的状态获取的。其中和分别表示当前的一般解和最优解的第i位，则是为当前个体量化而定制的适应度函数，步长可以根据具体实验设置。表1. 量子旋转门的旋转角查询表00N(No)0000000Y(Yes)0000001N0000001Y0.02-1+1±1010N0.02-1+1±1010Y0.02+1-10±111N0.02+1-10±111Y0.02+1-10±1 量子交叉种群中所有的染色体均参与交叉，这样可以形成很好的种群多样性，改善了一般交叉的

20、局部与片面性，容易产生新个体，同时避免了早熟现象的产生。量子进化规划(QEP)与量子进化策略(QES)步骤均依照QEA进行。2.2.4 生成嵌入水印的图像依据嵌入点稀疏矩阵(KSM,此过程中相当于私密钥)将前面提取的CCC嵌入到小波系数中。最后，将用来表征嵌入点的KSM存入可信第三方数据库中，以供认证之用。同时，将嵌入了水印信息的小波系数进行逆小波变换(IDWT)12，从而形成嵌入水印后的宿主图像，输出图像也不包含任何形式可感知的水印。由于用户或者说是黑客均无法识别出水印，因此，这可以认为是盲水印嵌入过程。最后，嵌入水印大致过程如下图1.a所示。KSMHost imageDWTQEAWater

21、markCCCEmbeddingWatermarked imageIDWT图1.a 嵌入水印流程图Fig.1.a The flowchart of embedding watermarkWatermarked imageDWTKSMMatch and authenticationCCCOriginal CCC图1.b 提取水印流程图Fig.1.b The flowchart of detecting watermark3 水印提取对待检图像进行像嵌入水印之前那样的DWT处理，然后将从可信第三方数据库中取出或走秘密通道得到的待检图片对应的KSM以及CCC，最后按照如图2中的流程进行待检图片CCC

22、的提取，将提取出来的CCC与从可信第三方或走秘密通道得到的CCC进行匹配，便可以对上述待检图片进行认证了。将提取出来的CCC与原有CCC进行异或()操作还能根据DWT变换过程还原出待检图片有否局部被攻击或修改过以及是什么位置被攻击或修改了。其中，提取水印过程流程如上图1.b所示。4 结果实验过程中，设置水印图像为64×64像素大小的灰阶图像，宿主图像采用512×512像素大小的图像，获取CCC阵列过程是不可逆的。对每个输入图像而言，CCC程序都将生成一个唯一的CCC码，CCC的互补图像如图2.c所示（颠倒像素的值，即黑白像素相互交换）。原始宿主图像为512×512

23、(由于成文原因，下面给的要嵌入水印和已嵌入水印的图并不是原始图片的大小，而是将原图按倍数缩小了)像素大小的位图文件，然后将CCC码嵌入到图像中。图2.b是一张原始图像，图2.d为嵌入水印后的图像。a 原水印a. Original watermarkc 水印颠倒c. Inverted watermarkb 原宿主图b. Original imaged 嵌入水印的图d. Watermarked image图2 图片显示Fig.2. Image display峰值信噪比（PSNR，这里采用8位采样点）和均方差（MSE）用来度量图像的质量，一般认为，在相同情况下，PSNR越大则说明图像质量就越高。 (

24、10)表2给出了通过不同图片测试、无攻击和压缩攻击的PSNR值。表2. 部分实验结果 宿主图像名PSNRLena45.5Baboon43.1Barbara43.85 结论本文方案使用的是盲水印嵌入615，因此，图像使用者也不能识别出外表看起来相同的图像。该算法将水印的CCC码信息存储在图像的一些特殊区域，由于这些区域嵌入CCC信息后人的视觉系统是察觉不到的，这就反过来使得用户对图像的认证变得更加简单可行。实践证明，其结果同其他技术367所得到的结果相比较而言，该算法大大提高了水印嵌入的速度，提高了安全性与鲁棒性等，总体上达到了预期效果。由于目前将量子进化算法应用于数字水印方面的研究还极少，因此

25、，后面我们可能会进一步研究这方面的内容，比如说量子进化算法在视频水印方面的应用、在音频水印方面的应用等等。参 考 文 献1 D. Hunter, Handmade Paper and its Watermarks: A Bibliography,New York: B. Franklin,1967.2 J. Simpson, E. Weiner, Oxford English Dictionary, New York, Oxford Press, 2000.3 I.J.Cox, M.L.Miller,J.A.Bloom,Digital Watermarking,Academic Press,

26、2002. Pp:12-26.4 刘兴，蒋天发.智能车牌识别系统中消除图像干扰的方法J，武汉理工大学学报(交通科学与工程版),2005(10):805-806.5 J Kim,S Hong,Development of Digital Watermarking Technology to Protect Cadastral Map Information,ICIS,Korea,2009,Nov:24-266 蒋天发，王理等.基于小波的二值图像盲数字水印的研究J,博士之窗.技术研究，2009.07.008:24-27.7 Channapragada,R.S.R;Prasad,M.V.N.K,Digital wat