Image analysis – Applications
Reexamination Certificate
2002-03-22
2003-06-17
Johns, Andrew W. (Department: 2621)
Image analysis
Applications
Reexamination Certificate
active
06580809
ABSTRACT:
TECHNICAL FIELD
The invention relates to multimedia signal processing, steganography and data hiding.
BACKGROUND AND SUMMARY
Digital watermarking is a process for modifying physical or electronic media to embed machine-readable auxiliary data into the media. The media may be modified such that the embedded code is imperceptible or nearly imperceptible to the user, yet may be recovered through an automated reader process. Most commonly, digital watermarking is applied to media signals such as images, audio signals, and video signals. However, it may also be applied to other types of media objects, including documents (e.g., through line, word or character shifting), software, multi-dimensional graphics models, and surface textures of objects.
Digital watermarking systems typically have two primary components: an encoder that embeds the watermark in a host media signal, and a decoder that detects and reads the embedded watermark from a signal suspected of containing a watermark (a suspect signal). The encoder embeds a watermark by altering the host media signal. The reading component analyzes a suspect signal to detect whether a watermark is present. In applications where the watermark encodes information, the reader extracts this information from the detected watermark.
Several particular watermarking techniques have been developed. The reader is presumed to be familiar with the literature in this field. Particular techniques for embedding and detecting imperceptible watermarks in media signals are detailed in the assignee's co-pending application Ser. Nos. 09/503,881, and 60/256,629 and U.S. Pat. No. 6,122,403 which are hereby incorporated by reference.
One category of data hiding methods embeds auxiliary data by quantizing samples or other features of a media signal such that the quantized sample falls within a quantization bin corresponding to a desired auxiliary message symbol. The message symbols may be binary or M-ary. Preferably, the modification made to the sample to move it into the quantization bin is constrained to stay within a desired perceptual distortion tolerance. This perceptual distortion tolerance enables the auxiliary data to be hidden in a manner that is imperceptible to the viewer or listener of embedded media content. One form of such auxiliary data embedding and reading is referred to as Quantization Index Modulation or QIM. Examples of this form of data hiding is disclosed in WO9960514A1: SYSTEM, METHOD, AND PRODUCT FOR INFORMATION EMBEDDING USING AN ENSEMBLE OF NON-INTERSECTING EMBEDDING GENERATORS and corresponding U.S. Pat. No. 6,233,347; which are hereby incorporated by reference.
To read embedded data, the samples of content expected to include auxiliary data are evaluated to determine which quantizer or quantization bin they represent. Symbol errors may result when samples get mapped to a different quantizer or quantization bin relative to the one used to encode them. Error correction encoding tends to mitigate symbol errors if the distortion is not significant or does not impact the embedded data adversely.
Quantization embedding techniques may be performed on samples or other signal features in various signal or transform domains of multimedia signals. To reduce the impact of distortion, the embedding domain may be chosen such that samples in that domain are relatively robust or invariant to expected types of distortion.
A challenge associated with data hiding methods, including quantization embedding techniques, is synchronizing the reader with the embedded data after the host signal carrying the embedded data has been distorted, e.g., geometrically or temporally distorted. Such forms of distortion have the effect of distorting the quantization bins. Thus, if the same quantizers or bins are used to interpret embedded data symbols in the reader as in the embedder, the reader may map distorted samples to the wrong quantizer or bin. Additional types of distortion that specifically effect quantization embedding techniques include the addition of an unknown offset or multiplication by an unknown gain.
This document details methods of synchronizing embedded data readers in quantization embedding systems for multimedia content. In the embedder, a reference signal and message symbols are encoded using a quantization embedding method. In the reader, the distorted data samples are evaluated to derive quantizers or quantization bins. The reader then uses the derived quantization information to convert the distorted data to raw symbol estimates. These raw symbol estimates are then evaluated to detect the presence of the reference signal. Once detected, the reference signal is used to determine the distortion and compensate for it by adjusting the quantization information or distorted data such that message symbols may be decoded more accurately.
Certain forms of offset and gain distortion make it difficult to recover hidden data embedded in an audio or image signal by quantization techniques. To compensate for this offset and gain distortion, an embedded data reader analyzes a statistical distribution (e.g., a histogram) of feature samples in an audio or image signal suspected of having hidden auxiliary data to derive an estimate of quantizers used to encode a reference signal (deriving an estimate of the quantizers is equivalent to estimating the offset and gain distortions). The estimated quantizers then recover the reference signal, and the reader uses the reference signal to determine and compensate for geometric or temporal distortion, like spatial scaling and rotation of image data, and time scale and speed changes of audio data. After compensating for such distortion, the reader can then more accurately recover hidden message data using quantization techniques to extract the message. The reference signal is preferably repeated in blocks of the image or audio data to enable synchronization at many points in an image or audio data stream.
The invention provides a method of hiding auxiliary data in a media signal such that the auxiliary data is humanly imperceptible yet recoverable by an automated auxiliary data reader. This method comprises segmenting the media signal into regions, determining statistics for the regions, and adapting quantization bins for each region based on the statistics calculated for the region. To hide auxiliary data in the regions, the method quantizes signal characteristics in the regions into the quantization bins adapted for the regions. The quantization bins correspond to auxiliary data symbols and the signal characteristics are quantized into selected bins depending on the auxiliary data symbol to be embedded in the signal characteristics.
Another aspect of the invention is a compatible reading method for this hidden data embedding method. The reading method segments the media signal into regions, determines statistics for the regions, and based on the statistics for each region, adapts quantization bins for the region. To extract auxiliary data hidden in the regions, the method maps signal characteristics in the regions into the quantization bins adapted for the regions. The quantization bins correspond to auxiliary data symbols, and thus symbols are extracted depending on which bins the signal characteristics map into. In the embedding method, the signal characteristics have been quantized into selected bins depending on the auxiliary data symbols embedded in the signal characteristics.
Further features will become apparent with reference to the following detailed description and accompanying drawings.
REFERENCES:
patent: 6233347 (2001-05-01), Chen et al.
patent: 6314192 (2001-11-01), Chen et al.
patent: 6396937 (2002-05-01), Chen et al.
patent: 6400826 (2002-06-01), Chen et al.
patent: 2002/0106104 (2002-08-01), Brunk et al.
patent: 2002/0126872 (2002-09-01), Brunk et al.
patent: 2002/0154778 (2002-10-01), Mihcak et al.
patent: WO 99/60514 (1999-05-01), None
patent: WO 00/65536 (2000-11-01), None
Chen et al., “Dither modulation: a new approach to digital watermarking and information hiding,”Proc. SPIE vol. 3657:
Brunk Hugh L.
Sharma Ravi K.
Stach John
Digimarc Corporation
Digimarc Corporation
Johns Andrew W.
Meyer Joel R.
LandOfFree
Quantization-based data hiding employing calibration and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Quantization-based data hiding employing calibration and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantization-based data hiding employing calibration and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3115854