Method and apparatus for data hiding in images

• US 5,689,587 A
• Filed: 02/09/1996
• Issued: 11/18/1997
• Est. Priority Date: 02/09/1996
• Status: Expired due to Term

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Bender, Walter, Gruhl, Daniel, Morimoto, Norishige
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Johnson, Timothy M.
• Application Number:
  US08/599,254
• Time in Patent Office: 648 Days
• Field of Search: 382/232, 382/260, 382/261, 283/73, 380/18, 380/46, 380/54, 364/260.81, 364/949.71, 364/224.21, 364/717, 364/717.5
• US Class Current: 382/232
• CPC Class Codes: G06T 1/0028 Adaptive watermarking, e.g. Human Visual System [HVS]-based watermarking
• CPC Class Codes: G06T 1/005 Robust watermarking, e.g. average attack or collusion attack resistant
• CPC Class Codes: G06T 2201/0051 Embedding of the watermark in the spatial domain
• CPC Class Codes: G06T 2201/0065 Extraction of an embedded watermark; Reliable detection
• CPC Class Codes: G06T 2201/0081 whereby both original and watermarked images are required at decoder, e.g. destination-based, non-blind, non-oblivious
• CPC Class Codes: G06T 2201/0601 whereby calibration information is embedded in the watermark, e.g. a grid, a scale, a list of transformations
• 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/32229 with selective or adaptive application of the additional information, e.g. in selected regions of the image H04N1/32213 takes precedence
• 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 method of hiding a pattern in a host image increases and decreases parameter values at randomly selected host image locations assigned to respective first and second groups. The alteration modifies the statistical behavior of a test statistic equivalent to a linear combination of a large number of instances of respective functions, associated with the pattern, of the parameter values at first and second group locations. The presence or absence of the pattern in a test image is determined by comparing the experimental value of the test statistic associated with the pattern with the expected value of the same sum for an unaltered host image.

Claims

1. A method of embedding data in an image encoded as points, each point having a parameter value, the method comprising the steps of:

a. generating an ordered series of pseudo-random numbers;

b. assigning each pseudo-random number of the series to a first or a second group;

c. associating each pseudo-random number with a point;

d. designating each point associated with a pseudo-random number assigned to the first group to be a first point each point associated with a pseudo-random number assigned to the second group to be a second point; and

e. altering the image by

i. increasing the parameter value of each first point and of a first patch of points surrounding each first point and

ii. decreasing the parameter value of each second point and of a second patch of points surrounding each second point,

thereby embedding data in the image.

2. The method of claim 1 wherein the generation of the series of pseudo-random numbers is based on a key number.

3. The method of claim 1 wherein each point corresponds to an electronically represented pixel.

4. The method of claim 1 wherein each pseudo-random number is assigned to a group by assigning alternate pseudo-random numbers in the series to the first and second groups.

5. The method of claim 4 wherein the parameter values of the points in each patch are changed by amounts having magnitudes that depend on position within the patches, the dependence being formulated on expected subsequent image processing.

6. The method of claim 4 wherein the parameter values of the points in each patch are changed by amounts having magnitudes that depend on position within the patches, the dependence being formulated on expected visual perceptibility.

7. The method of claim 1 wherein the parameter values of the points in each first patch are changed by a first constant amount and the parameter values of the points in each second patch are changed by a second constant amount.

8. The method of claim 1 wherein the parameter values of the points in each first patch are increased by a first amount and the parameter values of the points in each second patch are decreased by a second amount, the first and second amounts depending on position within the patch.

9. The method of claim 1 further comprising the step of associating each pseudo-random number with a plurality of adjacent points collectively forming a continuous patch, thereby defining several patches in the image.

10. The method of claim 9 wherein the patches are disjoint.

11. The method of claim 1 wherein the series is divided into first and second halves, each pseudo-random number being assigned to a group so that the first group comprises the numbers of the first half of the series and the second group comprises the numbers of the second half of the series.

12. The method of claim 1 wherein the ordered series comprises at least 5,000 pseudo-random numbers.

13. The method of claim 1 wherein the image is monochrome.

