System and method for hiding and extracting message data in multimedia data

• US 6,055,321 A
• Filed: 06/03/1997
• Issued: 04/25/2000
• Est. Priority Date: 06/20/1996
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Numao, Masayuki, Shimizu, Shuichi, Kobayashi, Mei, Morimoto, Norishige
• Primary Examiner(s): Johns, Andrew W.
• Application Number:
  US08/867,996
• Time in Patent Office: 1,057 Days
• Field of Search: 382/100, 382/232, 380/3, 380/5, 380/23, 380/49, 380/54
• US Class Current: 382/100
• CPC Class Codes: G06T 1/0021 Image watermarking
• CPC Class Codes: G06T 2201/0051 Embedding of the watermark in the spatial domain
• CPC Class Codes: G06T 2201/0061 Embedding of the watermark in each block of the image, e.g. segmented watermarking
• CPC Class Codes: G09C 5/00 Ciphering apparatus or methods not provided for in the preceding groups, e.g. involving the concealment or deformation of graphic data such as designs, written or printed messages
• 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/32251 in multilevel data, e.g. greyscale or continuous tone data
• CPC Class Codes: H04N 1/32309 in colour image data
• CPC Class Codes: H04N 21/23892 involving embedding information at multiplex stream level, e.g. embedding a watermark at packet level
• CPC Class Codes: H04N 21/8358 involving watermark protecting executable software by watermarking G06F21/16; image watermarking in general G06T1/0021; watermarks inserted in still images for transmission purposes H04N1/32144; inserting watermarks during video coding H04N19/467
• 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 present invention provides a data hiding method of hiding media data in message data and a data extraction method of extracting the hidden data wherein message data is dispersively hidden in media data such as an image or sound to prevent a third person from modifying the message data easily.

More specifically, the present invention relates to a data hiding method in which media data is expressed as a media array while message data is expressed as a message array so that the array elements of the message array can be dispersively hidden in the message array based on a state values specifying a particular array element of the media array, comprising the steps of:

(a) determining the j-th (j≧0) state value S_j ;

(b) determining (j+1)-th state value S_j+1 based on the j-th state value, the array element of the media array indicated by the j-th state value, and the array element of the message array; and

(c) hiding data with respect to the array element of the media array indicated by the (j+1)-th state value S_j+1.

Claims

1. A data hiding method in which media data is expressed as a media array while message data is expressed as a message array and in which the elements of said message array are dispersively hidden in said media array based on a state value specifying a particular array element of said media array, comprising the steps of:

(a) determining the j-th (j≧

0) state value;

(b) determining (j+1)-th state value based on said j-th state value, the array element of said media array indicated by the j-th state value, and the array elements of said message array; and

(c) hiding data with respect to the array element of said media array indicated by said (j+1)-th state value.

3. A data hiding method according to claim 1 or 2 wherein if j=0 in said step (a), the initial state value is determined on the basis of the data in the array elements of said message array.

4. A data hiding method according to claim 1 or 2 wherein if j=0 in said step (a), the exclusive OR of the data in all the array elements of said message array is used as an input to an initial function, the output of said initial function being used as an initial state value.

5. A data hiding method according to claim 1 or 2 wherein in said step (b), said (j+1)-th state value is determined on the basis of the exclusive OR of said j-th state value, the data in the array element of the media array indicated by the j-th state value, and the data in the array elements of said message array.

6. A data hiding method according to claim 1 or 2 wherein in step (b), the exclusive OR of said j-th state value, the data in the array element of said media array indicated by the j-th state value, and the data in the array elements of said message array is used as an input to a hiding position translation function, the output of said hiding position translation function being used as said (J+1)-th state value.

7. A data hiding method according to claim 6 wherein said hiding position translation function is an enciphering function that uses as a parameter, a secret key used in a public key method.

8. A data hiding method according to claim 1 or 2 wherein, in said step (c), said hiding data is the exclusive OR of the array element of said media array indicated by said j-th state value and the array elements of said message array.

