Multiple frame data hiding method and data detection method

• US 6,370,272 B1
• Filed: 04/07/1998
• Issued: 04/09/2002
• Est. Priority Date: 04/07/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Shimizu, Shuichi
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Bayat, Ali
• Application Number:
  US09/056,460
• Time in Patent Office: 1,463 Days
• Field of Search: 382/284, 382/176, 382/232, 382/115, 348/345, 348/62, 348/86, 348/125, 348/135, 348/161, 348/384, 348/571, 348/463, 348/465, 348/467, 725/20, 725/22
• US Class Current: 382/232
• CPC Class Codes: G06T 1/0071 using multiple or alternating watermarks
• CPC Class Codes: G06T 1/0085 Time domain based watermarking, e.g. watermarks spread over several images
• 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: G06T 2201/0065 Extraction of an embedded watermark; Reliable detection
• CPC Class Codes: H04N 1/44 Secrecy systems
• CPC Class Codes: H04N 7/24 Systems for the transmission of television signals using pulse code modulation H04N21/00 takes precedence

Abstract

Data hidden in a plurality of contents is protected from illegal access by a third party. An embedding process is performed by using a frame pattern (mark) that is composed of multiple embedded block patterns comprising several different types and wherein the embedding process is varied in accordance with the time and the frame. One embedding method mixes at random several types of frame patterns having different arrangements of block patterns. The embedding method may change at random a range in which a block pattern is embedded. An embedded mark is detected by processing in parallel a plurality of patterns that are to be detected in contents, and if as a result of detection there is a reaction, it is ascertained that a mark is present. An illegal process may be traced by using an electronic fingerprint obtained by entering a false detection mark in a detector or by using an electronic fingerprint using a random sync signal for an embedding detector.

Claims

1. A data hiding method for embedding information into contents which include a plurality of frames, in which the embedded information cannot be extracted using only statistical methods, comprising the steps of:

(a) defining a plurality of different block patterns, each of said block patterns being represented as a small array of elements each having a value;

(b) constructing a plurality of different frame patterns, each of said frame patterns consisting of a plurality of said block patterns arranged into an array in accordance with a specified rule; and

(c) embedding said frame patterns into said plurality of frames, with each of said different frame patterns being embedded in a different one of said frames, wherein different block patterns are embedded into successive ones of said frames at corresponding locations without forming a cyclic pattern and wherein corresponding elements of said different block patterns have an average value of zero to make extraction of block patterns without having the specified rule using only statistical methods impractical or impossible.

2. The data hiding method according to claim 1, wherein said block patterns are substantially perpendicular to each other.

3. The data hiding method according to claim 1, wherein each of said block patterns is composed of four types of 8×

8 array patterns, two of which are horizontal patterns, and two of which are sign inverted horizontal patterns for which the signs of said horizontal pattern are inverted.

4. The data hiding method according to claim 1, wherein each of said block patterns is composed of 16 types of 8×

8 array patterns, two of which are horizontal patterns, two of which are vertical patterns, two of which are a first check pattern, two of which are a second check pattern, and eight of which are sign inverted patterns for which the signs of the eight patterns are inverted.

5. A data hiding method for embedding information into contents which include a plurality of frames, in which the embedded information cannot be extracted using only statistical methods, comprising the steps of:

(a) defining a plurality of different block patterns, each of said block patterns being represented as a small array of elements each having a value;

(b) constructing a plurality of different frame patterns, each of said frame patterns consisting of a plurality of said block patterns arranged in an array in accordance with a specified rule, said block patterns being so arranged in each said array so as to differ from adjacent block patterns; and

(c) for each said frame, selecting one of said frame patterns at random from among said plurality of different frame patterns and embedding said selected frame pattern into said each frame, wherein different block patterns are embedded into successive ones of said frames at corresponding locations without forming a cyclic pattern and wherein corresponding elements of said different block patterns have an average value of zero to make extraction of block patterns without having the specified rule using only statistical methods impractical or impossible.

6. A data hiding method for embedding information into contents which include a plurality of frames, in which the embedded information cannot be extracted using only statistical methods, comprising the steps of:

(a) defining a plurality of different block patterns, each said block pattern being represented as a small array of elements each having a value;

(b) constructing a plurality of different frame patterns, each of said frame patterns consisting of a plurality of said block patterns arranged in an array in accordance with a specified rule, the number of said block patterns in each said array being equal to the number of said different frame patterns, said block patterns being so arranged in each said array so as to differ from adjacent block patterns; and

(c) for each said frame, selecting one of said frame patterns at random from among said plurality of different frame patterns and embedding said selected frame pattern into said each frame, wherein different block patterns are embedded into successive ones of said frames at corresponding locations without forming a cyclic pattern and wherein corresponding elements of said different block patterns have an average value of zero to make extraction of block patterns without having the specified rule using only statistical methods impractical or impossible.

7. A data hiding method for embedding information into contents which include a plurality of frames, in which the embedded information cannot be extracted using only statistical methods, comprising the steps of:

(a) defining a plurality of different block patterns, each said block pattern being represented as a small array of elements each having a value;

(b) constructing a plurality of different frame patterns, each of said frame patterns consisting of a plurality of said block patterns arranged in an array in accordance with a specified rule, said block patterns being so arranged in each said array so as to differ from adjacent block patterns, and said different frame patterns being sorted into frame pattern groups, the number of said groups being equal to or smaller than the number of said different frame patterns and the number of said block patterns in each said array being equal to the number of said groups; and

(c) for each said frame, selecting one of said frame pattern groups at random, selecting one of said frame patterns from said selected group, and embedding said selected frame pattern into said each frame, wherein different block patterns are embedded into successive ones of said frames at corresponding locations without forming a cyclic pattern and wherein corresponding elements of said different block patterns have an average value of zero to make extraction of block patterns without having the specified rule using only statistical methods impractical or impossible.

8. A data detecting method for detecting information embedded into contents which include a plurality of frames, in which the embedded information cannot be extracted using only statistical methods, said method comprising the steps of:

(a) preparing a plurality of block patterns, each of said block patterns using said embedded information and being represented as a small array of elements each having a value;

(b) constructing frame patterns, said frame patterns consisting of said block patterns located in accordance with specified rules, wherein different block patterns are embedded into successive ones of said frames at corresponding locations without forming a cyclic pattern and wherein corresponding elements of said different block patterns have an average value of zero to make extraction of block patterns without having the specified rule using only statistical methods impractical or impossible; and

(c) detecting said embedded information from said plurality of frames by calculating scalar products between each said frame and all of said frame patterns.

9. The method according to claim 8, wherein said information is detected by using at least one of the scalar products of said frame patterns.

10. The method according to claim 8, wherein at said step of constructing said frame patterns, a false pattern arrangement is added to the arrangement provided in accordance with said specified rules.

11. The method according to claim 8, wherein at said step of constructing said frame patterns, said arrangement provided in accordance with said specified rules is obtained in accordance with a random number row that differs for each detector.

12. A data hiding method for embedding information into a plurality of contents, in which the embedded information cannot be extracted using only statistical methods, comprising the steps of:

(a) defining a plurality of different block patterns, each of said block patterns being represented as a small array of elements each having a value;

(b) constructing a plurality of different frame patterns, each of said frame patterns consisting of a plurality of said block patterns arranged into an array in accordance with a specified rule; and

(c) embedding said frame patterns into said plurality of contents, with each of said different frame patterns being embedded in a different content, wherein different block patterns are embedded into said contents at corresponding locations without forming a cyclic pattern and wherein corresponding elements of said different block patterns have an average value of zero to make extraction of block patterns without having the specified rule using only statistical methods impractical or impossible.

13. The data hiding method according to claim 12, wherein said block patterns are substantially perpendicular to each other.

14. The data hiding method according to claim 12, wherein each of said block patterns is composed of four types of 8×

8 array patterns, two of which are horizontal patterns, and two of which are sign inverted horizontal patterns, for which the signs of said horizontal pattern are inverted.

15. The data hiding method according to claim 12, wherein each of said block patterns is composed of 16 types of 8×

