Data hiding method and data extraction method using statistical examination

• US 6,249,870 B1
• Filed: 12/24/1997
• Issued: 06/19/2001
• Est. Priority Date: 12/26/1996
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kobayashi, Seiji, Koide, Akio, Shimizu, Shuichi, Morimoto, Norishige
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): KABAKOFF, STEPHEN ERIC
• Application Number:
  US08/999,578
• Time in Patent Office: 1,273 Days
• Field of Search: 380/54, 380/55, 382/232, 713/176
• US Class Current: 713/176
• 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/0083 whereby only watermarked image required at decoder, e.g. source-based, blind, oblivious
• CPC Class Codes: G06T 2201/0202 whereby the quality of watermarked images is measured; Measuring quality or performance of watermarking methods; Balancing between quality and robustness
• CPC Class Codes: H04N 1/32203 Spatial or amplitude domain methods H04N1/32309 takes precedence
• CPC Class Codes: H04N 1/32208 involving changing the magnitude of selected pixels, e.g. overlay of information or super-imposition H04N1/32219, H04N1/32224 take precedence
• CPC Class Codes: H04N 1/32229 with selective or adaptive application of the additional information, e.g. in selected regions of the image H04N1/32213 takes precedence
• CPC Class Codes: H04N 2201/3233 of authentication information, e.g. digital signature, watermark
• CPC Class Codes: H04N 2201/327 which are undetectable to the naked eye, e.g. embedded codes

Abstract

The invention makes it possible to properly certify a genuine owner, and to inhibit deterioration of image quality of media information to which an embedding operation is performed by adaptively determining amount of embedding for characteristic values such as pixel values. It includes a data hiding method for embedding message data into media data comprising the steps of obtaining a secondary key by inputting a key having a predetermined value to a specified function; determining hiding positions in which the message data will be embedded according to the obtained secondary key, and selecting one of plural hiding functions according to the secondary key so that the selected hiding function is used for each of the determined hiding positions; and embedding the message data into each of the determined hiding positions according to the selected hiding function corresponding to the hiding position.

Claims

1. A data hiding method for embedding a message comprising one or more digital data bits into an array of data, said method comprising the steps of:

obtaining a secondary key by inputting a secret first key to a specified public unidirectional function, said second key specifying said array of data and detection basic functions for calculating values based on data near points in said array;

determining a plurality of point array groups from said array of data in which said message is to be embedded according to said secondary key, an amount of point array groups corresponding in number to an amount of digital data bits in said message, and selecting one corresponding detection basic function from a plurality of detection basic functions according to said secondary key so that said detection basic function is applied to each point of said point array groups at a time of detection; and

embedding each bit into its corresponding point array group by manipulating digital data near each point in the point array group to achieve a desired sum of detection basic function values over the point array group.

2. A method as recited in claim 1, wherein said array of data is comprised of pixel data or an image.

3. A method as recited in claim 2, wherein each of the hiding positions is comprised of a pixel point array of pixels, each of the pixels having at least one characteristic value.

4. A method as recited in claim 3, wherein the step of embedding is comprised of adaptively ascertaining a size of each pixel point array and a magnitude for manipulating said characteristic value.

5. A method as recited in claim 4, wherein said step of ascertaining the magnitude employs statistics of a plurality of characteristic values for the pixel point array.

6. A method as recited in claim 1, wherein said message is a fixed constant.

7. A method as recited in claim 1, further comprising the steps of generating the first key in a random fashion.

16. The method as claimed in claim 1, wherein performance of said embedding step according to said detection basic function further includes:

applying said detection basic function at each point in a point array group to determine a point value; and

,

accumulating a sum of point values for each group to obtain a point array sum, said step of manipulating data being performed such that said sum exceeds a predetermined value based on a detection function for determining bit information and its probable reliability.

17. The method as claimed in claim 16, wherein said embedding step further includes the step of specifying a target change range for each point during application of said detection basic function to enable said accumulated sum to exceed said predetermined value.

18. The method as claimed in claim 17, wherein said step of specifying a target change range includes the step of calculating an index of unperceptivity for each point in said point array group, said index being of a value calculated from the values of points near a given point in said array.

8. A data extraction method for extracting a message comprising one or more digital data bits from an array of data in which the message is embedded, said method comprising the steps of:

specifying said array of data and detection basic functions for calculating values based on data near points in said array according to a secondary key;

determining a plurality of point array groups from said array of data in which said message is embedded according to said secondary key, an amount of point array groups corresponding in number to an amount of digital data bits in said message, and selecting one corresponding detection basic function at each point of point array groups from a plurality of detection basic functions according to said secondary key;

inputting neighboring array data of each point in said point array group to the selected detection basic function for that point, calculating a function value for each point in said point array group and accumulating a sum of values calculated for each point array group;

inputting said accumulated sum of output values for each group to a detection function; and

determining with probable reliability whether a digital data bit is embedded in each of said point array groups according to an output of said detection function.

9. A method as in claim 8, further comprising a step of ascertaining whether or not information is embedded in a subset of the array of data.

10. A method as in claim 9, wherein said step of ascertaining includes determining whether or not an arithmetic operation was conducted on the subset.

11. A method as in claim 8, wherein said array of data is comprised of an array of pixels of an image.

12. A method as in claim 8, wherein said message is comprised of multi-bit information.

13. A method as in claim 12, wherein said multi-bit information is not perceived by a normal eye.

14. A data hiding method for embedding a message comprising one or more digital data bits into an array of data comprising the steps of:

obtaining a secondary key by inputting a secret first key to a specified public unidirectional function;

determining a plurality of point array groups in which said message will be embedded according to said obtained secondary key, an amount of point array groups corresponding the number to an amount of digital data bits in said message, and selecting one of plural detection basic functions for a corresponding hiding position in point array groups according to said secondary key so that said selected detected basic function is used for each of said determined hiding positions at a time of detection; and

embedding each bit of the message into its corresponding point array group by manipulating neighborhoods of said hiding positions according to said selected detection basic function, wherein each neighborhood comprises a group of pixels for computing a function value, said embedding step including adaptively determining a function value to be modified in said group of pixels according to values of surrounding pixels for each pixel in said group in order to achieve a desired unperceptivity and statistical characteristic.

15. A data extraction method for extracting message comprising one or more digital data bits from data in which the message is embedded comprising the steps of:

determining a plurality of point array groups in which said message is embedded according to a key, an amount of point array groups corresponding in number to an amount of digital data bits in said message, and selecting one of plural detection basic functions according to said key so that said selected detection basic function is used for a determined hiding positions in each said point array group;

inputting neighoring array data of each point in said point array group to said detection basic function and generating an output of said detection basic function;

calculating a function value for each point in said point array group and accumulating a sum of values calculated for each group;

inputting said accumulated sum to a detection function; and

determining with probable reliability whether a digital data bit is embedded according to an output of said detection function.