Image analysis – Color image processing – Compression of color images
Reexamination Certificate
1999-11-17
2004-01-27
Do, Anh Hong (Department: 2624)
Image analysis
Color image processing
Compression of color images
C382S232000, C725S146000
Reexamination Certificate
active
06683978
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to image processing systems, and more specifically, to three-dimensional rendering systems using fixed-rate image compression for textures.
2. Description of the Related Art
The art of generating images, such as realistic or animated graphics on a computer is known. To generate such images requires tremendous memory bandwidth and processing power on a graphics subsystem. To reduce the bandwidth and processing power requirements, various compression methods and systems were developed. These methods and systems included Entropy or lossless encoders, discrete cosine transform or JPEG type compressors, block truncation coding, color cell compression, and others. Each of these methods and systems, however, have numerous drawbacks.
Entropy or lossless encoders include Lempel-Ziv encoders and are used for many different purposes. Entropy coding relies on predictability. For data compression using Entropy encoders, a few bits are used to encode the most commonly occurring symbols. In stationary systems where the probabilities are fixed, Entropy coding provides a lower bound for the compression than can be achieved with a given alphabet of symbols. A problem with Entropy coding is that it does not allow random access to any given symbol. The part of the compressed data preceding a symbol of interest must be first fetched and decompressed to decode the symbol which takes considerable processing time and resources as well as decreasing memory throughput. Another problem with existing Entropy methods and systems is that they do not provide any guaranteed compression factor which makes this type of encoding scheme impractical where the memory size is fixed.
Discrete Cosine Transform (“DCT”) or JPEG-type compressors, allow users to select a level of image quality. With DCT, uncorrelated coefficients are produced so that each coefficient can be treated independently without loss of compression efficiency. The DCT coefficients can be quantized using visually-weighted quantization values which selectively discard the least important information.
DCT, however, suffers from a number of shortcomings. One problem with DCT and JPEG-type compressors is that they require usually bigger blocks of pixels, typically 8×8 or 16×16 pixels, as a minimally accessible unit in order to obtain a reasonable compression factor and quality. Access to a very small area, or even a single pixel involves fetching a large quantity of compressed data, thus requiring increased processor power and memory bandwidth. A second problem with DCT and JPEG-type compressors is that the compression factor is variable, therefore requiring a complicated memory management system that, in turn, requires greater processor resources. A third problem with DCT and JPEG-type compression is that using a large compression factor significantly degrades image quality. For example, the image may be considerably distorted with a form of a ringing around the edges in the image as well as noticeable color shifts in areas of the image. Neither artifact can be removed with subsequent low-pass filtering.
A fourth problem with DCT and JPEG-type compression is that such a decompressor is complex and has a significant associated hardware cost. Further, the high latency of the decompressor results in a large additional hardware cost for buffering throughout the system to compensate for the latency. Finally, a fifth problem with DCT and JPEG-type compressors is that it is not clear whether a color keyed image can be compressed with such a method and system.
Block truncation coding (“BTC”) and color cell compression (“CCC”) use a local one-bit quantizer on 4×4 pixel blocks. The compressed data for such a block consists of only two colors and 16-bits that indicate which one of the two colors is assigned to each of the 16 pixels. Decoding a BTC/CCC image consists of using a multiplexer with a look-up table so that once a 16-texel-block (32-bits) is retrieved from memory, the individual pixels are decoded by looking up the two possible colors for that block and selecting the color according to the associated bit from the 16 decision bits.
The BTC/CCC methods quantize each block to just two color levels resulting in significant image degradation. Further, a two-bit variation of CCC stores the two colors as eight-bit indices into a 256-entry color lookup table. Thus, such pixel blocks cannot be decoded without fetching additional information that can consume additional memory bandwidth.
The BTC/CCC methods and systems can use a three-bit per pixel scheme which store the two colors as 16-bit values (not indices into a table) resulting in pixel blocks of six bytes. Fetching such units, however, decreases system performance because of additional overhead due to memory misalignment. Another problem with BTC/CCC is that when it is used to compress images that use color keying to indicate transparent pixels, there will be a high degradation of image quality.
Therefore, there is a need for a method and system that maximizes the accuracy of compressed images while minimizing storage, memory bandwidth requirements, and decoding hardware complexities, while also compressing image data blocks into convenient sizes to maintain alignment for random access to any one or more pixels.
SUMMARY OF THE INVENTION
An image processing system includes an image encoder system and an 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 image blocks, each having a plurality of pixel values (e.g. colors) or equivalent color points. Each image block is then processed by the block encoder. Specifically, the color quantizer computes some number of base points, or codewords, that serve as reference pixel values, such as colors, from which computed or quantized pixel values are derived. The bitmap construction module then maps at least one pixel value in the image block to one of the computed or quantized colors or one of the codewords. The codewords and bitmap are output as encoded image blocks.
The decoder system includes a block decoder having one or more decoder units and an output selector. The block decoder may also include a block type detector for determining the block type of an image block. The block type determines the number of computed colors to use for mapping each pixel color from an image block. Using the codewords of the encoded data blocks, the comparator and the decoder units determine the computed colors for the encoded image block and map each pixel to one of the computed 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.
The present invention also includes a method of compressing an original image block having a set of original colors. The method includes: computing a set of codewords from the set of original colors; computing a set of computed colors using the set of codewords; and mapping each original color to one of the computed colors or one of the codewords to produce an index for each original color.
The compressed or encoded image block, which has a first set of indices and a set of codewords, where a set is equal to or greater than one, is decoded by: computing at least one computed color using the set of codewords; and mapping an index within the first set of indices to one of the computed colors or one of the codewords.
Those of ordinary skill in the art will readily recognize that the present invention may be practiced using any general purpose computer system, such as the computer system described below, or any “hardwired” device specifically designed to perform the method, such as but not limited to devices implemented using ASIC or FPGA technology and the like.
REFERENCES:
patent: 4821208 (1989-04-01),
Hong Zhou
Iourcha Konstantine I.
Nayak Krishna S.
Carr & Ferrell LLP
Do Anh Hong
S3 Graphics Co., Ltd.
LandOfFree
Fixed-rate block-based image compression with inferred pixel... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fixed-rate block-based image compression with inferred pixel..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fixed-rate block-based image compression with inferred pixel... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3258677