Block-based image compression method and apparatus

• US 7,606,429 B2
• Filed: 03/25/2005
• Issued: 10/20/2009
• Est. Priority Date: 03/25/2005
• Status: Active Grant

• Current Assignee: ATI Technologies ULC (Advanced Micro Devices, Inc.)
• Original Assignee: ATI Technologies ULC (Advanced Micro Devices, Inc.)
• Inventors: Aleksic, Milivoje, Ogden, Charles D., Munshi, Aaftab
• Primary Examiner(s): Kassa; Yosef
• Application Number:
  US11/090,378
• Publication Number:
  US 20060215914A1
• Time in Patent Office: 1,670 Days
• Field of Search: 382/232, 382/235, 382/244, 382/251, 382/274, 358/3.26, 358/3.27, 358/463
• US Class Current: 382/232
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/426 using memory downsizing methods
• CPC Class Codes: H04N 19/94 Vector quantisation

Abstract

A block-based image compression method and encoder/decoder circuit compresses a plurality of pixels having corresponding original color values and luminance values in a block according to different modes of operation. The encoding circuit includes a luminance-level-based representative color generator to generate representative color values for each of a plurality of luminance levels derived from the corresponding luminance levels to produce at least a block color offset value and a quantization value. According to mode zero, each of the pixels in the block is associated with one of the plurality of generated representative color values to generate error map values and a mode zero color error value. According to mode one, representative color values for each of at least three luminance levels are also generated to produce at least three representative color values, corresponding bitmap values and a mode one color error value. A mode based compressed data generator is capable of operating in mode zero and/or one and produces block color mode zero data when the mode zero color error value is less than the mode one color error value, otherwise block color mode one data.

Claims

1. A method of compressing a plurality of pixels in a block, each pixel in the block having an original color value and a corresponding luminance level, the method comprising:

generating representative color values for each of a plurality of luminance levels derived from the corresponding luminance levels to produce at least a high color value and a low color value, and in response associating each of the pixels in the block with one of the plurality of generated representative color values to produce a block color offset value and a quantization value;

generating a pixel color error value for each of the pixels in the block, based on the original color values corresponding with each pixel in the block, the block color offset value and the quantization value, to produce error map values and a mode zero color error value;

generating at least three representative color values for each of at least three luminance levels, to produce a mode one color error value, and in response associating each of the pixels in the block with one of the at least three generated representative color values to produce corresponding bitmap values; and

generating block color mode zero data when the mode zero color error value is less than the mode one color error value, otherwise generating block color mode one data.

2. The method of claim 1 including:

reassociating at least one pixel in the block with at least one other representative color value in response to generating the pixel color error value for each of the pixels in the block.

3. The method of claim 1, wherein at least one of:

the mode zero color error value and the mode one color error value corresponds with at least one of;

an absolute color error value, a mean square color error value, and a mean color error value.

4. The method of claim 1, wherein generating the representative color values includes averaging the color values corresponding with the pixels assigned to each of the luminance levels to generate an average color value for each of the luminance levels.

5. The method of claim 1, wherein generating the representative color values further includes selecting representative color values corresponding with at least one of:

a minimum mode zero color error value and a minimum mode one color error value.

6. The method of claim 1, including:

sending a data structure including at least the block color offset value, the quantization value and the error map values in response to generating the block color mode zero data; and

sending a data structure including at least the high color value, the low color value and the bitmap values in response to generating the block color mode one data.

7. A method of compressing a plurality of pixels in a block, each pixel in the block having an original color value and a corresponding luminance value, the method comprising:

generating representative color values for each of a plurality of luminance levels derived from the corresponding luminance levels to produce at least a high color value, a low color value, a block color offset value and a quantization value;

grouping each of the color values for the pixels in the block amongst the representative color values and, in response, selecting a grouping of color values such that the selected representative color values correspond with a minimum color error with respect to the color values in the block;

associating each of the pixels in the block with one of the plurality of selected representative color values to produce a mode zero color error value;

generating a pixel color error value for each of the pixels in the block, based on the original color values corresponding with each pixel in the block, the block color offset value and the quantization value, to produce error map values;

generating at least three representative color values for each of at least three luminance levels to produce a mode one color error value, and in response associating each of the pixels in the block with one of the at least three generated representative color values to produce corresponding bitmap values; and

generating block color mode zero data when the mode zero color error value is less than the mode one color error value, otherwise generating block color mode one data.

8. The method of claim 7, including:

reassociating each pixel in the block with at least one other representative color level in response to generating the pixel color error value for each of the pixels in the block.

9. The method of claim 7, wherein generating the representative color values includes averaging the color values corresponding with the pixels assigned to each of the luminance levels to generate an average color value for each of the luminance levels.

10. The method of claim 7, wherein at least one of:

the mode zero color error value and the mode one color error value corresponds with at least one of;

an absolute color error value, a mean square color error value, and a mean color error value.

11. The method of claim 7, including:

sending a data structure including at least the block color offset value, the quantization value and the error map values in response to generating the block color mode zero data; and

sending a data structure including at least the high color value, the low color value and the bitmap values in response to generating the block color mode one data.

12. A method of compressing a plurality of pixels in a block, each pixel in the block having an original color value and a corresponding luminance value, the method comprising:

generating a plurality of representative luminance values derived from the corresponding luminance levels, and in response, associating each of the pixels in the block with one of the plurality of representative luminance values;

generating representative color values for each of the plurality of luminance levels to produce at least a high color value, a low color value, a block color offset value and a quantization value;

grouping each of the original color values for the pixels in the block amongst the representative luminance values, and in response selecting a grouping of original color values such that the corresponding representative color values correspond with a minimum color error with respect to the original color values in the block;

associating each of the pixels in the block with one of the plurality of selected representative color values to produce a mode zero color error value;

generating a pixel color error value for each of the pixels in the block, based on the original color values corresponding with each pixel in the block, the block color offset value and the quantization value, to produce error map values;

generating at least three representative color values for each of at least three luminance levels to produce a mode one color error value, and in response associating each of the pixels in the block with one of the at least three generated representative color values to produce corresponding bitmap values; and

generating block color mode zero data when the mode zero color error value is less than the mode one color error value, otherwise generating block color mode one data.

13. The method of claim 12, wherein generating the plurality of representative luminance values further includes:

sorting the plurality of pixels in the block according to the luminance values; and

grouping the sorted luminance values and in response, selecting the representative luminance values for each group of luminance values such that the selected plurality of representative luminance values corresponds with a minimum error luminance value in the block.

14. The method of claim 12, including:

reassigning each pixel in the block to at least one other representative luminance level in response to generating the pixel color error value for each of the pixels in the block.

15. The method of claim 12, wherein generating the representative color values for each of the luminance levels includes averaging the color values corresponding with the pixels assigned to each of the luminance levels to generate an average color value for each of the luminance levels.

16. The method of claim 12, wherein at least one of:

the mode zero color error value and the mode one color error value corresponds with at least one of;

an absolute color error value, a mean square color error value, and a mean color error value.

17. The method of claim 12, including:

sending a data structure including at least the block color offset value, the quantization value and the error map values in response to generating the block mode zero data; and

sending a data structure including at least the high color value, the low color value and the bitmap values in response to generating the block mode one data.

18. An encoder circuit to compress a plurality of pixels in a block, each pixel in the block having an original color value and a corresponding luminance level, the encoder circuit comprising:

a luminance level based representative color generator operative to;

generate representative color values for each of a plurality of luminance levels derived from the corresponding luminance levels to produce at least a high color value and a low color value, and in response associate each of the pixels in the block with one of the plurality of generated representative color values to produce a block color offset value and a quantization value;

generate a pixel color error value for each of the pixels in the block, based on the original color values corresponding with each pixel in the block, the block color offset value and the quantization value, to produce error map values and a mode zero color error value;

generate at least three representative color values for each of at least three luminance levels to produce a mode one color error value, and in response associate each of the pixels in the block with one of the at least three generated representative color values to produce corresponding bitmap values; and

a mode based compressed data generator operative to generate block color mode zero data when the mode zero color error value is less than the mode one color error value, otherwise generate block color mode one data.

19. The encoder circuit of claim 18, wherein the luminance-level-based representative color generator is operative to:

reassociate at least one pixel in the block with at least one other representative luminance level in response to generating the pixel color error value for each of the pixels in the block.

20. The encoder circuit of claim 18, wherein the luminance level based representative color generator is operative to generate at least one of:

the mode zero color error value and the mode one color error value, according to at least one of;

an absolute color error value, a mean square color error value and a mean color error value.

21. The encoder circuit of claim 18, wherein the luminance-level-based representative color generator generates the representative color values based on averaging the color values corresponding with the pixels assigned to each of the luminance levels to generate an average color value for each of the luminance levels.

22. The encoder circuit of claim 18, wherein the luminance-level-based representative color generator selects representative color values corresponding with at least one of:

a minimum mode zero color error value and a minimum mode one color error value.

23. The encoder circuit of claim 18, further including:

memory operatively coupled to the luminance level based representative color generator, the memory having a data structure including;

at least the block color offset value, the quantization value and the error map values when the block color mode zero data is generated; and

at least the high color value, the low color value, and the bitmap values when the block color mode one data is generated.

24. An encoder circuit to compress a plurality of pixels in a block, each pixel in the block having an original color value and a corresponding luminance level, the encoder circuit comprising:

a luminance-based pixel grouping generator operative to generate a plurality of representative luminance values derived from the corresponding luminance levels, and in response associate each of the pixels in the block with one of the plurality of representative luminance values;

a representative color generator, operatively coupled to the luminance-based pixel grouping generator and operative to;

generate representative color values for each of the plurality of luminance levels to produce at least a high color value, a low color value, a block color offset value and a quantization value;

group each of the original color values for the pixels in the block amongst the representative luminance values and, in response, select a grouping of original color values such that the corresponding representative color values correspond with a minimum color error with respect to the color values in the block;

associate each of the pixels in the block with one of the plurality of selected representative color values to produce a mode zero color error value;

generate a pixel color error value for each of the pixels in the block, based on the original color values corresponding with each pixel in the block, the block color offset value and the quantization value, to produce error map values; and

generate at least three representative color values for each of at least three luminance levels to produce a mode one color error value, and in response associate each of the pixels in the block with one of the at least three generated representative color values to produce corresponding bitmap values; and

a mode based compressed data generator operative to generate block color mode zero data when the mode zero color error value is less than the mode one color error value, otherwise generate block color mode one data.

25. The encoder circuit of claim 24, wherein the luminance based pixel grouping generator is operative to:

reassociate at least one pixel in the block with at least one other representative luminance value in response to generating the pixel color error value for each of the pixels in the block.

26. The encoder circuit of claim 24, wherein the representative color value generator is operative to generate at least one of:

the mode zero color error value and the mode one color error value, according to at least one of;

an absolute color error value, a mean square color error value and a mean color error value.

27. The encoder circuit of claim 24,

memory operatively coupled to the mode based compressed data generator, the memory having a data structure including:

at least the block color offset value, the quantization value and the error map values including the pixel color error values for each of the pixels in the block in response to the generated block color mode zero data; and

at least the high color value, the low color value and the bitmap values in response to generating the block color mode one data.

28. Memory containing instructions executable by one or more processing devices that cause the one or more processing devices to:

receive a plurality of pixels in a block, each pixel in the block having an original color value and a corresponding luminance level;

generate representative color values for each of a plurality of luminance levels derived from the corresponding luminance levels to produce at least a high color value and a low color value, and in response associate each of the pixels in the block with one of the plurality of generated representative color values to produce a block color offset value and a quantization value;

generate a pixel color error value for each of the pixels in the block, based on the original color values corresponding with each pixel in the block, the block color offset value and the quantization value, to produce error map values and a mode zero color error value;

generate at least three representative color values for each of at least three luminance levels to produce a mode one color error value, and in response associate each of the pixels in the block with one of the at least three generated representative color values to produce corresponding bitmap values; and

generate block color mode zero data when the mode zero color error value is less than the mode one color error value, otherwise generate the block color mode one data.

29. The memory of claim 28 containing executable instructions that cause the one or more processing devices to:

reassign at least one pixel in the block to at least one other representative color value in response to generating the pixel color error value for each of the pixels in the block.

30. The memory of claim 28 containing executable instructions that cause the one or more processing devices to send a data structure including:

at least the block color offset value, the quantization value and the error map values in response to generating the block mode zero data; and

at least the high color value, the low color value and the bitmap values in response to generating the block color mode one data.

31. A decoding method for generating a plurality of pixels in a block comprising:

receiving at least one of;

block color mode zero data and block color mode one data;

in response to receiving the block color mode zero data;

receiving at least a block color offset value, a quantization value and error map values, and in response generating a high color value, a mid-high color value, a mid-low color value and a low color value; and

associating the generated high color value, the generated mid-high color value, the generated mid-low color value and the generated low color value with each pixel in the block according to the error map values; and

in response to receiving the block color mode one data, receiving at least a high color value, a mid-low color value, a low color value and bitmap values and in response associating at least one of;

the received high color value, the received mid-low color value and the received low color value with each pixel in the block according to the bitmap values.

32. The decoder method of claim 31, including generating block color values for each pixel in the block in response to associating each of the pixels in the block in accordance with at least one of:

the error map values and the bitmap values.

33. A decoder circuit including:

an N-level color information generator, operative to;

receive at least one of;

block color mode zero data and block color mode one data;

in response to receiving the block color mode zero data;

receive at least a block color offset value, a quantization value and error map values including pixel color error values for each of the pixels in the block, and in response generate a high color value, a mid-high color value, a mid-low color value and a low color value;

in response to receiving the block color mode one data;

receive at least a high color value, a mid color value, a low color value and bitmap values; and

a block color information generator, operatively coupled to the N-level color information generator, and operative to;

associate the generated high color value, the generated mid-high color value, the generated mid-low color value and the generated low color value according to the error map values in response to the block color mode zero data; and