9. A data hiding method according to claim 1 or 2 wherein, in said step (c), a first pixel block which corresponds to the array element of said media array indicated by said (j+1)-th state value and a second block are paired and wherein the characteristic values of the pixel blocks are manipulated based on a translation rule so as to hide the hiding data.

10. A data hiding method according to claim 9 wherein said second block is adjacent to said first block constituting a pair with the second block.

11. A data hiding method according to claim 9 wherein said translation rule specifies a rule used to manipulate said characteristic values based on the difference in the characteristic value between the respective pixel blocks constituting a pair.

12. A data hiding method according to claim 11 wherein said characteristic value is the brightness value of said pixel block.

13. A data hiding method according to claim 11 wherein said characteristic value is the variance value of said pixel block.

2. A data hiding method in which media data is expressed as a media array while message data is expressed as a message array and in which the J elements of said message array are dispersively hidden in said media array based on a state value specifying a particular array element of said media array, comprising the steps of:

(a) determining the j-th (j≧

0) state value;

(b) determining (j+1)-th state value based on said j-th state value, the array element of said media array indicated by the j-th state value, and the array elements of said message array;

(c) hiding data with respect to the array element of said media array indicated by said (j+1)-th state value; and

(d) recursively executing steps (a) to (c) to hide the J elements of said message array.

14. A data hiding method according to claim 2 further including the step of (d) extracting said media array in which said hiding data is hidden;

and the last state value.

15. A data extraction method in which message data is expressed as a message array, in which hiding data including said message data is expressed as a hiding array while media data with said hiding data dispersively hidden therein is expressed as a media array, and in which said message array is extracted from said media array based on a state value specifying a particular array element of said media array, comprising the steps of:

(a) determining the j-th (j≧

0) state value;

(b) extracting an array element of said hiding array from the array element of said media array indicated by said j-th state value;

(c) determining the (j-1)-th state value based on the j-th state value and said extracted array element of the hiding array; and

(d) extracting an array element of said message array based on the array element of said media array indicated by said (j-1)-th state value and the extracted array element of said hiding array.

17. A data extraction method according to claim 15 or 16 wherein in said step (a), the first state value used in starting extraction is provided to an extractor as information required for extraction.

18. A data extraction method according to claim 17 wherein the first state value used to start extraction is the last state value generated in hiding said message array.

19. A data extraction method according to claim 15 or 16 wherein in step (c), said (j-1)-th state value is determined on the basis of the exclusive OR of said j-th state value and the data in the array element of said hiding array extracted from the array element of said media array indicated by the j-th state value.

20. A data extraction method according to claim 15 or 16 wherein an extraction position translation function is provided, and wherein in said step (c), the exclusive OR of said j-th state value and the data in the array element of said hiding array extracted from the array element of said media element indicated by said j-th state value, the output of said position translation function being used as said (j-1)-th state value.

21. A data extraction method according to claim 20 wherein said extraction position translation function is an deciphering function that uses as a parameter, a public key used in the public key method.

22. A data extraction method according to claim 15 or 16 wherein, in said step (b), the array element of said hiding array is the exclusive OR of the array element of said media array indicated by said (j-1)-th state value and the array elements of said message array.

23. A data extraction method according to claim 15 or 16 wherein, in said step (b), a first pixel block which corresponds to the array element of said media array indicated by said j-th state value and a second block are paired and wherein the hidden data is extracted according to the relationship between the characteristic values of said first and second pixel blocks constituting a pair on the basis of an extraction rule.

24. A data extraction method according to claim 23 wherein said second block is adjacent to said first block constituting a pair with the second block.

25. A data extraction method according to claim 23 wherein said extraction rule is based on the difference in the characteristic value between said pixel blocks constituting a pair and corresponds to a translation rule that specifies the manipulation of said characteristic values during hiding.

26. A data extracting method according to claim 25 wherein said characteristic value is the brightness value of said pixel block.

27. A data extraction method according to claim 25 wherein said characteristic value is the variance value of said pixel block.

