Protecting images with an image watermark

• US 6,577,744 B1
• Filed: 06/16/1998
• Issued: 06/10/2003
• Est. Priority Date: 10/28/1996
• Status: Expired due to Fees

• Current Assignee: RPX Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Braudaway, Gordon Wesley, Mintzer, Frederick Cole
• Primary Examiner(s): Dastouri, Mehrdad
• Application Number:
  US09/098,233
• Time in Patent Office: 1,820 Days
• Field of Search: 382/100, 382/294, 382/135, 382/205, 382/137, 382/151, 382/138, 382/232, 380/4, 380/51, 380/54, 283/113, 162/110
• US Class Current: 382/100
• CPC Class Codes: G06T 1/005 Robust watermarking, e.g. average attack or collusion attack resistant
• CPC Class Codes: G06T 2201/0065 Extraction of an embedded watermark; Reliable detection
• CPC Class Codes: H04N 1/32203 Spatial or amplitude domain methods H04N1/32309 takes precedence
• 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/32251 in multilevel data, e.g. greyscale or continuous tone data
• CPC Class Codes: H04N 2201/3233 of authentication information, e.g. digital signature, watermark
• CPC Class Codes: H04N 2201/327 which are undetectable to the naked eye, e.g. embedded codes

Abstract

A robust means of watermarking a digitized image with a highly random sequence of pixel brightness multipliers is presented. The random sequence is formed from ′robust- watermarking-parameters′ selected and known only by the marker and/or the marking entity. A watermarking plane is generated which has an element array with one-to-one element correspondence to the pixels of the digitized image being marked. Each element of the watermarking plane is assigned a random value dependent upon a robust random sequence and a specified brightness modulation strength. The so generated watermarking plane is imparted onto the digitized image by multiplying the brightness value or values of each pixel by its corresponding element value in the watermarking plane. The resulting modified brightness values impart the random and relatively invisible watermark onto the digitized image. Brightness alteration is the essence of watermark imparting. Detection of an imparted watermark requires knowing the watermarking plane with which the watermark was imparted. Regeneration of the watermarking plane requires knowledge of the robust-marking-parameters used in its formulation. This is generally only known to the marker and/or marking entity. Once regenerated the watermarking plane is used together with a verifying image located in a ′visualizer′ to demonstrate the existence of the watermark.

Claims

1. A method for detecting a watermark in a marked image, wherein said marked image is marked by a watermarking plane, said marked image having at least one color plane including a plurality of image pixels, said watermarking plane having a plurality of watermarking elements, wherein each of said image pixels has at least one brightness value and each of said watermarking elements has a brightness multiplying factor, said method comprising:

(a) reconstructing said watermarking plane;

(b) aligning said watermarking plane with said marked image such that each watermarking element has a corresponding image pixel;

(c) providing a selector array and a visualizer image of equal size, wherein said selector array has a plurality of selector elements each having at least one counter, and wherein said visualizer image has a plurality of visualizer pixels each having at least one brightness value, and wherein said visualizer pixels represent a recognizable pattern when displayed;

(d) resetting said at least one counter to zero;

(e) placing said selector in an initial position by aligning said selector elements with a plurality of corresponding image pixels and a plurality of corresponding watermarking elements;

(f) choosing a selector element and identifying a corresponding watermarking element;

(g) identifying a first plurality of watermarking elements that neighbor said corresponding watermarking element;

(h) generating a first average that represents an average of brightness multiplying factors of said first plurality of watermarking elements;

(i) choosing a color plane ot said marked image and finding a corresponding image pixel;

(j) identifying a first plurality of neighboring pixels that neighbor said corresponding image pixel;

(k) generating a second average that represents an average of brightness values of said first plurality of neighboring pixels;

(l) updating said at least one counter based upon first and second comparison operations wherein said first comparison operation compares said first average with said brightness multiplying factor of said corresponding watermarking element and said second comparison operation compares said second average with said brightness value of said corresponding pixel;

(m) repeating steps (i) through (l) for all color planes;

(n) repeating steps (f) through (m) f or all selector elements;

(o) choosing a new selector position that does not overlap any previous selector position;

(p) repeating steps (f) through (o) for all non-overlapping selector positions; and

(q) generating a visual representation indicating detection of said watermark in said marked image utilizing said at least one counter of said selector array and said visualizer pixels.

2. The method as recited in claim 1, wherein said at least one counter includes a coincidence counter and a non-coincidence counter and wherein said updating step includes the steps of:

generating a first difference value by substrating said first average from said brightness multiplying factor of said corresponding watermarking element;

generating a second difference value by substracting said second average from said brightness value of said corresponding pixel; and

