METHOD AND APPARATUS FOR BLOCK BASED IMAGE COMPRESSION WITH MULTIPLE NON-UNIFORM BLOCK ENCODINGS

• US 20090274366A1
• Filed: 06/16/2009
• Published: 11/05/2009
• Est. Priority Date: 02/13/2003
• Status: Active Grant

• Current Assignee: ATI Technologies ULC (Advanced Micro Devices, Inc.)
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Iourcha, Konstantine, Koduri, Raja, Pomianowski, Andrew S. C.
• Granted Patent: US 8,326,053 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;

decomposing each of said plurality of pixel blocks to generate a plurality of decomposed blocks;

compressing each of said plurality of decomposed blocks to generate a plurality of compressed blocks;

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

wherein said decomposing is optimized for each of said plurality of pixel blocks to reduce loss of image quality.

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 decomposed 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 optimization of each of said plurality of pixel blocks further comprises:

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

decompressing said first compressed subset;

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

compressing second subset.

15. The method of claim 1 wherein decomposing each of said plurality of pixel blocks further comprises:

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

decompressing said first compressed subset;

feeding results of decompressing of first compressed subset to a decomposer device that changes the data value of a second subset comprising of one or more decomposed 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 decomposer 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.

16. The method of claim 1 wherein decomposing each of said plurality of pixel blocks further comprises:

projecting an original block onto a predefined vector;

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

17. The method of claim 1 wherein decomposing each of said plurality of pixel blocks further comprises:

projecting an original block onto a predefined vector;

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.

18. An image compression system comprising:

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

a decomposer unit configured to decompose each of said plurality of pixel blocks to generate a plurality of decomposed blocks;

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

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

wherein said decomposing by the decompser unit is optimized for each of said plurality of pixel blocks to reduce loss of image quality.

19. The image compression system of claim 18 wherein said image is a texture.

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

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

22. The image compression system of claim 18 wherein said compression unit uses one or more compression techniques.

23. The image compression system of claim 18 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.

24. The image compression system of claim 23 wherein said collection of possible colors comprises:

colors of said two points.

25. The image compression system of claim 23 wherein said collection of possible colors comprises:

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

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

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

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

29. The image compression system of claim 23 wherein said first pixel value is an RGB value.

30. The image compression system of claim 23 wherein said first pixel value is a YCrCb value.

31. The image compression system of claim 18 further comprising:

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

32. The image compression system of claim 18 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.

33. The image compression system of claim 18 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 decomposed 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 decomposer device that changes the data value of a second subset comprising of one or more decomposed 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.

34. The image compression system of claim 18 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;

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.

35. The image compression system of claim 18 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;

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.