中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 基于完全互補(bǔ)碼與量子進(jìn)化算法的數(shù)字水印方案——蔣天發(fā) 牟群剛

1、基于完全互補(bǔ)碼與量子進(jìn)化算法的數(shù)字水印方案蔣天發(fā)，牟群剛（中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074）摘 要 基于傳統(tǒng)數(shù)字水印算法有嵌入信息量小、嵌入與提取的定位精確度低以及實(shí)現(xiàn)速度慢等特點(diǎn)，人們找到了一種比較有效的優(yōu)化方案量子遺傳算法，而量子進(jìn)化算法在實(shí)際應(yīng)用中容易出現(xiàn)收斂慢、早熟等現(xiàn)象。本文提出了一種基于完全互補(bǔ)碼(CCC)和新量子進(jìn)化算法(QEA)相結(jié)合的數(shù)字水印方案，該方案借鑒量子理論保證收斂較快的同時(shí)兼顧了種群多樣性從而克服早熟的發(fā)生。經(jīng)實(shí)驗(yàn)結(jié)果驗(yàn)證可知，該方案具有快速、靈敏、健壯性以及計(jì)算復(fù)雜度低等優(yōu)點(diǎn)，同時(shí)在收斂性和種群多樣性之間求得平衡，達(dá)到了全局優(yōu)化的效果。關(guān)鍵詞 完全

2、互補(bǔ)碼；量子進(jìn)化算法；量子旋轉(zhuǎn)門；數(shù)字水印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 引言數(shù)字水印12，是指將特定的信息嵌入數(shù)字信號(hào)中，數(shù)字信號(hào)可能是音頻、圖片或是視頻等。若要拷貝有數(shù)字水印的信號(hào)，所嵌入的信息也會(huì)一并被拷貝。數(shù)字水印可分為浮現(xiàn)式和隱藏式兩種，前者是可被看見的水印，其所

7、包含的信息可在觀看圖片或視頻時(shí)同時(shí)被看見或形成干擾。一般來說，浮現(xiàn)式的水印通常包含版權(quán)擁有者的名稱或標(biāo)志，如電視臺(tái)在畫面角落所放置的標(biāo)志，就是浮現(xiàn)式水印的一種。隱藏式的水印是以數(shù)字?jǐn)?shù)據(jù)的方式加入音頻、圖片或視頻中，但在一般的狀況下無法被看見。隱藏式水印的重要應(yīng)用之一是保護(hù)版權(quán)，期望能借此避免或阻止數(shù)字媒體未經(jīng)授權(quán)的復(fù)制和拷貝。人們將水印定義為經(jīng)過電信號(hào)微小改變來嵌入響應(yīng)信號(hào)信息的實(shí)現(xiàn)過程。水印有著各種各樣的應(yīng)用，如身份鑒定、所有權(quán)認(rèn)證、確保真實(shí)性、廣播監(jiān)聽、事物跟蹤、版權(quán)管理與設(shè)備管理3。實(shí)例應(yīng)用如：智能車牌識(shí)別系統(tǒng)中消除圖像干擾的方法4，用于地圖冊(cè)的保護(hù)5，盲數(shù)字水印保護(hù)版權(quán)6等等。水印可以

8、基于空域和頻/轉(zhuǎn)換域分類。不同的轉(zhuǎn)換技術(shù)在水印方面都有了一定得應(yīng)用，如在空域上，人們可以直接“操縱”圖像的像素值。而在頻域上，可以將變換系數(shù)嵌入到宿主圖像中。目前，已有一系列的基于擴(kuò)頻算法的數(shù)字水印技術(shù)定義。如Prasad,M.V.N.K的一篇數(shù)字水印算法論文7就使用了CCC7并將其嵌入到原始的圖像之中，其中可以看出CCC方法要比使用其他擴(kuò)頻序列如m序列和黃金序列等算法更加有效。目前，CCC和QEA8910都不算什么新鮮技術(shù)，然而，將QEA思想應(yīng)用在數(shù)字水印方面的文章是屈指可數(shù)的，即使像基于量子進(jìn)化算法的快速水印算法也存在許多不足之處，文章只是對(duì)當(dāng)前水印速度上進(jìn)行了優(yōu)化而沒有考慮量子進(jìn)化算法的

