Protecting images with an image watermark

• US 7,130,442 B2
• Filed: 08/16/2001
• Issued: 10/31/2006
• 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): Johns, Andrew W.
• Application Number:
  US09/931,210
• Publication Number:
  US 20020090110A1
• Time in Patent Office: 1,902 Days
• Field of Search: 382/100, 382/217, 382/218, 382/232, 382/264, 713/176, 380/287, 380/51, 380/54, 380/55, 358/3.28
• 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 1/0064 Geometric transfor invariant watermarking, e.g. affine transform invariant
• 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 1/3232 Robust embedding or watermarking
• 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 having an element array with one-to-one element positional correspondence with 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 modulation 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. The process of watermark detection is enhanced by application of a blurring filter to the marked image before detection is attempted.

Claims

1. A method for imparting a watermark onto a digitized image, said method comprising:

providing a digitized image having at least one image plane, said image plane being represented by an image array having a plurality of pixels, each pixel in said plurality of pixels having at least one color component, said watermark being formed using a distinct watermarking plane represented by an array having a plurality of distinct watermarking elements, each of said distinct watermarking elements having an array position and having one-to-one positional correspondence with said image pixels, and

multiplying brightness data associated with said at least one color component by a predetermined brightness multiplying factor, wherein said brightness multiplying factor is a corresponding distinct watermarking element, and said watermark has a invisibility classification, wherein said brightness multiplying factor has a relationship with a number taken from a random number sequence.

2. A method as recited in claim 1, wherein said relationship is a linear remapping to provide a desired modulation strength.

3. A method as recited in claim 2, wherein said modulation strength lies in the domain greater than or equal to zero and less than or equal to 0.5.

4. A method as recited in claim 1, wherein said distinct watermarking element, has a value being in the domain greater than or equal to zero and less than or equal to one.

5. An apparatus to impart a watermark onto a digitized image, said apparatus comprising mechanisms for implementing the method of claim 1.

6. A method for imparting a watermark onto a digitized image comprising the steps of:

providing said digitized image comprised of a plurality of pixels, wherein each of said pixels includes brightness data that represents a brightness of at least one color; and

altering said brightness data associated with a plurality of said pixels maintaining the hue and saturation of said pixel,

wherein said image has I rows and J columns, and has a pixel in row i and column j having at least one brightness, Y(i,j), and the step of altering includes;

adding to or subtracting from the brightness Y(i,j) a different small random value e(i,j), wherein I<

i<

I and I<

j<

J are the row and column indices of a pixel location in the image, and

wherein color components of the unaltered pixel are X(i,j), Y(i,j), and Z(i,j), and color components of the brightness altered pixel are X′

(i,j), Y′

(i,j), and Z′

(i,j), and the step of adding to or subtracting from includes setting e(i,j)=d(i,j)Y(i,j), where d(i,j) is a value selected from an array of random values within a range of 0<

=d(i,j)<

=1, such that the modified brightness Y′

(i,j)=Y(i,j)+e(i,j)=Y(i,j)+d(i,j)Y(i,j), and X′

(i,j)/X(i,j)=Z′

(i,j)/Z(i,j)=Y′

(i,j)/Y(i,j)=e(i,j)=1−

d(i,j).

7. A method as recited in claim 6, wherein the step of adding to or subtracting from includes making e(i,j) proportional to an original brightness of the pixel.

8. An apparatus for imparting a watermark onto a digitized image comprising mechanisms for implementing the method of claim 7.

9. A method as recited in claim 6, wherein the step of setting includes preserving ratios of color components in each pixel.

10. A method as recited in claim 9, wherein the step of preserving includes setting X′

(i,j)/X(i,j)=Z′

(i,j)/Z(i,j)=Y′

(i,j)/Y(i,j)=1−

d(i,j), wherein the color components of the unaltered pixel are X(i,j), Y(i,j), and Z(i,j), and the color components of the brightness altered pixel are X′

(i,j), Y′

(i,j), and Z′

(i,j).

11. An apparatus for imparting a watermark onto a digitized image comprising mechanisms for implementing the method of claim 6.

12. An apparatus as recited in claim 11, wherein the image is a marked image, and the mechanisms for implementing includes means for altering said marked image employing a blurring filter.

13. A method for imparting a watermark onto a digitized image comprising the steps of:

providing said digitized image comprised of a plurality of pixels, wherein each of said pixels includes brightness data that represents a brightness of at least one color, with said image having I rows and J columns, and a pixel in row i and column j having a brightness Y(i,j); and

for a plurality i and at least one j adding to or subtracting from the brightness Y(i,j) a random value e(i,j), wherein 1 I and J are the row and column indices of a pixel location in the image,

