Method and system of decoding compressed image data

• US 6,259,810 B1
• Filed: 04/15/1997
• Issued: 07/10/2001
• Est. Priority Date: 04/15/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Johnson, Bruce A., Gill, John W.
• Primary Examiner(s): Bella, Matthew C.
• Assistant Examiner(s): CHAWAN, SHEELA C
• Application Number:
  US08/838,186
• Time in Patent Office: 1,547 Days
• Field of Search: 382/166, 382/194, 382/221, 382/232, 382/233, 382/234, 382/235, 382/245, 382/253, 358/426, 358/261.4, 345/431, 345/430, 345/428
• US Class Current: 382/166
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding

Abstract

A method and system of encoding and decoding image data in images having less than 128 distinct colors. Eight bit data bytes representing the color of each pixel data are re-indexed for each pixel to seven or less bits, and a sub-palette stores the relationship between the re-indexed colors and the original eight-bit color values. The remaining bits in the byte store run lengths of pixels that have contiguous colors. Further data compression is achieved by grouping pixels into rows, eliminating any duplicate rows and identifying the pixel data by a series of row pointers. Still further compression is accomplished by dropping representations of transparent pixels from the end of rows and representing a number of transparent pixels at the beginning of rows with a single byte. The compressed data is efficiently decoded using the row pointers to expedite vertical clipping of the image and adjusting horizontal clipping for leading and trailing transparent pixels.

Claims

1. A method of decoding a set of compressed data representing an original image including a plurality of rows of pixels into an image of pixels, comprising, accessing the set of compressed data to locate a row pointer, each row pointer in the compressed data pointing to a set of source data within the set of compressed data, the set of source data representing at least part of a row of pixels in the original image data, determining rows of pixels to be decoded into the image, and for each row of pixels determined, decoding the compressed data into a representation of the original image by locating the row pointer to the set of source data, locating the set of source data pointed to by the row pointer, determining a destination memory location corresponding to said row of pixels to be decoded, decoding the set of source data into actual pixel data, and writing the actual pixel data into the determined destination memory location.

2. The method of claim 1 wherein less rows are decoded than sets of source data are stored therefor in the compressed data, and wherein determining the rows of pixels to be decoded into the image includes selecting the first row and the last row to be decoded.

3. The method of claim 2 wherein for each row of pixels determined, decoding the compressed data by locating the row pointer includes locating the row pointer for the set of source data from the first row through the last row.

4. The method of claim 1 wherein the set of source data for each row includes a value indicative of a number of transparent pixels at the beginning of each row of pixels, and wherein determining a destination memory location further includes adjusting the memory location based on the number of transparent pixels.

5. The method of claim 1 wherein the set of source data for each row includes a count value indicative of the amount of row data stored therefor, and wherein decoding the set of source data into actual pixel data includes tracking the amount of data decoded with respect to the count value, and halting the decoding for the row when the amount of data decoded corresponds to the count value.

6. The method of claim 1 wherein the pixel data is encoded into units of storage in the set of source data, each unit including a run length and a color value, and decoding the set of data into actual pixel data includes extracting the run length and color value from each unit.

7. The method of claim 6 wherein a table of colors is stored with the compressed data, and wherein decoding the set of source data into actual pixel data includes using the color value extracted from each unit as in index into the table.

8. The method of claim 1 wherein less columns of pixels are to be decoded than represented in the sets of source data stored for each row in the compressed data, and wherein determining a destination memory location further includes adjusting the memory location based on the number of columns.

9. The method of claim 4 wherein less columns of pixels are to be decoded than represented in the sets of source data are stored for each row in the compressed data, and wherein determining a destination memory location further includes adjusting the memory location based on the number of columns and the number of transparent pixels.

27. The method of claim 1 wherein the set of source data includes a plurality of units of color storage and decoding the set of source data into actual pixel data comprises:

for each unit of color storage,

determining a color index from within the unit of color storage;

correlating the color index with a color value stored in a table;

obtaining a run length from within the unit of color storage corresponding to the color index; and

duplicating the color value based on the run length value to create the actual pixel data.

28. The method of claim 27 wherein the length of the table corresponds to a color index length for representing the color index in the unit of color storage.

29. The method of claim 27 wherein the table is stored in association with the compressed data.

30. The method of claim 27 wherein the unit of color storage comprises a fixed length number of bits.

31. The method of claim 1 wherein at least two row pointers point to the same set of source data in the compressed data.

32. A computer-readable medium having computer-executable instructions for performing the method of claim 1.

10. A system of decoding a set of compressed data into a representation of the original image of a plurality of rows of pixels, comprising, a memory including the compressed data, wherein each row of pixels in the image to be decoded has a row pointer corresponding thereto in the set of compressed data and each row pointer points to a set of source data in the set of compressed data that represents at least part of a row of pixels, means for determining the rows of pixels to be decoded into the image, and for each row of pixels determined, means for decompressing the compressed data by locating the row pointer to the set of source data and for locating the set of source data therefrom, means for determining a destination location in the memory corresponding to said row of pixels to be decoded, means for decoding the set of source data into actual pixel data, and means for writing the actual pixel data into the determined destination location in the memory.

11. The system of claim 10 wherein less rows are to be decoded than distinct sets of source data are stored therefor in the compressed data, and wherein the means for determining the rows of pixels to be decoded into the image includes means for selecting the first row and the last row to be decoded.

