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

• US 5,408,542 A
• Filed: 05/12/1992
• Issued: 04/18/1995
• Est. Priority Date: 05/12/1992
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Callahan, Sean M.
• Primary Examiner(s): Chin, Stephen
• Assistant Examiner(s): MAY, TIMOTHY
• Application Number:
  US07/881,770
• Time in Patent Office: 1,071 Days
• Field of Search: 382/56, 382/17, 358/429, 358/430, 358/433, 358/133, 358/426, 358/432, 358/261.3, 358/261.1, 348/420
• US Class Current: 382/244
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: H04N 19/00 Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/593 involving spatial prediction techniques
• CPC Class Codes: H04N 19/98 Adaptive-dynamic-range coding [ADRC]
• CPC Class Codes: H04N 5/781 on disks or drums
• CPC Class Codes: H04N 9/8042 involving data reduction

Abstract

A method and apparatus for lossless compression and decompression of video image data. Video data is composed of the RGB, YUV or gray scale (color) information for each pixel of each frame of the video data. Storage of such video data can require large amounts of data. The present invention provides for lossless compression and decompression of the individual frames of video image data. Each individual frame of video image data is processed in n×n pixel blocks. The combination of colors (called the color list) and the number of different colors in the pixel block is then determined. If the number of colors is above a predetermined threshold, no compression occurs. If the number of colors is below a predetermined threshold, searches for prior occurrences of the combination of colors is than performed. In some instances, a color list for contiguous pixel blocks will be the same. In this instance, a pixel map representing the positioning of the colors in the pixel block is output. Further, each encountered combination of colors is stored as an entry in a color cache. The color cache is subsequently used as a color combination dictionary. In such instances of a pixel block where it'"'"'s color list is in the color cache, an index to the entry into the color cache is used to represent the colors found in the pixel block. The color cache need not be stored with the compressed data stream since it is reconstructed during decompression of the compressed data stream.

Claims

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.

2. The method as recited in claim 1 wherein said current pixel block includes pixels of one or more different colors, said step of generating a current color list being further comprised of the steps of:

a) determining whether a pixel color of a pixel in said current pixel block has not been previously encountered;

b) if said pixel color has not been previously encountered, adding said pixel color to said current color list;

c) if said pixel color has not been previously encountered, incrementing a color count, said color count providing a count of said one or more different colors in said current pixel block; and

d) repeating steps a)-c) for all pixels in said current pixel block.

3. 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.