Scott McCloskey

Cryptography Research Paper

11-9-2000

Hiding Information in Images: An Overview of Watermarking

It's no news to anyone that's reading this that the meteoric rise of the Internet in recent years has significantly increased the availability of all forms of media. Nowhere is this more obvious than in the realm of commercial musical recordings, where Napster and other internet-based distribution systems have made incredible volumes of musical content widely available, all without the consent of the music's originators. This situation, though, is not unique to the music industry, as photographers, filmmakers, and other content-originators all have the same problem to varying degrees. The solution, and even the need for a solution, to this problem of copyright infringement is still a topic that is open to great debate, but there is no debating the fact that some interesting and novel technology has been designed to help. Digital image watermarking, the practice of secretly embedding a piece of information in an image, is one of the more interesting of these technologies, and deserves some consideration. It is the purpose of this paper to give the reader an overview of watermarking and the diverse benefits that it offers. We begin with a brief history of watermarking and then go on to describe the basic components of any watermarking system, different uses for and characteristics of watermarking systems, types of attacks that watermarks are designed to defend against, all followed by a simple example of a watermarking system. We then conclude with an analysis of this watermarking system and an overview of topics of current research in watermarking.

Digital image watermarking is actually a derivative of Steganography, the ages-old practice of covertly transmitting a message from one party to another, typically used by governments and spy organizations. The earliest recorded use of such a method is mentioned in the Histories of Herodotus, where Histiaeus used the scalp of a slave to convey a secret message through hostile territory in the hopes of inciting a revolt against the Persians (Katzenbeisser, 3). The slave's head was shaven and tattooed with the secret message. After sufficient time had passed that his hair had regrown, the slave was sent on his mission, passing through Persian territory without arousing suspicion. When he arrived at his destination, his head was re-shaven to reveal the message.

Further examples, both in fiction and in history, can be found in more modern times. In Mother Night, author Kurt Vonnegut writes about a fictional World War II spy, Howard W. Campbell, Jr., who passes information from American spies in Germany to intelligence agents in the United States by steganographic means. Campbell is the narrator of a propaganda program on a German radio broadcast, where he delivers regular denouncements of the United States to anyone listening. All the while, unbeknownst to the German government, Campbell is also broadcasting a subtext of intelligence information by the placement of pauses, coughs, and mispronunciations in the overt message.

As these two examples have endeavored to illustrate, the covert transmission of information by steganographic means has been practiced for most of the recorded history of western civilization. In certain respects steganography and watermarking are very similar in that both are concerned with the unnoticeable transmission of data in some sort of overt carrier (a digital image in the case of watermarking). There are, however, a number of important dissimilarities that make watermarking a discipline of its own. First, and perhaps most importantly, is that steganography is typically practiced between a source and a unique receiver in a one-to-one relationship, whereas watermarking is practiced between a source and many receivers in a one-to-many relationship (Katzenbeisser, 97). Furthermore, methods of watermarking typically adhere to the Kerckhoff principle of cryptography, where one assumes that attackers know the watermarking algorithm, relying instead on a mutually agreed upon key for security. The security of steganography, as should be clear from either of the two examples presented here, lies almost entirely in the secrecy of the algorithm or method and thus is in direct conflict with Kerckhoff's principle. This is not to say that the secret message could not be encrypted before its transmission, but rather that the existence of the secret message is protected only by the secrecy of the stenographic method.

All watermarking systems have, generically, two main steps: the watermark embedding and watermark extraction. The embedding process takes as input a watermark (the data to be embedded in the image), a carrier signal (the digital image into which the watermark will be embedded), and a key, similar to the keys used in cryptographic systems. The output of the embedding process is a new digital image which contains the watermark.

The reverse process, watermark extraction, is not the same for all watermarking systems. The extraction process, as a minimum, takes the watermarked image and the key as inputs. Depending on the specific watermarking method, the extraction may additionally take as input the original (unwatermarked) image and/or the watermark that is thought to be embedded in the image. The output of the extraction process varies, as well. Some watermarking systems extract the watermark and return it as an output, where others (most often those that take the watermark as an input to the extraction) will return a measure of confidence that the specified watermark is found in the image. The reasons for these different extraction methods will be explained later.

In addition to the generic embedding/extraction steps, watermarking systems have a number of characteristics that can be generically defined. The three most important of these characteristics are the watermark's robustness, payload, and level of perceptibility.

Robustness is simply the notion of how much can be done to the watermarked image in the form of attacks (deliberate and otherwise), such that the watermark can still successfully be extracted from that altered image. In general, a more robust watermark is preferred to one that is less so, but that is not always the case.

