Method and apparatus for block based image compression with multiple non-uniform block encodings

• US 20040228527A1
• Filed: 02/13/2004
• Published: 11/18/2004
• Est. Priority Date: 02/13/2003
• Status: Active Grant

• Current Assignee: ATI Technologies ULC (Advanced Micro Devices, Inc.)
• Original Assignee: ATI Technologies ULC (Advanced Micro Devices, Inc.)
• Inventors: Iourcha, Konstantine, Koduri, Raja, Pomianowski, Andrew S.C.
• Granted Patent: US 7,643,679 B2
• Time in Patent Office: Days
• US Class Current: 382/166
• CPC Class Codes: G06T 15/04 Texture mapping
• CPC Class Codes: H04N 19/96 Tree coding, e.g. quad-tree coding

Abstract

Embodiments of the present invention are directed to a method and apparatus for block based image compression with multiple non-uniform block encodings. In one embodiment, an image is divided into blocks of pixels. In one embodiment the blocks are four pixels by four pixels, but other block sizes are used in other embodiments. In one embodiment, a block of pixels in the original image is compressed using two different methods to produce a first and second compressed block. Thus, each block in the original image is represented by two, typically different, compressed blocks. In one embodiment, color associated with a pixel is determined by combining the compressed information about the pixel in the first compressed block with information about the pixel in the second compressed block. In another embodiment, global information about the image is combined with the information in the first and second compressed blocks.

Claims

1. A method for compressing an image comprising:

partitioning said image into a plurality of pixel blocks;

decompressing each of said plurality of pixel blocks to generate a plurality of decompress blocks;

compressing each of said plurality of decompress blocks to generate a plurality of compressed blocks; and

combining each of said plurality of compressed blocks to generate an output block.

2. The method of claim 1 wherein said image is a texture.

3. The method of claim 1 wherein said first pixel block is four pixels by four pixels.

4. The method of claim 1 wherein said first pixel block has 24 bits for each pixel.

5. The method of claim 1 wherein said compressing uses one or more compression techniques.

6. The method of claim 1 wherein said step of compressing each of said plurality of decompress blocks comprises:

determining a best fit curve in a color space;

storing two points of said best fit curve; and

storing an index value for a first pixel value in said first pixel block wherein said index maps to a collection of possible colors.

7. The method of claim 6 wherein said collection of possible colors comprises:

colors of said two points.

8. The method of claim 6 wherein said collection of possible colors comprises:

an interpolated value wherein said interpolated value is on said best fit curve.

9. The method of claim 6 wherein said two points are 16-bit values.

10. The method of claim 6 wherein said index value is a 2-bit value.

11. The method of claim 6 wherein said two points are endpoints of said best fit curve.

12. The method of claim 6 wherein said first pixel value is an RGB value.

13. The method of claim 6 wherein said first pixel value is a YCrCb value.

14. The method of claim 1 wherein said step of compressing each of said plurality of decompress blocks comprises:

applying a function to a first pixel value to produce an altered first pixel value;

determining a best fit curve in a color space;

storing two points of said best fit curve; and

storing an index value for said altered first pixel value in said first pixel block wherein said index maps to a collection of possible colors.

15. The method of claim 14 wherein said collection of possible colors comprises:

colors of said two points.

16. The method of claim 14 wherein said collection of possible colors comprises:

an interpolated value wherein said interpolated value is on said best fit curve.

17. The method of claim 14 wherein said two points are 8-bit values.

18. The method of claim 14 wherein said index value is a 3-bit value.

19. The method of claim 14 wherein said two points are endpoints of said best fit curve.

20. The method of claim 14 wherein said first pixel value has more bits than said altered pixel value.

21. The method of claim 14 wherein said function is an averaging function.

22. The method of claim 21 wherein said function averages a red component, a green component and a blue component.

23. The method of claim 14 wherein said first pixel value is an RGB value.

24. The method of claim 14 wherein said first pixel value is a YCrCb value.

25. The method of claim 1 further comprising:

storing a set of global data for use in decompressing said image.

26. The method of claim 1 wherein said decompressing is optimized for each of said plurality of pixel blocks to reduce loss of image quality.

27. The method of claim 26 wherein optimization of each of said plurality of pixel blocks further comprises:

compressing a first subset comprising of one or more decompress blocks to generate a first compressed subset;

decompressing said first compressed subset;

