Average PSNR and correlation of proposed method and Y. Wang method .
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 . 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 . 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 : 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 . 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 . 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 .
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. =), these filters should be related to each other according to the relations given below:
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 :
If P(z) was defined as a polynomial, where
Then it can be written as:
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.
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.
Pyramid transform was first introduced by Burt and Adelson . 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.
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:
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.
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 . 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
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
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) :
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).
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 ; 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):
Where. All the patterns are assumed to have equal probabilities. Then, the false alarm probability Pf equals to the fraction of two areas . A is the area of the whole sphere, while 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, can be calculated as follows:
And. Therefore, Pf can be calculated as given below :
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.
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 . 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 . 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.
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 . 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 . 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 . Our proposed method gives higher average values for both the PSNR and the correlation. This guarantees good perceptual transparency and reliability.
|Proposed method||Y. Wang |
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 . Table 3 shows the number of multiplications and savings for our method and method of Y. Wang . 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 |
|JPEG compression (average: 0.328 bpp)||0.602||0.562|
|1% Salt-and-pepper noise||0.948||0.956|
|Hiding technique||Proposed method||Y. Wang |
|Number of multiplications||16,687,104||36,347,904|
|Savings in computational complexity (%)||54.09||0|
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  which is 0.23. So, our algorithm is robust against JPEG compression at quality factors greater than 50.
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  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.