1、計算機學報2009年5期基于多級離散余弦變換的魯棒數字水印算法項目基金：國家高技術研究發展計劃(863)（No.2003AA144080）；國家自然科學基金資助課題（60772155）；北京市自然科學基金資助項目（4082029）；中國博士后科學基金資助項目（20080440553）肖俊 王穎（中國科學院研究生院，計算與通信工程學院，北京，100049）摘要：本文將多級離散小波變換的“多級”思想引入到離散余弦變換中，并對多級離散余弦變換的特性進行了分析，在此基礎上提出了一種基于多級離散余弦變換的數字水印算法，該算法從多級離散余弦變換系數中選擇適當的位置嵌入水印信息。實驗研究表明本文算法的魯棒性

2、優于常規基于離散余弦變換的數字水印算法，并且他的實時性不受多級變換的影響。此外，本文對多級離散余弦變換中變換系數和變換級數的選擇進行了研究，實驗結果表明合理選擇變換系數進行二級變換可以獲得最佳性能。關鍵詞：數字水印，多級變換，離散余弦變換，魯棒性， 抖動調制1引言早期人們對數字水印的研究基本上是基于時空域的，1993年出現的兩種數字圖像水印實現方案也是空域的，空域算法相對簡單，但是魯棒性等性能相對較差1。1996年Cox等提出了第一個變換域水印算法1,2，之后其良好的性能備受關注，很多研究者開始研究不同變換域的水印算法，包括離散余弦變換（Discrete Cosine Transform,DC

3、T）、離散傅立葉變換（Discrete Fourier Transform,DFT）和離散小波變換（Discrete Wavelet Transform,DWT)等1。隨后，哈德碼變換域、Fresnel變換域和Zernike變換域等變換域下也出現了很多數字水印算法。直到現在，變換域水印算法仍然是研究熱點之一，尤其是魯棒數字水印算法3-7。在眾多變換中，DWT是一種比較特殊的變換方式，它具有多分辨率分析的特點，而小波基和小波變換級數的選擇更是給小波變換域數字水印算法的設計帶來了很大的靈活性和優越性4-9，尤其是變換級數。與DWT相比，DCT、DFT等變換似乎沒有這些特點，將DWT多級變換的思想用

4、于DCT等變換域來設計數字水印算法會產生什么樣的效果？這是一個值得研究的問題。本文針對這一問題展開研究，對載體進行多級DCT之后再嵌入水印信息，從而提出了一種新的魯棒數字水印算法。下面首先分析DCT的能量集中特性，其次介紹基于多級DCT的數字水印算法，然后對算法的性能進行分析，最后給出全文結論。2. DCT的能量集中特性DCT具有很強的“能量集中”特性：大多數自然信號(包括聲音和圖像等)的能量都集中在離散余弦變換后的低頻部分，而且當信號具有接近馬爾科夫過程的統計特性時，離散余弦變換的去相關性接近于K-L變換(Karhunen-Loève變換，它具有最優的去相關性)的性能。以圖像載體為

5、例，在對圖像進行一次DCT變換后，變換系數矩陣左上角的數值較大，這些系數相對較重要，一般稱為低頻系數，常用于嵌入水印信息。圖1以8×8的圖像塊系數為例說明了DCT的能量集中特性，其中圖1(a)顯示的是一個圖像塊的空域系數矩陣，圖1(b)顯示的是對該塊進行一次DCT后獲得的變換域系數。正因為如此，DCT經常被信號處理和圖像處理所使用，常用于對圖像進行有損數據壓縮，同時DCT也倍受數字水印技術的青睞，Cox等2提出的第一個變換域擴頻水印算法就是在DCT域下實現的。與Cox等的第一個變換數字水印算法類似，常規的DCT域數字水印算法僅對載體進行一次DCT變換，然后選擇合適的變換系數嵌入水印信

6、息，如圖2所示，其中嵌入器完成三個工作，一是選擇適合嵌入水印的變換域系數，二是以適當的方式修改選定的變換域系數實現水印信息的嵌入，三是用修改后的系數替換原始變換域系數。（a）8×8的原始數據(b)一次DCT后的數據（c）直接進行二次DCT后的數據（d）低頻系數進行二次DCT后的數據圖1 DCT的能量集中特性示意圖圖2 常規DCT域數字水印嵌入過程對比DWT的多級分解思想，如果對載體進行多級DCT，會得到怎樣的結果？本文對圖1（b）所示的DCT數據進行二次DCT，得到圖1(c)所示的系數矩陣。從圖1(c)可見，直接進行二次DCT并不能對系數進行再次“能量集中”，于是我們選擇圖1(b)左

