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

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.

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 H₀, H₁, G₀, and G₁ are the low decomposition, high decomposition, low reconstruction and high reconstruction filters, respectively. For the perfect reconstruction (i.e. $$x_0$$ = $${\stackrel{\wedge }{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^{-2k+1}{G}_0(-z^{-1});k\in Z$$ E4

$$H_i(z)=G_i(z^{-1}),i\in \left\{\text{0}\text{,1}\right\}$$ E5

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

$$P\left(z\right)=G_0\left(z\right).G_0\left(z^{-1}\right)$$ E6

Then it can be written as:

$$P(z)=1+{\displaystyle \sum _{k=odd}{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 1^st-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 x₀(n₁,n₂) is the original image of size L₁×L₂ pixels, then its pyramid structure can be done as shown in Figure 7.

Figure 7.

Three-level pyramid decomposition of an image x₀(n₁,n₂).

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 x₁(n₁,n₂) which is 1/4 of the size of x₀(n₁,n₂) and it is called the first-level image of the pyramid. The second level image x₂(n₁,n₂) can be obtained from x₁(n₁,n₂) by the same process, and this process is completed for the higher levels. The image x₁(n₁,n₂) can be interpolated by a factor of 2 and then filtered using synthesis filter G. The resulting image will be I[x₁(n₁,n₂)]. 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) e₀(n₁,n₂) is given by:

$$e_0\left(n_1,n_2\right)=x_0\left(n_1,n_2\right)- I\left[x_1\left(n_1,n_2\right)\right]$$ E8

This process can be done for the higher levels and we will have the error images e₁(n₁,n₂), e₂(n₁,n₂₎…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 e₀, e₁, and e₂ and the decimated image d₃ in space domain are shown in Figures [8-11]. Frequency responses of the error images e₀, e₁, e₂ and decimated image d₃ 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, e₀ image.

Figure 9.

Pyramid decomposed KSU book image in space domain, e₁ image.

Figure 10.

Pyramid decomposed KSU book image in space domain, e₂ image.

Figure 11.

Pyramid decomposed KSU book image in space domain, d₃ image.

Figure 12.

Frequency responses of the pyramidal components of KSU image (a) e₀ image, (b) e₁ image, (c) e₂ image, (d) decimated image d₃.

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 x₀(n₁,n₂) of size L₁×L₂, the number of multiplications needed for the first level x₁(n₁,n₂) with decimation factor M will be

$$L_1{L}_2{\log }_2{L}_1+\frac{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

$$\begin{array}{c}{K}_1=L_1{\log }_2{L}_1\\ \text{And}\\ K_2=L_2{\log }_2{L}_2\end{array}$$ E10

Then equation (9) can be applied for higher levels. In general, the total number of multiplications needed to get the decimated images x₁(n₁,n₂), x₂(n₁,n₂),…, x_N-1(n₁,n₂) and the difference images e₀(n₁,n₂), e₁(n₁,n₂),…, e_N-2(n₁,n₂) can be written as follows in equations (11) and (12) [13]:

$$2\left(L_2{K}_1+\frac{L_1}{M}{K}_2\right)N=\text{1}$$ E11

$$2\left[{\displaystyle \sum _{i=0}^{N-1}\frac{L_2{K}_1}{{\left(M\right)}^{2i}}+\frac{L_1{K}_2}{{\left(M\right)}^{2i+1}}-L_1{L}_2{\displaystyle \sum _{i=0}^{N-2}\left(i+1\right)\frac{M+1}{{\left(M\right)}^{2i+3}}}}\right]N\ge 2$$ 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\left(L_2{K}_1+\frac{L_1}{M}{K}_2\right)N=\text{1}$$ E13

$$8\left[{\displaystyle \sum _{i=0}^{N-1}\frac{L_2{K}_1}{{\left(M\right)}^{2i}}+\frac{L_1{K}_2}{{\left(M\right)}^{2i+1}}-L_1{L}_2{\displaystyle \sum _{i=0}^{N-2}\left(i+1\right)\frac{M+1}{{\left(M\right)}^{2i+3}}}}\right]N\ge 2$$ 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 P_f 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 n² with radius one. If we define m = n², the surface area of a m-dimensional sphere of radius ρ is given in equation (15):

$$S=m{V}_m{\rho }^{m-1}$$ E15

Where $$V_m={\pi }^{m/2}/(m/2)!$$ . All the patterns are assumed to have equal probabilities. Then, the false alarm probability P_f 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={\displaystyle \underset{T}{\overset{1}{\int }}(m-1)V_{m-1}{\left(\sqrt{1-x^2}\right)}^{m-2}}\frac{dx}{\sqrt{1-x^2}}$$ E16

And $$A=m{V}_m$$ . Therefore, P_f can be calculated as given below [11]:

$$P_f=\frac{{\displaystyle \underset{T}{\overset{1}{\int }}(m-1)V_{m-1}{\left(\sqrt{1-x^2}\right)}^{m-3}dx}}{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 P_f less than 1.35×10^-11, corresponds to a correlation threshold value that should be greater than 0.40.

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 x₀(n₁ ,n₂) was the original image of size L₁×L₂ 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, e₀(n₁,n₂), e₁(n₁,n₂), and e₂(n₁,n₂) are the error images, and d₃ 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 e₀, e₁, and e₂ of sizes L₁×L₂, (L₁/2)×(L₂/2), and (L₁/4)×(L₂/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 e₀ will increase the computational complexity. Furthermore, the visual quality of the reconstructed image is found to be affected when the difference image e₂ 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 e₁ will provide a trade-off between imperceptibility, robustness, and computational complexity. These observations will be presented in the simulation results. Therefore, e₁ 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 e₁ is shown in Figure 14.

Figure 13.

Wavelet decomposition structure for the error image e₁.

Figure 14.

Proposed Pyramid-Wavelet watermarking algorithm using e₁.

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 P_f (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 e₁ 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].

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.

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.