Method and apparatus for compressing and decompressing color video data with an anti-aliasing mode

• US 5,046,119 A
• Filed: 03/16/1990
• Issued: 09/03/1991
• Est. Priority Date: 03/16/1990
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Mighdoll, Lee S., Miller, Gavin S. P., Hoffert, Eric M., Winner, Stephanie L.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Fox, David
• Application Number:
  US07/495,428
• Time in Patent Office: 536 Days
• Field of Search: 382/56, 358/13, 358/133, 358/429, 358/430, 358/433, 358/445, 358/465, 358/11, 358/78, 340/703
• US Class Current: 382/166
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H04N 1/64 Systems for the transmission or the storage of the colour picture signal; Details therefor, e.g. coding or decoding means therefor H04N19/00 takes precedence
• CPC Class Codes: H04N 11/044 involving transform coding
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
• CPC Class Codes: H04N 19/93 Run-length coding

Abstract

An adaptive compression/decompression method for color video data with an anti-aliasing mode. 4×4 blocks of pixel data are examined to determine which one of four compression techniques should be used on each block. User settable thresholds can be used to shift the types of compression used. Highest compression is obtained when more data is stored in run length blocks of single colors and lowest compression when more data is stored as two colors with a 32-bit bitmap for each 4×4 block. One type of compression used provides anti-aliasing.

Claims

1. A method for compressing digital video color data comprising the steps of:

considering the video data in blocks of n×

n pixels;

determining two diverse colors for each of said blocks by examining the n² pixels in each of said blocks;

determining if the difference in said two diverse colors for each of said blocks is greater than a first threshold value, and

if said difference is greater than said first threshold value, representing said block with four colors and a 2 n×

n bitmap, two of said four colors being intermediate colors calculated from said two diverse colors, said bitmap for selecting among said four colors,

if said difference is less than said first threshold value, representing said block as one color.

2. The method defined by claim 1 wherein, if said one color for a plurality of adjacent ones of said blocks are different by less than a second threshold value, representing said adjacent blocks by a single color and an instruction representing the number of said adjacent ones of said blocks.

3. The method defined by claim 1 wherein said step of determining said two diverse colors comprises the steps of:

determining the mean luminance of said n² pixels in each of said blocks;

computing one diverse color by averaging the colors of those of said pixels having a luminance greater than said mean luminance;

determining the other of said diverse colors by averaging the one of said pixels having a luminance less than said mean luminance.

4. A method for compressing digital video color data comprising the steps of:

considering the video data in blocks of n×

n pixels;

determining two diverse colors for each of said blocks by examining the n² pixels in each of said blocks;

comparing the difference in said two diverse colors for each of said blocks with a threshold value;

if said difference is greater than said threshold value, computing two intermediate colors from said diverse colors and computing a 2 n×

n bitmap said 2 n×

n bitmap for selecting among said two diverse colors and said two intermediate colors;

if said difference is less than said threshold value, representing said block as two colors and an n×

n bitmap.

5. The method defined by claim 4 wherein said step of determining said two diverse colors comprises the steps of:

determining the mean luminance of said n² pixels in each of said blocks;

computing one diverse color by averaging the colors of those of said pixels having a luminance greater than said means luminance;

determining the other of said diverse colors by averaging the one of said pixels having a luminance less than said mean luminance.

6. A method for compressing digital video color data comprising the steps of:

considering the data in blocks of n×

n pixels;

determining two diverse colors for each of said blocks by examining the n² pixels in each of said blocks;

determining if the difference in said two diverse colors for each of said blocks is greater than a first threshold value;

determining if the difference in said two diverse colors for each of said blocks is greater than a second threshold value;

if said difference is greater than said first threshold value, representing said block as two colors and an n×

n bitmap;

if said difference is greater than said second threshold value then;

determining two extended diverse colors;

determining two intermediate colors;

preparing a bitmap representing the closest one of said two extended diverse colors and said two intermediate colors for each of said pixels in said n×

n block.

7. A method for compressing digital video color data for an n×

n block of pixels comprising the steps of;

determining two diverse colors by examining said color data for said pixels in said n×

n block;

calculating from said two diverse colors a plurality of intermediate colors falling between said two diverse colors;

determining the closest one of said two diverse colors and said plurality of intermediate colors for each of said pixels in said n×

n block;

preparing a bitmap representing said closest one of said two diverse colors and said plurality of intermediate colors for each of said pixels in said n×

n block.

8. A method for compressing digital video color data for an n×

