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

• US 5,796,864 A
• Filed: 01/04/1995
• Issued: 08/18/1998
• 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): Mancuso, Joseph
• Assistant Examiner(s): CHANG, JON CARLTON
• Application Number:
  US08/368,337
• Time in Patent Office: 1,322 Days
• Field of Search: 382/166, 382/232-233, 382/244, 382/165, 358/429-430, 358/433, 358/426, 358/432, 358/261.1, 358/261.3, 358/539, 348/420
• US Class Current: 382/166
• 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 comprised 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 its 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 in a digital processing system for encoding a current pixel block by determining whether colors represented in a current pixel block match colors represented in any one of a plurality of other pixel blocks, the method comprising the steps of:

A) generating a plurality of color lists by generating a color list for each pixel block of said plurality of other pixel blocks, wherein the color list for each given pixel block of said plurality of other pixel blocks identifies colors represented in said given pixel block;

B) storing said plurality of color lists in a plurality of color caches, 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;

C) generating a current color list that identifies colors represented in said current pixel block;

D) 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 at least the same number of colors as are represented in said current color list;

E) comparing said current color list to one or more color lists contained in said selected color cache;

F) if said current color list matches a color list of said one or more color lists stored in said selected color cache, then outputting a first compressed data stream for said current pixel block wherein said first compressed data stream includes a cache index that corresponds to an entry in said color cache containing said one or more color lists that matches said current color list, and a current pixel map; and

G) if said current color list does not match said color list of said one or more color lists stored in said selected color cache, then outputting a second compressed data stream for said current pixel block wherein said second compressed data stream includes said current color list, and said current pixel map.

2. The method of claim 1 further comprising the steps prior to step F) and G) of:

obtaining said current pixel block from a block of color image data, wherein said current pixel block has a plurality of pixels; and

generating said current pixel map, wherein said current pixel map indicates a correspondence between said plurality of pixels and the colors represented in said current pixel block.

3. The method of claim 1 further comprising the steps prior to step F) and G) of:

generating a control block;

associating said control block with a particular color list of said plurality of color lists;

comparing said current color list to said particular color list prior to performing the steps of D) identifying the selected color cache and E) comparing said current color list to one or more color lists contained in said selected color cache;

incrementing a count field in said control block if said current color list matches said particular color list; and

wherein the steps of D) identifying the selected color cache and E) comparing said current color list to one or more color lists contained in said selected color cache are performed only if said color list does not match said particular color list.

4. The method of claim 1 wherein step F) further comprises the steps of:

generating a control block;

creating a reference in said control block to the color list in the selected color cache that matches said current color list; and

setting a type field in said control block corresponding to the number of colors in said current color list.

5. The method of claim 1 wherein said step of comparing said current color list to one or more color lists contained in said selected color cache is further comprised of the steps of:

a) creating a plurality of cache entry masks by generating a cache entry mask for each color list in said selected color cache, wherein each color list in said selected color cache represents one or more colors, wherein each color of said one or more colors falls within a color range of a plurality of color ranges, wherein said cache entry mask for each given color list in said selected color cache identifies the color ranges of said plurality of color ranges that correspond to said one or more colors represented in said given color list;

b) generating a pixel block mask, said pixel block mask identifying the color ranges of said plurality of color ranges that correspond to said colors represented in said current pixel block; and

c) comparing said pixel block mask to one or more of said cache entry masks.

6. The method of claim 5 wherein said step of (c) comparing said pixel block mask to one or more of said cache entry masks comprises the steps of

c1) comparing a cache entry mask of a selected cache color list 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;

c2) 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 step c1) for a next cache color list in said selected color cache;

c3) 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,

i) comparing the individual colors of said current color list and said selected cache color list;

ii) if a predetermined minimum number of colors identified in said selected cache color list do not match the colors identified in said current color list, repeating step c1) for a next cache color list in said selected color cache;

iii) if said predetermined minimum number of colors identified in said selected cache color list do match the colors identified in said current color list, identifying said selected cache color list as a match.

7. A method in a digital processing system for encoding a current pixel block by determining whether colors represented in a current pixel block match colors represented in any of a plurality of other pixel blocks, the method comprising the steps of:

A) generating a plurality of color lists by generating a color list for each pixel block of said plurality of other pixel blocks, wherein the color list for each given pixel block of said plurality of other pixel blocks identifies colors represented in said given pixel block;

B) storing said plurality of color lists in a color cache in said digital processing system;

C) generating a current color list that identifies colors represented in said current pixel block;

D) comparing said current color list to one or more color lists contained in said color cache by performing the steps of;

