Robust Embedding of Watermark in Wavelet Tree using SVD

Robust Embedding of Watermark in Wavelet Tree using SVD

Robust Embedding of Watermark in Wavelet Tree using SVD

Radhika G. Kabra

Assistant Professor Department of Electronics and Telecommunication

Government College of Engineering

& Research, Awasari, Pune,India

Rahul A. Mahadik Department of Electrical Engineering

Indian Institute of Technology, Kharagpur, India

Amol A. Mahadik Assistant Professor Department of Information Technology

Jawaharlal Nehru Engineering College, Aurangabad, India

Abstract Watermarking is a method of concealing a secret image within other original image used for security purpose. To improve the robustness and imperceptibility of the watermarking a structure called wavelet tree (WT) is used. This paper proposes a watermarking scheme based on wavelet tree, Lifting Wavelet Transform (LWT) and Singular Value Decomposition (SVD). Five level decomposition of the original image is done; wavelet tree is constructed for CH band followed by selection of four trees for embedding purpose. SVD is applied to selected trees. Singular values are updated using singular values of watermark. Results conclude that this scheme is considerably more robust against various attacks like sharpening, histogram equalization, re-watermark, noise, etc. This algorithm also achieves another property of watermarking called imperceptibility. Comparison with existing methods shows that results achieved using this algorithm is better.

Keywords Correlation coefficient (CRC); Lifting Wavelet Transform (LWT); Mean Square Error (MSE); Peak Signal to Noise ratio (PSNR); Singular Value Decomposition (SVD); Watermark; Wavelet Tree (WT)

1. INTRODUCTION

   Because of the rapid growth of multimedia technology, use and transfer of the digitized media over the internet have been increased. This revolution has raised concern in terms of the copyright protection. At present there are three different techniques to securely transfer the digital media over the internet. First one is cryptography in which message is encrypted using some key, but once the message is decrypted no security can be provided. Other two techniques comprise data hiding techniques. Image steganography deals with securely transmitting message signal by embedding it in the image. Message to be transferred is most important in this case. Third approach is digital image watermarking in which unlike steganography, message to be transferred does not need to be secret. Digital image watermarking is divided in to two different types depending on the visibility of the watermark on the host image; visible and invisible watermarking. As name implies in visible watermarking the watermark is visible on the host image. The example of visible watermarking is the television broadcasters gives there logo on the right side. Here we are doing second approach of watermarking which is invisible watermarking.

   Digital watermarking mitigates illegal copying of the digital media by hiding some ownership information, called

   watermark in the host contents. Imperceptibility and the robustness are the important properties of the watermarking scheme. Imperceptibility relates with the invisibility of the watermark to the human visual system. Robustness means the watermark must be resistant to the intentional and non- intentional attacks caused by various signal processing attacks.

   Watermarking techniques can be divided in to two types depending on the domain in which the watermark is being embedded, either spatial domain or frequency domain. Embedding the data in spatial domain is easy to realize with low computational cost but this method is not robust against different attacks. Spatial domain techniques embed the watermark directly into the intensity values of the host image. Frequency domain techniques embed the watermark in some transformed coefficients. Frequency domain techniques insert more bits of watermark and are more robust against various attacks.

   Wavelet transform based watermarking is a frequency domain technique but when lifting scheme is applied to wavelet all constructions will be derived in spatial domain. Use of lifting scheme reduces the computational complexity of the watermarking scheme. Modification in singular values of the image does not affect the image quality. So use of singular value decomposition satisfies the imperceptibility of watermarking scheme.

   Digital image watermarking has various applications in health care, secured e-voting systems, criminal photograph authentication and transmission, etc [1]. The authors in [2] presented a novel wavelet group based watermarking scheme using energy modulation and consistency check. This technique not only resists different attacks but also provides dual function of choices for blind and non-blind watermark embedding. It increases robustness of the watermarking scheme. In paper [3] authors developed a concept of qualified significant even wavelet tree. Unlike other watermarking techniques that use single casting energy, proposed technique assumes adaptive casting energy in different resolutions. In [4] authors proposed a color image watermarking scheme to solve the problem of choosing one of the three components of color space for embedding the watermark. Proposed watermarking scheme is based on wavelet tree. The authors in [5] devised a scheme to improve wavelet tree quantization's robustness. Chaotic system for block based scrambling is used. The host image is first split in to many blocks and the chaotic system is

   applied to scramble image before the implementation of wavelet tree quantization. The author in paper [6] presented a watermarking scheme based on zero tree of wavelet coefficient. In paper [7] a scheme is designed to make it robust against cryptanalysis attacks. Two trees constitute a super- tree. Some of these super-trees are quantized to embed the watermark information in image. In [8] authors used the concept of super-tree. The algorithm is designed to make it more robust against time domain geometric attacks.

   This paper proposes a new robust watermarking scheme using wavelet tree and SVD. The original image undergoes five levels of decomposition. Lifting wavelet transform is used for decomposition purpose. The wavelet trees are designed by using parent-child relationship. Each tree consists of 341 coefficients. We use 3 such trees and single coefficient from 4th tree for embedding purpose. SVD is applied to the selected tree coefficients and the watermark image. Then singular values of the tree matrix are modified using singular values of the watermark image. This scheme gives good imperceptibility and is eminent to different attacks.

   This paper is structured in to 4 sections. Section I gives introduction and literature review. Section II describes the concept of wavelet tree, LWT and SVD. This section also gives the idea of proposed watermarking algorithm. Section III discusses about the results of the method. Finally section IV concludes the paper.