14. The method of claim 1 wherein the image is color.

15. The method of claim 1 wherein either of the first or second groups comprises points belonging to a plurality of subgroups, each subgroup having a subgroup amount associated therewith, and wherein the step of altering the image comprises changing the parameter value at each point belonging to a subgroup, and at points in a patch surrounding that point, by the subgroup amount associated with the subgroup to which the point belongs.

16. The method of claim 15 wherein each subgroup amount has a magnitude that is independent of position within a patch.

17. The method of claim 15 wherein each subgroup amount has a magnitude that depends on position within a patch.

18. The method of claim 1 wherein the parameter is luminance.

19. The method of claim 1 wherein the parameter is chrominance.

20. A method of embedding a pattern in a host image electronically encoded as points, each point having a parameter value, the method comprising the steps of:

a. generating an ordered series of pseudo-random numbers;

b. assigning each pseudo-random number of the series to a first or a second group;

c. mapping a grid comprising an array of cells onto the host image by assigning groups of adjacent points to the cells;

d. associating each pseudo-random number with a cell in the host image, each group of points assigned to a cell so associated with a pseudo-random number being designated a patch;

e. further designating each patch in the host image associated with a pseudo-random number assigned to the first group to be a first patch and each patch in the host image associated with a pseudo-random number assigned to the second group to be a second patch; and

f. altering the host image by increasing the parameter values of points in each first patch and decreasing the parameter values of points in each second patch, thereby embedding the pattern in the host image.

21. The method of claim 20 wherein each pseudo-random number is assigned to a group by assigning alternate pseudo-random numbers in the series to the first and second groups.

22. The method of claim 20 wherein the cells are rectangular.

23. The method of claim 20 wherein the cells are hexagonal.

24. The method of claim 20 wherein the generation of the series of pseudo-random numbers is based on a key number.

25. The method of claim 20 wherein each point corresponds to an electronically represented pixel.

26. The method of claim 20 wherein the parameter values of the points in each first patch are changed by a first constant amount and the parameter values of the points in each second patch are changed by a second constant amount.

27. The method of claim 20 wherein the parameter values of the points in each first patch are changed by a first varying amount and the parameter values of the points in each second patch are changed by a second varying amount.

28. The method of claim 20 wherein the parameter values of the points in each patch are changed by amounts having magnitudes that depend on position within the patches, the dependence being formulated based on expected subsequent image processing.

29. The method of claim 20 wherein the parameter values of the points in each patch are changed by amounts having magnitudes that depend on position within the patches, the dependence being formulated based on expected visual perceptibility.

30. The method of claim 20 wherein the image is color.

31. The method of claim 20 wherein the image is monochrome.

32. A method for determining whether a test image, encoded as points, each point having a parameter value, contains data embedded according to the method of claim 20, the method comprising the steps of:

a. providing the series of pseudo-random numbers and assignment of each number to the first or the second group;

b. mapping a grid comprising an array of nonoverlapping cells onto the test image by assigning groups of adjacent points in the test image to the cells;

c. associating each pseudo-random number with a cell in the test image, the points assigned to each cell so associated with a pseudo-random number being designated a patch;

d. further designating each patch in the test image associated with a pseudo-random number assigned to the first group to be a first patch and each patch in the test image associated with a pseudo-random number assigned to the second group to be a second patch; and

e. calculating a value of a test statistic, comprising the parameter values at the first and second patches in the test image, formulated to reflect the pattern, the test statistic indicating whether the pattern is present in the test image.

33. The method of claim 32 wherein the test statistic comprises only parameter values at one designated point for each patch.

34. The method of claim 33 wherein each patch has a centroid point and the one designated point is the centroid point.

35. The method of claim 32 wherein the determination is generated based on a cumulative distribution function of a Gaussian probability distribution function of the test statistic in the unaltered host image.

36. The method of claim 32 wherein the test statistic is a linear combination of several instances of first and second functions of the parameter values at the first and second patches, respectively.

37. The method of claim 32 wherein each point in the test image corresponds to an electronically encoded pixel.