7、上角4×4大小的低頻系數塊進行二次DCT，得到了圖1(d)所示的系數矩陣，從中可以觀察到能量被再次集中的特性。本文將進行多次DCT變換的操作稱為“多級DCT”，并且對大量數據進行類似圖1所示的實驗得到了相同的結論：合理地進行多級DCT可以使DCT的“能量集中”特性得到更加充分的展示，從而獲得更多數值較大的數據。與多級DWT不同的是，多級DCT并不要求必須針對1/4的級DCT系數進行第級DCT，例如，對256×256的圖像進行一級DCT后，允許選擇一級DCT系數矩陣中左上角128×128的系數塊進行二級DCT，也允許選擇一級DCT系數矩陣中左上角64×64

8、的系數塊進行二級DCT。具體如何選擇，將在第4節展開討論。3. 基于多級DCT的數字水印算法常規的DCT域數字水印算法只對載體數據進行一次DCT，然后以適當的方式修改選擇的變換系數實現水印信息的嵌入。為了充分利用DCT的“能量集中”特性，本文對載體數據進行多級DCT，使得系數進行多次能量集中，然后選擇合適的系數嵌入水印信息。下面介紹基于多級DCT的數字水印算法。基于多級DCT的數字水印算法與常規基于DCT的數字水印算法類似，整個嵌入過程可以分為如下三步：（1）級DCT：首先對載體數據進行一次DCT，其次選擇全部或者部分DCT系數進行第二次DCT，然后進行第三次，第次，直到得到期望的能量集中程度

9、；（2）水印嵌入：在進行次DCT操作之后的系數中，選擇適當的系數以一種預定的嵌入方式嵌入水印信息，嵌入方式可以是典型的量化方式10或擴頻方式2等；（3）級IDCT：根據多級DCT的情況，進行級IDCT得到含水印信息的數據。嵌入過程也可以用圖3進行描述，其中表示第級DCT變換之后的數據，表示對嵌入水印信息后的數據進行級逆DCT（IDCT）所得到的數據。圖3 基于多級DCT的數字水印嵌入過程水印提取過程是嵌入過程的逆過程，首先按照與嵌入過程相同的方式對接收到的數據進行級DCT，然后根據嵌入水印信息時所采用的嵌入方式，選擇相應的解碼器提取水印信息，例如采用擴頻方式嵌入水印信息時可以采用相關檢測解碼2

10、，而采用量化方式嵌入水印信息時相應地采用最小距離解碼10等。4. 基于多級DCT的數字水印算法性能分析在多級DCT中，變換級數和每一級的變換系數都是可以選擇的，本節將分析這些因素對算法性能的影響。4.1 變換系數的選擇根據第二節的結論，對上一級變換所得部分變換系數進行下級變換與對上一級變換所得全部變換系數進行下級變換是有區別的，本小節將比較這兩種方式下算法的性能。比較之前，先給出用于比較的三種算法描述。算法1：對載體做一級DCT之后，選擇絕對值最大的N個DCT系數以抖動調制10的方式嵌入N比特水印信息，這些嵌入位置作為密鑰保存，提取水印信息時要用到。抖動調制的實現方式如圖4所示，其中表示抖動量

11、，對于二值水印信息而言，并且和之中的其中一個可以任意選擇，而另一個要受前一個制約，例如任意選擇時，要根據下式確定10： （1）其中表示量化步長，它需要在魯棒性和不可感知性之間折衷，是基本量化器，即 （2）水印提取過程是嵌入過程的逆過程，首先對待檢測數據進行與嵌入過程相應的一級DCT，并根據密鑰確定可能含有水印信息的系數，然后采用最小距離解碼器解碼，如圖5所示，其中解碼器按照式(3)解碼， （3）其中是可能含有水印信息的數據；與分別是用和對進行抖動的情況下，得到的抖動調制結果。圖4 抖動調制的實現框圖 圖5 最小距離檢測器的提取過程算法2：對載體做一級DCT之后，對所得全部DCT系數進行二級DC

