System and method for fixed-rate block-based image compression with inferred pixel values

• US 5,956,431 A
• Filed: 10/02/1997
• Issued: 09/21/1999
• Est. Priority Date: 10/02/1997
• Status: Expired due to Term

• Current Assignee: S3 Graphics Co., Ltd. (HTC Corporation)
• Original Assignee: S3 Inc. (SONICblue Incorporated)
• Inventors: Hong, Zhou, Iourcha, Konstantine I., Nayak, Krishna S.
• Primary Examiner(s): Coles, Edward L.
• Assistant Examiner(s): NGUYEN, JIMMY D
• Application Number:
  US08/942,860
• Time in Patent Office: 719 Days
• Field of Search: 382/253, 382/166, 382/233, 382/232, 382/236, 382/238, 382/239, 358/539, 358/425, 358/426, 358/427, 358/430
• US Class Current: 382/253
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

An image processing system includes an image encoder system and a image decoder system that are coupled together. The image encoder system includes a block decomposer and a block encoder that are coupled together. The block encoder includes a color quantizer and a bitmap construction module. The block decomposer breaks an original image into blocks. Each block is then processed by the block encoder. Specifically, the color quantizer selects some number of base points, or codewords, that serve as reference pixel values, such as colors, from which quantized pixel values are derived. The bitmap construction module then maps each pixel colors to one of the derived quantized colors. The codewords and bitmap are output as encoded image blocks. The decoder system includes a block decoder. The block decoder includes a block type detector, one or more decoder units, and an output selector. Using the codewords of the encoded data blocks, the comparator and the decoder units determine the quantized colors for the encoded image block and map each pixel to one of the quantized colors. The output selector outputs the appropriate color, which is ordered in an image composer with the other decoded blocks to output an image representative of the original image. A method for encoding an original image and for decoding the encoded image to generate a representation of the original image is also disclosed.

Claims

1. In an image processing system, a system for encoding an image, comprising:

an image decomposer, coupled to receive an image, for breaking the image into one or more image blocks;

at least one block encoder, each block encoder coupled to the image decomposer, for compressing each image block to generate an encoded image block; and

an encoded image composer, coupled to each block encoder, for ordering the encoded image blocks into a data file,

wherein each block encoder includes a color quantizer, coupled to receive an image block identifiable as a block type, for generating a first and a second codeword from which at least one quantized color is derived, the color quantizer comprising a curve selection module, coupled to the block type, for computing the optimal analog curve for the block type, the first codeword and the second codeword derived from the analog curve.

2. The system for encoding in claim 1, further comprising a header converter, coupled to the image decomposer and the encoded image composer, for receiving a header from the image, modifying the header, and outputting the modified header with the data file.

3. The system for encoding in claim 1, wherein each block encoder further comprises:

a bitmap construction module, coupled to the color quantizer, for mapping the colors of an image block to one of the at least one quantized colors.

4. The system for encoding in claim 1, wherein the color quantizer further comprises:

a block type module, coupled to receive the image block, for selecting the identifiable block type for the image block; and

a codeword generation module, coupled to the curve selection module, for generating the first codeword and the second codeword from the analog curve.

5. In an image processing system, a system for decoding a compressed image, comprising:

an encoded image decomposer, coupled to receive encoded image data file having at least one compressed image block, for breaking the encoded image data file into individual compressed image blocks, each compressed image block having at least one associated codeword, each codeword generated through selecting a block type for an original image block comprising the compressed image block, computing an analog curve for the block type, selecting a partition along the analog curve for the computed analog curve, and computing the set of codewords for the partition;

at least one block decoder, coupled to the encoded image decomposer, for decompressing the compressed image blocks; and

an image composer, coupled to each block decoder, for ordering the decompressed image blocks in an output file.

6. The system for decoding in claim 5, further comprising a header converter, coupled to the encoded image decomposer and the image composer, for receiving a modified header associated with the encoded image data file, generating an output header, and outputting the output header with the output file.

7. The system for decoding in claim 6, wherein each block decoder further comprises:

a block type detector, coupled to the encoded image decomposer, for selecting a block type for each compressed image block;

a first and a second decoder unit, each decoder unit coupled to the block type detector, for decompressing each compressed image block; and

an output selector, coupled to the block type detector and each decoder unit, for outputting the image block from the decoder unit in response to the block type selected by the block type detector.

8. In an image processing system a system for encoding and decoding an image, comprising:

an image encoder system, having

a block decomposer for breaking the image into a fixed number of image blocks, each image block having a fixed number of pixels,

at least one block encoder, each coupled to the block decomposer, for selecting at least one codeword for each block from which M quantized colors are derived, mapping each pixel for each block to one of the M quantized colors, and outputting the codewords and mapped pixels for each block as an encoded image block, where M is an integer value, and

an encoded image composer, coupled to each block encoder, for ordering each encoded image block in an encoded data file,

wherein each block encoder includes a color quantizer for examining the image block, including a block type, and generating the at least one codeword from which the M quantized colors are derived, the color quantizer comprising a curve selection module, coupled to receive the block type, for selecting an analog curve in a color space from the selected color set, the at least one codeword derived from the analog curve; and

an image decoder system, coupled to the image encoder system, having

an encoded image decomposer, coupled to receive the encoded data file, for decomposing, the encoded data file into the encoded image blocks;

at least one block decoder, each coupled to the encoded image decomposer, for decoding each encoded image block using the codewords to map each pixel of the encoded block to one of the M quantized colors to produce a decoded image block, and

an image composer, coupled to each block decoder, for ordering the decoded image blocks in an output file.

