蔣天發(fā)，牟群剛，周 爽

(1中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074；2 中南財(cái)經(jīng)政法大學(xué) 統(tǒng)計(jì)學(xué)與數(shù)學(xué)學(xué)院，武漢 430074)

數(shù)字水印[1,2]可分為浮現(xiàn)式和隱藏式兩種，前者是可視的水印，其包含的信息可在觀看圖片或視頻的同時(shí)被看見(jiàn)或形成干擾.隱藏式的水印是以數(shù)字?jǐn)?shù)據(jù)的方式加入音頻、圖片或視頻中，在一般的狀況下無(wú)法被看見(jiàn).水印有著各種各樣的應(yīng)用，如身份鑒定、所有權(quán)認(rèn)證、確保真實(shí)性、廣播監(jiān)聽(tīng)、事物跟蹤、版權(quán)管理與設(shè)備管理[3].實(shí)例應(yīng)用如：智能車(chē)牌識(shí)別系統(tǒng)中消除圖像干擾的方法[4]，用于地圖冊(cè)的保護(hù)[5]，盲數(shù)字水印保護(hù)版權(quán)[6]等等.

目前，完全互補(bǔ)碼(CCC)[7]和量子進(jìn)化算法 (QEA)[8,9]已經(jīng)得以應(yīng)用，然而，將QEA思想應(yīng)用在數(shù)字水印方面的卻不多見(jiàn)，即使象基于量子進(jìn)化算法的快速水印算法[10]也存在許多不足，本文利用量子進(jìn)化算法對(duì)水印速度進(jìn)行優(yōu)化.基于以上論述，本文在介紹了CCC和QEA的原理之后，將二者有機(jī)結(jié)合起來(lái)形成一種新的數(shù)字水印方案，在方案中不但充分發(fā)揮量子進(jìn)化算法在速度上的優(yōu)勢(shì)(相對(duì)于傳統(tǒng)算法有優(yōu)化性能)，同時(shí)還對(duì)量子進(jìn)化算法本身應(yīng)用于水印方面的不足加以權(quán)衡，最后，在量子進(jìn)化算法的收斂速度和種群多樣性之間尋求平衡，以達(dá)到全局優(yōu)化的效果.

1 水印嵌入

本文所提方案(算法)在水印上使用了具有可再生性、唯一性和不可逆操作等性質(zhì)(正是CCC的這些性質(zhì)，此處才選擇了CCC而沒(méi)有選擇其他變換技術(shù))的CCC技術(shù)，而在嵌入水印過(guò)程中應(yīng)用量子進(jìn)化算法來(lái)選擇水印嵌入點(diǎn)，以便將用稀疏矩陣表示的CCC碼嵌入到宿主圖像中.

1.1 CCC與QEA描述

1.1.1 完全互補(bǔ)碼

一般用序列的相關(guān)函數(shù)來(lái)定義補(bǔ)碼.序列Sm={Sml},l=1,2,…，L.L為序列總長(zhǎng)，可以將Sm的非周期自相關(guān)函數(shù)[11]定義為：

(1)

如果Sn的長(zhǎng)度也為L(zhǎng)，則序列Sm和Sn的非周期互相關(guān)函數(shù)為：

(2)

定義如果一對(duì)長(zhǎng)度均為L(zhǎng)的序列An=(a1,a2,…,an)和Bn=(b1,b2,…,bn)，按照(1)式，其對(duì)應(yīng)的自相關(guān)函數(shù)為：

(3)

對(duì)任意k若滿足：

(4)

可以將完全互補(bǔ)碼(CCC)定義為一組m序列自動(dòng)互補(bǔ)碼，其中的任意一對(duì)都是交叉互補(bǔ)碼.自相關(guān)就是同自身的信號(hào)相關(guān)聯(lián)，在空間領(lǐng)域中，任何數(shù)字圖像的內(nèi)容都能用一數(shù)組元素來(lái)表示.相同數(shù)組的副本可視為其相關(guān)函數(shù).自相關(guān)過(guò)程要丟棄相位信息，只返回其指數(shù)，因此是一個(gè)不可逆的操作.

1.1.2 量子進(jìn)化算法

