Fragile watermarks for detecting tampering in images

• US 6,064,764 A
• Filed: 03/30/1998
• Issued: 05/16/2000
• Est. Priority Date: 03/30/1998
• Status: Expired due to Term

• Current Assignee: Seiko Epson Corporation (Seiko Group)
• Original Assignee: Seiko Epson Corporation (Seiko Group)
• Inventors: Bhaskaran, Vasudev, Ratnakar, Viresh
• Primary Examiner(s): Tadayon, Bisan
• Assistant Examiner(s): AZARIAN, SEYED H
• Application Number:
  US09/052,041
• Time in Patent Office: 778 Days
• Field of Search: 382/100, 382/183, 382/232, 382/235, 382/238, 382/239, 382/243, 382/244, 382/245, 382/246, 358/426, 358/261.1, 358/261.2, 358/261.3, 358/427, 358/261.4, 358/428, 358/430, 358/431, 358/432, 713/176, 380/54, 380/10, 380/232
• US Class Current: 382/183
• CPC Class Codes: G06T 1/0042 Fragile watermarking, e.g. so as to detect tampering
• CPC Class Codes: G06T 2201/0052 Embedding of the watermark in the frequency domain
• CPC Class Codes: G06T 2201/0061 Embedding of the watermark in each block of the image, e.g. segmented watermarking
• CPC Class Codes: H04N 1/32154 Transform domain methods H04N1/32309 takes precedence
• CPC Class Codes: H04N 1/32187 with selective or adaptive application of the additional information, e.g. in selected frequency coefficients
• CPC Class Codes: H04N 1/32277 Compression
• CPC Class Codes: H04N 1/32283 Hashing
• CPC Class Codes: H04N 2201/3236 Details of authentication information generation
• CPC Class Codes: H04N 2201/327 which are undetectable to the naked eye, e.g. embedded codes
• CPC Class Codes: H04N 2201/3281 Encryption; Ciphering

Abstract

A watermarking scheme for images which includes techniques for inserting and extracting fragile watermarks in the frequency domain and for determining whether an image so watermarked has been tampered with. Watermark insertion is accomplished by embedding the bits of a digital signature of a hash function of the image in the frequency coefficients of the image. Tamper detection is accomplished generally as follows: the fragile watermark which was embedded during the watermark insertion process is extracted from the image; the hash function of the image is computed as in the insertion process; it is verified using a public key whether the extracted watermark is a valid signature of the hash value. If so, then there is assurance that the image has not been tampered with. Otherwise, there is reason to conclude that the image has been tampered with.

Claims

1. A method of watermarking a compressed digital image, comprising the steps of:

partially decoding the compressed digital image to generate a plurality of data blocks, each block having a plurality of transform coefficients;

determining whether to embed a watermark bit in each block based on one of the plurality of transform coefficients in that block and a number of watermark bits remaining to be embedded in the digital image;

computing a watermark, having a plurality of bits, for the entire digital image by applying a digital signature algorithm and a secret key; and

embedding a watermark bit in each block for which it was determined to do so in said determining step by setting the one of the plurality of transform coefficients in that block to match a corresponding bit of the computed watermark.

2. The method of claim 1, wherein the one of the plurality of transform coefficients in each block is the transform coefficient representative of the highest vertical frequency and highest horizontal frequency in that block.

3. The method of claim 1, wherein said step of computing the watermark further comprises the step of:

setting to zero at least one bit of the one of the plurality of transform coefficients in each block for which it is determined in said determining step to embed a watermark bit.

4. The method of claim 3, further comprising the step of:

encoding the plurality of blocks after said embedding step is completed to re-compress the watermarked image.

5. The method of claim 3, wherein said of computing the watermark further comprises the step of:

updating a hash value at each block by applying a hash function at each block, wherein the hash value computed at a last block is the multiple-bit hash value representative of the entire digital image.

6. The method of claim 5, wherein said step of computing the watermark further comprises the steps of:

obtaining a quantizer of the one of the plurality of transform coefficients in each block; and

multiplying the one of the plurality of transform coefficients in each block by its quantizer.

7. A method of watermarking a compressed digital image, comprising the steps of:

computing a watermark, having a plurality of bits, for the entire digital image, comprising the steps of;

partially decoding the compressed digital image to generate a plurality of data blocks, each block having a plurality of transform coefficients;

obtaining a quantizer of the one of the plurality of transform coefficients in each block;

multiplying the one of the plurality of transform coefficients in each block by its quantizer;

determining whether to embed a watermark bit in each block based on one of the plurality of transform coefficients in that block that is representative of a highest vertical frequency and a highest horizontal frequency in that block and a number of watermark bits remaining to be embedded in the digital image;

setting to zero at least one bit of the one of the plurality of transform coefficients in each block for which it is determined in said determining step to embed a watermark bit;

updating a hash value at each block by applying a hash function at each block, wherein the hash value computed at a last block is a multiple-bit hash value representative of the entire digital image; and

applying a secret key and a digital signature algorithm to the multiple-bit hash value to compute the watermark; and

embedding a watermark bit in each block for which it was determined to do so in said determining step by setting the at least one bit of the one of the plurality of transform coefficients in that block to match a corresponding bit of the computed watermark.

8. A method of detecting tampering of a compressed watermarked image, comprising the steps of:

partially decoding the compressed watermarked image to generate a plurality of data blocks, each block having a plurality of transform coefficients;

determining each block in which a watermark bit is embedded;

extracting, from each block for which it was determined in said determining step to be an embedder of a watermark bit, at least one bit of one of the plurality of transform coefficients in that block to generate an extracted watermark;

