HIERARCHICAL LOSSLESS COMPRESSION

• US 20100299454A1
• Filed: 05/19/2009
• Published: 11/25/2010
• Est. Priority Date: 05/19/2009
• Status: Active Grant

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Lyashevsky, Alexander M.
• Granted Patent: US 8,810,562 B2
• Time in Patent Office: Days
• US Class Current: 709/247
• CPC Class Codes: H04N 19/96 Tree coding, e.g. quad-tree coding

Abstract

A method is provided for data compression. The data compression method transforms a square of data into a tile of data. The tile of data is then divided into quads of data that are converted into a representative element, a first delta element, a second delta element, a third delta element, and a control word. A new tile of data is then formed with the representative elements, and the process is repeated until a single representative element remains. The single representative element is then embedded into an output stream with the control words and corresponding delta elements. Decompression of the data is symmetrical to the encoding once the bit stream has been parsed.

Claims

1. A hierarchical data compression method comprising a computer performing the steps of:

compressing a plurality of primary subarrays into compressed subarrays such that a plurality of compressed subarrays are formed, wherein the plurality of primary subarrays form a primary array;

arranging the compressed subarrays into a secondary array; and

repeating the compressing and arranging until a single subarray remains, wherein the secondary array becomes the primary array for the repetition of said compressing and arranging.

2. The method of claim 1, further comprising the step of embedding data from the compressed subarrays into an output stream.

3. A data compression method comprising a computer performing the steps of:

providing a square of data;

transforming the square of data into a tile of data;

dividing the tile of data into quads of data, each quad having an upper left pixel, an upper right pixel, a lower left pixel, and a lower right pixel;

converting each quad into a representative element, a first delta element, a second delta element, a third delta element, and a control word;

forming a new tile of data with the representative elements;

repeating the dividing, the converting, and the forming until a single representative element remains, wherein the new tile of data becomes the tile of data for the repetition of the dividing, converting and forming steps; and

embedding the single representative element, the control words and the delta elements into an output stream.

4. The method of claim 3, wherein the square of data is a division of a two-dimensional surface of data.

5. The method of claim 3, wherein the data is at least one of:

Z-buffer data, color buffer data and normal map data.

6. The method of claim 5, wherein the step of transforming the square of data into a tile of data comprises replacing each data value with a new data value, the new data value being equal to the data value subtracted by an adjacent data value.

7. The method of claim 3, wherein the step of transforming the square of data into a tile of data comprises replacing each data value with a decorrelated data value.

8. The method of claim 3, wherein the step of transforming the square of data into a tile of data comprises replacing each data value with a new data value having one less component.

9. The method of claim 3, wherein the step of converting each quad comprises:

setting the upper left pixel as the representative element;

subtracting the upper right pixel by the upper left pixel, thereby forming the first delta element;

subtracting the lower left pixel by the upper left pixel, thereby forming the second delta element;

subtracting the lower right pixel by the lower left pixel, thereby forming the third delta; and

setting the control word according to a correlation between the delta elements.

10. The method of claim 3, wherein control information is embedded into the output stream.

11. The method of claim 3, wherein a directory of sub-tiles is embedded into the output stream, the directory of sub-tiles being formed from the results of the dividing, converting and forming steps.

12. The method of claim 3, wherein the embedding follows a sub-tile pattern.

13. The method of claim 3, further comprising the step of encoding the delta elements according to their associated control words.

14. A program storage device readable by a machine, tangibly embodying a program of instructions executable to perform a data compression method comprising:

providing a square of data;

transforming the square of data into a tile of data;

dividing the tile of data into quads of data, each quad having an upper left pixel, an upper right pixel, a lower left pixel, and a lower right pixel;

converting each quad into a representative element, a first delta element, a second delta element, a third delta element, and a control word;

forming a new tile of data with the representative elements;

repeating the dividing, the converting, and the forming until a single representative element remains, wherein the new tile of data becomes the tile of data for the repetition of the dividing, converting and forming steps; and

embedding the single representative element, the control words and the delta elements into an output stream.

15. The method of claim 14, wherein the square of data is a division of a two-dimensional surface of data.

16. The method of claim 14, wherein the data is at least one of:

Z-buffer data, color buffer data and normal map data.

17. The method of claim 16, wherein the step of transforming the square of data into a tile of data comprises replacing each data value with a new data value, the new data value being equal to the data value subtracted by an adjacent data value.

18. The method of claim 14, wherein the step of transforming the square of data into a tile of data comprises replacing each data value with a decorrelated data value.

19. The method of claim 14, wherein the step of transforming the square of data into a tile of data comprises replacing each data value with a new data value having one less component.

20. The method of claim 14, wherein the step of converting each quad comprises:

setting the upper left pixel as the representative element;

subtracting the upper right pixel by the upper left pixel, thereby forming the first delta element;

subtracting the lower left pixel by the upper left pixel, thereby forming the second delta element;

subtracting the lower right pixel by the lower left pixel, thereby forming the third delta; and

setting the control word according to a correlation between the delta elements.

21. The method of claim 14, wherein control information is embedded into the output stream.

22. The method of claim 14, wherein a directory of sub-tiles is embedded into the output stream, the directory of sub-tiles being formed from the results of the dividing, converting and forming steps.

23. The method of claim 14, wherein the embedding follows a sub-tile pattern.

24. The method of claim 14, further comprising the step of encoding the delta elements according to their associated control words.