a) creating a plurality of cache entry masks by generating a cache entry mask for each color list in said color cache, wherein each color list in said color cache represents one or more colors, wherein each color of said one or more colors corresponds to a color range of a plurality of color ranges, wherein said cache entry mask for each given color list in said color cache identifies the color ranges of said plurality of color ranges that correspond to said one or more colors represented in said given color list;

b) generating a pixel block mask, said pixel block mask identifying the color ranges of said plurality of color ranges that correspond to said colors represented in said current pixel block; and

c) comparing said pixel block mask to one or more of said plurality of cache entry masks

E) using the result of comparing step (D) to encode said current pixel block.

8. The method of claim 7 wherein said step of (c) comparing said pixel block mask to one or more of said cache entry masks comprises the steps of

c1) comparing a cache entry mask of a selected cache color list in said 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;

c2) 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 step c1) for a next cache color list in said color cache;

c3) 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,

i) comparing the individual colors of said current color list and said selected cache color list;

ii) if a predetermined minimum number of colors identified in said selected cache color list do not match the colors identified in said current color list, repeating step c1) for a next cache color list in said selected color cache;

iii) if said predetermined minimum number of colors identified in said selected cache color list do match the colors identified in said current color list, identifying said selected cache color list as a match.

9. A method in a digital processing system for encoding a current pixel block by determining whether colors of a current pixel block match colors of any of a plurality of other pixel blocks, the method comprising the steps of:

A) generating a plurality of color lists by generating a color list for each pixel block of said plurality of other pixel blocks, wherein the color list for each given pixel block of said plurality of other pixel blocks identifies colors represented in said given pixel block;

B) providing a color cache in said digital processing system;

C) for each given color list of said plurality of color lists, performing the steps of

C1) determining whether a cache entry corresponding to the colors in said given color list is already stored in said color cache; and

C2) if a cache entry corresponding to the colors in said given color list is not already stored in said color cache, then storing a cache entry corresponding to the colors in said given color list in said color cache;

D) generating a current color list that identifies colors represented in said current pixel block;

E) determining whether a cache entry corresponding to the colors in said current color list is stored in said color cache and

F) using the result of determining step (E) to encode said current pixel block.

10. The method of claim 9 wherein said color cache includes a plurality of color caches, wherein the cache entry corresponding to the colors in said given color list is stored by performing the steps of:

determining a particular color cache of said plurality of color caches based on the number of colors in said given color list; and

storing said cache entry in said particular color cache.

11. The method of claim 10 wherein said step of determining whether a cache entry corresponding to the colors in said current color list is stored in said color cache includes the steps of:

selecting a selected color cache of said plurality of color caches based on the number of colors in said current color list; and

determining whether said selected color cache contains a cache entry corresponding to the colors in said current color list.

12. A method for outputting a representation of a current pixel block into a compressed data stream, wherein the current pixel block comprises a plurality of pixels having a plurality of colors, the method comprising the steps of:

A) processing a plurality of previous pixel blocks by performing the following steps for each given pixel block of said plurality of previous pixel blocks

A1) generating a cache entry corresponding to colors represented in said given pixel block;

A2) storing said cache entry in a color cache;

A3) generating a representation of said given pixel block; and

A4) outputting said representation into said compressed data stream;

B) generating a current color list that identifies said plurality of colors;

C) generating a current pixel map that indicates a correspondence between said plurality of pixels and said plurality of colors;

D) determining if said plurality of colors match colors represented in any of said plurality of previous pixel blocks by

D1) comparing said current color list to one or more cache entries in said color cache;

E) if colors represented in said current color list match colors represented in a given cache entry of said one or more cache entries, then

E1) generating first control information indicating that colors represented in said current color list match colors represented in said given cache entry;

E2) outputting as part of said compressed data stream said first control information;

E3) outputting as part of said compressed data stream said current pixel map;

F) if colors represented in said current color list do not match colors represented in any cache entry of said one or more cache entries, then

F1) generating second control information indicating the number of colors in said current color list, and

F2) outputting as part of said compressed data stream said second control information, said current color list and said current pixel map.

13. The method of claim 12 wherein said step of E1) generating said first control information indicating that colors represented in said current color list match colors represented in said given cache entry comprises the steps of

E1a) generating a new control block, said new control block having a flag field and a type field;

E1b) setting the flag field in said new control block to indicate that said current color list matches a cache entry stored in said color cache,

E1c) setting the type field in said new control block corresponding to the number of colors in said current color list, and

wherein the step of E2) outputting as part of said compressed data stream said first control information comprises the step of

E2a) outputting as part of said compressed data stream said new control block and an index to said given cache entry, wherein said index indicates a position of said given cache entry within said color cache.

