Open access

A Pyramid-Based Watermarking Technique for Digital Images Copyright Protection Using Discrete Wavelet Transforms Techniques

Written By

Awad Kh. Al-Asmari and Farhan A. Al-Enizi

Submitted: April 16th, 2012 Published: February 6th, 2013

DOI: 10.5772/50280

Chapter metrics overview

2,420 Chapter Downloads

View Full Metrics

1. Introduction

With the growth and advances in digital communication technologies, digital images have become easy to be delivered and exchanged. These forms of digital information can be easily copied and distributed through digital media. These concerns motivated significant researches in images watermarking [1]. New progress in digital technologies, such as compression techniques, has brought new challenges to watermarking. Various watermarking schemes that use different techniques have been proposed over the last few years [2-10]. To be effective, a watermark must be imperceptible within its host, easily extracted by the owner, and robust to intentional and unintentional distortions [7]. In specific, discrete wavelet transforms (DWT) has wide applications in the area of image watermarking. This is because it has many specifications that make the watermarking process robust. Some of these specifications are [4]: Space-frequency localization, Multi-resolution representation, Superior Human Visual system (HVS) modeling, and adaptively to the original image. A wavelet-based watermarking technique for ownership verification is presented by Y. Wang [11]. It uses orthonormal filter banks that are generated randomly to decompose the host image and insert the watermark in it.

Another transform technique that is used extensively in image coding is the pyramid transform which was first introduced by Burt and Adelson [12]. It can provide high compression rates and at the same time low complexity encoding. Like the DWT, pyramid transform provides multi-resolution representation of the images. These properties can be used in watermarking to establish a robust data hiding system.

In this chapter, our target is to develop an algorithm using optimal pyramid decomposition technique, and combine it with wavelet decompositions. The algorithm will be used for data hiding in digital images to meet the requirements of imperceptibility, robustness, storage requirements, security, and complexity.

Advertisement

2. Wavelet and Pyramid Transforms

The wavelet transform has the advantage of achieving both spatial and frequency localizations. Wavelet decomposition depends mainly on filter banks, typically the wavelet decomposition and reconstruction structures consist of filtering, decimation, and interpolation. Figure 1. shows two-channel wavelet structure [11].

Figure 1.

Two-channel wavelet transform structure: (a) decomposition, (b) reconstruction.

Where H0, H1, G0, and G1 are the low decomposition, high decomposition, low reconstruction and high reconstruction filters, respectively. For the perfect reconstruction (i.e. x 0 = x 0 ), these filters should be related to each other according to the relations given below:

H 0 ( z ) G 0 ( z ) + H 1 ( z ) G 1 ( z ) = 2 E1
H 0 ( z ) G 0 ( z ) + H 1 ( z ) G 1 ( z ) = 0 E2

Special type of wavelet filters is the orthonormal filters. These filters can be constructed in such a way that they have large side-lobes. This makes it possible to embed more watermarks in the lower bands to avoid the effect of the different images processing techniques. These filter banks can be generated randomly depending on the generating polynomials. For two-channel orthonormal FIR real coefficient filter banks, the following relations shall be applied [11]:

G 0 ( z ) G 0 ( z 1 ) + G 0 ( z ) G 0 ( z 1 ) = 2 E3
G 1 ( z ) = z 2 k + 1 G 0 ( z 1 ) ; k Z E4
H i ( z ) = G i ( z 1 ) , i { 0 ,1 } E5

If P(z) was defined as a polynomial, where

P ( z ) = G 0 ( z ) . G 0 ( z 1 ) E6

Then it can be written as:

P ( z ) = 1 + k = o d d a k z k , a k = a k E7

Depending on the factorization of the polynomials given in equation (7), analysis and synthesis filters can be generated. If k = 5, then we can get four filters each of length six which constitute the two-dimensional analysis and synthesis filters. A decomposition structure can be applied as shown in Figure 2 where sub-band ca1 (the blue square) is chosen for further decompositions.

