|
|
|
By signal having discrete frequency component |
Method and apparatus for watermarking images6879703
Abstract
Digital watermarks are embedded in image data (102)in order to enable authentication of the image data and/or replacement of rejected portions of the image data. Authentication codes are derived by comparing selected discrete cosine transform (DCT) (104) coefficients within DCT data (106) derived from the original, spatial-domain image data. The authentication codes thus generated are embedded in DCT coefficients (612) other than the ones which were used to derive the authentication codes. The resulting, watermarked data can be sent or made available to one or more recipients who can compress or otherwise use the watermarked data. Image data derived from the watermarked data--e.g, compressed versions of the watermarked data--can be authenticated by: extracting the embedded authentication codes, comparing DCT coefficients derived from the coefficients from which the original authentication codes were generated; and determining whether the compared DCT coefficients are consistent with the extracted authentication codes.
Claims
What is claimed is:
1. An image-processing method, comprising:
comparing a first transformed-domain image datum to a second transformed-domain image datum, for deriving a first authentication code, the first transformed-domain image datum having a first transformed-domain location, and the second transformed-domain image datum having a second transformed-domain location; and
using a replacement code to replace at least a portion of a third transformed-domain image datum, for converting the third transformed-domain image datum into a fourth transformed-domain image datum, the replacement code comprising at least one of the first authentication code, a code derived from the first authentication code, a code selected based upon at least the first authentication code, and a code selected based upon at least the code derived from the first authentication code, the fourth transformed-domain image datum having a third transformed-domain location, the first transformed-domain image datum being for deriving a fifth transformed-domain image datum having a fourth transformed-domain location, the second transformed-domain image datum being for deriving a sixth transformed-domain image datum having a fifth transformed-domain location, the fourth transformed-domain image datum being for deriving a seventh transformed-domain image datum having a sixth transformed-domain location, the fourth transformed-domain location being approximately equal to the first transformed-domain location, the fifth transformed-domain location being approximately equal to the second transformed-domain location, and the sixth transformed-domain location being approximately equal to the third transformed-domain location, wherein the fifth, sixth, and seventh transformed-domain image data are for being authenticated by an authentication procedure comprising the steps of:
using an authentication code extraction function to extract a second authentication code from the seventh transformed-domain image datum,
comparing the fifth transformed-domain image datum to the sixth transformed-domain image datum, for deriving a first comparison result,
based on the second authentication code, selecting a set of at least one acceptable value of the first comparison result, and
if the first comparison result is not within the set of at least one acceptable value of the first comparison result, determining that at least one of the fifth, sixth, and seventh transformed-domain image data has been improperly altered.
2. A method according to claim 1, wherein the first transformed-domain image datum is included in a first set of transformed-domain image data, the second transformed-domain image datum is included in a second set of transformed-domain image data, the fifth transformed-domain image datum is included in a third set of transformed-domain image data, and the sixth transformed-domain image datum is included in a fourth set of transformed-domain image data, the method further comprising:
using a first secret mapping to form an association between the first and second sets of transformed-domain image data; and
using the association between the first and second sets of transformed-domain image data for selecting at least one of the first and second transformed-domain image data to be compared in the step of comparing the first transformed-domain image datum to the second transformed-domain image datum, wherein the authentication procedure further comprises the steps of:
using the first secret mapping to form an association between the third and fourth sets of transformed-domain image data, and
using the association between the third and fourth sets of transformed-domain image data for selecting at least one of the fifth and sixth transformed-domain image data to be compared in the step of comparing the fifth transformed-domain image datum to the sixth transformed-domain image datum.
3. A method according to claim 2, wherein the first and second sets of transformed-domain image data are included in a fifth set of transformed-domain image data, the third transformed-domain image datum is included in a sixth set of transformed-domain image data, the third and fourth sets of transformed-domain image data are included in a seventh set of transformed-domain image data, and the seventh transformed-domain image datum is included in an eighth set of transformed-domain image data, the method further comprising:
using a second secret mapping to form an association between the fifth and sixth sets of transformed-domain image data; and
using the association between the fifth and sixth sets of transformed-domain image data for selecting the third transformed-domain image datum to be converted, in the step of using the replacement code, into the fourth transformed-domain image datum, wherein the authentication procedure further comprises the steps of:
using the second secret mapping to form an association between the seventh and eighth sets of transformed-domain image data, and
using the association between the seventh and eighth sets of transformed-domain image data for selecting the seventh transformed-domain image datum to be a datum from which the second authentication code is extracted in the step of using the authentication code extraction function to extract the second authentication code.
4. A method according to claim 1, wherein the first and second transformed-domain image data are included in a first set of transformed-domain image data, the third transformed-domain image datum is included in a second set of transformed-domain image data, the fifth and sixth transformed-domain image data are included in a third set of transformed-domain image data, and the seventh transformed-domain image datum is included in a fourth set of transformed-domain image data, the method further comprising:
using a first secret mapping to form an association between the first and second sets of transformed-domain image data; and
using the association between the first and second sets of transformed-domain image data for selecting the third transformed-domain image datum to be converted, in the step of using the replacement code, into the fourth transformed-domain image datum, wherein the authentication procedure further comprises the steps of:
using the first secret mapping to form an association between the third and fourth sets of transformed-domain image data, and
using the association between the third and fourth sets of transformed-domain image data for selecting the seventh transformed-domain image datum to be a datum from which the second authentication code is extracted in the step of using the authentication code extraction function to extract the second authentication code.
5. A method according to claim 1, wherein the first transformed-domain image datum is included in a first set of transformed-domain image data, the second transformed-domain image datum is included in a second set of transformed-domain image data, the fifth transformed-domain image datum is included in a third set of transformed-domain image data, and the sixth transformed-domain image datum is included in a fourth set of transformed-domain image data, the method further comprising:
using a first secret transformed-domain location selection pattern for selecting the first transformed-domain image datum to be compared in the step of comparing the first transformed-domain image datum to the second transformed-domain image datum, the first secret transformed-domain location selection pattern comprising at least a first datum selection location, the first transformed-domain location being approximately equal to the first datum selection location in a coordinate system of the first set of transformed-domain image data; and
using the first secret transformed-domain location selection pattern for selecting the second transformed-domain image datum to be compared in the step of comparing the first transformed-domain image datum to the second transformed-domain image datum, the second transformed-domain location being approximately equal to the first datum selection location in a coordinate system of the second set of transformed-domain image data, wherein the authentication procedure further comprises the steps of:
using the first secret transformed-domain location selection pattern for selecting the fifth transformed-domain image datum to be compared in the step of comparing the fifth transformed-domain image datum to the sixth transformed-domain image datum, the fourth transformed-domain location being approximately equal to the first datum selection location in a coordinate system of the third set of transformed-domain image data, and
using the first secret transformed-domain location selection pattern for selecting the sixth transformed-domain image datum to be compared in the step of comparing the fifth transformed-domain image datum to the sixth transformed-domain image datum, the fifth transformed-domain location being approximately equal to the first datum selection location in a coordinate system of the fourth set of transformed-domain image data.
6. A method according to claim 5, wherein the third transformed-domain image datum is included in a fifth set of transformed-domain image data, and the seventh transformed-domain image datum is included in a sixth set of transformed-domain image data, the method further comprising using a second secret transformed-domain location selection pattern for selecting the third transformed-domain image datum to be converted, in the step of using the replacement code, into the fourth transformed-domain image datum, the third transformed-domain image datum having the third transformed-domain location, the second secret transformed-domain location selection pattern comprising at least a second datum selection location, the third transformed-domain location being approximately equal to the second datum selection location in a coordinate system of the fifth set of transformed-domain image data, wherein the authentication procedure further comprises using the second secret transformed-domain location selection pattern for selecting the seventh transformed-domain image datum to be a datum from which the second authentication code is extracted in the step of using the authentication code extraction function to extract the second authentication code, the sixth transformed-domain location being approximately equal to the second datum selection location in a coordinate system of the sixth set of transformed-domain image data.
7. A method according to claim 1, wherein the third transformed-domain image datum is included in a first set of transformed-domain image data, and the seventh transformed-domain image datum is included in a second set of transformed-domain image data, the method further comprising using a secret transformed-domain location selection pattern for selecting the third transformed-domain image datum to be converted, in the step of using the replacement code, into the fourth transformed-domain image datum, the third transformed-domain image datum having the third transformed-domain location, the secret transformed-domain location selection pattern comprising at least a datum selection location, the third transformed-domain location being approximately equal to the datum selection location in a coordinate system of the first set of transformed-domain image data, wherein the authentication procedure further comprises using the secret transformed-domain location selection pattern for selecting the seventh transformed-domain image datum to be a datum from which the second authentication code is extracted in the step of using the authentication code extraction function to extract the second authentication code, the sixth transformed-domain location being approximately equal to the datum selection location in a coordinate system of the second set of transformed-domain image data.
8. A method according to claim 1, wherein the portion of the third transformed-domain image datum comprises a bit of the third transformed-domain image datum, and the first authentication code comprises an authentication bit, the method further comprising processing the authentication bit and a bit of a secret key by a binary operation, for deriving an encrypted bit, the replacement code comprising at least one of the encrypted bit, a code derived from the encrypted bit, and a code selected based upon the encrypted bit.
9. A method according to claim 1, wherein the portion of the third transformed-domain image datum comprises a bit of the third transformed-domain image datum, and the replacement code comprises at least one of a bit of the first authentication code and a code selected based upon the bit of the first authentication code.
10. A method according to claim 1, wherein the authentication procedure further comprises:
using the authentication code extraction function to extract a first set of authentication codes from at least one portion of a first set of transformed-domain image data, the first set of transformed-domain image data including the sixth transformed-domain image datum;
comparing at least one portion of a second set of transformed-domain image data to at least one portion of a third set of transformed-domain image data, for deriving a first set of comparison results;
based on each of the first set of authentication codes, selecting a set of at least one acceptable value of a member of the first set of comparison results associated with the each of the first set of authentication codes;
if the member of the first set of comparison results associated with the each of the first set of authentication codes is within the set of at least one acceptable value of the member of the first set of comparison results associated with the each of the first set of authentication codes, determining that the first set of transformed-domain image data has not been improperly altered.
11. A method according to claim 10, wherein the authentication procedure further comprises:
using the authentication code extraction function to extract a second set of authentication codes from at least one portion of a fourth set of transformed-domain image data;
comparing at least one portion of a fifth set of transformed-domain image data to at least one portion of a sixth set of transformed-domain image data, for deriving a second set of comparison results, the fifth set of transformed-domain image data including the seventh transformed-domain image datum;
based on each of the second set of authentication codes, selecting a set of at least one acceptable value of a member of the second set of comparison results associated with the each of the second set of authentication codes;
if the member of the second set of comparison results associated with the each of the second set of authentication codes is within the set of at least one acceptable value of the member of the second set of comparison results associated with the each of the second set of authentication codes, determining that the fifth set of transformed-domain image data has not been improperly altered.
12. A method according to claim 11, wherein the authentication procedure further comprises the step of: if the member of the first set of comparison results associated with the each of the first set of authentication codes is within the set of at least one acceptable value of the member of the first set of comparison results associated with the each of the first set of authentication codes, and if the member of the second set of comparison results associated with the each of the second set of authentication codes is within the set of at least one acceptable value of the member of the second set of comparison results associated with the each of the second set of authentication codes, determining that a seventh set of transformed-domain image data has been improperly altered, the seventh set of transformed-domain image data including the fifth transformed-domain image datum.
13. A method according to claim 10, wherein the authentication procedure further comprises:
using the authentication code extraction function to extract a second set of authentication codes from at least one portion of a fourth set of transformed-domain image data, the fourth set of transformed-domain image data including the fifth transformed-domain image datum;
comparing at least one portion of a fifth set of transformed-domain image data to at least one portion of a sixth set of transformed-domain image data, for deriving a second set of comparison results;
based on each of the second set of authentication codes, selecting a set of at least one acceptable value of a member of the second set of comparison results associated with the each of the second set of authentication codes;
if the member of the second set of comparison results associated with the each of the second set of authentication codes is within the set of at least one acceptable value of the member of the second set of comparison results associated with the each of the second set of authentication codes, determining that the fourth set of transformed-domain image data has not been improperly altered.
14. A method according to claim 13, wherein the authentication procedure further comprises the step of: if the member of the first set of comparison results associated with the each of the first set of authentication codes is within the set of at least one acceptable value of the member of the first set of comparison results associated with the each of the first set of authentication codes, and if the member of the second set of comparison results associated with the each of the second set of authentication codes is within the set of at least one acceptable value of the member of the second set of comparison results associated with the each of the second set of authentication codes, determining that a seventh set of transformed-domain image data has been improperly altered, the seventh set of transformed-domain image data including the seventh transformed-domain image datum.
15. An image-processing method, comprising:
encoding by an encoding function a first set of transformed-domain image data, for deriving a set of image data recovery codes comprising a first image data recovery code, the first set of transformed-domain image data being included in a second set of transformed-domain image data, the second set of transformed-domain image data being derived from a first set of spatial domain image data; and
using a replacement code to replace at least a portion of a first transformed-domain image datum, for converting the first transformed-domain image datum into a second transformed-domain image datum, the first transformed-domain image datum being included in a third set of transformed-domain image data, the third set of transformed-domain image data being derived from the first set of spatial domain image data, the replacement code comprising at least one of the first image data recovery code, a code derived from the first image data recovery code, a code selected based upon at least the first image data recovery code, and a code selected based upon at least the code derived from the first image data recovery code, the second transformed-domain image datum being for deriving a third transformed-domain image datum, the first set of spatial domain image data being for deriving a fourth set of transformed-domain image data, the third transformed-domain image datum being for deriving, by a recovery procedure, an approximation data set for replacing the fourth set of transformed-domain image data, and the recovery procedure comprising the steps of:
using a recovery code extraction function to extract a second image data recovery code from the third transformed-domain image datum, the second image data recovery code being approximately equal to the first image data recovery code; and
decoding by a decoding function at least the second image data recovery code, for deriving the approximation data set, the decoding function comprising a functional inverse of the encoding function.
16. A method according to claim 15, further comprising:
averaging a second set of spatial domain image data, for deriving a first reduced image datum;
averaging a third set of spatial domain image data, for deriving a second reduced image datum, the first and second reduced image data being included in a reduced set of spatial domain image data, and the second and third sets of spatial domain image data being included in the first set of spatial domain image data;
domain-transforming the reduced set of spatial domain image data, for deriving a fifth set of transformed-domain image data; and
quantizing the fifth set of transformed-domain image data, for deriving the first set of transformed-domain image data.
17. A method according to claim 16, wherein the portion of the first transformed-domain image datum comprises a bit of the first transformed-domain image datum, and the first image data recovery code comprises a data recovery bit.
18. A method according to claim 17, further comprising processing the data recovery bit and a bit of a secret key by a binary operation, for deriving an encrypted bit, the replacement code comprising at least one of the encrypted bit, a code derived from the encrypted bit, and a code selected based upon the encrypted bit.
19. A method according to claim 15, wherein the portion of the first transformed-domain image datum comprises a bit of the first transformed-domain image datum, and the first image data recovery code comprises a data recovery bit.
20. A method according to claim 19, further comprising processing the data recovery bit and a bit of a secret key by a binary operation, for deriving an encrypted bit, the replacement code comprising at least one of the encrypted bit, a code derived from the encrypted bit, and a code selected based upon the encrypted bit.
21. A method according to claim 15, wherein the encoding function comprises an entropy encoding function.
22. A method according to claim 21, wherein the entropy encoding function comprises at least one of a Huffman encoding function and a JPEG entropy encoding function.
23. An image-processing method, comprising:
quantizing a first set of transformed-domain image data based on a first quantization step size, for deriving a second set of transformed-domain image data, the second set of transformed-domain image data including at least a first transformed-domain image datum; and
using a replacement code to replace at least a portion of the first transformed-domain image datum, for converting the first transformed-domain image datum into a second transformed-domain image datum, the second transformed-domain image datum being included in a third set of transformed-domain image data, the replacement code comprising at least one of a watermark code, a code derived from the watermark code, a code selected based on the watermark code, and a code selected based upon at least the code derived from the watermark code, wherein the third set of transformed-domain image data is for being altered by an alteration procedure for deriving a fourth set of transformed-domain image data, the alteration procedure comprising at least one of: (1) quantizing the third set of transformed-domain image data based on a second quantization step size, the second quantization step size being no greater than the first quantization step size, (2) transforming a data encoding format of the third set of transformed-domain image data into a different data encoding format, and (3) filtering the third set of transformed domain image data, the fourth set of transformed-domain image data including at least a third transformed-domain image datum, and the third transformed-domain image datum being derived from the second transformed-domain image datum, wherein the third transformed-domain image datum is for being processed by a watermark extraction procedure for extracting the watermark code from the third transformed-domain image datum, the watermark extraction procedure comprising the steps of:
requantizing the third transformed-domain image datum based on the first quantization step size, for generating a fourth transformed-domain image datum, and
processing the fourth transformed-domain image datum by a watermark extraction function, for deriving an extracted code approximately equal to the watermark code.
24. A method according to claim 23, wherein the first set of transformed domain image data includes a fifth transformed-domain image datum, the first transformed-domain datum being derived from the fifth transformed-domain image datum, and the method further comprising deriving the watermark code based on at least one datum derived from at least a first portion of a set of spatial domain image data, the fifth transformed-domain image datum being derived from a second portion of the set of spatial domain image data.
25. A method according to claim 24, further comprising:
using a secret mapping to form an association between at least the first transformed-domain image datum and at least the datum derived from the first portion of the set of spatial domain image data; and
using the association between the at least the first transformed-domain image datum and the at least the datum derived from the first portion of the set of spatial domain image data for selecting the first transformed-domain image datum to be converted, in the step of using the first replacement code, into the second transformed-domain image datum.
26. A method according to claim 23, wherein the first transformed-domain image datum has a secret transformed-domain location.
27. An image-processing apparatus, comprising:
a first processor for comparing a first transformed-domain image datum to a second transformed-domain image datum, for deriving a first authentication code, the first transformed-domain image datum having a first transformed-domain location, and the second transformed-domain image datum having a second transformed-domain location; and
a second processor for using a replacement code to replace at least a portion of a third transformed-domain image datum, for converting the third transformed-domain image datum into a fourth transformed-domain image datum, the replacement code comprising at least one of the first authentication code, a code derived from the first authentication code, a code selected based upon at least the first authentication code, and a code selected based upon at least the code derived from the first authentication code, the fourth transformed-domain image datum having a third transformed-domain location, the first transformed-domain image datum being for deriving a fifth transformed-domain image datum having a fourth transformed-domain location, the second transformed-domain image datum being for deriving a sixth transformed-domain image datum having a fifth transformed-domain location, the fourth transformed-domain image datum being for deriving a seventh transformed-domain image datum having a sixth transformed-domain location, the fourth transformed-domain location being approximately equal to the first transformed-domain location, the fifth transformed-domain location being approximately equal to the second transformed-domain location, and the sixth transformed-domain location being approximately equal to the third transformed-domain location, wherein the fifth, sixth, and seventh transformed-domain image data are for being authenticated by an authentication processor comprising:
a third processor for using an authentication code extraction function to extract a second authentication code from the seventh transformed-domain image datum,
a fourth processor for comparing the fifth transformed-domain image datum to the sixth transformed-domain image datum, for deriving a first comparison result,
a fifth processor for selecting, based on the second authentication code, a set of at least one acceptable value of the first comparison result, and
a sixth processor for determining that at least one of the fifth, sixth, and seventh transformed-domain image data has been improperly altered if the first comparison result is not within the set of at least one acceptable value of the first comparison result.
28. An apparatus according to claim 27, wherein the first transformed-domain image datum is included in a first set of transformed-domain image data, the second transformed-domain image datum is included in a second set of transformed-domain image data, the fifth transformed-domain image datum is included in a third set of transformed-domain image data, and the sixth transformed-domain image datum is included in a fourth set of transformed-domain image data, the apparatus further comprising:
a seventh processor for using a first secret mapping to form an association between the first and second sets of transformed-domain image data; and
an eighth processor for using the association between the first and second sets of transformed-domain image data for selecting at least one of the first and second transformed-domain image data to be compared by the first processor, wherein the authentication processor further comprises:
a ninth processor for using the first secret mapping to form an association between the third and fourth sets of transformed-domain image data, and
a tenth processor for using the association between the third and fourth sets of transformed-domain image data for selecting at least one of the fifth and sixth transformed-domain image data to be compared by the fourth processor.
29. An apparatus according to claim 28, wherein the first and second sets of transformed-domain image data are included in a fifth set of transformed-domain image data, the third transformed-domain image datum is included in a sixth set of transformed-domain image data, the third and fourth sets of transformed-domain image data are included in a seventh set of transformed-domain image data, and the seventh transformed-domain image datum is included in an eighth set of transformed-domain image data, the apparatus further comprising:
an eleventh processor for using a second secret mapping to form an association between the fifth and sixth sets of transformed-domain image data; and
a twelfth processor for using the association between the fifth and sixth sets of transformed-domain image data for selecting the third transformed-domain image datum to be converted, by the second processor, into the fourth transformed-domain image datum, wherein the authentication processor further comprises:
a thirteenth processor for using the second secret mapping to form an association between the seventh and eighth sets of transformed-domain image data, and
a fourteenth processor for using the association between the seventh and eighth sets of transformed-domain image data for selecting the seventh transformed-domain image datum to be a datum from which the second authentication code is extracted by the third processor.
30. An apparatus according to claim 27, wherein the first and second transformed-domain image data are included in a first set of transformed-domain image data, the third transformed-domain image datum is included in a second set of transformed-domain image data, the fifth and sixth transformed-domain image data are included in a third set of transformed-domain image data, and the seventh transformed-domain image datum is included in a fourth set of transformed-domain image data, the apparatus further comprising:
a seventh processor for using a first secret mapping to form an association between the first and second sets of transformed-domain image data; and
an eighth processor for using the association between the first and second sets of transformed-domain image data for selecting the third transformed-domain image datum to be converted, by the second processor, into the fourth transformed-domain image datum, wherein the authentication processor further comprises:
a ninth processor for using the first secret mapping to form an association between the third and fourth sets of transformed-domain image data, and
a tenth processor for using the association between the third and fourth sets of transformed-domain image data for selecting the seventh transformed-domain image datum to be a datum from which the second authentication code is extracted by the third processor.
31. An apparatus according to claim 27, wherein the first transformed-domain image datum is included in a first set of transformed-domain image data, the second transformed-domain image datum is included in a second set of transformed-domain image data, the fifth transformed-domain image datum is included in a third set of transformed-domain image data, and the sixth transformed-domain image datum is included in a fourth set of transformed-domain image data, the apparatus further comprising:
a seventh processor for using a first secret transformed-domain location selection pattern for selecting the first transformed-domain image datum to be compared by the first processor, the first secret transformed-domain location selection pattern comprising at least a first datum selection location, the first transformed-domain location being approximately equal to the first datum selection location in a coordinate system of the first set of transformed-domain image data; and
an eighth processor for using the first secret transformed-domain location selection pattern for selecting the second transformed-domain image datum to be compared by the first processor, the second transformed-domain location being approximately equal to the first datum selection location in a coordinate system of the second set of transformed-domain image data, wherein the authentication processor further comprises:
a ninth processor for using the first secret transformed-domain location selection pattern for selecting the fifth transformed-domain image datum to be compared by the fourth processor, the fourth transformed-domain location being approximately equal to the first datum selection location in a coordinate system of the third set of transformed-domain image data, and
a tenth processor for using the first secret transformed-domain location selection pattern for selecting the sixth transformed-domain image datum to be compared by the fourth processor, the fifth transformed-domain location being approximately equal to the first datum selection location in a coordinate system of the fourth set of transformed-domain image data.
32. An apparatus according to claim 31, wherein the third transformed-domain image datum is included in a fifth set of transformed-domain image data, and the seventh transformed-domain image datum is included in a sixth set of transformed-domain image data, the apparatus further comprising an eleventh processor for using a second secret transformed-domain location selection pattern for selecting the third transformed-domain image datum to be converted, by the second processor, into the fourth transformed-domain image datum, the third transformed-domain image datum having the third transformed-domain location, the second secret transformed-domain location selection pattern comprising at least a second datum selection location, the third transformed-domain location being approximately equal to the second datum selection location in a coordinate system of the fifth set of transformed-domain image data, wherein the authentication processor further comprises a twelfth processor for using the second secret transformed-domain location selection pattern for selecting the seventh transformed-domain image datum to be a datum from which the second authentication code is extracted by the third processor, the sixth transformed-domain location being approximately equal to the second datum selection location in a coordinate system of the sixth set of transformed-domain image data.
33. An apparatus according to claim 27, wherein the third transformed-domain image datum is included in a first set of transformed-domain image data, and the seventh transformed-domain image datum is included in a second set of transformed-domain image data, the apparatus further comprising a seventh processor for using a secret transformed-domain location selection pattern for selecting the third transformed-domain image datum to be converted, by the second processor, into the fourth transformed-domain image datum, the third transformed-domain image datum having the third transformed-domain location, the secret transformed-domain location selection pattern comprising at least a datum selection location, the third transformed-domain location being approximately equal to the datum selection location in a coordinate system of the first set of transformed-domain image data, wherein the authentication processor further comprises an eighth processor for using the secret transformed-domain location selection pattern for selecting the seventh transformed-domain image datum to be a datum from which the second authentication code is extracted by the third processor, the sixth transformed-domain location being approximately equal to the datum selection location in a coordinate system of the second set of transformed-domain image data.
34. An apparatus according to claim 27, wherein the portion of the third transformed-domain image datum comprises a bit of the third transformed-domain image datum, and the first authentication code comprises an authentication bit, the apparatus further comprising a seventh processor for using a binary operation to process the authentication bit and a bit of a secret key, for deriving an encrypted bit, the replacement code comprising at least one of the encrypted bit, a code derived from the encrypted bit, and a code selected based upon the encrypted bit.
35. An apparatus according to claim 27, wherein the portion of the third transformed-domain image datum comprises a bit of the third transformed-domain image datum, and the replacement code comprises at least one of a bit of the first authentication code and a code selected based upon the bit of the first authentication code.
36. An apparatus according to claim 27, wherein the authentication processor further comprises:
a seventh processor for using the authentication code extraction function to extract a first set of authentication codes from at least one portion of a first set of transformed-domain image data, the first set of transformed-domain image data including the sixth transformed-domain image datum;
an eighth processor for comparing at least one portion of a second set of transformed-domain image data to at least one portion of a third set of transformed-domain image data, for deriving a first set of comparison results;
a ninth processor for selecting, based on each of the first set of authentication codes, a set of at least one acceptable value of a member of the first set of comparison results associated with the each of the first set of authentication codes;
a tenth processor for determining that the first set of transformed-domain image data has not been improperly altered if the member of the first set of comparison results associated with the each of the first set of authentication codes is within the set of at least one acceptable value of the member of the first set of comparison results associated with the each of the first set of authentication codes.
37. An apparatus according to claim 36, wherein the authentication processor further comprises:
an eleventh processor for using the authentication code extraction function to extract a second set of authentication codes from at least one portion of a fourth set of transformed-domain image data;
a twelfth processor for comparing at least one portion of a fifth set of transformed-domain image data to at least one portion of a sixth set of transformed-domain image data, for deriving a second set of comparison results, the fifth set of transformed-domain image data including the seventh transformed-domain image datum;
a thirteenth processor for selecting, based on each of the second set of authentication codes, a set of at least one acceptable value of a member of the second set of comparison results associated with the each of the second set of authentication codes;
a fourteenth processor for determining that the fifth set of transformed-domain image data has not been improperly altered if the member of the second set of comparison results associated with the each of the second set of authentication codes is within the set of at least one acceptable value of the member of the second set of comparison results associated with the each of the second set of authentication codes.
38. An apparatus according to claim 37, wherein the authentication processor further comprises a fifteenth processor for determining that a seventh set of transformed-domain image data has been improperly altered if: (a) the member of the first set of comparison results associated with the each of the first set of authentication codes is within the set of at least one acceptable value of the member of the first set of comparison results associated with the each of the first set of authentication codes; and (b) the member of the second set of comparison results associated with the each of the second set of authentication codes is within the set of at least one acceptable value of the member of the second set of comparison results associated with the each of the second set of authentication codes, the seventh set of transformed-domain image data including the fifth transformed-domain image datum.
39. An apparatus according to claim 36, wherein the authentication processor further comprises:
an eleventh processor for using the authentication code extraction function to extract a second set of authentication codes from at least one portion of a fourth set of transformed-domain image data, the fourth set of transformed-domain image data including the fifth transformed-domain image datum;
a twelfth processor for comparing at least one portion of a fifth set of transformed-domain image data to at least one portion of a sixth set of transformed-domain image data, for deriving a second set of comparison results;
a thirteenth processor for selecting, based on each of the second set of authentication codes, a set of at least one acceptable value of a member of the second set of comparison results associated with the each of the second set of authentication codes;
a fourteenth processor for determining that the fourth set of transformed-domain image data has not been improperly altered if the member of the second set of comparison results associated with the each of the second set of authentication codes is within the set of at least one acceptable value of the member of the second set of comparison results associated with the each of the second set of authentication codes.
40. An apparatus according to claim 39, wherein the authentication processor further comprises a fifteenth processor for determining that a seventh set of transformed-domain image data has been improperly altered if: (a) the member of the first set of comparison results associated with the each of the first set of authentication codes is within the set of at least one acceptable value of the member of the first set of comparison results associated with the each of the first set of authentication codes; and (b) the member of the second set of comparison results associated with the each of the second set of authentication codes is within the set of at least one acceptable value of the member of the second set of comparison results associated with the each of the second set of authentication codes, the seventh set of transformed-domain image data including the seventh transformed-domain image datum.
41. An image-processing apparatus, comprising:
a first processor for using an encoding function to encode a first set of transformed-domain image data, for deriving a set of image data recovery codes comprising a first image data recovery code, the first set of transformed-domain image data being included in a second set of transformed-domain image data, the second set of transformed-domain image data being derived from a first set of spatial domain image data; and
a second processor for using a replacement code to replace at least a portion of a first transformed-domain image datum, for converting the first transformed-domain image datum into a second transformed-domain image datum, the first transformed-domain image datum being included in a third set of transformed-domain image data, the third set of transformed-domain image data being derived from the first set of spatial domain image data, the replacement code comprising at least one of the first image data recovery code, a code derived from the first image data recovery code, a code selected based upon at least the first image data recovery code, and a code selected based upon at least the code derived from the first image data recovery code, the second transformed-domain image datum being for deriving a third transformed-domain image datum, the first set of spatial domain image data being for deriving a fourth set of transformed-domain image data, the third transformed-domain image datum being for deriving, by a recovery processor, an approximation data set for replacing the fourth set of transformed-domain image data, and the recovery processor comprising:
a third processor for using a recovery code extraction function to extract a second image data recovery code from the third transformed-domain image datum, the second image data recovery code being approximately equal to the first image data recovery code; and
a fourth processor for using a decoding function to decode at least the second image data recovery code, for deriving the approximation data set, the decoding function comprising a functional inverse of the encoding function.
42. An apparatus according to claim 41, further comprising:
a fifth processor for averaging a second set of spatial domain image data, for deriving a first reduced image datum;
a sixth processor for averaging a third set of spatial domain image data, for deriving a second reduced image datum, the first and second reduced image data being included in a reduced set of spatial domain image data, and the second and third sets of spatial domain image data being included in the first set of spatial domain image data;
a seventh processor for domain-transforming the reduced set of spatial domain image data, for deriving a fifth set of transformed-domain image data; and
an eighth processor for quantizing the fifth set of transformed-domain image data, for deriving the first set of transformed-domain image data.
43. An apparatus according to claim 42, wherein the portion of the first transformed-domain image datum comprises a bit of the first transformed-domain image datum, and the first image data recovery code comprises a data recovery bit.
44. An apparatus according to claim 43, further comprising a ninth processor for using a binary operation to process the data recovery bit and a bit of a secret key, for deriving an encrypted bit, the replacement code comprising at least one of the encrypted bit, a code derived from the encrypted bit, and a code selected based upon the encrypted bit.
45. An apparatus according to claim 41, wherein the portion of the first transformed-domain image datum comprises a bit of the first transformed-domain image datum, and the first image data recovery code comprises a data recovery bit.
46. An apparatus according to claim 45, further comprising a fifth processor for using a binary operation to process the data recovery bit and a bit of a secret key, for deriving an encrypted bit, the replacement code comprising at least one of the encrypted bit, a code derived from the encrypted bit, and a code selected based upon the encrypted bit.
47. An apparatus according to claim 41, wherein the encoding function comprises an entropy encoding function.
48. An apparatus according to claim 47, wherein the entropy encoding function comprises at least one of a Huffman encoding function and a JPEG entropy encoding function.
49. An image-processing apparatus, comprising:
a first processor for quantizing a first set of transformed-domain image data based on a first quantization step size, for deriving a second set of transformed-domain image data, the second set of transformed-domain image data including at least a first transformed-domain image datum; and
a second processor for using a replacement code to replace at least a portion of the first transformed-domain image datum, for converting the first transformed-domain image datum into a second transformed-domain image datum, the second transformed-domain image datum being included in a third set of transformed-domain image data, the replacement code comprising at least one of a watermark code, a code derived from the watermark code, a code selected based on the watermark code, and a code selected based upon at least the code derived from the watermark code, wherein the third set of transformed-domain image data is for being altered by an alteration processor for deriving a fourth set of transformed-domain image data, the alteration processor comprising at least one of: (1) a quantization processor for quantizing the third set of transformed-domain image data based on a second quantization step size, the second quantization step size being no greater than the first quantization step size, (2) a data encoding format transformation processor for transforming a data encoding format of the third set of transformed-domain image data into a different data encoding format, and (3) an image filtering processor for filtering the third set of transformed-domain image data, the fourth set of transformed-domain image data including at least a third transformed-domain image datum, and the third transformed-domain image datum being derived from the second transformed-domain image datum, wherein the third transformed-domain image datum is for being processed by a watermark extraction processor for extracting the watermark code from the third transformed-domain image datum, the watermark extraction processor comprising:
a third processor for requantizing the third transformed-domain image datum based on the first quantization step size, for generating a fourth transformed-domain image datum, and
a fourth processor for processing the fourth transformed-domain image datum by a watermark extraction function, for deriving an extracted code approximately equal to the watermark code.
50. An apparatus according to claim 49, wherein the first set of transformed-domain image data includes a fifth transformed-domain image datum, the first transformed-domain datum being derived from the fifth transformed-domain image datum, and the apparatus further comprising a fifth processor for deriving the watermark code based on at least one datum derived from at least a first portion of a set of spatial domain image data, the fifth transformed-domain image datum being derived from a second portion of the set of spatial domain image data.
51. An apparatus according to claim 50, further comprising:
a sixth processor for using a secret mapping to form an association between at least the first transformed-domain image datum and at least the datum derived from the first portion of the set of spatial domain image data; and
a seventh processor for using the association between the at least the first transformed-domain image datum and the at least the datum derived from the first portion of the set of spatial domain image data for selecting the first transformed-domain image datum to be converted, by the second processor, into the second transformed-domain image datum.
52. An apparatus according to claim 49, wherein the first transformed-domain image datum has a secret transformed-domain location.
53. A computer-readable medium having a set of instructions operable to direct a processor to perform the steps of:
comparing a first transformed-domain image datum to a second transformed-domain image datum, for deriving a first authentication code, the first transformed-domain image datum having a first transformed-domain location, and the second transformed-domain image datum having a second transformed-domain location; and
using a replacement code to replace at least a portion of a third transformed-domain image datum, for converting the third transformed-domain image datum into a fourth transformed-domain image datum, the replacement code comprising at least one of the first authentication code, a code derived from the first authentication code, a code selected based upon at least the first authentication code, and a code selected based upon at least the code derived from the first authentication code, the fourth transformed-domain image datum having a third transformed-domain location, the first transformed-domain image datum being for deriving a fifth transformed-domain image datum having a fourth transformed-domain location, the second transformed-domain image datum being for deriving a sixth transformed-domain image datum having a fifth transformed-domain location, the fourth transformed-domain image datum being for deriving a seventh transformed-domain image datum having a sixth transformed-domain location, the fourth transformed-domain location being approximately equal to the first transformed-domain location, the fifth transformed-domain location being approximately equal to the second transformed-domain location, and the sixth transformed-domain location being approximately equal to the third transformed-domain location, wherein the fifth, sixth, and seventh transformed-domain image data are for being authenticated by an authentication procedure comprising the steps of:
using an authentication code extraction function to extract a second authentication code from the seventh transformed-domain image datum,
comparing the fifth transformed-domain image datum to the sixth transformed-domain image datum, for deriving a first comparison result,
based on the second authentication code, selecting a set of at least one acceptable value of the first comparison result, and
if the first comparison result is not within the set of at least one acceptable value of the first comparison result, determining that at least one of the fifth, sixth, and seventh transformed-domain image data has been improperly altered.
54. A computer-readable medium according to claim 53, wherein the first transformed-domain image datum is included in a first set of transformed-domain image data, the second transformed-domain image datum is included in a second set of transformed-domain image data, the fifth transformed-domain image datum is included in a third set of transformed-domain image data, the sixth transformed-domain image datum is included in a fourth set of transformed-domain image data, and the set of instructions is further operable to direct the processor to perform the steps of:
using a first secret mapping to form an association between the first and second sets of transformed-domain image data; and
using the association between the first and second sets of transformed-domain image data for selecting at least one of the first and second transformed-domain image data to be compared in the step of comparing the first transformed-domain image datum to the second transformed-domain image datum, wherein the authentication procedure further comprises the steps of:
using the first secret mapping to form an association between the third and fourth sets of transformed-domain image data, and
using the association between the third and fourth sets of transformed-domain image data for selecting at least one of the fifth and sixth transformed-domain image data to be compared in the step of comparing the fifth transformed-domain image datum to the sixth transformed-domain image datum.
55. A computer-readable medium according to claim 54, wherein the first and second sets of transformed-domain image data are included in a fifth set of transformed-domain image data, the third transformed-domain image datum is included in a sixth set of transformed-domain image data, the third and fourth sets of transformed-domain image data are included in a seventh set of transformed-domain image data, the seventh transformed-domain image datum is included in an eighth set of transformed-domain image data, and the set of instructions is further operable to direct the processor to perform the steps of:
using a second secret mapping to form an association between the fifth and sixth sets of transformed-domain image data; and
using the association between the fifth and sixth sets of transformed-domain image data for selecting the third transformed-domain image datum to be converted, in the step of using the replacement code, into the fourth transformed-domain image datum, wherein the authentication procedure further comprises the steps of:
using the second secret mapping to form an association between the seventh and eighth sets of transformed-domain image data, and
using the association between the seventh and eighth sets of transformed-domain image data for selecting the seventh transformed-domain image datum to be a datum from which the second authentication code is extracted in the step of using the authentication code extraction function to extract the second authentication code.
56. A computer-readable medium according to claim 53, wherein the first and second transformed-domain image data are included in a first set of transformed-domain image data, the third transformed-domain image datum is included in a second set of transformed-domain image data, the fifth and sixth transformed-domain image data are included in a third set of transformed-domain image data, the seventh transformed-domain image datum is included in a fourth set of transformed-domain image data, and the set of instructions is further operable to direct the processor to perform the steps of:
using a first secret mapping to form an association between the first and second sets of transformed-domain image data; and
using the association between the first and second sets of transformed-domain image data for selecting the third transformed-domain image datum to be converted, in the step of using the replacement code, into the fourth transformed-domain image datum, wherein the authentication procedure further comprises the steps of:
using the first secret mapping to form an association between the third and fourth sets of transformed-domain image data, and
using the association between the third and fourth sets of transformed-domain image data for selecting the seventh transformed-domain image datum to be a datum from which the second authentication code is extracted in the step of using the authentication code extraction function to extract the second authentication code.
57. A computer-readable medium according to claim 53, wherein the first transformed-domain image datum is included in a first set of transformed-domain image data, the second transformed-domain image datum is included in a second set of transformed-domain image data, the fifth transformed-domain image datum is included in a third set of transformed-domain image data, the sixth transformed-domain image datum is included in a fourth set of transformed-domain image data, and the set of instructions is further operable to direct the processor to perform the steps of:
using a first secret transformed-domain location selection pattern for selecting the first transformed-domain image datum to be compared in the step of comparing the first transformed-domain image datum to the second transformed-domain image datum, the first secret transformed-domain location selection pattern comprising at least a first datum selection location, the first transformed-domain location being approximately equal to the first datum selection location in a coordinate system of the first set of transformed-domain image data; and
using the first secret transformed-domain location selection pattern for selecting the second transformed-domain image datum to be compared in the step of comparing the first transformed-domain image datum to the second transformed-domain image datum, the second transformed-domain location being approximately equal to the first datum selection location in a coordinate system of the second set of transformed-domain image data, wherein the authentication procedure further comprises the steps of:
using the first secret transformed-domain location selection pattern for selecting the fifth transformed-domain image datum to be compared in the step of comparing the fifth transformed-domain image datum to the sixth transformed-domain image datum, the fourth transformed-domain location being approximately equal to the first datum selection location in a coordinate system of the third set of transformed-domain image data, and
using the first secret transformed-domain location selection pattern for selecting the sixth transformed-domain image datum to be compared in the step of comparing the fifth transformed-domain image datum to the sixth transformed-domain image datum, the fifth transformed-domain location being approximately equal to the first datum selection location in a coordinate system of the fourth set of transformed-domain image data.
58. A computer-readable medium according to claim 57, wherein the third transformed-domain image datum is included in a fifth set of transformed-domain image data, the seventh transformed-domain image datum is included in a sixth set of transformed-domain image data, and the set of instructions is further operable to direct the processor to perform the step of using a second secret transformed-domain location selection pattern for selecting the third transformed-domain image datum to be converted, in the step of using the replacement code, into the fourth transformed-domain image datum, the third transformed-domain image datum having the third transformed-domain location, the second secret transformed-domain location selection pattern comprising at least a second datum selection location, the third transformed-domain location being approximately equal to the second datum selection location in a coordinate system of the fifth set of transformed-domain image data, wherein the authentication procedure further comprises using the second secret transformed-domain location selection pattern for selecting the seventh transformed-domain image datum to be a datum from which the second authentication code is extracted in the step of using the authentication code extraction function to extract the second authentication code, the sixth transformed-domain location being approximately equal to the second datum selection location in a coordinate system of the sixth set of transformed-domain image data.
59. A computer-readable medium according to claim 53, wherein the third transformed-domain image datum is included in a first set of transformed-domain image data, the seventh transformed-domain image datum is included in a second set of transformed-domain image data, and the set of instructions is further operable to direct the processor to perform the step of using a secret transformed-domain location selection pattern for selecting the third transformed-domain image datum to be converted, in the step of using the replacement code, into the fourth transformed-domain image datum, the third transformed-domain image datum having the third transformed-domain location, the secret transformed-domain location selection pattern comprising at least a datum selection location, the third transformed-domain location being approximately equal to the datum selection location in a coordinate system of the first set of transformed-domain image data, wherein the authentication procedure further comprises using the secret transformed-domain location selection pattern for selecting the seventh transformed-domain image datum to be a datum from which the second authentication code is extracted in the step of using the authentication code extraction function to extract the second authentication code, the sixth transformed-domain location being approximately equal to the datum selection location in a coordinate system of the second set of transformed-domain image data.
60. A computer-readable medium according to claim 53, wherein the portion of the third transformed-domain image datum comprises a bit of the third transformed-domain image datum, the first authentication code comprises an authentication bit, and the set of instructions is further operable to direct the processor to perform the step of processing the authentication bit and a bit of a secret key by a binary operation, for deriving an encrypted bit, the replacement code comprising at least one of the encrypted bit, a code derived from the encrypted bit, and a code selected based upon the encrypted bit.
61. A computer-readable medium according to claim 53, wherein the portion of the third transformed-domain image datum comprises a bit of the third transformed-domain image datum, and the replacement code comprises at least one of a bit of the first authentication code and a code selected based upon the bit of the first authentication code.
62. A computer-readable medium according to claim 53, wherein the authentication procedure further comprises:
using the authentication code extraction function to extract a first set of authentication codes from at least one portion of a first set of transformed-domain image data, the first set of transformed-domain image data including the sixth transformed-domain image datum;
comparing at least one portion of a second set of transformed-domain image data to at least one portion of a third set of transformed-domain image data, for deriving a first set of comparison results;
based on each of the first set of authentication codes, selecting a set of at least one acceptable value of a member of the first set of comparison results associated with the each of the first set of authentication codes;
if the member of the first set of comparison results associated with the each of the first set of authentication codes is within the set of at least one acceptable value of the member of the first set of comparison results associated with the each of the first set of authentication codes, determining that the first set of transformed-domain image data has not been improperly altered.
63. A computer-readable medium according to claim 62, wherein the authentication procedure further comprises:
using the authentication code extraction function to extract a second set of authentication codes from at least one portion of a fourth set of transformed-domain image data;
comparing at least one portion of a fifth set of transformed-domain image data to at least one portion of a sixth set of transformed-domain image data, for deriving a second set of comparison results, the fifth set of transformed-domain image data including the seventh transformed-domain image datum;
based on each of the second set of authentication codes, selecting a set of at least one acceptable value of a member of the second set of comparison results associated with the each of the second set of authentication codes;
if the member of the second set of comparison results associated with the each of the second set of authentication codes is within the set of at least one acceptable value of the member of the second set of comparison results associated with the each of the second set of authentication codes, determining that the fifth set of transformed-domain image data has not been improperly altered.
64. A computer-readable medium according to claim 63, wherein the authentication procedure further comprises:
if the member of the first set of comparison results associated with the each of the first set of authentication codes is within the set of at least one acceptable value of the member of the first set of comparison results associated with the each of the first set of authentication codes, and if the member of the second set of comparison results associated with the each of the second set of authentication codes is within the set of at least one acceptable value of the member of the second set of comparison results associated with the each of the second set of authentication codes, determining that a seventh set of transformed-domain image data has been improperly altered, the seventh set of transformed-domain image data including the fifth transformed-domain image datum.
65. A computer-readable medium according to claim 62, wherein the authentication procedure further comprises:
using the authentication code extraction function to extract a second set of authentication codes from at least one portion of a fourth set of transformed-domain image data, the fourth set of transformed-domain image data including the fifth transformed-domain image datum;
comparing at least one portion of a fifth set of transformed-domain image data to at least one portion of a sixth set of transformed-domain image data, for deriving a second set of comparison results;
based on each of the second set of authentication codes, selecting a set of at least one acceptable value of a member of the second set of comparison results associated with the each of the second set of authentication codes;
if the member of the second set of comparison results associated with the each of the second set of authentication codes is within the set of at least one acceptable value of the member of the second set of comparison results associated with the each of the second set of authentication codes, determining that the fourth set of transformed-domain image data has not been improperly altered.
66. A computer-readable medium according to claim 65, wherein the authentication procedure further comprises:
if the member of the first set of comparison results associated with the each of the first set of authentication codes is within the set of at least one acceptable value of the member of the first set of comparison results associated with the each of the first set of authentication codes, and if the member of the second set of comparison results associated with the each of the second set of authentication codes is within the set of at least one acceptable value of the member of the second set of comparison results associated with the each of the second set of authentication codes, determining that a seventh set of transformed-domain image data has been improperly altered, the seventh set of transformed-domain image data including the seventh transformed-domain image datum.
67. A computer-readable medium having a set of instructions operable to direct a processor to perform the steps of:
encoding by an encoding function a first set of transformed-domain image data, for deriving a set of image data recovery codes comprising a first image data recovery code, the first set of transformed-domain image data being included in a second set of transformed-domain image data, the second set of transformed-domain image data being derived from a first set of spatial domain image data; and
using a replacement code to replace at least a portion of a first transformed-domain image datum, for converting the first transformed-domain image datum into a second transformed-domain image datum, the first transformed-domain image datum being included in a third set of transformed-domain image data, the third set of transformed-domain image data being derived from the first set of spatial domain image data, the replacement code comprising at least one of the first image data recovery code, a code derived from the first image data recovery code, a code selected based upon at least the first image data recovery code, and a code selected based upon at least the code derived from the first image data recovery code, the second transformed-domain image datum being for deriving a third transformed-domain image datum, the first set of spatial domain image data being for deriving a fourth set of transformed-domain image data, the third transformed-domain image datum being for deriving, by a recovery procedure, an approximation data set for replacing the fourth set of transformed-domain image data, and the recovery procedure comprising the steps of:
using a recovery code extraction function to extract a second image data recovery code from the third transformed-domain image datum, the second image data recovery code being approximately equal to the first image data recovery code; and
decoding by a decoding function at least the second image data recovery code, for deriving the approximation data set, the decoding function comprising a functional inverse of the encoding function.
68. A computer-readable medium according to claim 67, wherein the set of instructions is further operable to direct the processor to perform the steps of:
averaging a second set of spatial domain image data, for deriving a first reduced image datum;
averaging a third set of spatial domain image data, for deriving a second reduced image datum, the first and second reduced image data being included in a reduced set of spatial domain image data, and the second and third sets of spatial domain image data being included in the first set of spatial domain image data;
domain-transforming the reduced set of spatial domain image data, for deriving a fifth set of transformed-domain image data; and
quantizing the fifth set of transformed-domain image data, for deriving the first set of transformed-domain image data.
69. A computer-readable medium according to claim 68, wherein the portion of the first transformed-domain image datum comprises a bit of the first transformed-domain image datum, and the first image data recovery code comprises a data recovery bit.
70. A computer-readable medium according to claim 69, wherein the set of instructions is further operable to direct the processor to perform the step of processing the data recovery bit and a bit of a secret key by a binary operation, for deriving an encrypted bit, the replacement code comprising at least one of the encrypted bit, a code derived from the encrypted bit, and a code selected based upon the encrypted bit.
71. A computer-readable medium according to claim 67, wherein the portion of the first transformed-domain image datum comprises a bit of the first transformed-domain image datum, and the first image data recovery code comprises a data recovery bit.
72. A computer-readable medium according to claim 71, wherein the set of instructions is further operable to direct the processor to perform the step of processing the data recovery bit and a bit of a secret key by a binary operation, for deriving an encrypted bit, the replacement code comprising at least one of the encrypted bit, a code derived from the encrypted bit, and a code selected based upon the encrypted bit.
73. A computer-readable medium according to claim 67, wherein the encoding function comprises an entropy encoding function.
74. A computer-readable medium according to claim 73, wherein the entropy encoding function comprises at least one of a Huffman encoding function and a JPEG entropy encoding function.
75. A computer-readable medium having a set of instructions operable to direct a processor to perform the steps of:
quantizing a first set of transformed-domain image data based on a first quantization step size, for deriving a second set of transformed-domain image data, the second set of transformed-domain image data including at least a first transformed-domain image datum; and
using a replacement code to replace at least a portion of the first transformed-domain image datum, for converting the first transformed-domain image datum into a second transformed-domain image datum, the second transformed-domain image datum being included in a third set of transformed-domain image data, the replacement code comprising at least one of a watermark code, a code derived from the watermark code, a code selected based on the watermark code, and a code selected based upon at least the code derived from the watermark code, wherein the third set of transformed-domain image data is for being altered by an alteration procedure for deriving a fourth set of transformed-domain image data, the alteration procedure comprising at least one of: (1) quantizing the third set of transformed-domain image data based on a second quantization step size, the second quantization step size being no greater than the first quantization step size, (2) transforming a data encoding format of the third set of transformed-domain image data into a different data encoding format, and (3) filtering the third set of transformed-domain image data, the fourth set of transformed-domain image data including at least a third transformed-domain image datum, and the third transformed-domain image datum being derived from the second transformed-domain image datum, wherein the third transformed-domain image datum is for being processed by a watermark extraction procedure for extracting the watermark code from the third transformed-domain image datum, the watermark extraction procedure comprising the steps of:
requantizing the third transformed-domain image datum based on the first quantization step size, for generating a fourth transformed-domain image datum, and
processing the fourth transformed-domain image datum by a watermark extraction function, for deriving an extracted code approximately equal to the watermark code.
76. A computer-readable medium according to claim 75, wherein the first set of transformed-domain image data includes a fifth transformed-domain image datum, the first transformed-domain datum is derived from the fifth transformed-domain image datum, and the set of instructions is further operable to direct the processor to perform the the step of deriving the watermark code based on at least one datum derived from at least a first portion of a set of spatial domain image data, the fifth transformed-domain image datum being derived from a second portion of the set of spatial domain image data.
77. A computer-readable medium according to claim 76, wherein the set of instructions is further operable to direct the processor to perform the steps of:
using a secret mapping to form an association between at least the first transformed-domain image datum and at least the datum derived from the first portion of the set of spatial domain image data; and
using the association between the at least the first transformed-domain image datum and the at least the datum derived from the first portion of the set of spatial domain image data for selecting the first transformed-domain image datum to be converted, in the step of using the first replacement code, into the second transformed-domain image datum.
78. A computer-readable medium according to claim 75, wherein the first transformed-domain image datum has a secret transformed-domain location.
Description
BACKGROUND OF THE INVENTION
Digital images are vulnerable to tampering such as cropping and replacement of image portions. Such "crop-and-replace" operations can be used to improperly add objects which were not present in the original image, or to improperly remove objects which were present in the original image. Various authentication methods have been used to detect such alterations. For example, a digital signature can be embedded in the image data as a "watermark." Conventional digital signature watermarking techniques tend to detect any and all alterations of the original data.
However, in many cases, certain types of alterations are considered acceptable. For example, unlike crop-and-replace operations, lossy compression processing such as JPEG compression is likely to be performed for legitimate reasons such as efficiency of storage and/or transmission of the data, rather than malicious purposes such as misleading the viewer as to the presence and/or absence of objects and/or people in the scene captured by the image. Similarly, simply changing the encoding format of the image data--e.g., converting a JPEG-encoded image to a JPEG 2000-encoded image or to a GIF-encoded image--is likely to be done for innocent reasons. Likewise, filtering of an image is considered a legitimate alteration for many purposes. For cases in which lossy compression, transformation of data encoding format, and/or image filtering are considered acceptable types of image processing, conventional digital signature watermarking techniques are unsuitable, because such technologies tend to reject any data which has been altered in any manner.
Other methods have been used in order to attempt to enable acceptance of legitimate alterations. For example, in one technique, a digital signature is generated based upon selected image points which are deemed to have a particular relevance. In other techniques, digital signatures have been generated based upon moments and/or edges within an image.
However, in many cases, moment-based digital signature techniques fail to detect important malicious manipulations such as cropping and replacement. Edge-based methods suffer from excessive signature length, inconsistencies in edge detection results, and excessive sensitivity to color alteration.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide an image-processing system which detects improper image alterations such as cropping and replacement of image positions.
It is an additional object of the present invention to provide an image-processing system which accepts data which has been altered in an acceptable manner, such as data which has been processed by lossy compression, transformation of encoding format, or filtering.
These and other objects are accomplished by the following aspects of the present invention.
In accordance with one aspect of the present invention, an image is processed by comparing a first transformed-domain image datum to a second transformed-domain image datum, in order to derive a first authentication code. A replacement code comprising, or derived from, the first authentication code, is used to replace at least a portion of a third transformed-domain image datum, in order to convert the third transformed-domain image datum into a fourth transformed-domain image datum. The first, second, third, and fourth transformed-domain image data are typically DCT coefficients. The first transformed-domain image datum has a first transformed-domain location; the second transformed-domain image datum has a second transformed-domain location; and the fourth transformed-domain image datum has a third transformed-domain location. The first transformed-domain image datum is for deriving a fifth transformed-domain image datum having a fourth transformed-domain location. The second transformed-domain image datum is for deriving a sixth transformed-domain image datum having a fifth transformed-domain location. The fourth transformed-domain image datum is for deriving a seventh transformed-domain image datum having a sixth transformed-domain location. The first and fourth transformed-domain locations are approximately equal, the second and fifth transformed-domain locations are approximately equal, and the third and sixth transformed-domain locations are approximately equal. The fifth, sixth and seventh transformed-domain image data are for being authenticated by an authentication procedure in which: (1) an authentication code extraction function is used to extract a second authentication code from the seventh transformed-domain image datum; (2) the fifth and sixth transformed-domain image data are compared in order to derive a first comparison result; and (3) based upon the second authentication code, a set of one or more acceptable values of the first comparison result are selected. If the first comparison result is not within the set of acceptable values, the authentication procedure determines that at least one of the fifth, sixth and seventh transformed-domain data has been improperly altered.
In accordance with an additional aspect of the present invention, an image is processed by using an encoding function to encode a first set of transformed-domain image data, in order to derive a set of image data recovery codes. The first set of transformed-domain image data is included in a second set of transformed-domain data which is typically a set of DCT coefficients derived from a set of spatial domain image data. The set of image data recovery codes includes a first image data recovery code. A replacement code is used to replace at least a portion of a first transformed-domain image datum, in order to convert the first transformed-domain image datum into a second transformed-domain image datum. The first transformed-domain image datum is included in a third set of transformed-domain image data derived from the first set of transformed-domain image data. The replacement code comprises, or is derived from, the first image data recovery code. The second transformed-domain image datum is for deriving a third transformed-domain image datum. The first set of spatial domain image data is for deriving a fourth set of transformed-domain image data. The third transformed-domain image datum is for deriving, by a recovery procedure, an approximation data set approximating the first set of transformed-domain image data. The approximation data set can be used to replace the fourth set of transformed-domain image data. In the recovery procedure, a recovery code extraction function is used to extract a second image data recovery code from the third transformed-domain image datum. The second image data recovery code is approximately equal to the first image data recovery code. A decoding function is used to decode the second image data recovery code, in order to derive the approximation data set. The decoding function is a functional inverse of the encoding function.
In accordance with another aspect of the present invention, an image is processed by quantizing a first set of transformed-domain image data based on a first quantization step size, in order to derive a second set of transformed-domain image data. The second set of transformed domain image data includes at least a first transformed-domain image datum. A replacement code is used to replace at least a portion of the first transformed-domain image datum, in order to convert the first transformed-domain image datum into a second transformed-image datum. The second transformed-domain image datum is included in a third set of transformed-domain image data. The replacement code comprises, or is derived from, a watermark code. The third set of transformed-domain data is for being processed by an alteration procedure for deriving a fourth set of transformed-domain image data. The alteration procedure comprises at least one of: (1) a second quantization procedure based on a second quantization step size, the second quantization step size being no greater than the first quantization step size, (2) a data encoding format transformation, and (3) an image filtering procedure. The fourth set of transformed-domain image data includes at least a third transformed-domain image datum which is derived from the second transformed-domain image datum. The third transformed-domain image datum is for being processed by a watermark extraction procedure which extracts the watermark code from the third transformed-domain image datum. The watermark extraction procedure comprises the steps of: (1) requantization the third transformed-domain image datum based on the first quantization step size, for generating a fourth transformed-domain image datum; and (2) processing the fourth transformed-domain image datum by a watermark extraction function, for deriving an extracted code approximately equal to the watermark code.
BRIEF DESCRIPTION OF THE DRAWINGS
Further objects, features, and advantages of the present invention will become apparent from the following detailed description taken in conjunction with the accompanying figures showing illustrative embodiments of the invention, in which:
FIG. 1 is a block diagram illustrating an exemplary image-processing procedure in accordance with the present invention;
FIG. 2 is a block diagram illustrating an additional exemplary image-processing procedure in accordance with the present invention;
FIG. 3 is a block diagram illustrating yet another exemplary image-processing procedure in accordance with the present invention;
FIG. 4 is a block diagram illustrating still another exemplary image-processing procedure in accordance with the present invention;
FIG. 5A is a diagram illustrating an exemplary secret coefficient selection pattern for selecting DCT coefficients in procedure 114 illustrated in FIG. 1;
FIG. 5B is a diagram illustrating an exemplary secret coefficient selection pattern for selecting DCT coefficients in procedure 122 illustrated in FIG. 1;
FIG. 6 is a diagram illustrating an exemplary manner of dividing a set of DCT coefficients into regions in accordance with the present invention;
FIG. 7 is a block diagram illustrating an exemplary procedure for spatial domain reduction of image data for use in the procedure illustrated in FIG. 3;
FIG. 8 is a block diagram illustrating an exemplary embedding procedure for use in the procedure illustrated in FIG. 3;
FIG. 9A is a diagram illustrating an exemplary arrangement of quantization step sizes or quantizing DCT coefficients;
FIG. 9B is a diagram illustrating an additional exemplary arrangement of quantization step sizes for quantizing DCT coefficients;
FIG. 10 is a block diagram illustrating an exemplary procedure for extracting authentication codes and using the authentication codes to authenticate image data in accordance with the present invention;
FIG. 11 is a block diagram illustrating an exemplary procedure for extracting recovery codes and using the recovery codes to recovery image data in accordance with the present invention;
FIG. 12 is a block diagram illustrating an exemplary procedure for deriving an authentication code, embedding the authentication code in image data, and using the authentication code to authenticate data derived from the image data;
FIG. 13 is a block diagram illustrating an exemplary procedure for authenticating watermarked data in accordance with the present invention;
FIG. 14 is a block diagram illustrating an exemplary procedure for embedding feature codes and/or image data recovery codes in image data coefficients in accordance with the present invention;
FIG. 15 is a block diagram illustrating an exemplary procedure for watermarking and authenticating image data in accordance with the present invention; and
FIG. 16 is a block diagram illustrating an exemplary watermark extraction procedure for use in the procedures of FIGS. 10-13 and 15.
DETAILED DESCRIPTION OF THE INVENTION
In accordance with the present invention, authentication data are generated and embedded as watermark codes in an image in order to enable later authentication of the watermarked image and/or images derived from the watermarked image. The authentication data are derived from the image in which they are to be embedded. FIG. 1 illustrates an exemplary procedure for generating such authentication data and embedding the authentication data in an image. The original, spatial domain image data 102 is processed using a domain transformation procedure for converting the spatial domain image data 102 into transformed-domain image data 106. In the illustrated example, a discrete cosine transform (DCT) 104 is used to process the spatial domain data 102, in order to derive DCT data 106. The spatial domain data 102 are typically divided into 8.times.8 blocks. Each 8.times.8 block of spatial domain data is separately processed by the DCT procedure, to generate an 8.times.8 block 402 of DCT coefficients, as illustrated in FIG. 4. For example, spatial domain blocks (e.g., 8.times.8 squares of pixels) 152, 154, 156, and 158 are transformed by the DCT procedure 104 in order to derive transformed-domain data sets P.sub.1, P.sub.2, 160, and 162, respectively. In this example, each of these sets is an 8.times.8 block of DCT coefficients.
FIG. 6 illustrates a typical 8.times.8 block 602 of DCT coefficients 612. This set 602 is divided into four regions (i.e., portions) 604, 606, 608, and 610. The first portion 604 contains the coefficients used to derive authentication codes--also referred to herein as "feature codes"--in accordance with the procedure illustrated in FIG. 1. The second portion 606 contains the coefficients into which authentication/feature codes--typically feature codes generated from other blocks--are to be embedded. The third portion 608 contains the coefficients into which image recovery data is to be embedded, as is discussed in further detail below with respect to the recovery data embedding and recovery procedures. The fourth region 610 contains those coefficients which are simply used as image data, and are not used for deriving or embedding authentication and/or recovery codes. As indicated by the arrangement of the numbers 1-64 in the illustrated block 602, the order/sequence in which the coefficients are arranged and indexed follows the standard, well-known "zig-zag" pattern which is widely used in image processing. With reference to the aforementioned zig-zag order, coefficients 1-6 are used to derive feature codes; feature codes from other blocks are embedded in coefficients 7-9; recovery codes derived from other blocks are embedded in coefficients 10-21; and coefficients 22-64 are not used to derive or embed feature codes or recovery data.
Referring again to FIG. 1, a pair selection procedure 110 is used for selecting pairs of DCT coefficient blocks, based on a secret DCT-domain block pair mapping 108. For example, as illustrated in FIGS. 1 and 4, blocks P.sub.1 and P.sub.2 are associated together to form a combined set: block pair 112. The DCT-domain block pair mapping 108 can be generated using a variety of different methods. For example, the mapping 108 can be generated by assigning a number to each block and then, for each block, picking an associated block based upon a random number or a sequence of random numbers. Such a random number or sequence can be generated by: (1) a random number generator, (2) a quasi-random number generator, (3) a password-based number sequence generator, or (4) any other well-known method for generating random numbers or sequences of numbers. The block pair mapping 108 can also be based upon a code typed in by a user. In fact, as will be readily understood by those skilled in the art, a secret pattern such as the DCT-domain block pair mapping 108 illustrated in FIGS. 1 and 4 can be generated using a wide variety of well-known methods for generating patterns, numbers, and/or sequences of numbers. Preferably, the mapping is stored in a look-up table (LUT).
Once pairs of DCT coefficient blocks are selected, the DCT data 106 is further processed by a coefficient selection procedure 114 in order to select the specific coefficients which will be used to derive authentication data. A secret transformed-domain location selection pattern 128 specifies the transformed-domain locations--in this example, DCT-domain locations--of one or more selected transformed-domain image data--in this example, DCT coefficients--in each block. The transformed-domain location selection pattern 128 can, for example, be a randomly ordered or quasi-randomly ordered list--e.g., {1, 6, 5}--of selected index numbers of the zig-zag order illustrated in FIG. 6. An example of such a selection pattern 128 is illustrated in FIG. 5A. The illustrated, exemplary, secret selection pattern comprises three datum selection locations 518, 520, and 522 which specify the locations of coefficients 506, 502, and 510, respectively. The aforementioned locations are specified with respect to the DCT-domain coordinate system of DCT coefficient block P.sub.1. The same datum selection locations 518, 520, and 522, in the DCT-domain coordinate system of DCT coefficient block P.sub.2, are used to select coefficients 508, 504, and 512, respectively. Each selected coefficient in a selected block is compared to the corresponding selected coefficient in the corresponding selected block (procedure 118 in FIG. 1). For example, as illustrated in FIG. 5A, coefficient 506 is compared to coefficient 508, coefficient 502 is compared to coefficient 504, and coefficient 510 is compared to coefficient 512. The results of the respective comparisons are used as authentication codes. For example, as illustrated in FIG. 1, the comparison of DCT coefficients 506 and 508 generates authentication code 202 and the comparison of DCT coefficients 502 and 504 generates authentication code 204. The transformed-domain locations of coefficients 502, 504, 506, and 508 are preferably secret so that the locations can only be determined if the secret block pair mapping 108 and secret selection pattern 128 are known.
Similarly to the block pair mapping 108 discussed above, the secret coefficient selection pattern 128 can be generated using a variety of different methods. For example, the pattern 128 can be based upon a random number generated by: (1) a random number generator, (2) a quasi-random number generator, (3) a password-based number sequence generator, or (4) any other well-known method for generating random numbers or sequences of numbers. The secret selection pattern 128 can also be based upon a code typed in by a user. In fact, as will be readily understood by those skilled in the art, a secret pattern such as the secret coefficient selection pattern 128 can be generated using a wide variety of well-known methods for generating patterns, numbers, and/or sequences of numbers. Preferably, the pattern 128 is stored in an LUT. Typically, the pattern 128 includes a relatively small subset of the coefficients in a given block--i.e., not all of the coefficients in the block are used for authentication code generation.
Optionally, the comparison procedure 118 can simply compare the respective sizes of two coefficients and generate a single-bit feature code having a value of one or zero, depending upon which coefficient is larger. For example, the comparison procedure 118 can yield an authentication bit having a value of 1 if coefficient 506 is greater than or equal to coefficient 508, and 0 if coefficient 506 is less than coefficient 508. Alternatively, the comparison procedure 118 can yield a bit having a value of 1 if coefficient 508 is greater than or equal to coefficient 506, and 0 if coefficient 508 is less than coefficient 506. Furthermore, although the exemplary comparison procedure discussed above derives single-bit authentication codes, other types of comparison procedures can be used. For example, the comparison procedure 118 can be configured to yield one of three different values,--e.g., 1, 0, or -1--depending upon whether coefficient 506 is, respectively, greater than, less than, or equal to coefficient 508. Such a comparison procedure is typically considered to generate 1.5 bits of information per comparison. An additional example of a 1.5 bit-per-comparison procedure is one which uses a threshold. In such a procedure, the difference of coefficients 506 and 508 is computed, and the comparison procedure 118 generates one of three possible values--e.g., 1, 0, or -1--depending upon whether the difference is, respectively, greater than the threshold, less than the threshold, or equal to the threshold. In fact, the size of the authentication codes need not be limited to limited to 1, 1.5, or even 2 bits. For example, an authentication code can be a multi-bit number representing the difference between the bits 506 and 508 being compared.
Once the feature codes 120 are derived, an embedding procedure 122 is used to embed the codes 120 into DCT-domain data 132 derived from the original spatial-domain data 102. The derivation of the DCT data 138 into which the feature codes 120 are to be embedded can be further understood with reference to FIG. 1. The DCT coefficients 106 derived from the original spatial-domain data 102 are quantized using a selected set of quantization steps. For example, as illustrated in FIG. 1, unquantized coefficients 144 and 146 in blocks 160 and 162, respectively, are quantized to generate quantized coefficients 216 and 220, respectively. Preferably, the quantization steps used in the quantization procedure 130 are based upon the well-known JPEG compression quantization tables. For example, FIGS. 9A and 9B illustrate the standard JPEG quantization tables 902 and 904 corresponding to a JPEG quality factor (QF) of 50. As will be readily understood by those skilled in the art, the quantization tables 902 and 904 illustrated in FIGS. 9A and 9B contain the quantization step sizes 906 and 908 used to quantize an 8.times.8 block of DCT coefficients. The quantization table 902 illustrated in FIG. 9A is used to quantize an 8.times.8 block of DCT coefficients representing the luminances of the pixels in the 8.times.8, spatial-domain block of pixels from which the DCT coefficients were derived. The quantization table 904 illustrated in FIG. 9B is used to quantize an 8.times.8 block of DCT coefficients representing the chrominance of the pixels in the 8.times.8, spatial-domain pixel block from which the DCT coefficients were derived.
The QF of a set of DCT-domain coefficients representing a JPEG-encoded image is a commonly-used indicator of the quality of the encoded image. QF=100 indicates the highest quality, and lower quality factors indicate reduced quality, typically due to compression of the data. JPEG data is typically compressed by increasing the quantization step sizes and re-quantizing the coefficients. For most common applications, the preferred QF typically ranges from 50 to 80, depending on the user's desire for high resolution, traded off against the user's desire to reduce the size of the image data file.
In general, the spatial-domain pixel data from which a set of DCT coefficients is derived can represent the luminance or chrominance of the respective pixels, and/or can represent the brightness of particular color channel--e.g., red, green, or blue--in a pixel. It is to be noted that the terms "image data" and "pixel data" as used herein are not meant to refer only to the absolute brightness or luminance of a pixel or a color channel within a pixel, nor are the aforementioned terms meant to refer only to the absolute chrominance or color value of a pixel. Rather, the terms "image data" and "pixel data" are meant to include both absolute and relative values of brightness, chrominance, and/or other image variables. For example, image data can include a set of difference or error pixels representing the differences and/or errors between respective pixels of two images. The two images used to generate the difference or error pixels can be, for example, an actual image and an estimated image.
It is also to be noted that image data can, but need not, be in the spatial domain--e.g., each datum representing the brightness, color, and/or color channel value of a pixel as seen by the typical viewer of the image. Image data can also include transformed-domain data such as DCT coefficients, discrete Fourier transform coefficients, discrete wavelet transform coefficients, and/or any type of data having been processed by a domain transformation such as a DCT, a discrete Fourier transform, a discrete wavelet transform, etc.
Referring again to FIG. 1, the quantized DCT coefficients 132 are processed using a pair selection procedure 136 to select pairs of coefficient blocks--e.g., pair 148 of blocks P.sub.3 and P.sub.4 --into which the feature codes 120 will be embedded. The pair selection procedure 136 is preferably similar or identical to the pair selection procedure 110 used to select the respective pairs of DCT coefficient blocks used to derive the feature codes 120. Similarly to pair selection procedure 110, pair selection procedure 136 preferably uses a secret DCT-domain block pair mapping 134 which forms an association between blocks P.sub.3 and P.sub.4, and also forms an association between block pair 112 and block pair 148. The secret DCT-domain block pair mapping 134 can be created using the same types of mapping generation techniques discussed above with respect to mapping 108.
Preferably, not every DCT-domain coefficient of a selected pair of DCT-domain coefficient blocks is used for embedding a feature code. Referring now to FIGS. 1 and 6, the input coefficients 216 and 220 into which the feature codes 202 and 204 are to be embedded are selected by a coefficient selection procedure 150. The selection procedure 150 can optionally select the coefficients 216 and 220 simply based on the zig-zag order described above with respect to FIG. 6. For example, coefficients 7, 8, and 9 illustrated in FIG. 6 can be used in their standard zig-zag order: 7, 8, and 9. Alternatively, or in addition, the coefficient selection procedure 150 can use a secret transformed-domain location selection pattern 142 for selecting the coefficients to be used for embedding feature codes. The pattern 142 also specifies the order in which the coefficients are to be used. The transformed-domain location selection pattern 142 can, for example, be a randomly ordered or quasi-randomly ordered list--e.g., {7, 9}--of selected index numbers of the zig-zag order illustrated in FIG. 6. The selection pattern 142 can be generated using the same random methods discussed above with respect to the selection pattern 128 used to select the coefficients from which the feature codes are derived. An exemplary secret transformed-domain location selection pattern 142 is illustrated in FIG. 5B. The illustrated pattern 142 includes datum selection locations 524 and 526 which specify the transformed-domain--e.g., DCT-domain--locations of coefficients 514 and 516, respectively, in the coordinate system of block P.sub.3. Data 514 and 516 are a subset of the set 606--illustrated in FIG. 6--of coefficients designated for embedding feature codes in block P.sub.3.
The transformed-domain locations of coefficients 216 and 220 are preferably secret so that the locations can only be determined if the secret block pair mapping 134 and secret selection pattern 142 are known.
FIG. 2 illustrates an example of an embedding procedure 122 for use in the procedure illustrated in FIG. 1. A set of feature codes 120 derived from DCT-domain image data is received into the embedding procedure 122. The set of feature codes 120 includes, for example, features codes 202 and 204 which are to be embedded into non-spatial-domain data such as DCT coefficients 216 and 220, respectively. Consider, for example, feature code 202 which is to be embedded into DCT coefficient 216 of block P.sub.3. The embedding procedure 122 includes a function 210 which operates upon the feature code 202. The function 210 can, optionally, also operate upon one or more bits 224 and 226 of a secret key 228. The function 210 generates a replacement code 212 which replaces the LSB 214 of the DCT-domain coefficient 216, thus deriving a new coefficient 206 having an LSB which is equal to the result 212 of the function 210. The function 210 can, for example, be a replacement operation which simply replaces the LSB 214 with the feature code 202. Such a replacement function can also be viewed as an identity operation which receives the feature code 202 and outputs a replacement code 212 equal to the feature code 202.
Alternatively, or in addition, the function 210 can be a binary operation such as, for example, an "exclusive OR" (XOR) operation receiving as inputs a feature code 202 and a bit 224 of a secret key 228. If such a function is used, the replacement code 212 equals the output of the XOR operation. The function 210 similarly processes additional feature codes such as feature code 204, and additional bits (e.g., bit 226) of the secret key 228, to derive additional coefficients in which feature codes are embedded. For example, the LSB of coefficient 208 is replacement code 218 which has replaced the LSB 222 of input coefficient 220.
It is to be noted that the above-described procedures of replacement of the LSB of an input coefficient are not the only methods for embedding a feature code in accordance with the present invention. For example, the embedding procedure 122 can take into account the value of the original, unquantized coefficient which was used to derive the quantized input coefficient into which the authentication code is to be embedded. An example of such an embedding procedure 122 is illustrated in FIG. 14. The illustrated procedure 122 can be used for embedding authentication feature codes, and also for embedding other types of watermark codes such as image data recovery codes, as discussed in further detail below. An object of the procedure 122 illustrated in FIG. 14 is to generate a quantized output coefficient which not only contains the embedded watermark code, but is also as close as possible to--i.e., has the smallest possible error with respect to--the original, unquantized coefficient which was used to derive the quantized input coefficient. The watermark code--i.e., the authentication code, recovery code, or recovery code portion--is embedded by changing one or more bits of the quantized input coefficient. If the value of the watermark code to be embedded equals the value(s) of the least significant bit or bits of the quantized coefficient (step 1402), then the coefficient is left unchanged (step 1404). On the other hand, if the value of the watermark code does not equal the value(s) of the least significant bit or bits, then the quantized coefficient is changed in such a way as to minimize the impact of the embedded watermark upon the appearance of the resulting image. For example, if 1-bit watermark codes are used, then each watermark code can have a value of 1 or 0. If the watermark code and the LSB of the quantized coefficient have the same value (step 1402), the coefficient is left unchanged (step 1404). If the watermark code and the aforementioned LSB have different values (step 1402), the procedure 122 compares the unquantized coefficient to the nearest quantization levels above and below the unquantized coefficient (step 1406). If the unquantized coefficient is closer to the quantization level below it (step 1408), then it is apparent that the unquantized coefficient has been rounded down in order to derive the quantized input coefficient (step 1408). Accordingly, the quantized coefficient is increased by one quantization step (step 1412), because the resulting difference between the quantized output coefficient and the original, unquantized coefficient will be relatively less if the quantized coefficient is increased--rather than decreased--by one quantization step. On the other hand, if the unquantized coefficient is closer to the quantization level above it (step 1408), then the quantized coefficient is decreased by one quantization step (step 1410), because it is then apparent that the unquantized coefficient was rounded up to derive the original input quantized coefficient; the difference between the quantized output coefficient and the original unquantized coefficient will be relatively less if the quantized coefficient is decreased--rather than increased--by one quantization step. After the procedure 122 determines whether or not to change the input coefficient, and after the coefficient is accordingly changed or not changed, the new coefficient is produced as an output of the embedding procedure 122 (step 1414). The next feature code is processed (step 1416).
It is to be noted that although the watermark embedding procedure illustrated in FIG. 14 leaves the quantized input coefficient unchanged if the watermark value(s) equals the value(s) of the LSB(s) of the quantized input coefficient, and changes the value of the coefficient if the watermark value(s) and the LSB value(s) are unequal, the watermark embedding procedure can just as easily be configured to embed the watermark in an inverted fashion. For example, in the case of a one-bit watermark, the coefficient can be left unchanged if the value of the watermark bit is unequal to the LSB of the coefficient, and the coefficient can be changed according to steps 1406, 1408, 1410, and 1412 if the values of the watermark bit and the LSB are equal.
Similarly to watermarks embedded by simple substitution of the LSB(s) of the coefficient, watermarks embedded using the procedure illustrated in FIG. 14 can also be extracted by simply determining the value(s) of the LSB(s) of the coefficient, because increasing or decreasing the quantized coefficient by one quantization level switches the value of the LSB. Accordingly, regardless of whether the LSB equalled the value of the watermark code before the embedding procedure was performed, the LSB will equal the value of the watermark code after the embedding procedure is performed.
The procedure 122 illustrated in FIG. 14 can be further understood with reference to the following simple example. Consider an input coefficient having a quantization step size of 1, and a quantized value of 7 which equals 111 in binary code. If a single-bit feature code to be embedded in the coefficient has a value of 1, and the LSB of the coefficient is to be set equal to the value of the feature code, then the output coefficient produced by the embedding procedure 122 will retain the value 7, because the LSB of the coefficient already equals 1. On the other hand, if the feature code has a value of 0, then the input coefficient will be either increased or decreased by one quantization level (i.e., adjusted by 1 or -1 in this example) in order to change the value of the LSB to 0. The choice of whether to increase or decrease the coefficient depends upon the value of the original unquantized coefficient. For example, if the original unquantized value was 6.8, then it is known that this coefficient was rounded up to derive the quantized value of 7. In such a case, the output coefficient will be given a value of 6, rather than 8, because 6 is closer to the original, unquantized value of 6.8. On the other hand, if the value of the original, unquantized coefficient was 7.2, then it is known that the unquantized coefficient was rounded down to derive the quantized value of 7. Accordingly, an output value of 8 will produce less error than an output value of 6, and the quantized coefficient of 7 is therefore increased by one quantization level to generate an output coefficient having a value of 8.
It is to be noted that although the particular exemplary procedure 122 illustrated in FIG. 14 generates an unchanged coefficient if the feature code equals the LSB of the input coefficient, and generates a changed coefficient if the feature code does not equal the LSB, the procedure 122 can just as easily be configured to generate a changed coefficient if the feature code equals the LSB, and an unchanged coefficient if the feature code does not equal the LSB.
Furthermore, although the above descriptions of various embedding procedures have emphasized the embedding of a single feature code in a single coefficient, it is also possible to embed a multi-bit feature code in one or more coefficients. For example, an embedding procedure 122 such as illustrated in FIG. 2 can modify the LSB of a first coefficient based upon the value of the first bit of a 2-bit feature code, and can modify the LSB of a second coefficient based upon the value of the second bit of the 2-bit feature code. In addition, a feature code can be designed to be a pre-defined function of the LSBs of two coefficients. Such a feature code is embedded by modifying the two LSBs as needed, such that the pre-defined function of the two LSBs has a value equal to that of the feature code. For example, the value of the F of the feature code can be defined as a binary function (e.g., XOR) of the LSBs of two coefficients (i.e., F=LSB.sub.1 XOR LSB.sub.2). One of the respective LSBs is modified if necessary, such that the value of the function LSB.sub.1 XOR LSB.sub.2 equals the value F of the feature code.
The embedding procedure 122 processes the other feature code 204 in a similar manner, embedding the feature code 204 into another DCT-domain coefficient 220 having an LSB 222. The LSB 222 and the feature code 204 are processed by the function 210 to generate a new LSB 218. The new LSB 218 is used to replace the old LSB 222 of the input coefficient 220, thereby generating a new DCT-domain coefficient 208.
Referring again to FIG. 1, the embedding procedure 122 generates a set 140 of watermarked data which includes coefficients 124 in which authentication codes (i.e., feature codes) have been embedded. For example, data set 124 includes coefficients 206 and 208--illustrated in FIG. 2--in which authentication codes 202 and 204, respectively, have been embedded. If the data recovery methods of the present invention--discussed in further detail below--are to be used, then the set 140 of watermarked data also includes a set 320 of coefficients in which image recovery data is embedded. The watermarked data 140 can, for example, be sent to a recipient 126, or can be stored or otherwise used.
FIG. 10 illustrates an exemplary procedure for extracting authentication/feature codes and using the extracted codes to authenticate a set of image data. The image data being authenticated is typically a set of DCT coefficients or other transformed-domain image data derived from a set of spatial-domain image data A JPEG-encoded image typically comprises one or more 8.times.8 blocks of DCT coefficients, each block being a set of quantized DCT coefficients derived from a corresponding 8.times.8 block of spatial-domain pixel data. In the procedure illustrated in FIG. 10, DCT-domain image data 1002 contains embedded authentication codes. The authentication codes are extracted and used to determine whether or not one or more 8.times.8 blocks of the DCT domain data 1002 have values consistent with the extracted authentication codes. The authentication procedure illustrated in FIG. 10 includes pair selection procedures 110 and 136, coefficient selection procedures 114 and 150, and a comparison procedure 118, all of which are similar or identical to the corresponding procedures in the authentication code generation and embedding procedure illustrated in FIG. 1. In the simple case in which the data 1002 has not been manipulated at all, a matched pair of coefficients can be compared in order to derive a comparison result which is identical to the authentication code which was derived from the corresponding two coefficients when the image was first watermarked by the procedure illustrated in FIG. 1. The comparison result thus generated should therefore match the authentication code extracted from the datum derived from--and in this case, equal to--the coefficient in which the original authentication code was embedded. However, as will be seen by the ensuing discussion, the procedure illustrated in FIG. 10 does not necessarily require an exact match between the new comparison result and the extracted authentication code.
In the illustrated procedure, the set 1002 of DCT data to be authenticated is processed using the same pair selection procedure 110, coefficient selection procedure 114, and comparison procedure 118 as those used in the authentication code generation and embedding procedure illustrated in FIG. 1. Furthermore, in both the feature code generation/embedding procedure illustrated in FIG. 1 and the authentication procedure illustrated in FIG. 10, the same DCT-domain block pair mapping 108 is used for selection of data blocks containing coefficients to be compared. Similarly, in both the code generation/embedding procedure and the authentication procedure, the same secret coefficient selection pattern 128 is used for coefficient selection 114. The pair selection procedure 110 processes the DCT data 1002, grouping the data 1002 into block pairs such as the illustrated pair 1004 of blocks P.sub.1 ' and P.sub.2 '. The locations of blocks P.sub.1 ' and P.sub.2 ' in the DCT domain are preferably identical to those of blocks P.sub.1 and P.sub.2 illustrated in FIG. 4. The coefficient selection procedure 114 uses the secret coefficient selection pattern 128 to select pairs of coefficients to be compared. For example, coefficients 1008 and 1012 are selected to be compared to each other, and coefficients 1010 and 1014 are also selected to be compared to each other. Each selected pair of coefficients is compared by the comparison procedure 118, thereby generating a set 1018 of comparison results. For example, the comparison of coefficients 1008 and 1012 yields the comparison result 1020, and the comparison of coefficients 1010 and 1014 yields the comparison result 1022.
The illustrated procedure also processes the same DCT-domain data 1002 using a pair selection procedure 136 similar or identical to the pair selection procedure 136 used in the authentication code generation and embedding procedure illustrated in FIG. 1. Furthermore, the same block pair mapping 134 is used in both the authentication procedure and the feature code generation and embedding procedure. In the authentication procedure illustrated in FIG. 10, the mapping 134 indicates, for example, the DCT-domain locations of blocks P.sub.3 ' and P.sub.4 '. Blocks P.sub.3 ' and P.sub.4 ' are derived from the blocks P.sub.3 and P.sub.4 in which the feature codes derived from blocks P.sub.1 and P.sub.2 were embedded in the watermarking procedure illustrated in FIG. 1. Blocks P.sub.3 ' and P.sub.4 ' are included in a block pair 1052. The block pair mapping 134 forms an association between block pair 1052 and the block pair 1004 containing blocks P.sub.1 ' and P.sub.2 ' which are derived from blocks P.sub.1 and P.sub.2, respectively.
Because blocks P.sub.1 ' and P.sub.2 ' were selected based on the same secret mapping 108 as blocks P.sub.1 'and P.sub.2 of data set 106 (illustrated in FIG. 1), it is known that blocks P.sub.1 ' and P.sub.2 ' have the same DCT-domain locations as blocks P.sub.1 'and P.sub.2. Similarly, because blocks P.sub.3 ' and P.sub.4 ' of data set 1036 (illustrated in FIG. 10) were selected based on the same secret mapping 134 as blocks P.sub.3 and P.sub.4 of data set 132 (illustrated in FIG. 1), it is known that blocks P.sub.3 ' and P.sub.4 ' have the same DCT-domain locations as blocks P.sub.3 and P.sub.4. Accordingly, pair selection procedure 136 selects pair 1052 of blocks P.sub.3 ' and P.sub.4 ' as the block pair which is expected to contain the embedded authentication codes corresponding to the block pair 1004 containing blocks P.sub.1 ' and P.sub.2 '. A coefficient selection procedure 150 utilizes coefficient selection pattern 142 to select the coefficients in which authentication codes 1024 are expected to be embedded. The coefficient selection pattern 142 indicates which coefficient in a particular block pair (e.g., P.sub.3 ' and P.sub.4 ') is expected to contain a feature code associated with a particular coefficient pair in blocks P.sub.1 ' and P.sub.2 '. For example, based upon pattern 142, the comparison result 1020 derived from coefficients 1008 and 1012 is expected to correspond to a feature code 1026 embedded in a particular coefficient 1038 in block P.sub.3 '. The coefficient selection procedure 150 therefore selects that coefficient 1038 to be processed by an authentication code extraction procedure 1034. Similarly, the comparison result 1022 is expected to correspond to a feature code 1028 embedded in coefficient 1040 of block P.sub.4 ', and the coefficient selection procedure 150 therefore selects that coefficient 1040 to be processed by the authentication code extraction procedure 1034. The authentication code extraction procedure 1034 is used to extract the authentication codes 1026 and 1028, respectively, from the selected coefficients 1038 and 1040.
The authentication procedure should accept data which has been altered by acceptable processing such as compression, encoding format transformation, and filtering, yet reject data which has been altered by improper procedures such as cropping and replacement. Accordingly, each of the extracted authentication codes 1024 is used (in procedure 1030) to select one or more acceptable values 1042 of the comparison results 1018 generated by the comparison procedure 118. The determination of the range of acceptable values is based upon the invariant properties of data compressed using quantization-based (e |
