Image analysis – Applications
Reexamination Certificate
1999-05-11
2001-06-05
Au, Amelia M. (Department: 2623)
Image analysis
Applications
C382S232000, C375S265000
Reexamination Certificate
active
06243481
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of recorded digital media. More specifically, the present invention pertains to a method and apparatus for embedding hidden data or authenticity codes within digital data.
2. Background Art
Digital still cameras are growing in popularity as they become easier to use and as it becomes easier to archive the captured images on a computer system or memory device. However, the archived images are difficult to search and/or browse, especially when the database of captured images is large. In addition, the user may want information to be associated with each image, such as when and where the image was taken and the like. Currently, digital cameras either do not provide this type of information or have only limited capability to do so.
Digital media (such as digital videocassette recorders, digital video (or versatile) disc players, digital camcorders, digital still cameras and the like) make it possible to efficiently access, manipulate and reproduce digital data such as image data (including text) and video data as well as audio data (including speech). Digital media also make it possible to embed into the digital data supplementary information (e.g., hidden data or authenticity codes) that can be extracted automatically or in response to a user command. For example, the hidden data can be used to embed multiple speech streams into a video, each speech stream in a different language, so that the video can be distributed to a wide range of users who can then each view the video in the language of their choosing.
The hidden data are embedded directly into a selected subset of the pixels in a digital image frame; that is, the selected pixels are modified in order to store the hidden data. However, it is desirable that the embedded hidden data be undetectable by the human visual system. It is also desirable that the hidden data be easy to embed and retrieve, in particular in those cases where the amount of hidden data is relatively large. In addition, it is desirable that the hidden data be robust; that is, the hidden data should remain intact when the host data are compressed, stored, transmitted, manipulated, etc.
In some prior art data hiding schemes, a random sequence representing the data to be hidden is inserted into the digital data (“host data”); however, these schemes introduce a number of difficulties. First, because of its random nature, there are problems with detecting the hidden data. For example, the detection metrics have to be computed for each of the random sequences used in order to determine a statistically satisfactory match between any sequence detected in the host data and valid hidden data. However, for a reasonably large sequence, this computation can take a very long time to complete.
Second, in order for the random sequence to be robust against noise, it must be different enough from other valid hidden data. Accordingly, the distance between each new sequence and other sequences must be checked to make sure that the sequences are not too close to each other. If they are too close, a new sequence must be generated and tested again. Again, these computations can take a very long time to complete.
Another common prior art data hiding technique is to repeat the same sequence at several different locations in the host data. However, the resulting hidden data are not robust against noise. This is especially true when the number of repetitions is small.
Another significant disadvantage to the data hiding techniques described above and in other prior art data hiding techniques is that the host data are often significantly altered in order to facilitate retrieval of the hidden data. For example, the pixel value of the host data at each of the particular locations (e.g., a pixel) where the hidden data are being embedded needs to be increased or decreased by a significant percentage so that the hidden data will stand out. Consequently, surrounding pixels may also need to be changed so that the image is properly blended. This in turn limits the number and position of possible locations within the host data which can be altered without being detectable by the human visual system or without compromising the accuracy of the host data.
In summary, prior art techniques for embedding hidden data into digital data suffer from a number of disadvantages. The hidden data generated using the prior art techniques are not robust against noise and are difficult to embed and retrieve. The prior art techniques can require significant alteration of the host digital image data, and so the number and position of possible locations within the digital data for placing the hidden data are limited.
SUMMARY OF THE INVENTION
Accordingly, what is needed is a method and system for embedding hidden data into digital data so that the hidden data are robust against noise and are easy to embed and retrieve. In addition, what is needed is a system and method that satisfy the above needs and embed hidden data into the host digital data without significantly altering the host data, thereby permitting the hidden data to occupy a large number of positions.
The present invention includes a method and system thereof that satisfy the above needs. These and other advantages of the present invention not specifically mentioned above will become clear within discussions of the present invention presented herein.
The present invention pertains to a method and system thereof for invisibly encoding and embedding information within digital data representing, for example, audio data, image data, and video data. The present invention is well suited for storing a large amount of information while being robust against noise.
In the present embodiment, the information is represented by a plurality of bits which are separated into a group of input bits and a group of pointer bits. One or more output bits are generated from an input bit using a convolutional code. A sequence of bits is selected using a pointer bit and the output bit(s). The information is encoded and embedded into the digital data by modifying coefficients of the digital data according to the sequence of bits selected. Each bit of the sequence of bits selected is used to modify a respective coefficient. In one embodiment, a coefficient is made into an even number when the bit has a first value and the coefficient is made into an odd number when the bit has a second value. In one embodiment, the digital data are in a compressed format.
In one embodiment, the output bit(s) is/are used to point to a subgroup comprising a plurality of sequences of bits, and the pointer bit is used to select one of the sequences of bits from the plurality of sequences of bits.
In one embodiment, the present invention is implemented using a digital camera. In this embodiment, the present invention provides an apparatus for invisibly embedding information about an image (e.g., when and where the image was taken).
In one embodiment, the digital data are in a compressed format (e.g., JPEG or MPEG for image data, MP3 or AC3 for audio data, as well as other data compression formats).
The digital data can be subsequently read to retrieve the embedded and encoded data, and the encoded sequence is then decoded and made available to the user.
REFERENCES:
patent: 5321725 (1994-06-01), Paik et al.
patent: 5721788 (1998-02-01), Powell et al.
patent: 5809160 (1998-09-01), Powell et al.
patent: 6055272 (2000-04-01), Kim
patent: 6064764 (2000-05-01), Bhaskaran et al.
patent: 6069914 (2000-05-01), Cox
Tao et al., “Adaptive Watermarking in the DCT Domain,” Apr. 1997, Department of Electrical Engineering, Princeton University, Princeton, NJ.
Cox et al., “Secure Spread Spectrum Watermarking for Multimedia,” NEC Research Institute, Princeton, NJ.
Swanson et al., “Data Hiding for Video-In-Video,” 1997, Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN.
Au Amelia M.
Do Danny
Sony Corporation of Japan
Wagner , Murabito & Hao LLP
LandOfFree
Information embedding and retrieval method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Information embedding and retrieval method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Information embedding and retrieval method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2544753