基于完全互補碼與量子進化算法的數(shù)字水印方案

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

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

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

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

1 水印嵌入

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

1.1 CCC與QEA描述

1.1.1 完全互補碼

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

(1)

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

(2)

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

(3)

對任意k若滿足：

(4)

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

1.1.2 量子進化算法

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

1.2 水印嵌入具體過程

在小波域中利用人類視覺系統(tǒng)可視門限值將宿主圖像的小波系數(shù)量化為量子比特序列，將從水印圖像中提取出來的CCC存入一個稀疏矩陣里，通過量子進化算法找到最佳嵌入點，將提取并存入稀疏矩陣的CCC嵌入到宿主圖像中.詳細嵌入步驟如下.

1.2.1 提取CCC

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

(5)

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

1.2.2 離散小波變換

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

1.2.3 量子進化算法QEA

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

(6)

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

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

(7)

量子比特染色體q就表示了問題解空間{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個量子比特的量子染色體有解空間的8個解信息，而傳統(tǒng)進化算法中3個比特位只有最多3個解信息，顯然，采用量子比特編碼更好地維護了種群的多樣性.而|α|2和|β|2是在不斷變化的，當概率靠近0或者1時，量子染色體就因種群多樣性的減少而逐漸收斂為某一種單一狀態(tài)了，形成問題解空間的確定解，算法收斂.

②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

③量子旋轉門.常用的旋轉門變換[9,10]如下：

(9)

其中θ為旋轉角，為了對每一位量子比特進行更新，可以利用此旋轉門變換設計出一種量子旋轉門變換即量子變異，用來加速收斂：

(10)

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

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

表1 量子旋轉門的旋轉角查詢表

1.2.4 生成嵌入水印的圖像

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

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

2 水印提取

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

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

3 結果

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

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

峰值信噪比(PSNR，這里采用8位采樣點)和均方差(MSE)用來度量圖像的質量，一般認為，在相同情況下，PSNR越大說明圖像質量越高.

(11)

表2 部分實驗結果

表2給出了通過不同圖片測試的PSNR和實驗速度值，并與純CCC方案進行對照.

圖3 圖片顯示Fig.3 Image display

4 結語

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

參 考 文 獻

[1] 蔣天發(fā),熊祥光,蔣 巍.一類SVD域水印問題分析及其改進算法[J].計算機科學,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ā).智能車牌識別系統(tǒng)中消除圖像干擾的方法[J]. 武漢理工大學學報：交通科學與工程版,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)絡安全,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] 宋強磊,車阿大.量子進化算法在生產調度中的應用綜述[J].計算機應用研究,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].武漢大學學報：工學版, 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.