UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Digital watermarking by DCT coefficient manipulation Sun, Xiaodi 2001

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-ubc_2001-0527.pdf [ 9.54MB ]
Metadata
JSON: 831-1.0051321.json
JSON-LD: 831-1.0051321-ld.json
RDF/XML (Pretty): 831-1.0051321-rdf.xml
RDF/JSON: 831-1.0051321-rdf.json
Turtle: 831-1.0051321-turtle.txt
N-Triples: 831-1.0051321-rdf-ntriples.txt
Original Record: 831-1.0051321-source.json
Full Text
831-1.0051321-fulltext.txt
Citation
831-1.0051321.ris

Full Text

Digital Watermarking by DCT Coefficient Manipulation by Xiaodi Sun Ph.D., University of British Columbia, 1998 M.Sc, Najing University, 1987 B.Sc, Najing University, 1984 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF Master of Science in THE FACULTY OF GRADUATE STUDIES (Department of Computer Science) We accept this thesis as conforming to the required standard The University of British Columbia August 2001 © Xiaodi Sun, 2001 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of fowfey $ U A MA The University of British Columbia Vancouver, Canada DE-6 (2/88) Abstract The advent of digital multimedia and worldwide area networks such as the Internet facilitates efficient distribution, reproduction and manipulation over networked information systems. To discourage the unauthorized copy-ing and distributing of electronic documents, new tools are needed for their tracking and copyright enforcement. Digital watermark, which is an invisible mark embedded in a digital medium, for example a serial number or copyright information and can be retrieved even after attacks such as image processing and lossy compression, is one of the most promising ways for this purpose. This thesis is concerned with analyzing and developing several digital watermarking schemes based on manipulating DCT coefficients of images. In the first scheme, a variant of the watermarking scheme proposed by Langelaar, et al. for JPEG/MPEG streams is implemented based on selectively discard-ing high frequency DCT coefficients. The watermark bits can be recovered by comparing the high frequency energy in difference DCT blocks. The second scheme embeds a watermark into the DCT coefficients of an image during the process of quantization; by introducing a self-reference pattern, the robustness of an watermark can be improved. In the third scheme, pairs of mid-frequency DCT coefficients are selected and modified to embed a watermark. The last scheme is built on the foundation of spread-spectrum communication. After presenting a generic spread spectrum based watermarking scheme, we derive the expectation and variance of the correlation between the investigated im-age and the watermark, from which the performance of our spread spectrum watermarking algorithm is analyzed and is found to be consistent with the experiment results. The watermarking schemes can detect the embedded watermarks in the DCT domain without the help from the original images. Experiment results n show that the embedded watermarks in images can be retrieved successfully even after the JPEG compression and certain other image processing attacks. In addition, our spread spectrum watermarking scheme is capable of embed-ding multiple watermarks into an image and is robust to cropping attack as well as the JPEG compression with a very low quality factor. in Contents Abstract ii Contents iv List of Tables vi List of Figures viii Acknowledgements xi Dedication xii 1 Introduction 1 1.1 Watermarking and Steganography 1 1.2 A Generic Digital Watermarking Process 3 1.3 Organization of this thesis 9 2 Background of Image Watermarking 12 2.1 Spatial domain watermarking 13 2.2 Watermarking in DCT domain 19 iv 2.3 Watermarking in Wavelet Domain 24 2.4 Miscellaneous watermarking algorithms 28 3 Watermarking algorithms by D C T coefficient removal 35 3.1 Watermarking scheme based on discarding D C T coefficients . 36 3.1.1 A modified watermarking scheme 40 3.2 Algorithms based on quantization and coefficient comparison . 41 3.3 Experiment results 44 3.3.1 Watermarking scheme with additional noises 44 3.3.2 Other schemes 50 4 Watermarking algorithms using spread spectrum technique 55 4.1 Introduction to direct sequence spread spectrum 57 4.2 Watermark embedding and decoding 61 4.3 Experiment results 69 5 Conclusion 75 Bibliography 79 v List of Tables 3.1 The minimal re-encode quality factor with which the watermark based on DCT coefficient removal can still be decoded correctly, given a JPEG compression quality factor Qjpeg- The watermark can survive a wider range of JPEG quality factors for a smaller 3.2 The minimal re-encode quality factor with which the watermark based on DCT coefficient removal can still be decoded correctly, given a threshold r. The watermark can survive a wider range of JPEG quality factors for a larger r 50 3.3 The minimal re-encode quality factor with which the watermark based on quantization can still be decoded correctly, given a JPEG compression quality factor Qjpeg- Here SF means using self-reference and NSF means no self-reference. The watermark can survive a wider range of JPEG quality factors when using self-reference 51 vi 3.4 The minimal re^ encode quality factor with which the watermark based on quantization can still be decoded correctly, given a watermark strength scale parameter a. Here SF means using self-reference and NSF means no self-reference. The watermark can survive a wider range and JPEG quality factors for a larger 'a 52 3.5 The minimal re-encode quality factor with which the water-mark based on DCT coefficient comparison can still be decoded correctly, given a JPEG compression quality factor Qjpeg- • • • 52 4.1 The responses of the watermark detector to the correct water-mark and others becomes larger when the value of fi increases. 72 4.2 The average value E(C)oi the DCT coefficients for different values oi fi 73 4.3 Comparison of the responses of the detector to the correct wa-termark and the others for different statistic distributions. . . 74 vii List of Figures 1.1 Generic digital Watermarking encoding process 3 1.2 Generic digital Watermarking decoding process 4 2.1 As n increases, the distribution of Sn shifts further to the right. 15 2.2 Quantization process to embed a watermark. The middle wavelet coefficient f k 2 , i ( m , n ) must be quantized to the nearest vertical bold bar to embed a one and to the nearest dotted line to embed a negative one 26 2.3 D W T pyramid decomposition of an image 27 2.4 A range block, its LSRA and its LSRB- LSRc is defined as their union 30 2.5 Rotation, scale and translation invariant scheme 32 3.1 Bit positions and block definitions in a still image or an I-frame of a video stream 37 3.2 Calculating the energy difference D 38 3.3 Plot of the original image, where we cut a portion of it such that any embedded noise will be more perceptible 46 viii 3.4 Plot of the watermarked images with n — 16 (left) and n = 2(right).Here c = 32, Qjpeg = 75 and r = 10. Noises are more noticeable for n = 2 than for n = 16 47 3.5 Plot of the watermarked images with c = 32 (left) and c = 60(right).Here n = 2, Qjpeg — 75 and r = 1. Noises are more noticeable for c = 60 than for c = 32 48 3.6 Plot of the watermarked images with c = 55 (left) and c = 5(right).Here n = 16, Qjpeg — 75 and r = 1. Block-effect is more noticeable for c = 5 than for c = 55 49 3.7 Plot of the original image "palace" 50 3.8 Plots of the watermarked image. Here n = 16, c = 55 and T = 0.2. Notice that larger values of Qjpeg can give better image quality, but less robustness to JPEG compression. . . . 53 3.9 Plots of the watermarked image. Here n = 16, c = 55 and Qjpeg — 75. Notice that smaller values of r can yield better image quality, but less robustness to JPEG compression. . . . 54 4.1 A generic watermarking process. . 56 4.2 A generic watermark embedding system 62 4.3 A generic detector based on correlation with the spread spec-trum sequence 64 4.4 Plot of the original image (left) and the watermarked image with spread spectrum algorithm (4.14) (right). No visual distortion is observed ' . . 70 ix 4.5 Plot of the cropped image (left) and the JPEG compressed wa-termarked image with compression rate 16 (right). The embed-ded message can still be recovered in these severely distorted images 71 4.6 Plot of the twicely watermarked image. One watermark corre-sponds to seed 300, and another one corresponds to seed 600. 72 4.7 Plot of the watermark detector responses to different water-marks. Peaks occur only when the watermarks correspond to seed 300 and 600 73 x A c k n o w l e d g e m e n t s I would like to express my deepest gratitude to my supervisor, Dr. Son Vuong. Without his advice and support, this thesis would never have been completed. The help from Vuong was not limited to the science; he also supported my personal goal. I also wish to thank Dr. Alan Wagner for his careful reading and insightful comments on my thesis. X I A O D I S U N The University of British Columbia August 2001 xi To my parents, LongGuan and XiaoLong, my wife, Yanping and my daughter, Amanda. v xii C h a p t e r 1 I n t r o d u c t i o n 1.1 Watermarking and Steganography In the last decade, there has been an explosion in the use of multimedia data. Computers and high rate digital transmission facilities are becoming less ex-pensive and more widespread. Digital networks and CD-ROM provide an ef-ficient cost-effective means of distributing digital media. However, all of these advanced technologies have made duplication of original artwork much easier with an unlimited number of copies. In order to protect intellectual property rights, new methods for signing and copyrighting digital data are in demand by artists and publishers. As a result, digital watermarking technology has. become a very popular area of research. The concept of digital watermarking is to sign images or other multi-media by introducing small changes that are imperceptible to the human eye but easily recoverable by a computer program. Generally, these small changes 1 represent the signature of the owner of the image, such as a serial number, or other identifications of the author. Another important requirement of a digital watermark is robustness. That is, it should be possible to retrieve the signature or watermark from an alternated image. Possible alternations of watermarked images include lossy compression, blurring, cropping, geometry transformation, etc. There alternations are called attacks. Digital watermarking is an important and new sub-discipline of com-munication security. In an ideal world, communication may be secured by encrypting the traffic, however this is not always adequate in reality. For ex-ample, the company you are working for may not allow encrypted email, and even so, an encrypted email message between a known criminal and someone else not under suspicion yet does have obvious implications. This is where steganography comes into play. The word steganography derives from Greek language and means "cover writing". It simply takes one piece of information and hides it within another. So while cryptography is about protecting the content of messages, steganography is about concealing their very existence. Digital watermarking is a technique of steganography which place a hidden copyright message in images, music, video, books, etc. Computer files and digital multimedia have redundant or insignificant areas of data,-or holes. By taking advantage of these holes, we can replace them with hidden infor-mation. For example, a recording of a song might contain a plan of escaping from prison, and an image might contain a train whistle or a letter to a friend. Steganographic techniques can trace their history back to antiquity. For 2 example, Gaspar Schott [41] explained how to embed information in music notes: each note represents a letter; David Kahn [12] explained how to use the acrostic method to put a name in the first letters of successive chapters of a book. First publication focusing on watermarking digital images were by Caronni [6] and Tirkel et al [47] in 1993. Since then, digital watermarking has received much attention from the research community and industry and played many important roles in a number of application areas. 1.2 A Generic Digital Watermarking Process There are some common terminologies for digital watermarking which were proposed at the first international workshop on Information Hiding [29] in 1996. A generic digital watermarking process was stated as follows. Every watermarking system consists of the same generic building components: a watermark embedding system and a watermark detection system. Figure 1.1 shows the structure for the watermark embedding process. Watermark (W) Stego-Image (I) Watermarking Algorithm Watermarked Image (!') Secret/Public Key Figure 1.1: Generic digital Watermarking encoding process. 3 The input to the embedded scheme includes the watermark, the stego-image (also often referred as cover or host data) and optionally a secret or public key (usually a seed for a pseudo-random number generator). The wa-termark can be a serial number, copyright information or a logo of a company. Under the assumption that the watermarking algorithm is public and known by interested parties, the public or secret key is necessary to enforce the secu-rity of the watermark. The output of the watermarking embedding scheme is a modified, that is watermarked, image. The generic detection process is shown is Figure 1.2. Using the public or secret key, the detection scheme can determine if there is a watermark in the test-image and recover it, or provide some kind of confidence measure indicating how likely it is for the given watermark at the input to be present in the test-image under inspection. The original image or the watermark may be used in the extraction process depending on the method. Watermark (M) and/or Original Image (1) Test Image (I') 1  Detection Algorithm \ Mark or confidence measure Secret/Public Key Figure 1.2: Generic digital Watermarking decoding process. There are several types of robust copyright watermarking systems. Given 4 an image / , a watermark W and a key K, the embedding process can be de-fined as a mapping of the form: / x K x W —> I and is common to all marking methods. They are differentiated by the detection process as follows. • private watermarking system requires at least the original image. There are two types of these systems. The first type of systems use the original image as a reference to find out where the watermark could be in the possibly distorted image I and then extract the watermark W from I. The second type of systems also require the embedded water-mark for extraction and just give a "yes" or "no" answer to the question: does the test-image I contain the mark Wl (I x / x K x W -> {0,1}). It can be expected that this type of systems are more robust than the others since they convey very little information and more data can be used to embed the one bit mark. Examples of private watermarking include [7, 8, 16]. • Semi-private watermarking answers the same question as the second type of private watermarking, but doesn't require the original image for extraction. It is defined as / x K x W —> {0,1}. The only practical application of the private and semi-private watermarks we can identify is in a court as evidence to prove ownership. Specifically, the number of the original image wants to distinguish among many apparently copies of the cover image in order to identify users who have given away illegal copies. Many of the currently proposed watermarking schemes fall into this categories (cf. [17, 42, 51]). r • Public watermarking requires neither the original image I nor the embedded watermark W. It is also called blind or oblivious watermark-ing, meaning that the embedded watermark can be read without prior knowledge of the cover image. Indeed such systems can extracts n bits of information (watermark) from the marked image: / x K —> W. Ex-amples are given in [14, 20, 44, 45]. We consider the private watermarking schemes are of limited interest due to their narrow range of applications. Since the embedded watermark can only be recovered by one who owns the original, the embedded message can't be extracted by a user. For instance, a user's web browser would not be possible to extract and display a caption such as "do not copy" warning embedded in a download image. In addition, the need of the original image also make oblivious, batch extraction impractical. One might desire a web crawler or a search engine to automatically identify all illegal copies of anyone of the images belong to a particular photo archive, but this is not feasible for the private watermarking system. Even worse, the proof value of such systems is sometimes questionable since it is possible to construct an "original" image a posteriori to make any image appear to contain any watermark. So in this thesis, we are only interested in the public watermark schemes. Another application of digital watermarking is for content and/or au-thor authentication. An example of this scenario is images taken by a presti-gious photographer using a digital camera. The images must be watermarked upon capture so that the clients can be sure that the images they want to 6 purchase have not' been altered. Here the unrestricted distribution of copies of images is much less a concern than verifying an image's origin and content. This is an important issue in the protection of historical artwork and those used in courts of law as evidence. It is critical that very slight changes to the image can be detected and localized, and it is not desirable for the watermark to remain in the image after any attacks on the images such as filtering. In contrast to copyright protection watermarks, which are also referred as robust watermarks, this type of watermarks are known as fragile watermarks. Although most of recent research is about robust watermarks, the issue of fragile watermarking, with focus on content authentication, remains a subject of active research (cf. [18, 51 , 54]) . Different applications pose different requirements on watermarking schemes. However watermark imperceptibility is a common requirement and indepen-dent of the application purpose for all watermarking systems. The embedding process should not introduce any perceptible artifacts in the cover data, oth-erwise the commercial value of the images or other multimedia will depreciate. This is similar to designing lossy compression algorithms since the human visual/auditory system is used in both cases. For all watermarking applications, except authentication watermarking, the robustness is one of the most^ important design issues because it determines the algorithm behavior toward data manipulation and signal processing oper-ations on the host data. The robust watermarks should have these properties: 7 invariance to noise, covariance to geometry transformation and localization. Specifically, the following distortions and attacks should be taken into consid-eration: • Noise (additive, multiplicative, lossy compression, etc.) • Linear and nonlinear filtering (low pass, high pass, bandpass, etc.) • Affine transformation (rotation, translation, scaling, shearing, etc.) • Data reduction (cropping, clipping) • A / D and D/A data conversion (print-scan) • File format conversion (JPEG -» GIF, H.265^ MPEG-2) The other watermarking design issues include: multiple watermarks, collusion attacks, trustworthy detection and automatic searching. After the owner of an image embedded a watermark in it and then sold it to another person. The second owner should also be able to embed his own watermark and extract it afterwards. The watermark should be characteristic of an au-thor, but "collusion attacks" should not be able to detect the watermark by comparing several signals belong to the same author. As mention before, for the second type of private watermarking and semi-private watermarking, the embedded watermark has to be available in the detection process. The system detects if an image is "trustworthy" by verifying if the given watermark is present in the image under inspection. If the original watermark is not re-quired, then the detection process can extract the embedded information and 8 such systems are for example useful for automatic searching on the Internet with a web crawler or intelligent agent. Here it might not only be of interest to find images, but also to clarify them through the embedded watermarks as their identification number. 1.3 Organization of this thesis The goal of the thesis is to survey and develop digital watermarking schemes for data hiding in digital images for the purpose of copyright protection. The techniques implemented in this thesis research fall into two categories: DCT coefficient manipulation and spread spectrum techniques. The organization of this thesis is as follows. Chapter 2 starts with an introduction into the field of digital image watermarking. There are two basic categories for image watermark encod-ing: spatial domain watermarking which embeds watermarks into the spatial domain of an image and spectral domain watermarking which embeds wa-termarks into the spectral domain of an image. So we first introduce the techniques of spatial domain watermarking including least significant bits, patchwork, spread spectrum techniques, etc. Then various digital watermark-ing schemes in DCT domain and wavelet domain are presented. Other mis-cellaneous watermarking algorithms such as fractal, Fourier-Mellin transform and several watermarking algorithms for image authentication will also be described. In Chapter 3, a spatial domain watermarking scheme is implemented 9 using D C T coefficient removal technique. This technique is first proposed in Langelaar, et al [21], but our scheme overcomes its disadvantage that a water-mark bit sometime can't be embedded depending on the local image properties. Two other related watermarking based on D C T coefficient manipulation are also presented, including quantizing and pairing schemes. The scheme based on quantization encodes a watermark into the D C T coefficients of an image during the process of quantization, and its robustness can be improved if a self-reference pattern is used. In the pairing scheme, pairs of mid-frequency D C T coefficients are selected and modified to embed a watermark; a key file is generated during the encoding phase and is used in the decoding phase to retrieve the watermark. Using this approach, it is possible that the original image is not touched and thus no image distortion occurs. In Chapter 4, we start with an introduction to the basic idea of direct sequence spread spectrum. Then we present a generic spread spectrum based watermarking scheme. For our spread spectrum based watermarking scheme the watermark is modulated and spreaded in the 8 x 8 D C T domain as in the J P E G compression, we will also derive the expectation and various of the correlation between the investigated image'the watermark, from which the performance of our spread spectrum watermarking algorithm is analyzed and is found to be consistent with the experiment results. The major advantage of this scheme is capable of embedding multiple watermarks into an image and is robust to cropping attack as well as the J P E G compression with a very low quality factor. 10 Finally, a summary of the major results in this thesis and the potential problems for future research are presented in Chapter 5. ( 11 C h a p t e r 2 B a c k g r o u n d o f I m a g e W a t e r m a r k i n g This chapter presents background material on the state of the art for image watermarking. There are two basic modalities for image watermarking encod-ing: spatial domain techniques which yield spatial watermarks, and frequency domain techniques which yield spectral watermarks depending on the domain of watermark insertion. While most of the spatial watermarking schemes pro-vide simple and effective ways for embedding an invisible watermark into the cover image, they are usually not robust to common image alternations. The frequency domain schemes first transform an image into the frequency domain using Fourier, DCT, wavelet, etc.) and then embed the information directly into the frequency coefficients of the image. The inversed coefficients form the watermarked image. Generally speaking, casting watermarks in the frequency domain can provide more protection under most signal processing and high 12 ratio compression attacks. It can be recognized that most of the current water-marking algorithms are based on some kind of spread spectrum modulation in the spatial, frequency or space-frequency domain. Specifically, small, pseudo-random changes are applied to selected coefficients in the spatial or spectral domain and are later on identified by correlation or correlation-like similarity measures. 2.1 Spatial domain watermarking For most existing commercial products, the watermark is cast in the spatial domain (cf. [1, 7, 46, 47, 42]. Generally speaking, the watermark is embed-ded in the least significant bits (LSB) of image pixels. For example, in their 1993 publication entitled Electronic Watermark, Tirkel et al [47] proposed two watermarking methods for gray scale images. In their first approach, the watermark is in form of an m-sequence derived pseudo-noise code and is em-bedded in the least significant bits of the image pixels. To avoid introducing much visual distortion, the image is first compressed to 7 bits through adap-tive histogram manipulation. This method is in fact an extension to simple LSB coding schemes in which we insert the code information directly into the LSB bit plane. The watermarking decoding is straightforward by comparing the LSB bit pattern with a stored counterpart. The second approach uses LSB addition for embedding the watermark, again in the form of an m-sequence derived code. The decoding process makes use of the unique and optimal auto-correlation function of m-sequence [23]. A modified version of this pa-13 per was published in 1994 [42], which was the first publication that explicitly mentioned and hence defined the term "digital watermarking" In [48], the idea of using m-sequence and L S B addition was extended and improved through the use of two dimensional m-sequences which resulted in more robust watermarks. Let X be a N x M gray-scale image, and a bipolar extended m-sequence from a small key file is uniquely associated with an owner. The sequence fills multiple 8 x 8 pixel blocks to eventually cover the entire original image. The collection of blocks forms the full watermark W. W is then arithmetically added to X to form the watermarked image, Y: Y=X+W. As part of the encoding procedure, the inner product between each watermark block and corresponding marked image block is computed. To verify a possibly forged image Z, the spatial cross-correlation function between Z and W is computed and compared with the previously stored value. A user defined threshold on the magnitude of the change determines whether a block is altered from the original one. Another example is known as the patchwork [1]. In this method, n pairs of points (OJ, bi) are selected randomly to hide bit 1 by increasing the brightness of aj by one and decreasing the brightness of 6j by one simultaneously. Provided that the image satisfies certain statistic properties, the expected value of the sum of the differences between the a^s and <Vs is given by 2n, { 2n for watermarked image 0 for unwatermarked image 14 See Figure 2.1 for the distribution of 5n. A second method presented in [1] is called texture block coding. The watermark is embedded by copying one image texture block to another area in the image with a similar texture. The watermark can be recovered by computing the autocorrelation function. A remarkable feature of this scheme is the high robustness to any kind of distor-tion, since both image areas are distorted in a similar way which means that the watermark recovery by autocorrelation still works. This scheme, however, requires that the image contain relatively large areas of texture; the techniques is also vulnerable to low pass filtering. So the transparency requirement comes at the expense of robustness. 0 2n Figure 2.1: As n increases, the distribution of Sn shifts further to the right. Similar idea as those by Bender et al [1] was proposed by Pitas et al [25, 30, 31]. Consider a N x M gray image / = {xnm} and assume that watermarks S = {snm} is a binary .pattern of size N x M where the number of ones equals the number of zeros. The original image i" is first splited into two subsets of equal size p — N x M/2 as follows 15 B — {%nm ^ I i S n m — 0 } The watermark 5 is superimposed by changing the elements of the subset A by the positive integer factor k, i.e., C = {xnm + k , xnm G A} and the signal image is given by Is = I © C. To verify if the image is watermarked, the mean c of set C and the mean b oi B can be calculated first to obtain the test statistic c-b where ac and cr;, are the standard deviations of set C and B respectively. Then the Null and the Alternative Hypotheses ([22]) H o : There is no watermark in the image (q = 0) H x : There is a watermark in the image (q — 1) can be applied to verify the presence of a watermark by comparing the test statistic with a pre-defined threshold. This scheme is robust to J P E G compres-sion up to a compression ration of 4 : 1 as well as sub-sampling and multiple watermarks. In [20], amplitude modulation was used to embed a watermark into color images. Let s be a single bit to be embedded in an image I = (R, G, B), p = is pseudo-random position within I depending on a secret key. The bit s is embedded by modifying the blue channel B at position p as Bij <r- Bij + (2 5 - \)Lijq, where q is a constant determining the signature strength and Lij is the lu-minance at P. In order to retrieval the embedded bit, a prediction B^ of 16 L the original value of the pixel is computed based on a linear combination of pixel values in a neighborhood around p. Then the difference S between the prediction and the actual value of the pixel is taken 5 = B{j — Bij . The sign of the difference 5 determines the value of the embedded bit. Since the embedding and the retrieval functions are not symmetric, the correct re-trieval is not guaranteed though it is very likely. To reduce the probability of false retrieval, the bit can be embedded multiple times at different locations. The method was shown to be resistant to both classical attacks, such as filter-ing, and geometrical attacks after determining what operations (translation, rotation, etc.) have been applied to produce the tampered image. Moreover, the signature can be extracted without the original image. The spectrum spreading techniques used in RF communications [10, 43] was first employed by Smith, et al [44] in digital watermarking. In their modu-lation scheme, each bit 6, is represented by some basis function fa multiplied by either positive or negative one, depending on the value of the bit. The modu-lated message S = J2i hfai^, y) is added pixel-wise to the cover image N(x, y) to create the stego-image D(x, y) = S(x, y) + N(x, y). The basis functions will always be chosen to be orthogonal to each other, so that the embedded bits do not equivocate. In addition, we assume that the basis functions are also uncorrelated with the cover image, although they are not always so in reality. If they were, we could hide our signal using arbitrarily little energy and still 17 be able to recover it later as follows (D, <f>i) = J2 hifa{x, y)N(x, y) + Y< bifiip, y) ~ h . x,y x,y Different spread spectrum schemes can be obtained by choosing different basis functions fa. In direct sequence spread spectrum, basis function fa is a con-stant G multiplied by a pseudo-random block of +1 and —1 values. Each block fa has a distinct location in the (x, y)-plane. The blocks fa are non-overlapping and therefore trivially orthogonal. They tile the (rr, y) plane without gaps. The embedded bits can be recovered by demodulation with the original modulating function. This scheme is oblivious and robust to various noise attacks. This modulation idea was further extended by Kutter [19]. He investi-gated various efficient ways to watermark digital gray and color images, based on the foundations of spread spectrum communication in the spatial domain. Two different watermark detectors are introduced, the alternative sign detec-tor and the linear correlator detector. A pre-processing step is introduced prior to the watermark extraction process to increase the robustness of the scheme. Furthermore, it is shown that the use of M-ary modulation, instead of binary signaling, is advantageous in the context of digital watermarking. In addition a technique is developed to detect if an image under investigation is watermarked based on the theory of detection of weak signals in non-Gaussian noise, and the concept of self-reference is introduced to identify geometrical image transformations and hence provide a functionality which allows for the design of watermarking schemes resilient to geometrical alternation. Beside spatial domain watermarking related to modulation, it is possible 18 to insert a watermark by modifying certain special characteristics of an image. Knox, et al [13] has developed a watermarking algorithm for half-tone image, which is based on the fact that many different half-tone patterns will produce a perceptually similar gray field in an image. By modifying the half-tone pattern of an image, a watermarking can be incorporated into the image and can be then recovered as follows: a transparent sheet with a certain half-tone pattern is overlaid on a printed version of the watermarked image. Upon sliding the testing sheet into alignment with the printed image, a visible watermark appears, but it is invisible in the printed image itself. Another method is to modify the geometry features of an image [24]. This method is based on a dense line pattern which is generated pseudo-randomly and represents the watermark. Using an edge detector, a set of salient points is obtained in the image. These points are then warped such that most of them are within the vicinity of lines. In the extraction process, the method verifies if a significant large amount of points are in the vicinity of lines. 2.2 Watermarking in DCT domain A first efficient watermarking scheme in spectral domain was introduced by Koch, Burgett, Zhao and Rinfrey [5, 14, 15]. After the image is divided into square blocks of size 8 x 8 for which the DCT is computed, a pair of mid-frequency coefficients from a pseudo-randomly selected block determined by a secret key. The pairs are modified to embed a watermark bit such that the difference of them is either positive or negative depending on the bit value. 19 To survive JPEG compression, the quantization matrix is taken into account when altering the DCT coefficients. This method is oblivious. A frequency domain method for digital watermarking of image proposed in [8] is also based on the idea of spread spectrum communication. The key insight of this work is the realization that in order for watermark to be robust, it must be embedded in the perceptually significant regions of the image despite the risk of protected fidelity distortions. In its most basic implementation, a watermark X consists of a sequence of normally distributed, zero-mean unit-variance random number V to produce the watermarked image V. Three naturally formulae for watermarking insertion are v[ = vt + a%i, v'i = Vi(l + ctXi), or where a is the watermark strength and the vfs are the perceptually significant spectral components. Inversely transforming v\ to form the watermarked image completes the encoding procedure. The authors propose an empirically derived value of 0.1 for a. The scheme can be generalized by introducing multiple scaling parameters as to adapt to the different spectral components and thus reduce visual artifacts. To verify if a watermark is present in the image, one can evaluate the similarity between the recovered watermarked vector X* and the original watermark vector X. The similarity of X and A'* is defined by / v v*\ X • X* y/X* -X 20 where the recovered watermark vector X* is calculated by using formulae X*{i) = -(v'i-Vi), a X*{i) = - f ^ - l ) , or X*{i) = - l o g ( ^ M ) -a In this method, the original image is needed in decoding phase, so it isn't oblivious. If an image has not been watermarked with X, sim is distributed as a zero mean random variable. If X* is slightly different from X (i.e., V is watermarked with X, although slightly altered), then E(sim) » 0. A hypothesis test on sim determines if X is present in the image. Robust-ness tests showed that the method resists to J P E G compression, dithering, fax transmission, printing-photocopying-scanning, multiple watermarking and collusion attacks. Another global method by modulating D C T coefficients is presented in [3]. One first calculates the D C T of the image and then sort them in the order of their absolute magnitude. A percentage of total energy, p, is defined to identify the largest n coefficients that makes up p percent of the total energy. The watermark sequence which is a one-dimensional bipolar binary sequence is added to all the A C coefficients in the list v[ = vl + xl. The percentage p can be adjusted to trade off robustness and imperceptibility. The decoding phase first extracts X* from the test image V: X*(i) = Vi-Vl. 21 Then the similarity between X and X* can be used to verify A'*. Note that this method requires the original image to extract the watermark. A similar method to [3] is given by Piva, et al [32]. The watermark consists of a pseudo-random sequence of M real numbers with normal distri-bution X = {xi,... ,XM}- The DCT coefficients of an entire original image /.are reordered in the zig-zag fashion of JPEG. To decrease the chance of the watermark being perceptible, the first L coefficients are not marked and M coefficients starting at position L + 1 are selected to generate the vector T = {ti,..., £M}- The watermark X is then embedded into T as follows: t• = tt + a\ti\Xi, i = 1,..., M , where a is a user-defined scaling factor. The modified coefficients replace the non-modified coefficients before the intermediate image / ' is reconstructed. Pixels in the watermarked image Y are linear combinations of the pixels in I and / ' as follows: where is a weighting factor factor that takes account the characteristics of the human visual system. To detect the presence of a watermarked X in a test image /*, the correlation Z between the possibly corrupted signed DCT coefficients T* and the watermark is calculated as _ X-T* ,* Z ~ M " M Y ' and compared with a predefined threshold sz. The threshold sz is evaluated 22 directly on the marked image and given as a M 3Mf Experiment results demonstrate that the watermark is robust to several image processing techniques and geometry distortions. Liu, Podilchuk and Zeng [33, 55] introduce perceptual watermarking using the Just Noticeable Difference (JND) to determine an image depen-dent modulation mark. The watermark modulation in either D C T or wavelet transform domain can be described as where X U } V refers to the frequency coefficients of the original image samples Xij, X*V refers to the watermarked image coefficients, wu<v is the sequence of watermark values, and JUTV is the computed just noticeable difference based on visual models. Watermark detection is based on the correlation between the difference of the original image and the image under inspection, the watermark sequence and watermark sequence. Experiments showed that the watermark is extremely robust to J P E G compression, cropping, scaling additive noise, gamma correction and print-scanning. This scheme requires the original .image in detection. A revision is also proposed to avoid the use of the original image in the verification procedure. In this technique, it is assumed that the original image has already been J P E G compressed. A subset called feature vector is denoted by {XQ}. If a D C T coefficient XD is larger that half of its U,V ) (2.1) U,V ) otherwise 23 corresponding quantization table value, Q, it is included in {Xp}: XD G {XD} , if XD > y • The watermark w is a sequence of iV(0,1) random numbers that is added to {xDy. UD = xD + w , xD e {XD} , UD = %D i otherwise. The I D C T of Y D forms the marked image Y. To verify the presence of w in a test image Z, the feature vector {Z^} is obtained. A correlation measure x — c is found between {Z^} and w. c = , a where and a are the mean and variance of the point-wise multiplication of [ZD] and w. c will be distributed roughly according to N(0,1) if w is not in {ZQ}, otherwise it will be much higher. 2.3 Watermarking in Wavelet Domain Various wavelet based schemes have been proposed [16, 17, 53, 50]. The differ-ence between them usually lies in the way the watermark is weighted in order to decrease visual effects. A robust digital image watermarking method using wavelet-based fusion is proposed in [16]. This method assumes that the binary watermark is of 2 4 length A ,^ and consists of elements from the set { — 1,1}. The watermark is embedded into the detail wavelet coefficients of the host image with the use of a key. The number of ones in the key.must be greater than or equal to the size of the watermark. The watermark values can be repeatly embedded in different coefficients if the length of the watermark is less than the number of ones in the key. The encoding procedure has three stages. Stage I computes the L-th discrete wavelet decomposition of the host image to produce a sequence of SL detailed images, corresponding to horizontal, vertical and diagonal details at each of the L resolution levels, and one gross approximation. Stage II considers each resolution level I and coefficient location (m, n). The detailed coefficients are sorted in ascending order (fkui(m,n) < fk2,i{min) — fk3,i{m^n)- ^ the associated value of the key is one, then some middle wavelet coefficient must be quantized appropriately to embed the .binary watermark (See Figure 2.2, where Q is a user pre-defined variable and A = %'(m^^i y Stage III forms the watermarked image by the inverse wavelet transformation of the fused image components. The detection is performed by estimating the watermark bit value from the relative position of the middle wavelet coefficient. It was shown that this method is robust to some common image distortions, such as JPEG compression, additive noise and linear filtering. Xia, et al [53] implemented a multi-resolution watermark for digital images. In the encoding part, an image is first decompose into several bands with a pyramid structure as shown in Figure 2.3 and then a pseudo-random sequence (Gaussian noise) is added to the large coefficients not in the lowest 25 To embed a watermark with Q=4 fkui{m,n) A A /fc2,/(m,n) To embed a 1 To embed a-1 Figure 2.2: Quantization process to embed a watermark. The middle wavelet coefficient fk2!i(m,n) must be quantized to the nearest vertical bold bar to embed a one and to the nearest dotted line to embed a negative one. resolution. Let y(m,n) denote the discrete wavelet transformation (DWT) coefficients not in lowest frequency band. The Gaussian noise N(m,n) with mean zero and variance one is added to y(m, n): y(m, n) =. y(m, n) + ay2(m, n)N(m, n), where a is the watermark strength. The DWT coefficients at the lowest reso-lution are not changed. The inverse DWT forms the watermarked image. The decoding method is hierarchical and the original image is required. One first decomposes the test image and the original one with DWT into four bands ( L L 1 , L H 1 , H L 1 , H H 1 ) , then calculates the cross correlation between the sig-nature added in H H 1 band and the difference of the DWT coefficients in H H 1 26 bands of the test and the original images. If there is a peak in the cross correla-tion, the signature is then detected. Otherwise, compare the signature added in HHI and LHl bands with the difference of the DWT coefficients in the corresponding bands. If there is a peak, the signature is detected. Otherwise, consider the signature added in the HHI, LHl , HLl , and so on. An important advantage of this scheme is that the watermarking method has multi-resolution characteristic and is hierarchical. In the case when the received image is not altered significally, the cross correlation with the whole size of the image may not be necessary, and thus much of the computation can be saved. This scheme is robust to some common image distortion, such as wavelet transform based image compression and image half-toning. LL3 HL3 HL2 LH3 HH3 H L l LH2 HH2 L H l HHI Figure 2.3: DWT pyramid decomposition of an image. The scheme in [53] fails under a DCT-based compression attack (e.g. JPEG), since JPEG quantization table sets most coefficients of high frequency 27 components in each block to zero so that the watermark cast in these coeffi-cients is lost. To overcome this problem, a new scheme to search perceptually significant wavelet coefficients for effective digital watermark casting is pro-posed in [50]. An adaptive watermark hiding method is first developed to determine significant wavelet sub-bands and to select a couple of significant wavelet coefficients in these sub-bands. Then a blind watermark retrieval tech-nique that can detect the embedded image's watermark in the wavelet domain without the help from the original image is described. The basic idea in this blind watermarking algorithm is to truncate selected significant coefficients to some specific values. Experiments showed that the cast watermark can be suc-cessfully retrieved after various attacks including signal processing, geometry transform, noise, JPEG and wavelet compression methods. With the help of original image, the watermark can be detected after more serious attacks. 2.4 Miscellaneous watermarking algorithms There are other miscellaneous watermarking algorithms (cf. [9, 18, 35, 37, 40, 38, 39, 49], etc.). One of them is related to spatial domain watermarking schemes based on fractal image compression proposed by Puate and Jordan [35]. In general term, a fractal coder exploits the spatial redundancy within the image by es-tablishing a relationship between its different parts. They described a way to use this relationship as a means of embedding a watermark. Specifically, the original image is divided into square block Rb, called range blocks, and 28 similarly, into square blocks Db, called domain blocks. The domain blocks are larger than range blocks. The goal of the encoding algorithm is to establish a mapping in such a way that any Rb can be expressed as a set of transforma-tions to be applied on a particular Db. For each range block Rbj, the mapping function consists of a vector Vj, which has its original in Rbj and points to the corresponding Dbj which becomes its matching block (Mi,.)', and an appropri-ate transformation Tj which minimizes the difference between the range block Rbj and the mapped domain block. Decoding is complished by iterating over the coded mapping function using any initial image. The partition of domain blocks where the search is performed is commonly taken as a square region surrounding the Rbj, denoted by LSR (local searching region). Signing an image, consists of a coding-decoding process with variable searching regions.1 Consider two different LSR, A and B (see Figure 2.4), and a third one, C, defined as their union. To sign a bit s,, a range block is randomly selected, and denoted by .{Rb}j. To sign one, Rbj is coded by searching {Mbj} in region {A}j. To sign zero, Rb. is coded by searching {Mb}j in region {B}j. Other-wise, {Rbj, which is not signed, is coded by searching {M&.} in {C}j. The rule to decide if a range block has been signed with a zero, one, or not signed, is determined by examining if Vj belongs to region Aj, Bj or Cj. The algorithm was tested against JPEG compression and showed good robustness down to a compression quality of 50%. A drawback of this technique is the slow speed due to the fractal compression. Ruanaidh, et al [38, 39] proposed a phase based method of conveying 29 Figure 2.4: A range block, its LSRA and its LSRB- LSRC is defined as their union. the watermark information in gray scale digital images. To embed a bit, the phase of a selected coefficient F(kx, k2) of an N\ x A r 2 discrete Fourier transform (DFT) is modified by adding a small value 8: (F(k1,k2)^(F(k1,k2)+S. The condition that the image be real imposes the following additional modifi-cation (F(JV, - ku N2 - k2) *- (F(Ni - ku N2 - k2) - 5, i.e., the phase must satisfy negative symmetry. A DFT coefficient is marked only if its relative power is above a given threshold. Two distinct methods for watermark detection were described. Assuming the original image is available, 30 the first one is simply to compare the phase. The second one which doesn't require the original is to pre-quantize the original phase prior to encoding and use the deviations from these quantized states to convey information. Experiments showed this scheme survives 15:1 JPEG compression. Another publication by Ruanaidh and Pun [40] proposed a Fourier-Mellin transform-based watermarking method which is robust to any combi-nation of rotation, scale and translation transformations. The key idea is to obtain an invariant of an image, which is unaffected by these transformation. The watermarking process is described in Figure 2.5. The first step is to per-form a DFT on an image. One of the DFT properties is that spatial shifts affect only the phase shifts in the frequency domain, but not the amplitude. So keeping only the amplitude for further processing makes the image translation invariant. The second step is to achieve a rotation and scaling invariance by mapping the amplitude from the Cartesian grid to a log-polar grid defined as x = cos 9 , y = eM sin 0 , where (x,y) G R2, fj. G R, and 0 < 9 < 27r. It is easy to observe that for every point (x,y) there exists a corresponding point (fj.,6) and in this new coordinate system scaling and rotation are converted to a translation of \x and 9 coordinates respectively. So one can implement a rotation and scale invariant by applying the DFT of the log-polar Map (LPM) and keeping only the amplitude. Taking Fourier transform of a LPM is equivalent to computing the Fourier-Mellin transform. These two steps results in a rotation, scale and 31 translation (RST) invariant in which a watermark may be safely embedded. After watermark insertion the inverse transform of the previous two step yield a watermarked image. The watermark takes the form of a 2-dimensional spread spectrum signal in the RST transformation invariant domain. This scheme resists to the JPEG compression and is the first published one which was especially designed to resist to geometry attacks. RST invariant Amplitude Phase DFT IDFT Image Figure 2.5: Rotation, scale and translation invariant scheme. An earlier watermarking algorithm, for the purpose of image authenti-cation and tamper detection, is known as the check-sum technique [49]. It is formed from the checksum value of the seven most significant bits of all pixels 32 in an image. This method randomly selects the locations of pixels to contain one bit of the checksum. The last bit of each selected pixel is changed to equal the corresponding checksum bit. To verify if a test image is authentic, the checksum of the image is computed and compared to the values in the locations where the checksum is embedded. Any discrepancy means that the image is not an exact copy the original. Another fragile watermarking scheme for authentication was proposed in [ 1 8 ] . There are three main stages to the watermark embedding procedure. The first stage computes the L-th level discrete wavelet decomposition of the host image to produce a sequence of 3 L detail images, corresponding to the horizontal, vertical and diagonal details at each of the L resolution levels, and a gross approximation at the coarsest level. In the, second stage, the watermark bit stream is embedded by modifying selected wavelet coefficients through an appropriate quantization procedure. The selection of the coefficients is ran-dom and well-spread spatially and throughout each resolution level. In the final stage, the corresponding L-th level inverse wavelet transform of the marked image components is computed to form the tamper-proofed image. During wa-termark extraction, the L-th level discrete wavelet transform is applied to the given image and a quantization function is applied to the key-determined coef-ficients to extract the watermark value W{. To assess the extent of tampering, the tamper assessment function (TAF) is defined by I NW TAF(w,w) = J^w j = 1 where w is the true watermark, w is the extracted watermark, is the length 33 of the watermark, and © is the exclusive-OR operator. The value of TAF is between 0 and 1. The presence of tampering is determined by comparing TAF with a threshold. 34 C h a p t e r 3 W a t e r m a r k i n g a l g o r i t h m s b y D C T c o e f f i c i e n t r e m o v a l In this chapter, we first implement a variant of the watermarking scheme proposed by Langelaar, et al. in [21]. In their paper, they proposed a wa-termarking algorithm for JPEG/MPEG streams that is based on selectively discarding high frequency DCT coefficients. They used a statistic model to derive the probability that a label bit can't be embedded and this model is used for maximizing the robustness against re-encoding and for developing adequate error correcting codes for the label bit string. A disadvantage of this scheme is that we sometime can't embed a label bit depending on the local image properties. The reason is that we can't guarantee that an energy differ-ence between the /c-subregions in either positive or negative. We here propose a scheme such that this difference is always away from zero by a predefined threshold. Consequently, a label bit can always be embedded not depending 35 on the image properties. We further implement two other related watermark-ing schemes based on DCT coefficient manipulation, including quantizing and pairing schemes. The organization of this chapter is as follows. In § 3.1, we first introduce the watermarking algorithm based on discarding DCT coefficients proposed in [21] and a modification of this scheme such that a label bit can always be encoded and decoded correctly. Then we describe the quantizing scheme and pairing scheme in § 3.2. Finally, experiments and analysis are given in § 3.3. 3.1 Watermarking scheme based on discard-ing DCT coefficients Langelaar, et al. have proposed in [21] a watermarking algorithm for JPEG/MPEG streams that is based on selectively discarding high frequency DCT coefficients in the compressed data stream. The watermark bits are encoded in the pattern of DCT blocks in which high frequency DCT coefficients are removed. Specifically, we can first represent a watermark or label as a label bit string L consisting of label bits Lj (j — 1,2,...,/). This label bit string is embedded in an JPEG still image or in the I-frame of an MPEG video stream bit by bit. To provide better security, all 8 x 8 DCT-blocks are shuffled randomly before encoding as shown in Figure 3.1. Each bit out of the bit string is embedded in a label bit-carry-region, or /c-region, in a shuffled image or a shuffled I-frame. The size of a Zc-region, i.e., the value of n, determine 36 the maximal number of label bits that can be encoded in the image. The larger the size of n, the smaller the maximal number of label bits that could be embedded, but the more robust the embedded watermark. Label: QlQ 1 M d o o i o Lc-region 16 8*8 blocks I 8*8 DCT block A A A A A A T J t j r > D / \ B / \ D / \ / \ \ / V \ / Ic-subregion 8 8*8 DCT blocks Figure 3.1: Bit positions and block definitions in a still image or an I-frame of a video stream A label bit is embedded in a /c-region by introducing an "energy" dif-ference between the high frequency DCT-coefficients of the top half of the /c-region (denoted by /c-subregion A) and the bottom half (denoted by B). The energy is computed over a subset of zip-zag scanned DCT-coefficients indicated by S(c): 5(c) = {i E {0,..., 63}|z > c} / 37 where c is the cut-off point, indicating that the DCT coefficients after c will be discarded. The selection of a suitable cut-off point c is essential for the robustness and the visibility of the watermark. The larger the cut-off points are chosen, the less distortion the watermark embedding will introduce. But this will decrease the robustness of the watermark. The energy in ic-subregion A is then defined as 7 1 / 2 - 1 2 EA{c,n,Qjpeg) = J/J {[Oibhjpeg) 6=o ies(c) Here 9ib denotes the z-th non-weighted DCT coefficient in the 6-th block of the 'c-region A (see Figure 3.2). The notation [*]Q- indicates that, prior to the calculation of EAL the DCT-coefficients are re-quantized using the standard JPEG quantization procedure with quality factor Qjpeg- • The energy EB in /c-subregion B can be defined similarly. Figure 3.2: Calculating the energy difference D. 38 Now define the energy difference between the Zc-subregions A and B as D{c,n, QjPeg) = EA(c,n,Qjpeg) - EB(c,n,Qjpeg) Then the value of a label bit can encoded as the sign of the energy difference D. A label bit 0 is defined if D is positive and bit 1 is defined if D is negative. So we can embed a label bit string by manipulating the energy difference D. If label bit 0 must be embedded, all energy after the cut-off point c in the DCT-blocks of Zc-subregion B is eliminated by setting the corresponding DCT-coefficients to zero, yielding D = EA — EB = EA — 0 = +EA If label bit 1 must be embedded, all energy after the cut-off point in the DCT-blocks of Zc-subregion A is eliminated, yielding D = —EB < 0. There is one obvious problem which may occur in the previous algo-rithm. That is, what if the energy difference is zero? As a simple example, for a constant luminance gray image, the energy difference is always zero no matter what the value of cut-off point or the value of n and Qjpeg you use. To minimize the possible failure of the watermarking scheme, Langelaar, et al. [21] have used a statistic model to derive the possibility that a label bit can-not be embedded. The resulting model is used for maximizing the robustness against re-encoding and for developing adequate error correcting codes for the label bit string. 39 3.1.1 A modified watermarking scheme While it is true that the statistic model can reduce the label bit error proba-bility, it is still possible that the failure will occur during watermark encoding or decoding due to a very small energy difference. To overcome this problem, we propose a variant of the watermarking scheme in [21] by introducing some additional noises in the high frequency DCT coefficients such that the energy difference can always be kept away from zero by some threshold, not depending on the local image properties. Let T be a threshold of the energy difference, i.e., we require that energy difference between /c-subregions A and B is greater than r. Since we set the high frequency DCT coefficients zero in one /c-subregion (say A), we need that the energy in the other /c-subregion (say B) be greater than r. There are | DCT blocks in /c-subregion B, so we can add an amount of 2r/n energy into each of these blocks if EB < T. To do so, assuming the cut-off point is c, we can increase each high frequency DCT coefficient after c by Q T a b l £ [ u ] \ J ^ ( k ^ (« = c + 1 ' - ' 6 3 ) -Here QTable is the quantization table determined by quality factor Qjpeg us-ing the standard JPEG quantization procedure. It is easy to show that by discarding high frequency DCT coefficients in one /c-subregion and introduc-ing some amount of noise in the high frequency DCT coefficients in the other /c-subregion, it can be guaranteed that the energy difference D is greater than the threshold r. Thus a label bit can always be embedded. 40 3.2 Algorithms based on quantization and co-efficient comparison In addition to watermarking by DCT coefficient removals, we propose two other schemes based on quantization and comparison of DCT coefficients in a progressive transmission scheme. The first algorithm embeds the watermark bits into an image by mod-ifying the rounding rule for the quantized coefficients such that the resulting coefficients are odd or even, depending on the values of the watermark bits. Specifically, as in § 3.1, the image is first divided into square blocks of size 8 x 8 for which the DCT is computed. Each bit out of the label bit string corresponds to a label bit-carrying-region (Zc-region) in a shuffled image. The mid-frequency coefficients of each 8 x 8 DCT block is indicated by S defined by S(cm, cM) = {i e {0,1,..., 63} | cm < % < cM} , where cm and CM are the margin coefficients between which the zig-zag scanned DCT coefficients will be modified to embed a watermark bit. The parameters of cm and CM are to be selected to obtain a trade-off between perceptual invisi-bility and robustness to image processing techniques! We perform quantization the DCT coefficients which are real number in the following manner. Let 6ib be the i-th non-weighted DCT coefficient in the 6-th block of a /e-region, Lj be the corresponding watermark label bit and A = a.QTable[i\, where QTable[i] is the i-th element of the quantization table determined by the quality factor 41 Qjpeg and a is a scale parameter. Assume the coefficient 9ib satisfies r A < 0lb < (r + 1)A , r = 0, ± 1 , ± 2 , . . . . Then in order to embed the label bit Lj, we quantize 9ib for i € S(cm, CM) and 0 < b < n as follows: ( r A if Lj = 0, r odd or Lj = 1, r even (r + 1)A if Lj = 1, r even or Lj = 1, r odd. The inverse of the quantized DCT coefficients forms the watermarked image. To extract the label bit Lj, which corresponds to a k-region, we first calculate the DCT coefficients 9ib (cm < i < cM and 0 < b < n) of the blocks in the Zc-region. Then we identify whether the quantized coefficient [9ib}QJpeg is close to an odd number or an even number by checking if + 0.5J is odd or even, where [xj represents the largest integer less than or equal to x. Finally, we calculate as follows: 1 if more than half of [0ib\c>jpeg are even 0 otherwise In order to enhance the performance of the watermark extraction pro-cess, we can introduce a concept called self-reference. This concept em-beds an known pattern into the multiple mid-frequency coefficients with the goal of indicating whether the recovered bits are trusted. For example, in the encoding stage, we can make the quantized coefficients [0ib]Qjpeg even for % = cm, cm + 2, cm + 4,..., cM, assuming the difference between cm and cM is even. And the label bit Lj is embedded in the rest coefficients. In the decoding 42 stage, only those DCT coefficients [Oib\Qjpeg whose two direct neighborhoods are even (i.e., only when the neighborhoods are correctly recovered) are taken into account. When their neighborhoods are not even, i.e., they are corrupted, we don't expect the DCT coefficients 0^ can be trusted. So those coefficients are discarded in the decoding stage. Experiments showed that this approach often gives better robustness to JPEG image compression. The second watermarking algorithm is totally different from the other watermarking schemes. Usually, a watermark is embedded by changing data portion of an image in such a way that the watermark is invisible and can be retrieved by a decoding algorithm. Our algorithm tries to remember some characteristics of an image depending on the watermark in a separate file and tries to keep the original image intact. Specifically, from a pseudo-randomly selected DCT block, a pair (poiPi) of mid-frequency coefficients in S(cm,cM) is selected such that the difference of them is maximized. The goal of this maximization is to provide better robustness to watermark attacks. If this maximum is still less than a pre-defined threshold r, then this pair is modified as follows: r r Po = Po - g » Pi = Pi + 2 ' where we assume po < P\ • To embed a bit one, we write the positions of the zig-zag scanned DCT coefficients po and p\ into a file; to embed a bit zero, the positions of p\ and p 0 are written. During the recovery process, the file is used to locate the positions of the pairs and the watermark bits can be determined by checking if the difference between the pairs is positive or negative. In this 43 approach, it is often the case that the original image is untouched. 3.3 Experiment results 3.3.1 Watermarking scheme with additional noises In this sub-section, we implement the watermarking algorithm introduced in § 3.1.1 using C and evaluate the following performance of our watermarking algorithms: • the robustness against attacks such as JPEG compression, and other image processing • the visual impact of the watermark • the size of the watermark. These performance factors are controlled by four parameters: • Qjpeg-, which is the minimum JPEG quality setting up to which the watermark is resistant against re-encoding, • n, which is the number of DCT blocks used to embed a single watermark bit, • c, which represents the lowest DCT coefficient that we permit to be discarded during the label embedding, • r, which is a threshold that the energy difference must be greater than. 44 Now we analyze how these parameters affect the performance of the watermarking algorithm. In all of our experiments, we assume the watermark to be encoded is a string Secret is "CPSC 549"! We first analyze the number n of blocks for encoding a label bit by running the program with c = 32, Qjpeg = 75 and r = 0.5. Let length be the number of chars in the watermark. Then the image has to have 8xlengthxn DCT blocks to embed the watermark. Generally, if we select a larger number value of n, then the watermark will be more robust since the label bits are embedded in more blocks and thus less fragile. For example, if we take n = 16, then we can retrieve the watermark correctly; on the other hand, if we take n = 2 or n — 4, then there is one bit error in the retrieved watermark. This number n of blocks can also affects the visibility of a watermark. To see this effect, we set r = 10 and run the program with n = 2 and n = 16 to obtain the watermarked images shown in Figure 3.4. We can notice that the distortion is less noticeable in the image with n = 16 than that with n = 2 since the energy (for a larger n) is distributed in more DCT blocks so that the noise in each DCT block is smaller. Please note that we cut a portion of the image out (see Figure 3.3) such that you can see the embedded noise more clear. For the same purpose, we set the threshold r very large (10, in real world, you can use some r < 0.01)'. We then study the relationship between the cut-off point c and the performance of the watermark. Since there are two types of blocks in an image, the situation is little bit complicated. For the first type of blocks where we may put some noise in them such that energy difference is greater 45 Figure 3.3: Plot of the original image, where we cut a portion of it such that any embedded noise will be more perceptible. than a threshold, if c is small, then the distributed energy in each block may be too small to survive the rounding operation to the nearest integer in the DCT transformation. In this case, the embedded watermark is usually less visible, but is not very robust. On the other hand, if c is large, then the watermark is generally more visible, but is also more robust. See Figure 3.5 for comparisons. For the second type of DCT blocks, where we discard the high fre-quency DCT coefficients, small value of c can yield more robustness, but less invisibility. On the other hand, large value of C can give less robustness, but also less distortion of the image. See Figure 3.6 for some comparisons. There-fore, smaller values of c will make the noise in those blocks discarding DCT 46 Figure 3.4: Plot of the watermarked images with n = 16 (left) and n — 2(right).Here c = 32, Qjpeg = 75 and r = 10. Noises are more noticeable for n = 2 than for n — 16. coefficients more perceptible and those blocks putting additional energy less perceptible; for larger values of c, the effect is opposite. Generally, we can take c = 55 ~ 60 for most of the cases. We now discuss how the JPEG quality factor Qjpeg is related to the performance of the watermarking algorithm. This factor is the minimum JPEG quality setting up to which the watermark is resistant against re-encoding. We select T = 0.2, n = 16 and c = 55 , and run the program with various values of Qjpeg for the image "palace.pnm" shown in Figure 3.7. The results are shown in Table 3.1 and Figure 3.8. In the table, given Qjpeg, we encode the watermark, then re-compress the image using JPEG with different values of JPEG quality factor and record the minimum of them for which the watermark 47 Figure 3.5: Plot of the watermarked images with c = 32 (left) and c = 60(right).Here n = 2, Qjpeg = 75 and r = 1. Noises are more noticeable for c = 60 than for c = 32. can still be decoded correctly. We can notice that a small value of Qjpeg can provide more robustness of the watermarking scheme, but will degrade the image quality. Qjpeg 90 80 75 70 65 60 50 40 30 20 mini, factor 86 74 74 65 65 56 38 33 27 0 Table 3.1: The minimal re-encode quality factor with which the watermark based on DCT coefficient removal can still be decoded correctly, given a JPEG compression quality factor Qjpeg. The watermark can survive a wider range of JPEG quality factors for a smaller Qjpeg. The relationship between the threshold r and the performance of a watermarking algorithm is obvious: larger the value of r is, more robust but more visible the embedded watermark is. This is illustrated in Figure 3.9 and 48 Figure 3.6: Plot of the watermarked images with c = 55 (left) and c = 5(right).Here n = 16, Qjpeg = 75 and r = 1. Block-effect is more notice-able for c = 5 than for c = 55 . Table 3 .2 , where we watermark the image "palace.pnm" using n = 16, c = 55 , Qjpeg = 75 with various values of r. In the table, we first encode the watermark in the image, then compress this file with JPEG encoding using different values of quality factors and record the minimum of them for which the watermark can still be decoded correctly. From this table, we can see that with a larger value of r, the watermark can survive JPEG compression using a higher compression rate. We have also tested if our watermarking algorithm in § 3.1.1 can survive other image processing attacks. Our experiments demonstrated that the algo-rithm may be robust to some image processing attacks such as blur, motion blur, supernova, sparkle, sharpening, N L filter, destripe, applycanvas, noisify, 49 Figure 3.7: Plot of the original image "palace". T 2 1 0.5 0.1 0.05 0.01 mini, factor 28 35 60 77 85 94 Table 3.2: The minimal re-encode quality factor with which the watermark based on DCT coefficient removal can still be decoded correctly, given a thresh-old r. The watermark can survive a wider range of JPEG quality factors for a larger r. etc. (These filters are given in Gimp [56]). 3.3.2 Other schemes In this sub-section, we implement the watermarking algorithms introduced in § 3.2 to study how these schemes survive JPEG compression attack and if the self-reference pattern can improve the performance of the watermark extraction. 50 For the algorithm based on quantization rule, we first analyze how the JPEG quality factor Qjpeg is related to the performance of the watermark again JPEG compression attack. We encode the image in Figure 3.7 with different values of Qjpeg- We choose cm = 21, CM = 35, a = 1 and the size of Zc-region is four. The encoded watermark message is "UBC". The result is given in Table 3.3, in which given the value of Qjpeg, we encode the watermark in the image, then compress the watermarked image using JPEG with different values of JPEG quality factor and record the minimum of them for which the watermark can still be recovered correctly. We can notice that the small value of Qjpeg can provide more robustness of the watermarking scheme, but at the expense of image quality. Also we can notice that the algorithm with self-reference pattern gives better performance. We also test the relationship between the parameters a and the robustness. The results are shown in Table 3.4, where cm = 21, CM = 35, Qjpeg — 75 and the size of /c-region is four. We again notice that self-reference gives better robustness again JPEG compression. And the value of a can increase the performance of the watermark but it will degrade the image quality as it can be expected. Qjpeg 90 80 75 70 65 60 50 40 30 20 mini, factor: SF 81 60 51 43 36 32 26 20 16 0 mini, factor: NSF 86 72 64 57 49 44 35 28 21 16 Table 3.3: The minimal re-encode quality factor with which the watermark based on quantization can still be decoded correctly, given a JPEG compression quality factor Qjpeg- Here SF means using self-reference and NSF means no self-reference. The watermark can survive a wider range of JPEG quality factors when using self-reference. 51 l/a 1 1.5 2 4 mini, factor: SF 51 68 76 88 mini, factor: NSF 64 76 83 91 Table 3.4: The minimal re-encode quality factor with which the watermark based on quantization can still be decoded correctly, given a watermark strength scale parameter a. Here SF means using self-reference and NSF means no self-reference. The watermark can survive a wider range and JPEG quality factors for a larger a. For the watermarking algorithm based on coefficient comparison in § 3.2, we first study how robust this algorithm is against the JPEG com-pression attack. We choose cm = 21, CM = 35, Qjpeg = 75 and the pre-defined threshold r = QTable[c'm] + QTable[c'M], where c'm and c'M are the zig-zag positions corresponding cm and The encoded message is "computer". We list the results in Table 3.5. Comparing this table with Tables 3.1 and 3.3, we notice that this scheme yields better performance than the watermarking algorithms based on DCT coefficient removal and quantization. In addition, the distortion in the watermarked images is usually less noticeable since most of the /c-regions are untouched. A disadvantage of this scheme is that a secret file which keeps the position and pairing information is needed, since this is not convenient for some applications such as searching images with a specific watermark on Internet. Qjpeg 90 80 75 70 65 60 50 40 30 20 mini, factor 78 54 41 38 34 29 25 21 17 16 Table 3.5: The minimal re-encode quality factor with which the watermark based on DCT coefficient comparison can still be decoded correctly, given a JPEG compression quality factor Qjpeg-52 Figure 3.8: Plots of the watermarked image. Here n - 16, c = 55 and r = 0.2. Notice that larger values of Qjpeg can give better image quality, but less robustness to JPEG compression. 53 r = 0.1 Figure 3.9: Plots of the watermarked image. Here n = 16, c = 55 and QJpeg — 75. Notice that smaller values of r can yield better image quality, but less robustness to JPEG compression. 54 C h a p t e r 4 W a t e r m a r k i n g a l g o r i t h m s u s i n g s p r e a d s p e c t r u m t e c h n i q u e The spread spectrum techniques used in RF communications (cf. [10, 43]) are frequently applied in digital watermarking development (cf. [44, 55, 32, 45, 53, 8]). Through the spread spectrum techniques, signal-to-noise ratio (SNR) is traded for bandwidth: the signal energy is spread over a wider frequency band at low SNR such that it is hard to detect, intercept, or jam. In the context of information hiding or watermarking, the goal is to send a message, the watermark, over a very noisy channel, the image. The explosive interest in developing the spread spectrum based watermarking schemes is due to the fact that spread spectrum signals, which are distributed over a wide range of frequencies and then collected onto their original frequencies at the receiver, are so inconspicuous as to be "transparent". Just as they are unlikely to be intercept, detect or jam in RF communication by a military opponent, so are 55 the watermarks unlikely to be detected or destroyed. One big difference is that in watermarking communication, the channel is very noisy (unless the image is uniform) and largely non-Gaussian. Another difference is that signal transmission in watermarking process doesn't have any connection to the physical world because modulation, transmission and demodulation are usually performed in a purely digital environment. The general model for a watermarking system can be depicted as in Figure 4.1. The input is an N-bit binary information S. The information is modulated and added to the image in some modulation space. The mod-ulation of the input is based on certain spread spectrum techniques such as direct sequence, frequency hopping, chirp, etc. But we will only employ a direct sequence spread spectrum approach in the thesis. After the watermark embedding, the image is released and thus subject to various attacks and alter-nations. The watermarked or probably distorted image is then the input to the demodulator which performs the following two tasks: detect if the image under investigation is watermarked; if so, demodulate the embedded information. Watermark embedding Image processing Watermark decoding B Spread sprectnim modulator Noisy channel Demodulator B Figure 4.1: A generic watermarking process. 56 The organization of this chapter is as follows. In § 4.1, we introduce the basic idea of direct sequence spread spectrum. Then the watermarking algorithm based on spread spectrum is proposed in § 4.2, and the experiment results are presented in § 4.3. 4.1 Introduction to direct sequence spread spec-trum In this section, we give a introduction the direct sequence spread spectrum. Let's consider a binary discrete time communication system with the received signal as a time sequence {SJ}^0 defined by Si = Tbi + rii, where T is the unit chip energy, bi is the sequence of two input symbols which are antipodal binary, i.e., bi G { — 1,1}, and is additive white Gaussian noise with zero mean, i.e., the expectation values satisfy E(m) = 0 , E(ninl+l) = a2S(l). Here a is the standard variance and 8(1) is the dialet function. To determine whether a positive one or a negative one was transmitted, we assume that the transmitter is connected to an information source which yields +l's and -l's with equal probability. In this circumstance, such a receiver is a simple level detector using the theory of Hypothesis Testing [22, 26]: H 0 : +1 was sent if S j > 0; 57 H i : —1 was sent if st < 0. Here z/i = S j is called the decision variable. Its statistic determine the perfor-mance of the receiver. It is not hard to show that yi is a normal (Gaussian) random variable with mean Tbi and variance cr2. Now we modulate each input symbol bi with another ±l-valued se-quence called a spreading sequence { C J } ^ 1 . Depending on the value of 6;, each symbol bi results in the transmission of either Co, C i , . . . , C j V - l , or — Co, — C i , . . . , — C j V - l • Thus each bit of duration T is encoded into a sequence of N chips of duration Tc = T/N. And the received sequence can be written as Sj = Tcbcj + rij , j = 0 , 1 , . . . , N - 1 , *> where T c = ^, E(ri*) = ^ and we omit the subscript i for simplicity. Now we make two assumptions about the spreading sequence {CJ}: • its mean is approximately zero, i.e., X/^ Jo1 cj — 0 ; • its autocorrelation is given by r N, k = 0, N-l E  c3c3+k - { 3=0 0, k^O These two conditions are ideal, but can be closely approached in practice when N is large. This type of sequences are noise-like, thus called pseudo-noise (PN) 58 sequences. To retrieve the transmitted signal, we use a correlation receiver to determine whether a + 1 or —1 was transmitted. The correlation receiver performs the following operation to obtain the decision variable y: N-1 y = JlsjCj, j=0 i.e., N-1 V = Y, (Tcbc3 + nAcj . 3=0 Using the properties of the spreading sequence, it is easy to show that N-1 y = NTcb + nicj , j=o which is normal with mean NTcb — Tb and variance a2. Compared with the non-spreading system above, this result shows that the spreading yields no improvement in the ideal white Gaussian noisy channel. This can be intuitively explained by the fact that the signal bandwidth is increased by a factor of N, although the unit chip energy is decreased by a factor of N. As we will show, however, the power of spectrum spreading is its effect on narrow band or correlated signals. These includes interference, multi-path or signals from other transmitters. Now we assume that there is an interferer in the communication channel, i.e., an unknown constant is added to the transmitted signal. Then we have Sj = TcbCj + Ij + rij , j = 0 , 1 , . . . , N — 1 , where Ij = / is a real unknown constant. Then we calculate the decision variable for our correlation receiver N-1. y= (Tcbcj + ij + n.j)cj. • 3=0 5 9 It is easy to show that N-l N-l y = NTcb + I CJ + £ N 3 c j 3=0 j=0 N-l ~ NTcb + 0 + N3C3 • 3=0 Again the decision variable is normal with mean NTcb = Tb and variance <r2, so the interference is suppressed by the despreading/correlation operation. On the other hand, the decision variable in a non-spread system is normal with a mean of Tb + I, which will render the system useless for | / | sufficiently large. Similar results can be obtained for a multi-path channel with a direct path and a specular (reflected) path which causes another copy of the signal to arrive at a delay of / with unknown attenuation bid + Pbi-icN-i+j, j = 0,1, 1, Sj = < bjCj + pbjCn-t, j = I,..., N — 1 where we assume that / < N, i.e., the delay is less than one symbol duration. Specifically, we can calculate the decision variable N-l Hi = JZ S3C3 3=0 l-l N-l N-l = Nbi + pbi-i cN-I+JCJ + /3bj Cj-iCj + JZ n j C 3 • 3=0 3=1 3=0 This yields, using the properties of Cj, N-l y{ ~ Nbj + 0 + 0 + cjbj •. 3=0 Again the multi-path signal is suppressed by the despreading/correlation, but for the unspread system, this system has severe inter symbol interference (ISI) and will result in a performance loss. 60 Based on the above observation, we can anticipate that spread spectrum techniques can yield a more robust and more imperceptible digital watermark at the expense of less watermark capacity (the number of bits that may be hidden and then recovered). 4.2 Watermark embedding and decoding For our image watermarking, we employ the above direct sequence spread spectrum modulation technique. The basic idea is to spread the signal over all or part of frequencies of an image to increase robustness and resilience to noise. In direct sequence spread spectrum modulation, a binary information is modulated with a binary pseudo-noise sequence (also called chirp sequence). This leads to a spreading of the frequency spectrum of the input signal. Our generic watermark encoding system is described in Figure 4.2. The goal is to embed an N bit long watermark B — {bQ, bi,..., 6JV-I} into an image / . Assume / = {Imn} is an gray image, where (m, n) € Z2 is the spatial location in the Cartesian coordinate system. In general, the pixel values Imn are continuous, however in digital imaging, they are usually coded with 8 bits, which means that they are any integer values between 0 and 255. The watermark embedding process takes place in the watermarking space Q. To project an image into the watermarking space, a transformation X is applied to the image, i.e., x '• —> C(m,n). After the watermark is embedded in the watermarking space, an inverse transformation is performed to obtain the watermarked image, i.e., x~~l '• C(m,n) —> I(k,l). There is no 61 Original Image Projection into watermarking space c _ c Weighting a Inverse projection Watermarked Image Watermark Spread Spectrum W | Key Figure 4.2: A generic watermark embedding system. special constraints on the projection except that the image representation in the watermarking space has to be.two dimensional. To embed an N bit binary watermark B, we employ a set <Pfc of N two dimensional orthogonal functions fa, i 6 {1,..., N}, where k defines the secret key used as initializing seed to generate the set. Each function fa in the set is used to represent one bit value of the watermark. These functions can be defined as the pseudo-noise sequences depending on different keys. To not introduce the inter symbol interference (ISI), i.e., to make the functions orthogonal, it is convenient to design them to be not overlapping. That is, if $ i = {(m, n),Vfa(m, n) ^ 0} is the set of all locations for which the function fa is not zero, then the intersection of all these set $; is an empty set, $ j f| $j = 62 0 , V i = j . Now the watermark can be defined as N w(m,n) = Y^b[a(m,n)<pi(m,n), (4-1) i=0 where a(m, n) is a local scaling factor which adapts the watermark as robust and imperceptible as possible, and b[ is defined by b' = l - 1 , if 6i = 0, " (4.2) 1, if bi = 1. By adding the watermark to the image representation in the water-marking space and applying the inverse projection, we obtain the watermarked image I = X-1(C + w), (4.3) The best way to determine an optimal scaling factor a(m, n) such that the image distortion is minimized whiling maintaining strongest robustness is to employ the human visual system. We, however, use a simple interpolation for a(m, n) in next section. To extract the embedded watermark, the correlation is calculated be-tween the data under investigation C and the modulation function 4>i, as shown in Figure 4.3. The sign of the correlation is used to determine the embedded watermark bit. A positive correlation indicates an embedded bit value of 1 , while a negative correlation indicates an embedded bit value of 0 . We now analyze the correlator statistics by investigating a watermarked and undistorted image C = C + w projected into the watermarking space. For 63 C(m, n) X rt > 0 : bt = 1 Ti < 0 : bi = - 1 \ z3(m,n) 1 <j>i(m,n) Figure 4.3: A generic detector based on correlation with the spread spectrum sequence: a bit bi, the detector statistic conditioned on a fixed set $ f c is given by Ti = <C,(f>i> = <C,(f)i> + <W,<j>i> - Y C{m,n)</)i(m,ri) + ^ w(m,n)<pi(m,n), (4.4) {m,n) (m,n) where < • > is the inner product operator. To study the performance of the watermark detector, we calculate the mean and the variance of the random variable at the output of the detector. It is easy to show that EVi] = EiYl w(m' n)<j>i(m, n)] + E[ C(m, n )&(m, n)}. (4.5) (m,n) (m,n) Substituting (4.1) into (4.5) and using the fact that Si and Sj(i ^ j) are not overlapping give FVi] = # [ £ b[a(rn,n)ti{m,n)} + E[Y, C(m,n)<f>i{m,n)]. (4.6) (m,7i) (m,rc) Assuming that the distribution of Si is symmetric and has zero mean, the second item in (4.6) becomes zero. If we further assume the variance aSi — Var[<f>i] to be 1, then the expectation value becomes (m,n) (4.7) 64 To calculate the variance aSi, we compute the second moment of the detector statistic and subtract the square of its expectation (4.7). The second moment is defined as follows E[r2} = E E 53 w(m,n)(f>i(m,n)-+ 53 C(m,n)(j)i(rn,n) > ,(m,n)6*i (m,n)G* J 53 b\a(m,n)(j>2(rn,n) \ + < E 0(171,12)^(771,11) ,(m,n)e<I>i J l,(m,7i)e*i . , +2 53 b\a(m, n)4>2(m, n) • 53 C(m,n)(pi(rn,n) (m,n)e*j (m,n)G*i It is not hard to derive that if we we assume -E^f] = 1, then 2" E C(m,n)<j)i(rn,n) k (m,ra)€3>i E C(m,n) 2 , (m,n)e*j 2 53 b[a(m,n)(f>2(m,n) 53 C(m,n)4>i(m,n) L (m,n)€*i (m,n)e*i 26^  53 a ( m , n ) C ( m , n ) £ [ < ^ 3 ( m , n ) ] (m,n)G3>i and 53 6-a(m,n)c/>2(m,n) 53 ^ n ) ^ . } ] (m,n)e*i Combining (4.8) to (4.11), we obtain E[r}] = E C2(m,n)+ ^ a2(m,n)E[s{\ (m,n)e*i (m,n)e*j +26,; 51 a(m,n)C(m,n)E [s3(m, n)j , i.e., the variance of the detector is Var [r (4.8) (4.9) (4.10) (4.11) (4.12) E C2(m,n) + 53 a2(m,n) (E [S\\ - l ) , (4.13) (m,n)e*,- (m,7i)6$,-65 where we assume again that the distribution of S j is symmetric and has zero mean (i.e., E[sf] = 0). In order to increase the performance of the watermarking scheme, we should make the expectation of the correlation as large as possible while keep its variance as small as possible. By inspecting the expectation (4.7) and the variance (4.13), we can make the following observations • The expected value depends exclusively on the watermark embedding strength a, which suggests that finding optimal large scaling values is important under the restriction of invisibility of the watermark. • The four-th moment of any probability density function (pdf) is larger than or equal to 1, i.e., E{sf\ > 1 if E[s2} = 1 ([11]). The lower bound is achieved only when the random variables are bilevel. In this case, the last term of (4.13.) vanishes. • The first term of (4.13) depends exclusively on the image in watermark-ing space or the second order moment. So one way to decrease the vari-ance (4.13) is to subtract out the mean of the.image, i.e., C — E[C] —> C. In this circumstance, the second order moment is equivalent to the vari-ance since E[x2] = Var[x] + E2[x] and here E[x] =0. This modification doesn't change the expected value of r,, but may substantially increase the detector performance. We will examine this behavior in next section. The previous discussion is based on a generic watermarking space fi. There can be difference choices of this space. In [1] and [44], the watermark-66 ing space is just correspondent to the spatial domain, i.e., a spatial domain technique. In [32], the DCT domain of the whole image is used as fi, which corresponds to a spectral domain. Specifically, they first compute the DCT coefficients of an N x N image the re-order them into a zig-zag scan. Let a pseudo-random sequence (size of M) represent a watermark bit. After skip-ping the first L lowest DCT coefficients, they embed the watermark into the next M DCT coefficients as follows (see Chapter 2 for details). In our implementation, we also choose the DCT domain as the wa-termarking space fi. However, we take a different approach as that in [32]. Specifically, the image is first divided into square blocks of size 8 x 8 for which the DCT is computed as in the JPEG compression scheme. The DCT co-efficients are re-ordered into a zig-zag scan and we denote the total number of the blocks by K. In order to obtain a trade-off between perceptual invis-ibility and robustness to image processing techniques, we also skip the first L DCT coefficients and only embed our binary watermark bits into the next M DCT coefficients in each DCT block, i.e., T — {^L+I, • • • > *L+M}, where 1 < L, L + M < 64 and N < M. Here we restrict the number N of the the watermark bits is less than M, i.e., N can't be greater than 64. Now given a key generator KEY which generates an integer between L + 1 and L + M without duplicate for each integer i : 0 < i < N — 1, we embed our water-mark B = {bo, b\,..., &AT-I} into the DCT coefficient as follows, for each block K(k = 0,l,...,K-l), ti'(k) = U'(k) + ^(i)|ti(/c)|^ s(fc), z = 0 , l , . . . , i V - l , (4.14) 67 where b\ is defined in (4.2), i' = KEY(i) is determined by the key generator and i, ti'(k) is the i'-th scanned DCT coefficient in k-th DCT block, (3(i) is the scaling parameter, and (s(0), s(l),..., s(K — 1)) is a pseudo-random sequence which can be normal, uniform, bilevel, etc. More precisely, we embed bit bi into the i'-th DCT coefficients of all the DCT blocks, i.e., we spread a bit all over the domain, and the pseudo-random sequence s(k), k = 0,1,..., K — 1 can be obtained by a pseudo-random generator with certain seed. If we write (4.14) in the form of (4.1), then we have a(m, n) = P(i')\ti>(k)\ and fa(m, n) = s(k). Here fa(m,n) is identical for each (m,n), but you can make fa depend on the coefficient location which is unnecessary. To retrieval the embedded watermark, we calculate the correlation (4.4), which is K-l Ti=YJtAk)s{k). (4.15) fc=0 Then a positive correlation indicates a bit 1 and a negative correlation indicates a bit 0. Compared with Piva's DCT-based watermarking scheme [32], our spread spectrum based watermarking algorithm has several advantages. First, since our transformation is performed on 8 x 8 DCT blocks, it is faster and more computational economic when the size of the image is large. This is true even when the fast Fourier transformation is employed. Secondly, our algorithm can embed multiple watermark bits into an image while the scheme in [32] is only limited to one single bit. More importantly, since we employ the spread spectrum technique and the bit is spread over the whole image, the embedded watermark using our scheme may easily easily be recovered if the image has 68 been cropped or translated as well as JPEG compressed. 4.3 Experiment results To illustrate the effectiveness of the proposed watermarking system, we will evaluate its robustness against attacks such as JPEG compression, cropping and multiple watermarking. We will also study the performance of the wa-termarking system with respect to the choices of the scale parameter /?, basis functions fa, etc. One major difference of this spread spectrum watermarking algorithm with those in previous chapter is that it is not only survives JPEG compres-sion, but also cropping attack. In addition, we can embed multiple watermarks in an image without interference. In our first experiment, we insert a secret message, an integer "1987", into the image (Figure 3.3) using the spread spec-trum algorithm. In this algorithm, we set L = 30, L + M = 41 and the scale parameter j3 is a linear interpolation of 0.4 at ti+\ and'2.4 at tL+M- This choice of (3 is obviously not an optimized one, but is better than any constant due to the fact that for higher frequencies more energy can be put in without causing visual distortions. The pseudo-random sequence (s(0), s(l), s(N — 1,)) is generated according to the normal distribution N(0,1). For this configura-tion, we notice that the watermarked image which is shown in Figure 4.4 is indistinguishable from the original image. The watermarked image can resist the JPEG compression attack with compression factor Qjpeg greater than 15, which is a much better result than in Chapter 4 (See Table 3.1). In addition, 69 this algorithm is also robust to cropping, even when the most of the water-marked image is cropped. In Figure 4.5 we can find that the re-JPEGed image with Qjpeg = 16 is very distorted and the cropped image is totally unusable, but we can still recover the embedded message without any bit errors. Figure 4.4: Plot of the original image (left) and the watermarked image with spread spectrum algorithm (4.14) (right). No visual distortion is observed. Another advantage of this spread spectrum scheme is that it can embed several watermarks into an image and can retrieve them without interference. To illustrate this, the original image is first signed with a watermark bit cor-responding to a seed that equals to 300 and the watermarked image is then signed again with another watermark bit corresponding to a seed that equals to 600. The final image is shown in Figure 4.6. To detect the watermarks, we calculate the correlation (4.15) with various watermarks. The responses of the watermark detector to the marks is shown in Figure 4.7. From this figure, 70 Figure 4.5: Plot of the cropped image (left) and the JPEG compressed water-marked image with compression rate 16 (right). The embedded message can still be recovered in these severely distorted images. we find that the responses to the correct watermarks are much larger than the responses to the others, suggesting that the possibility of achieving very low false positive and false negative rates. The more energy we put for a watermark, the more robust the water-mark will be. So if we choose the scaling parameter /3 larger, the watermark will be retrieved with a larger probability of correct recovery. This is partially illustrated by Table 4.1, where j3 is the scaling parameter, mean is the mean value of the detector responses to the various watermarks except the correct, one, std is the corresponding standard deviation, peak is the response of the detector to the correct watermark and ratio is the ratio between the values of peak and std. We can notice that the ratio of the responses of the watermark 71 Figure 4.6: Plot of the twicely watermarked image. One watermark corre-sponds to seed 300, and another one corresponds to seed 600. detector to the correct watermark and others becomes larger when the value of ft increases. p 0.25 0.5 1 1.5 2 3 4 mean -36.42 -34.97 -42.28 -43.91 -52.18 -51.72 -56.67 std 605.9 657.2 839.7 1057.1 1318.3 1835.3 2369.4 peak 4343.9 11107.1 25014.4 38736.9 52390.6 79388.4 106267.1 ratio 7.18 16.9 29.8 36.6 39.7 43.3 44.9 Table 4.1: The responses of the watermark detector to the correct watermark and others becomes larger when the value of ft increases. Another performance related factor is the expectation value E(C) of the image in watermarking space il. We mentioned that one way to decrease the variance of the correlation is to subtract it out the image. However, we 72 x 10 1000 Figure 4.7: Plot of the watermark detector responses to different watermarks. Peaks occur only when the watermarks correspond to seed 300 and 600. didn't see any big difference if we do so in the experiments. In fact', it is easy to observe that the expectation value E(C) in the D C T domain is zero. This can be illustrated by Table 4.2, where we calculate the average value of the related D C T coefficients of the image in Figure 4.4 for different values of /?. 0.25 0.5 1 1.5 2 3 4 E(C) 0.07998 0.09186 0.08912 0.12591 0.10950 ,0.12798 0.16099 Table 4.2: The average value E(C)of the D C T coefficients for different values of p. From (4.13), we may expect that bilevel random variable will probably 73 give the best performance of a watermarking scheme among all random vari-able because the corresponding variance is minimized in such case. But this might be not true since the second term of (4.13) is relatively small, compared with the first term for most images. So which random generator is used to obtain fa is not critical to the performance of a watermarking scheme as long as it has zero mean and its variance is one. This is demonstrated by Table 4.3, where we compare the responses of the watermark detector to the correct wa-termark and others, and the meaning of the parameters mean, std and peak is same as in Table 4.2. No big difference is observed for different random distributions. mean std peak normal 28.23 780.41 24118.1 flat 152.7 870.54 24118.09 bilevel 82.11 804.35 23425.39 Table 4.3: Comparison of the responses of the detector to the correct water-mark and the others for different statistic distributions. 74 C h a p t e r 5 C o n c l u s i o n In this thesis, we have given a brief survey on the state of the art for digi-tal watermarking for images and implemented several watermarking schemes based on DCT coefficient manipulation. From the survey, we notice that there are a large number of publications in image watermarking, but most of them such as patchwork, 2D m-sequence and spread spectrum share similar concepts and consider digital watermarking as communication in non-Gaussian noise. In general, small, pseudo-random al-ternations are applied to certain coefficients in the spatial or spectral domain, and these alternations can later be recovered by correlation or correlation-like similarity measures. As we have noticed, the choice of the watermarking embedding domain is critical to the watermark robustness. Spatial domain schemes are usually less robust towards noise-like attacks, such as lossy JPEG compression, but its big advantage is that the watermark may be easily re-trieved if the image is cropped or translated. On the other hand, the spectral 7 5 domain watermarking schemes are in general very robust to the noise-like at-tacks, but can't survive cropping and translation attacks. In fact, cropping or translation in the spatial domain results in a substantially large distortion in the frequency domain which usually destroys the embedded watermark. In Chapter 3, we presented several digital watermarking schemes not based on spread spectrum technique, but on spectral features. The first scheme is a variant of the watermarking scheme proposed by Langelaar, et al. for JPEG/MPEG streams, based on selectively discarding high frequency DCT coefficients. Our scheme can survive JPEG compression with medium quan-tization factor and other noise-like attacks such as blur motion, sharpening, supernova, etc. In addition, unlike the original scheme, this modified scheme always works independent on the local image properties. Another watermark-ing scheme embeds the watermark bits into an image by modifying the round-ing rule for the quantized coefficients. We found that this simple scheme can also survive JPEG compression and its robustness can be improved by intro-ducing a self-reference pattern. The pairing scheme tries to remember some charastic of an image depending on the watermark in a separate file and tries to keep the original image intact. So this scheme provides a good visual imper-ceptibility, but is sometime inconvenient since a secret separate file is needed during the decoding process. A common disadvantage of these three schemes is as we discussed before that the watermarks are not robust to the cropping and translation attacks and for JPEG attack with a very low quantization factor the confidence measure is very unreliable. 76 Our watermarking algorithm using the spread spectrum technique mod-ulates each watermark bit into certain coefficient of each 8x8 DCT block in the whole image. Since the discrete cosine transform is performed locally to each block, our scheme can survive cropping or translation attack (as long as we know the block positions) as well as the JPEG compression. In addition, we can embed several watermarks into an image and later on retrieve them without interference. Although less information may be embedded into an image, this scheme can survive more severe lossy JPEG compression attack, e.g., with quantization factor as low as 16 without visual distortion. The work of this thesis is certainly not complete. Some of the future problems I plan to work on are: • Human Visual System. For maximal robustness it is important to put as much energy into the watermark as possible under the constraint that the watermark remains invisible. So in order to enhance the robustness of the watermark, the characteristic of the Human Visual System is planed to be exploited to adapt the watermark to the image being signed. For example, we may design the weight function a in (4.1) such that its energy is maximized subject to a required maximal acceptable distortion. • Reed-Solomon code. It is inevitable that there will be some degrada-tion to the embedded watermark when the host image is attacked. In order to compensate for errors due to the channel noise and host image modifications, we believe that it is helpful to apply forward error cor-rection codes such as Reed-Solomon code [36, 2] to the watermark being 77 embedded. By embedding a relatively large amount of data into the host image, the data (watermark) integrity may be ensured. • Video and Audio. Finally, we wish to apply our watermarking al-gorithms to other forms of multimedia such as audio and video with a minimum amount of perceivable degradation. 78 B i b l i o g r a p h y [1] W. Bender, D. Gruhl, N. Morimoto and A. Lu, Techniques for data hiding. IBM Systems Journal, vol. 35, no. 3, (1996), pp. 313-336. [2] R. Blahut, Theory and Practice of Error Control Codes, Addison-Wesley, 1984. [3] F. Boland, J. O'Ruanaidh and D. Dautzenberg, Watermarking digital images for copyright protection, In Proceedings of the International Con-ference on Image Processing and its Applications, Edinburgh, Scotland, July 1995, pp. 321-326. [4] A. Bors and I. Pitas, Image watermarking using DCT domain constraints. In Proceedings of the International Conference on Image Processing , Lausanne, September 1996, pp. 232-234. [5] S. Burgett, E. Koch and J. Zhao, A novel method for copyright labeling digitized image data, Technical report, Frauenhofer Institue for Computer Graphics, Darmstadt, Germany, September, 1994. [6] G. Caronni, Errmtteln unauthorisierter Verteiler Von maschinenlesbaren Eaten, Technical report, ETH Zurich, Switzerland, August, 1993. 79 [7] G. Caronni, Assuring ownership rights for digital images, Proc. Reliable IT Systems, VIS'95, 1995, pp. 251-263. [8] I. Cox, J. Kilian, T. Leighton and T. Shamoon, Secure spread spectrum watermarking for images, audio, and video. In Proceedings of the Inter-national Conference on Image Processing 1996, pp. 243-246. [9] P. Davern and M . Scott, Fractal based image steganography, In Lec-ture notes in computer science: Information Hiding, vol. 1174, Springer, May/June 1996, pp. 279-294. [10] R. Dixon, Spread spectrum system with commercial applications, John Wiley and Sons, New York, 1994. [11] J. Hernandez, F. Perez-Gonzalez, J. Rodriguez and G. Nieto, Performance analysis of a 2-D multi-pulse amplitude modulation scheme for data hid-ing and watermarking still image, IEEE Journal on Selected Areas of Communications, 16(4), 1998, pp. 510-524. [12] D. Kahn, The Codebreakers: The Story of Secret Writing, New York, New York, U.S.A.: Scribner, 1996, ISBN 0-684-83130-9. [13] K . Knox and S. Wang, Digital watermarks using stochastic screens — a halftoning watermark, In Proceedings of the SPIE International Confer-ence on Storage and Retrieval for Image and Video Databases V , San Jose, C A , 1997, vol. 3022, pp. 310-316. 80 [14] E. Koch, J. Rindfrey and J. Zhao, Copyright protection for multimedia data, Digital Media and Electronic Publishing, 1996 [15] E. Koch and J. Zhao, Towards robust and hidden image copyright la-beling, In Proceedings of the Workshop on Nonlinear Signal and Image Processing, Marmaros, Greece, June, 1995. [16] D. Kundar and D. Hatzinakos, A robust digital image watermarking method using wavelet fusion. In Proceedings of the. International Con-ference on Image Processing , 1997, pp. 544-547. [17] D. Kundar and D. Hatzinakos, Digital watermarking using multi-resolution wavelet decomposition, International Conference on Acoustic, Speech and Signal Processing (ICASSP), vol. 5, Seattle, WA, USA, 1998, IEEE, pp. 2969-2972. [18] D. Kundar and D. Hatzinakos, Digital watermarking for telltale tamper-proofing and authentication, Proceedings of the IEEE — Special Issue on Identification and Protection of Multimedia Information, vol. 87, no. 7, July 1999, pp. 1167-1180. [19] M. Kutter, Digital image watermarking: hiding information in images. Doctoral thesis, Swiss Federal Institute of Technology, Lausanne, Switzer-land, 1999. [20] M. Kutter, F. Jordan and F. Bossen Digital watermarking of color images using amplitude modulation, J. of Electronic Imaging, 7(2), 1998, pp. 326-332. 81 [21] G. Langelaar, R. Lagendijk, J. Biemond, Watermarking by DCT Coeffi-cient Removal: A statistical approach to optimal parameter settings, In Proceedings of the SPIE Security and Watermarking of Multimedia Con-tents, San Jose, California, January 25-27, 1999, pp. 1-13, ISBN: 0-8194-3128-1, SPIE, Bellingham, Washington, Eds: P.W. Wong, E.J. Delp. [22] E. L. Lehmann, Testing statistic hypotheses, Wiley, 1987. [23] H.D. Luke, Korrelationssignale, Springer, 1992. [24] M. Maes and C. Overveld,Digital watermarking by geometric warping, In Proceedings of the International Conference on Image Processing (ICIP), vol. 1, 1998. [25] N. Nikolaidis and I. Pitas, Copyright protection of images using robust digital signatures, In Proceedings ICASSP 96, May 1996 [26] A. Papoulis, Probability and Statistics, Prentice Hall, 1991. [27] F. Petitcolas, R. Anderson and M. Kuhn, Information hiding — survey. In Proceedings of the IEEE, special issues on protection of multimedia content, 87(7), (1999), pp. 1062-1078. [28] F. Petitcolas, R. Anderson and M. Kuhn, Attacks on copyright marking systems. Lecture notes in computer science, vol. 1525, (1998), pp. 218-238. [29] B. Pfitzmann, Information hiding terminology, In First International Workshop on Information Hiding, R. Anderson (ed), 1996, pp. 347-350. 82 [30] I. Pitas, A method for signature casting on digital images. In Proceedings of the International Conference on Image Processing , 1996, pp. 215-218. [31] I. Pitas and T. Kaskalis, Applying signatures on digital images, In IEEE Workshop on Nonlinear Image and Signal Processing, pp. 460-463, Neos Marmaras, Greece, June 1995. [32] A. Piva, M . Barni, F. Bartolini and V. Capperllini, DCT-based water-mark recovering without resorting to the uncorrupted original image. In Proceedings of the International Conference on Image Processing, 1997, pp. 520-523. [33] C. Podilchuk and W. Zeng, Watermarking of the JPEG bitstream, In Proceedings of.the International Conference on Imaging Science, Systems and Technology, Las Vegas, Nevada, 1997, pp. 253-260. [34] C. Podilchuk and W. Zeng, Perceptual watermarking of still images, In Proceedings of the workshop on multimedia signal processing, Princeton, New Jersey, USA, June 1997. [35] J. Puate and F. Jordan, Using fractal compression scheme to embed a digital signature into an image, In Proceedings of the SPIE, Video Tech-niques and Software for Full-Service Networks, vol. 2915, Boston, USA, 1996, pp. 108-118. [36] I. Reed and G. Solomon, Polynomial codes over certain finite fields, J. Soc. Indust. Appl. Math., Chapter 8, 1960. 83 [37] S. Roche, J.-L Dugelay and r. Molva, Multi-resolution access control al-gorithm based on fractal coding, In Proceedings of the International Con-ference on Image Processing , 1996, pp. 235-238. [38] J. Ruanaidh, F. Boland and O. Sinnen, Watermarking digital images for copyright protection, In Proceedings of the Electronic Imaging and the Visual Arts, Florence, Italy, February 1996. [39] J. Ruanaidh, W. Dowling and F. Boland, Phase watermarking of digital images, In Proceedings of the International Conference on Image Process-ing, vol. 3, 1996, pp .239-242. [40] J. Ruanaidh and T. Pun, Rotation, scale and translation invariant digital image watermarking. In Proceedings of the International Conference on Image Processing , 1997, pp. 536-539. [41] G. Schott, Schola steganographica: in classes octo distributa. . . Jobus Hertz, printer, 1680, bound with: Casparis Schotti... Technical curiosa . . . Herbipoli, 1665. [42] R. Schyndel, A. Tirkel and C. Osborne, A digital watermark, In Proceed-ings of the International Conference on Image Processing (ICIP), vol. 2, IEEE, 1994, pp. 86^ 89. [43] M. Simon, J. Omura, R. Scholtz and B. Levitt, The spread spectrum communications Handbook, McGraw-Hill, New York, 1994. 84 [44] J. Smith and B. Corniskey, Modulation and information hiding in images. Lecture notes in computer science, 1174, 1996, pp. 207-226. [45] M Swanson, B. Zhu and A. Tewfik, Robust data hiding for images. IEEE DSP workshop, 1996, pp. 37-40. [46] Y.N.K. Tanaka and K. Matsui, Embedding secret information into a dithered multi-level image, Proc. IEEE military communication confer-. ence, 1990, pp. 216-220. [47] A. Tirkel, G. Rankin, R. van Schyndel, W. Ho, N. Mee and C. Os-borne, Electronic water mark, In Proceedings DICTA 1993, December 1993, pp. 666-672. [48] A. Tirkel, R. Schyndel and C. Osborne, A two dimensional watermark, In Proceedings DICTA 1995, 1995. [49] S. Walton, Information authentication for a slippery new age, Dr. Dobbs Journal, vol. 20, no. 4, 1995, pp. 18-26. [50] H.-J. Wang, P.-C Su and C.-C.J. Kuo, Wavelet-based blind watermark retrieval technique, In Symposium on Voice, Video, and Data Communi-cations, Boston, Massachusetts, November 2-5, 1998. [51] R.B. Wolfgang and E.J. Delp, A watermark for digital images, Proceed-ings of the International Conference on Image Processing, pp. 219-222, Lausanne, Switzerland, 1996, IEEE. 85 [52] R.B. Wolfgang and E.J. Delp, A watermark techniques for digital im-agery: Further studies, In Proceedings of the Imaging Science, Systems and Technology, Las Vegas, 1997, pp. 279-287. [53] X. Xia, C. Boncelet and G. Arce, A multi-resolution watermark for digital images. In Proceedings of the International Conference on Image Process-ing, 1997, pp. 548-551. [54] M.M. Yeung and F.C. Mintzer, Invisible watermarking for image verifi-cation, Journal of Electronic Imaging, 7(3), 1998, pp. 578-591. [55] W. Zeng and B. Liu, On resolving rightfull ownerships of digital images by invisible watermarks, In Proceedings of the IEEE International Confer-ence on Image Processing, 1997, Santa Barbara, CA, vol. 1, pp. 552-555. [56] The Gnu Image Manipulation' Program (GIMP) Home Page: http://www.gimp.org 86 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051321/manifest

Comment

Related Items