School of Computer Science and Software Engineering
Monash University
Bachelor of Science (Computer Science) with Honours
Clayton Campus
Honours Thesis 2000
Digital Watermarking of Images Project
(DWIP)
By
Peter An
12283673
Supervisor: Dr Henry Wu
I Peter An declare that this thesis is my own work and has not been submitted in any form for another degree or diploma at any university or other institute of tertiary education. Information derived from the published and unpublished work of others has been acknowledged in the text and a list of references is given in the bibliography.
--------------------------
Peter An
--------------------------
Date
Copyright protection of images has become a major concern with the rapid expansion of the Internet, which contains millions of freely available images. Digital watermarking has been suggested as a form of copyright protection and is becoming a major player not only for use in images but also in the latest technology such as DVD. This thesis investigates the following relevant concepts and terminology: History of watermarks and how they come about in digital form, the properties of a watermarking system, the applications and what the watermark is used for, the requirements, and also a number of different watermarking techniques, with the main focus being on watermarking in the transform domain. Two watermarking techniques, which are based on the discrete cosine transform, are tested and the results are analysed. A program is created that implements the technique that gave the best result, and a watermarking system is also proposed for the use of digital images.
I would like to thank my supervisor, Dr Henry Wu for his wisdom and guidance throughout the year.
A special thanks also goes to Dr Jack Yu for his contribution.
To my family and friends, thankyou for your support.
Declaration of Originality *
Thesis Abstract
Acknowledgements
*Table of Contents
*List of Figures
*Chapter 1. Introduction
*1.1 Motivation
*1.2 Aims
*1.3 Thesis Outline
*Chapter 2. Digital Watermarking Background
*2.1 Watermarks
*2.2 History
*2.3 Properties
*2.4 Applications
*2.5 Requirements
*2.6 Techniques
*2.7 Attacks
*Chapter 3. Research Methods
*3.1 Methodology
*3.2 Technique 1
*3.3 Technique 2
*Chapter 4. Results and Analysis
*4.1 Gathering Results
*4.2 Results and Analysis for Technique 1
*4.3 Results and Analysis for Technique 2
*4.4 Comparison
*Chapter 5. Implementation
*5.1 Watermarking Program
*5.2 Watermarking system
*Chapter 6. Conclusion and Further Research
*6.1 Conclusion
*6.2 Further Research
*Appendix A
*Appendix B
*Appendix C
*Bibliography
*List of Figures
Figure 2-1. Visible watermark *
Figure 2-2. Invisible watermarks *
Figure 2-3. MediaBridge *
Figure 3-1. The basic technique used to insert and retrieve the watermark. *
Figure 3-2 Watermark inserted using two DCT coefficients *
Figure 3-3 Watermark is encoded using three quantised DCT coefficients. *
Figure 4-1. Comparison of x = 1 and x = 50 *
Figure 4-2. The relationship between x and the signal to noise ratio *
Figure 4-3. x vs Accuracy, from x = 3 and beyond the accuracy is 100%. *
Figure 4-4. Watermarked with QF of 41 *
Figure 4-5. Comparison of D = 1 and D = 4 *
Figure 4-6. The relationship between D and the SNR. *
Figure 4-7. The accuracy increases as D is increased *
Figure 4-8. Watermarked with QF = 65 *
Figure 4-9. The accuracy dramatically drops when the SNR > 38 *
Figure 4-10. The accuracy steadily falls as the SNR increases *
Figure 5-1. Watermark system *
The ability to access and "share" images has become increasingly easy with the Internet allowing people to reach information from anywhere in the world. There has also been an increase in the number of digital images on the Internet due to the fact that millions of people are taking digital photos. This brings about the need for people to protect their images or intellectual property. Given the motivation to protect intellectual property, Digital Watermarking has been suggested as a form of copyright protection and a deterrent to those wishing to obtain images illegally.
Watermarks are "a subtle perturbation of digitised multimedia [1], and they are used for many different purposes. One purpose is to hide a description of the image as the watermark. With traditional images, when people want to describe the image they write it on a piece of paper and place it below or near the image. In the digital domain the description can be inserted into the image as a watermark and then read by a watermarking program. The advantage of this is that the image does not increase in size and the description remains even when the image is printed. Watermarks are also used for captioning where the owner's details are stored with the watermark, which allows rightful ownership to be resolved [2], but an area in which it is most useful is in copyright protection. For a watermark to be used as a copyright protection tool it must be robust, meaning that it will be hard to remove and any attempt to remove it will damage the image, making it unrecognisable. There is great potential in this field, because companies are looking for a secure and effective method of protecting images.
A great deal of research has gone into the different techniques of creating and inserting a watermark into a digital image, however there is a need to continue this research into the field of making the watermarks robust and secure. The aim of this project was to investigate techniques that are robust in the transform domain and develop a watermarking program that implemented a robust technique. A watermarking system was also proposed for use with digital images.
Following on from this chapter, chapter 2 gives the background to this thesis and looks at digital watermarking, it’s history, properties, applications, requirements, techniques, and attacks on watermarks. With the background in hand, Chapter 3 details the methodology used in researching two different techniques. Chapter 4 lists the results of the tests carried out and an analysis on the results is given, with the aim of comparing the two techniques to see which is the better method. Chapter 5 describes the program that implements the best technique and Chapter 6 concludes the research with a view to further research in the future.
Watermarking is part of the Information Hiding family, which also includes cryptography and steganography. Cryptography tries to conceal the contents of a message, while steganography goes a bit further and tries to hide the fact that communication is taking place. Watermarking, as opposed to steganography, has the additional notion of robustness against attack [3]. If an attacker discovers the existence of the hidden information, it should be hard for the attacker to destroy the embedded watermark.
There are two types of watermarks visible and invisible:
Figure -2. Invisible watermarks
Paper watermarks appeared in the art of handmade papermaking nearly 700 years ago. After their invention, watermarks quickly spread in Italy and then over Europe and although initially used to indicate the paper brand, they later served as an indication for paper format, quality, and strength, and were also used as the basis for dating and authenticating paper[3]. It was the use of watermarks in bank notes or stamps that first inspired the use of the term "watermark" in the context of digital data. The first publications that focused on digital images were published by Tanaka et al. [5] in 1990 and by Tirkel et al. [6] in 1993. Since van Schyndel et al. [7] embedded an m-sequence watermark by changing the least significant bit of an image in 1994, more efforts have gone into the research of digital watermarking. However, the main focus has shifted from how to embed the watermark to improving the robustness of the watermark.
All watermarking techniques share the same generic implementation: a watermark embedding system and a watermark recovery system. The input to the scheme is the watermark, the image and an optional public or secret key. The watermark can be of any form, such as a number, text, or an image. The key is used to enforce security, this prevents any unauthorised party the privilege of recovering and manipulating the watermark. The output of the watermarking scheme is the watermarked data [3]. There are a few general properties shared by all watermarking systems, these are:
The watermark recovery process consists of the watermarked data, the secret or public key, and, depending on the method, the original data and the original watermark. The output is the recovered watermark [3].
There are three types of watermarking systems. The difference between them is in the nature and combination of inputs and outputs:
Currently there is no "universal" watermarking method due to the different applications in which watermarks are applied. Different applications require different levels of robustness. Watermarking can be used for the following applications and many more applications are also possible and are constantly being invented.
MediaBridge - MediaBridge allows you to access the Internet through a watermark that has been embedded into an advertisement.
Depending on the watermarking application and purpose, different requirements arise resulting in various design issues. Watermark imperceptibility is a common requirement and independent of the application purpose. Additional requirements have to be taken into consideration when designing watermarking techniques [3]:
In general, watermarks can be embedded in the spatial domain or the frequency domain. A public technique that uses the spatial domain is the Patchwork method [10], which takes a statistical approach. It is based on a pseudorandom, statistical process. Pairs of image points are randomly chosen and the brightness at one point is increased while the brightness of the corresponding point is decreased. The expected value of the sum of the differences of the n pairs of points is then 2n. The Patchwork technique is considered to be secure, in that it is difficult to remove the Patchwork coding without degrading the picture beyond recognition, although this method has a limitation on the amount of information that can be embedded. Another method, which has been suggested by Burgett et al. [11], is the Pulse Embedding System, where the position sequence is used to generate a sequence of pixel-mapped locations where the code is then embedded. The code pulses are superimposed on the signal-selected locations and then the quantised data is decoded and inversely transformed to produce the labeled image data. Watermarking in the spatial domain has its downfalls in that the watermark can be destroyed because the domain deals with the image pixels or luminance information. Hence any translation, rotation, scaling, compression or any change to the image can cause the destruction of the watermark, depending on its robustness. Therefore over the years the research focus has shifted from the spatial domain to the frequency domain.
The frequency domain has an advantage over the spatial domain in that frequency-based schemes "spread the watermark over the whole spatial extent of the image, and is therefore less likely to be affected by cropping." [12]. The Discrete Cosine Transform (DCT) is widely studied due to the fact that watermarks embedded in the DCT domain are often more robust to JPEG and MPEG compression. Ingemar et al. [12] suggests the following private method, Secure Spread Spectrum Watermarking, which spreads the watermark thinly over the image in the most significant spectral components of the data.
The following is an overview of the algorithm used in this technique.
extracted from the image, to obtain an adjusted sequence of values V' = v'1,..., v'n.
the watermark in perceptually significant regions.
The watermark extraction algorithm consists of the following steps:
to get a possible watermark X*
Research has also been conducted on the possible attacks on watermarks [13]. In order to create a robust and secure watermark we need to know the area in which the watermark is most vulnerable. Some methods used to attack watermarks are:
With this background to digital watermarking complete, the focus in the following chapters is now shifted towards investigating two techniques that are robust against JPEG compression.
In order to come up with a watermarking program that was robust in the transform domain a transform function had to be chosen. There are many transform functions, some of which include the Wavelet transform, the Fourier transform, and the Discrete cosine transform (DCT). The techniques chosen are based on the DCT, with the main advantage being that it is used in the Joint Photographic Experts Group (JPEG) standard, which is a file format that is widely used on the Internet. This ensures that the watermark is robust against JPEG compression. Figure 3-1 shows the basic technique used to insert and retrieve the watermark. The two techniques investigated are outlined in the following sections, with the main difference between the two being that the first technique is based on embedding the watermark using two DCT coefficients and the second technique is based on embedding the watermark using three quantised DCT coefficients. Equation 3.1 was used to calculate the forward DCT and Equation 3.2 was used to calculate the inverse DCT. Equation 3.3 was used to change the Red, Green, Blue (RGB) pixel values to one Luminance (Y) and two Chrominance (Cb, Cr) components.
Figure -1. The basic technique used to insert and retrieve the watermark.
This basic technique inserts the watermark into the DCT of the image. The watermark is retrieved by performing the DCT on the watermarked image.
This first method, which was suggested by Zhao et al [14], inserts the watermark in the DCT coefficients by breaking the image into 8 x 8 blocks computing the DCT for each block. The relationship between two DCT coefficients and the next watermark bit is looked at and if needed modifications are made in order to impose a specific relationship between the two coefficients. The choice of the two coefficients is based on the JPEG quantisation table, where the coefficients are quantised with the same value in the belief that the relationship will remain the same after the inverse quantisation.
Figure 3-2 shows a detailed description of how the watermark is inserted.
Figure -2 Watermark inserted using two DCT coefficients
The image is split into 8 x 8 RGB blocks. These blocks are then converted into YCC components using Equation 3.3, and we now work with the luminance values. The DCT is performed and Two coefficients are then chosen based on the JPEG quantisation table for the luminance components. These values are used to encode the watermark.
The watermark is encoded using the following algorithm, where a is the first coefficient and b is the second coefficient. The relationship between the two coefficients is altered so that they fulfil a certain requirement depending on the watermark bit.
The watermark is retrieved using the following algorithm.
The second method, which was suggested by Koch et al. [15], breaks an image into 8 x 8 blocks and computes the DCT of each of the blocks. These blocks are then quantised and 3 frequencies, from the middle frequency range in each block, are modified so that their relative strengths encode a 1 or 0 value. The choice of the three frequencies to be altered within the quantised DCT block is based on a belief that the "middle frequencies...have moderate variance", i.e. they have similar magnitude. This property is needed in order to allow the relative strength the frequency triples to be altered without requiring modification that would be perceptually noticeable.
This is a detailed description of how the watermark is inserted and retrieved.
Figure -3 Watermark is encoded using three quantised DCT coefficients.
The image is split into 8 x 8 RGB blocks. These blocks are then converted into YCC components using Equation 3.3, and we now work with the luminance values. The DCT is performed and then quantised based on the JPEG quantisation table and three quantised coefficients are chosen. These values are used to encode the watermark.
The watermark is encoded using the following algorithm, where a, b, and c are the chosen coefficients. The difference between the largest and smallest values are check and if the difference is greater than a constant, MD, the block is marked invalid by adjusting the coefficients so that they meet a condition.
The watermark is retrieved using the following algorithm, which checks to see if the block has been marked invalid, otherwise it checks the condition of the chosen values to extract the watermark. If the block is damaged then it is skipped.
The testing of each method was performed by taking a 512 x 512, 24-bit colour image and inserting an 8 bit length watermark. The signal to noise ratio, Equation 4.1, is a commonly used pixel-based visual distortion metric [3] and this was used measure the distortion between the original image and the watermarked image. A low SNR means that the image has been greatly distorted.
The signal to noise ratio is usually measured in decibels and converted using Equation 4.2.
The percentage accuracy of the recovered watermark was calculated by finding the frequency of the actual watermark and dividing it by the total of all watermarks recovered.
4.2 Results and Analysis for Technique 1
For this method tests were performed using different values of x, where x is the distance between two coefficients. This becomes the measure of robustness since the values are altered slightly in the DCT step, we require that the relationship between the chosen values remains the same.
Table 1. Results for different x values Figure -1. Comparison of x = 1 and x = 50
Figure -2. The relationship between x and the signal to noise ratio
Figure -3. x vs Accuracy, from x = 3 and beyond the accuracy is 100%.
Using x = 3, JPEG compression was performed with different quality factors.
Table 2. JPEG compression for x = 3 Figure -4. Watermarked with QF of 41
In testing for different values of x the results in Table 1 indicate that as x is increased the SNR decreases, meaning that the image is more effected by the watermark as the value of x is increased which can also be seen in Figure 5, where the watermark becomes noticeable when x = 50. The accuracy in which the watermark was found increased as the value of x increased which was expected because the greater the distance between the two numbers the more likely they will meet the condition in which the watermark was encoded. The optimal result was for x = 3, the SNR was 38.1dB and the accuracy was 100% and this result was used to test JPEG compression. When JPEG compression was performed the accuracy dramatically decreases until a quality factor of 40 is reached where beyond this point the watermark was unrecoverable.
4.3 Results and Analysis for Technique 2
Tests were performed on different values of D, where D is the minimum distance between and two coefficients, and MD, which is the maximum distance, is set to 10.
Table 3. results for different D values Figure -5. Comparison of D = 1 and D = 4
Figure -6. The relationship between D and the SNR.
Figure -7. The accuracy increases as D is increased
Using D = 1, JPEG compression was performed with different quality factors
Table 4. JPEG compression for D = 1 Figure -8. Watermarked with QF = 65
As expected the results for different D values with respect to the SNR came out to be almost linear, meaning that as D was increased the image quality degraded dramatically, the watermark can clearly be seen in figure 4-5 for D = 1 and D = 4. The accuracy increased as D was increased which was due to the fact that the distances between the values were great enough for them to stay within the imposed relationship after quantisation and DCT. When testing JPEG compression the watermark was not found beyond a quality factor of 65 and the accuracy was also very poor. This was due to the fact that JPEG compression uses different quantisation tables for different quality factors, therefore the robustness of this watermarking technique also depends on the quantisation values.
The tests carried out indicate that method 1 was more robust than method 2 when using JPEG compression. There were favourable results for both methods however; the accuracy of the first method was greater than that of the second method for the same SNR. By comparing Figure 4-9 and Figure 4-10, it can be seen that the SNR of the first method was much greater for a higher accuracy than for the second method.
Figure -9. The accuracy dramatically drops when the SNR > 38
The reason for this was that the second method has to do many more alterations than the first method due to the marking of an invalid block. JPEG compression also performed better for the first method due to the fact that the watermark is inserted into the DCT coefficients rather than in the quantised DCT coefficients. One of the major drawbacks in using the quantised values is that there are a number of JPEG quantisation tables that can be used and this directly impacts the robustness of the watermark under JPEG compression. From these results the first technique was implemented into a watermarking program, which is described in the next chapter.
Figure -10. The accuracy steadily falls as the SNR increases
A watermarking program was created based on the results obtained from the testing of both techniques. In making the program a number of factors were taken into account including the image quality and the robustness of the watermark under JPEG compression. The program has a menu that asks the user if they want to insert a watermark or read a watermark.
If the user wants to insert a watermark then they enter the number 1.
They are then asked to enter in a string with a maximum length of 50 characters, which is the watermark and it gets converted into binary. This binary string is inserted into the image using method 1, with x = 3. The image can then be saved.
If the user wants to retrieve the watermark they enter the number 2
The program searches for the watermark and displays it on the screen.
The code for this program can be found in Appendix C.
This is a proposed watermarking system for the program. There is a watermark encoder and a watermark reader. The Encoder can insert, remove, and read the watermark and this is available for people to buy where as the reader, which can only read the watermark, is freely available. This is how the system is used:
Say Alice has both the encoder and reader and she wants to send Bob a watermarked image
There is also the added option to encrypt the watermark with a secret key for added security.
Figure -1. Watermark system
With the watermark encoder, the message is typed into the box under the word message and a key, which is used for encryption is also enter. The user then clicks on Write to insert the watermark in the image and they can then save the image. The remove feature gives the user the option of removing the watermark and inserting a new watermark. The Watermark Reader has a simple operation, the image is loaded and the user enters the key and presses the read button. The watermark is read by the program and displayed in the box under the word message.
Watermarking is a viable means for people to use in copyright protection and many other applications. Many of the images on the Internet are in the JPEG file format, which uses the DCT, this was one of the reasons for using techniques that insert the watermark in the transform domain. It was proven that a watermarking method can be made robust against JPEG compression and also have an acceptable watermarked image that is indistinguishable from the original image to the human eye. The visual quality and the robustness of the watermark were inversely proportional to each other. The more robust the watermark the poorer the quality of the image. This was taken into account in the development of the watermarking program. The program was designed using the first method, which takes two DCT coefficients and imposes a certain condition on them depending on the watermark bit. A watermark system was also proposed based on the program, which has an encoder, which is made available for a price and a reader, which is freely available.
Further research should go towards improving the watermarking program and adding extra functionality. One of these is looking at having multiple watermarks for a single image, so that different parts of the image have a different watermark. There is also the need to further develop the robustness of existing watermarking techniques to combat the ever-increasing attacks on watermarks. The coefficients that are chosen in both techniques can also be investigated to see if choosing different coefficients has an effect on the robustness of the watermark and visual quality.