associate at least one of;

the received high color value, the received mid-low color value and the received low color value with each pixel in the block according to the bitmap values in response to the block color mode one data.

34. The decoder circuit of claim 33, wherein the N-level color information generator is operative to:

generate block color values for each pixel in the block in response to associating each of the pixels in the block in according with at least one of;

the error map values and the bitmap values.

35. A graphics processor operative to compress a plurality of pixels in a block, each pixel in the blocking having a corresponding original color value and a corresponding luminance value, the graphics processor including:

an encoder circuit comprising;

a luminance level based representative color generator operative to;

generate representative color values for each of a plurality of luminance levels derived from the corresponding luminance levels to produce at least a high color value and a low color value and in response associate each of the pixels in the block with one of the plurality of generated representative color values to produce a block color offset value and a quantization value;

generate a pixel color error value for each of the pixels in the block, based on the original color values corresponding with each pixel in the block, the block color offset value and the quantization value, to produce error map values and a mode zero color error value;

generate at least three representative color values for each of at least three luminance levels to produce a mode one color error value, and in response associate each of the pixels in the block with one of the at least three generated representative color values to produce corresponding bitmap values; and

a mode based compressed data generator operative to;

generate block color mode zero data when the mode zero color error value is less than the mode one color error value, otherwise generate the block color mode one data.

36. The graphics processor of claim 35, further including:

memory operatively coupled to the block color type generator, the memory having a data structure including;

at least the block color offset value, the quantization value and the error map values including the pixel color error values for each of the pixels in the block in response to the generated block color mode zero data; and

at least the high color value, the low color value and the bitmap values in response to the generated block color mode one data.

37. A network element operative to compress a plurality of pixels in a block, each pixel in the blocking having a corresponding original color value and a corresponding luminance value, the network element including:

an encoder circuit comprising;

a luminance level based representative color generator operatively coupled to the receiver and operative to;

generate representative color values for each of a plurality of luminance levels derived from the corresponding luminance levels to produce at least a high color value and a low color value and in response associate each of the pixels in the block with one of the plurality of generated representative color values to produce a block color offset value and a quantization value;

generate a pixel color error value for each of the pixels in the block, based on the original color values corresponding with each pixel in the block, the block color offset value and the quantization value, to produce error map values and a mode zero color error value;

generate at least three representative color values for each of at least three luminance levels to produce a mode one color error value, and in response associate each of the pixels in the block with one of the at least three generated representative color values to produce corresponding bitmap values;

a mode based compressed data generator operative to;

generate block color mode zero data when the mode zero color error value is less than the mode one color error value, otherwise generate block color mode one data; and

a transmitter, operatively coupled to the mode based compressed data generator and operative to transmit at least one of;

(a) at least the block color offset value, the quantization value and the error map values and (b) at least the high color value, the low color value and the bitmap values.

38. The network element of claim 37, further including:

memory operatively coupled to the block color type generator, the memory having a data structure including;

at least the block color offset value, the quantization value and the error map values including the pixel color error values for each of the pixels in the block in response to the generated block color mode zero data; and

at least the high color value, the low color value and the bitmap values in response to the generated block color mode one data.

39. A method of compressing a plurality of pixels in a block, each pixel in the block having an original corresponding color value and a corresponding luminance value, the method comprising:

generating representative color values for each of a plurality of luminance levels derived from the corresponding luminance levels to produce at least a high color value, a low color value, a block color offset value and a quantization value and in response associating each of the pixels in the block with one of the plurality of generated representative color values; and

generating a pixel color error value for each of the pixels in the block, based on the original color values corresponding with each pixel in the block, the block color offset value and the quantization value, to produce error map values.

40. The method of claim 39 wherein generating the representative color values further includes selecting representative color values corresponding with at least one of:

a minimum mode zero color error value and a minimum mode one color error value.

41. The method of claim 39 including:

reassociating at least one pixel in the block with at least one other representative color value.

42. The method of claim 39, wherein generating the representative color values includes averaging the color values corresponding with the pixels assigned to each of the luminance levels to generate an average color value for each of the at least four luminance levels.

43. The method of claim 39, including:

sending a data structure including at least the block color offset value, the quantization value and the error map values.

44. A method of compressing a plurality of pixels in a block, each pixel in the block having an original corresponding color value and a corresponding luminance value, the method comprising:

generating at least three representative color values for each of at least three luminance levels derived from the corresponding luminance levels to produce at least a high color value, a low color value and a mid color value and in response associating each of the pixels in the block with one of the at least three generated representative color values to produce corresponding bitmap values; and

generating block color mode data indicating a diverse color mode.

45. The method of claim 44 including:

sending the at least the high color value, the mid color value, the low color value and the bitmap values as a data bit structure.