Image analysis – Color image processing – Compression of color images
Reexamination Certificate
1999-12-10
2004-01-27
Boudreau, Leo (Department: 2721)
Image analysis
Color image processing
Compression of color images
C358S539000
Reexamination Certificate
active
06683979
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of computer graphics. More specifically, the present invention relates to a method of and apparatus for compressing and uncompressing (or decompressing) image data in a computer system.
2. Related Art
Computer graphics is used in a wide variety of applications, such as in business, science, animation, simulation, computer-aided design, process control, electronic publishing, gaming, medical diagnosis, etc. In those applications, three-dimensional (3D) objects are displayed on a computer screen by using a number of polygons to represent the three-dimensional objects. In order to portray a more realistic real-world representation, texture mapping is often applied. Texture mapping refers to techniques for using two-dimensional (2D) or three-dimensional (3D) texture images, or texture maps, for adding surface details to areas or surfaces of these 3D graphical objects. For example, given a featureless solid cube and a texture map defining a wood grain pattern, texture mapping techniques may be used to map the wood grain pattern onto the cube. The resulting image is that of a cube that appears to be made of wood. In another example, vegetation and trees can be added by texture mapping to an otherwise barren terrain model in order to portray a landscape filled with vegetation and trees.
In computer systems having dedicated graphics hardware, images for use in texture mapping are typically stored in memory in the form of a collection of tiles. These tiles are addressed and managed as a virtually contiguous region of address space by a two-dimensional index (S, T). In other words, this memory management scheme treats a texture map as an array of small, contiguous tiles each including a matrix of texels. Thereby, memory management issues, such as caching, virtual-to-physical mapping, swapping, etc. are more easily executed.
In order to utilize computer resources more efficiently, computer graphics systems typically include a graphics co-processor for offloading processing burdens from the CPU of the computer system, and a texture memory for storing texture data. Moreover, in order to further accelerate the texture mapping process, a special cache memory, also known as a texture cache, may also be implemented in the computer graphics systems for providing faster access to and temporary storage of frequently used tiles of texture data. In these computer systems, the texture data is frequently transferred between these memories. The bandwidth for transferring texture data between these memories, thus, becomes a critical factor in determining the texture mapping performance of such systems. Additionally, the memories themselves are valuable resources. Therefore, it would be advantageous to store and transfer texture data in a compressed format.
The need for a method of compressing texture images also arises in computer systems without a dedicated texture cache memory. In those systems, texture images are rendered directly from the system memory. That method of rendering, however, places significant burdens on system memory bandwidth. In addition to passing texture data and other image data, the memory bus must also handle access to the system memory by the operating system and the application programs. Therefore, in order to alleviate this problem, it is would also be advantageous to store and transfer compressed texture data such that the burden on system memory bandwidth is minimized.
A further need for a method of compressing images arises in network systems. Often, a computer network has only one or at most a few network graphic machines that are capable of rendering complex images, such as three-dimensional scientific graphs or engineering drawings. It would be advantageous if these complex images could be rendered on a network graphics machine and sent in a compressed data format over the network to a user for real-time display on the users personal computer.
Conventional methods of compressing image data, however, are not suitable for compressing complex or texture images. For instance, these conventional methods introduce significant amounts of visual artifacts, such as color “jaggies,” in the image data. These visual artifacts, while hardly noticeable in non-3D applications, are magnified when conventionally compressed texture images are used in texture mapping. Further, conventional compression algorithms, such as the color cell compression (CCC) algorithm, make use of a color look-up table (LUT) for storing representative colors of the image. Because color LUTs can be quite large, and given the limited system memory bandwidth, the overall performance of the texture mapping process would be significantly impeded if conventional algorithms such as the CCC algorithm are used to compress texture data.
Other well known compression schemes such as the JPEG or MPEG compression schemes produce good quality compression but are mathematically complex and require considerable amounts of hardware to implement. This high hardware cost makes these schemes unsuitable for texture compression. For the network transport case, where the implementation can be in software, these other schemes are too slow to maintain interactive frame rates.
Therefore, what is needed is a method of and apparatus for compressing and uncompressing color images with minimal information loss. What is also needed is a method of and apparatus for compressing and uncompressing color images without color look-up tables. What is yet further needed is a method of and apparatus for compressing and uncompressing texture data to be used in texture mapping. For the network transfer case, what is needed is a method that can be implemented in software and still maintain interactive frame rates.
SUMMARY OF THE INVENTION
The present invention provides for a method of and apparatus for compressing and uncompressing image data. According to one embodiment of the present invention, the method of compressing a color cell comprises the steps of: defining at least four luminance levels of the color cell; generating at least two bitmasks for the color cell, generating a first base color representative of pixels associated with a first one of the luminance levels; generating a second base color representative of pixels associated with a second one of the luminance levels; and storing the bitmasks in association with the first base color and the second base color. According to the present embodiment, the bitmasks each includes a plurality of entries each corresponding to a respective one of the pixels. Further, each entry is for storing data that identifies the luminance levels associated with the pixels. The present invention is particularly applicable to compress texture data such that the texture data can be more efficiently cached and moved during texture mapping.
In accordance with the present embodiment, the step of defining the luminance levels includes the steps of: calculating a mean luminance value for all pixels within the color cell; calculating an upper-mean luminance value for pixels having luminance values higher than the mean luminance value; and calculating a lower-mean luminance value for pixels having luminance values lower than the mean luminance value. In the present embodiment, the mean luminance value, the upper-mean luminance value, and the lower-mean luminance value partition the plurality of pixels into four different luminance levels including a highest luminance level, a high luminance level, a low luminance level, and a lowest luminance level. According to one embodiment, the first base color is computed by averaging the color values of all the pixels associated with the highest luminance level, and the second average color is computed by averaging the color values of all the pixels associated with the lowest luminance level.
In a second embodiment of the present invention, the method of compressing a color cell comprises the steps of: determining a luminance value (Y) for each pixel of the color cell; selecting a maxi
Schafer Marc A.
Walker Christopher A.
Boudreau Leo
Sherali Ishrat
Silicon Graphics Inc.
Sterne Kessler Goldstein & Fox P.L.L.C.
LandOfFree
Image data compression and decompression does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image data compression and decompression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image data compression and decompression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3213594