Method and apparatus for real-time lossless compression and decompression of image data

Claim 1

A method for compressing a block of color image data to create a compressed data stream comprised of encoded control blocks and color value data, said method comprising the steps of: A) generating a control block having a type field, a count field and a flag field, said control block being associated with a particular color list; B) obtaining a current pixel block from said block of color image data, said current pixel block including a plurality of pixels having a plurality of colors; C) generating a current color list corresponding to said current pixel block, said current color list identifying said plurality of colors; D) generating a current pixel map, said current pixel map indicating a correspondence between said plurality of pixels and said plurality of colors; E) providing a plurality of color caches for storing a plurality of color lists, wherein said plurality of color lists are stored in said plurality of color caches based upon the number of colors represented in each of said plurality of color lists; F) comparing said current color list to said particular color list associated with said control block to determine a match; and G) if said current color list matches said particular color list associated with said current color block, then G1) incrementing the count field of said current block; and G2) outputting as part of said compressed data stream said current pixel map; H) if said current color list does not match said particular color list associated with said control block, then H1) identifying a selected color cache of said plurality of color caches, the selected color cache being a color cache that stores color lists that represent the same number of colors as are represented in said current color list; H2) comparing said current color list to one or more color lists from said selected color cache to determine if said current color list matches a color list of said one or more color lists stored in said selected color cache; H3) if said current color list matches said color list of said one or more color lists stored in said selected color cache, then encoding said current pixel block by H3a) generating a new control block, said new control block having a flag field and a type field; H3b) creating a reference to said color list of said one or more color lists stored in said selected color cache by setting the flag field in said new control block indicating that said current color list matches one or more color lists stored in said plurality of color caches, H3c) setting the type field in said new control block corresponding to the number of colors in said current color list, and H3d) outputting as part of said compressed data stream said control block and an index to said color list of said one or more color lists stored in said selected color cache; and H3e) outputting as part of said compressed data stream said current pixel map; H4) if said current color list does not match one of said one or more color lists stored in said selected color cache, then encoding said current pixel block by H4a) generating a new control block, said new control block having a type field; H4b) setting the type field of said new control block to a value corresponding to the number of colors in said current color list, H4c) outputting as part of said compressed data stream said new control block, said current color list and said current pixel map, and H4d) entering said current color list into said selected color cache.

Claim 2

A method for compressing a block of color image data to create a compressed data stream comprised of encoded control blocks and color value data, said method comprising the steps of: A) generating a control block having a type field, a count field and a flag field, said control block being associated with a particular color list; B) obtaining a current pixel block from said block of color image data, said current pixel block including a plurality of pixels having a plurality of colors; C) generating a current color list corresponding to said current pixel block, said current color list identifying said plurality of colors; D) generating a current pixel map, said current pixel map indicating a correspondence between said plurality of pixels and said plurality of colors; E) providing a plurality of color caches for storing a plurality of color lists, wherein said plurality of color lists are stored in said plurality of color caches based upon the number of colors represented in each of said plurality of color lists; F) comparing said current color list to said particular color list associated with said control block to determine a match; and G) if said current color list matches said particular color list associated with said current color block, then G1) incrementing the count field of said current block; and G2) outputting as part of said compressed data stream said current pixel map; H) if said current color list does not match said particular color list associated with said control block, then H1) identifying a selected color cache of said plurality of color caches, the selected color cache being a color cache that stores color lists that represent the same number of colors as are represented in said current color list; H2) comparing said current color list to one or more color lists from said selected color cache to determine if said current color list matches a color list of said one or more color lists stored in said selected color cache; H3) if said current color list matches said color list of said one or more color lists stored in said selected color cache, then encoding said current pixel block by H3a) generating a new control block, said new control block having a flag field and a type field; H3b) creating a reference to said color list of said one or more color lists stored in said selected color cache by setting the flag field in said new control block indicating that said current color list matches one or more color lists stored in said plurality of color caches, H3c) setting the type field in said new control block corresponding to the number of colors in said current color list, and H3d) outputting as part of said compressed data stream said control block and an index to said color list of said one or more color lists stored in said selected color cache; and H3e) outputting as part of said compressed data stream said current pixel map; H4) if said current color list does not match one of said one or more color lists stored in said selected color cache, then encoding said current pixel block by H4a) generating a new control block, said new control block having a type field; H4b) setting the type field of said new control block to a value corresponding to the number of colors in said current color list, H4c) outputting as part of said compressed data stream said new control block, said current color list and said current pixel map, and H4d) entering said current color list into said selected color cache.

Claim 4