16. A data extraction method in which message data is expressed as a message array, in which hiding data including said message data is expressed as a hiding array while media data with said hiding data dispersively hidden therein is expressed as a media array, and in which said message array is extracted from said media array based on a state value specifying a particular array element of said media array, comprising the steps of:

(a) determining the j-th (j≧

1) state value;

(b) extracting an array element of said hiding array from the array element of said media array indicated by said j-th state value;

(c) determining the (j-1)-th state value based on the j-th state value and said extracted array element of the hiding array;

(d) extracting an array element of said message array based on the array element of said media array indicated by said (j-1)-th state value and the extracted array element of said hiding array; and

(e) recursively executing steps (a) to (c) until an extraction end condition is met.

28. A data extraction method according to claim 16 wherein an initial function used in hiding data in order to determine the initial state value based on the data in the array elements of said message array, and wherein the method further includes the steps of:

(f) in said step (d), each time an element of said message element is extracted, using the data in all the array elements of said message array as an input to determine an extraction end condition that the output of said initial function is equal to said (j-1)-th state value.

29. A data extraction method according to claim 28 wherein the exclusive OR of the data in all the extracted array elements of said message array is used as an input to said initial function.

30. A data extraction method according to claim 28 wherein in step (f), the end of extraction is recognized when the output of said initial function is equal to said (j-1)-th state value.

31. A system for transmitting data to a network, comprising:

a storage apparatus in which media data is stored;

a coding apparatus for hiding message data in said media data; and

a server for controlling an encoder so as to hide said message data in said media data read from said storage means and transmitting the output data from said encoder to the network, wherein;

said message data is dispersively hidden in said media data based on the contents of said message data.

32. A system for transmitting data to a network according to claim 31, wherein said apparatus for hiding message data implements a data hiding method in which media data is expressed as a media array while message data is expressed as a message array and in which the elements of said message array are dispersively hidden in said media array based on a state value specifying a particular array element of said media array, said method comprising the steps of:

(a) determining the j-th (j>

0) state value;

(b) determining (j+1)-th state value based on said j-th state value, the array element of said media array indicated by the j-th state value, and the array elements of said message array; and

(c) hiding data with respect to the array element of said media array indicated by said (j+1) -th state value.

33. A system for receiving data from a network, comprising:

a receiver for receiving media data with message data hidden therein from the network; and

a decoder for extracting said message data from said media data;

wherein;

based on the contents of said message data, the positions of said dispersively message data in said media data are identified and the message data is then extracted.

34. A system for receiving data from a network according to claim 33, wherein said extraction method is a data extraction method in which message data is expressed as a message array, in which hiding data including said message data is expressed as a hiding array while media data with said hiding data dispersively hidden therein is expressed as a media array, and in which said message array is extracted from said media array based on a state value specifying a particular array element of said media array, said method comprising the steps of:

(a) determining the j-th (j>

0) state value;

(b) determining (j+1)-th state value based on said j-th state value. the array element of said media array indicated by the j-th state value, and the array elements of said message array; and

(c) hiding data with respect to the array element of said media array indicated by said (j+1)-th state value.

35. A data hiding method in which first data is expressed as a first array while a second data is expressed as a second array and in which the elements of said second array are dispersively hidden in said first array based on a state value specifying a particular array element of said first array, comprising the steps of:

(a) determining the j-th (j≧

2) state value;

(b) determining (j+1)-th state value based on said j-th state value, the array element of said first array indicated by the j-th state value, and the array elements of said second array; and

(c) hiding data with respect to the array element of said first array indicated by said (j+1)-th state value.

36. A data extraction method in which second data is expressed as a second array while third data including said second data is expressed as a third array and in which first data with said third data dispersively hidden therein is expressed as a first array, said second array being extracted from said first array based on a state value specifying a particular array element of said first array, comprising the steps of:

(a) determining the j-th (j≧

1) state value;

(b) extracting an array element of said third array from the array element of said first array indicated by said j-th state value;

