BLOCK TRANSFORM AND QUANTIZATION FOR IMAGE AND VIDEO CODING

• US 20110116543A1
• Filed: 01/19/2011
• Published: 05/19/2011
• Est. Priority Date: 09/18/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Malvar, Henrique S.
• Granted Patent: US 8,971,405 B2
• Time in Patent Office: Days
• US Class Current: 375/240.03
• CPC Class Codes: G06F 17/147 Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform G06F17/145 takes precedence
• CPC Class Codes: H04N 19/126 Details of normalisation or weighting functions, e.g. normalisation matrices or variable uniform quantisers
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

An improved method and block transform for image or video encoding and decoding, wherein transformation and inverse transformation matrixes are defined such that computational complexity is significantly reduced when encoding and decoding. For example, in the two-dimensional inverse transformation of de-quantized transform coefficients into output pixel information during decoding, only four additions plus one shift operation are needed, per co-efficient transformation, all in sixteen-bit arithmetic. Transformations provide correct results because quantization during encoding and de-quantization (sixteen bit) during decoding, via the use of one of three tables selected based on each coefficient'"'"'s position, have parameter values that already compensate for factors of other transformation multiplications, except for those of a power of two, (e.g., two or one-half), which are performed by a shift operation during the transformation and inverse transformation processes. Computational complexity is significantly reduced with respect to other known transforms without adversely impacting compression or quality.

Claims

1. A computing device, comprising:

at least one battery; and

a processor coupled so as to be powered by the at least one battery and configured to implement a coding method comprising;

receiving a set of quantized transform coefficients;

de-quantizing the quantized transform coefficients into de-quantized transform coefficients, wherein the quantized transform coefficients are logically arranged in a block, and wherein for each of the quantized transform coefficients the de-quantizing includes;

based on position of the quantized transform coefficient in the block, selecting a group from among plural groups of scaling factors, wherein a group index identifies the selected group;

depending on a quantization parameter index, selecting a scaling factor within the selected group, wherein the quantization parameter index and the group index together indicate the selected scaling factor in a lookup operation; and

scaling the quantized transform coefficient by the selected scaling factor; and

applying a two-dimensional inverse transform process to the de-quantized transform coefficients, wherein the inverse transform process is based on values represented in a two dimensional orthogonal inverse transform matrix with plural columns having different norms with row and column inverse transforms, the inverse transform process applying inverse transformation calculations based on auxiliary variables corresponding to, for a selected row or column of transform coefficients, a sum and a difference of a first pair of de-quantized transform coefficients of the selected row or column, and, for a second pair of de-quantized transform coefficients of the selected row or column, a sum of a first coefficient of the second pair with a value corresponding to a bit shift of the second coefficient of the pair, and a difference of the second coefficient of and a value corresponding to a bit shift of the first coefficient of the pair, and wherein the de-quantizing uses the selection from among the plural groups of scaling factors to at least in part adjust for the different norms of the two-dimensional inverse transform.

2. The computing device of claim 1, further comprising a power supply configured to be coupled to an external power source so as to charge the battery.

3. The computing device of claim 1, further comprising computer storage media configured to store computer executable instructions for the coding method.

4. The computing device of claim 1, wherein the computer storage media is configured to store computer executable instructions for at least one application program.

5. The computing device of claim 4, wherein the at least one application program is an email program.

6. The computing device of claim 4, wherein the at least one application program is an Internet browser.

7. The computing device of claim 4, wherein the computer storage media is removable.

8. The computing device of claim 1, further comprising a touchscreen coupled to receive user input.

9. The computing device of claim 1, wherein the quantized transform coefficients and scaling factor values enable the de-quantizing in 16-bit arithmetic.

10. The computing device of claim 1, wherein the processor is configured to apply an inverse transform process to the de-quantized transform coefficients in 16-bit or 32-bit arithmetic.

11. The computing device of claim 10, wherein the reconstructed information comprises prediction error information for a 4×

4 block.

12. The computing device of claim 1, further comprising a virtual keyboard.

13. The computing device of claim 1, wherein the processor is configure to wirelessly receive the set of quantized transform coefficients.

14. A coding method, comprising:

receiving a set of quantized transform coefficients at a portable computing device;

de-quantizing the quantized transform coefficients into de-quantized transform coefficients, wherein the quantized transform coefficients are logically arranged in a block, and wherein for each of the quantized transform coefficients the de-quantizing includes;

based on position of the quantized transform coefficient in the block, selecting a group from among plural groups of scaling factors, wherein a group index identifies the selected group;

depending on a quantization parameter index, selecting a scaling factor within the selected group, wherein the quantization parameter index and the group index together indicate the selected scaling factor in a lookup operation; and

scaling the quantized transform coefficient by the selected scaling factor; and

applying a two-dimensional inverse transform process to the de-quantized transform coefficients, wherein the inverse transform process is based on values represented in a two dimensional orthogonal inverse transform matrix with plural columns having different norms with row and column inverse transforms, the inverse transform process applying inverse transformation calculations based on auxiliary variables corresponding to, for a selected row or column of transform coefficients, a sum and a difference of a first pair of de-quantized transform coefficients of the selected row or column, and, for a second pair of de-quantized transform coefficients of the selected row or column, a sum of a first coefficient of the second pair with a value corresponding to a bit shift of the second coefficient of the pair, and a difference of the second coefficient of and a value corresponding to a bit shift of the first coefficient of the pair, and wherein the de-quantizing uses the selection from among the plural groups of scaling factors to at least in part adjust for the different norms of the two-dimensional inverse transform.

15. The method of claim 14, wherein the coding method is a decoding method.

16. The method of claim 14, wherein the portable computing device is a laptop computer.

17. The method of claim 14, wherein the portable computing device is a cellular telephone.

18. The method of claim 14, wherein the quantized transform coefficients and scaling factor values enable the de-quantizing in 16-bit or 32-bit arithmetic.

19. The method of claim 14, further comprising wirelessly receiving the receiving a set of quantized transform coefficients.

20. At least one computer readable medium configured to store computer-executable instructions for the method comprising:

receiving a set of quantized transform coefficients at a portable computing device;

de-quantizing the quantized transform coefficients into de-quantized transform coefficients, wherein the quantized transform coefficients are logically arranged in a block, and wherein for each of the quantized transform coefficients the de-quantizing includes;

based on position of the quantized transform coefficient in the block, selecting a group from among plural groups of scaling factors, wherein a group index identifies the selected group;

depending on a quantization parameter index, selecting a scaling factor within the selected group, wherein the quantization parameter index and the group index together indicate the selected scaling factor in a lookup operation; and

scaling the quantized transform coefficient by the selected scaling factor; and

applying a two-dimensional inverse transform process to the de-quantized transform coefficients, wherein the inverse transform process is based on values represented in a two dimensional orthogonal inverse transform matrix with plural columns having different norms with row and column inverse transforms, the inverse transform process applying inverse transformation calculations based on auxiliary variables corresponding to, for a selected row or column of transform coefficients, a sum and a difference of a first pair of de-quantized transform coefficients of the selected row or column, and, for a second pair of de-quantized transform coefficients of the selected row or column, a sum of a first coefficient of the second pair with a value corresponding to a bit shift of the second coefficient of the pair, and a difference of the second coefficient of and a value corresponding to a bit shift of the first coefficient of the pair, and wherein the de-quantizing uses the selection from among the plural groups of scaling factors to at least in part adjust for the different norms of the two-dimensional inverse transform.