Image analysis – Applications
Reexamination Certificate
1998-08-28
2001-08-14
Ahmed, Samir (Department: 2623)
Image analysis
Applications
Reexamination Certificate
active
06275599
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to imperceptible watermarking of images and, more particularly, to watermarking implemented on the compressed version of an image in a way that allows the usage of public key cryptography.
2. Background Description
The image to be watermarked is assumed to be in digital form. An imperceptible watermark (hereafter watermark for short) is defined as an alteration of the data set which is mostly not perceptible to a human, but can be recognized by a machine such as a computer. Otherwise, the watermark should be (mostly) invisible. The general principle of such a watermark has been disclosed, for instance, in “Digital Watermarking for High-quality Imaging”, by M. M. Yeung, F. C. Mintzer, G. W. Braudaway, and A. R. Rao, Proceedings of the IEEE Signal Processing Society Multimedia Workshop, Princeton, N.J., 1997. Here we are interested in fragile watermarks, by which we mean watermarks which allow the recognition that an image is authentic and has not been altered, rather that in robust watermarks which are mainly devoted to establish ownership. Such fragile watermark schemes already exist with several virtues as for example in copending U.S. patent application Ser. No. 09/059,498 to D. Coppersmith, F Mintzer, C. Tresser, C. W. Wu, and M. M. Yeung, filed Apr. 13, 1998 and entitled “Secured Signal Modification and Verification with Privacy Control”. Here we are interested in a fragile watermark scheme which is compatible with image compression. The discussion will be organized around JPEG compressed images, as described in JPEG Still Image Compression Standard by W. B. Pennebaker and J. L. Mitchell published by Van Nostrand Reinhold, New York, 1993. However, anybody versed in the art of computer imaging would readily understand how to adapt this invention to other compression schemes as long as the least visible information content can be extracted and modified. The choice we have made is motivated by the fact that JPEG is a widely accepted International standard for image compression.
A digitized color image could be thought of as a single n
1
×n
2
×N array with N≦3. Here, the picture is supposed to be rectangular with n
1
, pixels in the horizontal direction, n
2
pixels in the vertical direction, and 3 is the minimal number of components for a color image.
Similarly, a digitized gray-scale image could be thought of as a single n
1
×n
2
array. The description of an embodiment of the invention focuses on gray-scale images; however, the invention is readily applicable to other data sets in more general sense, so that the word “image” could be replaced by any other human perceptible data sets such as color images or video. For definiteness, we will assume in the sequel that n
1
=n
2
=512, but more general cases would be treated by an obvious adaptation of what will be presented here. In particular, the essential invisibility of the artifacts generated by this invention should result in even less visibility for color image than for grey-scale images.
Prior Art
Prior work such as “An Invisible Watermarking Technique for Image Verification” by M. M. Yeung and F. C. Mintzer, Proceedings International Conference on Image Processing 1997, pp. II-680-683, describes watermarking schemes where the owner of a data set incorporates an imperceptible watermark into the data set. In “The Trustworthy Digital Camera: Restoring Credibility to the Photographic Image” G. L. Friedman, IEEE Trans. on Consumer Elec., vol. 39, no. 4, pp. 905-910, 1993, and in U.S. Pat. No. 5,499,294 by G. L. Friedman, a digital camera is proposed which uses cryptography to create a signature for authenticating the images generated. In the invention of Friedman, a coded message is attached to the picture to allow the authentication.
It was argued that it is better to incorporate the authenticating message into the picture in U.S. patent application Ser. No. 09/059,498 to D. Coppersmith et al., where solutions to do so were proposed. In U.S. patent application Ser. No. 08/918,163 to S. Shimizu, M. Numao and N. Morimoto, filed Aug. 25, 1997 and entitled “A System for Embedding Authentication Information into an Image and an Image Alteration Detecting System”, the signature of part of an image is embedded into another part of an image.
Image watermarking algorithms have been proposed which modify the DCT coefficients as for example in “Transparent robust image watermarking” by M. D. Swanson, B. Zhu and A. H. Tewfik, Proceedings of the Int. Conf. on Image Proc., 1996, vol 3, pp. 211-214 and in “Hidden signatures in images” by C. T. Hsu and J. L. Wu, Proceedings of the Int. Conf. on Image Proc., 1996, vol.3, pp.223-226. However, these algorithms differ from the present invention in the following ways:
1. In the above prior art, the emphasis is on robust watermarks, where some error in the watermark is tolerated, whereas the current invention is used as fragile watermarks where any error in the authentication implies that the image has been tampered with.
2. In the above prior art, the DCT coefficients rather than the quantized DCT coefficients are modified in the watermarking procedure. This results in a watermark which will be changed when JPEG compression is applied by the image and thus cannot be used as a fragile watermark.
3. In the above prior art, the watermark does not depend on the image itself. This allows a malicious party to modify the image while retaining the watermark and thus resulting in an image which is still authentic. Therefore these algorithms cannot be used to test whether the image has been tampered with.
Problems to be Solved
Because of the huge size of color and even grey-scale images, and the need of lots of them in industries like car insurance or the press, there is a great advantage in keeping all images in a compressed form, for instance in the JPEG standard. If the authentication message is attached to the picture as in Friedman's invention, one can as well create the message on the basis of the compressed version of the image. What the present invention achieves is to carry over this possibility to a watermarking scheme which incorporates the authentication message in the picture compressed using a lossy compression scheme (for lossless compression schemes, one can use any watermarking scheme for uncompressed images, as in the disclosure by Coppersmith et al.). The watermarking scheme proposed here produces very faint modifications of the image which are mostly imperceptible to the eye.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a watermarking method that involves mostly invisible artifacts and is sensitive to any modification of the picture at the level of precision rendered by the compressed version of the image.
According to the invention, the image is compressed according to a known compression standard, such as the JPEG standard, and with a fixed quality setting. Using the JPEG standard, the original image is cut into blocks to which the Discrete Cosine Transform (DCT) is applied and the DCT coefficients subsequently quantized. The watermark according to the invention is applied to the quantized DCT coefficients. This is done using an encryption function, such as a secret key/public key algorithm. The JPEG compression is then completed using a lossless compression scheme, such as Huffman coding, to produce the compressed and watermarked image. Authentication of the compressed and watermarked image begins with a lossless decompression scheme to obtain the set of quantized DCT coefficients. The coefficients are authenticated, and the DCT output of each block is dequantized. If necessary, an inverse DCT is applied to each block to output the decompressed watermarked image.
REFERENCES:
patent: 6037984 (2000-03-01), Isnardi et al.
patent: 6064764 (2000-05-01), Bhaskaran et al.
Adler Roy L.
Kitchens Bruce P.
Tresser Charles P.
Wu Chai W.
Ahmed Samir
International Business Machines - Corporation
Kaufman Stephen C.
McGuireWoods LLP
LandOfFree
Compressed image authentication and verification does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Compressed image authentication and verification, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compressed image authentication and verification will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2505721