Method and apparatus for video compression using block and wavelet techniques

• US 6,526,174 B1
• Filed: 02/28/2000
• Issued: 02/25/2003
• Est. Priority Date: 05/19/1994
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: NeXT Computer, Inc. (Apple Inc.)
• Inventors: Graffagnino, Peter N.
• Primary Examiner(s): Patel, Jayanti K.
• Application Number:
  US09/514,472
• Time in Patent Office: 1,093 Days
• Field of Search: 382/140, 382/232-238, 382/239-247, 341/107, 341/51, 341/55, 341/67, 345/589, 348/246, 348/396.1, 348/416.1, 356/388, 358/1-8, 375/240, 375/240.23, 712/300
• US Class Current: 382/236
• CPC Class Codes: H04N 19/10 using adaptive coding
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/593 involving spatial prediction techniques
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/645 by grouping of coefficients into blocks after the transform
• CPC Class Codes: H04N 19/90 using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals

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.

Claims

1. 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 said pixel of said plurality of pixels and a average luminance value of said block; and

,

encoding a quantized average color difference and a second plurality of frequency details of said block, wherein said second plurality of frequency details is less than or equal to a first plurality of frequency details of said block.

2. The method of claim 1 wherein said plurality of pixels comprises 2^k×

2^k pixels.

3. The method of claim 1 wherein k is equal to one.

4. The method of claim 1 wherein said first color space is a RGB color space.

5. 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.

6. The method of claim 5 wherein said second plurality of frequency details comprises said horizontal term and said vertical term.

7. The method of claim 1 wherein an average color difference and said first plurality of frequency details are quantized using a Lloyd-Max quantization.

8. The method of claim 7 wherein said Lloyd-Max quantization is dependent on a variance and a number of reconstruction levels.

9. The method of claim 1 wherein said quantized average color difference and said second plurality of frequency details are encoded using a Huffman coding.

10. 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.

11. The method of claim 10 wherein said skip code comprises an entry in a lookup table referencing said previous block.

12. An apparatus for compressing an image, said image comprising a plurality of blocks, comprising the steps of:

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 said pixel of said plurality of pixels and a average luminance value of said block; and

,

encoding means for variable length encoding of a quantized average color difference and a second plurality of frequency details of said block, wherein said second plurality of frequency details is less than or equal to a first plurality of frequency details of said block.

13. The apparatus of claim 12 wherein said plurality of pixels comprises 2^k×

2^k pixels.

14. The apparatus of claim 12 wherein k is equal to one.

15. The apparatus of claim 12 wherein a first color space is a RGB color space.

16. 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.

17. The apparatus of claim 16 wherein said second plurality of frequency details comprises said horizontal term and said vertical term.

18. The apparatus of claim 12 wherein a quantization means is a Lloyd-Max quantization means.

19. The apparatus of claim 18 wherein said Lloyd-Max quantization means is dependent on a variance and a number of reconstruction levels.

20. The apparatus of claim 12 wherein said quantized average color difference and said second plurality of frequency details are encoded using a Huffman coding.

21. The apparatus of claim 12 further comprising a skip code generation means coupled to a 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.

22. The method of claim 21 wherein said skip code comprises an entry in a lookup table referencing said previous block.

23. 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 said differential luminance is the difference in luminance value between each particular luminance value of each said pixel of said plurality of pixels and a average luminance value of said block; and

encoding a quantized average color difference and a second plurality of frequency details of said block, wherein said second plurality of frequency details is less than or equal to a first plurality of frequency details of said block.