Image analysis – Color image processing – Compression of color images
Reexamination Certificate
2000-06-30
2004-11-16
Wu, Jingge (Department: 2621)
Image analysis
Color image processing
Compression of color images
Reexamination Certificate
active
06819793
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates generally to compressing computer graphics information. More particularly, the invention relates to a system and method for compressing computer graphics and textures for three dimensional computer graphics.
2. Background Information
In order to provide realistic computer graphics with smooth continuous rendering rates, it is desirable to have fast access to a large number of high-quality detailed textures. This goal is somewhat constrained by system memory and memory access bandwidth limitations. Texture compression can be used to significantly reduce the memory required to store textures and the bandwidth required to access textures from memory. Thus, four qualities are typically important for texture compression methods: (1) high compression ratio, (2) sufficient quality of decompressed images, (3) fast decoding, and (4) fast access to any texel in any order. Methods having these qualities allow more and higher-resolution textures to be incorporated into graphics, and provide a more realistic, immersing experience.
Block decomposition is one approach to texture compression. This approach is based on dividing an image into equally sized blocks (typically, 4×4 texels) and storing each of them in a uniform manner, so that after compression each block takes the same amount of memory. Thus, all blocks may be stored row by row, and an offset of a block containing any individual texel may be easily calculated. Three prior art block-decomposition methods will be discussed below: (1) Microsoft's Texture and Rendering Engine Compression (TREC), (2) S3 Texture Compression (S3TC), and (3) 3dfx's Texture Compression (FXT1).
Texture and Rendering Engine Compression (TREC)
Texture and Rendering Engine Compression (TREC) was developed by Microsoft Corporation. This technique is very similar to the JPEG standard since it is based on the two-dimensional discrete cosine transform (DCT) of 8×8 pixel blocks and quantization of coefficients. This approach provides variable compression ratios with satisfactory visual quality. However, implementing a hardware DCT decoder on a graphics accelerator board only for texture decompression is relatively expensive.
S3 Texture Compression (S3TC)
FIG. 1
shows a representative indexed texture block
110
for compression of a 4×4 texel texture block according to the S3TC approach. This approach stores two color values
115
for the texture block. A reconstructed color palette
120
, corresponding to indexed texture block
110
, contains the two stored color values
115
and two interpolated colors
140
. The interpolated color values
140
are determined by equations
160
. A two-bit index
170
(e.g., 00, 01, 10, 11) is assigned to each of the texels in block
110
, wherein each of the indices represents a color value in one of the four color palette entries
130
in the reconstructed color palette
120
.
Because colors are stored in RGB565 format, palette information requires 32 bits per each texture block (two colors times 16 bits per color). Indices take another 32 bits per block (16 texels times 2 bits per texel). Thus, the compressed texture block requires 8 bytes, while the original takes 48 considering RGB888. Consequently, S3TC scheme provides 6:1 compression ratio.
3dfx's Texture Compression
FXT1 may be considered an extension of the S3TC approach, since it separately encodes equally sized blocks of 4×8 texels by small local palettes (look-up tables). FXT1 has four modifications, however all the modifications have a common approach: (1) some basic colors (RGB555) are stored in a block, (2) a local palette (or palettes) is generated by interpolation of basic colors, and (3) each texel is represented by index of the most appropriate color from the corresponding look-up table.
FIG. 2
briefly presents the FXT
1
encoding parameters for different modifications. For CC_HI scheme, two basic RGB555 colors, which are stored in a block, are used for interpolating seven RGB888 look-up table entries, while the eighth entry is defined transparent. Thus, three bits are required for each texel. CC_CHROMA refers to storing four colors, which are used with no change as the four-entry palette. CC_MIXED is very similar to the S3TC approach, since two four-entry palettes are generated, each by interpolating between two colors (therefore, four colors are stored for a 4×8 texel block). Then, two sub-blocks of 4×4 texels are encoded separately by their own palettes. CC_ALPHA creates an aggregate of two 4×4 texel texture blocks and stores three colors for that aggregate. The first and second colors are used as the primary colors of the left 4×4 texel texture block and the second and third colors are used as the primary colors of the right 4×4 texel texture block. Two additional colors are created for each texture block by interpolating between the two primary colors for that block. During compression, FXT
1
encoder produces all representations of each 4×8 block of texels, chooses the one that introduces the least error, and stores the corresponding data in the resulting data stream.
Thus, S3TC represents each block of 4×4 texels by 8 bytes (4 for colors +4 for indices), while FXT1 uses a 16-byte data chunk for each 4×8 texel block. The compression ratio, provided by these techniques, is 6:1 for TrueColor 24 bpp images, and 8:1 for 32 bpp images.
Quality Degradation of Compressed Textures
One major problem with current texture compression methods including S3TC and FXT
1
is an inadequate balance between visual quality and compression ratio. In the prior art, high compression ratio is achieved by serious reduction of color data available for texel representation. In general, the methods described above use interpolation to determine some colors, and the interpolated colors lack diversity. As a result, less independent colors are available to represent the image, and this may introduce perceptible quality degradation in some cases.
As an example, consider an image having three colors that do not belong to one line in an RGB cube. For instance, it may be red, green and blue. If pixels of these colors appear in one block simultaneously, many prior art methods will not be able to reproduce them without visual degradation by interpolation of any two. It will either discard less frequent color or construct a line (in an RGB cube) being less distant from all existing points. This will often introduce perceptible quality degradation effects as shown in FIG.
3
.
FIG. 3
shows an original image
310
where shades of gray are used for representing a red flower
320
with a blue core
330
. As shown for the S3TC method of compression
340
, compression and reconstruction using S3TC resulted in regions with quality degradation 360 because only two basic independent colors were available.
REFERENCES:
patent: 5327509 (1994-07-01), Rich
patent: 5548709 (1996-08-01), Hannah et al.
patent: 5751292 (1998-05-01), Emmot
patent: 5808621 (1998-09-01), Sundaresan
patent: 5822452 (1998-10-01), Tarolli et al.
patent: 5845013 (1998-12-01), Bouchard et al.
patent: 5852443 (1998-12-01), Kenworthy
patent: 5943058 (1999-08-01), Nagy
Cross, “DXTn Texture Compression” at http://www.cdmag.com/articles/021.068/dxt_feature.html, Jul. 1999.*
Ivanov, “Texture Compression Survey” at http://www.fit.com.ru/Surveys/TextureCompression/index.html. Apr. 1999.*
J. Puzicha, M. Held, J. Ketterer, J. Buhmann, D. Fellner. On Spatial Quantization of Color Images. Technical Report IAI-TR-98-1, University of Bonn, 1998.
J.M. Buhmann, D. Fellner, M. Held, J. Ketterer and J. Puzicha. Dithered Color Quantization. Proceedings of EUROGRAPHICS, vol. 17, No. 3, 1998.
FXT1: White paper. 3dfx Interactive, Inc. Retrieved from the Internet at http://wwwdev.3dfx.com/fxt1/fxt1whitepaper.pdf. pp. 1-7.
Texture and Rendering Engine Compression (TREC): White paper. Microsoft Corporation. Retrieved from the internet at http://www.microsotf.com/hwdevdes/WHNTREC.htm. pp. 1
Ivanov Denis
Kuzmin Yevgeniy
Reshetov Alexander
Blakely , Sokoloff, Taylor & Zafman LLP
Intel Corporation
Wu Jingge
LandOfFree
Color distribution for texture and image compression does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Color distribution for texture and image compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Color distribution for texture and image compression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3343799