Fast video codec transform implementations

• US 20050256916A1
• Filed: 05/14/2004
• Published: 11/17/2005
• Est. Priority Date: 05/14/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Srinivasan, Sridhar, Liang, Jie
• Granted Patent: US 7,487,193 B2
• Time in Patent Office: Days
• US Class Current: 708/400
• 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/60 using transform coding
• CPC Class Codes: H04N 19/625 using discrete cosine transform [DCT]
• CPC Class Codes: H04N 19/80 Details of filtering operations specially adapted for video compression, e.g. for pixel interpolation H04N19/635, H04N19/86 take precedence

Abstract

A fast implementation of the 8-point WMV9/VC-9 transform is realized using a sequence of butterfly operations and matrix multiplies. A fast implementation of the inverse transform is realized by applying inverses of the butterfly operations with the matrix multiplies in reverse flow. These fast implementations permit scaling to be incorporated into the transform stages either at the end of both dimensions of filtering, or separately at each stage. These fast implementations of the transform can be used in encoders and decoders based on this transform in image compression and other signal processing systems.

Claims

1. A method of transform-coding media data in two-dimensional blocks using a fast transform implementation of a block transform of 8-points in at least one of the block'"'"'s dimensions based on a transform matrix represented by

$T_8=\left[\begin{array}{cccccccc}12& 12& 12& 12& 12& 12& 12& 12\\ 16& 15& 9& 4& -4& -9& -15& -16\\ 16& 6& -6& -16& -16& -6& 6& 16\\ 15& -4& -16& -9& 9& 16& 4& -15\\ 12& -12& -12& 12& 12& -12& -12& 12\\ 9& -16& 4& 15& -15& -4& 16& -9\\ 6& -16& 16& -6& -6& 16& -16& 6\\ 4& -9& 15& -16& 16& -15& 9& -4\end{array}\right],$

the method comprising:

performing multiple stages of butterfly operations converting between an 8-point set of spatial domain co-efficients and 8-point transform domain co-efficients in the at least one 8-point dimension, the multiple stages comprising for odd transform domain co-efficients, performing a matrix multiply by the matrix,

$\left[\begin{array}{cc}4& 3\\ 3& -2\end{array}\right].$

2. A media system providing transform coding of a media data, comprising:

forward transform stage operating, for a two dimensional block of the media data, to perform a forward transform of the block to convert the block into a transform domain,

a quantization stage operating to quantize the transform-domain block;

a dequantization stage operating to dequantize the transform-domain block; and

an inverse transform stage for performing an inverse transform of the transform-domain block to produce a reconstructed block of the form,

$R=\frac{\left(T_n^{\mathrm{\prime <br><br>}}·<br><br>D·<br><br>T_m\right)}{1024},$

wherein at least one dimension T_n or T_m of the inverse transform is the 8-point matrix

$T_8=\left[\begin{array}{cccccccc}12& 12& 12& 12& 12& 12& 12& 12\\ 16& 15& 9& 4& -4& -9& -15& -16\\ 16& 6& -6& -16& -16& -6& 6& 16\\ 15& -4& -16& -9& 9& 16& 4& -15\\ 12& -12& -12& 12& 12& -12& -12& 12\\ 9& -16& 4& 15& -15& -4& 16& -9\\ 6& -16& 16& -6& -6& 16& -16& 6\\ 4& -9& 15& -16& 16& -15& 9& -4\end{array}\right],$

the inverse transform being implemented as a sequence of butterfly operations and a matrix multiply by the matrix,

$\left[\begin{array}{cc}4& 3\\ 3& -2\end{array}\right].$

3. A computer-readable medium carrying thereon computer-executable software instructions for effecting a method of transform-coding media data in two-dimensional blocks using a fast transform implementation of a block transform of 8-points in at least one of the block'"'"'s dimensions based on a transform matrix represented by

$T_8=\left[\begin{array}{cccccccc}12& 12& 12& 12& 12& 12& 12& 12\\ 16& 15& 9& 4& -4& -9& -15& -16\\ 16& 6& -6& -16& -16& -6& 6& 16\\ 15& -4& -16& -9& 9& 16& 4& -15\\ 12& -12& -12& 12& 12& -12& -12& 12\\ 9& -16& 4& 15& -15& -4& 16& -9\\ 6& -16& 16& -6& -6& 16& -16& 6\\ 4& -9& 15& -16& 16& -15& 9& -4\end{array}\right],$