Figure 2.

Five-level wavelet decomposing structure.

This decomposing structure is applied to King Saud University (KSU book) image of size 512×512 pixels shown in Figure 3. The resulting wavelet sub-bands are shown in Figure 4.

Figure 3.

KSU book image.

Figure 4.

Five-level discrete-wavelet decomposition of KSU book image.

To have a good understanding of the DWT and its effects on the image, it is better to study this decomposition technique in the frequency domain. Frequency spectrum of the original KSU image (the book) is shown in Figure 5, and frequency responses of the four sub-bands that result from the first level decomposition are shown in Figure 6. The spectrums of the four bands show the effect of the filtering process, and the shapes of these filters. From these two figures it can be seen that the spectrum of sub-band ca1 is very close to the shape of the original image because it is only a decimated version of KSU image, whereas the other sub-bands represent the details of the test image. This is the reason why the visual perception is more sensitive to low-frequency variations than to high-frequency variations.

Figure 5.

Spectrum decomposition of KSU image.

Figure 6.

Spectrums of the 1st-level wavelet decomposition sub-bands of KSU image (the book) (a) ca1, (b) ch1, (c) cv1, and (d) cd1.

Pyramid transform was first introduced by Burt and Adelson [12]. It was used mainly for image compression. Like the DWT, pyramid transform provides the multi-resolution structure. If x0(n1,n2) is the original image of size L1×L2 pixels, then its pyramid structure can be done as shown in Figure 7.

Figure 7.

Three-level pyramid decomposition of an image x0(n1,n2).

For decimation by a factor of 2, the image will be filtered using analysis lowpass filter H, and then it will be decimated by a factor of two. This results in an image x1(n1,n2) which is 1/4 of the size of x0(n1,n2) and it is called the first-level image of the pyramid. The second level image x2(n1,n2) can be obtained from x1(n1,n2) by the same process, and this process is completed for the higher levels. The image x1(n1,n2) can be interpolated by a factor of 2 and then filtered using synthesis filter G. The resulting image will be I[x1(n1,n2)]. Where I[.] is the spatial interpolation and filtering operation. The synthesis filter G is a time reversal version of the analysis filter H. The difference (error image) e0(n1,n2) is given by:

e 0 ( n 1 , n 2 ) = x 0 ( n 1 , n 2 )   I [ x 1 ( n 1 , n 2 ) ] E8

This process can be done for the higher levels and we will have the error images e1(n1,n2), e2(n1,n2)etc. The optimizing of the analysis and synthesis filters plays the major role in the perfect reconstruction of the images. For watermarking purposes, random filters will be used. The error images e0, e1, and e2 and the decimated image d3 in space domain are shown in Figures [8-11]. Frequency responses of the error images e0, e1, e2 and decimated image d3 for KSU image (the book) are shown in Figure 12. The frequency response of the original image indicates that most of the energy is concentrated in the low frequency bands, mainly around the zero frequency. High frequency bands contain less energy. This results in limitations on the hiding capacity in these regions. These facts have a great effect in watermarking algorithm. So that normally high-pass bands are avoided in watermarking due to the compression effects, and low-pass bands are also avoided because there will be huge artifacts on the visual quality of the images. To perform the watermarking in the pyramid and the wavelet transforms, two requirements should be met. First, the filter banks should be generated randomly, and the decomposition structure and the bands being used for watermarking must be determined by the owner. This requires the storage of the coefficients that are used for generating these filters, and the decomposition structure of the host image. The second requirement for practical watermarking system is to perform the hiding and the extracting processes in minimum time. Storage requirements as seen before are not that large. The filters can be generated by changing only three coefficients. The running time is related directly to the computational complexity of the pyramid and wavelet transforms.

Figure 8.

Pyramid decomposed KSU book image in space domain, e0 image.

Figure 9.

Pyramid decomposed KSU book image in space domain, e1 image.

