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

• US 7,643,679 B2
• Filed: 02/13/2004
• Issued: 01/05/2010
• 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: Pomianowski, Andrew S. C., Iourcha, Konstantine, Koduri, Raja
• Primary Examiner(s): Do; Anh Hong
• Application Number:
  US10/778,902
• Publication Number:
  US 20040228527A1
• Time in Patent Office: 2,153 Days
• Field of Search: 382/232, 382/233, 382/243, 382/240, 382/168, 382/270, 382/239, 382/166, 382/236, 382/244, 382/245, 382/238, 382/246, 382/247, 358/1.3, 358/1.8, 358/1.9, 358/2.99, 358/466, 375/240.11, 375/240.25, 375/240.12, 375/240.26, 375/240.1, 375/E7.094, 375/240.24, 375/E7.047, 375/E7.049, 345/555, 345/545, 711/118, 347/11, 347/20, 341/50, 342/54, 342/123
• 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 by an image compression apparatus 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;

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

and wherein 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.

2. The method of claim 1 wherein said collection of possible colors comprises:

colors of said two points.

3. The method of claim 1 wherein said collection of possible colors comprises:

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

4. The method of claim 1 wherein said two points are 16-bit values.

5. The method of claim 1 wherein said index value is a 2-bit value.

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

7. The method of claim 1 wherein said first pixel value is an RGB value.

8. The method of claim 1 wherein said first pixel value is a YCrCb value.

9. A method for compressing an image by an image compression apparatus 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;

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

and 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 the second subset.

10. A method for compressing an image by an image compression apparatus 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;

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

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.

11. A method for compressing an image by an image compression apparatus 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;

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

and wherein decomposing each of said plurality of pixel blocks further comprises;

projecting an original block onto a predefined vector; and

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

12. A method for compressing an image by an image compression apparatus 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;

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

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.

13. 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;

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

and wherein said 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 farther 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.

14. The image compression system of claim 13 wherein said collection of possible colors comprises:

colors of said two points.

15. The image compression system of claim 13 wherein said collection of possible colors comprises:

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

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

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

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

19. The image compression system of claim 13 wherein said first pixel value is an RGB value.

20. The image compression system of claim 13 wherein said first pixel value is a YCrCb value.

21. 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 pluraliw of compressed blocks;

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

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

wherein optimization of each of said plurality of pixel blocks utilizes;

a first compressing unit configured to compress a first subset comprising of one or more decomposed 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 decomposer device that changes the data value of a second subset comprising of one or more decomposed blocks different from the first subset; and

a second compressing unit configured to compress the second subset.

22. 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;

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

wherein optimization of each of said plurality of pixel blocks utilizes;

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 decomposer 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.

23. 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;

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

wherein optimization of each of said plurality of pixel blocks utilizes;

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

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.

24. 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;

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

wherein optimization of each of said plurality of pixel blocks utilizes;

a projection unit configured 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.

25. A method for compressing an image by an image compression apparatus 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;

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

and wherein optimizing comprises conducting a series of functions on a first subset comprised of one or more decomposed blocks and applying the results to a second subset comprising of one or more decomposed blocks different from the ones in the first subset.