Parallel Block Compression With a GPU

• US 20110157192A1
• Filed: 12/29/2009
• Published: 06/30/2011
• Est. Priority Date: 12/29/2009
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Jiaping, Ren, Peiran, Gong, Minmin
• Application Number:
  US12/648,699
• Publication Number:
  US 20110157192A1
• Time in Patent Office: Days
• US Class Current: 345/505
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: H04N 19/436 using parallelised computational arrangements
• CPC Class Codes: H04N 19/98 Adaptive-dynamic-range coding [ADRC]

Abstract

Disclosed is a system and method for determining, in parallel on a graphics processing unit, a block compression case which results in a least error to a block. Once determined, the block compression case may be used to compress the block.

Claims

1. One or more computer-readable storage media storing instructions that, when executed by a processor cause the processor to perform acts comprising:

accessing a pixel block comprising a plurality of original pixels;

determining a plurality of possible cases for compressing the pixel block;

evaluating the plurality of the possible cases in parallel by processing each of the possible cases on at least one of a plurality of graphics processing unit (GPU) cores;

determining a least error case from the evaluated plurality of possible cases; and

encoding the pixel block using the least error case.

2. The computer-readable storage media of claim 1, wherein the pixel block comprises texture data.

3. The computer-readable storage media of claim 1, wherein the determining the least error case comprises a parallel reduction of evaluated plurality of the possible cases.

4. The computer-readable storage media of claim 3, further comprising executing the parallel reduction on one or more of the plurality of GPU cores.

5. The computer-readable storage media of claim 1, wherein the evaluating comprises:

initializing a set of end points for the block;

optimizing the end points;

quantizing the end points;

encoding all pixels of the block with the end points;

unquantizing the end points;

reconstructing all pixels; and

measuring a variance between the original pixels and the reconstructed pixels.

6. The computer-readable storage media of claim 5, wherein the least error case is determined by

Σ

{(R(r)−

R(p))²+(G(r)−

G(p))²+(B(r)−

B(p))²}

wherein r is a reconstructed pixel, p is an original pixel, and R(x), G(x), and B(x) return red, green, and blue components, respectively, of a pixel x.

7. The computer-readable storage media of claim 5, wherein the optimizing comprises:

determining three-dimensional points in the pixel block comprising n points, wherein the points comprise p₁=(x₁₁ x₁₂ x₁₃) to p_n=(x_n1 x_n2 x_n3);

calculating a weighted center v₀=(v₀₁ v₀₂ v₀₃) of these points;

subtracting v₀ from all the points to produce {circumflex over (p)}{circumflex over (p₁)}=({circumflex over (x)}{circumflex over (x₁₁)} {circumflex over (x)}{circumflex over (x₁₂)} {circumflex over (x)}{circumflex over (x₁₃)}) to p_n=({circumflex over (x)}{circumflex over (x_n1)} {circumflex over (x)}{circumflex over (x_n2)} {circumflex over (x)}{circumflex over (x_n3)});

forming a matrix comprising;

8. A method comprising:

accessing a pixel block comprising a plurality of original pixels;

selecting a plurality of possible compression cases for compressing the pixel block;

evaluating at least a portion of the plurality of possible compression cases in parallel on a multi-core device;

determining a least error compression case from the evaluated plurality of possible compression cases; and

block compressing the pixel block with the least error case.

9. The method of claim 8, wherein the least error case is determined by

Σ

{(R(r)−

R(p))²+(G(r)−

G(p))²+(B(r)−

B(p))²}

wherein r is a reconstructed pixel, p is an original pixel, and R(x), G(x), and B(x) return red, green, and blue components, respectively, of a pixel x.

10. The method of claim 8, wherein the least error compression case comprises a compression case with the lowest error of all compression cases evaluated.

11. The method of claim 8, wherein the determining the least error compression case comprises parallel reduction of the evaluated plurality of possible compression cases on the multi-core device.

12. The method of claim 8, wherein the multi-core device comprises a graphics processing unit.

13. The method of claim 8, wherein the pixel block comprises 16 pixels.

14. The method of claim 8, wherein the compression cases further comprise partition cases.

15. A system to perform parallel block compression comprising:

a processor;

a memory coupled to the processor and configured to store an image comprising at least one pixel block;

a graphics processing unit (GPU) comprising a plurality of processor cores and coupled to the processor and memory;

a block compression module stored in the memory and configured to;

determine a plurality of cases for compressing the pixel block;

load each case into a core of the GPU for evaluation;

evaluate at least a portion of the plurality of cases in the GPU core in parallel;

measure the error of each of the plurality of cases; and

determine a least error case.

16. The system of claim 15, wherein the block compression module is further configured to load two or more cases into a single core of the GPU.

17. The system of claim 15, wherein the block compression module is further configured to encode the pixel block with the least error case.

18. The system of claim 15, wherein the block compression module is further configured to process a plurality of pixel blocks in parallel.

19. The system of claim 15, wherein parallel reduction executed on the GPU determines the least error case.

20. The system of claim 15, wherein the least error case is determined by

Σ

{(R(r)−

R(p))²+(G(r)−

G(p))²+(B(r)−

B(p))²}

wherein r is a reconstructed pixel, p is an original pixel, and R(x), G(x), and B(x) return red, green, and blue components, respectively, of a pixel x.