(c) determining the (j-1)-th state value based on the j-th state value and the extracted array element of said third array; and

(d) extracting an array element of said second array based on the array element of said first array indicated by said (j-1)-th state value and the extracted array element of said third array.

37. A data hiding method for hiding data in media data wherein:

information on the reference position for the said message data and said media data is hidden in said message data, and wherein

the information on said reference position is hidden in said message data and enables said reference position of the original message data or a relative position based on said reference position to be detected even if part of said message data is cut off as partial message data.

38. A data hiding method for hiding data in media data according to claim 37 wherein the information on said reference position is concentric circular arcs drawn around said reference position.

39. A data hiding method for hiding data in media data comprising the steps of:

(a) identifying a first block in the media data in which the message data is to be hidden;

(b) determining the characteristic value of said identified first block;

(c) manipulating the characteristic value of said first block so as to hide the message data by referencing a translation rule that associates the contents of the data to be hidden with the difference between a reference value for the characteristic value and the characteristic value of said first block, wherein the hiding data are elements of a message array and media data are elements of a media array, a media data for hiding message data being identified by an associated state value determined according to a prior state value associated with a prior media data element of said media array, and array elements of said message array.

40. A data hiding method for hiding data in media data according to claim 39 wherein said reference value is provided by the characteristic value of a second block present in the media data.

43. A data hiding method according to claim 40, 41, or 42 wherein said second block is adjacent to said first block constituting a pair with the second block.

44. A data hiding method according to claim 40, 41, or 42 wherein said translation rule states that one of the bits is hidden if the characteristic value of said first block is larger than that of the second block, while the other bit is hidden if the characteristic value of said first block is smaller than that of the second block.

45. A data hiding method according to claim 40, 41, or 42 further including the step of prohibiting the execution of said step (c) if the difference in the characteristic value between said first block and said second block is larger than a first threshold, thereby preventing the media data from being degraded.

46. A data hiding method according to claim 40, 41, or 42 further including the step of prohibiting the execution of said step (c) if the difference in the characteristic value between said first block and said second block is smaller than a second threshold, thereby preventing the degradation of the accuracy in extracting the message data.

47. A data hiding method according to claim 40, 41, or 42 wherein said first and second blocks are pixel blocks, and wherein said characteristic value is the brightness value of said pixel blocks.

48. A data hiding method according to claim 40, 41, or 42 wherein said first and second blocks are pixel blocks, and wherein said characteristic value is the variance value of said pixel blocks.

41. A data hiding method for hiding data in media data comprising the steps of:

(a) identifying a pair of blocks in the media data which comprise a first block and a second block;

(b) determining characteristic values of each said first and second blocks and manipulating the characteristic values of said blocks so as to hide the message data;

(c) comparing the difference between said determined characteristic values, and based on a translation rule, manipulating the characteristic values of said respective blocks constituting said pair so as to hide part of the data in the message data;

(d) repeating steps (a) to (c) to hide all message data, wherein the hiding data are elements of a message array and media data are elements of a media array, a media data for hiding message data being identified by an associated state value determined according to a prior state value associated with a prior media data element of said media array, and array elements of said message array.

42. A data hiding method for hiding data in media data comprising the steps of:

(a) identifying a pair of blocks in the media data which comprise a first block and a second block;

(b) determining characteristic values of said respective blocks constituting said pair;

(c) exchanging the characteristic values of said blocks constituting said pair so as to hide message data, based on a translation rule that specifies the difference in the characteristic value between the blocks, wherein message data to be hidden are elements of a message array and media data are elements of a media array, a media data for hiding message data being identified by an associated state value determined according to a prior state value associated with a prior media data element of said media array, and array elements of said message array.

49. A data extraction method for extracting message data from media data with the message data hidden therein comprising the steps of:

(a) identifying a first block in the media data in which the message data is hidden;

(b) determining the characteristic value of said identified first block; and