wherein e(i,j) is in the domain 0 to 1 multiplied by Y(i,j).

14. A method for detecting a watermark in a marked image, said method comprising:

providing said marked image 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 adding and/or subtracting factor, including the steps of;

(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) plating 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 tat represents an average of brightness adding and/or subtracting factors of said first plurality of watermarking elements;

(i) choosing a color plane of 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 adding and/or subtracting 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) for 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, wherein the step of aligning said watermarking plane with said marked image includes altering said marked image employing a blurring filter.

15. An apparatus for detecting a watermark in a marked image comprising mechanisms for implementing the method of claim 14.

16. A method for detecting a watermarking plane comprising the steps of:

providing an image having a plurality of image pixels, u(i,j), with said image having I rows and J columns, and a pixel in row i and column j having at least one component, marked by a watermarking plane;

said watermarking plane having a plurality of watermarking elements, w(i,j), with said watermarking plane having I rows and J columns, and an element in row i and column j having a brightness multiplying factor;

aligning said watermarking plane with said image;

identifying a subset of said image elements;

for each pixel, u(i,j), of said subset of image pixels,

generating a first value representing a relationship between an attribute of said pixel u(i,j) and an attribute of image pixels that neighbor said pixel u(i,j);

identifying a watermarking element, w(i,j), that corresponds to said pixel u(i,j) and watermarking elements that correspond to said image pixels that neighbor said image pixel u(i,j);

generating a second value representing a relationship between an attribute of said watermarking element w(i,j) and an attribute of the identified watermarking elements; and

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

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 16.

18. An article of manufacture as recited in claim 17, wherein the image is a marked image, and the step of aligning includes altering said marked image employing a blurring filter.

19. A method as recited in claim 16, wherein the image is a marked image, and the step of aligning includes altering said marked image employing a blurring filter.

20. An apparatus for detecting a watermarking plane comprising mechanisms for for implementing the method of claim 16.

21. A method for imparting a watermark onto a digitized image comprising the steps of:

providing said digitized image comprised of a plurality of image pixels with said digitized image having I rows and J columns, and a pixel in row i and column j having at least one component, Y(i,j); and

adding to or subtracting from said brightness data associated with at least one of said pixels a predetermined brightness adding factor in the range of 0 to Y(i,j), or brightness subtracting factor in the range of 0 to Y(i,j),

wherein said brightness adding or subtracting factor has a relationship with a number taken from a random number sequence, said relationship is a linear remapping to provide a desired modulation strength, and said modulation strength is less than or equal to 50 percent.

22. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing a watermark to be imparted onto a digitized 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 21.

23. A method for imparting a watermark onto a digitized image comprising the steps of:

providing said digitized image comprised of a plurality of image pixels with said image having I rows and J columns, and a pixel in row i and column j having at least one component, Y(i,j); and

adding to or subtracting from said brightness data associated with at least one of said pixels by a predetermined brightness adding or subtracting factor in the range of 0 to Y(i,j),

wherein said brightness adding or subtracting factor has a relationship with a number taken from a random number sequence, said relationship is a linear remapping to provide a desired modulation strength, said sequence is formed from a plurality of robust watermarking parameters, and said parameters comprise a cryptographic key, two coefficients and an initial value of said random number generator.

24. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing a watermark to be imparted onto a digitized 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 23.

25. An apparatus for imparting a watermark onto a digitized image comprising mechanisms for implementing the method of claim 23.

26. A method for detecting a watermark, said method comprising:

providing a marked image having a plurality of image pixels said marked image being marked by a watermarking plane, having a plurality of watermark elements;

aligning said watermarking plane with said marked image, and

generating a coincidence value by averaging a detection coincidence for each selector element of a group of selector elements taken from said image pixels.

27. A method as recited in claim 26, wherein each of said group of selector elements has a selector size, said method further comprising:

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

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

28. A method as recited in claim 26 wherein said watermark is based on a factor multiplying a brightness value of each of said image pixels.

29. A method as recited in claim 26, further comprising:

reconstructing said watermarking plane used in generating said watermark.

30. A method as recited in claim 29, wherein said watermarking plane has a plurality of watermarking elements, said method further comprising:

rotating, resizing and said image to bring it to a size and position of an original image, and

aligning said watermarking plane with said marked image such that each of said watermarking elements has a corresponding image pixel.

31. A method as recited in claim 26, wherein each said group contains 128 elements.

32. A method as recited in claim 26, wherein each pixel of said image pixels has a monochrome brightness value.