incrementing said coincidence counter if said first and second difference values are both positive, and incrementing said coincidence counter if said first and second difference values are both negative, otherwise, incrementing said non-coincidence counter.

3. A method as recited in claim 1, wherein said placing step is performed using random vertical and horizontal offsets.

4. A method as recited in claim 3, wherein said offsets are derived from a secure random sequence.

5. A method as recited in claim 1, wherein said first plurality is a number equal to 120.

6. A method as claimed in claim 1, wherein each pixel of said visualizer image has a monochrome brightness value.

7. A method as recited in claim 1, wherein each pixel of said visualizer image has a plurality of brightness values.

8. A method as claimed in claim 7, wherein each pixel of said visualizer image has a red, green and blue brightness value.

9. A method as recited in claim 1, wherein generating step (q) includes the step of building a visualizer coincidence image having a plurality of coincidence pixels that have one-to-one correspondance with said visualizer and said elements of said selector array, and which includes for each given coincidence pixel the steps of:

identifying a first element of said selector array that corresponds to said given coincidence pixel;

generating a coincidence value based upon a value stored in said at least one counter associated with said first element of said selector array;

identifying a first pixel of said visualizer image that corresponds to said given coincidence pixel;

generating at least one brightness value for said given coincidence pixel based upon said coincidence value and at least one brightness value of said first pixel of said visualizer image.

10. A method as recited in claim 9, further comprises the step of displaying said visualizer coincidence image such that a user can make a determination as to whether said pattern encoded by said visualizer pixels is recognizable.

11. A method as recited in claim 9, wherein said at least one counter includes a coincidence counter and a non-coincidence counter, and wherein said updating step includes the steps of:

generating a first difference value by subtracting said first average from said brightness multiplying factor of said corresponding watermarking element;

generating a second difference value by subtracting said second average from said brightness value of said corresponding image pixel; and

incrementing said coincidence counter if said first and second difference values are both positive, and incrementing said coincidence counter if said first and second difference values are both negative, otherwise, incrementing said non-coincidence counter.

12. A method as recited in claim 11, wherein said step of generating said coincidence value includes the step of generating a third difference value by subtracting said non-coincidence counter from said coincidence counter, and generating said at least one brightness value of said given coincidence pixel by modifying said at least one brightness value of said first pixel of said visualizer image otherwise.

13. The method as recited in claim 12, wherein each visualizer pixel has a monochrome brightness value, and wherein said modifying step comprises the step of inverting said monochrome brightness value associated with said first pixel of said visualizer image.

14. The method as recited in claim 11,

wherein each visualizer pixel has a binary monochrome brightness value, said binary monochrome brightness value being one of a first value representing a black brightness and a second value representing a white brightness;

wherein said step of generating said coincidence value includes the step of generating a ratio R, wherein R represents said coincidence counter divided by a sum of said coincidence counter and said non-coincidence counter; and

wherein said step of generating said at least one brightness value of said given coincidence pixel includes the steps of;

assigning said at least one brightness value of said given coincidence pixel to a value (1-R) if said binary monochrome brightness value of said first pixel is set to said first value, and

assigning said at least one brightness value of said given coincidence pixel to said ratio R if said binary monochrome brightness value of said first pixel is set to said second value.

15. A method as recited in claim 9, further comprising the step of displaying said visualizer coincidence image such that a user can make a determination as to whether said watermark is detected.

17. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing detection of a watermark in a marked image, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 1.

18. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing detection of a watermark in a marked image, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 9.

19. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing detection of a watermark in a marked image, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the steps of claim 1.

16. In a system wherein an image having a plurality of image elements is marked by a watermarking plane having a plurality of watermarking elements, a method for detecting said watermarking plane comprising the steps of:

aligning said watermarking plane with said image;

identifying a subset of said image elements, wherein said subset forms a group of selector elements having a selector size;

for each image element I of said subset of image elements,

generating a first value representing a relationship between an attribute of said image element I and an attribute of image elements that neighbor said image element I;

identifying a watermarking element W that corresponds to said image element I and watermarking elements that correspond to said image elements that neighbor said image element I;

generating a second value representing a relationship between an attribute of said watermarking element W and an attribute of the identified watermarking elements; and

generating a coincidence value representing likelihood that said image is marked by said watermarking plane based upon said first and second values;

providing a visualizer pattern having a plurality of visualizer elements and a visualizer size equal to said selector size, each of said visualizer elements being associated with one of said selector elements and having a visualizer color; and

displaying a watermark detection pattern having a size equal to said visualizer size and a plurality of detection elements, wherein each of said detection elements is associated with a corresponding selector element said a corresponding visualizer element, and has said visualizer color when said coincidence value of said corresponding selected element has an indication of a detection success, and has another color otherwise.