Image analysis – Applications
Reexamination Certificate
1998-04-30
2003-01-07
Johns, Andrew W. (Department: 2621)
Image analysis
Applications
Reexamination Certificate
active
06504941
ABSTRACT:
BACKGROUND OF THE INVENTION
Digital watermarking is a technique to insert a digital identifier into an image so that the identifier can be extracted for the purposes of ownership verification and/or authentication. By ownership verification, we mean that we can extract a digital identifier from a watermarked image that can be identified as being associated with a owner. Authentication refers to the fact that we can detect any change to the watermarked image. Digital watermarking is becoming increasingly important due to the popularity of the usage of digital images on the world wide web and in electronic commerce.
From the perspective of an image viewer, watermarks can be classified into two categories: visible and invisible. Visible watermarking refers to the class of watermarking procedures where a visible stamp, e.g., a company logo, is inserted into an image. The stamp is visible in similar fashion as the watermark to current U.S. dollar bills. U.S. Pat. No. 5,530,759, entitled “Color Correct Digital Watermarking of Images,” to Braudaway et al. describes a method of inserting a visible watermark into an original digital image. Braudaway et al. teaches modifying the brightness or darkness of the original image based on the position of the watermark. The watermark insertion and extraction methodology described in Braudaway et al. includes a random noise component which increases the difficulty of removal of the watermark from the original image by anyone except the authorized user.
An invisible watermark is a digital identifier added to a digital image so that the resulting image is visibly indistinguishable from the original unmarked image. The invisible signature can be extracted or detected through a sequence of image processing operations on the digital image. The article “Secure Spread Spectrum Watermarking for Multimedia,” Tech. Rep. 95-10, NEC Research Institute, 1995 by I. J. Cox, J. Kilian, T. Leighton, and T. Shamoon, describes a method of inserting an invisible watermark into a digital image. The Cox article describes transformation of an original image into a frequency domain representation of the image. From the frequency transformed representation of the image, the method described in Cox picks N frequency components of the image that are visually important and inserts a watermarking signal into these frequency components of the original image as a watermark.
One way to accomplish ownership verification is to associate a user key with a watermark so that the desired watermark can only be extracted from a watermarked image with the appropriate user key. Two conventional watermarking methodologies include: (1) secret key watermarking, that requires that both the owner and receiver possess the same secret key and (2) public key watermarking, that requires the use of two different keys: a private key, and a corresponding public key. The private key is known only to the owner. The public key need not be secret and is used by the receiver of the image to detect the watermark. A problem with secret key watermarking is that key exchange must occur before the actual transmission, typically via a more expensive secret alternative path, or must be arranged when sender and receiver are proximate.
In the article “An invisible watermarking technique for image verification,”, M. M. Yeung and F. Mintzer, Proceedings of ICIP (Santa Barbara, Calif.), October 1997, an authentication watermarking method is described for a secret key system. In the method described in the Yeung article, a secret key is used in combination with a random number generator to generate a look up table. The look up table defines a watermark extraction procedure, which in turn suggests a watermark insertion step through adjustments to the original image. In the watermark extraction step, the extracted watermark is compared to a known watermark to determine if the original image has been modified. Although, the technique described by Yeung can detect changes to the pixel values of a watermarked image, it does not detect changes in image size resulting from cropping or certain scaling algorithms.
A method of invisible watermarking that can be used both for purposes of ownership verification and authentication, that can detect changes in pixel values as well as image size, and that may be used in public key or alternatively, secret key watermarking systems is needed.
SUMMARY OF THE INVENTION
The present invention provides an invisible digital watermarking technique that can serve the two purposes of ownership verification and authentication, that can detect changes in pixel values as well as image size, and that may be used in public key or alternatively, secret key watermarking systems. The present invention includes a watermark insertion procedure used by the image owner and a corresponding extraction procedure used by the receiver of the image. The watermark insertion procedure computes a hash function of a modified image block, a key and various image parameters, and then combines the hashed output with a block of the watermark bitmap, resulting in a combined image block. In the preferred embodiment, the modified image block is the original image block with its LSB's set to zero. As a final step to create a watermarked image block, the combined image block is inserted into a LSB of the modified image.
The watermark extraction procedure takes the watermarked image block and creates two different image blocks: a first image block with the LSB's of the watermarked image block set to zero, and a second image block with the LSB's of the watermarked image block extracted. The first image block, a key and various image parameters are used as inputs to the hash function. Although the inputs to the hash function for the watermark extraction process are different than the inputs to the hash function for the watermark insertion process, the cryptographic hash functions used for both watermark insertion and extraction must be identical. If the hash functions are different, the watermark will not be able to be properly extracted and the extracted watermark image will appear as noise.
The watermark extraction procedure uses the hash function to calculate a digest of values, resulting in a hashed output. The hashed output is combined with the second image block, preferably using an exclusive OR function. The result of the combined hashed output with the second image block is a block of the extracted watermark.
The previously described insertion and extraction methodology may be used for secret key encryption where the same secret key is used for both watermark insertion and extraction. In an alternative embodiment, the methodology described is modified so that the integrity and ownership of the image can be verified using a public key. In this alternative embodiment, a public key encryption step is included after the step combining of the hashed function with the watermark bitmap for the watermark insertion procedure. In addition, for the watermark extraction procedure, a public key decryption step is included before the extraction of the watermark using the reversible exclusive OR logic function. In such a system, the owner of the image inserts a watermark using a private key K′. In the watermark extraction procedure, any person can use the public key K (corresponding to the private key K′) to extract a binary watermark, that will indicate any changes that have been made to the watermarked image.
The present invention provides authentication that detects any change to the watermarked image for both a secret key and public key watermarking system. Detection of change is important for example where an image is to be used as evidence for legal purposes and in electronic commerce of images, where the buyer of an image can be assured that no change to the image has occurred when the image is delivered from the seller to the buyer. If any part of the image is changed, the watermark extraction procedure, according to the present invention, will return an output that indicates the specific parts of
Hewlett--Packard Company
Johns Andrew W.
Nakhjavan Shervin
LandOfFree
Method and apparatus for digital watermarking of images does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for digital watermarking of images, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for digital watermarking of images will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3013422