9、局限性，即沒有實(shí)現(xiàn)快速收斂和防止過早成熟等操作?；谝陨险撌觯疚脑诮榻B了CCC和QEA的原理之后，就將二者有機(jī)結(jié)合起來形成一種新的數(shù)字水印方案，在方案中不但從分發(fā)揮量子進(jìn)化算法的速度上對(duì)傳統(tǒng)算法有優(yōu)化性能的優(yōu)勢(shì)，同時(shí)還對(duì)量子進(jìn)化算法本身用于水印方面的不足之處加以權(quán)衡，最后，在量子進(jìn)化算法的收斂速度和種群多樣性之間追求平衡，以達(dá)到全局優(yōu)化的效果。本文余下部分結(jié)構(gòu)組織為：第2部分簡單介紹了CCC和QEA基本概念后對(duì)水印嵌入過程進(jìn)行了詳細(xì)論述以及流程圖；第3部分給出水印提取過程；第4部分為模擬實(shí)驗(yàn)結(jié)果，第5部分得出實(shí)驗(yàn)結(jié)論。2 水印嵌入本文所提方案算法在水印上使用了具有可再生性、唯一性和不可逆操作

10、等性質(zhì)(正式CCC的這些性質(zhì)，此處才選擇了CCC而沒選擇其他變換技術(shù))的CCC技術(shù)，而在嵌入水印過程中應(yīng)用量子進(jìn)化算法來選擇水印嵌入點(diǎn)，以便將用稀疏矩陣表示的CCC碼嵌入到宿主圖像中。2.1 CCC與QEA簡介2.1.1 CCC一般用序列的相關(guān)函數(shù)來定義補(bǔ)碼。序列。L為序列總長，則可以將Sm的非周期自相關(guān)函數(shù)11定義為 (1)如果Sn的長度也為L，序列Sm和Sn的非周期互相關(guān)函數(shù)則為 (2)定義 如果一對(duì)長度均為L的序列An=(a1,a2,.,an)和Bn=(b1,b2,.,bn)，按照上面自相關(guān)函數(shù)，其對(duì)應(yīng)的自相關(guān)函數(shù)為：， (3)對(duì)任意k若滿足： (4)則認(rèn)為An和Bn是一對(duì)互補(bǔ)碼。同理，

11、設(shè)An,Bn和,是兩個(gè)長度均為n的兩對(duì)互補(bǔ)碼，如果也滿足上述自相關(guān)函數(shù)，則可以說這兩對(duì)序列構(gòu)成了完全互補(bǔ)碼序列?？梢詫CC定義為一組m序列自動(dòng)互補(bǔ)碼，其中的任意一對(duì)都是交叉互補(bǔ)碼。在信號(hào)處理過程中，互相關(guān)是一種確定給定的波形是否是完全相同的或者說并非是基于應(yīng)用到其中的時(shí)間滯后函數(shù)的方法。在長時(shí)間的持續(xù)信號(hào)中，這種方法通常用來搜索更短的信號(hào)。自相關(guān)就是同自身的信號(hào)相關(guān)聯(lián)，在空間領(lǐng)域中，任何數(shù)字圖像的內(nèi)容都能用一數(shù)組元素來表示。相同數(shù)組的副本可視為其相關(guān)函數(shù)。自相關(guān)過程要丟棄相位信息，只返回其指數(shù)，因此是一個(gè)不可逆的操作。2.1.2 QEA目前，量子進(jìn)化算法已然成為了學(xué)術(shù)領(lǐng)域的只能計(jì)算中重要的一

12、員，量子進(jìn)化算法主要針對(duì)實(shí)際問題進(jìn)行優(yōu)化處理，它是量子計(jì)算和進(jìn)化算法相結(jié)合的產(chǎn)物。在量子計(jì)算中，信息的最小單位是量子比特，量子比特同經(jīng)典二進(jìn)制單位比特相比，量子比特不僅可以表示二進(jìn)制能表達(dá)的二進(jìn)制基態(tài)和，還可以表示這兩個(gè)基態(tài)的任意疊加狀態(tài)。單個(gè)量子比特狀態(tài)可表示為：，其中，復(fù)數(shù)和表示滿足歸一化條件的基態(tài)概率幅，即表示測(cè)量值為0的概率，表示測(cè)量值為1的概率910。2.2 水印嵌入具體過程在小波域中利用人類視覺系統(tǒng)可視門限值將宿主圖像的小波系數(shù)量化為量子比特序列，將從水印圖像中提取出來的CCC存入一個(gè)稀疏矩陣?yán)?，通過量子進(jìn)化算法找到最佳嵌入點(diǎn)并將提取并存入稀疏矩陣的CCC嵌入到宿主圖像中。詳細(xì)嵌入

