Method of compressing and decompressing graphics images

In a computer system, an apparatus for compressing a block of graphics image data into a compressed block, the block having a plurality of lines, each line having a plurality of columns, each column including a pixel, each pixel having a color represented by red, green, blue, and intensity values, the apparatus comprising:

• means for building an array of color ordinal numbers by identifying all colors present in the pixels of the block, each color ordinal number representing one of the colors, the array of color ordinal numbers comprising one of the color ordinal numbers corresponding to the color of a pixel for each pixel in the block;
• means for building a first set of flags indicating lines in the block having pixels of a selected color according to the array of color ordinal numbers;
• means for building at least one second set of flags indicating columns having pixels of the selected color within lines in the block having pixels of the selected color according to the array of color ordinal numbers, each line having pixels of the selected color being represented by one of the second set of flags;
• means for storing the red, green, blue, and intensity values, the first set of flags, and the at least one second set of flags for a selected one of the colors in the compressed block.

A computer-implemented method of compressing graphics image data into at least one compressed block comprising the steps of:

• (A) reading at least one block of graphics image data, the block having a plurality of lines, each line having a plurality of columns, each column including a pixel, each pixel having a color represented by red, green, blue, and intensity values;
• (B) building an array of color ordinal numbers by identifying all distinct colors present in the pixels of the block, each color ordinal number representing one of the distinct colors, the array of color ordinal numbers comprising one of the color ordinal numbers corresponding to the distinct color of a pixel for each pixel in the block;
• (C) selecting a current color of the distinct colors present in the block;
• (D) storing the red, green, blue, and intensity values for the current color in the compressed block;
• (E) building a set of group flags indicating lines in the block having pixels of the current color according to the array of color ordinal numbers;
• (F) storing the set of group flags in the compressed block;
• (G) building at least one set of line flags indicating columns having pixels of the current color within lines in the block having pixels of the current color according to the array of color ordinal numbers, each line having pixels of the current color being represented by one set of line flags;
• and
• (H) storing the at least one set of line flags in the compressed block.

A computer-implemented method of compressing graphics image data into at least one compressed block comprising the steps of:

• (A) obtaining a mask value;
• (B) reading at least one block of graphics image data, the block having a plurality of lines, each line having a plurality of columns, each column including a pixel, each pixel having a color represented by red, green, blue, and intensity values;
• (C) building an array of color ordinal numbers by identifying all distinct colors present in the pixels of the block according to the mask value, each color ordinal number representing one of the distinct colors, the array of color ordinal numbers comprising one of the color ordinal numbers corresponding to the distinct color of a pixel for each pixel in the block;
• (D) selecting a current color of the distinct colors present in the block;
• (E) storing the red, green, blue, and intensity values for the current color in the compressed block;
• (F) building a set of group flags indicating lines in the block having pixels of the current color according to the array of color ordinal numbers;
• (G) storing the set of group flags in the compressed block;
• (H) building at least one set of line flags indicating columns having pixels of the current color within lines in the block having pixels of the current color according to the array of color ordinal numbers, each line having pixels of the current color being represented by one set of line flags;
• and
• (I) storing the at least one set of line flags in the compressed block.

In a computer system, an apparatus for compressing a block of graphics image data into at least one compressed block, the block having a plurality of lines, each line having a plurality of columns, each column including a pixel, each pixel having a color represented by red, green, blue, and intensity values, the apparatus comprising:

• means for obtaining a mask value;
• means for reading at least one block of graphics image data;
• means for building an array of color ordinal numbers by identifying all distinct colors present in the pixels of the block according to the mask value, each color ordinal number representing one of the distinct colors, the array of color ordinal numbers comprising one of the color ordinal numbers corresponding to the distinct color of a pixel for each pixel in the block;
• means for selecting a current color of the distinct colors present in the block;
• means for building a set of group flags indicating lines in the block having pixels of the current color according to the array of color ordinal numbers;
• means for building at least one set of line flags indicating columns having pixels of the current color within lines in the block having pixels of the current color according to the array of color ordinal numbers, each line having pixels of the current color being represented by one set of line flags;
• and
• means for storing the number of distinct colors, the mask value, the red, green, blue, and intensity values, the set of group flags, and the at least one set of line flags for the current color in the compressed block.

A computer-implemented method of compressing graphics image data into at least one compressed block comprising the steps of:

