US5689587A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for data hiding in images
Assignee: Massachusetts Institute of Technology
•
Filing: 1996-02-09
•
Granted: 1997-11-18
•
Expires: 2016-02-09
Abstract
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.
Inventors
- 👤 Walter Bender
- 👤 Norishige Morimoto
- 👤 Daniel Gruhl
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 05:54
CPC Classifications
G; G06; G06T; G06T1/00; G06T1/0021; G06T1/0028; G06T1/005; H; H04; H04N; H04N1/00; H04N1/32; H04N1/32101; H04N1/32144; H04N1/32149; H04N1/32203; H04N1/32208; H04N1/32229; G06T2201/00; G06T2201/005; G06T2201/0051; G06T2201/0065; G06T2201/0081; G06T2201/0601; H04N2201/00; H04N2201/32; H04N2201/3201; H04N2201/3225; H04N2201/3233; H04N2201/3269; H04N2201/327
Claims Analysis
Total Claims: 91
Claim 1
Independent Claim
143 words
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.
Claim 2
Independent Claim
143 words
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.
Claim 3
Dependent Claim
20 words
The method of claim 1 wherein the generation of the series of pseudo-random numbers is based on a key number.
Claim 4
Dependent Claim
14 words
The method of claim 1 wherein each point corresponds to an electronically represented pixel.
Claim 5
Dependent Claim
28 words
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.
Claim 6
Dependent Claim
37 words
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.
Claim 7
Dependent Claim
36 words
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.
Claim 8
Dependent Claim
41 words
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.
Claim 9
Dependent Claim
50 words
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.
Claim 10
Dependent Claim
32 words
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.
Claim 11
Dependent Claim
10 words
The method of claim 9 wherein the patches are disjoint.
Claim 12
Dependent Claim
52 words
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.
Claim 13
Dependent Claim
15 words
The method of claim 1 wherein the ordered series comprises at least 5,000 pseudo-random numbers.
Claim 14
Dependent Claim
10 words
The method of claim 1 wherein the image is monochrome.
Claim 15
Dependent Claim
10 words
The method of claim 1 wherein the image is color.
Claim 16
Dependent Claim
71 words
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.
Claim 17
Dependent Claim
20 words
The method of claim 15 wherein each subgroup amount has a magnitude that is independent of position within a patch.
Claim 18
Dependent Claim
19 words
The method of claim 15 wherein each subgroup amount has a magnitude that depends on position within a patch.
Claim 19
Dependent Claim
10 words
The method of claim 1 wherein the parameter is luminance.
Claim 20
Dependent Claim
10 words
The method of claim 1 wherein the parameter is chrominance.
Claim 21
Independent Claim
183 words
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.
Claim 22
Independent Claim
183 words
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.
Claim 23
Dependent Claim
28 words
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.
Claim 24
Dependent Claim
10 words
The method of claim 20 wherein the cells are rectangular.
Claim 25
Dependent Claim
10 words
The method of claim 20 wherein the cells are hexagonal.
Claim 26
Dependent Claim
20 words
The method of claim 20 wherein the generation of the series of pseudo-random numbers is based on a key number.
Claim 27
Dependent Claim
14 words
The method of claim 20 wherein each point corresponds to an electronically represented pixel.
Claim 28
Dependent Claim
41 words
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.
Claim 29
Dependent Claim
41 words
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.
Claim 30
Dependent Claim
38 words
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.
Claim 31
Dependent Claim
37 words
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.
Claim 32
Dependent Claim
10 words
The method of claim 20 wherein the image is color.
Claim 33
Dependent Claim
10 words
The method of claim 20 wherein the image is monochrome.
Claim 34
Dependent Claim
194 words
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.
Claim 35
Dependent Claim
20 words
The method of claim 32 wherein the test statistic comprises only parameter values at one designated point for each patch.
Claim 36
Dependent Claim
21 words
The method of claim 33 wherein each patch has a centroid point and the one designated point is the centroid point.
Claim 37
Dependent Claim
31 words
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.
Claim 38
Dependent Claim
32 words
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.
Claim 39
Dependent Claim
18 words
The method of claim 32 wherein each point in the test image corresponds to an electronically encoded pixel.
Claim 40
Dependent Claim
26 words
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.
Claim 41
Dependent Claim
34 words
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.
Claim 42
Dependent Claim
10 words
The method of claim 32 wherein the parameter is luminance.
Claim 43
Dependent Claim
10 words
The method of claim 32 wherein the parameter is chrominance.
Claim 44
Dependent Claim
36 words
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.
Claim 45
Dependent Claim
52 words
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.
Claim 46
Dependent Claim
60 words
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.
Claim 47
Dependent Claim
20 words
The method of claim 44 wherein each subgroup amount has a magnitude that is independent of position within a patch.
Claim 48
Dependent Claim
19 words
The method of claim 44 wherein each subgroup amount has a magnitude that depends on position within a patch.
Claim 49
Dependent Claim
10 words
The method of claim 20 wherein the parameter is luminance.
Claim 50
Dependent Claim
10 words
The method of claim 20 wherein the parameter is chrominance.
Claim 51
Independent Claim
199 words
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.
Claim 52
Independent Claim
199 words
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.
Claim 53
Dependent Claim
31 words
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.
Claim 54
Dependent Claim
32 words
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.
Claim 55
Dependent Claim
18 words
The method of claim 49 wherein each point in the test image corresponds to an electronically represented pixel.
Claim 56
Dependent Claim
34 words
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.
Claim 57
Dependent Claim
34 words
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.
Claim 58
Dependent Claim
10 words
The method of claim 49 wherein the parameter is luminance.
Claim 59
Dependent Claim
10 words
The method of claim 49 wherein the parameter is chrominance.
Claim 60
Dependent Claim
35 words
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.
Claim 61
Independent Claim
160 words
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.
Claim 62
Independent Claim
160 words
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.
Claim 63
Dependent Claim
21 words
The apparatus of claim 58 wherein the means for generating a series of numbers generates the numbers based on a key.
Claim 64
Dependent Claim
30 words
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.
Claim 65
Dependent Claim
44 words
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.
Claim 66
Dependent Claim
54 words
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.
Claim 67
Dependent Claim
18 words
The apparatus of claim 58 wherein the series-generating means generates a series having at least 5,000 pseudo-random numbers.
Claim 68
Dependent Claim
25 words
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.
Claim 69
Dependent Claim
23 words
The apparatus of claim 58 wherein the image-altering means changes the pixel parameter values of the points by amounts based on visual perceptibility.
Claim 70
Dependent Claim
55 words
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.
Claim 71
Dependent Claim
60 words
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.
Claim 72
Dependent Claim
20 words
The apparatus of claim 67 wherein each subgroup amount has a magnitude that is independent of position within a patch.
Claim 73
Dependent Claim
19 words
The apparatus of claim 67 wherein each subgroup amount has a magnitude that depends on position within a patch.
Claim 74
Independent Claim
230 words
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.
Claim 75
Independent Claim
230 words
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.
Claim 76
Dependent Claim
20 words
The apparatus of claim 70 further comprising means for generating an indication of whether the test image contains the pattern.
Claim 77
Dependent Claim
27 words
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.
Claim 78
Dependent Claim
32 words
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.
Claim 79
Dependent Claim
32 words
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.
Claim 80
Dependent Claim
34 words
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.
Claim 81
Dependent Claim
10 words
The apparatus of claim 70 wherein the parameter is luminance.
Claim 82
Dependent Claim
10 words
The apparatus of claim 70 wherein the parameter is chrominance.
Claim 83
Dependent Claim
94 words
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.
Claim 84
Dependent Claim
94 words
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.
Claim 85
Dependent Claim
11 words
The image of claim 78 wherein the image is a photograph.
Claim 86
Dependent Claim
15 words
The image of claim 78 wherein the image is an electronically encoded array of pixels.
Claim 87
Dependent Claim
52 words
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.
Claim 88
Dependent Claim
28 words
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.
Claim 89
Dependent Claim
13 words
The image of claim 78 wherein the image is a print or lithograph.
Claim 90
Dependent Claim
10 words
The image of claim 70 wherein the parameter is luminance.
Claim 91
Dependent Claim
10 words
The image of claim 70 wherein the parameter is chrominance.
References Cited (Backward Citations)
US4499551A
Cited
US4673975A
Cited
US4783840A
Cited
US5243423A
Cited
EP0581317A2
Cited
US5398283A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-11-17 | 2001-05-19 | 2001-11-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-11-17 | 2005-05-19 | 2005-11-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-11-17 | 2009-05-19 | 2009-11-18 | $7700.00 | Window Closed / Lapsed |