Figure 10.

Pyramid decomposed KSU book image in space domain, e2 image.

Figure 11.

Pyramid decomposed KSU book image in space domain, d3 image.

Figure 12.

Frequency responses of the pyramidal components of KSU image (a) e0 image, (b) e1 image, (c) e2 image, (d) decimated image d3.

Computational complexity depends on the number of operations (here multiplications) required to transform an image for a number of levels N. A mathematical derivation of this complexity for pyramid transform is introduced in [13]. The derivation assumes that circular convolution based on fast Fourier transform (FFT) and inverse fast Fourier transforms (IFFT) is used for transforming an image pyramidally. This derivation is summarized below.

For an image x0(n1,n2) of size L1×L2, the number of multiplications needed for the first level x1(n1,n2) with decimation factor M will be

L 1 L 2 log 2 L 1 + L 1 L 2 M log 2 L 2 E9

The first part of equation (9) results from horizontal filtering and the second part is the number of multiplications needed for vertical filtering after decimated by M. Let

K 1 = L 1 log 2 L 1 And K 2 = L 2 log 2 L 2 E10

Then equation (9) can be applied for higher levels. In general, the total number of multiplications needed to get the decimated images x1(n1,n2), x2(n1,n2),…, xN-1(n1,n2) and the difference images e0(n1,n2), e1(n1,n2),…, eN-2(n1,n2) can be written as follows in equations (11) and (12) [13]:

2( L 2 K 1 + L 1 M K 2 )N=1 E11
2[ i=0 N1 L 2 K 1 ( M ) 2i + L 1 K 2 ( M ) 2i+1 L 1 L 2 i=0 N2 ( i+1 ) M+1 ( M ) 2i+3 ]N2 E12

Where N is number of decomposition levels, M is the decimation factor.

The above analysis can be extended to the wavelet transform taking into account that there are four filters for each stage of decompositions and four filters for each stage of reconstructions, and the decimation factor is M = 2. Numbers of multiplications in the wavelet transform are shown in equations (13) and (14).

8( L 2 K 1 + L 1 M K 2 )N=1 E13
8[ i=0 N1 L 2 K 1 ( M ) 2i + L 1 K 2 ( M ) 2i+1 L 1 L 2 i=0 N2 ( i+1 ) M+1 ( M ) 2i+3 ]N2 E14

Our algorithm performance will be measured in terms of peak signal-to-noise ratio (PSNR) between the original image and the watermarked one, and the correlation between the original watermark and the extracted one. False alarm probability Pf is an important aspect in the watermarking systems. It is the probability that the extracted pattern from unwatermarked image or an image watermarked with another pattern, has a correlation with the original watermark greater than the threshold value T, or the probability that the extracted pattern from our watermarked image has a correlation with the original one less than the threshold value. This probability is related to the threshold that is chosen.

The watermark extraction is similar to determining a signal in a noisy environment [11]; since the watermark is of size n by n and the energy of the extracted pattern is normalized before computing the correlation, then, all the possible patterns are lying on a sphere of dimension n2 with radius one. If we define m = n2, the surface area of a m-dimensional sphere of radius ρ is given in equation (15):

S = m V m ρ m 1 E15

Where V m = π m / 2 / ( m / 2 ) ! . All the patterns are assumed to have equal probabilities. Then, the false alarm probability Pf equals to the fraction of two areas A 1 / A . A is the area of the whole sphere, while A 1 contains all points on the sphere whose inner products with the point corresponding to the rotated watermark pattern are larger than T. By rotating the coordinate axes to make the rotated watermark pattern correspond to point [1,0,…,0]T, then, A 1 can be calculated as follows:

A 1 = T 1 ( m 1 ) V m 1 ( 1 x 2 ) m 2 d x 1 x 2 E16

And A = m V m . Therefore, Pf can be calculated as given below [11]:

P f = T 1 ( m 1 ) V m 1 ( 1 x 2 ) m 3 d x m V m E17