computing a hash value of the digital image by applying a hash function at each block based on a zeroed value of the at least one bit of one of the plurality of transform coefficients in that block, wherein the hash value computed at a last block is a multiple-bit value representative of the entire digital image; and

applying a digital signature verification algorithm to the extracted watermark and the multiple-bit computed hash value and a public key to determine whether the compressed watermarked image has been tampered with.

9. The method of claim 8, wherein the one of the plurality of transform coefficients in each block is the transform coefficient representative of the highest vertical frequency and highest horizontal frequency in that block.

10. An image capturing device, comprising:

a sensor for capturing light and converting the light into an analog image signal;

an analog-to-digital converter for converting the analog image signal to a digital image; and

a digital image processor for compressing the digital image to generate a plurality of data blocks, each block having a plurality of transform coefficients, determining whether to embed a watermark bit in each block based on one of the plurality of transform coefficients in that block and a number of watermark bits remaining to be embedded in the digital image, computing a watermark, having a plurality of bits, for the entire digital image, and embedding a watermark bit in each block for which it was determined to do so by setting the one of the plurality of transform coefficients in that block to match a corresponding bit of the computed watermark.

11. The image capturing device of claim 10, wherein said digital image processor sets to zero at least one bit of the one of the plurality of transform coefficients in each block for which it is determined to embed a watermark bit.

12. The image capturing device of claim 11, wherein said digital image processor encodes the plurality of blocks after the watermark bit embedding is completed to re-compress the watermarked image.

13. The image capturing device of claim 11, wherein said digital image processor updates a hash value at each block by applying a hash function at each block, wherein the hash value computed at a last block is the multiple-bit hash value representative of the entire digital image.

14. The image capturing device of claim 11, wherein said digital image processor obtains a quantizer of the one of the plurality of transform coefficients in each block and multiples the one of the plurality of transform coefficients in each block by its quantizer.

15. A computer system including a processor and a memory having a computer-readable readable program code embodied therein for causing the processor to detect tampering of a compressed watermarked digital image by performing the steps of:

partially decoding the compressed watermarked image to generate a plurality of data blocks, each block having a plurality of transform coefficients;

determining each block in which a watermark bit is embedded;

extracting, from each block for which it was determined in said determining step to be an embedder of a watermark bit, at least one bit of one of the plurality of transform coefficients in that block to generate an extracted watermark;

computing a hash value of the digital image by applying a hash function at each block based on a zeroed value of the at least one bit of one of the plurality of transform coefficients in that block, wherein the hash value computed at a last block is a multiple-bit value representative of the entire digital image; and

comparing the extracted watermark with the multiple-bit value by applying a digital signature verification algorithm to determine whether the compressed watermarked image has been tampered with.

16. The computer system of claim 15, wherein the one of the plurality of transform coefficients in each block is the transform coefficient representative of the highest vertical frequency and highest horizontal frequency in that block.

17. A method of watermarking a digital image, having a plurality of pixels, comprising the steps of:

computing a watermark, having a plurality of bits, for the entire digital image, comprising the steps of;

determining whether to embed a watermark bit in each pixel based on one of a plurality of bits representative of that pixel and a number of watermark bits remaining to be embedded in the digital image;

setting to zero at least one bit of each pixel for which it is determined in said determining step to embed a watermark bit;

updating a hash value at each pixel by applying a hash function at each pixel, wherein the hash value computed at a last pixel is a multiple-bit hash value representative of the entire digital image; and

applying a secret key and a digital signature algorithm to the multiple-bit hash value to compute the watermark; and

embedding a watermark bit in each pixel for which it was determined to do so in said determining step by setting the at least one bit of that pixel to match a corresponding bit of the computed watermark.

18. The method of claim 17, wherein the at least one bit is the least significant bit.

19. A method of detecting tampering of a watermarked digital image, having a lo plurality of pixels, comprising the steps of:

determining each pixel in which a watermark bit is embedded;

extracting, from each pixel for which it was determined in said determining step to be an embedder of a watermark bit, at least one of a plurality of bits representative of that pixel to generate an extracted watermark;

computing a hash value of the digital image by applying a hash function at each pixel based on a zeroed value of the at least one bit of that pixel, wherein the hash value computed at a last pixel is a multiple-bit value representative of the entire digital image; and

applying a digital signature verification algorithm to the extracted watermark and the multiple-bit computed hash value and a public key to determine whether the compressed watermarked image has been tampered with.

20. The method of claim 19, wherein the at least one bit is the least significant bit.

21. A method of watermarking a compressed digital image, comprising the steps of:

adding a visible watermark;

computing an invisible watermark from the digital image and the visible watermark, comprising the steps of;

partially decoding the compressed digital image to generate a plurality of data blocks, each block having a plurality of transform coefficients;

obtaining a quantizer of the one of the plurality of transform coefficients in each block;

multiplying the one of the plurality of transform coefficients in each block by its quantizer;

determining whether to embed an invisible watermark bit in each block based on one of the plurality of transform coefficients in that block that is representative of a highest vertical frequency and a highest horizontal frequency in that block and a number of invisible watermark bits remaining to be embedded in the digital image;

setting to zero at least one bit of the one of the plurality of transform coefficients in each block for which it is determined in said determining step to embed an invisible watermark bit;

updating a hash value at each block by applying a hash function at each block, wherein the hash value computed at a last block is a multiple-bit hash value representative of the entire digital image; and

applying a secret key and a digital signature algorithm to the multiple-bit hash value to compute the invisible watermark; and

embedding an invisible watermark bit in each block for which it was determined to do so in said determining step by setting the at least one bit of the one of the plurality of transform coefficients in that block to match a corresponding bit of the computed invisible watermark.