• (A) obtaining a mask value;
• (B) reading a block of graphics image data, the block having a plurality of lines, each line having a plurality of columns, each column including a pixel, each pixel having a color represented by red, green, blue, and intensity values;
• (C) building an array of color ordinal numbers by identifying all distinct colors present in the pixels of the block according to the mask value, each color ordinal number representing one of the distinct colors, the array of color ordinal numbers comprising one of the color ordinal numbers corresponding to the distinct color of a pixel for each pixel in the block;
• (D) selecting a current color of the distinct colors present in the block;
• (E) storing the red, green, blue, and intensity values for the current color in the compressed block;
• (F) building a set of group flags indicating lines in the block having pixels of the current color according to the array of color ordinal numbers;
• (G) storing the set of group flags in the compressed block;
• (H) building at least one set of line flags indicating columns having pixels of the current color within lines in the block having pixels of the current color according to the array of color ordinal numbers, each line having pixels of the current color being represented by one set of line flags;
• (I) storing the at least one set of line flags in the compressed block;
• (J) repeating steps (D) through (I) for all distinct colors in the block;
• (K) moving the red, green, blue, and intensity values of a distinct color occurring most frequently in pixels of the block to the end of the compressed block;
• (L) storing a size of the compressed block and the mask value in the compressed block;
• and
• (M) repeating steps (B) through (L) for all blocks of graphics image data.

A computer-implemented method of decompressing a compressed block of graphics image data into an uncompressed block, the uncompressed block having a plurality of lines, each line having a plurality of columns, each column including a pixel, each pixel having a color represented by red, green, blue, and intensity values, the compressed block having a plurality of distinct red, green, blue, and intensity values color combinations, each distinct color combination having a set of group flags representing the presence of the distinct color combination in lines of the uncompressed block and at least one set of line flags representing the presence of the distinct color combination in columns of the uncompressed block for lines of the uncompressed block having the distinct color combination, the computer-implemented method comprising the steps of:

• (A) getting the red, green, blue, and intensity values for a selected color from the compressed block;
• (B) getting the set of group flags for the selected color from the compressed block;
• (C) getting a set of line flags corresponding to a selected group flag in the set of group flags indicating the presence of the selected color in at least one line of the compressed block;
• (D) writing the red, green, blue, and intensity values into the uncompressed block at selected locations indexed by columns having the selected color as indicated by the set of line flags for the line having the selected color as indicated by the selected group flag;
• (E) repeating steps (C) and (D) for each group flag in the set of group flags indicating the presence of the selected color in at least one line of the compressed block;
• and
• (F) repeating steps (A)-(E) for all distinct color combinations of the compressed block.

In a computer system, an apparatus for decompressing a compressed block of graphics image data into an uncompressed block, the uncompressed block having a plurality of lines, each line having a plurality of columns, each column including a pixel, each pixel having a color represented by red, green, blue, and intensity values, the compressed block having a plurality of distinct red, green, blue, and intensity values color combinations, each distinct color combination having a set of group flags representing the presence of the distinct color combination in lines of the uncompressed block and at least one set of line flags representing the presence of the distinct color combination in columns of the uncompressed block for lines of the uncompressed block having the distinct color combination, the apparatus comprising:

• means for reading the red, green, blue, and intensity values for a selected color from the compressed block, the set of group flags for the selected color from the compressed block, and at least one set of line flags corresponding to a group flag in the set of group flags indicating the presence of the selected color in at least one line of the compressed block;
• and
• means for writing the red, green, blue, and intensity values into the uncompressed block at selected locations indexed by columns having the selected color as indicated by the at least one set of line flags and by lines having the selected color as indicated by the set of group flags.

A computer-implemented method of decompressing a compressed graphics image data into at least one uncompressed block, the uncompressed block having a plurality of lines, each line having a plurality of columns, each column including a pixel, each pixel having a color represented by red, green, blue, and intensity values, the computer-implemented method comprising the steps of:

• (A) reading a block of compressed graphics image data, the compressed block having a plurality of distinct red, green, blue, and intensity values color combinations, each distinct color combination having a set of group flags representing the presence of the distinct color combination in lines of the uncompressed block and at least one set of line flags representing the presence of the distinct color combination in columns of the uncompressed block for lines of the uncompressed block having the distinct color combination;
• (B) getting the red, green, blue, and intensity values for a selected color from the compressed block;
• (C) getting the set of group flags for the selected color from the compressed block;
• (D) getting a set of line flags corresponding to a selected group flag in the set of group flags indicating the presence of the selected color in at least one line of the compressed block;
• (E) writing the red, green, blue, and intensity values into the uncompressed block at selected locations indexed by columns having the selected color as indicated by the set of line flags for the line having the selected color as indicated by the selected group flag;
• (F) repeating steps (D) and (E) for each group flag in the set of group flags indicating the presence of the selected color in at least one line of the compressed block;
• (G) repeating steps (B)-(F) for all distinct color combinations of the compressed block;
• and
• (H) repeating steps (A)-(G) for all blocks of the compressed graphics image data.

