Image analysis – Image compression or coding – Quantization
Reexamination Certificate
1998-10-27
2001-10-02
Tran, Phouc (Department: 2621)
Image analysis
Image compression or coding
Quantization
C382S232000
Reexamination Certificate
active
06298169
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to methods and apparatus for compressing and decompressing texture patterns, and more particularly, methods and apparatus for compressing and decompressing texture patterns by using a codebook technique.
BACKGROUND OF THE INVENTION
While, as will be better understood from the following description, the present invention was developed to improve the quality and compression ratios of compressed texture patterns while allowing somewhat random single pixel decompression, this invention may also find utility in other environments.
Texture pattern mapping is employed on high-end graphics workstations and rendering systems to increase the visual complexity of a scene without increasing its geometric complexity. Texture pattern mapping allows a rendering system to map an image onto simple scene geometry to make objects look much more complex or realistic than the underlying geometry. Recently, texture pattern mapping hardware has become available on lower-end workstations, personal computers, and home game systems.
One of the costs of texture pattern mapping is the memory space occupied by the texture patterns. For a particular scene, the memory space required by the texture patterns is dependent on the number of texture patterns and the size of each texture pattern. In some cases, the memory space occupied by the stored texture patterns may exceed in size the memory space occupied by the stored scene geometry.
In real-time texture mapping hardware systems, texture patterns arc generally placed in dedicated memory that can be accessed as quickly as pixels are generated. In some hardware systems, texture patterns are replicated in memory to facilitate fast parallel access. Because texture memory is a limited resource in these systems, it is consumed quickly. Although memory concerns are less severe for software rendering systems, since texture patterns are usually stored in main memory, there are advantages to conserving texture memory. Using less memory for texture patterns may yield caching benefits. One way to alleviate these memory limitations is to store compressed representations of texture patterns in memory. A modified renderer can then render directly from the compressed representation.
Vector quantization (VQ) supports fast decompression while achieving compression ratios of up to 35:1 with acceptable loss in the visual quality of the rendered scene. Processing time is increased only slightly, and incorporating VQ into hardware has very little impact on rendering performance. Unfortunately, VQ compressed texture patterns require large codebooks that take up expensive cache space.
The present invention is directed to overcoming the foregoing and other disadvantages associated with the compression and decompression of texture patterns. More specifically, the present invention is directed to methods and apparatus for providing a high speed, high image quality and high compression ratio texture pattern compression scheme.
SUMMARY OF THE INVENTION
In accordance with this invention, a method and apparatus for compressing and decompressing texture patterns using a predefined two or more stage codebook for storing texture blocks is provided. A texture block is an array of texels, wherein each texel is defined by its offset within the texture block. The method includes selecting a texture block in an uncompressed texture pattern and determining a distortion value for the selected texture block as compared to a texture block stored in the two or more stage codebook. If not below a predetermined threshold, the distortion value determining step is repeated for different texture blocks stored in the two or more stage codebook, until the determined distortion value is below the predetermined threshold. When the determined distortion value is below the predetermined threshold, the indices of the stored texture block in the two or more stage codebook are retrieved and stored.
In accordance with other aspects of this invention, the indices storing step further includes storing the retrieved indices in an index block within an index map, wherein the index blocks correspond to texture blocks in the texture pattern.
In accordance with still other aspects of this invention, the predefined two or more stage codebook is based on a representative texture pattern.
In accordance with yet other aspects of this invention a method for rendering an image with a compressed texture pattern, the compressed texture pattern including a stored index map that includes index blocks, wherein each index block includes codebook block indices to codebook blocks in a predefined two or more stage codebook and a vector component is prestored in each codebook block, is provided. The method of rendering includes determining the coordinates of a texel that is to be mapped to a pixel requested for rendering, determining the texture block and the texels offset within the determined texture block based on the determined texel coordinates, and determining the index block associated with the determined texture block. Then, the codebook block indices are retrieved from the determined index block and vector components from the two or more stage codebook are retrieved based on the retrieved codebook block indices. Next, a texture block vector is generated by adding the retrieved vector components and the texel's value is retrieved from the generated texture block vector based on the determined texel's offset with the texture block. These steps are repeated for all the texels located within the pixel to be rendered. Finally, the pixel is rendered based on the retrieved texel values of the texels located within the pixel.
As will be readily appreciated from the foregoing summary, the invention provides a method and apparatus for compressing and decompressing texture patterns. Because the present invention includes fixed index block (codeword) length and simple decompression properties similar to VQ, better image quality is possible at the same or better compression ratios than previous texture pattern compression techniques.
REFERENCES:
patent: 5892847 (1999-04-01), Johnson
patent: 6071193 (2000-06-01), Suzuoki
Alav{dot over (i)} Amör
Christensen O'Connor Johnson & Kindness PLLC
Microsoft Corporation
Tran Phouc
LandOfFree
Residual vector quantization for texture pattern 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 Residual vector quantization for texture pattern compression..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Residual vector quantization for texture pattern compression... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2579467