US6031937A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for video compression using block and wavelet techniques
Assignee: Apple Inc
•
Filing: 1994-05-19
•
Granted: 2000-02-29
•
Expires: 2014-05-19
Abstract
Abstract A method and apparatus are disclosed for symmetrically compressing and decompressing video information in real time by coupling block and wavelet techniques. In the compression pipeline, the image is divided into blocks comprising 2 k ×2 k pixels (in the preferred embodiment, k=1). The average color of each block is computed. The system computes an average luminance for each block and differential luminances of each pixel of the plurality of pixels of each block. A first plurality of frequency details of each block are determined by Haar transforming the differential luminances. The system computes an average color difference between each block and the preceding block, and quantizes the average color difference and the first plurality of frequency details using Lloyd-Max quantization. In an alternate embodiment, skip codes are generated for blocks having the same quantized average color difference and second plurality of frequency details. The quantized average color difference and a second plurality of frequency details are encoded using variable length codes. The system employs lookup tables to decompress the compressed image and to format output pixels. The output of the compression pipeline containing variable length codes is decoded into fixed-length codes, which are then decoded using a first lookup table into three device-independent components that represent each block. The three components index a second lookup table containing precomputed RGB values that include precomputed display dependent formatting to produce the output image. In the alternate embodiment, skip codes contained in the output of the variable length decoder are decoded.
Inventors
- 👤 Peter N. Graffagnino
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 17:46
CPC Classifications
H; H04; H04N; H04N19/00; H04N19/90; H04N19/10; H04N19/169; H04N19/186; H04N19/50; H04N19/593; H04N19/60; H04N19/63; H04N19/64; H04N19/645; H04N19/102; H04N19/124
Claims Analysis
Total Claims: 52
Claim 1
Independent Claim
184 words
A method for compressing an image of a first color space, wherein said image is divided into a plurality of blocks, comprising the steps of: computing an average color of a block of said plurality of blocks, said block comprising a plurality of pixels; computing an average luminance of said block dependent on said average color and a differential luminance of each pixel of said plurality of pixels of said block, wherein differential luminance is the difference in luminance value between each particular luminance value of each pixel of said plurality of pixels and the average luminance value of said block; providing a first plurality of frequency details of said block by transforming said differential luminance of each pixel of said plurality of pixels of said block; computing an average color difference between said block and a previous block; quantizing said average color difference and said first plurality of frequency details; and encoding said quantized average color difference and a second plurality of frequency details, wherein said second plurality of frequency details is less than or equal to said first plurality of frequency details.
Claim 2
Independent Claim
184 words
A method for compressing an image of a first color space, wherein said image is divided into a plurality of blocks, comprising the steps of: computing an average color of a block of said plurality of blocks, said block comprising a plurality of pixels; computing an average luminance of said block dependent on said average color and a differential luminance of each pixel of said plurality of pixels of said block, wherein differential luminance is the difference in luminance value between each particular luminance value of each pixel of said plurality of pixels and the average luminance value of said block; providing a first plurality of frequency details of said block by transforming said differential luminance of each pixel of said plurality of pixels of said block; computing an average color difference between said block and a previous block; quantizing said average color difference and said first plurality of frequency details; and encoding said quantized average color difference and a second plurality of frequency details, wherein said second plurality of frequency details is less than or equal to said first plurality of frequency details.
Claim 3
Dependent Claim
16 words
The method of claim 1 wherein said plurality of pixels comprises 2 k ×2 k pixels.
Claim 4
Dependent Claim
11 words
The method of claim 1 wherein k is equal to one.
Claim 5
Dependent Claim
14 words
The method of claim 1 wherein said first color space is RGB color space.
Claim 6
Dependent Claim
26 words
The method of claim 1 wherein said first plurality of frequency details comprises an average term, a horizontal term, a vertical term, and a diagonal term.
Claim 7
Dependent Claim
20 words
The method of claim 5 wherein said second plurality of frequency details comprises said horizontal term and said vertical term.
Claim 8
Dependent Claim
22 words
The method of claim 1 wherein said average color difference and said first plurality of frequency details are quantized using Lloyd-Max quantization.
Claim 9
Dependent Claim
20 words
The method of claim 7 wherein said Lloyd-Max quantization is dependent on a variance and a number of reconstruction levels.
Claim 10
Dependent Claim
22 words
The method of claim 1 wherein said quantized average color and said second plurality of frequency details are encoded using Huffman coding.
Claim 11
Dependent Claim
34 words
The method of claim 1 further comprising the step of providing a skip code when said quantized average color difference and said second plurality of frequency details of said block matches a previous block.
Claim 12
Dependent Claim
20 words
The method of claim 10 wherein said skip code comprises an entry in a lookup table referencing said previous block.
Claim 13
Independent Claim
228 words
An apparatus for compressing an image, said image comprising a plurality of blocks, comprising: average color computation means for computing an average color of a block of said plurality of blocks, said block comprising a plurality of pixels; average and differential luminance computation means coupled to said average color computation means for computing an average luminance of said block dependent on said average color and a differential luminance of each pixel of said plurality of pixels of said block, wherein differential luminance is the difference in luminance value between each particular luminance value of each pixel of said plurality of pixels and the average luminance value of said block; transform means coupled to said average and differential luminance calculation means for computing a first plurality of frequency details of said block dependent on said differential luminance of each pixel of said plurality of pixels of said block; average color difference means coupled to said transform means for calculating an average color difference between said block and a previous block; quantization means coupled to average color difference means for quantizing said average color difference and said first plurality of frequency details; and encoding means for variable length encoding said quantized average color difference and a second plurality of frequency details, wherein said second plurality of frequency details is less than or equal to said first plurality of frequency details.
Claim 14
Independent Claim
228 words
An apparatus for compressing an image, said image comprising a plurality of blocks, comprising: average color computation means for computing an average color of a block of said plurality of blocks, said block comprising a plurality of pixels; average and differential luminance computation means coupled to said average color computation means for computing an average luminance of said block dependent on said average color and a differential luminance of each pixel of said plurality of pixels of said block, wherein differential luminance is the difference in luminance value between each particular luminance value of each pixel of said plurality of pixels and the average luminance value of said block; transform means coupled to said average and differential luminance calculation means for computing a first plurality of frequency details of said block dependent on said differential luminance of each pixel of said plurality of pixels of said block; average color difference means coupled to said transform means for calculating an average color difference between said block and a previous block; quantization means coupled to average color difference means for quantizing said average color difference and said first plurality of frequency details; and encoding means for variable length encoding said quantized average color difference and a second plurality of frequency details, wherein said second plurality of frequency details is less than or equal to said first plurality of frequency details.
Claim 15
Dependent Claim
16 words
The apparatus of claim 12 wherein said plurality of pixels comprises 2 k ×2 k pixels.
Claim 16
Dependent Claim
11 words
The apparatus of claim 12 wherein k is equal to one.
Claim 17
Dependent Claim
14 words
The apparatus of claim 12 wherein said first color space is RGB color space.
Claim 18
Dependent Claim
26 words
The apparatus of claim 12 wherein said first plurality of frequency details comprises an average term, a horizontal term, a vertical term, and a diagonal term.
Claim 19
Dependent Claim
20 words
The apparatus of claim 16 wherein said second plurality of frequency details comprises said horizontal term and said vertical term.
Claim 20
Dependent Claim
13 words
The apparatus of claim 12 wherein said quantization means is Lloyd-Max quantization means.
Claim 21
Dependent Claim
21 words
The apparatus of claim 18 wherein said Lloyd-Max quantization means is dependent on a variance and a number of reconstruction levels.
Claim 22
Dependent Claim
22 words
The apparatus of claim 12 wherein said quantized average color and said second plurality of frequency details are encoded using Huffman coding.
Claim 23
Dependent Claim
42 words
The apparatus of claim 12 further comprising a skip code generation means coupled to said quantization means for generating a skip code when said quantized average color difference and said second plurality of frequency details of said block matches a previous block.
Claim 24
Dependent Claim
20 words
The method of claim 21 wherein said skip code comprises an entry in a lookup table referencing said previous block.
Claim 25
Independent Claim
200 words
A method for compressing an image of a first color space, comprising the steps of: dividing said image into a plurality of blocks in image space, wherein said blocks are comprised of a plurality of adjacent pixels in image space; computing an average color of a block of said plurality of blocks, said block comprising a plurality of pixels; computing an average luminance of said block dependent on said average color and a differential luminance of each pixel of said plurality of pixels of said block; wherein differential luminance is the difference in luminance value between each particular luminance value of each pixel of said plurality of pixels and the average luminance value of said block; providing a first plurality of frequency details of said block by Haar transforming said differential luminance of each pixel of said plurality of pixels of said block; computing an average color difference between said block and a previous block; quantizing said average color difference and said first plurality of frequency details; and encoding said quantized average color difference and a second plurality of frequency details, wherein said second plurality of frequency details is less than or equal to said first plurality of frequency details.
Claim 26
Independent Claim
200 words
A method for compressing an image of a first color space, comprising the steps of: dividing said image into a plurality of blocks in image space, wherein said blocks are comprised of a plurality of adjacent pixels in image space; computing an average color of a block of said plurality of blocks, said block comprising a plurality of pixels; computing an average luminance of said block dependent on said average color and a differential luminance of each pixel of said plurality of pixels of said block; wherein differential luminance is the difference in luminance value between each particular luminance value of each pixel of said plurality of pixels and the average luminance value of said block; providing a first plurality of frequency details of said block by Haar transforming said differential luminance of each pixel of said plurality of pixels of said block; computing an average color difference between said block and a previous block; quantizing said average color difference and said first plurality of frequency details; and encoding said quantized average color difference and a second plurality of frequency details, wherein said second plurality of frequency details is less than or equal to said first plurality of frequency details.
Claim 27
Independent Claim
233 words
An apparatus for compressing an image, said image comprising a plurality of blocks, comprising: average color computation means for computing an average color of a block of said plurality of blocks, said block comprising a plurality of adjacent pixels in image space; average and differential luminance computation means coupled to said average color computation means for computing an average luminance of said block dependent on said average color and a differential luminance of each pixel of said plurality of pixels of said block; wherein differential luminance is the difference in luminance value between each particular luminance value of each pixel of said plurality of pixels and the average luminance value of said block; Haar transform means coupled to said average and differential luminance calculation means for computing a first plurality of frequency details of said block dependent on said differential luminance of each pixel of said plurality of pixels of said block; average color difference means coupled to said transform means for calculating an average color difference between said block and a previous block; quantization means coupled to average color difference means for quantizing said average color difference and said first plurality of frequency details; and encoding means for variable length encoding said quantized average color difference and a second plurality of frequency details, wherein said second plurality of frequency details is less than or equal to said first plurality of frequency details.
Claim 28
Independent Claim
233 words
An apparatus for compressing an image, said image comprising a plurality of blocks, comprising: average color computation means for computing an average color of a block of said plurality of blocks, said block comprising a plurality of adjacent pixels in image space; average and differential luminance computation means coupled to said average color computation means for computing an average luminance of said block dependent on said average color and a differential luminance of each pixel of said plurality of pixels of said block; wherein differential luminance is the difference in luminance value between each particular luminance value of each pixel of said plurality of pixels and the average luminance value of said block; Haar transform means coupled to said average and differential luminance calculation means for computing a first plurality of frequency details of said block dependent on said differential luminance of each pixel of said plurality of pixels of said block; average color difference means coupled to said transform means for calculating an average color difference between said block and a previous block; quantization means coupled to average color difference means for quantizing said average color difference and said first plurality of frequency details; and encoding means for variable length encoding said quantized average color difference and a second plurality of frequency details, wherein said second plurality of frequency details is less than or equal to said first plurality of frequency details.
Claim 29
Independent Claim
185 words
A method for compressing an image of a first color space, wherein said image is divided into a plurality of blocks, comprising the steps of: computing an average color of a block of said plurality of blocks, said block comprising a plurality of pixels; computing an average luminance of said block dependent on said average color and a differential luminance of each pixel of said plurality of pixels of said block, wherein said differential luminance is the difference in luminance value between each particular luminance value of each pixel of said plurality of pixels and the average luminance value of said block; providing a first plurality of frequency details of said block by transforming said differential luminance of each pixel of said plurality of pixels of said block; computing an average color difference between said block and a previous block; quantizing said average color difference and said first plurality of frequency details; and encoding said quantized average color difference and a second plurality of frequency details, wherein said second plurality of frequency details is less than or equal to said first plurality of frequency details.
Claim 30
Independent Claim
185 words
A method for compressing an image of a first color space, wherein said image is divided into a plurality of blocks, comprising the steps of: computing an average color of a block of said plurality of blocks, said block comprising a plurality of pixels; computing an average luminance of said block dependent on said average color and a differential luminance of each pixel of said plurality of pixels of said block, wherein said differential luminance is the difference in luminance value between each particular luminance value of each pixel of said plurality of pixels and the average luminance value of said block; providing a first plurality of frequency details of said block by transforming said differential luminance of each pixel of said plurality of pixels of said block; computing an average color difference between said block and a previous block; quantizing said average color difference and said first plurality of frequency details; and encoding said quantized average color difference and a second plurality of frequency details, wherein said second plurality of frequency details is less than or equal to said first plurality of frequency details.
Claim 31
Dependent Claim
16 words
The method of claim 25 wherein said plurality of pixels comprises 2 k ×2 k pixels.
Claim 32
Dependent Claim
11 words
The method of claim 25 wherein k is equal to one.
Claim 33
Dependent Claim
14 words
The method of claim 25 wherein said first color space is RGB color space.
Claim 34
Dependent Claim
26 words
The method of claim 25 wherein said first plurality of frequency details comprises an average term, a horizontal term, a vertical term, and a diagonal term.
Claim 35
Dependent Claim
20 words
The method of claim 29 wherein said second plurality of frequency details comprises said horizontal term and said vertical term.
Claim 36
Dependent Claim
22 words
The method of claim 25 wherein said average color difference and said first plurality of frequency detail are quantized using Lloyd-Max quantization.
Claim 37
Dependent Claim
20 words
The method of claim 31 wherein said Lloyd-Max quantization is dependent on a variance and a number of reconstruction levels.
Claim 38
Dependent Claim
22 words
The method of claim 25 wherein said quantized average color and said second plurality of frequency details are encoded using Huffman coding.
Claim 39
Dependent Claim
34 words
The method of claim 25 further comprising the step of providing a skip code when said quantized average color difference and said second plurality of frequency details of said block matches a previous block.
Claim 40
Dependent Claim
20 words
The method of claim 34 wherein said skip code comprises an entry in a lookup table referencing said previous block.
Claim 41
Independent Claim
229 words
An apparatus for compressing an image, said image comprising a plurality of blocks, comprising: average color computation means for computing an average color of a block of said plurality of blocks, said block comprising a plurality of pixels; average and differential luminance computation means coupled to said average color computation means for computing an average luminance of said block dependent on said average color and a differential luminance of each pixel of said plurality of pixels of said block, wherein said differential luminance is the difference in luminance value between each particular luminance value of each pixel of said plurality of pixels and the average luminance value of said block; transform means coupled to said average and differential luminance calculation means for computing a first plurality of frequency details of said block dependent on said differential luminance of each pixel of said plurality of pixels of said block; average color difference means coupled to said transform means for calculating an average color difference between said block and a previous block; quantization means coupled to average color difference means for quantizing said average color difference and said first plurality of frequency details; and encoding means for variable length encoding said quantized average color difference and a second plurality of frequency details, wherein said second plurality of frequency details is less than or equal to said first plurality of frequency details.
Claim 42
Independent Claim
229 words
An apparatus for compressing an image, said image comprising a plurality of blocks, comprising: average color computation means for computing an average color of a block of said plurality of blocks, said block comprising a plurality of pixels; average and differential luminance computation means coupled to said average color computation means for computing an average luminance of said block dependent on said average color and a differential luminance of each pixel of said plurality of pixels of said block, wherein said differential luminance is the difference in luminance value between each particular luminance value of each pixel of said plurality of pixels and the average luminance value of said block; transform means coupled to said average and differential luminance calculation means for computing a first plurality of frequency details of said block dependent on said differential luminance of each pixel of said plurality of pixels of said block; average color difference means coupled to said transform means for calculating an average color difference between said block and a previous block; quantization means coupled to average color difference means for quantizing said average color difference and said first plurality of frequency details; and encoding means for variable length encoding said quantized average color difference and a second plurality of frequency details, wherein said second plurality of frequency details is less than or equal to said first plurality of frequency details.
Claim 43
Dependent Claim
16 words
The apparatus of claim 36 wherein said plurality of pixels comprises 2 k ×2 k pixels.
Claim 44
Dependent Claim
11 words
The apparatus of claim 36 wherein k is equal to one.
Claim 45
Dependent Claim
14 words
The apparatus of claim 36 wherein said first color space is RGB color space.
Claim 46
Dependent Claim
26 words
The apparatus of claim 36 wherein said first plurality of frequency details comprises an average term, a horizontal term, a vertical term, and a diagonal term.
Claim 47
Dependent Claim
20 words
The apparatus of claim 40 wherein said second plurality of frequency details comprises said horizontal term and said vertical term.
Claim 48
Dependent Claim
13 words
The apparatus of claim 36 wherein said quantization means is Lloyd-Max quantization means.
Claim 49
Dependent Claim
21 words
The apparatus of claim 42 wherein said Lloyd-Max quantization means is dependent on a variance and a number of reconstruction levels.
Claim 50
Dependent Claim
22 words
The apparatus of claim 36 wherein said quantized average color and said second plurality of frequency details are encoded using Huffman coding.
Claim 51
Dependent Claim
42 words
The apparatus of claim 36 further comprising a skip code generation means coupled to said quantization means for generating a skip code when said quantized average color difference and said second plurality of frequency details of said block matches a previous block.
Claim 52
Dependent Claim
20 words
The method of claim 45 wherein said skip code comprises an entry in a lookup table referencing said previous block.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-02-28 | 2003-08-30 | 2004-02-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-02-28 | 2007-08-30 | 2008-02-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-02-28 | 2011-08-30 | 2012-02-29 | $7700.00 | Window Closed / Lapsed |