8 array patterns, two of which are horizontal patterns, two of which are vertical patterns, two of which are check patterns of a first type, two of which are check patterns of a second type, and eight of which are sign inverted patterns, for which the signs of the eight patterns are inverted.

16. A data hiding method for embedding information into a plurality of contents, in which the embedded information cannot be extracted using only statistical methods, comprising the steps of:

(a) defining a plurality of different block patterns, each of said block patterns being represented as a small array of elements each having a value;

(b) constructing a plurality of different frame patterns, each of said frame patterns consisting of a plurality of said block patterns arranged in an array in accordance with a specified rule, said block patterns being so arranged in each said array so as to differ from adjacent block patterns; and

(c) for each said content, selecting one of said frame patterns at random from among said plurality of different frame patterns and embedding said selected frame pattern into said each content, wherein different block patterns are embedded into successive contents at corresponding locations without forming a cyclic pattern and wherein corresponding elements of said different block patterns have an average value of zero to make extraction of block patterns without having the specified rule using only statistical methods impractical or impossible.

17. A data hiding method for embedding information into a plurality of contents, in which the embedded information cannot be extracted using only statistical methods, comprising the steps of:

(a) defining a plurality of different block patterns, each of said block patterns being represented as a small array of elements each having a value;

(b) constructing a plurality of different frame patterns, each of said frame patterns consisting of a plurality of said block patterns arranged in an array in accordance with a specified rule, the number of said block patterns in each said array being equal to the number of said different frame patterns, said block patterns being so arranged in each said array so as to differ from adjacent block patterns; and

(c) for each said content, selecting one of said frame patterns at random from among said plurality of different frame patterns and embedding said selected frame pattern into said each content, wherein different block patterns are embedded into successive contents at corresponding locations without forming a cyclic pattern and wherein corresponding elements of said different block patterns have an average value of zero to make extraction of block patterns without having the specified rule using only statistical methods impractical or impossible.

18. A data hiding method for embedding information into a plurality of contents, in which the embedded information cannot be extracted using only statistical methods, comprising the steps of:

(a) defining a plurality of different block patterns, each of said block patterns being represented as a small array of elements each having a value;

(b) constructing a plurality of different frame patterns, each of said frame patterns consisting of a plurality of said block patterns arranged in an array in accordance with a specified rule, said block patterns being so arranged in each said array so as to differ from adjacent block patterns, and said different frame patterns being sorted into frame pattern groups, the number of said groups being equal to or smaller than the number of said different frame patterns and the number of said block patterns in each said array being equal to the number of said groups; and

(c) for each said content, selecting one of said frame pattern groups at random, selecting one of said frame patterns from said selected group, and embedding said selected frame pattern into said each content, wherein different block patterns are embedded into successive contents at corresponding locations without forming a cyclic pattern and wherein corresponding elements of said different block patterns have an average value of zero to make extraction of block patterns without having the specified rule using only statistical methods impractical or impossible.

19. A data detecting method for detecting information embedded into a plurality of contents, in which the embedded information cannot be extracted using only statistical methods, comprising the steps of:

(a) preparing a plurality of block patterns, each of said block patterns using said embedded information and being represented as a small array of elements each having a value;

(b) constructing frame patterns, said frame patterns consisting of said block patterns located in accordance with specified rules, wherein different block patterns are embedded into successive ones of said frames at corresponding locations without forming a cyclic pattern and wherein corresponding elements of said different block patterns have an average value of zero to make extraction of block patterns without having the specified rule using only statistical methods impractical or impossible; and

(c) detecting said embedded information from said plurality of contents by calculating scalar products between each said content and all of said frame patterns.

20. The method according to claim 19, wherein said information is detected by using at least one of the scalar products of said frame patterns.

21. The method according to claim 19, wherein at said step of constructing said frame patterns, a false pattern arrangement is added to the arrangement provided in accordance with said specified rules.

22. The method according to claim 19, wherein at said step of constructing said frame patterns, said arrangement provided in accordance with said specified rules is obtained in accordance with a random number row that differs for each detector.