外文翻译英文：基于离散小波变换的数字图像水印

Vol.17 No.2 J. Comput. Sci. DXQ Received March 28, 2000; revised July 9, 2001. Abstract This paper aims at digital watermark which is a new popular research topic recently, presents some methods to embed digital watermark based on modifying frequency coefficients in discrete wavelet transform (DWT) domain. First, the present progress of digital watermark is briefly introduced; after that, starting from Pitass method and discarding his pseudo random number method, the authors use a digital image scrambling technology as preprocessing for digital watermarking. Then the authors discuss how to embed a 1-bit digital image as watermark in frequency domain. Finally another digital watermarking method is given in which 3-D DWT is used to transform a given digital image. Based on the experimental results, it is shown that the proposed methods are robust to a large extent. Keywords discrete wavelet transform, digital image watermarking, digital image scram- bling 1 Introduction The word watermark is well-known. Its earliest use was to record the manufacturers trademark on the product so that authenticity could be clearly established without degrading the aesthetics and utility of the goods. Recently, many electronic publications appear, such as digital audio, image, music and video. Since they could be easily and accurately achieved, transmitted and stored, they become the necessary means for information communication. However, on the other hand, because of the ease that they could be copied many times, illegal copies appear at the same time. The situation causes heavy loss to those authors. In order to protect the correctness and ownership of those electronic publications, digital watermark (hidden copyright messages) and digital fingerprints (hidden serial numbers) has become a very significant topic in recent research. Generally speaking, the latter helps to identify copyright violators, and the former helps to prosecute them. The general mode of watermarking and detection is illustrated in Fig.l, in which the dashed parts are optional parts. 10 ig,oal ImageJ I Watermark I , J Vatermarked . I Original Image Image ,Watermark Key . -J I I Key Fig.1. General flow chart of digital watermarking. This work is supported by the National Natural Science Foundation of China (Grant No.60133020) and the NKBRSF Project of China (Grant No.G1998030608). 130 DING Wei, YAN Weiqi et al. Vol.17 According to the representation, anti-attack ability and requirement of original images and wa- termarks during the detection process, we can classify watermarks as follows: perceptible and im- perceptible, fragile and robust, dependent and independent. Different kinds of watermarks are fit for different applications. In this paper, we will focus on the imperceptible, robust, dependent and independent watermarking technique. The digital image watermarking technique could be approximately classified into two kinds based on their operation-domains: the spaciaI domain and the frequency domain. The typical method which belongs to the spacial domain is LSB (Least Significant Bits) metho:d 23. The principle of this kind of method is to modify the gray-scale of pixels to embed watermarks, basically, at those least significmnt bits since they are inconsequential to human visual system (HVS). Although the result is perfect for HVS, the limitation of its basic principle leads to fragility for lossy compression, requantization or other image processing or attacks. An emblematical algorithm in the frequency domain is the spread spectrum method presented by Cox in 1995 4-6 . The basic principle is based on the time-frequency analysis, spread spectrum measure, and modification in the frequency domain of a given digital image to embed watermarks. This kind of methods commendably used the characteristics of HVS. After some kinds of modulation, the watermark information is embedded into the most significant component of the digital image, by this it could resist many kinds of image processing and potential attacks. Recently, along with rapid increasing focus on digital watermark, many scholars present some different method 7-14. Aiming at the still image compression standard JPEG (Joint Photographer Expert Croup) Is, Barni and Piva 1617, Huang Is, Hsu 19-21, Tang 22 presented some important researches based on discrete cosine transform (DCT). For the popular video compression standards, MPEG (Moving Picture Expert Group) 23 and H.263 24, Dittmann 25 presented two kinds of algo- rithms which are suitable in both spacial and frequency domains. Xia 26 and Zeng 272s, based on discrete wavelet transform (DWT), gave their algorithms, and Zhu 29 presented a method from the point of view of coding. Pitas 133 presented a kind of novel method based on statistical and chaotic views. Wolfgang s,33 and Schyndel 34 defined m-sequence, and then gave their results. Qu 35 gave his interesting method which starts from the graph coloring problem. Kankanhalli 361 gave a content-based method which is related to computer vision. In the area of computer graphics, Praun 371 presented a method in SIGGRAPH99, which watermarked on the 3-D meshes of a model. Ohbuchi did some similar work 3s. Maes presented methods based on geometry transform39; Paute 4 gave results based on fractal compression. Furthermore, Petitcolas I4142, Barnett 431, Scott 44 gave some kinds of methods for attacking. Their studies are very important and necessary for the research of robust watermarking. Chinese researchers did a lot of work at the same time 45-52. We have briefly introduced some development of digital image and video watermarking. We also should notice that many of the early studies are related to plain texts, e.g., Maxemchuk 53 from AT Digimarc Ltd. developed some similar work; NEC Research Institute (America) produced Tiger Mark Data Blade; Informix Software Companys database management system INFORMIX-Universal Server could also be used in digital watermarking; and the coming JPEG2000 is collecting related watermarking proposals. This paper aims at digital watermarking which is a new research topic popular recently, presents some methods to embed digital watermarks based on modifying frequency coefficients in the DWT domain. Firstly, we will briefly introduce the present progress of digital watermarking; after that, we will start from Pitass method, discard his pseudo random number method, and use our digital image scrambling technology as preprocessing for digital watermarking. Then we will discuss how to embed a 1-bit digital image as the watermark in the frequency domain. Finally, we will give another digital watermarking method in which we use 3-D DWT to transform digital images. Based on our experimental results, our methods are robust to a large extent. No.2 Digital Image Watermarking Based on Discrete “vVavelet Transform 131 2 Discrete Wavelet Transform Recently, wavelet analysis is becoming more and more popular in many different research areas and applications. Wavelet analysis has perfect local property, giving nice combination of classical temporal analysis and frequency analysis. Wavelet analysis is used in digital image and video compression and coding, computer vision, pattern recognization, etc. The details about wavelet analysis could be found in 56-60, so we just give a general introduction. Generally, similar to the 1-dimensional case, the 2-dimensional discrete wavelet analysis defines the following scale factor: r y) = r162 (2.1) where r is a 1-dimensional scale factor. Let (x) be a wavelet related to r then the other three wavelets are defined as: eH(.,y) = r e(y) = (2.2) Fig.2(a) illustrates the pyramid decomposing process of a given digital image, where h and g are 1-dimensional filters. The procedure generates frequency coefficients at different resolution levels (Fig.2(c), and the inverse synthesis process is illustrated in Fig.2(b). Column Coiumn ; Row synthesis L2- L2 - HL l Row decomposition synthesis ; L 11, HL o (a) (b) (c) Fig.2. Sketch map of wavelet analysis and synthesis. (a) Analysis. (b) Synthesis. (c) Frequency coefficients distribution. In this paper, we will use the (9-3)-tap filter 6t-63 (Table 2.1) which is recommended by MPEG-4. The reason is that HVS is more sensitive to the horizontal direction than the vertical direction. Table 2.1. (9-3)-tap Wavelet Filter k 0 4-1 =1=2 +4 Low-pass 0.99436891104 0.41984465132 -0-0.06629126073 0.03314563036 High-pass 0.70710678118 -0.35355339059 After we briefly introduce the wavelet analysis and synthesis process for digital images, we know for sure that it is easy to be generalized to the 3-dimensional case for digital video, since digital video can be considered as a sequence of digital images. Similarly, we can do 3-D analysis and synthesis to digital video. Obviously, we should firstly define scale factor r y, z): r y, z) = r162162 (2.3) where r is a 1-D scale factor. This means we have to do analysis along not only x and y directions, bu also temporal axis. Frequency coefficients could be com- posed as a cuboid in Fig.3, in the order of the top-left-front corner of low-pass coef- ficients to the bottom-right-back corner of high-pass coefficients. Higher-pass coefficens Highest-pass coefficients l / Fig.3. 3-D decomposition to digital video. 132 DING Wei, YAN Weiqi et al. Vol.17 3 Applying Improved Pitass Method to DWT Coefficient Domain In this section, we will discuss how to generalize and improve Pitass method from the spacial domain to the wavelet transform frequency domain. 3.1 Basic Pitass Algorithm 133 and Our Improvement Suppose a given digital image F = fij, 0 i M, 0 _ j N which we want to watermark. In the basic Pitass algorithm, digital watermark is a kind of ms defined as: S=(sij, O_iM,O_jN (3.1) where slj E 0, 1, and the numbers of elements 0 and 1 are equal. The watermarking algorithm is as follows: (1) Use S to separate the original image F into two subsets .FA and FB: Fa = fj e F, s = 0, FB = (Aj e F, sj = 1 (3.2) FA and FB satisfy: FAUFs=F, FANFs= (2) Modify each element of FA to generate a new subset F: (3.3) (3) Generate watermarked image F: F = F4 t2 FB (3.4) What we need to notice is that Pitas suggested to use a pseudo random number generator to produce the watermark S, after he did a lot of work on statistical analysis. This means we have to depend on the pseudo random number to separate the original image into two parts with the same size. From the above, it is easy to get the following watermark detection algorithm: (1) Use the original watermark S as the mask to separate the watermarked image F into two subsets: F and F; and m of the elements of F and F respectively; (2) Calculate the average values m A (3) Ifmt and m satisfy: Im -ml Ikl, the conclusion is that the image has been watermarked, otherwise, there is no watermark. If we think about the above algorithm, we can obtain the following results: (1) The algorithm applies to the spacial domain of the image; (2) The pseudo random number is the key to the generation of watermark S, furthermore, its function is important to watermarking the given image, therefore we should do our best to guarantee the average values of subsets FA and FB should be equal; ignature Signatur ignture Signatur l OrS not exlsts (a) (b) Fig.4. Two types of possible errors of Pitass algorithm. (a) Error type L (b) Error type IL (3) Ikl should be a relatively small value, oth- erwise it will cause the quality decrease of the watermarked image; (4) The detection needs the original image F or watermark S. After using Pitass algorithm to watermark many digital images, we get to know Piths did a lot of statistical analysis on the result data, and also find two kinds of different errors may occur. No.2 Digital Image vVatermarking Based on Discrete Vavelet Transform 133 In Fig.4, the left curve in each figure represents the frequency distribution of the difference of two average values of the original subsets FA and FB, and the right one represents the frequency distribution of the difference of two average values of the watermarked subsets F and F. Errors occur at the superposition part of these two curves. The shadow of Fig.4(a) shows error type I which means a watermark is successfully detected although there is no one indeed, and Fig.4(b) shows the error type II which means it is failed to detect a watermark although there really exists one. In fact, these two kinds of errors also occur in some other watermarking algorithms. The simplest solution includes two parts: selecting a good pseudo random number generator which makes the energy difference of those two subsets close to 0; or selecting k such that the absolute value of k is small enough. The detailed information about how to choose k could be found in Pitass papers. Here we still use the core of Pitass method which affects the spacial domain of a given image and modify the gray-scale to represent the watermark, but the difference is that we use scrambling technique 6465 to separate the original image. The pseudo random number generator which plays the key role in Pitass method becomes the optional one in the improved algorithm. The scrambling technique becomes the most important key. After we have scrambled the original image, we distort the image by which we make the energy of the original image distributed uniformly, then we can simply cut the scrambled image into two parts with the same size by the horizontal or vertical central line. It will obviously get the same result as the pseudo random number generator in Pitass algorithm. As illustrated in Fig.5, Fig.5(a) represents the original image, the scrambled image is shown in Fig.5(b), the watermarked scrambled image is shown in Fig.5(c), and the watermarked image is shown in Fig.5(d). In Figs.5(b) and (c), we use a vertical central line to cut the scrambled image into two subsets, the left one is FA and the right one is FB, and in Fig.5(c) for each element in the left subset FA, we increase it by a small value k = 8 which represents the watermark process. By using the improved algorithm, we tested many digital images. The frequency distribution of the difference of the average values of the original two subsets is listed in Fig.6(a). We also list the () (d) . () Fig.5. Example of the improved Pitass basic algorithm. (a) Original image. (b) Scrambled image. (c) Watermarked embedded k = 8. (d) Watermarked image PSNR = 30.09. DIFF DIFF_4 DIFF-8 300 300 300 200 20 200 i00 = IO _ I00 73 v = .73 0 o 2 o O o %0 .% % % % % %0 %0 176 % 5 5 5 5 5 5 () (b) (c) Dev .73 ,n = 9.00 1282.00 Fig.6. Statistical analysis result of the improved Pitass basic algorithm. (a) Original difference. (b) Watermarked difference k - 4. (c) Watermarked difference k = 8. 134 DING Wei, YAN Weiqi et al. Vol.17 difference of the average values of those two subsets of the watermarked images in Figs.6(b) and (c), with k = 4 and k = 8 respectively. From the figure, we can find out that even if we select k = 4, the superposition part still exists. But if we choose k = 8, these two types of errors disappear. 3.2 Applying Improved Pitass Algorithm to DWT Coefficient Domain After doing DWT analysis on digital images, we can obtain the coefficient distribution like Fig.2(c). If we choose subset FA as all the coefficients of sub-band LHo and FB as all the coefficients of sub- band HLo, we can add a shift value A to subset FA, then do DWT synthesis, and as a result the watermarked image appears. The flow chart is as follows: t Input i mage 2 su Watermarked r I Not watermarkedll Y 2 su4 ima Fig.7. Flow chart of the improved Pitass basic algorithm applied to DWT coefficients. () (b) (r (d) Fig.8. Example of the improved Pitass basic algorithm applied to DWT. (a) Original image. (b) DWT coefficients. (c) Modified coefficients. (d) Watermarked image PSNR = 41.04. Fig.8 gives a simple example of applying improved Pitass algorithm to DWT coefficient domain. After testing many digital images, we got two frequency distribution curves of energy differences (Fig.9). Obviously, when we select k -= 8, these two curves are not spliced. / P A=8 Fig.9. Frequency distribution curves of the original and watermarked energy differences. No.2 Digital Image Watermarking Based on Discrete Vcavelet Transform 135 4 Embedding 1-Bit Digital Image as Watermark in DWT Coefficient Do- main In this section, we will discuss how to embed a 1-bit digital image as the watermark in DWT coeff domain. Suppose W(x, y) is a 1-bit watermark image, where W(x, y) e (0, 1 and (x, y) ?9 0, M-l 0, N- 1, both x and y are integers. We can choose two sub-bands So and $1 at the same decomposition layer. Then from those two Sub-bands, we can choose one rectangle from each sub-band with size M N, their energy should satisfy: where S C So and S C $1. For each pixel of W(x, y), (4.1) (1) if W(x,y) = O, we change both S(x,y) and S(x,y) by: s(x,y) = s,(,y) = s(,y) + s(,y) 2 (2) if W(x,y) - 1, we change both S(x,y) and S(x,y) by: , s(, y) + s(, y) So (z, y) = 2 s,(, y) = s(,y) + s(,y) + A 2 After replacing both S and S by S and S in So and 51, we do wavelet synthesis to those coefficients to obtain the watermarked image. () (b) (c) (d) Fig.10. 1-bit watermark image embedding based on DWT. (a) Original image. (b) Original watermark image. (c) Watermarked image PSNR = 34.57. (d) Detected watermark image NR = 0.87%. .,; -., !: , ?9 . () (d) (b) (c) ?9 *“ o. i “ jl (e) (f) Fig.ll. Examples of the robustness of our algorithm. (a) Blured. (b) Irregular cutting. (c) Central cutting. (d) Recovered from (a). (e) Recovered from (b). (f) Recovered from (c). 136 DING Wei, YAN Weiqi et al. Vol.17 To pick up the water