Image compression method to reduce pixel and texture memory requirements in graphics applications

• US 6,292,194 B1
• Filed: 07/29/1999
• Issued: 09/18/2001
• Est. Priority Date: 08/04/1995
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Powell, William Chambers III
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US09/365,605
• Time in Patent Office: 782 Days
• Field of Search: 345/419, 345/420, 345/421, 345/430, 345/433, 345/113, 345/114
• US Class Current: 345/582
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: G06T 13/80 2D [Two Dimensional] animation, e.g. using sprites
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 15/04 Texture mapping
• CPC Class Codes: G06T 15/60 Shadow generation

Abstract

A method for still image compression reduces pixel and texture memory requirements in graphics rendering and other applications. The image compression method divides an image into blocks and stores a quantization index (QIndex) for each block that reflects the level of quantization applied to the block. The QIndex is an index into a table of QFactors. The method performs an invertable transform on a block to generate coefficients for spatial frequency components in the block. It then quantizes coefficients in the block by dividing them by the QFactor in the table corresponding to the QIndex for the block. The QIndex enables the compression ratio of an image to vary across blocks and within each block. A control structure associated with the image stores a pointer to each of the blocks in an image. This control structure allows each block to be accessed and decompressed independently.

Claims

1. A method for still image compression comprising:

dividing an image into a plurality of blocks;

storing a QIndex for one or more of the blocks, where the QIndex is an index into a table of QFactors, such that each block has an associated QIndex;

independently compressing the blocks including;

a) performing an invertable transform on a block of the image to generate coefficients for spatial frequency components in the block; and

b) quantizing at least two of the coefficients by dividing coefficients by a QFactor in the table corresponding to the QIndex for the block; and

repeating the compressing step for subsequent blocks in the image.

2. The method of claim 1 further including:

storing a pointer to each of the blocks in a control structure associated with the image so that each of the blocks is randomly accessible and independently decompressable.

3. The method of claim 2 wherein the quantizing step is not performed on a DC coefficient of each block.

4. The method of claim 1 wherein the compressing step includes:

encoding the quantized coefficients using entropy encoding.

5. The method of claim 4 wherein the entropy coding comprises Huffman and run length encoding.

6. The method of claim 4 wherein the entropy coding comprises arithmetic encoding.

7. The method of claim 1 further including:

varying compression ratio within the image on a block by block basis by modifying the QIndex associated with two or more blocks.

8. The method of claim 1 further including:

varying compression ratio within a block by modifying the QIndex associated with the block for selected coefficients.

9. The method of claim 1 further including:

while compressing the image, to compress one or more blocks using a lossy compression method including steps a) and b), and selecting to compress one or more other blocks in the image using prediction and entropy coding, wherein the lossy compression method and the entropy coding are selected on a block by block basis.

10. The method of claim 1 wherein the invertable transform comprises a discrete cosine transform.

11. A method for still image compression comprising:

dividing an image into a plurality of blocks;

storing a QIndex for one or more of the blocks, where the QIndex is an index into a table of QFactors, such that each block has an associated QIndex;

deriving a QIndex for each block by modifying a chunk QIndex;

independently compressing one block at a time including;

a) performing a discrete cosine transform on a block of the image to generate coefficients for spatial frequency components in the block;

b) quantizing at least two of the coefficients by dividing coefficients, except for a DC coefficient, by a QFactor in the table corresponding to the QIndex for the block; and

c) encoding the quantized coefficients using Huffman and run length encoding; and

repeating the compressing step for subsequent blocks in the image.