33. A method as recited in claim 26, wherein said watermarking plane is generated using a plurality of robust watermarking parameters.

34. A method as recited in claim 26, wherein said coincidence value is determined using a statistically related attribute relating each said selector element to a plurality of neighboring elements.

35. A method as recited in claim 34, wherein said attribute is a brightness value.

36. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing detection of a watermark imparted onto a digitized 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 26.

37. A method as recited in claim 26, wherein the image is a marked image, and the step of aligning includes altering said marked image employing a blurring filter.

38. An apparatus for detecting a watermark comprising mechanisms for implementing the method of claim 26.

39. A method for detecting a watermark imparted on an image, said method comprising:

providing said image having at least one image plane, said image plane being represented by an image array having a plurality of image elements, said watermark being formed using a watermarking plane represented by a watermarking array having a plurality of watermarking elements, each of said watermarking elements having a first array position and having one-to-one positional correspondence with said image elements;

computing a first statistically related variable for each element of at least one first grouping of a first selector array of elements taken from said image elements, wherein each of said image elements has a second array position;

computing a second statistically related variable for each element of at least one second grouping of a second selector array of elements taken from said watermarking elements, wherein each element of said second selector array of elements has one-to-one positional correspondence with said first selector array, and wherein said correspondence forms combinations of corresponding elements;

comparing to determine an affirmative and non-affirmative likeness of said first and second statistically related variables for each of said combinations of corresponding elements; and

forming at least one comparison array having one-to-one correspondence with said at least one first grouping and having a plurality of comparison elements, wherein each of said comparison elements contains a positive detection indication for each element of said first grouping when said step of comparing results in an affirmative likeness, and a negative detection indication for each element of said first grouping when said step of comparing results in a non-affirmative likeness.

40. A method as recited in claim 39, wherein said watermark is formed by adding or subtracting a brightness factor of each of said image elements by an amount contained in a corresponding element of said watermarking elements.

41. A method as recited in claim 39, wherein said first grouping corresponds to a selector positioned to encompass said first selector array of elements forming a rectangular cluster of elements.

42. A method as recited in claim 39, wherein said first statistical variable is formed by comparing an attribute of said each element of said first selector array of elements to an average attribute of its 128 closest neighbors.

43. A method as recited in claim 42, wherein said attribute is a ratio of the color component to the average of neighboring color components in the same color plane.

44. A method as recited in claim 39, wherein each of said at least one first grouping is positioned so as not to overlap any other of said at least one first grouping.

45. A method as recited in claim 39, wherein each said comparison elements has a particular position in said comparison array, said method further comprising:

determining an average percentage of said affirmative and non-affirmative likeness of each element of said comparison elements having a same particular position in all arrays of said at least one comparison array, and

forming a detection array of elements having one-to-one element correspondence with said comparison elements, wherein each element of said detection array of elements contains said average percentage.

46. A method as recited in claim 45, further comprising the steps of:

providing a visualizer pattern of pixels represented by an array having visualizer pixels which have one-to-one element correspondence with said detection array, each of said visualizer pixels has a first logical value if a corresponding visualizer pixel is black, and a complementary logical value if said corresponding pixel is white;

forming a visualizer coincidence image having a plurality of coincidence pixels, wherein a coincidence pixel has a corresponding visualizer pixel and a corresponding detection array element; and

setting said coincidence pixel to black if both said corresponding visualizer pixel is black and said percentage average of said corresponding detection array element has a value greater than a predetermined detection threshold, otherwise setting said coincidence pixel to white.

47. A method as recited in claim 39, wherein said image has three color planes.

48. 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 39.

49. A method as recited in claim 39, wherein the image is a marked image, and the step of providing includes altering said marked image employing a blurring filter.

50. An apparatus for detecting a watermark comprising mechanisms for implementing the method of claim 39.

51. A method comprising generating a visual representation of a data array of data elements having a data array size, including the steps of:

providing a visualizer pattern of visualizer pixels represented by a visualizer array of visualizer pixels, said visualizer array having a visualizer array size equal to said data array size;

forming a visualizer-coincidence image of image pixels represented by an image array having an image array size equal to said visualizer array size;

setting each said visualizer-coincidence pixel to the color of said corresponding visualizer pixel if a value of said corresponding data element is above a predetermined threshold and to another color if said value is below said predetermined threshold; and

displaying said visualizer-coincidence image to form said visual representation.

52. A method as recited in claim 51, wherein said data array represents data resulting from a watermark detection implementation.

53. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing generation of a visual representation of a data array of data elements, 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 52.

54. A method as recited in claim 51, wherein said first color is black and said second color is white.