12、T，然后在二級DCT系數中選擇絕對值最大的N個系數以抖動調制的方式嵌入水印信息。算法3：對載體做一級DCT之后，選擇系數矩陣左上角的M×M系數塊進行二級DCT，然后在二級變換系數中選擇最大的N個系數以抖動調制的方式嵌入水印信息。算法2和算法3的提取過程與算法1類似，這里不再詳述。本文對大量圖像進行了測試，得到了相同的結論，出于篇幅的原因，下面僅給出以Lena圖像（如圖6(a)所示）作為載體的實驗結果。實驗中選擇256×256的灰度圖像作為載體，32×32的二值圖像作為水印信息，取N1024，M50，采用峰值信噪比（PSNR）衡量嵌入失真，用誤碼率度量魯棒性。圖6(

13、b)顯示的是原始水印信息，圖6(c),(d)和(e) 分別顯示了算法1、算法2和算法3所得到的含水印圖像，其PSNR均為39.5dB。而表1給出了三種算法的量化步長和用于嵌入水印的最小DCT系數。由圖6可見，三種算法的感知失真均不明顯，但算法2的感知失真略大，因為在這三個算法中，算法2的量化步長較大，而用于嵌入水印的最小系數最小。但另一方面，這也說明用PSNR衡量嵌入失真具有一定的缺陷。 （a）原始載體 （b）原始水印 (c)算法1所得含水印圖像 (d)算法2所得含水印圖像 (e)算法3所得含水印圖像圖6 以Lena圖像為載體的實驗結果表1 三種算法的參數設置算法量化步長用于嵌入水印的最小系數

14、算法177.596算法274.8241.1算法378.6501本文對圖6所示的三幅含水印圖像進行了各種攻擊以比較其魯棒性。圖7顯示了三種算法在不同強度的JPEG壓縮和高斯噪聲攻擊下的誤碼率比較，圖7(a)中橫軸Q表示JPEG壓縮因子，圖7(b)中橫軸Var表示高斯噪聲的方差，縱軸均表示誤碼率（BER）。而表2顯示的是三種算法在其他常見攻擊下的誤碼率比較。由圖7和表2可見，針對大部分攻擊時算法3的魯棒性最優，僅針對放大攻擊時算法2略優于算法3。而算法1和算法2在針對高斯噪聲攻擊時魯棒性相當，針對剪切攻擊時算法2略優于算法1，其他情況下算法2均不及算法1。得到這樣的結果主要有兩方面的原因：首先，這

15、與多級DCT的能量集中特性是對應的：合理地進行多級DCT可以獲得較多數值較大的變換系數，在其中嵌入水印信息可以提高算法的魯棒性；其次，從表1所顯示的參數可見：算法3中的最小系數最大，量化步長也最大，魯棒性理應較好，而算法2中的最小系數雖然大于算法1中的最小系數，但其量化步長最小，魯棒性不能得到提高。因此，要通過多級DCT來提高水印算法的魯棒性，需要選擇合適的系數進行多級DCT才能合理的利用DCT的能量集中特性，否則不能得到預期效果，甚至適得其反。 (a)JPEG壓縮的誤碼率比較 (b)高斯噪聲攻擊的誤碼率比較圖7 三種算法對抗JPEG壓縮和高斯噪聲的誤碼率比較表2 算法1、2和3的魯棒性比較（

16、誤碼率）算法放大4倍縮小1/43×3空域低通濾波4領域平均8領域平均3×3中值濾波1×3中值濾波中央剪切1/8算法10.07620.01270.25100.13770.32010.04880.01860.4893算法20.01270.14160.32520.38090.28320.28320.07710.4802算法30.01560.00100.05860.04390.06350.01560.00780.4756除魯棒性外，算法的實時性在有些場合下也是一個需要考慮的指標，本文對三種算法的實時性進行了比較。在CPU主頻為3.2GHz，內存為1G的奔騰4臺式機上運行三

