IT HAD all the hallmarks of a prizewinning war photograph. Under hostile fire, an armed British soldier towered over an Iraqi man carrying a baby and directed him to take cover. The composition was perfect. Delighted with the image, photographer Brian Walski emailed it to his employer, the Los Angeles Times, who promptly splashed it on the front page of the 31 March 2003 edition. But all was not as it seemed.
A keen-eyed editor on The Hartford Courant 鈥� a sister paper of the Los Angeles Times 鈥� noticed that civilians in the background appeared twice in Walski鈥檚 photo. The Los Angeles Times immediately called Walski for an explanation. Walski confessed he had artificially created the photograph by combining two separate images. Outraged, the paper fired him.
A period of soul searching followed in media circles: if we can鈥檛 trust a seasoned professional like Walski, wondered the pundits, who can we trust? One would assume the Los Angeles Times editors didn鈥檛 publish the fake knowingly, but could they have spotted it more easily and avoided the embarrassment? What if Walski had somehow managed to obscure the duplicated figures that the Courant editor spotted, could the tampering still have been detected before the paper went to press? I believe the answer is yes. Furthermore, along with my colleagues at Dartmouth College in New Hampshire, I have developed the first system that makes the passive detection of digital tampering possible.
Advertisement
Walski is by no means the first to fiddle with photos. Stalin famously had banished party members airbrushed out of state photos. In the early 1980s, National Geographic 鈥渕oved鈥� the Great pyramid at Giza so that all the Giza pyramids would fit on its cover, Time darkened a cover image featuring a police photo of OJ Simpson in 1996 (see page 41), and fashion magazines routinely airbrush pictures of models. All this led me to wonder how many of the hundreds of images that we see daily are frauds? How do newspapers and magazines verify the authenticity of images? What standards have the courts put in place to ensure that digital evidence has not been tampered with?
The answers aren鈥檛 clear-cut. What is clear, however, is that over the past few years, digital tampering 鈥� altering digital images, videos and sound 鈥� has become commonplace, but neither the media nor the courts are prepared for the consequences. Some people have suggested using digital watermarks 鈥� an imperceptible identification code that can be integrated into digital media 鈥� to prevent tampering. If a watermark is inserted into a file at the time of recording 鈥� when a photo is shot, for example 鈥� then tampering can be detected by simply verifying that the watermark has not changed since it was created.
However, there are problems with this approach. To insert a watermark when the picture is taken requires a special-purpose camera. Also, it must be impossible for a third party to remove the watermark. If the watermark can be removed without affecting the quality of the image, then the image could be tampered with and the watermark re-inserted, thus bypassing its purported security. In my opinion, it is currently possible to remove any type of digital watermark.
For example, the creators of the Secure Digital Music Initiative (SDMI), a system designed to protect digital music from piracy, were so confident of its impenetrability that they challenged researchers to crack it (New 杏吧原创, 17 February 2001, p 34). And they did. A team at Princeton University in New Jersey showed exactly how SDMI鈥檚 watermark technology could be circumvented. It seems likely that other digital-watermarking techniques will meet with a similar fate.
Instead, I propose a more holistic approach. It turns out that when you analyse 鈥渘atural鈥� images mathematically, they all have certain properties in common that distinguish them from artificial ones. These properties are mostly imperceptible to the human eye, but show up in the method we use to analyse images. The analysis relies on a technique used in compression systems employed to transmit music and images over the internet more quickly, such as the MP3 and JPEG formats. Most compression schemes rely on transforming the data into a more compact representation using mathematical tricks. An image is broken down into discrete chunks called wavelets. These decompositions, or wavelet transforms, start with a pattern, let鈥檚 call it the 鈥渕other鈥� wavelet, that is repeated in different shapes by stretching and scaling it, to form an approximation to the original image. The smaller you scale this mother wavelet, the more fine-grained the information it represents, and so the more detail is retained in the compressed file (New 杏吧原创, 2 March 1996, p 24). The beauty of this technique is that only the values by which the wavelet is stretched and scaled need be stored in the compressed file. That鈥檚 how the compressed file ends up smaller than the original.
So if digital tampering can visually disturb an image, could it also disturb the compressed version of that image? After an analysis of the wavelet transform of several images, it became clear that it does. At last, it seems we have found our tamperers鈥� Achilles鈥� heel. Almost all digital manipulation alters certain properties of recorded data. So to detect tampering we simply have to discover whether any of these properties have been altered.
At the heart of our approach lies a simple assumption: natural photographs, such as news reportage or holiday snaps, aren鈥檛 a random collection of dots. In the same way that placing a monkey in front of a typewriter is unlikely to produce a play by Shakespeare, placing a random set of pixels onto a screen is unlikely to yield a natural image. Given this assumption, it turns out that there are identifiable patterns in the wavelet transforms of all natural images. For example, the frequency and number of edges 鈥� sudden changes in brightness between neighbouring pixels 鈥� are similar in all sorts of photographs.
In order to detect tampering we must first understand what the wavelet transformation of natural images looks like (see 鈥淪pot the difference鈥�, left). We collected around a thousand natural images from trusted sources, applied a wavelet transformation to each image, and collected information about changes in the brightness across neighbouring pixels. In most cases this has the effect of producing an outline of the different objects in an image. The wavelet transformation is applied at different resolution levels 鈥� depending on the resolution of the original image 鈥� each time stepping up the resolution by a factor of two. At each resolution three sweeps are performed, searching for contrast changes in a vertical, horizontal and diagonal direction. For colour images this process is repeated separately in each of the three colour bands (red, blue and green). We repeated this process on 10,000 randomly chosen images from the web to boost our database.
For each image in the database we calculated the average amount of information measured at each level of resolution and the amount of correlation of bright pixels in each orientation at different resolutions. For example, if a pixel is bright in the horizontal high-resolution pass, is it bright in the horizontal medium-resolution pass? Together, the results formed our trusted values. So, when trying to decide whether or not an image has been digitally manipulated, all you have to do is calculate the properties of its wavelet transforms and compare them with the trusted values. If they are consistent then the image is considered to be natural, but if they are very different, the chances are high that it has been tampered with. For example, natural images often contain information across all orientations and resolutions with certain ratios. But an airbrushed image will have slightly less information at the high-resolution level because it has been blurred over.
So far, we have found eight different statistical properties that are consistent across most natural images, and are difficult for a forger to imitate. But our system is not foolproof and will occasionally throw up false positives, or not recognise a tampered image. The ability to detect traces of digital tampering depends on a number of different factors. For example, the changing of a handful of pixels in a high-resolution digital image is virtually impossible to detect. But overall we have managed to detect various types of tampering with a reasonable degree of accuracy.
False alarms
Depending on the sort of tampering in the image, we have reduced the number of false alarms from 1 in 100 to 1 in 10,000. We have also increased our success rate in the most difficult to detect situations from 50 per cent to 75 per cent. The difference in accuracy depends on both the form and extent of the tampering. So far we have been successful in detecting the following six types of tampering. Splicing: two (or more) portions of an image are digitally combined. Resizing: a portion of an image is enlarged, shrunk or rotated. Printing and rescanning: a photograph is digitally scanned, altered and then reprinted. Double compression: an image is saved directly from a digital camera with a fixed amount of compression, for example as a JPEG, and then altered and saved with a slightly different level of compression. Artificial graphics: an image is created entirely from a computer graphics rendering package and passed off as a natural photograph (see 鈥淐hild pornography鈥�). Steganography: a hidden message is embedded within a digital image in a way that is imperceptible to the human eye 鈥� this is a popular technique for covert communication (see 鈥淗idden messages鈥�).
The remarkable thing is that tampering always disturbs the underlying wavelet statistics and can, more often than not, be detected. As we further refine our understanding of natural images and their statistics, the detection accuracy will continue to improve. There are, of course, some fundamental limitations to our approach. Most importantly, as yet we cannot distinguish nefarious from innocent forms of digital tampering. For example, boosting the contrast of an image and then re-saving it with a slightly different compression ratio. Our algorithm will view this image as having been tampered with even though its content and meaning have been unchanged.
But this sensitivity can be a good thing. When it comes to digital recordings being published by the media or presented in a court of law, I would argue that any form of manipulation is unacceptable. And if a digital image is going to be submitted as evidence, then it should be transferred directly from the camera鈥檚 memory, and any manipulation should be done in the presence of a judge. Though our work is still in the early stages of development, I am confident it will prove critical in helping society contend with the dilemmas of the digital age.
Child pornography
Pornographic images of children under the age of 18 are illegal in many countries. In the US, Congress passed the Child Pornography Prevention Act in 1996, prohibiting any image that appeared to be, or conveyed the impression, of someone under 18 engaged in sexually explicit conduct.
The ban included images such as those in which the head of a minor had been combined with the body of a consenting adult performing an explicit act, by digital splicing or computer generation. But the individuals who made such images argued that the law was unconstitutional, since it was there to protect minors, and no minor was being harmed in these artificial images. In 2002, after a protracted legal battle, the Supreme Court agreed and struck down the law.
The ruling makes it considerably more difficult for law enforcement agencies to prosecute child pornography crimes, since defendants can claim that images are computer generated.
Spotting the genuine images would greatly help the authorities to convict paedophiles. In our database of 10,000 natural images and 5000 computer-generated ones, our system automatically discarded just over half of the computer-generated ones as fakes, greatly narrowing down which are likely to be genuine.
Hidden messages
Message hiding, or steganography, has recently received a lot of attention. Some reports claim terrorists use steganography to communicate secretly under the noses of law enforcement agencies.
A message is hidden by first encoding it as a string of numbers and then invisibly weaving it into the individual pixels of an innocent-looking image. Though this process can slightly alter the colour of a subset of the pixels, it is usually unnoticeable to the naked eye. This process does not encrypt data, merely hiding it, so anybody who knows an image contains a message can extract it. The recipient then reverses the process and the message is extracted. Because the message is invisible, the image can be posted to a website or sent through the internet without raising suspicion.
But as with other forms of digital tampering, hidden messages disturb the statistics of natural images. By analysing the wavelet statistics we have been able to detect, from our own database of 10,000 images, between 50 and 90 per cent of hidden messages. Only one image was mistakenly thought to be hiding a message.
Successful detection depends on a number of factors. Some steganography programs are better than others at hiding messages. Also, the smaller the message being hidden, in comparison with the size of the image it is being hidden in, the harder it is to detect.