38. The method of claim 32 wherein the step of mapping a grid is performed so as to account for post-embedding geometric transformation of the host image.

39. The method of claim 32 wherein the test statistic is the difference between the sum of the parameter values of the first points and the sum of the parameter values of the second points.

40. The method of claim 32 wherein the parameter is luminance.

41. The method of claim 32 wherein the parameter is chrominance.

42. The apparatus of claim 32 wherein the test statistic is a linear combination of several instances of first and second functions of the parameter values in the first and second patches, respectively, in the test image.

43. The method of claim 20 wherein the series is divided into first and second halves, each pseudo-random number being assigned to a group so that the first group comprises the numbers of the first half of the series and the second group comprises the numbers of the second half of the series.

44. The method of claim 20 wherein either of the first or second groups comprises patches belonging to a plurality of subgroups, each subgroup having a subgroup amount associated therewith, and wherein the step of altering the image comprises changing the parameter values at points in each patch by the subgroup amount associated with the subgroup to which the patch belongs.

45. The method of claim 44 wherein each subgroup amount has a magnitude that is independent of position within a patch.

46. The method of claim 44 wherein each subgroup amount has a magnitude that depends on position within a patch.

47. The method of claim 20 wherein the parameter is luminance.

48. The method of claim 20 wherein the parameter is chrominance.

49. A method for determining whether a test image, encoded as points, each point having a parameter value, contains a pattern embedded in a host image by altering the host image by increasing and decreasing the parameter values of host image points designated as respective first and second host image points according to an association of each first or second point with a pseudo-random number of a series, of which each number is assigned to a first or a second group, the method comprising the steps of:

a. providing the series of pseudo-random numbers and assignment of each number to the first or the second group;

b. associating each pseudo-random number with a point in the test image;

c. designating each point in the test image associated with a pseudo-random number assigned to the first group to be a first point and each point associated with a pseudo-random number assigned to the second group to be a second point; and

d. calculating a value of a test statistic, comprising the parameter values at the first and second points in the test image, formulated to reflect the pattern, the test statistic indicating whether the pattern is present in the test image.

50. The method of claim 49 wherein the determination is generated based on a cumulative distribution function of a Gaussian probability distribution function of the test statistic in the unaltered host image.

51. The method of claim 49 wherein the test statistic is a linear combination of several instances of first and second functions of the parameter values at the first and second points, respectively.

52. The method of claim 49 wherein each point in the test image corresponds to an electronically represented pixel.

53. The method of claim 49 wherein the step of associating each pseudo-random number with a point in the test image is performed so as to account for post-embedding geometric transformation of the host image.

54. The method of claim 49 wherein the test statistic is the difference between the sum of the parameter values of the first points and the sum of the parameter values of the second points.

55. The method of claim 49 wherein the parameter is luminance.

56. The method of claim 49 wherein the parameter is chrominance.

57. The apparatus of claim 49 wherein the test statistic is linear combination of several instances of first and second functions of the parameter values at the first and second points, respectively, in the test image.

58. An apparatus for embedding data in an image, the apparatus comprising:

a. a computer memory for storing the image as an ordered set of pixels, each pixel having a pixel parameter value;

b. means for generating a series of ordered pseudo-random numbers;

c. means for assigning each pseudo-random number to a first or a second group;

d. means for associating each pseudo-random number with a pixel and designating each pixel associated with a pseudo-random number assigned to the first group to be a first pixel and each pixel associated with a pseudo-random number of the second group to be a second pixel; and

e. means for creating an altered image by

i. increasing the pixel parameter value of each first pixel and of a first patch of pixels surrounding each first pixel and

ii. decreasing the pixel parameter value of each second pixel and of a second patch of pixels surrounding each second pixel,

thereby embedding data in the image.

59. The apparatus of claim 58 wherein the means for generating a series of numbers generates the numbers based on a key.

60. The apparatus of claim 58 wherein the assigning means assigns each pseudo-random number to a group by assigning alternate pseudo-random numbers in the series to the first and second groups.

61. The apparatus of claim 60 wherein the image-altering means increases the pixel parameter values of the pixels in each first patch by a first constant amount and decreases the pixel parameter values of the pixels in each second patch by a second constant amount.