17、種算法的嵌入算法時，算法1的運行時間為0.219秒，算法2的運行時間為0.296秒，算法3的運行時間為0.203秒。得到這樣的結論并不奇怪，因為算法1和算法2需要在256×256個系數中搜索最大的1024個系數，而算法3只需要在50×50個系數中搜索最大的1024個系數。而且三個算法的運行時間差別并不大，即使改進三個算法使得算法不需要對系數進行排序選擇，三種算法的運行時間也不會有很大的差別。因此多級DCT并不影響算法的實時性，合理設計算法甚至可以提高實時性。4.2變換級數的選擇與DWT域數字水印算法類似，變換級數是基于多級DCT的水印算法中的一個可選項，但是進行多少級DCT

18、比較合適？本小節對此問題進行研究。為了比較，本文設計了基于3級DCT的水印算法，為便于描述，稱之為算法4。算法4的嵌入過程為：對載體做一級DCT之后，選擇系數矩陣左上角的J×J系數塊進行二級DCT，然后在二級變換系數矩陣中選擇左上角M×M的系數塊進行三級DCT，最后在三級DCT系數中選擇最大的N個系數以抖動調制的方式嵌入水印信息。提取過程類似算法1，這里不再詳述。為了與算法1和算法3獲得相同的PSNR，設置算法4中的量化步長為77.7，J100，M50，N1024。在所選擇的用于嵌入水印信息的1024個系數中，最小的系數為22.2。算法4得到的含水印圖像如圖8所示。由圖8，

19、圖6(c)和圖6(e)可見，算法4的感知失真比較大，這主要有兩方面的原因：第一，用于嵌入水印的系數較小，而量化步長較大；第二，進行多級DCT和IDCT操作的過程中會導致一些誤差積累。 圖8 算法4所得含水印圖像本文對算1、算法3和算法4的魯棒性進行了比較，實驗結果如圖9和表3所示。由圖9和表3可見，算法3對幾乎所有攻擊的魯棒性仍然最優，僅在剪切攻擊下略次于算法4。此外，本文還進行了基于更多級的DCT水印算法性能測試，實驗結果均不及2級DCT的情況。因此，合理地進行2級DCT可以使得算法性能達到最優。 (a)JPEG壓縮的誤碼率比較 (b)高斯噪聲攻擊的誤碼率比較圖9 算法1，3和4針對JPEG

20、和高斯噪聲攻擊時的魯棒性比較表3 算法1,3和4的魯棒性比較（誤碼率）算法放大4倍縮小1/43×3空域低通濾波4領域平均8領域平均3×3中值濾波1×3中值濾波中央剪切1/8算法10.07620.01270.25100.13770.33010.04880.01860.4873算法30.01560.00100.05860.04390.06350.01560.00780.4756算法40.05860.02640.20800.12300.24800.06640.00980.41705. 結論本文首先類比多級小波變換的思想，將多級變換的思想引入DCT中，并分析了多級DCT的

21、能量集中特性。為了充分利用DCT的“能量集中”特性，本文對載體數據進行多級DCT使得系數進行多次能量集中，然后選擇合適的系數嵌入水印信息，從而提出了基于多級DCT的數字水印算法。實驗結果表明，與常規基于DCT的水印算法相比，基于多級DCT的水印算法具有更好的魯棒性，而且其實時性不受影響。此外，在變換系數和變換級數的選擇上，實驗研究表明合理選擇變換系數進行二級DCT可以獲得最佳性能。參考文獻1 Wang Ying, Xiao Jun, Wang Yun-hong. Digital Watermarking Principles and Techniques.Beijing, Science Pr

22、ess,2007. (王穎，肖俊，王蘊紅. 數字水印原理與技術. 北京：科學出版社，2007)2 Cox I J, Kilian J, Leighton T, et al. Secure Spread Spectrum Watermarking for Multimedia, IEEE Trans. on Image Processing, 1997, 6(12):1673-16873 CHEN Zhen-Yong,TANG Long,TANG Ze-Sheng, XIONG Zhang. Multi-Watermark Method Toward Goal of Robustness. Ch

23、inese Journal of Computer, 2006,29(11): 2037-2043(陳真勇, 唐龍, 唐澤圣, 熊璋. 以魯棒性為目標的數字多水印研究.計算機學報,2006,29(11): 2037-2043)4 Ge Weiwei1, Cui Zhiming, Wu Jian. Robust gray level watermarking method based on wavelet. Journal of Information and Computational Science. 2008, 5(1): 391-3965 Bi Ning, Sun Qiyu, Huang

