Lossless recovery of an original image containing embedded data

• US 6,278,791 B1
• Filed: 05/07/1998
• Issued: 08/21/2001
• Est. Priority Date: 05/07/1998
• Status: Expired due to Term

• Current Assignee: Eastman Kodak Company
• Original Assignee: Eastman Kodak Company
• Inventors: Rabbani, Majid, Honsinger, Chris W., Jones, Paul W., Stoffel, James C.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): CHOOBIN, BARRY
• Application Number:
  US09/074,282
• Time in Patent Office: 1,202 Days
• Field of Search: 380/23, 382/248, 382/232, 382/100, 430/140, 707/104, 707/101, 705/54, 128/922
• US Class Current: 382/100
• CPC Class Codes: G06F 21/16 Program or content traceability, e.g. by watermarking
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06T 1/0028 Adaptive watermarking, e.g. Human Visual System [HVS]-based watermarking
• CPC Class Codes: G06T 1/005 Robust watermarking, e.g. average attack or collusion attack resistant
• CPC Class Codes: G06T 2201/0065 Extraction of an embedded watermark; Reliable detection
• CPC Class Codes: G06T 2201/0203 whereby the image with embedded watermark is reverted to the original condition before embedding, e.g. lossless, distortion-free or invertible watermarking
• CPC Class Codes: Y10S 128/922 including image analysis

Abstract

The method and system embeds digital meta-data into an original image in such a way that the meta-data can be completely removed at a later time to allow loss less recovery of the original image. The loss less recovery of the original image allows for a digital signature of the image to be embedded in the image itself and later recovered and used to verify the authenticity of a received image.

Claims

1. A method for embedding metadata in and recovering meta-data from an n-bit original digital image, comprising the steps of:

a) forming a digital message from meta-data;

b) converting the digital message to embedded data;

c) adding the embedded data to the original image, pixel by pixel, using Modulo-N arithmetic, where N=2ⁿ, to form an n-bit modified digital image containing the embedded data such that the original digital image can always be exactly recovered given the modified image and the embedded data;

d) extracting the embedded data from the modified digital image; and

e) recovering exactly the original image by subtracting the embedded data from the modified image, pixel by pixel, using Modulo-N arithmetic, where N=2ⁿ.

2. The method according to claim 1, wherein the meta-data is a digital signature for the original n-bit digital image formed by the steps of:

i) generating a hash value from the original n-bit digital image; and

ii) encrypting the hash value using a private key to form the digital signature.

3. The method according to claim 1, further comprising the steps of:

i) separating the original n-bit digital image into sub-regions; and

ii) applying the steps of claim 1 to each sub-region.

4. The method according to claim 2, further comprising the steps of:

i) separating the original n-bit digital image into sub-regions; and

ii) applying the steps of claim 2 to each sub-region.

5. A method for embedding meta-data into an original n-bit digital image that allows exact recovery of the original image, comprising the steps of:

a) forming a digital message from meta-data;

b) converting the digital message to embedded data; and

c) adding the embedded data to the original image, pixel by pixel, using modulo-N addition to form an n-bit digital image containing the embedded data.

6. The method according to claim 5, wherein the meta-data is a digital signature for the original n-bit digital image formed by the steps of:

i) generating a hash value from the original n-bit digital image; and

ii) encrypting the hash value using a private key to form the digital signature.

7. A method for embedding meta-data into an original n-bit digital image that allows exact recovery of the original image, comprising the steps of:

a) forming a digital message from meta-data;

b) converting the digital message to embedded data;

c) modifying the amplitude of the embedded data to form scaled embedded data; and

d) adding the scaled embedded data to the original image, pixel by pixel, using modulo-N addition to form an n-bit digital image containing the embedded data.

8. The method according to claim 7, wherein the meta-data is a digital signature for the original n-bit digital image formed by the steps of:

i) generating a hash value from the original n-bit digital image; and

ii) encrypting the hash value using a private key to form the digital signature.

9. A method for embedding meta-data into an original n-bit digital image that allows recovery of the original image, comprising the steps of:

a) forming a digital message from meta-data;

b) generating a random phase carrier based on a private or public key;

c) convolving the digital message and the random phase carrier to form embedded data;

d) scaling the embedded data with an amplitude scaling factor to form scaled embedded data; and

e) adding the scaled embedded data to the original image, pixel by pixel, using modulo-N addition where N=2ⁿ to form an n-bit digital image containing the scaled embedded data.

10. The method according to claim 9, wherein the meta-data is a digital signature for the original n-bit digital image formed by the steps of:

i) generating a hash value from the original n-bit digital image; and

ii) encrypting the hash value using a private key to form the digital signature.

11. The method according to claim 9, wherein the amplitude scaling factor is included in the meta-data that is embedded in the original n-bit digital image.

12. The method according to claim 11, wherein the amplitude scaling factor is dynamically adjusted, comprising the additional steps of:

g) setting the amplitude scaling factor to an initial minimum value;

h) embedding the meta-data into the original image to form an n-bit image containing scaled embedded data;