12. The system of claim 11 wherein for each row of pixels determined, the means for decompressing the compressed data by locating the pointer to the set of source data includes means for locating the pointer for the set of source data from the first row through the last row.

13. The system of claim 10 wherein the set of source data includes a value indicative of a number of transparent pixels at the beginning of each row of pixels, and wherein the means for determining a destination memory location includes means for adjusting the memory location based on the number of transparent pixels.

14. The system of claim 10 wherein the set of source data includes a count value indicative of the amount of row data stored therefor, and wherein the means for decoding the set of source data into actual pixel data includes means for tracking the amount of data decoded with respect to the count value, and means for halting the decoding for the row when the amount of data decoded corresponds to the count value.

15. The system of claim 10 wherein the pixel data is encoded into units of storage in the distinct set of source data, each unit including a run length and a color value, and the means for decoding the distinct set of source data into actual pixel data includes means for extracting the run length and color value from each unit.

16. The system of claim 15 wherein a table of colors is stored with the compressed data, and wherein the means for decoding the distinct set of source data into actual pixel data includes means for using the color value extracted from each unit as in index into the table.

17. The system of claim 10 wherein less columns of pixels are to be decoded than represented in the sets of source data stored in the compressed data, and wherein the means for determining a destination memory location includes means for adjusting the memory location based on the number of columns.

18. The system of claim 13 wherein less columns of pixels are to be decoded than represented in the sets of source data are stored in the compressed data, and wherein the means for determining a destination memory location includes means for adjusting the memory location based on the number of columns and the number of transparent pixels.

33. The system of claim 10 wherein the row pointer corresponds to two or more rows of pixels in the image to be decoded.

19. A method of decoding a set of compressed data into a representation of an original image of a plurality of rows of pixels, comprising:

(a) determining the rows of pixels to be decoded for the image;

(b) for each row of pixels determined, decoding the compressed data by locating and accessing one of a plurality of row pointers corresponding to the row of pixels to be decoded, each row pointer pointing to a set of source data in the set of compressed data that represents at least part of a row of pixels;

(c) determining the first and last row of pixels to be decoded into the image and setting a row counter to a value indicative of the first row;

(d) locating the row pointer to the set of source data for the row of pixels to be decoded based upon the value of the row counter and locating the set of source data from the row pointer;

(e) determining a destination memory location corresponding to the row of pixels to be decoded;

(f) decoding the set of source data into actual pixel data and writing the actual pixel data into the determined destination memory location;

(g) evaluating the row counter against the last row to be decoded; and

(h) if the row counter does not indicate that the last row has been decoded, changing the value of the row counter to a value indicative of the next row and repeating steps (d)-(h).

20. The method of claim 19 wherein less rows are decoded than distinct sets of source data are stored therefor in the compressed data.

34. A computer-readable medium having computer-executable instructions for performing the method of claim 19.

21. A method of decoding data representative of an image of pixels, comprising, determining a fixed number of bits in a unit of color storage corresponding to a run length and a number of bits corresponding to a color index that represents no more than one color, selecting at least some of the units of color storage having run length, color information therein, and for each selected unit of color storage, obtaining a color index value from a value of the bits therein and obtaining a run length value from a value of the bits therein, looking up pixel information based on the color index value, and outputting the pixel information to a number of pixels based on the run length.

22. The method of claim 21 wherein the unit is a byte.

23. The method of claim 21 wherein determining a fixed number of bits includes accessing information in a header indicative of the number of bits corresponding to the run length and the number of bits corresponding to the color index.

24. The method of claim 21 wherein looking up pixel information includes accessing a table in a header indicative of the pixel values via the index.

25. A computer-readable medium having stored thereon a data structure, comprising:

a plurality of units of compressed image source data of a plurality of rows, each unit comprising a section indicative of run length in at least one of the rows and another section indicative of a color index;

a first field including a color table; and

a second field indicative of a fixed number of bits of the units that represent the run length information and a number of bits that represent the color index, each color index corresponding to one color in the color table.

26. The computer-readable medium having stored thereon the data structure of claim 25 further comprising a fourth field including at least one row pointer to the compressed image source data.

35. A method of decoding compressed data of an original image into an image of pixels, comprising,

selecting a fixed unit of color storage from the compressed data, each unit having a number of bits representing a color index and a number of bits representing a run length of one or more pixels having the same output color data that represents no more than one color;

determining the color index from within the unit of color storage;

obtaining a run length from within the unit of color storage corresponding to the color index; and

providing color data for a number of pixels based on the run length and the color index.

36. The method of claim 35 further comprising, providing a differently-colored image of pixels by correlating the color index with a color value stored in a second table that is different from the first table.

37. The method of claim 35 wherein selecting a fixed unit of color storage from the compressed data comprises, accessing the compressed image data to determine a row pointer, and locating the fixed unit based on the row pointer.

39. The method of claim 35 wherein selecting a fixed unit of color storage from the compressed data comprises, accessing the compressed image data to determine a row pointer, and locating the fixed unit based on the row pointer.

38. A method of decoding compressed data of an original image into an image of pixels, comprising,

selecting a unit of color storage from the compressed data, each unit having a number of bits representing a color index and a number of bits representing a run length;

determining the color index from within the unit of color storage;

obtaining a run length from within the unit of color storage corresponding to the color index;

providing a first image by correlating the color index with a color value stored in a first table to provide first color data for a number of pixels based on the run length and the color value; and

providing a second image by correlating the color index with a color value stored in a second table that is different from the first table.