As the threshold value of the correlator increases, then the false alarm probability decreases which indicates more reliability. Accepted false alarm probability depends on the requirements, for example a Pf less than 1.35×10-11, corresponds to a correlation threshold value that should be greater than 0.40.

Advertisement

3. Proposed Watermarking Technique

In this section, we introduce our digital image watermarking technique. The technique consists of two stages: first stage is the pyramid transform and the second stage is the DWT. The watermark can be a logo image of size n×n pixels. If x0(n1 ,n2) was the original image of size L1×L2 pixels, then the pyramid structure for three levels can be done as shown in Figure 7, where H and G are the analysis and synthesis filters respectively, e0(n1,n2), e1(n1,n2), and e2(n1,n2) are the error images, and d3 is the decimated image.

Our proposed algorithm will use one of the error images resulting from the pyramid decomposition as a host image for the wavelet watermarking process. That is, the watermark will be inserted in one of the error images using wavelet decomposition. A method for wavelet image watermarking is proposed by Y. Wang [11]. It uses FIR, real-coefficients, randomly generated orthonormal filter banks. The watermark will replace the coefficients of one of the higher sub-bands. Then, the watermarked image will be reconstructed. However, a method for generating optimal pyramid transform filters has been introduced by F. Chin [14]. Therefore, The original image can be pyramidally decomposed using random analysis filters for three levels resulting in three error images e0, e1, and e2 of sizes L1×L2, (L1/2)×(L2/2), and (L1/4)×(L2/4) pixels respectively. Each of these error images can be used for wavelet watermarking process that will be interpreted in three methods.

Method that depends on decomposing e0 will increase the computational complexity. Furthermore, the visual quality of the reconstructed image is found to be affected when the difference image e2 is decomposed. This is due to the fact that the watermark is hidden in the lower frequency bands, which will affect the significant coefficients of the decomposed image. The method that depends on decomposing e1 will provide a trade-off between imperceptibility, robustness, and computational complexity. These observations will be presented in the simulation results. Therefore, e1 can be wavelet decomposed using the analysis filter banks that were generated according to a structure chosen by the owner and guarantees imperceptibility and robustness. A possible structure is shown in Figure 2. Then, the watermark which is 16×16 pixels image will be scrambled, rotated, and then it will replace the black sub-band shown in Figure 13. Wavelet and pyramid reconstructions using the synthesis filters will then be performed. The proposed watermarking algorithm using e1 is shown in Figure 14.

Figure 13.

Wavelet decomposition structure for the error image e1.

Figure 14.

Proposed Pyramid-Wavelet watermarking algorithm using e1.

Advertisement

4. Experimental Results

In this section we demonstrate the performance of our algorithm using our proposed method on grayscale test images of sizes 512×512 pixels, and compare it with method of Y. Wang [11]. The test images are Lena, Baboon, Peppers, Goldhill, and Barbara. The original and watermarked images of Lena are shown in figure 15. Our algorithm performance will be measured in terms of peak signal-to-noise ratio (PSNR) between the original image and the watermarked one, and the correlation between the original watermark and the extracted one. For accepted false alarm probability Pf (i.e. less than 1.35×10-11), correlation threshold value should be greater than 0.40 [11]. For comparison, the average values over the five test images are computed. Table 1 shows the average PSNR and the average correlation values for our method and method of Y. Wang [11]. Our proposed method gives higher average values for both the PSNR and the correlation. This guarantees good perceptual transparency and reliability.

Figure 15.

Original and watermarked images.

Proposed method Y. Wang [11]
Average PSNR 46.52 42.14
Average correlation 0.992 0.986

Table 1.

Average PSNR and correlation of proposed method and Y. Wang method [8].