2. BACKGROUND REVIEW AND PROPOSED APPROACH

   Fig.1. Parent Child Relationship

   The second step is Predict step, in which odd set is anticipated from even set. Predict phase ensures polynomial cancellation in high pass. The third step is update phase that will modernize even set using wavelet coefficient to calculate scaling function. Update stage ensures preservation of moments in low pass. Fig. 2 shows lifting wavelet transform scheme. Lifting scheme allows faster implementation of wavelet transform.

   A. WAVELET TREE

   Concept of wavelet tree is dependent on parent child relationship betweencoefficients of wavelet decomposition at different levels. Each coefficient at the particular scale can be related with a set of coefficients at the next finer scale. The lowest frequency sub-band is excluded while designing the wavelet tree. So if the size of image is m*m and it undergoes n level decomposition then number of trees we get are m m 3 . The coefficient at the coarser scale is called as

   4n

   the parent and the set of coefficients related to that coefficient at the finer scale are called as the children. One coefficient at the coarser scale relates to the 2*2 coefficients at the finer scale. The wavelet tree representation and the parent child relationship are as shown in figure 1. Arrow points from the scale of parent coefficient towards the children coefficients scale.

   1. Lifting Wavelet Transform

      Lifting wavelet transform is substitute to the discrete wavelet transform. Lifting scheme is simplest and efficient algorithm to calculate wavelet transforms. It is independent on Fourier transforms. Lifting scheme is used to generate second- generation wavelets, which are not necessarily translation and dilation of one particular function [9]. Assembling wavelets using lifting scheme involve three steps: The first step is split phase that splits data into odd and even sets.

      Fig.2. Lifting Wavelet Transform

   2. Singular Value Decomposition

   The SVD belongs to orthogonal transform which decompose the given matrix into three matrices of same size. To decompose the matrix using SVD technique it need not be a square matrix.

   In linear algebra, the singular value decomposition

   (SVD) is an important factorization of a rectangular real or complex matrix, with several applications in signal processing and statistics [10]. The SVD of rectangle matrix A is a decomposition of the form

   A=U*S*VT (1)

   where U, V are orthogonal matrices and S is a diagonal matrix composed of singular values of A. The singular values appear in descending order along the main diagonal of S [10]. The singular values of an image have very good noise immunity i.e. singular values do not change significantly when a small change is added to image intensity values [11].

   1. Proposed watermarking scheme

      Proposed watermarking algorithm is based on wavelet tree and singular value decomposition. Consider the original image and apply five levels of decomposition using lifting scheme of wavelet transform. Tree can be formed by using

      parent-child relationship between the coefficients at the different scales.

      1. Apply inverse process for reconstruction of the CH components at each level of decomposition from the wavelet trees.

         Let us assume a coefficient

         xn i, jat decomposition

         level n then related coefficients at the finer scale that constitutes a wavelet tree can be formulated as,

      2. Obtain watermarked image by applying 5 level

   inverse lifting wavelet transform using the new CH values.

   m

   r1 2

   i 2m

   m

   1, r2 2 i

   1. Extraction Algorithm:

      Watermark Extraction Algorithm is as follows:

      m

      c1 2

      j 2m

      m

      1, c2 2 j

      1. Decompose the watermarked and original image in to wavelet domain with 5 resolution levels.

         Where m= 5 n for n = 1, 2, 3, 4.

      2. Construct the wavelet tree for both watermarked and

   Therefore

   xn i, j

   is parent of

   xn p, q

   for p r1 | r2 ,

   original image.

   q c1 | c2 . Reconstruction of coefficients of each level of decomposition from wavelet tree is done in reverse manner. For 5 level decomposition the number of coefficients in the wavelet tree are 341 out of which 1 is from 5th level, 4 from 4th level, 16 from 3rd level, 64 from 2nd level, and 256 from 1st level of decomposition.

   1. Embedding Algorithm:

      Embedding algorithm of proposed method is given below

      1. Consider the original image (O) and watermark image (W).

      2. The original image is decomposed in to wavelet domain using lifting wavelet transform with 5 -resolution levels. There will be 16 sub-bands after 5 level decomposition

      3. Use 5 horizontal components (CH) obtained after level LWT decomposition for the construction of wavelet tree.

      4. Construct the wavelet tree (Htree) by using the parent child relationship between the coefficients at the different scales.

      5. Select 3 trees and one coefficient from the 4th tree

   1. Select corresponding trees as used for embedding purpose.

   2. Apply SVD to the matrices formed using coefficients of the selected trees of original and watermarked image.

   3. Compute the singular value matrix

      S Sw S

      1n

      Where Sw is singular matrix of watermarked image

   4. Get the possibly distorted watermark by using singular value S1n.