A computer-implemented method of decompressing a compressed graphics image data into at least one uncompressed block, the uncompressed block having a plurality of lines, each line having a plurality of columns, each column including a pixel, each pixel having a color represented by red, green, blue, and intensity values, the computer-implemented method comprising the steps of:

• (A) reading a block of compressed graphics image data, the compressed block having a mask value, a plurality of distinct red, green, blue, and intensity values color combinations, each distinct color combination having a set of group flags representing the presence of the distinct color combination in lines of the uncompressed block and at least one set of line flags representing the presence of the distinct color combination in columns of the uncompressed block for lines of the uncompressed block having the distinct color combination;
• (B) getting the mask value from the compressed block;
• (C) getting the red, green, blue, and intensity values for a last color from the compressed block and modifying the red, green, blue, and intensity values according to the mask value;
• (D) writing the modified red, green, blue, and intensity values for the last color into the uncompressed block for all pixels of the uncompressed block;
• (E) getting the red, green, blue, and intensity values for a selected color from the compressed block and modifying the red, green, blue, and intensity values according to the mask value;
• (F) getting the set of group flags for the selected color from the compressed block;
• (G) getting a set of line flags corresponding to a selected group flag in the set of group flags indicating the presence of the selected color in at least one line of the compressed block;
• (H) writing the modified red, green, blue, and intensity values of the selected color into the uncompressed block at selected locations indexed by columns having the selected color as indicated by the set of line flags and for the line having the selected color as indicated by the selected group flag;
• (I) repeating steps (G) and (H) for each group flag in the set of group flags indicating the presence of the selected color in at least one line of the compressed block;
• (J) repeating steps (E)-(I) for all distinct color combinations of the compressed block;
• and
• (K) repeating steps (A)-(J) for all blocks of the compressed graphics image data.

In a computer system, an apparatus for decompressing a compressed block of graphics image data into an uncompressed block, the uncompressed block having a plurality of lines, each line having a plurality of columns, each column including a pixel, each pixel having a color represented by red, green, blue, and intensity values, the compressed block having a plurality of distinct red, green, blue, and intensity values color combinations, each distinct color combination having a set of group flags representing the presence of the distinct color combination in lines of the uncompressed block and at least one set of line flags representing the presence of the distinct color combination in columns of the uncompressed block for lines of the uncompressed block having the distinct color combination, the apparatus comprising:

• means for reading a mask value from the compressed block and the red, green, blue, and intensity values for a last color from the compressed block;
• means for modifying red, green, blue, and intensity values according to the mask value;
• means for writing the modified red, green, blue, and intensity values for the last color into the uncompressed block for all pixels of the uncompressed block;
• means for reading the red, green, blue, and intensity values for a selected color from the compressed block, the set of group flags for the selected color from the compressed block, and at least one set of line flags corresponding to a group flag in the set of group flags indicating the presence of the selected color in at least one line of the compressed block;
• and
• means for writing the modified red, green, blue, and intensity values for the selected color into the uncompressed block at selected locations indexed by columns having the selected color as indicated by the set of line flags and by lines having the selected color as indicated by the set of group flags.

A computer-readable medium comprising:

• a program code embodied in the computer readable medium for compressing a block of graphics image data into a compressed block, the block having a plurality of lines, each line having a plurality of columns, each column including a pixel, each pixel having a color represented by red, green, blue, and intensity values, the computer-readable program segment comprising instructions for performing the steps of:
• (A) building an array of color ordinal numbers by identifying all colors present in the pixels of the block, each color ordinal number representing one of the colors, the array of color ordinal numbers comprising one of the color ordinal numbers corresponding to the color of a pixel for each pixel in the block;
• (B) storing the red, green, blue, and intensity values for a selected one of the colors in the compressed block;
• (C) building a first set of flags indicating lines in the block having pixels of the selected color according to the array of color ordinal numbers;
• (D) storing the first set of flags in the compressed block;
• (E) building at least one second set of flags indicating columns having pixels of the selected color within lines in the block having pixels of the selected color according to the array of color ordinal numbers, each line having pixels of the selected color being represented by one of the second set of flags;
• (F) storing the at least one second set of flags in the compressed block;
• and
• (G) repeating steps (B) through (F) for all colors in the block.

A computer-readable medium comprising:

• a program code embodied in the computer readable medium for decompressing a compressed block of graphics image data into an uncompressed block, the uncompressed block having a plurality of lines, each line having a plurality of columns, each column including a pixel, each pixel having a color represented by red, green, blue, and intensity values, the compressed block having a plurality of distinct red, green, blue, and intensity values color combinations, each distinct color combination having a set of group flags representing the presence of the distinct color combination in lines of the uncompressed block and at least one set of line flags representing the presence of the distinct color combination in columns of the uncompressed block for lines of the uncompressed block having the distinct color combination, the computer-readable program segment comprising instructions for performing the steps of:
• (A) getting the red, green, blue, and intensity values for a selected color from the compressed block;
• (B) getting the set of group flags for the selected color from the compressed block;
• (C) getting a set of line flags corresponding to a selected group flag in the set of group flags indicating the presence of the selected color in at least one line of the compressed block;
• (D) writing the red, green, blue, and intensity values into the uncompressed block at selected locations indexed by columns having the selected color as indicated by the set of line flags for the line having the selected color as indicated by the selected group flag;
• (E) repeating steps (C) and (D) for each group flag in the set of group flags indicating the presence of the selected color in at least one line of the compressed block;
• and
• (F) repeating steps (A)-(E) for all distinct color combinations of the compressed block.

An article of manufacture, comprising:

• a computer-readable medium bearing a program code embodied therein for compressing graphics image data including a first computer-readable program segment for compressing a block of graphics image data into a compressed block, the block having a plurality of lines, each line having a plurality of columns, each column including a pixel, each pixel having a color represented by red, green, blue, and intensity values, the first computer-readable program segment comprising instructions for performing the steps of:
• (A) building an array of color ordinal numbers by identifying all colors present in the pixels of the block, each color ordinal number representing one of the colors, the array of color ordinal numbers comprising one of the color ordinal numbers corresponding to the color of a pixel for each pixel in the block;
• (B) storing the red, green, blue, and intensity values for a selected one of the colors in the compressed block;
• (C) building a first set of flags indicating lines in the block having pixels of the selected color according to the array of color ordinal numbers;
• (D) storing the first set of flags in the compressed block;
• (E) building at least one second set of flags indicating columns having pixels of the selected color within lines in the block having pixels of the selected color according to the array of color ordinal numbers, each line having pixels of the selected color being represented by one of the second set of flags;
• (F) storing the at least one second set of flags in the compressed block;
• and
• (G) repeating steps (A) through (F) for all colors in the block.

An article of manufacture, comprising:

• a computer-readable medium bearing a program code embodied therein for decompressing a compressed graphics image data including a first computer-readable program segment for decompressing a compressed block of graphics image data into an uncompressed block, the uncompressed block having a plurality of lines, each line having a plurality of columns, each column including a pixel, each pixel having a color represented by red, green, blue, and intensity values, the compressed block having a plurality of distinct red, green, blue, and intensity values color combinations, each distinct color combination having a set of group flags representing the presence of the distinct color combination in lines of the uncompressed block and at least one set of line flags representing the presence of the distinct color combination in columns of the uncompressed block for lines of the uncompressed block having the distinct color combination, the first computer-readable program segment comprising instructions for performing the steps of:
• (A) getting the red, green, blue, and intensity values for a selected color from the compressed block;
• (B) getting the set of group flags for the selected color from the compressed block;
• (C) getting a set of line flags corresponding to a selected group flag in the set of group flags indicating the presence of the selected color in at least one line of the compressed block;
• (D) writing the red, green, blue, and intensity values into the uncompressed block at selected locations indexed by columns having the selected color as indicated by the set of line flags and for the line having the selected color as indicated by the selected group flag;
• (E) repeating steps (C) and (D) for each group flag in the set of group flags indicating the presence of the selected color in at least one line of the compressed block;
• and
• (F) repeating steps (A)-(E) for all distinct color combinations of the compressed block.

A memory storing data for representing a compressed block of graphics image data based on an uncompressed block of graphics image data, the uncompressed block having a plurality of lines, each line having a plurality of columns, each column including a pixel, each pixel having a color represented by red, green, blue, and intensity values, the memory comprising:

• a data structure stored in said memory and comprising:
• a plurality of distinct color combinations having red, green, blue, and intensity values, a set of group flags representing the presence of each distinct color combination in lines of the uncompressed block for each distinct color combination and at least one set of line flags representing the presence of each distinct color combination in columns of the uncompressed block for each line of the uncompressed block having each distinct color combination;
• and
• a mask value for the compressed block wherein two colors, a first color having a first red value, a first green value, a first blue value, and a first intensity value, and a second color having a second red value, a second green value, a second blue value, and a second intensity value, are distinct if the first red value divided by the mask value is not equal to the second red value divided by the mask value, the first green value divided by the mask value, the first blue value divided by the mask value is not equal to the second blue value divided by the mask value, and the first intensity value divided by the mask value is not equal to the second intensity value divided by the mask value.