To see the robustness of our algorithm, the watermarked images were subjected to certain common attacks. These attacks are JPEG compression, median filters, histogram equalization, zero mean 100 variance Gaussian noise, and 1% salt-and-pepper noise. The average compression over the five test images is 0.328 bpp. Table 2 shows the average correlation values for the five test images with these attacks. It can be seen that our proposed algorithm provides higher values with two of the attacks. These attacks are the median filter and the JPEG compression. However, for the additive noise and the histogram equalization, it gives approximately the same average values. Importance of this result is that median filters and JPEG attacks are among the worst attacks in watermarking systems. They are able to destroy many watermarking systems without affecting the visual quality. Surviving them gives the used algorithm high robustness.

The other important advantage of our proposed algorithm is the savings in the computational complexity. Normally, DWT and pyramid transform use the fast Fourier transform (FFT). Computational complexity depends on the number of multiplications being performed [13]. Table 3 shows the number of multiplications and savings for our method and method of Y. Wang [11]. It can be shown that our method achieves a saving of 54%. This is due to the fact that the wavelet decomposition was performed on a smaller image e1 of size 256×256 pixels rather than performing it on the original image of 512×512 pixels.

Type of Attack Average Correlations
Proposed method Y. Wang [11]
JPEG compression (average: 0.328 bpp) 0.602 0.562
Median filter 0.909 0.430
Histogram equalization 0.965 0.963
Gaussian noise 0.967 0.974
1% Salt-and-pepper noise 0.948 0.956

Table 2.

Average correlations of proposed method and Y. Wang method [11] upon some common attacks.

Hiding technique Proposed method Y. Wang [11]
Number of multiplications 16,687,104 36,347,904
Savings in computational complexity (%) 54.09 0

Table 3.

Computational complexity and savings with respect to method of Y. Wang [11].

Advertisement

5. Application on Digital Color Images

The proposed Pyramid-Based Watermarking Technique can also be applied on the digital color images. In this section, we demonstrate the performance of our algorithm using the proposed method on standard RGB color test images of sizes 512×512 pixels and the watermark was inserted in the green component. The test images are Lena, Baboon, and Peppers. The original and watermarked images of Lena are shown in Figure 16. Table 4 shows the correlation values of the watermarking process for the images. To ensure the robustness of our method, it was subjected to attacks of Gaussian noise of zero mean and variance of 100, 1% salt-and-pepper noise, and JPEG compression. Tables 5 and 6 show the correlation values when adding the two types of noise. It can be seen that our proposed algorithm is robust to these kinds of noise. Table 7 shows the correlation values when our watermarked images were compressed using JPEG compression at quality factors of 50,60,70,80, and 90 to different bit rates. It can be seen that for an average bit rate of 1.67 bpp, the normalized correlation is 0.50. This value is above the threshold mentioned in reference [10] which is 0.23. So, our algorithm is robust against JPEG compression at quality factors greater than 50.

Figure 16.

a). The original standard 512×512 RGB color image. (b) Watermarked color image.

Image Correlation
Lena 1
Baboon 1
Peppers 1

Table 4.

Correlation values of watermarking process of color images using our proposed method.

Image Correlation
Lena 0.90
Baboon 0.98
Peppers 0.77

Table 5.

Correlation values of watermarking process of color images using our proposed method upon attack of Gaussian noise.

Image Correlation
Lena 0.91
Baboon 0.98
Peppers 0.70

Table 6.

Correlation values of watermarking process of color images using our proposed method upon attack of 1% salt-and-pepper noise.

Image Quality
factor
Bitrate
(bpp)
CorrelationProposed method
Lena 50 0.74 0.29
60 0.85 0.30
70 1.03 0.41
80 1.34 0.44
90 2.11 0.74
Baboon 50 1.54 0.50
60 1.78 0.54
70 2.13 0.65
80 2.71 0.75
90 4.06 0.91
Peppers 50 0.80 0.23
60 0.93 0.29
70 1.13 0.35
80 1.47 0.42
90 2.45 0.67
Average 1.67 0.50

Table 7.

