Fast video codec transform implementations
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.
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
=
[
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
]
,
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,
[
4
3
3
-
2
]
;
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
=
(
T
n
′
·
D
·
T
m
)
1024
,
wherein at least one dimension T n or T m of the inverse transform is the 8-point matrix
T
8
=
[
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
]
,
the inverse transform being implemented as a sequence of butterfly operations and a matrix multiply by the matrix,
[
4
3
3
-
2
]
;
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
=
[
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
]
,
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,
[
4
3
3
-
2
]
;
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
[
c
s
s
-
c
]
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,
[
4
3
3
-
2
]
;
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
[
c
s
s
-
c
]
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,
[
4
3
3
-
2
]
;
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
[
c
s
s
-
c
]
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,
[
4
3
3
-
2
]
.
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
[
c
s
s
-
c
]
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,
[
4
3
3
-
2
]
;
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
=
[
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
]
,
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
[
c
s
s
-
c
]
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,
[
4
3
3
-
2
]
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
=
[
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
]
,
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
[
c
s
s
-
c
]
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,
[
4
3
3
-
2
]
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
=
[
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
]
,
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
[
c
s
s
-
c
]
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,
[
4
3
3
-
2
]
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
=
[
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
]
,
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
[
c
s
s
-
c
]
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,
[
4
3
3
-
2
]
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.