Modular error embedding

• US 5,970,140 A
• Filed: 08/02/1996
• Issued: 10/19/1999
• Est. Priority Date: 05/08/1996
• Status: Expired due to Fees

• Current Assignee: Los Alamos National Security LLC (Government of the United States of America)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Ettinger, J. Mark, Handel, Theodore G., Sandford, Maxwell T. II
• Primary Examiner(s): Dombroske, George
• Assistant Examiner(s): AMROZOWICZ, PAUL DOUGLAS
• Application Number:
  US08/646,837
• Time in Patent Office: 1,173 Days
• Field of Search: 380/7, 380/10, 380/49, 380/54, 707/101
• US Class Current: 380/205
• CPC Class Codes: G06T 1/0028 Adaptive watermarking, e.g. Human Visual System [HVS]-based watermarking
• CPC Class Codes: G06T 11/00 2D [Two Dimensional] image generation
• CPC Class Codes: G06T 2201/0051 Embedding of the watermark in the spatial domain
• 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/32229 with selective or adaptive application of the additional information, e.g. in selected regions of the image H04N1/32213 takes 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 2201/327 which are undetectable to the naked eye, e.g. embedded codes

Abstract

A method of embedding auxiliary information into the digital representation of host data containing noise in the low-order bits. The method applies to digital data representing analog signals, for example digital images. The method reduces the error introduced by other methods that replace the low-order bits with auxiliary information. By a substantially reverse process, the embedded auxiliary data can be retrieved easily by an authorized user through use of a digital key. The modular error embedding method includes a process to permute the order in which the host data values are processed. The method doubles the amount of auxiliary information that can be added to host data values, in comparison with bit-replacement methods for high bit-rate coding. The invention preserves human perception of the meaning and content of the host data, permitting the addition of auxiliary data in the amount of 50% or greater of the original host data.

Claims

1. A method of embedding auxiliary data into digital host data of any kind containing noise in the low-order bits comprising the steps of:

selecting values from said digital host data in a sequence determined by a digital key;

creating a digital representation of said auxiliary data in the form of a sequence of individual bit values;

selecting from said digital host data a block of values having a center and a first offset value obtained from said center of said block;

replacing individual host data values with a second block offset value determined from said auxiliary data; and

outputting said replacement values with said auxiliary data embedded into a file format specified for said digital host data.

2. The method as described in claim 1 further comprising the step of combining said auxiliary data with predetermined information indicative of the presence of said auxiliary data, its file name, and file size, said step to be performed after the step of digitizing said auxiliary data.

3. The method as described in claim 1 further comprising the step of modifying a histogram of said host data for the purpose of identifying said host data for copyright purposes.

4. The method as described in claim 1, wherein said digital representation of said host data originates from a color image comprising color intensity components consisting of digital values representing said color intensity components.

5. The method as described in claim 1, wherein said digital representation of said host data originates from a color image comprising color components consisting of digital values for hue, saturation, and intensity.

6. The method as described in claim 1, wherein said digital representation of said host data originates from a black and white image represented by intensity components consisting of digital values.

7. The method as described in claim 1, wherein said digital representation of said host data originates from an audio source.

8. The method as described in claim 1, wherein said digital representation of said host data originates from X-ray, Magnetic Resonance, Positive Electron Tomography, Ultrasound, and Computer Aided Tomagraphic Imaging data.

9. The method as described in claim 1, wherein said digital representation of said host data originates from personal security and identification information.

10. The method as described in claim 1, wherein said representation of said digital host data originates from images made with a camera producing digital images.

11. The method as described in claim 1, wherein said representation of said digital host data originates from, or is relayed by a computer network or a satellite of the Earth.

12. A method of reconstructing auxiliary data from a machine readable digital host data representation into which said auxiliary data has been emedded comprising the steps of:

extracting said auxiliary data from said host data representation in a sequence determined by a digital key;

interpreting said extracted auxiliary data according to the remainder values of a block size that is a binary power of two; and

verifying said auxiliary data by examining said remainder values.