feeding results of decompressing of first compressed subset to a decompress device that changes the data value of a second subset comprising of one or more decompressed blocks different from first subset; and

compressing second subset.

28. The method of claim 26 wherein optimization of each of said plurality of pixel blocks further comprises:

compressing a first subset comprising of one or more decompressed blocks to generate a first compressed subset;

decompressing said first compressed subset;

feeding results of decompressing of first compressed subset to a decompress device that changes the data value of a second subset comprising of one or more decompressed blocks different from first subset to generate a new second subset;

compressing said new second subset;

decompressing said new second subset;

feeding results of decompressing of new second subset to said decompress device that changes the data value of said first subset; and

repeating steps of compressing, decompressing, and feeding of said first subset and repeating steps of compressing, decompressing, and feeding of said new second subset until a threshold is achieved.

29. The method of claim 26 wherein optimization of each of said plurality of pixel blocks further comprises:

projecting an original block onto a predefined vector to generate a projected;

concurrently storing a magnitude of said original block in a first new block and subtracting said projected block from said original block.

30. The method of claim 26 wherein optimization of each of said plurality of pixel blocks further comprises:

projecting an original block onto a predefined vector to generate a projected;

storing a magnitude of said original block in a first new block;

compressing said first new block to generate a compressed first block;

decompressing said compressed first block to generate a decompressed block;

subtracting data value of said decompressed block from data value of said original block to generate a new second block;

compressing said new second block to generate a compressed second block; and

combining said compressed first block and said compressed second block.

31. The method of claim 26 wherein optimization of each of said plurality of pixel blocks further comprises:

projecting an original block onto a predefined vector to generate a projected;

storing a magnitude of said original block in a first new block;

compressing said first new block to generate a compressed first block;

decompressing said compressed first block to generate a first decompressed block;

subtracting data value of said first decompressed block from data value of said original block to generate a new second block;

compressing said new second block to generate a compressed second block;

decompressing said compressed second block to generate a second decompressed block;

subtracting data value of said second decompressed block from data value of said original block and storing results in a third block;

subtracting data value of said third block from data value of said original block and storing the results in said first new block;

repeating steps of storing, compressing, decompressing, and subtracting of said first new block, repeating steps of compressing, decompressing, and subtracting of said new second block, and repeating steps of subtracting of said third block until a threshold is achieved; and

combining said compressed first block with said compressed second block.

39. The image compression system of claim 29 wherein said collection of possible colors comprises:

an interpolated value wherein said interpolated value is on said best fit curve.

32. An image compression system comprising:

a partitioner configured to partition an image into a plurality of pixel blocks;

a decompression unit configured to decompress each of said plurality of pixel blocks to generate a plurality of decompress blocks;

a compression unit configured to compress each of said plurality of decompress blocks to generate a plurality of compressed blocks; and

a combining unit configured to combine each of said plurality of compressed blocks to generate an output block.

33. The image compression system of claim 32 wherein said image is a texture.

34. The image compression system of claim 32 wherein said first pixel block is four pixels by four pixels.

35. The image compression system of claim 32 wherein said first pixel block has 24 bits for each pixel.

36. The image compression system of claim 32 wherein said compression unit uses one or more compression techniques.

37. The image compression system of claim 32 wherein said first compression unit comprises:

a determiner configured to determine a best fit curve in a color space; and

a storage device configured to store two points of said best fit curve, wherein said storage device is further configured to store an index value for a first pixel value in said first pixel block wherein said index maps to a collection of possible colors.

38. The image compression system of claim 37 wherein said collection of possible colors comprises:

colors of said two points.

40. The image compression system of claim 37 wherein said two points are 16-bit values.

41. The image compression system of claim 37 wherein said index value is a 2-bit value.

42. The image compression system of claim 37 wherein said two points are endpoints of said best fit curve.

43. The image compression system of claim 37 wherein said first pixel value is an RGB value.

44. The image compression system of claim 37 wherein said first pixel value is a YCrCb value.

45. The image compression system of claim 32 wherein said compression unit comprises:

a calculator configured to apply a function to a first pixel value to produce an altered first pixel value;

a determiner configured to determine a best fit curve in a color space; and

a storage unit configured to store two points of said best fit curve, wherein said storage unit is further configured to store an index value for said altered first pixel value in said first pixel block wherein said index maps to a collection of possible colors.

