Data hiding and extraction methods

• US 6,512,835 B1
• Filed: 01/10/2000
• Issued: 01/28/2003
• Est. Priority Date: 06/20/1996
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kobayashi, Mei, Numao, Masayuki, Shimizu, Shuichi, Morimoto, Norishige
• Primary Examiner(s): Mancuso, Joseph
• Assistant Examiner(s): MILLER, MARTIN E
• Application Number:
  US09/480,024
• Time in Patent Office: 1,114 Days
• Field of Search: 382/100, 725/9, 725/20, 725/22, 348/460, 348/461, 348/463
• 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 broadcast system comprising:

a storage apparatus in which commercial media data is stored;

an encoder for hiding in said commercial media data, message data used to count the number of broadcasts of said commercial media data; and

a broadcast apparatus for broadcasting said commercial media data with said message data hidden therein, wherein;

said message data is dispersively hidden in said commercial media data based on the data in said message data for counting, 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; and

(a) means for determining the j-th (j≧

0) state value;

(b) means for 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) means for hiding data with respect to the array element of said media array indicated by said (j+1)-th state value.

2. The broadcast system according to claim 1 wherein if j=0 in said means for determining in subparagraph (a), the initial state value is determined on the basis of the data in the array elements of said message array.

3. The broadcast system according to claim 1 wherein if j=0 in said means for determining in subparagraph (a), the exclusive OR of the data in all the array elements of said message array is used as an input to said initial function, the output of said initial function being used as said initial state value.

4. The broadcast system according to claim 1 wherein in said means for determining in subparagraph (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.

5. The broadcast system according to claim 1 wherein in said means for determining in subparagraph (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.

6. The broadcast system according to claim 5 wherein said hiding position translation function is an enciphering function that uses as a parameter, a secret key used in a public key method.

7. The broadcast system according to claim 1 wherein, in said means for hiding data in subparagraph (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.

8. The broadcast system according to claim 1 wherein, in said means for hiding data in subparagraph (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 characteristic values of the pixel blocks are manipulated based on a translation rule so as to hide the hiding data.

9. The broadcast system according to claim 8 wherein said second block is adjacent to said first block constituting a pair with the second block.

10. The broadcast system according to claim 8 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.

11. The broadcast system according to claim 10 wherein said characteristic value is the brightness value of said pixel block.

12. The broadcast system according to claim 10 wherein said characteristic value is the variance value of said pixel block.

13. A broadcast system comprising:

a storage apparatus in which commercial media data is stored;

an encoder for hiding in said commercial media data, message data used to count the number of broadcasts of said commercial media data; and

a broadcast apparatus for broadcasting said commercial media data with said message data hidden therein, wherein;

said message data is dispersively hidden in said commercial media data based on the data in said message data for counting, 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; 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, further comprising;

(a) means for determining the j-th (j≧

0) state value;

(b) means for 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) means for hiding data with respect to the array element of said media array indicated by said (j+1)-th state value; and

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

14. The broadcast system according to claim 13 further including means for extracting said media array in which said hiding data is hidden;

and the last state value.

15. A receiving system comprising:

a receiver for receiving commercial media data including dispersively hidden message data used to count the number of broadcasts of said commercial media data;

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

a counter for counting the number of broadcasts of said commercial media data based on said extracted message data, wherein;

based on the data in said message data for counting, the positions of said dispersively hidden message data in said commercial media data are identified and the message data is then extracted, 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;

(a) means for determining the j-th (j≧

0) state value;

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

(c) means for 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) means for 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.

16. The receiving system according to claim 15 wherein in said means for determining in subparagraph (a), the first state value used in starting extraction is provided to an extractor as information required for extraction.

17. The receiving system according to claim 16 wherein the first state value used to start extraction is the last state value generated in hiding said message array.

18. The receiving system according to claim 15 wherein in said means for determining in subparagraph (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.

19. The receiving system according to claim 15 wherein an extraction position translation function is provided, and wherein in said means for determining in subparagraph (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.

20. The receiving system according to claim 19 wherein said extraction position translation function is an deciphering function that uses as a parameter, a public key used in the public key method.

21. The receiving system according to claim 15 wherein, in said means for extracting in subparagraph (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.

22. The receiving system according to claim 15 wherein, in said means for extracting in subparagraph (b), a first pixel block corresponding 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 characteristic values of said first and second pixel blocks constituting a pair on the basis of an extraction rule.

23. The receiving system according to claim 22 wherein said second block is adjacent to said first block constituting a pair with the second block.

24. The receiving system according to claim 22 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.

25. The receiving system according to claim 24 wherein said characteristic value is the brightness value of said pixel block.

26. The receiving system according to claim 24 wherein said characteristic value is the variance value of said pixel block.

27. The receiving system according to claim 24 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 further including:

(f) in said means for extracting in subparagraph (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.

28. The receiving system according to claim 27 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.

29. The receiving system according to claim 27 wherein in said means for extracting in subparagraph (d), the end of extraction is recognized when the output of said initial function is equal to said (j−

1)-th state value.

30. A receiving system comprising:

a receiver for receiving commercial media data including dispersively hidden message data used to count the number of broadcasts of said commercial media data;

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

a counter for counting the number of broadcasts of said commercial media data based on said extracted message data, wherein;

based on the data in said message data for counting, the positions of said dispersively hidden message data in said commercial media data are identified and the message data is then extracted, 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;

(a) means for determining the j-th (j≧

1) state value;

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

(c) means for determining the (j−

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

(d) means for 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) means for recursively executing subparagraphs (a) to (c) until an extraction end condition is met.