the method comprising:

performing multiple stages of butterfly operations converting between an 8-point set of spatial domain co-efficients and 8-point transform domain co-efficients in the at least one 8-point dimension, the multiple stages comprising for odd transform domain co-efficients, performing a matrix multiply by the matrix,

$\left[\begin{array}{cc}4& 3\\ 3& -2\end{array}\right].$

4. A fast transform method of transforming a two-dimensional block of image data between spatial and transform domain representations, where at least one dimension of the block is 8 points, comprising, for a forward transform:

performing a sequence of butterfly operations of the type

$\hspace{1em}<br><br>\left[\begin{array}{cc}c& s\\ s& -c\end{array}\right]$

on a set of variables 0 through 7, including at least,

a butterfly operation of variables 0 and 7, where values c and s are 1;

a butterfly operation of variables 1 and 6, where values c and s are 1;

a butterfly operation of variables 2 and 5, where values c and s are 1;

a butterfly operation of variables 3 and 4, where values c and s are 1;

a butterfly operation of variables 0 and 3, where values c and s are 1;

a butterfly operation of variables 1 and 2, where values c and s are 1;

a butterfly operation of variables 0 and 1, where values c and s are 1, with a scaling by 12;

a butterfly operation of variables 3 and 2, where values c and s are 16 and 6;

a butterfly operation of variables 4 and 7, where values c and s are 4 and 1;

a butterfly operation of variables 5 and 6, where values c and s are 5 and 3, followed by negating the variable 6;

a second butterfly operation of variables 5 and 6, where values c and s are 1; and

prior to the second butterfly operation of variables 5 and 6, performing a matrix multiply of variables 4 and 5 and variables 7 and 6 by the matrix,

$\left[\begin{array}{cc}4& 3\\ 3& -2\end{array}\right];<br><br>$

whereby the variables 0 through 3 produce even coefficients and variables 4 through 7 produce odd coefficients in the transform domain.

5. The fast transform method of claim 4, comprising, for an inverse transform:

performing inverses of the butterfly operations in reverse flow of the forward transform.

6. A fast transform method of transforming a two-dimensional block of image data between spatial and transform domain representations, where at least one dimension of the block is 8 points, comprising, for an inverse transform:

performing a sequence of butterfly operations of the type

$\hspace{1em}<br><br>\left[\begin{array}{cc}c& s\\ s& -c\end{array}\right]<br><br>\text{\hspace{1em}<br><br>}$

on a set of variables 0 through 7, where variables 0 through 3 are even transform coefficients and variables 4 through 7 are odd transform coefficients, including at least, a butterfly operation of variables 5 and 6, where values c and s are 1;

a second butterfly operation of variables 6 and 5, where values c and s are 5 and 3, followed by negating the variable 5;

a butterfly operation of variables 4 and 7, where values c and s are 4 and 1;

a butterfly operation of variables 0 and 1, where values c and s are 1, with a scaling by 12;

a butterfly operation of variables 3 and 2, where values c and s are 16 and 6;

a butterfly operation of variables 1 and 2, where values c and s are 1;

a butterfly operation of variables 0 and 3, where values c and s are 1;

a butterfly operation of variables 3 and 4, where values c and s are 1;

a butterfly operation of variables 2 and 5, where values c and s are 1;

a butterfly operation of variables 1 and 6, where values c and s are 1;

a butterfly operation of variables 0 and 7, where values c and s are 1; and

prior to the second butterfly operation of variables 5 and 6, performing a matrix multiply of variables 4 and 5 and variables 7 and 6 by the matrix,

$\left[\begin{array}{cc}4& 3\\ 3& -2\end{array}\right].$

7. A fast transform method of transforming a two-dimensional block of image data between spatial and transform domain representations, where at least one dimension of the block is 8 points, comprising, for an inverse transform:

performing a sequence of butterfly operations of the type