13、步驟如下：2.2.1 提取CCC任何大小為64×64像素的灰度圖像都可以作為水印圖像，在空域上，水印圖像的一維掃描結(jié)果存入數(shù)組序列。Matlab中的CCC碼由函數(shù)normxcorr2()產(chǎn)生，該函數(shù)適用于任何給定信號(hào)/圖像的歸一化互相關(guān)處理，因此，相同的數(shù)組將插入到該函數(shù)中以便獲取CCC，這也是一個(gè)不可逆的操作，顯然，不同的水印圖像會(huì)生成不同的CCC碼。 （1）上述公式中，m和n分別表示水印中一行和一列所含元素的個(gè)數(shù)。結(jié)式矩陣將會(huì)以一個(gè)隨機(jī)的位置映射為一個(gè)新的512×512的稀疏矩陣（SM）。2.2.2 DWT對(duì)將要嵌入水印的宿主圖像進(jìn)行離散小波變換(DWT)12，根據(jù)小波

14、系數(shù)的零樹結(jié)構(gòu)1314性質(zhì)提取原圖特征并選擇出重要的小波系數(shù)。2.2.3 QEA對(duì)重要的小波系數(shù)進(jìn)行量子初始化編碼，利用量子進(jìn)化算法找出最佳信息嵌入位置同時(shí)將位置信息存入密鑰稀疏矩陣(KSM)。以下是量子進(jìn)化算法具體內(nèi)容： 量子染色體QEA中，用量子比特編碼的染色體稱為量子染色體910，如果當(dāng)前種群進(jìn)化到第t代，則此時(shí)的量子種群可以表示為，n為種群大小為進(jìn)化到第t代是第i個(gè)個(gè)體的染色體表達(dá)(初始種群需要按照一定規(guī)則進(jìn)行構(gòu)造)，其具體形式為： (5)其中m表示染色體長度，即量子比特的個(gè)數(shù)。采用量子比特編碼時(shí)，一條染色體表達(dá)了多個(gè)態(tài)的疊加。如，一個(gè)具有3個(gè)量子比特的量子染色體： (6)量子比特染色

15、體q就表示了問題解空間000,001,010,011,100,101,110,111的疊加形式:(7)即上述解空間的解出現(xiàn)的概率依次為1/12,1/4,1/24,1/8,1/12,1/4,1/24,1/8。這里，只有3個(gè)量子比特的量子染色體有解空間的8個(gè)解信息，而傳統(tǒng)進(jìn)化算法中3個(gè)比特位只有最多3個(gè)解信息，顯然，采用量子比特編碼更好地維護(hù)了種群的多樣性。而和是在不斷變化(該變化由后面描述的量子旋轉(zhuǎn)門引起)的，當(dāng)概率靠近0或者1時(shí)，量子染色體就因種群多樣性的減少而逐漸收斂為某一種單一狀態(tài)了，形成問題解空間的確定解，算法收斂。 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相比，僅僅是增加了產(chǎn)生P(t)和進(jìn)化Q(t)這兩步。由Q(t)產(chǎn)生P(t)過程為：在第t代中，每個(gè)長度為m的二進(jìn)制解是利用量子比特

18、幅度進(jìn)行選擇得到的，在二進(jìn)制情況下產(chǎn)生過程為：隨機(jī)產(chǎn)生一個(gè)0,1閉區(qū)間的浮點(diǎn)數(shù)，如果該數(shù)值大于，則相應(yīng)位取0，否則為1；更新Q(t)過程中： 原理上可以采用交叉、變異、隨機(jī)產(chǎn)生概率幅值以及運(yùn)用合適的舉證運(yùn)算產(chǎn)生量子變換門來實(shí)現(xiàn)，由于概率歸一化條件等，這里采用利用了酉矩陣進(jìn)行變換操作的量子旋轉(zhuǎn)門來更新Q(t)，依靠量子旋轉(zhuǎn)門的旋轉(zhuǎn)角度表示量子染色體的變異。 量子旋轉(zhuǎn)門常用的旋轉(zhuǎn)門變換910：， (8)其中為旋轉(zhuǎn)角，為了對(duì)每一位量子比特進(jìn)行更新，可以利用此旋轉(zhuǎn)門變換可設(shè)計(jì)出一種量子旋轉(zhuǎn)門變換(即量子變異，用來加速收斂)：即 (9)式中旋轉(zhuǎn)角由給出，表示當(dāng)前變量的收斂方向(正向收斂，逆向收斂或者無需

19、收斂)，則表示收斂步長，控制收斂速度，二者的值均可在如下表中查詢到，即量子旋轉(zhuǎn)門的旋轉(zhuǎn)角是由以下表格對(duì)應(yīng)的狀態(tài)獲取的。其中和分別表示當(dāng)前的一般解和最優(yōu)解的第i位，則是為當(dāng)前個(gè)體量化而定制的適應(yīng)度函數(shù)，步長可以根據(jù)具體實(shí)驗(yàn)設(shè)置。表1. 量子旋轉(zhuǎn)門的旋轉(zhuǎn)角查詢表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、局部與片面性，容易產(chǎn)生新個(gè)體，同時(shí)避免了早熟現(xiàn)象的產(chǎn)生。量子進(jìn)化規(guī)劃(QEP)與量子進(jìn)化策略(QES)步驟均依照QEA進(jìn)行。2.2.4 生成嵌入水印的圖像依據(jù)嵌入點(diǎn)稀疏矩陣(KSM,此過程中相當(dāng)于私密鑰)將前面提取的CCC嵌入到小波系數(shù)中。最后，將用來表征嵌入點(diǎn)的KSM存入可信第三方數(shù)據(jù)庫中，以供認(rèn)證之用。同時(shí)，將嵌入了水印信息的小波系數(shù)進(jìn)行逆小波變換(IDWT)12，從而形成嵌入水印后的宿主圖像，輸出圖像也不包含任何形式可感知的水印。由于用戶或者說是黑客均無法識(shí)別出水印，因此，這可以認(rèn)為是盲水印嵌入過程。最后，嵌入水印大致過程如下圖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 水印提取對(duì)待檢圖像進(jìn)行像嵌入水印之前那樣的DWT處理，然后將從可信第三方數(shù)據(jù)庫中取出或走秘密通道得到的待檢圖片對(duì)應(yīng)的KSM以及CCC，最后按照如圖2中的流程進(jìn)行待檢圖片CCC

