Method and computer program for embedding and extracting an embedded message from a digital image

• US 6,678,390 B1
• Filed: 12/02/1999
• Issued: 01/13/2004
• Est. Priority Date: 12/02/1999
• Status: Expired due to Fees

• Current Assignee: Apple Inc.
• Original Assignee: Eastman Kodak Company
• Inventors: Honsinger, Chris W.
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): CARTER, AARON W
• Application Number:
  US09/453,160
• Time in Patent Office: 1,503 Days
• Field of Search: 382/100, 382/232, 382/278, 382/209, 380/51, 380/54, 713/176
• US Class Current: 382/100
• CPC Class Codes: G06T 1/005 Robust watermarking, e.g. average attack or collusion attack resistant
• CPC Class Codes: G06T 2201/0061 Embedding of the watermark in each block of the image, e.g. segmented watermarking
• CPC Class Codes: G06T 2201/0065 Extraction of an embedded watermark; Reliable detection
• CPC Class Codes: H04N 1/32208 involving changing the magnitude of selected pixels, e.g. overlay of information or super-imposition H04N1/32219, H04N1/32224 take precedence
• CPC Class Codes: H04N 1/32245 Random or pseudorandom selection of pixels
• CPC Class Codes: H04N 2201/327 which are undetectable to the naked eye, e.g. embedded codes

Abstract

A method and computer program for extracting an embedded message from a digital image, the embedded message being formed by convolution with a carrier, employs a message template indicating the relative locations of data in the embedded message, the relative locations of the data being such that the autocorrelation of the message template is strongly peaked. An arbitrary region of the digital image is correlated with the carrier to extract a cyclically shifted message from the digital image. The absolute value of the cyclically shifted message is taken to form a positive valued cyclically shifted message. The positive valued cyclically shifted message is correlated with the message template to form a shifted offset image having a peak amplitude representing the location of the message boundary. The location of the message boundary is employed to extract the hidden message.

Claims

1. A method for extracting an embedded binary message from a digital image, the embedded message being formed by convolution with a carrier, comprising the steps of:

a) providing a message template indicating the relative locations of data in the embedded message, the relative locations of the data being such that the autocorrelation of the message template is strongly peaked at zero offset with substantially smaller sidelobes occurring at nonzero offset locations and further such that no bit location is closer to another bit location by less then three pixels and further arranged substantially along concentric circles or along a spiral pattern;

b) correlating an arbitrary region of the digital image with the carrier to extract a cyclically shifted binary message from the digital image;

c) taking the absolute value of the cyclically shifted message to form a positive valued cyclically shifted binary message;

d) correlating the positive valued cyclically shifted binary message with the message template to form a shifted offset image having a peak amplitude representing the location of the message boundary; and

e) employing the location of the message boundary to extract the hidden message.

2. The method claimed in claim 1, wherein the step of correlating an arbitrary region with the carrier, comprises the steps of:

summing a plurality of congruent arbitrary regions and correlating the carrier with the resulting sum.

3. The method claimed in claim 1, wherein the arbitrary region has the same size as the message template.

4. The method claimed in claim 1, wherein the arbitrary region has a size that is smaller than the message template.

5. The method claimed in claim 1, further comprising the step of correcting the rotation and scale of the digital image prior to the correlation of the arbitrary region with the carrier.

6. A message template indicating the relative locations of data in a message that is to be embedded in an image, the relative locations of the data being such that the autocorrelation of the message template is strongly peaked at zero offset with substantially smaller sidelobes occurring at non-zero offset locations and further such that no bit location is closer to another bit location by less then three pixels and further arranged substantially along concentric circles or along a spiral pattern.

7. A method of embedding a message in an image, comprising the steps of:

a) providing a message template indicating the relative locations of data in the embedded message, the relative locations of the data being such that the autocorrelation of the message template is strongly peaked at zero offset with substantially smaller sidelobes occurring at non-zero offset locations and further such that no bit location is closer to another bit location by less then three pixels and further arranged substantially along concentric circles or along a spiral pattern;

b) placing message data bits at the data bit locations defined by the template;

c) convolving the message data in the template with a carrier to form a dispersed message; and

d) combining the dispersed message with the image.

8. An image having an embedded message produced by the method of claim 7.

9. A computer program embodied on a computer readable medium for extracting an embedded message from a digital image, the embedded message being formed by convolution with a carrier, comprising the steps of:

a) accessing a message template indicating the relative locations of data in the embedded message, the relative locations of the data being such that the autocorrelation of the message template is strongly peaked at zero offset with substantially smaller sidelobes occurring at non-zero offset locations and further such that no bit location is closer to another bit location by less then three pixels and further arranged substantially along concentric circles or along a spiral pattern;

b) correlating an arbitrary region of the digital image with the carrier to extract a cyclically shifted binary message from the digital image;

c) taking the absolute value of the cyclically shifted message to form a positive valued cyclically shifted binary message;

d) correlating the positive valued cyclically shifted binary message with the message template to form a shifted offset image having a peak amplitude representing the location of the message boundary; and

e) employing the location of the message boundary to extract the hidden message.

10. The method claimed in claim 9, wherein the arbitrary region has the same size as the message template.

11. The method claimed in claim 9, wherein the arbitrary region has a size that is smaller than the message template.

12. The method claimed in claim 9, further comprising the step of correcting the rotation and scale of the digital image prior to the correlation of the arbitrary region with the carrier.