55. A method as recited in claim 51, wherein said threshold is set at a fifty percent success rate.

56. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing generation of a visual representation of a data array of data elements, 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 51.

57. A method for demonstrating an existence of a watermark in a marked image, said image having a plurality of image pixels, said method comprising:

providing a visualizer pattern represented by an array of visualizer elements, each of said visualizer elements corresponding with one pixel of a plurality of visualizer pixels and having a first value if said one pixel has a first color and a second value if said one pixel has a second color, said visualizer array having a visualizer array size;

implementing a watermark detection scheme and computing a coincidence value for each of said image pixels within a plurality of pixel selector arrays taken from among said image pixels, each of said pixel selector arrays having a selector array size equal to said visualizer array size;

forming a detection array from a plurality of coincidence values, wherein said detection array has a detection array size equal to said visualizer size; and

computing a coincidence detection value for each of said visualizer elements such that said detection value represents a visualizer.

58. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing demonstration of an existence 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 57.

59. An apparatus for demonstrating an existence of a watermark in a marked image comprising mechanisms for implementing the method of claim 57.

60. A method for detecting a watermark in a marked image having a plurality of image pixels, said marked image marked by a watermarking plane having a plurality of watermarking elements, said method comprising:

providing a visualizer pattern having a plurality of visualizer pixels and a visualizer size;

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

generating a statistically related variable for each image element in a plurality of groupings of image elements in relationship with said corresponding watermarking element;

wherein each of said groupings has a grouping size equal to said visualizer size;

averaging said variable for each element in a like position of all of said groupings to obtain a composite detection success value; and

displaying detection success values by a plurality of visualizer-coincidence pixels having a size equal to said visualizer size, each said visualizer-coincidence pixel having a same color as said corresponding visualizer pixel when said corresponding success value indicates detection success and another color otherwise.

61. 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 60.

62. An article of manufacture as recited in claim 61, wherein the image is a marked image, and the step of aligning includes altering said marked image employing a blurring filter.

63. A method as recited in claim 60, wherein the image is a marked image, and the step of aligning includes altering said marked image employing a blurring filter.

64. An apparatus for detecting a watermark comprising mechanisms for implementing the method of claim 60.

65. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing a watermark to be imparted into an 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:

providing a digitized image having at least one image plane, said image plane being represented by an image array having a plurality of pixels, each of said pixels having at least one color component, said watermark being formed using a distinct watermarking plane represented by an array having a plurality of distinct watermarking elements, each of said distinct watermarking elements having an array position and having one-to-one positional correspondence wit said image pixels, and

multiplying brightness data associated with said at least one color component by a predetermined brightness multiplying factor, wherein said brightness multiplying factor is a corresponding distinct watermarking element, and said watermark has a invisibility classification, wherein said distinct watermarking element, has a value being in the domain greater than or equal to zero and less than or equal to one.

66. A method of generating a visual representation of a data array of data elements having a data array size, said method comprising:

providing a visualizer pattern of visualizer pixels represented by a visualizer array of visualizer elements, said visualizer array having a visualizer array size equal to said data array size, wherein each of said visualizer elements has a first logical value if a corresponding visualizer pixel is a first color and a complementary logical value if said corresponding visualizer pixel has a second color;

forming a data image of image pixels represented by an image array having an image array size equal to said data array size, wherein an image pixel has a corresponding data element and a corresponding visualizer pixel;

setting said data pixel to a color of said corresponding visualizer pixel if a value of said data element is above a predetermined threshold and to another color if said value is below said predetermined threshold; and

displaying said data image to form said visual representation.

67. A method as recited in claim 66, wherein said data array represents data resulting from a watermark detection implementation.

68. A method as recited in claim 66, wherein said first color is black and said second color is white.

69. A method as recited in claim 66, wherein said threshold is set at a fifty percent success rate.

70. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing generation of a visual representation of a data array of data elements, 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 66.

71. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing generation of a visual representation of a data array of data elements, 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 66.

72. A method for detecting a watermarking plane comprising the steps of:

providing an image having a plurality of image pixels, u(i,j), with said image having I rows and J columns, and a pixel in row i and column j having at least one component, marked by a watermarking plane;

said watermarking plane having a plurality of watermarking elements, w(i,j), with said watermarking plane having I rows and J columns, and an element in row i and column j having a brightness multiplying factor;

aligning said watermarking plane with said image;

identifying a subset of said image elements; and

for each pixel, u(i,j), of said subset of image pixels, employing a detection scheme in determining a probability of watermark detection based on a property of uniform distribution of the random brightness multiplying factors or the random brightness adding or subtracting factors.