Correlation values of watermarking process of color images using our proposed method upon attack of JPEG compression.

Advertisement

6. Conclusions

In this chapter, we proposed a pyramid-wavelet watermarking technique. The technique uses the spatial-frequency properties of the pyramid and wavelet transforms to embed a watermark in digital images. From the results, the proposed algorithm achieved a trade-off between the perceptual invisibility and the robustness. However, it enhanced the performance of the wavelet-based watermarking algorithm of Y. Wang [11] in many aspects such as compression and median filter attacks. The security issues were addressed extensively in the design, where the filter banks being used are generated randomly. The owner has full control on the filter banks, the decomposition structure, and the band being used for embedding. On the other hand, the watermark can be also controlled by the owner; he can rotate and scramble it. The proposed algorithm provided savings in the computational complexity which is a significant aspect in watermarking systems design. The filters being used for pyramid and wavelet transform should be optimized for perfect reconstruction, and this will help in designing robust watermarking systems to get the best performance.

References

  1. 1. Langelaar G. C. Setyawan I. Lagendijk R. L. 2000 Watermarking digital image and video data. A state-of-the-art overview IEEE Signal Processing Magazine 17 20 46 Sept.
  2. 2. Aboofazeli M. Thomas G. Moussavi Z. 2004 A wavelet transform based digital image watermarking scheme Proc. IEEE CCECE 2 823 826 May
  3. 3. Al-Asmari Awad Kh. Al-Enizi Farhan A. 2006 A Pyramid-Based Watermarking Technique for Digital Images Ownership Verification First National Information Technology Symposium (NITS 2006), Feb. 5-7 King Saud University, Saudi Arabia
  4. 4. Meerwald P. Uhl A. 2001 A survey of wavelet-domain watermarking algorithms Proc. SPIE 4314 505 516
  5. 5. Mong-Shu L. 2003 Image compression and watermarking by wavelet localization Intern. J. Computer Math. 80 4 401 412
  6. 6. Al-Enizi Farhan A. Al-Asmari Awad Kh. 2006 A Pyramid-Based Watermarking Technique for Secure Fingerprint Images Exchange. The International Conference on Computer & Communication 2006 (ICCC06), International Islamic University Malaysia.
  7. 7. Kundur D. Hatzinakos D. 1998 Digital watermarking using multiresolution wavelet decomposition Proc. IEEE ICASSP 5 2969 2972 May
  8. 8. Guzman V. H. Miyatake M. N. Meana H. M. P. 2004 Analysis of a wavelet-based watermarking algorithm Proc. IEEE CONIELECOMP 283 287
  9. 9. Al-Asmari Awad Kh. Al-Enizi Farhan A. 2009 Watermarking Technique for Digital Color Images Copyright Protection. International Conference of Computing in engineering, science and information 2009 (HPCNCS-09) Florida, USA.
  10. 10. Shih-Hao W. Yuan-Pei L. 2004 Wavelet tree quantization for copyright protection watermarking IEEE Transactions on Image Processing 13 154 165 Feb.
  11. 11. Wang Y. Doherty J. F. Van Dyck R. E. 2002 A wavelet-based watermarking algorithm for ownership verification of digital images IEEE Trans. Image Processing 11 77 88
  12. 12. Burt P. J. Adelson E. H. 1983 The Laplacian pyramid as a compact image code IEEE Trans. Communication 31 532 540
  13. 13. Al-Asmari A. Kh. 1995 Optimum bit rate pyramid coding with low computational and memory requirements IEEE trans. Circuits Syst. Video Technol. 5 182 192
  14. 14. Chin F. Choi A. Luo Y. 1992 Optimal Generating Kernels for Image Pyramids by Piecewise Fitting IEEE trans. Pattern Anal. Machine Intell. 14 1190 1198

Written By

Awad Kh. Al-Asmari and Farhan A. Al-Enizi

Submitted: April 16th, 2012 Published: February 6th, 2013