Watermarking scheme for image authentication

• US 6,285,775 B1
• Filed: 10/01/1998
• Issued: 09/04/2001
• Est. Priority Date: 10/01/1998
• Status: Expired due to Fees

• Current Assignee: Princeton University
• Original Assignee: Princeton University
• Inventors: Wu, Min, Liu, Bede
• Primary Examiner(s): Johns, Andrew W.
• Assistant Examiner(s): NAKHJAVAN, SHERVIN K
• Application Number:
  US09/164,474
• Time in Patent Office: 1,069 Days
• Field of Search: 382/100, 382/232, 380/28, 380/29, 380/30, 380/54, 705/51
• US Class Current: 382/100
• 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

Abstract

A digital watermarking process whereby an invisible watermark inserted into a host image is utilized to determine whether or not the image has been altered and, if so, where in the image such alteration occurred. The watermarking method includes the steps of providing a look-up table containing a plurality of coefficients and corresponding values; transforming the image into a plurality of blocks, wherein each block contains coefficients matching coefficients in the look-up table; and embedding the watermark in the image by performing the following substeps for at least some of the blocks: First, a coefficient is selected for insertion of a marking value representative of a corresponding portion of the watermark. Next, the value of the selected coefficient to used to identify a corresponding value in the look-up table. Finally, the identified coefficient is left unchanged if the corresponding value is the same as the marking value, and is changed if the corresponding value is different from the marking value. After the insertion of the watermark, the image may be stored in a lossy-compression form, thus permitting efficient storage and distribution. Moreover, the method may be used to produce two output signals for authentication: (1) a meaningful pattern to facilitate a quick visual check, and (2) an additional signal to detect unauthorized alteration. The method can be applied to an image compressed using JPEG or other techniques, such as Wavelet compression, and the marked image can be kept in the compressed format. Any alteration made on the marked image can be localized, making the method suitable for use in a “trustworthy” digital camera or camcorder.

Claims

1. A method for applying a digital watermark to an image, comprising the steps of:

(A) deriving from the image a plurality of component images, wherein each component image contains coefficients;

(B) providing at least one look-up table containing a plurality of coefficients and corresponding values, wherein at least some of the look-up table coefficients match coefficients in said component images;

(C) embedding said watermark in said image by performing the following substeps for at least some of said component images;

(1) selecting a coefficient into which a marking value, representative of a corresponding portion of the watermark, is to be embedded;

(2) using the value of the selected coefficient to identify a corresponding value in said look-up table(s);

(3) leaving the selected coefficient unchanged if the corresponding value is the same as the marking value; and

(4) changing the selected coefficient if the corresponding value is different from the marking value;

further comprising the step of identifying selected coefficients as being unembeddable, wherein said unembeddable coefficients are not employed in step (C) to embed marking values, and wherein some of said coefficients are identified as DC coefficients, and said DC coefficients are considered unembeddable; and

further comprising selecting a threshold value, wherein coefficients having a value below said threshold value are considered small valued and thus unembeddable.

2. A method for applying a digital watermark to an image, comprising the steps of:

(A) deriving from the image a plurality of component images, wherein each component image contains coefficients;

(B) providing at least one look-up table containing a plurality of coefficients and corresponding values, wherein at least some of the look-up table coefficients match coefficients in said component images; and

(C) embedding said watermark in said image by performing the following substeps for at least some of said component images;

(1) selecting a coefficient into which a marking value, representative of a corresponding portion of the watermark, is to be embedded;

(2) using the value of the selected coefficient to identify a corresponding value in said look-up table(s);

(3) leaving the selected coefficient unchanged if the corresponding value is the same as the marking value; and

(4) changing the selected coefficient if the corresponding value is different from the marking value;

further comprising the step of identifying selected coefficients as being unembeddable, wherein said unembeddable coefficients are not employed in step (C) to embed marking values; and

further comprising selecting a plurality of threshold values, wherein coefficients having values below said threshold values are considered small valued and thus unembeddable.

3. A method for applying a digital watermark to an image, comprising the steps of:

(A) deriving from the image a plurality of component images, wherein each component image contains coefficients;

(B) providing at least one look-up table containing a plurality of coefficients and corresponding values, wherein at least some of the look-up table coefficients match coefficients in said component images;

(C) shuffling the coefficients prior to said embedding step; and

(D) embedding said watermark in said image by performing the following substeps for at least some of said component images;

(1) selecting a coefficient into which a marking value, representative of a corresponding portion of the watermark, is to be embedded;

(2) using the value of the selected coefficient to identify a corresponding value in said look-up table(s);

(3) leaving the selected coefficient unchanged if the corresponding value is the same as the marking value; and

(4) changing the selected coefficient if the corresponding value is different from the marking value;

wherein the image is divided into a plurality of component images of n×

m pixels, wherein n and m are integers, and wherein each component image is transformed using the discrete cosine transform (DCT) into n×

m transform coefficients;

wherein the corresponding values in said look-up table(s) are binary-valued and are constrained to have a prescribed maximum run length of either binary value;

wherein, in the embedding substep (D)(4), the selected coefficient is changed minimally to a value having a corresponding value in the look-up table(s) whose value is the same as the marking value, wherein the selected coefficient is changed minimally by changing its value to that of the nearest coefficient having a corresponding look-up table value equal to the marking value.

