1. Field of the Invention
The present invention relates to a data hiding method for embedding additional information in contents, such as multiple still images, movies, multimedia or MOPES, and a data extraction method.
2. Related Art
Generally, for data hiding, additional information is hidden by performing some process for embedding it in contents. This applies not only when embedding is performed for a single part of the contents or a single frame, but also when it is performed for multiple parts of the contents or a plurality of frames.
For an example, refer to FIG. 1, an outline for a process for hiding data in a plurality of frames. FIG. 1 is a diagram showing the process for hiding information 30 (data) in contents composed of a set of sequential frames 15, which consists of single frames 10.
Commonly, for data hiding, an embedding process based on a secret key is employed to hide additional information in the contents. Specifically, as is shown in FIG. 2, frame patterns 40 are embedded in frames to hide data.
More specifically, by using an information arrangement acquired using the secret key in accordance with a specified rule, small arrays of block patterns 50 prepared in advance are arranged to produce a single pattern frame 40. This pattern frame 40 is embedded in the original contents 20 to hide the information 30.
In FIG. 2, there are four block pattern types: B1 through B4, each pattern being constructed by purposely arranging elements xe2x88x921, 0 and +1. The block patterns in FIG. 2 are merely samples. In actuality, the number of block pattern types is not limited to four, and variable values, such as xe2x88x92k, 0 and +k (k: integer), can be used as the elements of the block pattern.
In the data hiding technique, supposing that the original contents can not be acquired, without a key, it is not easy without a key to extract embedded information from the contents and to illegally erase information.
Illegal reading of only a single image is impossible; however, when a data hiding method developed for still images is applied for moving images, or when the data hiding method is applied for multiple types of still images by using the same key, the images could be illegally read, even without a key, if a statistical process is performed for multiple image samples.
In FIG. 3 is shown an example wherein a conventional data hiding method is applied for the frame set 15. In FIG. 3, there are m types of block patterns 50, B1 to Bm, and the total number of blocks in a frame pattern 40 is N. The m type pixel block patterns are arranged in a certain order on a frame pattern 40, and the frame pattern 40 is embedded in a frame 10. This data hiding method is basically the same as the xe2x80x9cdata hiding method employing a statistical property and extraction methodxe2x80x9d disclosed in Japanese Patent Application No. Hei 8-345568.
The arrangement of block patterns in a frame pattern serves as a key for a data detection process. To deduce the arrangement of block patterns from an image frame in which data have been embedded, mN trials are required. Therefore, the deducing the arrangement without possessing a key is quite difficult when the number of calculations required is taken into consideration, since N normally denotes the number of blocks, which could be 5400, for example. However, when as is shown in FIG. 3 the block patterns are added in the same arrangement to sequential image frames, i.e., when a block pattern B is determined only at location i below:
xe2x80x83Block Pattern: B(i),
the same pattern block is employed at specified positions 25 in the frame, even though the frame numbers may differ. Relative to frames, the number of which (e.g., 1000) is so adequate that a statistically unique value can be measured by using the above property, if m types of patterns are applied to the specified locations in the frames to acquire the statistical unique value, block patterns embedded at the locations can be deduced by observing the unique value. When this measurement process is performed for the entire frame, the arrangement of the block patterns can be illegally deduced even without a key.
To extract added information from sequential data, such as video data and audio data, an extraction process must be synchronized with an embedded signal in the sequential data. For a single set of data such as stationary image, sometimes an embedded signal is repeated cyclically to defeat an illegal extraction process, so that synchronization is required for the extraction of the embedded information. However, this processing cycle is an important clue for a third party to illegally access information. This is a big problem because if embedded information can be accurately read, it is possible for the embedded information to be erased illegally.
Assuming that t denotes a frame number (time) and mod denotes a multiplication/subtraction calculation, a block pattern that is repeated at time T, for example, can be represented as follows:
xe2x80x83Block Pattern: B(i, t mod T).
In this case, an embedded frame pattern can be deduced by measuring a statistic value every time T.
In addition, when an embedding process is to be performed using a different pattern arrangement for each frame, the block pattern is as follows:
Block Pattern: B(i, t).
While a pattern can not be illegally deduced by measuring a statistical value, there is also nothing to induce the performance of synchronized processing by a detector. As a result, another problem arises in that real-time synchronization is difficult.
The consideration or countermeasure for the above problems is not described for the conventional methods disclosed, for example, in Japanese Patent Application No. Hei 8-345568 and xe2x80x9cMethod and Apparatus for Data Hiding in Imagesxe2x80x9d in U.S. patent application No. 109026-20/7116T.
It is one object of the present invention to prevent in advance a security hole that occurs when a conventional data hiding technique for stationary images is applied for video images.
That is, it is another object of the present invention to hide data in contents that are composed of a plurality of frames, to detect the hidden data, and to prevent the illegal extraction of the hidden data, or key.
It is an additional object of the present invention to hide data in a plurality of contents that are not related to each other, to detect the hidden data, and to prevent illegal extraction of the hidden data, or key.
It is a further object of the present invention to provide a method, for preventing the illegal reading of data by a third party who does not know an embedded key, whereby embedded data can not be completely read even if the third party illegally decodes a detector.
It is still another object of the present invention to provide a method for hiding an electronic fingerprint and in a detector an embedding device.
It is a still further object of the present invention to provide a data hiding method whereby a deduction is difficult for a party illegally accessing data because a large number of calculations is required, and whereby real-time synchronous detection is enabled by a detector.
To achieve the above objects, according to the present invention, provided is a method whereby an embedding process is performed by using a frame pattern (mark) that is composed of multiple embedded block patterns comprising several different types and whereby the embedding process is varied in accordance with the time and the frame. Specifically, the following methods are employed:
an embedding method for mixing at random several types of frame patterns having different arrangements of block patterns, and
an embedding method for changing at random a range in which a block pattern is embedded.
The following method is employed to detect an embedded mark: a method whereby a plurality of patterns to be detected in contents are processed in parallel, and whereby, if as a result of detection there is a reaction, it is ascertained that a mark is present.
The following items are employed to trace an illegal process:
an electronic fingerprint obtained by entering a false detection mark in a detector; and
an electronic fingerprint using a random sync signal for an embedding detector.
With the above methods, it is possible to securely protect data hidden in a plurality of contents from illegal access by a third party.