$\hspace{1em}<br><br>\left[\begin{array}{cc}c& s\\ s& -c\end{array}\right]<br><br>\text{\hspace{1em}<br><br>}$

on a set of variables 0 through 7, where variables 0 through 3 are even transform coefficients and variables 4 through 7 are odd transform coefficients, including at least, a butterfly operation of variables 5 and 6, where values c and s are 5 and 3, followed by negating the variable 6;

a butterfly operation of variables 4 and 7, where values c and s are 4 and a second butterfly operation of variables 1 and 6, where values c and s are a butterfly operation of variables 0 and 1, where values c and s are 1, with a scaling by 12;

a butterfly operation of variables 3 and 2, where values c and s are 16 and 6;

a butterfly operation of variables 1 and 2, where values c and s are 1;

a butterfly operation of variables 0 and 3, where values c and s are 1;

a butterfly operation of variables 3 and 4, where values c and s are 1;

a butterfly operation of variables 2 and 5, where values c and s are 1;

a butterfly operation of variables 1 and 6, where values c and s are 1;

a butterfly operation of variables 0 and 7, where values c and s are 1; and

following the butterfly operation of variables 4 and 7 and prior to the second butterfly operation of variables 5 and 6, performing a matrix multiply of variables 4 and 5 and variables 7 and 6 by the matrix,

$\left[\begin{array}{cc}4& 3<br><br>\\ 3& -2<br><br>\end{array}\right].$

8. The fast transform method of claim 7, comprising, for a forward transform:

performing inverses of the butterfly operations in reverse flow of the forward transform.

9. A fast transform method of transforming a two-dimensional block of image data between spatial and transform domain representations, where at least one dimension of the block is 8 points, comprising, for a forward transform:

performing a sequence of butterfly operations of the type

$\left[\begin{array}{cc}c& s<br><br>\\ s& -c<br><br>\end{array}\right]\hspace{1em}<br><br>$

on a set of variables 0 through 7, including at least,

a butterfly operation of variables 0 and 7, where values c and s are 1;

a butterfly operation of variables 1 and 6, where values c and s are 1;

a butterfly operation of variables 2 and 5, where values c and s are 1;

a butterfly operation of variables 3 and 4, where values c and s are 1;

a butterfly operation of variables 0 and 3, where values c and s are 1;

a butterfly operation of variables 1 and 2, where values c and s are 1;

a butterfly operation of variables 0 and 1, where values c and s are 1, with a scaling by 12;

a butterfly operation of variables 3 and 2, where values c and s are 16 and 6;

a first butterfly operation of variables 5 and 6, where values c and s are 1;

a butterfly operation of variables 4 and 7, where values c and s are 4 and 1;

a second butterfly operation of variables 6 and 5, where values c and s are 5 and 3, followed by negating the variable 5; and

following the first butterfly operation of variables 5 and 6 and prior to the butterfly operation of variables 4 and 7, performing a matrix multiply of variables 4 and 5 and variables 7 and 6 by the matrix,

$\left[\begin{array}{cc}4& 3<br><br>\\ 3& -2<br><br>\end{array}\right];<br><br>$

whereby the variables 0 through 3 produce even coefficients and variables 4 through 7 produce odd co-efficients in the transform domain.

10. A two-dimensional media compression processor for performing transform-based compression/decompression of two-dimensional media blocks, wherein the transform in at least one 8-point dimension of the blocks is based on the transform matrix,

$T_8=[\begin{array}{cc}12& 12\end{array}$

12 ⁢

12 ⁢

12 ⁢

12 12 ⁢

12 ⁢

16 15 ⁢

9 ⁢

4 ⁢

- 4 ⁢

- 9 - 15 ⁢

- 16 ⁢

16 6 - 6 - 16 - 16 - 6 6 16 15 - 4 - 16 - 9 9 16 4 - 15 12 - 12 - 12 12 12 - 12 - 12 12 9 - 16 4 15 - 15 - 4 16 - 9 6 - 16 16 - 6 - 6 16 - 16 6 4 - 9 15 - 16 16 - 15 9 - 4 ] ,

the processor comprising;

means for performing a sequence of butterfly operations of the type

$\left[\begin{array}{cc}c& s<br><br>\\ s& -c<br><br>\end{array}\right]\hspace{1em}<br><br>$

