Image analysis – Color image processing – Compression of color images
Reexamination Certificate
1997-04-15
2001-07-10
Bella, Matthew C. (Department: 2621)
Image analysis
Color image processing
Compression of color images
C382S194000, C382S233000, C382S245000, C358S296000
Reexamination Certificate
active
06259810
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to video image data, and more particularly to a method and system for rapidly and efficiently decoding stored video information.
BACKGROUND OF THE INVENTION
In one well-known color scheme, each pixel in an image is represented by a single byte having a value corresponding to the pixel's color. The value of the byte serves as an index to a 256-byte color table, or palette. The palette is a 256 by 3 byte array, with each indexed entry in the palette having a first byte specifying a red level, a second byte specifying a green level and a third byte specifying a blue level. In another well-known scheme referred to as 24-bit true color, each pixel has four bytes directly stored therefor, one red, one green, one blue and one for various flags. In either scheme, the image may be stored as an array of such bytes.
The byte arrays representing video images are often compressed to save both storage space and the amount of time required to transfer the data from one medium (e.g., CD-ROM) to another (e.g., random access memory). For example, with the 256-byte color scheme, existing image data compression techniques utilize a two-byte format, with a first byte representing a run length of contiguous pixels of one color and the second byte identifying that color. This compression scheme works well with images having long runs (up to 256 pixels) of pixels of the same color. However, where there are few runs of constant color, the encoding scheme approaches two bytes per pixel, which is worse than leaving the data uncompressed with one byte per pixel.
Other types of compression schemes are applied to previously fixed descriptions of the pixel data. One such technique, known as LZW, (which stores files with a “.GIF” extension), examines fixed image data (or other types of data) for patterns of replicated data. LZW then encodes the data as a pattern length followed by the data in that pattern, and the compressed image data includes references to the patterns. As can be appreciated, such a compression technique functions well when there are a few patterns repeated many times, but is often not very useful for compressing many other types of images.
Another compression scheme applied to fixed image data is known as JPEG, which first breaks an image into rectangular portions, and then applies algorithms to reduce the amount of data required to describe those portions. Significantly, JPEG image compression is not lossless, that is, the pixel information cannot be precisely recreated from the compressed data. In short, existing image data-compression schemes have a number of drawbacks associated therewith, and no one compression scheme is optimal for every image.
Moreover, consideration must be given to the decompression of the image, particularly given the likelihood that an end-user decompressing a compressed image has a less-powerful computer than the manufacturer or the like that originally compressed the image. In general, as the compression scheme increases in complexity, the amount of compression achieved is increased. However, often times the more complex the compression scheme, the greater the cost of decompression in terms of time and/or processing power required to decode the image.
OBJECTS AND SUMMARY OF THE INVENTION
Accordingly, it is an object of the invention to provide a method and system for reducing the amount of data required to encode an image while providing for efficient decoding of the encoded image.
It is a related object to provide such a method and system that encodes and decodes an image without any loss of data.
Another object is to provide a method and system of the above kind that redefines the pixel description data as a function of the image data.
Yet another object is to provide a compression scheme as characterized above that facilitates efficient and rapid decompression.
Another object is to provide a method and system for decoding that can be incorporated into the block transfer routines of an operating system or the like.
Briefly, the present invention provides a method and system for decoding compressed data into an image of pixels. The compressed data is arranged such that each row of pixels in the image to be decoded has a distinct set of data corresponding thereto in the compressed data, and further includes a pointer to each distinct set of data. The rows of pixels to be decoded into the image are determined, and for each row of pixels determined, the pointer to the distinct set of data therefor is located, a destination memory location corresponding to the row of pixels to be decoded is determined, the distinct set of data is decoded into actual pixel data, and the actual pixel data is written into the determined destination memory location.
Other objects and advantages will become apparent from the following detailed description when taken in conjunction with the drawings, in which:
REFERENCES:
patent: 5064144 (1991-11-01), Edelson et al.
patent: 5065144 (1991-11-01), Edelson et al.
patent: 5218431 (1993-06-01), Gleicher et al.
patent: 5295203 (1994-03-01), Krause et al.
patent: 5313534 (1994-05-01), Burel
patent: 5339164 (1994-08-01), Lim
patent: 5426379 (1995-06-01), Trimberger
patent: 5497434 (1996-03-01), Wilson
patent: 5572235 (1996-11-01), Mical et al.
patent: 5659631 (1997-08-01), Gormish et al.
patent: 5684895 (1997-11-01), Harrington
patent: 5727090 (1998-03-01), Yellin
patent: 5734744 (1998-03-01), Wittenstein et al.
patent: 5768481 (1998-06-01), Chan et al.
patent: 5777749 (1998-07-01), Noda et al.
Gill John W.
Johnson Bruce A.
Bella Matthew C.
Chawans Sheela
Michalik & Wylie PLLC
Microsoft Corporation
LandOfFree
Method and system of decoding compressed image data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system of decoding compressed image data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system of decoding compressed image data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2529118