Block transform and quantization for image and video coding

• US 7,839,928 B2
• Filed: 04/12/2005
• Issued: 11/23/2010
• 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.
• Primary Examiner(s): DIEP, NHON THANH
• Application Number:
  US11/105,216
• Publication Number:
  US 20050180503A1
• Time in Patent Office: 2,051 Days
• Field of Search: None
• 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 method for decoding video or image information with a computing device that implements a video or image decoder, the method comprising:

receiving quantized transform coefficients at the computing device;

with the computing device, de-quantizing the received quantized transform coefficients into de-quantized transform coefficients, wherein the de-quantizing scales the quantized transform coefficients by scaling factors selected from plural groups of scaling factors, wherein the quantized transform coefficients are logically organized in a block, wherein the inverse transform process is a two-dimensional inverse transform with row and column inverse transforms, the two-dimensional inverse transform having different norms, and wherein selection between the plural groups for the de-quantizing is based on relative coefficient position within the block; and

with the computing device, applying an inverse transform process to the de-quantized transform coefficients to generate reconstructed information therefrom.

2. The method of claim 1 wherein each of the plural groups is adapted to adjust for a different norm characterizing a transform process corresponding to the inverse transform process.

3. The method of claim 1 wherein the block is a 4×

4 block, and wherein the plural groups consist of first, second, and third groups of scaling factors.

4. The method of claim 3 wherein the first group is selected for four coefficient positions with low scaling, the second group is selected for four coefficient positions with high scaling, and the third group is selected for eight coefficient positions with intermediate scaling.

5. The method of claim 3 wherein the scaling factors in the second and third groups are approximately 1.6 and 1.3, respectively, times greater than corresponding scaling factors in the first group.

6. The method of claim 1 wherein selection of the scaling factors within one of the plural groups is based on a quantization parameter.

7. The method of claim 1 wherein the de-quantizing includes multiplying each of the quantized transform coefficients in the block by one of the scaling factors.

8. The method of claim 1 wherein the reconstructed information is for reconstructed prediction error information for a 4×

4 block.

9. The method of claim 1, wherein scaling factors are selected from the plural groups of scaling factors depending on a group index that identifies the selected group and a quantization parameter index selecting the scaling factor within the selected group.

10. The method of claim 9, wherein the block of quantized transform coefficients is a 4×

4 block, wherein the plural groups of scaling factors consist of three groups of scaling factors, wherein the two-dimensional inverse transform has three different norms, and wherein each of the three groups of scaling factors is adapted to adjust for a different norm of the three different norms of the two-dimensional inverse transform.

11. The method of claim 9, wherein, for each of the plural groups of scaling factors, scaling with scaling factors of the group approximately doubles for every increment of six in quantization parameter value.

12. A method of coding video or image information in a computing device that implements a video or image encoder, the method comprising:

with the computing device, applying a transform process to the information to produce transform coefficients; and

with the computing device, quantizing the transform coefficients into quantized transform coefficients, wherein the quantizing scales the transform coefficients by scaling factors selected from plural groups of scaling factors, wherein the transform coefficients are logically organized in a block, wherein the transform process is a two-dimensional transform with row and column transforms, the two-dimensional transform having different norms, wherein scaling factors are selected from the plural groups of scaling factors depending on a group index that identifies the selected group and a quantization parameter index selecting the scaling factor within the selected group, and wherein selection between the plural groups for the quantizing is based on relative coefficient position within the block.

13. The method of claim 12 wherein each of the plural groups is adapted to adjust for a different norm characterizing the transform process.

14. The method of claim 12 wherein the block is a 4×

4 block, and wherein the plural groups consist of first, second, and third groups of scaling factors.

15. The method of claim 14 wherein the first group is selected for four coefficient positions with low scaling, the second group is selected for four coefficient positions with high scaling, and the third group is selected for eight coefficient positions with intermediate scaling.

16. The method of claim 12 wherein selection of the scaling factors within one of the plural groups is based on a quantization parameter.

17. The method of claim 12 wherein the quantizing includes multiplying each of the transform coefficients in the block by one of the scaling factors.

18. The method of claim 12 wherein the information includes prediction error information for a 4×

4 block.

19. A video decoder comprising:

means for de-quantizing quantized transform coefficients into de-quantized transform coefficients, wherein the de-quantizing scales the quantized transform coefficients by scaling factors selected from three groups of scaling factors, wherein the de-quantizing includes multiplying each of the quantized transform coefficients by one of the scaling factors, wherein the quantized transform coefficients are logically organized in a 4×

4 block, wherein the inverse transform process is a two-dimensional inverse transform with row and column inverse transforms, the two-dimensional inverse transform having different norms, wherein scaling factors are selected from the plural groups of scaling factors depending on a group index that identifies the selected group and a quantization parameter index selecting the scaling factor within the selected group, and wherein selection between the three groups is based on relative coefficient position within the block; and

means for applying an inverse transform process to the de-quantized transform coefficients.

20. The decoder of claim 19 wherein a first group of the three groups is selected for four coefficient positions with low scaling, a second group of the three groups is selected for four coefficient positions with high scaling, and a third group of the three groups is selected for eight coefficient positions with intermediate scaling.

21. The decoder of claim 20 wherein the scaling factors in the second and third groups are approximately 1.6 and 1.3, respectively, times greater than corresponding scaling factors in the first group.

22. The decoder of claim 19 wherein each of the three groups is adapted to adjust for a different norm characterizing a transform process corresponding to the inverse transform process.

23. The decoder of claim 19 wherein selection of the scaling factors within one of the three groups is based on a quantization parameter.