目前，量子進(jìn)化算法(QEA)已然成為學(xué)術(shù)領(lǐng)域智能計(jì)算中重要的一員，量子進(jìn)化算法主要針對(duì)實(shí)際問(wèn)題進(jìn)行優(yōu)化處理，它是量子計(jì)算和進(jìn)化算法相結(jié)合的產(chǎn)物[12].在量子計(jì)算中，信息的最小單位是量子比特，與經(jīng)典二進(jìn)制單位比特相比，量子比特不僅可以表示二進(jìn)制能表達(dá)的二進(jìn)制基態(tài)|0〉和|1〉，還可以表示這2個(gè)基態(tài)的任意疊加狀態(tài).單個(gè)量子比特狀態(tài)可表示為：|ψ〉=α|0〉+β|1〉，其中，復(fù)數(shù)α和β表示滿足歸一化條件|α|2+|β|2=1的基態(tài)概率幅，即|α|2表示測(cè)量值為0的概率，|β|2表示測(cè)量值為1的概率[9,10].

1.2 水印嵌入具體過(guò)程

在小波域中利用人類(lèi)視覺(jué)系統(tǒng)可視門(mén)限值將宿主圖像的小波系數(shù)量化為量子比特序列，將從水印圖像中提取出來(lái)的CCC存入一個(gè)稀疏矩陣?yán)?，通過(guò)量子進(jìn)化算法找到最佳嵌入點(diǎn)，將提取并存入稀疏矩陣的CCC嵌入到宿主圖像中.詳細(xì)嵌入步驟如下.

1.2.1 提取CCC

任何大小為64×64像素的灰度圖像都可以作為水印圖像，在空域上，水印圖像的一維掃描結(jié)果存入數(shù)組序列wij.Matlab中的CCC碼由函數(shù)normxcorr2()產(chǎn)生，該函數(shù)適用于任何給定信號(hào)/圖像的歸一化互相關(guān)處理，因此，將相同的數(shù)組wij插入到該函數(shù)中以便獲取CCC，這也是一個(gè)不可逆的操作，顯然，不同的水印圖像會(huì)生成不同的CCC碼.

(5)

其中，m和n分別表示水印中一行和一列所含元素的個(gè)數(shù).結(jié)式矩陣Rij將會(huì)以一個(gè)隨機(jī)的位置映射為一個(gè)新的512×512的稀疏矩陣(SM).

1.2.2 離散小波變換

對(duì)將要嵌入水印的宿主圖像進(jìn)行離散小波變換(Discrete Wavelet Transform ，DWT)[13]，根據(jù)小波系數(shù)的零樹(shù)結(jié)構(gòu)性質(zhì)提取原圖特征并選擇出重要的小波系數(shù)[14,15].

1.2.3 量子進(jìn)化算法QEA

對(duì)重要的小波系數(shù)進(jìn)行量子初始化編碼，利用量子進(jìn)化算法找出最佳信息嵌入位置，同時(shí)將位置信息存入密鑰稀疏矩陣(KSM).以下是量子進(jìn)化算法的具體內(nèi)容.

(6)

其中n表示染色體長(zhǎng)度，即量子比特的個(gè)數(shù).

采用量子比特編碼時(shí)，一條染色體表達(dá)了多個(gè)態(tài)的疊加.如，一個(gè)具有3個(gè)量子比特的量子染色體：

(7)

量子比特染色體q就表示了問(wèn)題解空間{000,001,010,011,100,101,110,111}的疊加形式:

(8)

即上述解空間的解出現(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ù)了種群的多樣性.而|α|2和|β|2是在不斷變化的，當(dāng)概率靠近0或者1時(shí)，量子染色體就因種群多樣性的減少而逐漸收斂為某一種單一狀態(tài)了，形成問(wèn)題解空間的確定解，算法收斂.

②QEA程序.

Begin

Initialize population Q(t) 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 it′s value of fitness,and find worst individuals;

While NOT END do

Begin

t=t+1;

test population 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 it′s value of fitness;

End

Output best fitness individuals;

End

③量子旋轉(zhuǎn)門(mén).常用的旋轉(zhuǎn)門(mén)變換[9,10]如下：

(9)

其中θ為旋轉(zhuǎn)角，為了對(duì)每一位量子比特進(jìn)行更新，可以利用此旋轉(zhuǎn)門(mén)變換設(shè)計(jì)出一種量子旋轉(zhuǎn)門(mén)變換即量子變異，用來(lái)加速收斂：

(10)