3. EXPERIMENTAL RESULTS

   This unit gives simulation results of the proposed algorithm based on LWT and SVD. Six original images of size 512*512 and watermark image of size 32*32 as displayed in Fig. 3 are selected. Watermarked images are displayed in Fig. 4. Two constraints to illustrate the strength of proposed watermarking method have been used viz. PSNR and CRC. PSNR is used to estimate the eminence of watermarked image [6], and it is formulated as follows:

   2552

   for embedding purpose.

   1. Apply SVD to the matrix formed using the

      PSNR 10 log10

      MSE

      (2)

      coefficients selected in above step.

   2. Apply SVD on the watermark image.

      where MSE is computed using original image and

      watermarked image as follows,

      512 512 Oi, j Wi, j2

   3. Modify singular values of the tree matrix with the singular values of the watermark image.

      MSE

      i1 j1

      512 512

      (3)

      Snw S S1

      Where is a scaling factor, S and S1 are singular matrices of the wavelet tree matrix and watermark image respectively.

   4. Using the orthogonal matrices U & V values obtained from step (f) and singular values obtained from step

   (h) apply inverse SVD.

   & Pepper noise (SP), Gaussian filtering (GF), Weiner Filtering (WF), Median Filter (MF); 3) Image processing attack: Histogram equalization (HE), Re-watermark (RW), Gamma correction (GC), Pseudo coloring (PC), Dithering

   where O and W are original and watermarked image, respectively. Table II shows the PSNR values for six different images.

   Correlation coefficient is used to find similarity between original and extracted watermark. To evaluate the robustness of the method, the watermarked image is verified against different attacks [7]: 1) Geometrical attack: Cropping (CR), Rotation (ROT); 2) Noising and de-noising attack: Salt (DT) and Sharpening (SH). Correlation coefficients values of the original and extracted watermark under different attacks are tabulated in Table I. 12 different attacks are interjected on watermarked image and then watermark is

   extracted from it. Watermarked image under different attacks are as shown in Fig. 5 and Fig. 6 and corresponding

   extracted watermarks are as shown in Fig. 7 and Fig. 8.

   Fig.3. Original Images (Peppers, Coins, Rice, Trees, Cameraman, Elaine), Watermark

   Fig.4. Watermarked Images (Peppers, Coins, Rice, Trees, Cameraman, Elaine)

   Fig.5. Watermarked images under different attacks (Sharpening, Gaussian Filter, Rotation, Histogram Equalization, Dithering, and Weiner Filtering)

   Fig.6. Watermarked images under different attacks (Gamma Correction, Median Filter, Pseudo Coloring, Cropping, Re-watermark, and Salt & Pepper Noise)

   Fig.7. Extracted watermarks under (Without any Attack, Sharpening, Gaussian Filter, Rotation, Histogram Equalization, Dithering, and Weiner Filtering)

   Fig.8. Extractedwatermarks under different attacks (Gamma Correction, Median Filter, Pseudo Coloring, Cropping, Re-watermark, and Salt & Pepper Noise)

   TABLE I CRC VALUES

   Original image	CRC Without any attack	CRC Values under different attacks
   		GF	PC	GC	ROT	DT	HE	SP	SH	RW	CR	WF	MF
   Elaine	1	0.9079	1	0.9286	0.9322	0.9684	0.9608	0.9673	0.9724	0.9999	0.9984	0.9494	0.9202
   Cameraman	1	0.9994	1	0.8254	0.8732	0.8665	0.9305	0.9428	0.9978	1	1	0.9945	0.9949
   Rice	1	0.9929	1	0.9610	0.7554	0.9530	0.9210	0.9065	0.9869	0.9998	1	0.9821	0.9804
   Coins	1	0.9997	1	0.9994	0.7604	0.8335	0.9066	0.9277	0.9975	1	0.9999	0.9976	0.9962
   Peppers	1	0.9981	1	0.9332	0.9528	0.9766	0.9392	0.9344	0.9983	1	0.9998	0.9930	0.9944
   Trees	1	0.9915	0.9563	0.8426	0.9123	0.9490	0.9300	0.9528	0.9864	1	0.9997	0.9914	0.9861

   TABLE II PSNR VALUES