62. The apparatus of claim 60 wherein the image-altering means increases the pixel parameter values of the pixels in each first patch by a first amount and decreases the pixel parameter values of the pixels in each second patch by a second varying amount, the first and second amounts depending on position within the patch.

63. The apparatus of claim 58 wherein the series-generating means generates a series having at least 5,000 pseudo-random numbers.

64. The apparatus of claim 58 wherein the image-altering means changes the pixel parameter values of the points by amounts based on expected subsequent image processing.

65. The apparatus of claim 58 wherein the image-altering means changes the pixel parameter values of the points by amounts based on visual perceptibility.

66. The apparatus of claim 58 wherein the series is divided into first and second halves, and the assigning means assigns each pseudo-random number to a group so that the first group comprises the numbers of the first half of the series and the second group comprises the numbers of the first half of the series.

67. The apparatus of claim 58 wherein either of the first or second groups comprises patches belonging to a plurality of subgroups, each subgroup having a subgroup amount associated therewith, and wherein the means for creating an altered image changes the parameter value at points in each patch by the subgroup amount associated with the subgroup to which the patch belongs.

68. The apparatus of claim 67 wherein each subgroup amount has a magnitude that is independent of position within a patch.

69. The apparatus of claim 67 wherein each subgroup amount has a magnitude that depends on position within a patch.

70. An apparatus for determining whether a test image, electronically encoded as points, each point having a parameter value, contains a pattern embedded in a host image by associating each number of a pseudo-random series with a point in the host image, each number being assigned to a first or a second group, and designating each point in the host image associated with a pseudo-random number assigned to the first group to be a first point and each point associated with a pseudo-random number assigned to the second group to be a second point, and altering the host image by increasing the parameter value of each first point in the host image and decreasing the parameter value of each second point in the host image, the apparatus comprising:

a. means for providing the series of pseudo-random numbers and assignment of each number to the first or second group;

b. means for associating each pseudo-random number with a point in the test image;

c. means for designating each point in the test image associated with a pseudo-random number assigned to the first group to be a first point and each point associated with a pseudo-random number assigned to the second group to be a second point;

d. means for calculating a test statistic, comprising the parameter values at the first and second points in the test image, formulated to reflect the pattern.

71. The apparatus of claim 70 further comprising means for generating an indication of whether the test image contains the pattern.

72. The apparatus of claim 71 wherein the indication-generating means generates an indication based on a cumulative distribution function of the test statistic in the unaltered host image.

73. The apparatus of claim 70 wherein the associating means associates each pseudo-random number with a point in the test image so as to account for post-embedding geometric transformation of the host image.

74. The apparatus of claim 70 wherein the test statistic is a linear combination of several instances of first and second functions of the parameter values at the first and second points, respectively.

75. The apparatus of claim 70 wherein the test statistic is the difference between the sum of the parameter values of the first points and the sum of the parameter values of the second points.

76. The apparatus of claim 70 wherein the parameter is luminance.

77. The apparatus of claim 70 wherein the parameter is chrominance.

84. The image of claim 70 wherein the parameter is luminance.

85. The image of claim 70 wherein the parameter is chrominance.

78. An image created by altering a host image comprised of points, each point having a parameter value, by associating each number of a pseudo-random series with a point, each number being assigned to a first or a second group, and designating each point associated with a pseudo-random number assigned to the first group to be a first point and each point associated with a pseudo-random number assigned to the second group to be a second point, and increasing the parameter value of each first point and decreasing the parameter value of each second point.

79. The image of claim 78 wherein the image is a photograph.

80. The image of claim 78 wherein the image is an electronically encoded array of pixels.

81. The image of claim 78 wherein the series is divided into first and second halves, each pseudo-random number being assigned to a group so that the first group comprises the numbers of the first half of the series and the second group comprises the numbers of the second half of the series.

82. The image of claim 78 wherein each pseudo-random number is assigned to a group by assigning alternate pseudo-random numbers in the series to the first and second groups.

83. The image of claim 78 wherein the image is a print or lithograph.