46. The image compression system of claim 45 wherein said collection of possible colors comprises:

colors of said two points.

47. The image compression system of claim 45 wherein said collection of possible colors comprises:

an interpolated value wherein said interpolated value is on said best fit curve.

48. The image compression system of claim 45 wherein said two points are 8-bit values.

49. The image compression system of claim 45 wherein said index value is a 3-bit value.

50. The image compression system of claim 45 wherein said two points are endpoints of said best fit curve.

51. The image compression system of claim 45 wherein said first pixel value has more bits than said altered pixel value.

52. The image compression system of claim 45 wherein said function is an averaging function.

53. The image compression system of claim 52 wherein said function averages a red component, a green component and a blue component.

54. The image compression system of claim 45 wherein said first pixel value is an RGB value.

55. The image compression system of claim 45 wherein said first pixel value is a YCrCb value.

56. The image compression system of claim 32 further comprising:

a second storage device configured to store a set of global data for use in decompressing said image.

57. The image compression system of claim 32 wherein said decompressing unit is optimized for each of said plurality of pixel blocks to reduce loss of image quality.

58. The image compression system of claim 57 wherein optimization of each of said plurality of pixel blocks further comprises:

a first compressing unit configured to compress a first subset comprising of one or more decompress blocks to generate a first compressed subset;

a decompressing unit configured to decompress said first compressed subset;

a feeding unit configured to feed results of decompression of first compressed subset to a decompress device that changes the data value of a second subset comprising of one or more decompressed blocks different from first subset; and

a second compressing unit configured to compress second subset.

59. The image compression system of claim 57 wherein optimization of each of said plurality of pixel blocks further comprises:

a first compression unit configured to compress a first subset comprising of one or more decompressed blocks to generate a first compressed subset;

a first decompressing unit configured to decompress said first compressed subset;

a first feeding unit configured to feed results of decompressing of first compressed subset to a decompress device that changes the data value of a second subset comprising of one or more decompressed blocks different from first subset to generate a new second subset;

a second compression unit configured to compress said new second subset;

a second decompressing unit configured to decompress said new second subset;

a second feeding unit configured to feed results of decompressing of new second subset to said decompress device that changes the data value of said first subset; and

a repeating unit configured to repeat steps of compress, decompress, and feed said first subset and repeating steps of compress, decompress, and feed said new second subset until a threshold is achieved.

60. The image compression system of claim 57 wherein optimization of each of said plurality of pixel blocks further comprises:

a projection unit configured to project an original block onto a predefined vector to generate a projected;

a device configured to concurrently store a magnitude of said original block in a first new block and subtract said projected block from said original block.

61. The image compression system of claim 57 wherein optimization of each of said plurality of pixel blocks further comprises:

a projection unit configure to project an original block onto a predefined vector to generate a projected;

a storing unit configured to store a magnitude of said original block in a first new block;

a first compression unit configured to compress said first new block to generate a compressed first block;

a decompression unit configured to decompress said compressed first block to generate a decompressed block;

a subtracting unit configured to subtract data value of said decompressed block from data value of said original block to generate a new second block;

a second compression unit configured to compress said new second block to generate a compressed second block; and

a combining unit configured to combine said compressed first block and said compressed second block.

62. The image compression unit of claim 57 wherein optimization of each of said plurality of pixel blocks further comprises:

a projection unit configured to project an original block onto a predefined vector to generate a projected;

a storing unit configured to store a magnitude of said original block in a first new block;

a first compressing unit configured to compress said first new block to generate a compressed first block;

a first decompressing unit configured to decompress said compressed first block to generate a first decompressed block;

a first subtracting unit configured to subtract data value of said first decompressed block from data value of said original block to generate a new second block;

a second compressing unit configured to compress said new second block to generate a compressed second block;

a second decompressing unit configured to decompress said compressed second block to generate a second decompressed block;

a second subtracting unit configured to subtract data value of said second decompressed block from data value of said original block and storing results in a third block;

a third subtracting unit configured to subtract data value of said third block from data value of said original block and storing the results in said first new block;

a repeating unit configured to repeat steps to store, compress, decompress, and subtract of said first new block, repeat steps to compress, decompress, and subtract of said new second block, and repeat steps to subtract said third block until a threshold is achieved; and

a combining unit configured to combine said compressed first block with said compressed second block.