Block transform and quantization for image and video coding

• US 7,881,371 B2
• Filed: 02/25/2005
• Issued: 02/01/2011
• Est. Priority Date: 09/18/2001
• Status: Expired due to Fees

• 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/067,101
• Publication Number:
  US 20050141609A1
• Time in Patent Office: 2,167 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, the method comprising:

at a computing device that implements a decoder, receiving a set of quantized transform coefficients;

with the 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

with the computing device, applying an inverse transform process to the de-quantized transform coefficients to generate reconstructed information therefrom, the inverse transform process applying inverse transformation calculations having values such that each multiplication operation in the inverse transformation calculations can be performed by a shift operation, wherein the inverse transform process is orthogonal, the values of the inverse transformation calculations are based on values represented in an inverse transform matrix with plural columns having different norms, 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 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 method of claim 1 wherein three groups of scaling factors are accessible.

3. The method of claim 1 wherein the quantized transform coefficients and scaling factor values enable the de-quantizing in 16-bit arithmetic.

4. The method of claim 1 wherein the applying an inverse transform process to the de-quantized transform coefficients is performed in 16-bit arithmetic.

5. The method of claim 1 wherein the reconstructed information comprises prediction error information for a 4x4 block.

6. A method for decoding video or image information, the method comprising:

at a computing device that implements a decoder, receiving a set of quantized transform coefficients;

with the 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;

depending on a quantization parameter, selecting a scaling factor within the selected group; and

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

with the computing device, applying an inverse transform process to the de-quantized transform coefficients to generate reconstructed information therefrom, the inverse transform process applying inverse transformation calculations having values such that each multiplication operation in the inverse transformation calculations can be performed by a shift operation, wherein the inverse transform process is orthogonal, wherein each multiplication operation in the inverse transformation calculations is performed by a right shift operation, and wherein the inverse transformation calculations consist of sixteen right shift operations, plural addition operations, and plural subtraction operations per 4x4 block of the reconstructed information.

7. A video decoder comprising:

means for receiving a set of quantized transform coefficients;

means for de-quantizing the quantized transform coefficients into de-quantized transform coefficients, wherein the quantized transform coefficients are logically arranged in a block, and wherein the de-quantizing includes scaling the quantized transform coefficients by scaling factors selected from among plural groups of scaling factors, the selection depending on relative positions of the quantized transform coefficients in the block and also depending on a quantization parameter; and

means for applying an inverse transform process to the de-quantized transform coefficients to generate reconstructed information therefrom, the inverse transform process applying inverse transformation calculations having values such that each multiplication operation in the inverse transformation calculations can be performed by a shift operation, wherein the inverse transform process is orthogonal, wherein each multiplication operation in the inverse transformation calculations is performed by a right shift operation, and wherein the inverse transformation calculations consist of sixteen right shift operations, plural addition operations, and plural subtraction operations per 4x4 block of the reconstructed information.

8. The decoder of claim 7 wherein the reconstructed information comprises prediction error information for a 4x4 block.

9. A method comprising:

at a computing device that implements a decoder, receiving plural quantized transform coefficients;

with the computing device, de-quantizing the plural quantized transform coefficients, wherein the plural quantized transform coefficients are logically arranged in a block, and wherein the de-quantizing includes scaling the quantized transform coefficients by scaling factors selected from among plural groups of scaling factors, the selection depending on relative positions of the quantized transform coefficients in the block and also depending on a quantization parameter; and

with the computing device, generating reconstructed information from the plural de-quantized transform coefficients by applying an inverse transform to the plural de-quantized transform coefficients, wherein each multiplication operation in the inverse transform can be performed by a right shift operation, and wherein the inverse transform is orthogonal, wherein the applying the inverse transform to the plural de-quantized transform coefficients consists of performing sixteen right shift operations, plural addition operations, and plural subtraction operations per 4x4 block of the reconstructed information.

10. A method for decoding video or image information, the method comprising:

at a computing device that implements a decoder, receiving a set of quantized transform coefficients;

with the 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;

depending on a quantization parameter, selecting a scaling factor within the selected group; and

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

with the computing device, applying an inverse transform process to the de-quantized transform coefficients to generate reconstructed information therefrom, the inverse transform process applying inverse transformation calculations having values such that each multiplication operation in the inverse transformation calculations can be performed by a shift operation, wherein the inverse transform process is orthogonal, wherein the values of the inverse transformation calculations are based on a matrix having columns that are orthogonal to each other.

11. A video decoder comprising:

means for receiving a set of quantized transform coefficients;

means for de-quantizing the quantized transform coefficients into de-quantized transform coefficients, wherein the quantized transform coefficients are logically arranged in a block, and wherein the de-quantizing includes scaling the quantized transform coefficients by scaling factors selected from among plural groups of scaling factors, the selection depending on relative positions of the quantized transform coefficients in the block and also depending on a quantization parameter; and

means for applying an inverse transform process to the de-quantized transform coefficients to generate reconstructed information therefrom, the inverse transform process applying inverse transformation calculations having values such that each multiplication operation in the inverse transformation calculations can be performed by a shift operation, wherein the inverse transform process is orthogonal, wherein the values of the inverse transformation calculations are based on a matrix having columns that are orthogonal to each other.

12. A method comprising:

at a computing device that implements a decoder, receiving plural quantized transform coefficients;

with the computing device, de-quantizing the plural quantized transform coefficients, wherein the plural quantized transform coefficients are logically arranged in a block, and wherein the de-quantizing includes scaling the quantized transform coefficients by scaling factors selected from among plural groups of scaling factors, the selection depending on relative positions of the quantized transform coefficients in the block and also depending on a quantization parameter; and

with the computing device, generating reconstructed information from the plural de-quantized transform coefficients by applying an inverse transform to the plural de-quantized transform coefficients, wherein each multiplication operation in the inverse transform can be performed by a right shift operation, and wherein the inverse transform is orthogonal, wherein the inverse transform corresponds to a two-dimensional transformation with a matrix having columns that are orthogonal to each other.