4. CONCLUSION

Original Image	PSNR(dB)
Elaine	53.0819
Cameraman	52.9721
Rice	52.9623
Coins	52.9878
Peppers	53.0220
Trees	53.2445

This paper intends a watermarking scheme using wavelet tree and SVD. Use of lifting scheme reduces half number of computations with lossless compression. The singular values of the watermark are inserted in the singular values of tree matrix obtained after five level decomposition of the original image. To prove heftiness of the watermarking scheme six different original images are taken. Robustness and imperceptibility is accomplished based on PSNR & CRC values. 12 different attacks are interjected on the watermarked images. CRC values are quite ameliorated than other papers while PSNR values are not improved after certain extent. Experimental simulations in MATLAB show that wavelet tree-SVD approach gives good imperceptibility and eminent results against different kind of geometric and image processing attacks. In future

robustness of the scheme can be improved using optimization. Image and audio signal can be embedded simultaneously in different detail components of a same cover image. Also the real time approach using FPGA can be realized.

REFERENCES

[1] B. L. Gunjal and S. N. Mali, Applications of digital image watermarking in industries, CSI Communications, sep 2012

[2] Min-Jen Tsai, Jin-Sheng Yin, and Imam Yuadi, Tree Group Based Wavelet Watermarking Using Energy Modulation and Consistency Check (WW-EMCC)for digital images, Springer, 19 Aug 2014

[3] B. Vijaykumar, Dr. V. Vijayakumar, and Dr. Rajya Lakshmi, A Robust Tree Quantization Image Watermarking Technique Based On Qualified Significant Even Wavelet Tree(QSEWT), (IJCSIT) International journal of computer science and information technologies, vol. 3(2), 2012

[4] Yu Tang Chin, Chung-Yen Su, andYen-Lin Chen, An Adaptive Color Image Watermarking Using Wavelet-tree Structure, IEEE 978-1-4799-5277 , sept 2014

[5] Min-Jen Tsai, Wavelet tree based digital image watermarking by adopting the chaotic system for security enhancement, Springer, 2011

[6] Jerome M. Shapiro, Embedded image coding using zerotrees of wavelet coefficient, IEEE Transaction on signal processing vol. 41 no. 12, Dec 1993

[7] Tanmoy Kanti Das, Subhamoy Maitra, Analysis of the Wavelet Tree Quantization watermarking strategy and a modified robust scheme, Springer 19 Aug 2006

[8] Shih-Hao Wang and Yuan-Pei Lin, Wavelet Tree Quantization for Copyright Protection Watermarking, IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 13, NO. 2, FEBRUARY 2004

[9] I. Daubechies and W . Sweldens , Factoring Wavelet Transforms into Lifting Steps, The Journal Of Fourier Analysis And Application, vol. 4, Issue 3, 1998

[10] S. Kumar, A. K. Saini, and P. Kumar, SVD based Robust Digital Image Watermarking using Discrete Wavelet Transform, International Journal of Computer Applications, vol45 No.10, May 2012

[11] A. K. Gupta, M. S. Raval, A robust and secure watermarking scheme based on singular values replacement, Sadhana vol. 37,

Part 4, pp. 425-440, August 2012

[12] I. J. Cox J. Kilian, F. Leighton, and T. Shamoon, Secure spread spectrum watermarking for multimedia, IEEE Transactions on Image Process. 6, 16731687 (1997)

[13] K. R. Kakkirala and S. R. Chalamala, Block based robust blind image watermarking using discrete wavelet transform, IEEE 10th International Colloquim on signal processing & its applications (CSPA2014), 7-9Mac.2014, Kuala Lumpur,Malaysia

[14] K. Loukhaoukha, M. Nabti, and K. Zebbiche, A robust SVD-based image watermarking using multi-objective particle swarm optimization, Opto-Electron. Rev..22,no.1,2014

[15] S, G. Kejgir, and M. Kokare, Lifting wavelet transform with singular value decomposition for robust digital image watermarking, International Journal Of Computer Application, vol 39- No.18, Feb 2012

[16] T. Sridevi and S. S. Fatima, Digital image watermarking using genetic algorithm in DWT and SVD transform, Third International Conference on computational intelligence and information technology (CIIT), pp. 485-490,2013