n block of pixels comprising the steps of;

determining two diverse colors by examining said color data for said pixels in said n×

n block;

determining two extended diverse colors from said two diverse colors;

determining a plurality of intermediate colors falling between said two extended diverse colors;

determining the closest one of said two extended diverse colors and said plurality of intermediate colors for each of said pixels in each of said n×

n block;

preparing a bitmap representing said closest one of said two extended diverse colors and said plurality of intermediate colors for each of said pixels in said n×

n block.

9. The method defined by claim 8 wherein n is equal to 4, 2 intermediate colors are used and wherein said bitmap representation comprises 32 bits.

10. The method defined by claim 8 wherein n is equal to 4, 6 intermediate colors are used and wherein said bitmap representation comprises 48 bits.

11. The method defined by claim 8 wherein n is equal to 4, 14 intermediate colors are used and wherein said bitmap representation comprises 64 bits.

12. The method defined by claim 8 wherein n is equal to 8, 2 intermediate colors are used and wherein said bitmap representation comprises 128 bits.

13. The method defined by claim 8 wherein n is equal to 8, 6 intermediate colors are used and wherein said bitmap representation comprises 192 bits.

14. The method defined by claim 8 wherein n is equal to 8, 14 intermediate colors are used and wherein said bitmap representation comprises 256 bits.

15. The method defined by claim 8, including the step of storing said compressed digital video color data by storing said 2 extended diverse colors and said bitmap.

16. The method defined by claim 8, including the following steps for decompressing said compressed digital video color data;

redetermining said plurality of intermediate colors from said two extended diverse colors;

selecting from said two extended diverse colors and said plurality of intermediate colors a color for each pixel in said n×

n block as a function of said bitmap.

17. The method defined by claim 8, including the following steps for decompressing said compressed digital video color data;

redetermining said plurality of intermediate colors from said two diverse colors;

selecting from said two diverse colors and said plurality of intermediate colors a color for each pixel in said n×

n block as a function of said bitmap.

18. An apparatus for compressing digital video color data comprising;

a buffer for storing n scan lines of pixel data;

first computational means for determining for each n×

n block of pixels in said buffer two diverse colors, said first computational means being coupled to said buffer;

second computational means for determining for each n×

n block of pixels two extended diverse colors, said second computational means coupled to said first computational means.

register means for storing a color threshold value;

comparator means coupled to said storage means and said first computational means for determining if the difference between said diverse colors is greater than said color threshold value;

storage means for storing each n×

n block as two extended diverse colors and a bitmap if the output of said comparator means indicates that the difference in said two diverse colors is greater than said color threshold value, and for storing each n×

n block as a single color if the output of said comparator means indicates that the difference between said two diverse colors is less than said color threshold value, said storage means being coupled to said second computational means and said comparator means.

19. A method for compressing digital video color data for storage or transmission comprising the steps of:

considering the video data in blocks each having an equal number of pixels;

determining if the color differences among the colors in each block are greater than a predetermined amount;

if said differences are greater than said predetermined amount, representing said block by two representative diverse colors and at least two intermediate colors computed from said two diverse representative colors, and bitmap data to select the closest color for each color in each block from among said two representative diverse colors and said intermediate colors;

if said differences are less than said predetermined amount representing said block as one color.

20. The method defined by claim 19 wherein if said one color for a plurality of adjacent ones of said blocks is approximately the same, representing said adjacent blocks by a single color and an instruction indicating the number of said adjacent blocks.

21. The method defined by claims 19 or 20 wherein said intermediate colors are discarded prior to said storing or transmission.

22. The method defined by claim 21 wherein said two representative diverse colors are extended diverse colors.

23. The method defined by claim 22 wherein each of said blocks are 4×

4 blocks.

24. The method defined by claim 23 wherein said selection of said closest color to said two representative diverse colors and said intermediate colors for said bitmap data occurs by examining the luminance values of said representative diverse colors and said intermediate colors, and the luminance value of the color associated with each pixel.

25. A method for compressing digital video color data for storing or transmission, comprising the steps of:

considering the video data in blocks each having an equal number of pixels;

determining two representative diverse colors for each block by examining the video data in each of said blocks;

representing said block by said two representative diverse colors and at least two intermediate colors computed from said two representative diverse colors and bitmap data which indicates the closest color for each color in each block to said two representative diverse colors and said intermediate colors;

discarding said intermediate colors prior to said storing or transmission.

26. The method defined by claim 25 wherein said two representative diverse colors are extended diverse colors.