24、 Daren, Yang Zhihua, Huang Jiwu. Robust image watermarking based on multiband wavelets and empirical mode decomposition. IEEE Transactions on Image Processing, 2007, 16(8): 1956-19666 Jin C， Peng J X. A robust wavelet-based blind digital watermarking algorithm. Information Technology Journal,2006, 5

25、(2): 358-3637 Hung K M, Wang Y T,Chen G, Yeh C H. A robust watermarking technique using Zernike moment and wavelet packet. WSEAS Transactions on Information Science and Applications, 2007,4(5):909-9158 Wang QiuSheng,Sun ShengHe, Zheng WeiMin. The Fragile Watermark Embedding Algorithm for Digital Aud

26、io Signal.Chinese Journal of Computer, 2002，5（2）：520-525(王秋生，孫圣和，鄭為民. 數字音頻信號的脆弱水印嵌入算法. 計算機學報，2002，5（2）：520-525)9 Huo Fei-fei ,Gao Xin-b. A 3D Wavelet Based Video Watermarking Embedding and Blind Extraction Algorithm. Journal of Electronics & Information Technology,2007,29(2):447-450(霍菲菲,高新波.基于三維

27、小波變換的視頻水印嵌入與盲提取算法. 電子與信息學報,2007,29(2):447-450)10 Chen B, Wornell GW. Quantization index modulation: A class of provably good methods for digital watermarking and information embedding. IEEE Trans. on Information Theory 2001, 47(4):14231443A Robust Digital Watermarking Algorithm Based on Multiple-lev

28、el Discrete Cosine TransformXiao Jun Wang Ying(The Graduated School of the Chinese Academy of Sciences,College of computing & communication Engineering, Bei Jing 10049)Abstract：TheMultiple-levelidea was introduced from Discrete Wavelet Transform to Discrete Cosine Transform, and the properties o

29、f multiple-level Discrete Cosine Transform were analyzed. A digital watermarking algorithm was proposed based on multiple-level Discrete Cosine Transform. In the proposed algorithm, the watermark information was embedded in the selected coefficients of multiple-level Discrete Cosine Transform. Exper

30、imental studies show that the proposed algorithm has better robustness compared with common digital watermarking algorithms based on Discrete Cosine Transform, and its real-time property isnt affected by the multiple-level transform. Besides, the methods of choosing transform coefficients and transf

31、orm levels were studied, and experimental results show that the best performance can be achieved by reasonably choosing transform coefficients for the two-level transform.Keywords： Digital watermark, Multiple-level transform, Discrete Cosine Transform, Robustness, Dither ModulationBackgroundWith the

32、 wide application of digital watermarking in copyright protection and broadcast surveillance, digital watermarking has become one of the hottest research topics. As an embranchment of digital watermarking, robust watermarking has become one of the research hotpots, such as watermarking algorithms in

33、 Discrete Cosine Transform (DCT) domain, Discrete Wavelet Transform (DWT) domain, and Discrete Fourier Transform (DFT) domain. As one of the typical transforms, DCT is widely used in digital watermarking, but usually DCT is used only once when embedding watermarks, and DWT is used many times. How ma

34、ny times of DCT can be used in watermarking is still unknown to us.In this paper, theMultiple-levelidea is introduced from Discrete Wavelet Transform to Discrete Cosine Transform, and we call it multiple-level Discrete Cosine Transform. The properties of multiple-level Discrete Cosine Transform are

35、analyzed compared with the common Discrete Cosine Transform. Then a digital watermarking algorithm is proposed based on multiple-level Discrete Cosine Transform. That is to say, we try to use DCT more than once when watermarking, and the watermarks are embedded in the coefficients of multiple-level

36、Discrete Cosine Transform.The properties of the proposed algorithms are studied. Experimental studies show that the proposed algorithm has better robustness compared with common digital watermarking algorithms based on Discrete Cosine Transform, and its real-time property isnt affected by the multip

37、le-level transform. Besides, the methods of choosing transform coefficients and transform levels are studied, and experimental results show that the best performance can be achieved by reasonably choosing transform coefficients for the two-level transform.This work is supported by National 863 high

38、technology research and development plan of China (No.2003AA144080), National Natural Science Foundation of China (No.60772155), Beijing Natural Science Foundation (No.4082029) and China Postdoctoral Science Foundation (No.20080440553).This work can be used to improve the performance of digital watermarking algorith