式中旋轉(zhuǎn)角由s(θi)Δθi給出，s(θi)表示當(dāng)前變量的收斂方向(正向收斂、逆向收斂或者無(wú)需收斂)，Δθi則表示收斂步長(zhǎng)，控制收斂速度，二者的值均可在表1中查詢到，即量子旋轉(zhuǎn)門(mén)的旋轉(zhuǎn)角是由表1對(duì)應(yīng)的狀態(tài)獲取的.其中xi和besti分別表示當(dāng)前的一般解x和最優(yōu)解best的第i位，f(x)=|αi|2+|βi|2則是為當(dāng)前個(gè)體量化而定制的適應(yīng)度函數(shù)，步長(zhǎng)可以根據(jù)具體實(shí)驗(yàn)設(shè)置.

④量子交叉.種群中所有的染色體均參與交叉，這樣可以形成很好的種群多樣性，改善了一般交叉的局部性與片面性，容易產(chǎn)生新個(gè)體，同時(shí)避免了早熟現(xiàn)象的產(chǎn)生.量子進(jìn)化規(guī)劃(Quantum Evolutionary Programming,QEP)與量子進(jìn)化策略(QES)步驟均依照QEA進(jìn)行.

表1 量子旋轉(zhuǎn)門(mén)的旋轉(zhuǎn)角查詢表

1.2.4 生成嵌入水印的圖像

依據(jù)嵌入點(diǎn)稀疏矩陣(KSM)，將前面提取的CCC嵌入到小波系數(shù)中(此過(guò)程中KSM相當(dāng)于私密鑰).最后，將用來(lái)表征嵌入點(diǎn)的KSM存入可信第三方數(shù)據(jù)庫(kù)中，以供認(rèn)證之用.同時(shí)，將嵌入了水印信息的小波系數(shù)進(jìn)行逆小波變換(IDWT)[13]，從而形成嵌入水印后的宿主圖像，輸出圖像也不包含任何形式可感知的水印.由于用戶或者說(shuō)是黑客均無(wú)法識(shí)別出水印，因此，這可以認(rèn)為是盲水印嵌入過(guò)程.嵌入水印大致過(guò)程如圖1所示.

圖1 嵌入水印流程圖Fig.1 The flowchart of embedding watermark

2 水印提取

對(duì)待檢圖像作類(lèi)似嵌入水印之前那樣的DWT處理，然后將從可信第三方數(shù)據(jù)庫(kù)中取出或走秘密通道得到待檢圖片對(duì)應(yīng)的KSM以及CCC，最后按照?qǐng)D2中的流程進(jìn)行待檢圖片CCC的提取，將提取出來(lái)的CCC與從可信第三方或走秘密通道得到的CCC進(jìn)行匹配，便可以對(duì)上述待檢圖片進(jìn)行認(rèn)證了.將提取出來(lái)的CCC與原有CCC進(jìn)行異或(⊕)操作還能根據(jù)DWT變換過(guò)程還原出待檢圖片有否局部被攻擊或被修改過(guò)以及是什么位置被攻擊或修改了.其中，提取水印過(guò)程如圖2所示.

圖2 提取水印流程圖Fig.2 The flowchart of extract watermark

3 結(jié)果

實(shí)驗(yàn)過(guò)程中，設(shè)置水印圖像為64×64像素大小的灰階圖像，宿主圖像采用512×512像素大小的圖像，獲取CCC陣列過(guò)程是不可逆的.對(duì)每個(gè)輸入的圖像而言，CCC程序都將生成一個(gè)唯一的CCC碼，CCC的互補(bǔ)圖像如圖3(c)所示(顛倒像素的值，即黑白像素相互交換).

原始宿主圖像為512×512(由于成文原因，下面給的要嵌入水印和已嵌入水印的圖像并不是原始圖片大小，而是將原圖按倍數(shù)縮小了)像素大小的位圖文件，然后將CCC碼嵌入到圖像中.圖3(b)是一張?jiān)紙D像，圖3(d)為嵌入水印后的圖像，肉眼很難找出二者的不同.

峰值信噪比(PSNR，這里采用8位采樣點(diǎn))和均方差(MSE)用來(lái)度量圖像的質(zhì)量，一般認(rèn)為，在相同情況下，PSNR越大說(shuō)明圖像質(zhì)量越高.

(11)

表2 部分實(shí)驗(yàn)結(jié)果

表2給出了通過(guò)不同圖片測(cè)試的PSNR和實(shí)驗(yàn)速度值，并與純CCC方案進(jìn)行對(duì)照.

圖3 圖片顯示Fig.3 Image display

4 結(jié)語(yǔ)