A method for compressing a block of color image data to create a compressed data stream comprised of encoded control blocks and color value data, said method comprising the steps of: generating a control block having a type field, said control block being associated with a particular color list; obtaining a current pixel block from said block of color image data, said current pixel block including a plurality of pixels having a plurality of colors; generating a current color list corresponding to said current pixel block, said current color list identifying said plurality of colors; generating a current pixel map, said current pixel map indicating a correspondence between said plurality of pixels and said plurality of colors; providing a plurality of color caches for storing a plurality of color lists, wherein said plurality of color lists are stored in said plurality of color caches based upon the number of colors represented in each of said plurality of color lists; comparing said current color list to said particular color list associated with said control block to determine a match; and if said current color list does not match said particular color list associated with said control block, then identifying a selected color cache of said plurality of color caches, the selected color cache being a color cache that stored color lists that represent the same number of colors as are represented in said current color list; comparing said current color list to one or more color lists from said selected color cache to determine if said current color list matches a color list of said one or more color lists stored in said selected color cache; if said current color list does match said color list of said one or more color lists stored in said selected color cache, then encoding said current pixel block by creating a reference to said color list of said one or more color lists stored in said selected color cache, and outputting as part of said compressed data stream said current pixel map; if said current color list does not match one of said one or more color lists stored in said selected color cache, then encoding said current pixel block by generating a new control block, said new control block having a type field; setting the type field to said new control block to a value corresponding to the number of colors in said current color list, outputting as part of said compressed data stream said new control block, said current list and said current pixel map, and entering said current color list into said selected color cache; wherein said step of comparing said current color list to one or more color lists from said selected color cache to determine if said current color list matches a color list of said one or more color lists stored in said selected color cache is further comprised of the steps of: a) generating a cache entry mask for each entry in said selected color cache, each entry in said selected color cache representing one or more colors, each color of said one or more colors corresponding to a color range of a plurality of color ranges, said cache entry mask for each entry in said selected color cache identifying the color ranges of said plurality of color ranges that correspond to said one or more colors represented in said cache entry; b) generating a pixel block mask, said pixel block mask identifying the color ranges of said plurality of color ranges that correspond to said plurality of colors of said plurality of pixels in said current pixel block; c) comparing a cache entry mask of a selected cache entry in said selected color cache with said pixel block mask to determine if a predetermined minimum number of color ranges identified by the cache entry mask match the color ranges identified by the pixel block mask; d) if said predetermined minimum number of color ranges identified by the cache entry mask do not match the color ranges identified by the pixel block mask repeating at step c) for a next cache entry; e) if said predetermined minimum number of color ranges identified by the cache entry mask do match the color ranges identified by the pixel block mask comparing the individual colors of said current color list and said selected cache entry; f) if a predetermined minimum number of colors identified in said cache entry do not match the colors identified in said current color list, repeating at step c) for a next cache entry; g) If said predetermined minimum number of colors identified in said cache entry do match the colors identified in said current color list, identifying said cache entry as a match; and h) repeating steps c)-g) until a match is found or until steps c)-g) have been performed on all the cache entries in said selected cache.

Claim 5

A method for compressing a block of color image data to create a compressed data stream comprised of encoded control blocks and color value data, said method comprising the steps of: generating a control block having a type field, said control block being associated with a particular color list; obtaining a current pixel block from said block of color image data, said current pixel block including a plurality of pixels having a plurality of colors; generating a current color list corresponding to said current pixel block, said current color list identifying said plurality of colors; generating a current pixel map, said current pixel map indicating a correspondence between said plurality of pixels and said plurality of colors; providing a plurality of color caches for storing a plurality of color lists, wherein said plurality of color lists are stored in said plurality of color caches based upon the number of colors represented in each of said plurality of color lists; comparing said current color list to said particular color list associated with said control block to determine a match; and if said current color list does not match said particular color list associated with said control block, then identifying a selected color cache of said plurality of color caches, the selected color cache being a color cache that stored color lists that represent the same number of colors as are represented in said current color list; comparing said current color list to one or more color lists from said selected color cache to determine if said current color list matches a color list of said one or more color lists stored in said selected color cache; if said current color list does match said color list of said one or more color lists stored in said selected color cache, then encoding said current pixel block by creating a reference to said color list of said one or more color lists stored in said selected color cache, and outputting as part of said compressed data stream said current pixel map; if said current color list does not match one of said one or more color lists stored in said selected color cache, then encoding said current pixel block by generating a new control block, said new control block having a type field; setting the type field to said new control block to a value corresponding to the number of colors in said current color list, outputting as part of said compressed data stream said new control block, said current list and said current pixel map, and entering said current color list into said selected color cache; wherein said step of comparing said current color list to one or more color lists from said selected color cache to determine if said current color list matches a color list of said one or more color lists stored in said selected color cache is further comprised of the steps of: a) generating a cache entry mask for each entry in said selected color cache, each entry in said selected color cache representing one or more colors, each color of said one or more colors corresponding to a color range of a plurality of color ranges, said cache entry mask for each entry in said selected color cache identifying the color ranges of said plurality of color ranges that correspond to said one or more colors represented in said cache entry; b) generating a pixel block mask, said pixel block mask identifying the color ranges of said plurality of color ranges that correspond to said plurality of colors of said plurality of pixels in said current pixel block; c) comparing a cache entry mask of a selected cache entry in said selected color cache with said pixel block mask to determine if a predetermined minimum number of color ranges identified by the cache entry mask match the color ranges identified by the pixel block mask; d) if said predetermined minimum number of color ranges identified by the cache entry mask do not match the color ranges identified by the pixel block mask repeating at step c) for a next cache entry; e) if said predetermined minimum number of color ranges identified by the cache entry mask do match the color ranges identified by the pixel block mask comparing the individual colors of said current color list and said selected cache entry; f) if a predetermined minimum number of colors identified in said cache entry do not match the colors identified in said current color list, repeating at step c) for a next cache entry; g) If said predetermined minimum number of colors identified in said cache entry do match the colors identified in said current color list, identifying said cache entry as a match; and h) repeating steps c)-g) until a match is found or until steps c)-g) have been performed on all the cache entries in said selected cache.