The payload of a watermark is the amount of information (measured typically in bits) that can be conveyed in a single image. Payloads of watermarks can vary from one bit of information (which typically indicates whether or not the image contains a specified watermark) to several bytes of information. Obviously, larger payloads are preferable in general, as longer watermarks make possible the embedding of more useful information such as an identification number, copyright statement, etc.

The perceptibility of the watermark is simply the degree to which a viewer of the watermarked image can see the distortion induced by the embedding process. This is certainly affected by alterations to the image, such as magnification, rotation, etc. As with robustness and payload, the perceptibility of the watermark varies based on its intended application; watermarks added to scenic imagery are best if they go unseen, whereas more obvious watermarks are desired for other applications. While not an example of a digital watermark, currency issued by the United States mint carry a number of different and very visible watermarks intended to prevent counterfeiting.

These three characteristics of watermarks are in conflict to a certain degree. Increasing the payload of a watermark, for instance, is likely to reduce that watermark's robustness or increase the level of perceptibility of that watermark (Katzenbeisser, 109). Consequentially tradeoffs are a normal part of designing or choosing a watermarking system for a particular application.

In order to decide on amount of robustness that is required for a watermark to succeed for a given application, one must consider the numerous attacks that might be marshaled against a watermarked image, from the mundane to the deliberate attacks against a known watermark. A few of the more obvious attacks are:

• Image Compression - Lossy compression, such as that included as part of the JPEG standard, can result in the destruction of an image's watermark.
• Geometric transformations - the rotation, translation, sheering, or resizing of an image.
• Image Enhancements - Sharpening, color correction/calibration, contrast modifications, histogram equalization.
• Image Composition - The addition of text, windowing with another image, etc.
• Information Reduction - Cropping, color gamut reduction
• Image filtering and the introduction of noise.
• Digital-to-analog conversion

In addition to these fairly simple attacks, there are also a number of attacks that one might attempt on an image that is known to have a watermark. Some of these more sophisticated attacks are:

• Multiple watermarking - In the case where the watermark contains a copyright notice, the addition of a second copyright notice can create problems. Who was the first to copyright the picture? Which of the two copyright notices is valid?

• Collusion attacks - Multiple recipients of the same carrier image, each containing a different watermark, may be able to produce a version of the image without the watermark by averaging the pixel values of their different images.
• Forgery - Multiple recipients of different images, all with the same watermark (presumably here identifying the owner), could be able to insert that same watermark into other images without the consent of the identified party.

All of these attacks, and others which are not mentioned explicitly here, need to be taken under consideration when choosing a particular watermarking method for an application.

While watermarking is applicable to a large number of different problems, three primary applications have been the driving force behind the current interest in watermarking. Those three applications are copyright enforcement, image authentication, and fingerprinting.

The use of watermarks to ensure copyright enforcement, as has already been mentioned, is by far the largest motivation for watermarking today. Photographers, for instance, can embed some unique identifier (social security number, etc.) into each image that they capture in order to identify themselves as the owner of that image. Others attempting to use these images without the photographer's consent can subsequently be identified by extracting the watermark from the image(s) in question.

The proliferation of the Internet is the largest motivation for these types of watermarks, as images on the Internet are free to be taken and reused by others. It should be clear that the use of a watermark is not effective in, nor intended to prevent someone from reusing an image that is publicly available. Rather the watermark is used to identify the proper owner if and when there is a dispute between two people who claim ownership. Thus, in addition to being robust against common forms of image processing (cropping, rotating, etc.), watermarks containing copyright notices need to be able to identify the unique owner in the event of multiple watermarks. Additionally, since the same person may embed the same copyright notice into a number of different images, such watermarks are susceptible to the forgery attack, though it is unclear why someone would want to embed another person's copyright notice into an image that they did not originate.