9. The image processing system in claim 8, wherein each block encoder further comprises:

a bitmap construction module, coupled to the codeword selection module, for mapping each pixel of the image block to one of the M quantized colors.

10. The image processing system in claim 9, wherein the color quantizer further comprises:

a block type module, coupled to receive the image blocks, for selecting the block type for each examined image block, the block type representing a predefined color set; and

a codeword generation module, coupled to the curve selection module, for providing the at least one codeword from the analog curve.

11. The image processing system in claim 8, wherein each block decoder comprises:

a block type detector, coupled to receive the encoded data block, for selecting the block type for decoding the encoded image block; and

a first decoder unit and a second decoder unit, each coupled to the block type detector, each decoder unit decoding the encoded image block to restore one of the M quantized colors derived from the at least one codeword.

12. The image processing system in claim 11, wherein each block decoder further comprises an output selector, the output selector coupled to each decoder unit and the block type detector, for outputting the restored color of the M quantized colors from one of the decoder units in response to the block type selected for the encoded image block.

13. In an image processing system, a method for generating an encoded image of an original image having a header, comprising:

converting the header to a modified header;

decomposing the original image into image blocks;

encoding each image block to generate an encoded image block for each image block, including selecting a set of codewords, the set having at least one codeword, for representing a property value for an image block selecting at least one block type, the selecting the set of codewords further including computing an optimal analog curve for each selected block type, selecting at least one partition along the analog curve for each computed analog curve, and computing the set of codewords for each selected partition; and

composing the modified header and each encoded image block in a file to generate the encoded image.

14. The method for generating an encoded image in claim 13, wherein encoding each image block further comprises:

quantizing colors for an image block for representing the image block, each quantized color derived from the set of codewords.

15. The method for generating an encoded image in claim 14, wherein selecting the set of codewords further comprises:

computing an error for each computed set of codewords; and

outputting the block type and set of codewords producing the minimum computed error for each computed set of codewords.

16. In an image processing system, a method for generating an original image from an encoded image including a modified header and at least one encoded image block, comprising:

receiving the encoded image data;

decomposing the encoded image into the modified header and the individual encoded image blocks;

reading the modified header to generate an output header;

decoding each individual encoded image block to generate a decoded image block, including receiving each individual encoded image block, including a plurality of codewords, and a bitmap of at least one pixel, the plurality of codewords derived through selecting a block type for an original image block of the encoded image block, computing an analog curve for the block type, selecting a partition along the analog curve for the computed analog curve, and computing the plurality of codewords for the partition; and

composing the output header and the individual decoded image blocks to generate an output file of the original image.

17. The method for generating an original image in claim 16, wherein the decoding each individual image block further comprises:

detecting the block type for the encoded image block to select a decoder unit;

calculating at least one quantized color level for the encoded image block using the set of codewords; and

mapping each pixel of the bitmap to one of the calculated quantized color levels for the encoded image block.

18. In an image processing system, a method for compressing an original image and generating an output image representing the original image from the compressed original image, comprising:

breaking the original image into a fixed number of image blocks, each image block having an associated color and a fixed number of pixels;

selecting a set of codewords, the set having at least one codeword, for each image block to represent colors in a color space, including selecting at least one block type for each image block, computing an optimal analog curve for each selected block type, selecting at least one partition along the analog curve for each computed analog curve, and computing the set of codewords for each selected partition;

quantizing colors for each image block, the quantized colors derived from the set of codewords;

mapping each pixel to one of the quantized colors to produce a bitmap;

generating an encoded image block for each image block, each encoded image block comprising the set of codewords and the bitmap;

composing the each encoded image block into an encoded image data file;

receiving the encoded image data file at a decoder system;

breaking the encoded image data file into the encoded image blocks;

decoding each encoded image block using the set of codewords to map each pixel of each encoded image block with a restored quantized color; and

composing the restored quantized colors in an output file to output an image representing the original image.

19. The method for compressing an original image and generating an output image representing the original image from the compressed original image in claim 18, wherein the selecting the set of codewords further comprises:

computing an error for each of the sets of codewords; and

outputting the block type and the set of codewords producing the minimum computed error.

20. The method for compressing an original image and generating an output image representing the original image from the compressed original image in claim 18, wherein decoding each encoded image block further comprises:

receiving the individual encoded image block, including the set of codewords, and a bitmap having at least one pixel;

detecting the block type for the encoded image block to select a decoder unit;

calculating the at least one quantized color level for the encoded image block using the set of codewords; and

mapping each pixel of the bitmap to one of the calculated quantized colors for the encoded image block.

21. A system for processing any identified pixel from an encoded image data file having header information, including at least one codeword derived through computation of an analog curve from a selected original image block, and an encoded image block portion including at least one encoded image block derived from an original image block, the system comprising:

a block address computation module, coupled to receive each codeword from the header information, for computing an address of an encoded image block having the identified pixel;

a block fetching module, coupled to receive the encoded image block portion and the computed address, for fetching the encoded image block having the identified pixel; and

a block decoder, coupled to receive the fetched encoded image block, for decoding the image block to generate a quantized color associated with the identified pixel.

22. In an image processing system, a method for processing any identified pixel of an encoded image data file having a header, including at least one codeword derived through calculation of an analog curve associated with an original image block, and an encoded image block portion including at least one encoded image block associated with an original image block, the method comprising:

computing an address for an encoded image block having the identified pixel, the address computed from the at least one codeword for the encoded image block;

fetching the encoded image block using the computed address;

computing quantized color levels for the fetched encoded image block; and

selecting a color of the identified pixel from the quantized color levels to output.