本文使用的是盲水印嵌入[6]方案，因此，圖像使用者也不能識(shí)別出外表看起來(lái)相同的圖像.該算法將水印的CCC碼信息存儲(chǔ)在圖像的一些特殊區(qū)域，由于這些區(qū)域嵌入CCC信息后，人的視覺(jué)系統(tǒng)是察覺(jué)不到的，這就反過(guò)來(lái)使得用戶對(duì)圖像的認(rèn)證變得更加簡(jiǎn)單可行.實(shí)踐證明，其結(jié)果與其他技術(shù)[3,6,7]所得到的結(jié)果相比較，該算法大大提高了水印嵌入的速度，基于操作不可逆性，提高了安全性與魯棒性等，總體上達(dá)到了預(yù)期效果.由于目前將量子進(jìn)化算法應(yīng)用于數(shù)字水印方面的研究極少，因此，我們將對(duì)這方面的內(nèi)容作進(jìn)一步研究，例如量子進(jìn)化算法在視頻水印、音頻水印方面的應(yīng)用等等.

參 考 文 獻(xiàn)

[1] 蔣天發(fā),熊祥光,蔣 巍.一類(lèi)SVD域水印問(wèn)題分析及其改進(jìn)算法[J].計(jì)算機(jī)科學(xué),2011, 38(10A):62-65.

[2] Simpson J, Weiner E. Oxford English dictionary[M]. New York: Oxford Press, 2000.

[3] Cox I J,Miller M L,Bloom J A. Digital watermarking[M]. Burlington: Academic Press, 2002: 12-26.

[4] 劉 興,蔣天發(fā).智能車(chē)牌識(shí)別系統(tǒng)中消除圖像干擾的方法[J]. 武漢理工大學(xué)學(xué)報(bào)：交通科學(xué)與工程版,2005(10):805-806.

[5] Kim J,Hong S. Development of digital watermarking technology to protect cadastral map information[C]//Proc. Proceedings of the 2nd International Conference on Interaction Sciences: Information Technology, Culture and Human. Seoul: Proc, 2009:24-26.

[6] 蔣天發(fā),王 理,蔣 巍,等.基于小波的二值圖像盲數(shù)字水印系統(tǒng)的研究[J].信息網(wǎng)絡(luò)安全,2009(7):24-27.

[7] Channapragada R S R, Prasad M V N K. Digital watermarking algorithm base on complete complementary code[C]// ICCCNT. Computing Communication & Networking Technologies (ICCCNT). 2012 Third International Conference on Karur. Karur: ICCCNT, 2012：1-4.

[8] 宋強(qiáng)磊,車(chē)阿大.量子進(jìn)化算法在生產(chǎn)調(diào)度中的應(yīng)用綜述[J].計(jì)算機(jī)應(yīng)用研究,2012,5: 1061-1065.

[9] Chen Ming,Quan Huiyun. Quantum-inspired evolutionary algorithm based on estimation of distribution[C]//IEEE. Bio-Inspired Computing: Theories and Applications. Second International Conference on Zhengzhou. Zhengzhou: IEEE Proc, 2007:17-19.

[10] Li Y Y, Jiao L C. Quantum-inspired immune clonal algorithm and its application [C]// IEEE. Proceedings of 2007 International Symposium on Intelligent Signal Processing and Communication Systems. Xiamen: IEEE,2007: 670-673.

[11] Nie Jingnan, Liao Xiaoding. Performance simulation of CDMA system base on complete complementary code[J]. Journal of PLA University of Science and Technology,2006,4:112-116.

[12] 安 玉,蔣天發(fā),吳有林.一種基于量子保密通信及信息隱藏協(xié)議方案[J].武漢大學(xué)學(xué)報(bào)：工學(xué)版, 2012,45(3):394-398.

[13] Ma Bin. Experimental research of image digital watermark based on DWT technology[C]// IEEE. Uncertainty Reasoning and Knowledge Engineering(URKE), 2011 International Conference on Bali. Bali: IEEE URKE, 2011:9-12.

[14] Moinuddin A A. Wavelet based embedded image coding using unified zero-block-zero-tree approach[C]//IEEE. Acoustics,Speech and Signal Processing, 2006. ICASSP 2006 Proceedings. 2006 IEEE International Conference on Toulouse. Toulouse: Proc, 2006:2.

[15] Arivazhagan S. Evaluation of zero tree wavelet coders[C]//ITCC. Information Technology: Coding and Computing [Computers and Communications],2003.Proceedings.ITCC 2003 International Conference. LasVegas: IEEE ITCC, 2003:507-511.