(c) extracting the message data according to the characteristic value of said first block by referencing a translation rule that associates the contents of the data to be extracted with the difference between a reference value for the characteristic value and the characteristic value of said first block, wherein message data to be extracted are elements of a message array and media data are elements of a media array, a media data having message data hidden therein being identified by an associated state value determined according to a prior state value associated with a prior media data element of said media array, and array elements of said message array.

50. A data extraction method according to claim 49 wherein said reference value is present in the media data and is the characteristic value of a second block different from said first block.

52. A data extraction method according to claim 50 or 51 wherein said second block is adjacent to said first block constituting a pair with the second block.

53. A data extraction method according to claim 50 or 51 wherein said translation rule states that one of the bits is extracted if the characteristic value of said first block is larger than that of the second block, while the other bit is extracted if the characteristic value of said first block is smaller than that of the second block.

54. A data extraction method according to claim 50 or 51 wherein said translation rule determines that no media data is hidden in the pair if the difference in the characteristic value between said first block and said second block constituting the pair is smaller than a specified threshold.

55. A data extraction method according to claim 49 or 51 wherein said first block is a first pixel block, and wherein said characteristic value is the brightness value of said first pixel block.

56. A data extraction method according to claim 50 or 51 wherein said first and second blocks are pixel blocks, and wherein said characteristic value is the variance value of said pixel blocks.

51. A data extraction method for extracting message data from media data with the message data hidden therein comprising the steps of:

(a) identifying first and second blocks in the media data in which the message data is hidden;

(b) determining the characteristic values of said first and second blocks constituting said pair; and

(c) extracting the hidden data according to the characteristic value of the said respective blocks by referencing a translation rule that associates the contents of the data to be extracted with the difference in the characteristic value between said first and second blocks constituting said pair, wherein message data to be extracted are elements of a message array and media data are elements of a media array, a media data having message data hidden therein being identified by an associated state value determined according to a prior state value associated with a prior media data element of said media array, and array elements of said message array.

57. A data extraction system for extracting message data from media data with the message data hidden therein, comprising:

a converter for converting the message data comprising analog signals and including the hidden message data, into digital signals and for outputting the digital signals;

an identifier for identifying a first block in the media data in which the message data is hidden;

a characteristic value calculator for determining the characteristic value of said first block identified by said identifier;

a storage for storing a translation rule that associates the contents of the data to be extracted with the difference between a reference value for the characteristic value and the characteristic value of said first block; and

an extractor for extracting the message data according to the characteristic value of said first block by referencing said translation rule, wherein message data to be extracted are elements of a message array and media data are elements of a media array, a media data having message data hidden therein being identified by an associated state value determined according to a prior state value associated with a prior media data element of said media array, and array elements of said message array.

58. A data extraction system according to claim 57 wherein said reference value is present in the media data and is the characteristic value of a second block different from said first block.

59. A data extraction system according to claim 58 wherein said translation rule states that one of the bits is extracted if the characteristic value of said first block is larger than that of the second block, while the other bit is extracted if the characteristic value of said first block is smaller than that of the second block.

60. A semiconductor integrated circuit for extracting message data from media data with the message data hidden therein, comprising:

a device for determining the characteristic value of a first block in the media data comprising input signals which is identified as the one in which the message data is hidden; and

an extractor for extracting the hidden message data according to the characteristic value of said first block by referencing a translation rule that associates the contents of the data to be extracted with the difference between a reference value for the characteristic value and the characteristic value of said first block, wherein message data to be extracted are elements of a message array and media data are elements of a media array, a media data having message data hidden therein being identified by an associated state value determined according to a prior state value associated with a prior media data element of said media array, and array elements of said message array.

61. A semiconductor integrated circuit according to claim 60 wherein said reference value is present in the media data and is the characteristic value of a second block different from said first block.

62. A semiconductor integrated circuit according to claim 61 wherein said translation rule states that one of the bits is extracted if the characteristic value of said first block is larger than that of the second block, while the other bit is extracted if the characteristic value of said first block is smaller than that of the second block.