Fast video codec transform implementations

• US 7,487,193 B2
• Filed: 05/14/2004
• Issued: 02/03/2009
• Est. Priority Date: 05/14/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Liang, Jie, Srinivasan, Sridhar
• Primary Examiner(s): Mai; Tan V
• Application Number:
  US10/845,808
• Publication Number:
  US 20050256916A1
• Time in Patent Office: 1,726 Days
• Field of Search: 708/400, 708/409
• 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 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:

receiving the media data;

transform-coding the media data to an output data stream for compression or decompression, comprising in part by 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];<br><br>$

and

outputting the data stream.

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

a media data input for receiving the media data;

a transform-based block coder for transform-coding the media data to an output data stream for compression or decompression, comprising in part;

a 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];<br><br>$

and

an output for outputting the output data stream.

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:

receiving the media data;

transform-coding the media data to an output data stream for compression or decompression, comprising in part by 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];<br><br>$

and

outputting the data stream.

4. A method of transform coding-based compression or decompression of two-dimensional media blocks using fast transform of a two-dimensional block of image data between spatial and transform domain representations, where at least one dimension of the block is 8 points, the transform coding-based compression/decompression method comprising;

receiving the media data;

transform-coding the media data to an output data stream for compression or decompression, comprising in part by, 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 co-efficients and variables 4 through 7 produce odd co-efficients in the transform domain; and

outputting the data stream.

5. The transform coding-based compression or decompression method of claim 4, comprising, for an inverse transform:

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

6. A method of transform coding-based compression or decompression of two-dimensional media blocks using fast transform of a two-dimensional block of image data between spatial and transform domain representations, where at least one dimension of the block is 8 points, the transform coding-based compression/decompression method comprising;

receiving the media data;

transform-coding the media data to an output data stream for compression or decompression, comprising in part by, 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>$

 

on a set of variables 0 through 7, where variables 0 through 3 are even transform co-efficients and variables 4 through 7 are odd transform co-efficients, 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];<br><br>$

 

and

outputting the data stream.

7. A method of transform coding-based compression or decompression of two-dimensional media blocks using fast transform of a two-dimensional block of image data between spatial and transform domain representations, where at least one dimension of the block is 8 points, the transform coding-based compression/decompression method comprising;

receiving the media data;

transform-coding the media data to an output data stream for compression or decompression, comprising in part by, 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>$

 

on a set of variables 0 through 7, where variables 0 through 3 are even transform co-efficients and variables 4 through 7 are odd transform co-efficients, 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

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].$

 

and

outputting the data stream.

8. The transform coding-based compression/decompression method of claim 7, wherein said transform-coding the media data to an output data stream for compression or decompression, comprises in part by, for a forward transform:

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

9. A method of transform coding-based compression or decompression of two-dimensional media blocks using fast transform of a two-dimensional block of image data between spatial and transform domain representations, where at least one dimension of the block is 8 points, the transform coding-based compression/decompression method comprising;

receiving the media data;

transform-coding the media data to an output data stream for compression or decompression, comprising in part by, 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 co-efficients and variables 4 through 7 produce odd co-efficients in the transform domain; and

outputting the data stream.

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 input of the media blocks;

means for transform-coding the media data to an output data stream for compression or decompression, 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 co-efficients and variables 4 through 7 are odd transform co-efficients, 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; and

means for output of the output data stream.

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 input of the media blocks;

means for transform-coding the media data to an output data stream for compression or decompression, 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 co-efficients and variables 4 through 7 are odd transform co-efficients, 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

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; and

means for output of the output data stream.

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 input of the media blocks;

means for transform-coding the media data to an output data stream for compression or decompression, 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 co-efficients and variables 4 through 7 are odd transform co-efficients, 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 butterfly operation of variables 5 and 6; and

means for output of the output data stream.

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 input of the media blocks;

means for transform-coding the media data to an output data stream for compression or decompression, 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 co-efficients and variables 4 through 7 are odd transform co-efficients, 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

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; and

means for output of the output data stream.