22、的提取，將提取出來的CCC與從可信第三方或走秘密通道得到的CCC進(jìn)行匹配，便可以對(duì)上述待檢圖片進(jìn)行認(rèn)證了。將提取出來的CCC與原有CCC進(jìn)行異或()操作還能根據(jù)DWT變換過程還原出待檢圖片有否局部被攻擊或修改過以及是什么位置被攻擊或修改了。其中，提取水印過程流程如上圖1.b所示。4 結(jié)果實(shí)驗(yàn)過程中，設(shè)置水印圖像為64×64像素大小的灰階圖像，宿主圖像采用512×512像素大小的圖像，獲取CCC陣列過程是不可逆的。對(duì)每個(gè)輸入圖像而言，CCC程序都將生成一個(gè)唯一的CCC碼，CCC的互補(bǔ)圖像如圖2.c所示（顛倒像素的值，即黑白像素相互交換）。原始宿主圖像為512×512

23、(由于成文原因，下面給的要嵌入水印和已嵌入水印的圖并不是原始圖片的大小，而是將原圖按倍數(shù)縮小了)像素大小的位圖文件，然后將CCC碼嵌入到圖像中。圖2.b是一張?jiān)紙D像，圖2.d為嵌入水印后的圖像。a 原水印a. Original watermarkc 水印顛倒c. Inverted watermarkb 原宿主圖b. Original imaged 嵌入水印的圖d. Watermarked image圖2 圖片顯示Fig.2. Image display峰值信噪比（PSNR，這里采用8位采樣點(diǎn)）和均方差（MSE）用來度量圖像的質(zhì)量，一般認(rèn)為，在相同情況下，PSNR越大則說明圖像質(zhì)量就越高。 (

24、10)表2給出了通過不同圖片測(cè)試、無攻擊和壓縮攻擊的PSNR值。表2. 部分實(shí)驗(yàn)結(jié)果 宿主圖像名PSNRLena45.5Baboon43.1Barbara43.85 結(jié)論本文方案使用的是盲水印嵌入615，因此，圖像使用者也不能識(shí)別出外表看起來相同的圖像。該算法將水印的CCC碼信息存儲(chǔ)在圖像的一些特殊區(qū)域，由于這些區(qū)域嵌入CCC信息后人的視覺系統(tǒng)是察覺不到的，這就反過來使得用戶對(duì)圖像的認(rèn)證變得更加簡單可行。實(shí)踐證明，其結(jié)果同其他技術(shù)367所得到的結(jié)果相比較而言，該算法大大提高了水印嵌入的速度，提高了安全性與魯棒性等，總體上達(dá)到了預(yù)期效果。由于目前將量子進(jìn)化算法應(yīng)用于數(shù)字水印方面的研究還極少，因此

25、，后面我們可能會(huì)進(jìn)一步研究這方面的內(nèi)容，比如說量子進(jìn)化算法在視頻水印方面的應(yīng)用、在音頻水印方面的應(yīng)用等等。參 考 文 獻(xiàn)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 劉興，蔣天發(fā).智能車牌識(shí)別系統(tǒng)中消除圖像干擾的方法J，武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版),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 蔣天發(fā)，王理等.基于小波的二值圖像盲數(shù)字水印的研究J,博士之窗.技術(shù)研究，2009.07.008:24-27.7 Channapragada,R.S.R;Prasad,M.V.N.K,Digital wat