14. The method of claim 12 wherein said step of F1) generating second control information indicating the number of colors in said current color list comprises the steps of

F1a) generating a new control block, said new control block having a type field;

F1b) setting the type field of said new control block to a value corresponding to the number of colors in said current color list;

wherein said step of outputting as part of said compressed data stream said second control information comprises the step of

F2a) outputting said new control block as part of said compressed data stream.

15. The method of claim 12 further comprising the steps of

F3) generating a cache entry corresponding to said plurality of colors;

and

F4) entering said cache entry into said color cache.

16. The method of claim 12 further comprising the step of

generating a control block associated with colors of a most recently processed pixel block of said plurality of previous pixel blocks;

wherein the step of D) determining if said plurality of colors match colors represented in any of said plurality of previous pixel blocks further comprises the step of;

comparing colors in said current color list to said colors associated with said control block before performing said step of D1) comparing said current color list to one or more cache entries in said color cache;

if colors in said current color list match said colors associated with said control block, then

incrementing a count field in said control block; and

outputting as part of said compressed data stream said current pixel map;

wherein the steps of D1), E) and F) are performed only if colors in said current color list do not match colors associated with said control block.

17. A method for decompressing a compressed data stream, wherein said compressed data stream includes a plurality of compressed sequences, wherein each compressed sequence of said plurality of compressed sequences includes a control block, said decompression method comprising the steps of:

A) providing a color cache for storing a plurality of color lists; and

B) for each given compressed sequence of said plurality of compressed sequences

b) identifying a type of said given compressed sequence based on said control block included in said given compressed sequence;

c) if said control block identifies said given compressed sequence as a first type of compressed sequence, wherein said first type of compressed sequence has a plurality of color list/pixel map combinations, wherein each color list/pixel map combination includes a color list and a corresponding pixel map, then performing the following steps for each given pixel color list/pixel map combination of said plurality of color list/pixel map combinations;

c1) retrieving said given color list/pixel map combination from said given compressed sequence;

c2) generating a colored pixel block based on the color list in said given color list/pixel map combination and the corresponding pixel map in said given color list/pixel map combination;

c3) storing said color list of said given color list/pixel map combination in said color cache;

d) if said control block identifies said given compressed sequence as a second type of compressed sequence, wherein the second type of compressed sequence has a color cache index that indicates a position within said color cache, wherein the second type of compressed sequence further includes a plurality of corresponding pixel maps, then performing the steps of;

d1) retrieving a color list from said position within said color cache based on said color cache index included in said given compressed sequence; and

d2) for each given pixel map of said plurality of corresponding pixel maps, generating a colored pixel block based on the color list from said position within said color cache and said given pixel map.

18. The method of claim 17 wherein:

said step of providing a color cache for storing a plurality of color lists includes providing a plurality of color caches; and

said step of storing said color list of said given color list/pixel map combination in said color cache includes

selecting a selected color cache of said plurality of color caches based on how many colors are represented in said color list of said given color list/pixel map combination; and

storing said color list of said given color list/pixel map combination in said selected color cache.

19. A method for compressing image data, the method comprising the steps of:

a) extracting a pixel block from a block of image data, wherein the pixel block includes a plurality of pixels having a plurality of different colors;

b) determining how many different colors are included in said plurality of different colors;

c) creating a pixel block count representing how many different colors are included in said plurality of different colors;

d) creating a color list representing each color of said plurality of different colors;

e) if said pixel block count is equal to or below a first predetermined number of color values, then

generating a color value reference that identifies said plurality of different colors;

generating a pixel map that indicates a correspondence between said plurality of different colors and said plurality of pixels in said pixel block;

storing said pixel block as a compressed pixel block, wherein said compressed pixel block includes said color value reference and said pixel map; and

f) if said pixel block count is above said first predetermined number of color values, then storing said pixel block as uncompressed.

20. The method as recited in claim 19 wherein said step of generating a pixel map that indicates a correspondence between said plurality of different colors and said plurality of pixels in said pixel block is further comprised of the steps of:

a) comparing said color list to a plurality of other color lists, wherein the plurality of other color lists are color lists that indicate colors contained in a plurality of previously processed pixel blocks;

b) if said color list matches a matching color list of said plurality of other color lists, then generating said pixel map in reference to said matching color list; and

c) if said color list does not match any color list of said plurality of other color lists, then generating said pixel map in reference to said color list.

21. The method as recited in claim 20 wherein said step of comparing said color list to a plurality of other color lists is further comprised of the step of comparing said color list to one or more entries in a color cache.

22. The method as recited in claim 21 wherein said color value reference is an index to a cache entry in said color cache, wherein said cache entry corresponds to said matching color list.