i) cross-correlating the random phase carrier with the n-bit image containing scaled embedded data to form a recovered digital message;

j) extracting test meta-data from the recovered digital message;

k) comparing the test meta-data with the meta-data to determine equivalence;

l) increasing the amplitude scaling factor if equivalency is not met; and

m) repeating steps h) through l) until equivalency is met.

24. The method claimed in claim 9, wherein the step of scaling the embedded data with an amplitude scale factor further includes multiplying the embedded data by a scale factor α

, where α

is chosen such as to make the embedded data visually undetectable when combined with the original image.

25. The method claimed in claim 24, further comprising the step of including the scale factor in the original image.

13. A method for recovering an original n-bit digital image and associated meta-data from a received n-bit digital image containing embedded data representing a digital message, comprising the steps of:

a) recovering the digital message from the received n-bit digital image;

b) extracting the meta-data from the recovered digital message;

c) converting the recovered digital message to embedded data; and

d) adding the embedded data to the received n-bit digital image, pixel by pixel, using Modulo N-arithmetic, where N=2ⁿ, to form a recovered original n-bit digital image.

14. The method according to claim 13, wherein the meta-data is a digital signature for the original n-bit image, comprising the additional steps of:

e) decrypting the signature from the meta-data using a public key to recover the original hash value;

f) generating a test hash value from the recovered original image; and

g) comparing the test hash value with original hash value to authenticate the recovered original image.

15. The method according to claim 13, further comprising the steps of:

i) separating the received n-bit digital image into sub-regions; and

ii) applying the steps of claim 13 to each sub-region.

16. The method according to claim 14, further comprising the steps of:

i) separating the received n-bit digital image into sub-regions; and

ii) applying the steps of claim 14 to each sub-region.

17. A method for recovering an original n-bit digital image and associated meta-data from a received n-bit digital image containing embedded data representing a digital message, comprising the steps of:

a) recovering the digital message from the received n-bit digital image;

b) extracting the meta-data from the recovered digital message;

c) converting the recovered digital message to embedded data; and

d) subtracting the embedded data from the received n-bit digital image using modulo-N subtraction, where N=2ⁿ, to form a recovered original n-bit digital image.

18. The method according to claim 17, wherein the meta-data is a digital signature for the original n-bit image, comprising the additional steps of:

e) decrypting the signature from the meta-data using a public key to recover the original hash value;

f) generating a test hash value from the recovered original image; and

g) comparing the test hash value with original hash value to authenticate the recovered original image.

19. A method for recovering an original n-bit digital image and associated meta-data from a received n-bit digital image containing scaled embedded data representing a digital message, comprising the steps of:

a) recovering the digital message from the received n-bit digital image;

b) extracting the meta-data from the recovered digital message;

c) converting the recovered digital message to embedded data;

d) modifying the amplitude of the embedded data to form scaled embedded data; and

e) subtracting the scaled embedded data from the received n-bit digital image, pixel by pixel, using modulo-N subtraction, where N=2ⁿ, to form a recovered original n-bit digital image.

20. The method according to claim 19, wherein the meta-data is a digital signature for the original n-bit image, comprising the additional steps of:

f) decrypting the signature from the meta-data using a public key to recover the original hash value;

g) generating a test hash value from the recovered original image; and

h) comparing the test hash value with original hash value to authenticate the recovered original image.

21. A method for recovering an original n-bit digital image and associated meta-data from a received n-bit digital image containing scaled embedded data, comprising the steps of:

a) generating a random phase carrier based on a private or public key;

b) cross-correlating the random phase carrier with the received n-bit digital image to form a recovered digital message;

c) extracting the meta data from the recovered digital message;

d) convolving the recovered digital message and the generated random phase carrier to form embedded data;

e) scaling the embedded data with an amplitude scaling factor to form scaled embedded data; and

f) subtracting the scaled embedded data from the received n-bit digital image, pixel by pixel, using modulo-N subtraction, where N=2ⁿ, to form a recovered original n-bit digital image.

22. The method according to claim 21, wherein the meta-data is a digital signature for the original n-bit image, comprising the additional steps of:

g) decrypting the signature from the meta-data using a public key to recover the original hash value;

h) generating a test hash value from the recovered original image; and

i) comparing the test hash value with original hash value to authenticate the recovered original image.

23. The method according to claim 21, wherein the amplitude scaling factor included in the meta-data is extracted from the recovered digital message by the step of, recovering the amplitude scaling factor from the extracted meta-data.

26. A method for embedding and recovering meta-data into an original n-bit digital image, comprising the steps of:

a) forming a digital message from meta-data;

b) converting the digital message to embedded data by convolving the digital message with a carrier;

c) adding the embedded data with the original image, pixel by pixel, using Modulo N-arithmetic, where N=2ⁿ, to create an n-bit digital image containing the embedded data;

d) recovering the digital message by correlating the original image containing the embedded data with the carrier;

e) recreating the embedded data by convolving the recovered digital message with the carrier; and

f) subtracting the recreated embedded data from the original image, pixel by pixel, having the embedded data within, and using the Modulo N-arithmetic to exactly recover the original image.