on a set of variables 0 through 7, where variables 0 through 3 are even transform coefficients and variables 4 through 7 are odd transform coefficients, including at least,

a butterfly operation of variables 0 and 7, where values c and s are 1;

a butterfly operation of variables 1 and 6, where values c and s are 1;

a butterfly operation of variables 2 and 5, where values c and s are 1;

a butterfly operation of variables 3 and 4, where values c and s are 1;

a butterfly operation of variables 0 and 3, where values c and s are 1;

a butterfly operation of variables 1 and 2, where values c and s are 1;

a butterfly operation of variables 0 and 1, where values c and s are 1, with a scaling by 12;

a butterfly operation of variables 3 and 2, where values c and s are 16 and 6;

a butterfly operation of variables 4 and 7, where values c and s are 4 and 1;

a butterfly operation of variables 5 and 6, where values c and s are 5 and 3, followed by negating the variable 6;

a second butterfly operation of variables 5 and 6, where values c and s are 1; and

means for performing a matrix multiply of variables 4 and 5 and variables 7 and 6 by the matrix,

$\left[\begin{array}{cc}4& 3<br><br>\\ 3& -2<br><br>\end{array}\right]\hspace{1em}<br><br>$

prior to the second butterfly operation of variables 5 and 6.

11. A two-dimensional media compression processor for performing transform-based compression/decompression of two-dimensional media blocks, wherein the transform in at least one 8-point dimension of the blocks is based on the transform matrix,

$T_8=[\begin{array}{cc}12& 12\end{array}$

12 ⁢

12 ⁢

12 ⁢

12 12 ⁢

12 ⁢

16 15 ⁢

9 ⁢

4 ⁢

- 4 ⁢

- 9 - 15 ⁢

- 16 ⁢

16 6 - 6 - 16 - 16 - 6 6 16 15 - 4 - 16 - 9 9 16 4 - 15 12 - 12 - 12 12 12 - 12 - 12 12 9 - 16 4 15 - 15 - 4 16 - 9 6 - 16 16 - 6 - 6 16 - 16 6 4 - 9 15 - 16 16 - 15 9 - 4 ] ,

the processor comprising;

means for performing a sequence of butterfly operations of the type

$\left[\begin{array}{cc}c& s<br><br>\\ s& -c<br><br>\end{array}\right]\hspace{1em}<br><br>$

on a set of variables 0 through 7, where variables 0 through 3 are even transform coefficients and variables 4 through 7 are odd transform coefficients, including at least,

a butterfly operation of variables 5 and 6, where values c and s are 1;

a second butterfly operation of variables 6 and 5, where values c and s are 5 and 3, followed by negating the variable 5;

a butterfly operation of variables 4 and 7, where values c and s are 4 and a butterfly operation of variables 0 and 1, where values c and s are 1, with a scaling by 12;

a butterfly operation of variables 3 and 2, where values c and s are 16 and 6;

a butterfly operation of variables 1 and 2, where values c and s are 1;

a butterfly operation of variables 0 and 3, where values c and s are 1;

a butterfly operation of variables 3 and 4, where values c and s are 1;

a butterfly operation of variables 2 and 5, where values c and s are 1;

a butterfly operation of variables 1 and 6, where values c and s are 1;

a butterfly operation of variables 0 and 7, where values c and s are 1; and

means for performing a matrix multiply of variables 4 and 5 and variables 7 and 6 by the matrix,

$\left[\begin{array}{cc}4& 3<br><br>\\ 3& -2<br><br>\end{array}\right]\hspace{1em}<br><br>$

prior to the second butterfly operation of variables 5 and 6.

12. A two-dimensional media compression processor for performing transform-based compression/decompression of two-dimensional media blocks, wherein the transform in at least one 8-point dimension of the blocks is based on the transform matrix,

