Digital watermarking by adding random, smooth patterns

• US 6,101,602 A
• Filed: 12/08/1997
• Issued: 08/08/2000
• Est. Priority Date: 12/08/1997
• Status: Expired due to Term

• Current Assignee: United States Air Force (Government of the United States of America)
• Original Assignee: United States Of America As Represented By The Secretary Of The Air Force
• Inventors: Fridrich, Jiri
• Primary Examiner(s): Swann, Tod B.
• Assistant Examiner(s): Smithers, Matthew
• Application Number:
  US08/986,695
• Time in Patent Office: 974 Days
• Field of Search: 380/4, 380/5, 380/28, 380/51, 380/54, 380/43, 380/48, 380/200, 380/201, 380/263, 713/176, 713/168
• US Class Current: 713/176
• CPC Class Codes: G06T 1/005 Robust watermarking, e.g. average attack or collusion attack resistant
• CPC Class Codes: G06T 2201/0063 in relation to collusion attacks, e.g. collusion attack resistant
• CPC Class Codes: H04N 1/32144 embedded in the image data, i.e. enclosed or integrated in the image, e.g. watermark, super-imposed logo or stamp
• CPC Class Codes: H04N 1/32208 involving changing the magnitude of selected pixels, e.g. overlay of information or super-imposition H04N1/32219, H04N1/32224 take precedence
• 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

Abstract

A digital image is "watermarked", that is, authenticated by an embedded pattern. The pattern is created by hashing the image and adding a signature element. Manipulating this result by the seed for a random number generator leads to an initial two dimensional random black-and-white pattern. This pattern is manipulated by a cellular automaton and smoothed before being added to the original image. To determine whether the image is authentic, one retrieves the watermark by subtracting the watermarked image from the original to obtain the difference. The value of the correlation between the difference thus obtained and the smoothed pattern determines the presence or absence of the watermark.

Claims

1. A method of marking, with an invisible identifier that cannot be removed therefrom, an electronic file containing a stream of samples comprising at least one image, which method comprises the steps of:

selecting a first bit-string to represent authorship of said file;

selecting a second bit-string to represent content of said file;

combining said first and said second bit-string into said identifier;

applying a function to convert said identifier into a number in a range effective for seeding a pseudo-random number generator;

deriving a pseudo-random black and white pattern from said number by means of said generator,

said pattern having dimensions substantially the same as said file;

processing said pattern to create a random collection of connected areas, thereby transforming said pattern'"'"'s spectral energy to lower frequencies;

smoothing said pattern;

rescaling said smoothed pattern so that its amplitude is more than one unit sample; and

adding said rescaled, smoothed pattern to said file, whereby said file is marked with said identifier.

2. The method of claim 1, wherein said step of applying includes a hash function.

3. The method of claim 1, wherein said step of applying includes a message digest function.

4. The method of claim 1, wherein said step of processing includes applying a cellular automaton.

5. The method of claim 4, wherein said cellular automaton has voting rules.

6. The method of claim 4, wherein said cellular automaton has annealing rules.

7. The method of claim 1, wherein said step of processing includes using said pattern as an initial condition for a chaotic spatio-temporal dynamical system.

8. The method of claim 7, wherein said dynamical system tends to create large-scale smooth structures.

9. The method of claim 1, wherein said step of processing includes eliminating high frequencies from said pattern'"'"'s spectral energy.

10. The method of claim 9, wherein said step of processing includes eliminating said high frequencies by applying at least one low-pass filter.

11. The method of claim 1, wherein said step of combining includes concatenating.

12. The method of claim 1, wherein said step of combining includes alternating bits from said first and said second bit-strings.

13. The method of claim 1, wherein said step of combining includes processing bits from said first and said second bit-strings prior to combining them.

14. The method of claim 13, wherein said step of processing includes applying a hash function to said first string and/or said second string.

15. A method of determining whether or not an electronic file containing at least one image also contains an invisible identifier, which method comprises the steps of:

subtracting a first modified version of said file from a second modified version thereof to obtain a difference;

calculating a correlation between said difference and said second modified version; and

comparing a value of said correlation with a threshold value to determine whether or not said invisible identifier is present in said second modified version.

16. The method of claim 15, wherein said step of evaluating includes evaluating the function ##EQU4## where said file is X, said first modified version is X'"'"', said second modified version is X*, the symbols Y, Y'"'"', and Y* denote the lowest 1024 discrete cosine coefficients that correspond respectively to X, X'"'"', and X*, and D=Y'"'"'-Y, D*=Y*-Y.

17. An invisible identifier irremovably embedded in an electronic file that contains at least one image, said identifier comprising:

a smoothed, randomized black-and-white pattern;

said pattern being rescaled to dimensions substantially the same as said file and overlaid thereon;

said pattern being generated from a combination of a first and a second bit-string;

said first bit-string being selected to represent authorship of said file; and

said second bit-string being selected to represent content of said file.

18. The identifier of claim 17, wherein said pattern is processed by a cellular automaton.

19. The identifier of claim 18, wherein said cellular automaton has a voting rule.

20. The identifier of claim 17, wherein said pattern is two-dimensional.

21. A computer-readable storage medium embodying program instructions for a method to mark, with an invisible identifier that cannot be removed therefrom, an electronic file containing a stream of samples comprising at least one image, said method comprising the steps of:

selecting a first bit-string to represent authorship of said file;

selecting a second bit-string to represent content of said file;

combining said first and said second bit-string into said identifier;

applying a function to convert said identifier into a number in a range effective for seeding a pseudo-random number generator;

deriving a pseudo-random black and white pattern from said number by means of said generator,

said pattern having dimensions substantially the same as said file;

processing said pattern to create a random collection of connected areas, thereby transforming said pattern'"'"'s spectral energy to lower frequencies;

smoothing said pattern;

rescaling said smoothed pattern so that its amplitude is more than one unit sample; and

adding said resealed, smoothed pattern to said file, whereby said file is marked with said identifier.

22. A computer-readable storage medium embodying program instructions for a method to determine whether or not an electronic file containing at least one image also contains an invisible identifier, said method comprising the steps of:

subtracting a first modified version of said file from a second modified version thereof to obtain a difference;

calculating a correlation between said difference and said second modified version; and

comparing a value of said correlation with a threshold value to determine whether or not said invisible identifier is present in said second modified version.