US5778102A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Compression embedding
Assignee: University of California
•
Filing: 1996-12-19
•
Granted: 1998-07-07
•
Expires: 2016-12-19
Abstract
Abstract A method and apparatus for embedding auxiliary information into the digital representation of host data created by a lossy compression technique and a method and apparatus for constructing auxiliary data from the correspondence between values in a digital key-pair table with integer index values existing in a representation of host data created by a lossy compression technique. The methods apply to data compressed with algorithms based on series expansion, quantization to a finite number of symbols, and entropy coding. Lossy compression methods represent the original data as ordered sequences of blocks containing integer indices having redundancy and uncertainty of value by one unit, allowing indices which are adjacent in value to be manipulated to encode auxiliary data. Also included is a method to improve the efficiency of lossy compression algorithms by embedding white noise into the integer indices. Lossy compression methods use loss-less compression to reduce to the final size the intermediate representation as indices. The efficiency of the loss-less compression, known also as entropy coding compression, is increased by manipulating the indices at the intermediate stage. Manipulation of the intermediate representation improves lossy compression performance by 1 to 10%.
Inventors
- 👤 II Maxwell T. Sandford
- 👤 Theodore G. Handel
- 👤 Jonathan N. Bradley
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 11:28
CPC Classifications
H; H04; H04N; H04N7/00; H04N7/24; H04N7/52; H04N1/00; H04N1/32; H04N1/32101; H04N1/32144; H04N1/32149; H04N1/32154; H04N1/32165; H04N1/32267; H04N1/32277; H04N19/00; H04N19/46; H04N19/467; H04N19/60; H04N19/61; H04N21/00; H04N21/20; H04N21/23; H04N21/238; H04N21/2389; H04N21/23892; H04N21/80; H04N21/83; H04N21/835; H04N21/8358; H04N19/63; H04N2201/00; H04N2201/32; H04N2201/3201; H04N2201/3269; H04N2201/327
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
162 words
A method of embedding auxiliary data into host data compressed by lossy compression ratio methods that use series expansion and quantization techniques comprising the steps of: creating a duplicate digital compression representation of said host data in terms of intermediate integer indices representing coefficients, said digital compression representation having certain statistical properties; creating a digital representation of said auxiliary data in the form of a sequence of individual bit values; evaluating said digital compression representation to determine pairs of integer indices differing by a specified number of units and occurring with similar frequency in said digital compression representation; replacing individual integer indices in said digital compression representation with values taken from a digital key comprising a schedule of said pairs of integer indices in order to embed individual bit values corresponding to said sequence of individual bit values of said auxiliary data; and outputting said digital compression representation with said auxiliary data embedded into a file format specified for said compressed data.
Claim 2
Independent Claim
162 words
A method of embedding auxiliary data into host data compressed by lossy compression ratio methods that use series expansion and quantization techniques comprising the steps of: creating a duplicate digital compression representation of said host data in terms of intermediate integer indices representing coefficients, said digital compression representation having certain statistical properties; creating a digital representation of said auxiliary data in the form of a sequence of individual bit values; evaluating said digital compression representation to determine pairs of integer indices differing by a specified number of units and occurring with similar frequency in said digital compression representation; replacing individual integer indices in said digital compression representation with values taken from a digital key comprising a schedule of said pairs of integer indices in order to embed individual bit values corresponding to said sequence of individual bit values of said auxiliary data; and outputting said digital compression representation with said auxiliary data embedded into a file format specified for said compressed data.
Claim 3
Dependent Claim
46 words
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.
Claim 4
Dependent Claim
31 words
The method as described in claim 1 further comprising the step of equalizing said statistical properties of said digital compression representation for the purpose of improving said lossy compression ratio methods.
Claim 5
Dependent Claim
29 words
The method as described in claim 1, wherein said digital compression representation originates from a color image compressed with the JPEG or WSQ algorithm, and their derivative compression representations.
Claim 6
Dependent Claim
31 words
The method as described in claim 1, wherein said digital compression representation originates from a black and white image compressed with the JPEG or WSQ algorithm, and their derivative compression representations.
Claim 7
Dependent Claim
32 words
The method as described in claim 1, wherein said digital compression representation originates from a television or video disc signal compressed with the MPEG and DCT-based algorithms, and their derivative compression representations.
Claim 8
Dependent Claim
21 words
The method as described in claim 1, wherein said digital compression representation originates from digital audio represented by lossy compression representations.
Claim 9
Dependent Claim
21 words
The method as described in claim 1, wherein said digital compression representation originates from X-ray, CT-scan, or Magnetic Resonance Imaging data.
Claim 10
Dependent Claim
19 words
The method as described in claim 1, wherein said digital compression representation originates from personal security and identification information.
Claim 11
Dependent Claim
16 words
The method as described in claim 1, wherein said digital compression representation originates from fingerprint images.
Claim 12
Dependent Claim
22 words
The method as described in claim 1, wherein said digital compression representation originates from images made with a camera producing digital images.
Claim 13
Independent Claim
151 words
A method of constructing embedded a quantity of auxiliary data from a machine readable lossy digital compression representation containing integer indices comprising the steps of: creating a look-up table defining a correlation between decoded integer indices from said lossy digital compression representation and elements of a key-pair table; matching said decoded integer indices from said lossy digital compression representation with entries in said look-up table, for determining correspondence of said integer indices from said lossy digital compression representation with said elements in said key-pair; constructing said auxiliary data according to said correspondence in said look-up table between said integer indices from said lossy digital compression representation and an element in said key-pair table; validating the content and correctness of said auxiliary data by examining header data constructed from the correspondence between said integer indices and said key-pair values; and interpreting said auxiliary bits as data unrelated to said lossy compressed data.
Claim 14
Independent Claim
151 words
A method of constructing embedded a quantity of auxiliary data from a machine readable lossy digital compression representation containing integer indices comprising the steps of: creating a look-up table defining a correlation between decoded integer indices from said lossy digital compression representation and elements of a key-pair table; matching said decoded integer indices from said lossy digital compression representation with entries in said look-up table, for determining correspondence of said integer indices from said lossy digital compression representation with said elements in said key-pair; constructing said auxiliary data according to said correspondence in said look-up table between said integer indices from said lossy digital compression representation and an element in said key-pair table; validating the content and correctness of said auxiliary data by examining header data constructed from the correspondence between said integer indices and said key-pair values; and interpreting said auxiliary bits as data unrelated to said lossy compressed data.
Claim 15
Dependent Claim
15 words
The method as described in claim 12, wherein said auxiliary data consist of digital text.
Claim 16
Dependent Claim
26 words
The method as described in claim 12, wherein said auxiliary data consist of script or code intended for execution on a network client or server machine.
Claim 17
Dependent Claim
27 words
The method as described in claim 12, wherein said auxiliary data consist of motion vector data or script used in the reconstruction of a digital motion picture.
Claim 18
Dependent Claim
29 words
The method as described in claim 12, wherein said auxiliary data consist of text or digital audio data used for subtitles or language translation of digital motion picture audio.
Claim 19
Dependent Claim
31 words
The method as described in claim 12, wherein said auxiliary data consist of information used to correct degraded, or to decode scrambled image data, for the purpose of controlled service delivery.
Claim 20
Dependent Claim
18 words
The method as described in claim 12, wherein said auxiliary data consist of additional or supplemental digital imagery.
Claim 21
Dependent Claim
16 words
The method as described in claim 12, wherein said auxiliary data consist of personal identification information.
Claim 22
Dependent Claim
18 words
The method as described in claim 12, wherein said auxiliary data consist of medical record or diagnostic information.
Claim 23
Dependent Claim
22 words
The method as described in claim 12, wherein said auxiliary data consist of a portion of the said original lossy compressed data.
Claim 24
Dependent Claim
15 words
The method as described in claim 12, wherein said auxiliary data consist of encrypted information.
Claim 25
Dependent Claim
39 words
The method as described in claim 12, wherein said auxiliary data consist of information transmitted in the space of said lossy compressed representation afforded by the existence of a correspondence between said integer indices and said pair key table.
Claim 26
Dependent Claim
238 words
Apparatus for embedding auxiliary data into individual frames of host data having integer indices of certain values and frequencies of occurrence compressed by lossy compression ratio methods that use series expansion and quantization techniques comprising: buffer storage means receiving said individual frames of host data for entropy decoding, modifying and momentarily storing said integer indices of said individual frames of host data, entropy coding said modifications to said integer indices of said individual frames of host data, and outputting said entropy coded modifications to said integer indices of said individual frames of host data; histogram analysis means receiving said entropy decoded integer indices of said individual frames of host data for processing a statistical relationship between said frequency of occurrence and said value of said integer indices of said individual frame of host data identify embedding pair candidates in said individual frames of host data, and outputting said embedding pair candidates; key-pair table means receiving said embedding pair candidates for creating a key-pair table for each of said individual frames of host data, and outputting said embedding pair candidates as a randomized table; compression embedding means receiving said embedding key pair table, said integer indices from said individual frames of host data retained in said buffer storage, and said auxiliary data for embedding said auxiliary data and said key-pair table into said individual frames of host data and outputting an embedded stream of individual frames of host data.
Claim 27
Dependent Claim
238 words
Apparatus for embedding auxiliary data into individual frames of host data having integer indices of certain values and frequencies of occurrence compressed by lossy compression ratio methods that use series expansion and quantization techniques comprising: buffer storage means receiving said individual frames of host data for entropy decoding, modifying and momentarily storing said integer indices of said individual frames of host data, entropy coding said modifications to said integer indices of said individual frames of host data, and outputting said entropy coded modifications to said integer indices of said individual frames of host data; histogram analysis means receiving said entropy decoded integer indices of said individual frames of host data for processing a statistical relationship between said frequency of occurrence and said value of said integer indices of said individual frame of host data identify embedding pair candidates in said individual frames of host data, and outputting said embedding pair candidates; key-pair table means receiving said embedding pair candidates for creating a key-pair table for each of said individual frames of host data, and outputting said embedding pair candidates as a randomized table; compression embedding means receiving said embedding key pair table, said integer indices from said individual frames of host data retained in said buffer storage, and said auxiliary data for embedding said auxiliary data and said key-pair table into said individual frames of host data and outputting an embedded stream of individual frames of host data.
Claim 28
Dependent Claim
26 words
The apparatus as described in claim 24 wherein said buffer storage means, said key-pair table means, and said compression embedding means are contained within a chipset.
Claim 29
Dependent Claim
27 words
The apparatus as described in claim 24 wherein said buffer storage means, said key-pair table means, and said compression embedding means are implemented in circuit board circuitry.
Claim 30
Dependent Claim
131 words
Apparatus for constructing auxiliary data and a key-pair table embedded into individual frames of host data compressed by lossy compression ratio methods that use series expansion and quantization techniques comprising: look-up table means receiving said key-pair table from said individual frames of host data for extracting said key-pair table and outputting a key-pair index corresponding to each of said integer indices from said individual frames of host data in a buffer storage; and auxiliary data construction means receiving said key pair table for each of said individual frames of host data and said integer indices from said individual frames of host data stored in said buffer storage for using said key pair to construct said auxiliary data from said individual frames of host data and outputting an auxiliary data bit stream.
Claim 31
Dependent Claim
131 words
Apparatus for constructing auxiliary data and a key-pair table embedded into individual frames of host data compressed by lossy compression ratio methods that use series expansion and quantization techniques comprising: look-up table means receiving said key-pair table from said individual frames of host data for extracting said key-pair table and outputting a key-pair index corresponding to each of said integer indices from said individual frames of host data in a buffer storage; and auxiliary data construction means receiving said key pair table for each of said individual frames of host data and said integer indices from said individual frames of host data stored in said buffer storage for using said key pair to construct said auxiliary data from said individual frames of host data and outputting an auxiliary data bit stream.
Claim 32
Dependent Claim
23 words
The apparatus as described in claim 27 wherein said look-up table means and said auxiliary data construction means are contained within a chipset.
Claim 33
Dependent Claim
24 words
The apparatus as described in claim 27 wherein said look-up table means and said auxiliary data construction means are implemented in circuit board circuitry.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-07-06 | 2002-01-05 | 2002-07-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-07-06 | 2006-01-05 | 2006-07-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-07-06 | 2010-01-05 | 2010-07-07 | $7700.00 | Window Closed / Lapsed |