$T_8=[\begin{array}{cc}12& 12\end{array}$

12 ⁢

12 ⁢

12 ⁢

12 12 ⁢

12 ⁢

16 15 ⁢

9 ⁢

4 ⁢

- 4 ⁢

- 9 - 15 ⁢

- 16 ⁢

16 6 - 6 - 16 - 16 - 6 6 16 15 - 4 - 16 - 9 9 16 4 - 15 12 - 12 - 12 12 12 - 12 - 12 12 9 - 16 4 15 - 15 - 4 16 - 9 6 - 16 16 - 6 - 6 16 - 16 6 4 - 9 15 - 16 16 - 15 9 - 4 ] ,

the processor comprising;

means for performing a sequence of butterfly operations of the type

$\left[\begin{array}{cc}c& s<br><br>\\ s& -c<br><br>\end{array}\right]\hspace{1em}<br><br>$

on a set of variables 0 through 7, where variables 0 through 3 are even transform coefficients and variables 4 through 7 are odd transform coefficients, including at least, a butterfly operation of variables 5 and 6, where values c and s are 5 and 3, followed by negating the variable 6;

a butterfly operation of variables 4 and 7, where values c and s are 4 and 1;

a second butterfly operation of variables 5 and 6, where values c and s are 1;

a butterfly operation of variables 0 and 1, where values c and s are 1, with a scaling by 12;

a butterfly operation of variables 3 and 2, where values c and s are 16 and 6;

a butterfly operation of variables 1 and 2, where values c and s are 1;

a butterfly operation of variables 0 and 3, where values c and s are 1;

a butterfly operation of variables 3 and 4, where values c and s are 1;

a butterfly operation of variables 2 and 5, where values c and s are 1;

a butterfly operation of variables 1 and 6, where values c and s are 1;

a butterfly operation of variables 0 and 7, where values c and s are 1; and

means for performing a matrix multiply of variables 4 and 5 and variables 7 and 6 by the matrix,

$\left[\begin{array}{cc}4& 3<br><br>\\ 3& -2<br><br>\end{array}\right]\hspace{1em}<br><br>$

following the butterfly operation of variables 4 and 7 and prior to the second buterfly operation of variables 5 and 6.

13. A two-dimensional media compression processor for performing transform-based compression/decompression of two-dimensional media blocks, wherein the transform in at least one 8-point dimension of the blocks is based on the transform matrix,

$T_8=\left[\begin{array}{cccccccc}12& 12& 12& 12& 12& 12& 12& 12\\ 16& 15& 9& 4& -4& -9& -15& -16\\ 16& 6& -6& -16& -16& -6& 6& 16\\ 15& -4& -16& -9& 9& 16& 4& -15\\ 12& -12& -12& 12& 12& -12& -12& 12\\ 9& -16& 4& 15& -15& -4& 16& -9\\ 6& -16& 16& -6& -6& 16& -16& 6\\ 4& -9& 15& -16& 16& -15& 9& -4\end{array}\right],$

the processor comprising:

means for performing a sequence of butterfly operations of the type

$\left[\begin{array}{cc}c& s<br><br>\\ s& -c<br><br>\end{array}\right]\hspace{1em}<br><br>$

on a set of variables 0 through 7, where variables 0 through 3 are even transform coefficients and variables 4 through 7 are odd transform coefficients, including at least,

a butterfly operation of variables 0 and 7, where values c and s are 1;

a butterfly operation of variables 1 and 6, where values c and s are 1;

a butterfly operation of variables 2 and 5, where values c and s are 1;

a butterfly operation of variables 3 and 4, where values c and s are 1;

a butterfly operation of variables 0 and 3, where values c and s are 1;

a butterfly operation of variables 1 and 2, where values c and s are 1;

a butterfly operation of variables 0 and 1, where values c and s are 1, with by 12;

a butterfly operation of variables 3 and 2, where values c and s are 16 and 6;

a first butterfly operation of variables 5 and 6, where values c and s are 1;

a butterfly operation of variables 4 and 7, where values c and s are 4 and 1;

a second butterfly operation of variables 6 and 5, where values c and s are 5 and 3, followed by negating the variable 5; and

means for performing a matrix multiply of variables 4 and 5 and variables 7 and 6 by the matrix,

$\left[\begin{array}{cc}4& 3<br><br>\\ 3& -2<br><br>\end{array}\right]\hspace{1em}<br><br>$

following the first butterfly operation of variables 5 and 6 and prior to the butterfly operation of variables 4 and 7.