In order to provide image authentication, systems use what are known as "fragile" watermarks. A fragile watermark is one that is specifically designed so that any change to the image will result in the destruction of the embedded watermark. One potential application for such watermarks is the insurance industry, where the assurance of image authenticity is important. A digital camera, for instance, can be designed to automatically embed a watermark in each image it takes. Then, in order to prove that the image hasn't been altered since it was taken, one can check to see that the same watermark is intact in an image. While fragile watermarks needn't be (and in fact shouldn't be) robust to image processing attacks, they still may need to be robust to other attacks such as image compression, in the event that compression is an expected event in the image's life. Furthermore, fragile watermarking systems need to be robust against forgery attacks, as unscrupulous individuals may attempt, given a large number of authentic watermarked images, to embed the same authenticating watermark in an image which has been altered.

The third and final popular application for watermarking is the fingerprinting watermark. The use of fingerprint type watermarks in images is similar to the use of serial numbers in the distribution of software, in that both are designed to limit the unauthorized copying of the data (Katzenbeisser, 104). Here, unlike copyright watermarking, the image is embedded with a watermark that identifies uniquely each receiver of the image. As with copyright watermarks, the payload of such a system is simply some unique identifier that associates the image with the recipient. Consequentially, if that image is found to have been illegally copied or distributed, the watermark identifies which of the approved recipients passed this image along without authorization. Fingerprinting watermark systems need to be particularly robust against collusion attacks, whereby the authorized recipients may attempt to average their copies of the image in an effort to remove the watermark and defeat the tracking.

The Patchwork algorithm, perhaps the simplest form of a watermark, is one that provides an effective payload of one bit, that bit being the yes or no answer to the question: does this image contain a given patchwork watermark? The embedding process is begun by pseudo-randomly choosing n ordered pairs of pixels within the image. For each of the n ordered pairs (a_i, b_i), one code value is added to the first pixel in the pair while one code value is subtracted from the second pixel in the pair, giving the watermarked image. Formally,

(a_i, b_i) gets (a_i + 1, b_i - 1)

The seed of the pseudo-random number generator is the key for this watermark.

The extraction process for the patchwork watermark proceeds by choosing (using the same key) the same n ordered pairs of pixels. The receiver then sums the value

(a_i - b_i) for all n values of i. The watermark is detected if this sum is around 2n, and is not detected if the sum is close to zero. As the work "around" indicates, there is actually a threshold used to determine if the sum is close enough to 2n.

The patchwork watermark works based on the validity of the assumption that, given a sufficiently large value of n, the average values of the a's and b's will be close to one another. The introduction of the watermark to the image, then, causes the average value of the a's to increase by one while decreasing the average value of the b's by one. The summation of the differences of the a's and b's detects these changes exactly when the watermark has been added. This assumption, it should be mentioned, can be validated during the embedding process.

In analyzing the robustness of the patchwork watermark, the most obvious observation is that it is rendered useless by any attack that changes the locations of the altered pixels. Rotation, cropping, rescaling, shearing or translation would all destroy the watermark. Furthermore, any attack that changes the values of the image's pixels is likely to destroy this watermark, specifically filtering, sharpening, lossy compression, etc. Finally, since the patchwork watermark gives no indication of the order in which different watermarks were applied, images embedded with patchwork watermarks would be susceptible to a multiple watermarking attack.

As we've already mentioned that the patchwork watermark has a payload of 1 bit, the last principle characteristic to comment on is perceptibility. This particular characteristic is hard to summarize, as it depends on the type of imagery that it is applied to. Since each pixel value is only being changed by one code value (ignoring the chance of a pixel being picked more than once) it is tempting to say that the watermark will go unnoticed. While this is almost certainly true in the case of 8-bit imagery, other images, such as those from facsimile machines, that have fewer levels of quantization will tend to show the watermark more obviously. In general, though, it is probably safe to say that the watermark will be imperceptible in most photographic images.

While the current research in the field of watermarking is large and hard to characterize, a fair amount of it is concerned with applying what we know about the human visual system to make watermarks less perceptible to the human observer. Much of this information about the human visual system is the result of numerous studies designed to make better image compression encoders, particularly for the popular JPEG compression standard. The alterations made to images in the watermark embedding process, after all, are not entirely unlike the (usually) small perturbations made during lossy image compression. It makes sense, then, to apply the lessons learned from JPEG research to make a better watermark, more specifically one that is less visible.

In order to better conceal the watermark from the viewer it is certainly favorable to make alterations to portions of the image where our vision is less accurate, or where it would notice such changes least. A number of psycho-visual studies have shown that contain edges or transitions are more thoroughly scrutinized by our visual system, and that the addition of watermark data there would be more likely to be detected (Kankanhalli, 63). A slightly better situation would be the addition of watermark data to portions of an image containing smooth areas, as they are typically scrutinized less by our visual system. The best situation, according to these studies, is the addition of the watermark data to areas of the image that contain strong textures, such as fields of grass, shag carpet, etc. These facts, then, make it possible to insert the bits of a watermark in the regions of the image where they will be least detectable. This assumes, of course, that it is possible to characterize a particular pixel is part of an edge region, smooth region, or texture region, which is true but beyond the scope of this paper.

It has been the purpose of this paper to describe the basics of watermarking, its history, applications, and the ways in which watermarking systems are evaluated. Hopefully this information has helped prepare the reader for future learnings about particular watermarking systems and introduced some interest in doing so. This knowledge may also be helpful in addressing the important questions that have been or will be raised about watermarking, particularly regarding the admissibility of watermark data in courtrooms, and the possible future standardization of one or a small number of watermarking algorithms.

Works Cited

Kankanhalli, Mohan S., Ramakrishnan, K. R.

Katzenbeisser, S. and Petitcolas, F., editors. Information Hiding: Techniques for

Dittmann, J., Stabenau, M., Steinmetz, R.. Robust MPEG Video Watermarking