Image analysis – Image compression or coding – Quantization
Reexamination Certificate
2002-01-17
2004-08-10
Do, Anh Hong (Department: 2624)
Image analysis
Image compression or coding
Quantization
C382S232000, C725S146000
Reexamination Certificate
active
06775417
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to image processing, and more particularly to three-dimensional rendering using fixed-rate image compression.
2. Description of Related Art
Conventionally, generating images, such as realistic and animated graphics on a computing device, required tremendous memory bandwidth and processing power on a graphics system. Requirements for memory and processing power are particularly true when dealing with three-dimensional images. In order to reduce bandwidth and processing power requirements, various compression methods and systems have been developed including Entropy or lossless encoders, Discrete Cosine Transform (“DCT”) or JPEG type compressors, block truncation coding, and color cell compression. However, these methods and systems have numerous disadvantages.
Entropy or lossless encoders include Lempel-Ziv encoders which rely on predictability. For data compression using entropy encoders, a few bits are used to encode most commonly occurring symbols. In stationary systems where probabilities are fixed, entropy coding provides a lower bound for compression than can be achieved with a given alphabet of symbols. However, coding does not allow random access to any given symbol. Part of the compressed data preceding a symbol of interest must be first fetched and decompressed to decode the symbol, requiring considerable processing time and resources, as well as decreasing memory throughput. Another problem with existing Entropy methods and systems is that no guaranteed compression factor is provided. Thus, this type of encoding scheme is impractical where memory size is fixed.
Discrete Cosine Transform 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 least important information.
DCT, however, suffers from a number of shortcomings. One problem with DCT and JPEG-type compressors is a requirement of large 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 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, an image may be considerably distorted with a form of ringing around 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 further disadvantage with DCT and JPEG-type compression is the complexity and significant hardware cost for a compressor and decompressor (“CODEC”). Furthermore, high latency of a decompressor results in a large additional hardware cost for buffering throughout the system to compensate for the latency. Finally, DCT and JPEG-type compressors may not be able to compress a color keyed image.
Block truncation coding (“BTC”) and color cell compression (“CCC”) use a local one-bit quantizer on 4×4 pixel blocks. Compressed data for such a block consists of only two colors and 16-bits that indicate which of the two colors is assigned to each of 16 pixels. Decoding a BTC/CCC image consists of using a multiplexer with a look-up table so that once a 16-texel (or texture element, which is the smallest addressable unit of a texture map) 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 an associated bit from 16 decision bits.
Because the BTC/CCC methods quantize each block to just two color levels, significant image degradation may occur. Further, a two-bit variation of CCC stores the two colors as 8-bit indices into a 256-entry color lookup table. Thus, such pixel blocks cannot be decoded without fetching additional information which may consume additional memory bandwidth.
The BTC/CCC methods and systems can use a 3-bit per pixel scheme which stores 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 associated with BTC/CCC methods is a high degradation of image quality when used to compress images that use color keying to indicate transparent pixels.
Therefore, there is a need for a system and method that maximizes accuracy of compressed images while minimizing storage, memory bandwidth requirements, and decoding hardware complexities. There is a further need for compressing image data blocks into convenient sizes to maintain alignment for random access to any one or more pixels.
SUMMARY OF THE INVENTION
The present invention provides for fixed-rate block based image compression with inferred pixel values. An image processing system includes an image encoder engine and an image decoder engine. The image encoder engine includes an image decomposer, at least one block encoder, and an encoded image composer. The block decomposer decomposes an original image into a header and a plurality of blocks which are composed of a plurality of image elements or pixels. The block encoder subsequently processes each block. The block encoder includes a selection module, a codeword generation module, and a construction module. Specifically, the selection module computes a set of parameters from image data values of each set of image elements. The codeword generation module then generates codewords which are reference image data values such as colors or density values. Subsequently, the construction module uses the codewords to derive a set of quantized image data values. The construction module then maps each of the image element's original image data values with an index to one of the derived image data values. Finally, the codewords and indices are output as encoded image blocks.
Conversely, the image decoder engine includes an encoded image decomposer, at least one block decoder, and an image composer. The image decomposer takes the encoded image and decomposes the encoded image into a header and plurality of encoded image blocks. The block decoder uses the codewords in the encoded image blocks to generate a set of derived image data values. Subsequently, the block decoder maps the index values for each image element to one of the derived image data values. The image composer then reorders the decompressed image blocks in an output data file, which is forwarded to a display device.
REFERENCES:
patent: 4821208 (1989-04-01), Ryan et al.
patent: 4887151 (1989-12-01), Wataya
patent: 5734744 (1998-03-01), Wittenstein et al.
patent: 5742892 (1998-04-01), Chaddha
patent: 5748904 (1998-05-01), Huang et al.
patent: 5787192 (1998-07-01), Takaichi et al.
patent: 5822465 (1998-10-01), Normile et al.
patent: 5956425 (1999-09-01), Yoshida
patent: 5956431 (1999-09-01), Iourcha et al.
patent: 6075619 (2000-06-01), Iizuka
patent: 401284188 (1989-11-01), None
patent: 405216993 (1993-08-01), None
Feng et al., “A Dynamic Address Vector Quantization Based on Inter-Block and Inter-Color Correction for Color Image Coding,”IEEE International Conference on Acoustics, Speech and Signal Processing, vol. 3, May 1989, pp. 1755-1758.
Schilling et al., “Texram: A Smart Memory for Texturing,” IEEE Computer Graphics & Applications, May 1996, vol. 16, No. 3, pp. 9-19.
Knittel et al., “Hardware and Software for Superior Texture Performance,” In 10: Eurographics Hardware Workshop 1995, Maastricht, The Netherlands, Aug. 28-29, 1995, pp.
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-3359795