4. A method as recited in claim 3, wherein, prior to the embedding step (C), the image is compressed using JPEG compression.

5. A method as recited in claim 3, further comprising the step of shuffling the coefficients prior to said embedding step, wherein said shuffling step comprises concatenating the coefficients of a plurality of component images into a string and shuffling the order of the coefficients in said string;

and wherein, after embedding, the string is inverse shuffled.

6. A method as recited in claim 3, wherein the marking value is embedded multiple times in each component image, whereby a majority voting process may be employed to decode the respective component images.

7. A method as recited in claim 3, wherein the marking value is embedded using error correction encoding, and wherein error correction decoding is employed to extract the marking values.

8. A method as recited in claim 7, wherein the error correction encoding comprises embedding of the marking value multiple times and the decoding comprises the use of majority voting.

9. A method as recited in claim 3, wherein the marked image is decodable to determine whether it has been altered and, if so, where in the image such alterations were made.

10. A method as recited in claim 3, further comprising the step of storing the marked image in a lossy-compression form.

11. A method as recited in claim 3, wherein the method is used in a digital camera or camcorder.

12. A method for applying a digital watermark to an image, comprising the steps of:

(A) deriving from the image a plurality of component images, wherein each component image contains coefficients;

(B) providing at least one look-up table containing a plurality of coefficients and corresponding values, wherein at least some of the look-up table coefficients match coefficients in said component images;

(C) shuffling the coefficients; and

(D) embedding said watermark in said image by performing the following substeps for at least some of said component images;

(1) selecting a coefficient into which a marking value, representative of a corresponding portion of the watermark, is to be embedded;

(2) using the value of the selected coefficient to identify a corresponding value in said look-up table(s);

(3) leaving the selected coefficient unchanged if the corresponding value is the same as the marking value; and

(4) changing the selected coefficient if the corresponding value is different from the marking value;

wherein the image is divided into a plurality of component images of n×

m pixels, wherein n and m are integers, and wherein each component image is transformed using the discrete cosine transform (DCT) into n×

m transform coefficients;

wherein the corresponding values in said look-up table(s) are binary-valued and are constrained to have a prescribed maximum run length of either binary value;

wherein, in the embedding substep (C)(4), the selected coefficient is changed minimally to a value having a corresponding value in the look-up table(s) whose value is the same as the marking value, wherein the selected coefficient is changed minimally by changing its value to that of the nearest coefficient having a corresponding look-up table value equal to the marking value; and

further comprising the step of identifying selected coefficients as being unembeddable, wherein said unembeddable coefficients are not employed in step (C) to embed marking values;

wherein some of said coefficients are identified as DC coefficients that are considered unembeddable; and

wherein coefficients having values below threshold values are considered unembeddable.

13. A method for applying a digital watermark to an image, comprising the steps of:

(A) deriving from the image a plurality of component images, wherein each component image contains coefficients;

(B) providing at least one look-up table containing a plurality of coefficients and corresponding values, wherein at least some of the look-up table coefficients match coefficients in said component images;

(C) shuffling the coefficients prior to said embedding step; and

(D) embedding said watermark in said image by performing the following substeps for at least some of said component images;

(1) selecting a coefficient into which a marking value, representative of a corresponding portion of the watermark, is to be embedded;

(2) using the value of the selected coefficient to identify a corresponding value in said look-up table(s);

(3) leaving the selected coefficient unchanged if the corresponding value is the same as the marking value; and

(4) changing the selected coefficient if the corresponding value is different from the marking value.

wherein the image is divided into a plurality of component images of size n×

m pixels, wherein n and m are integers, and wherein each component image is transformed into coefficients;

further comprising the step of shuffling the coefficients prior to said embedding step;

wherein said shuffling step comprises concatenating the coefficients of a plurality of component images into a string and shuffling the order of the coefficients in said string; and

wherein the shuffled string of coefficients are put into a plurality of sub-strings and each sub-string is used to embed one watermark or is to be used for error detection or for error correction.

14. A method for applying a digital watermark to an image, comprising the steps of:

(A) deriving from the image a plurality of component images, wherein each component image contains coefficients;

(B) providing at least one look-up table containing a plurality of coefficients and corresponding values, wherein at least some of the look-up table coefficients match coefficients in said component images;

(C) shuffling the coefficients prior to said embedding step; and

(D) embedding said watermark in said image by performing the following substeps for at least some of said component images;

(1) selecting a coefficient into which a marking value, representative of a corresponding portion of the watermark, is to be embedded;

(2) using the value of the selected coefficient to identify a corresponding value in said look-up table(s);

(3) leaving the selected coefficient unchanged if the corresponding value is the same as the marking value; and

(4) changing the selected coefficient if the corresponding value is different from the marking value.

wherein the image is divided into a plurality of component images of size n×

m pixels, wherein n and m are integers, and wherein each component image is transformed into coefficients;

further comprising the step of shuffling the coefficients prior to said embedding step;

wherein said shuffling step comprises concatenating the coefficients of a plurality of component images into a string and shuffling the order of the coefficients in said string; and

wherein the shuffled string of coefficients are put into a plurality of sub-strings and each sub-string is used to embed one watermark or is to be used for error detection or for error correction.