2-D transforms for image and video coding
View Patent ↗A set of one and two-dimensional transforms is constructed subject to certain range limited constraints to provide a computationally efficient transform implementation, such as for use in image and video coding. The constraints can include that the transform has a scaled integer implementation, provides perfect or near perfect reconstruction, has a DCT-like basis, is limited to coefficient within a range for representation in n-bits (e.g., n is 16 bits), has basis functions that are close in norm, and provides sufficient headroom for overflow of the range. A set of transforms is constructed with this procedure having an implementation within a 16-bit integer range for efficient computation using integer matrix multiplication operations.
1. A method of encoding media data, comprising:
for a two dimensional block of the media data, performing a forward transform of the block to convert the block into a transform domain,
quantizing the transform-domain block;
dequantizing the transform-domain block; and
performing an inverse transform of the transform-domain block to produce a reconstructed block, the inverse transform being implemented as a sequence of matrix multiplications by a transform matrix composed of integer numbers conforming within a predetermined tolerance to certain constraints, the constraints comprising a scaled integer constraint, a perfect reconstruction constraint, a DCT-like basis constraint, and an integer range limitation constraint, wherein the constraints also comprise a constraint that basis functions of the transform are close in norm, and a constraint that there be sufficient headroom.
2. The method of claim 1 further comprising compensating for any mismatch in basis function norms at quantization.
3. The method of claim 1 further comprising compensating for any mismatch in basis function norms at dequantization.
4. The method of claim 1 further comprising compensating for any mismatch in basis function norms partly at quantization and partly at dequantization.
5. A media system providing transform coding of a media data, comprising:
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, the inverse transform being implemented as a sequence of matrix multiplications by a transform matrix composed of integer numbers conforming within a predetermined tolerance to certain constraints, the constraints comprising a scaled integer constraint, a perfect reconstruction constraint, a DCT-like basis constraint, and an integer range limitation constraint, wherein the constraints also comprise a constraint that basis functions of the transform are close in norm, and a constraint that there be sufficient headroom.
6. A computer readable storage medium having a computer-executable program instructions stored thereon operative upon execution on a computer system to perform a method of encoding media data, comprising:
for a two dimensional block of the media data, performing a forward transform of the block to convert the block into a transform domain,
quantizing the transform-domain block;
dequantizing the transform-domain block; and
performing an inverse transform of the transform-domain block to produce a reconstructed block, the inverse transform being implemented as a sequence of matrix multiplications by a transform matrix composed of integer numbers conforming within a predetermined tolerance to certain constraints, the constraints comprising a scaled integer constraint, a perfect reconstruction constraint, a DCT-like basis constraint, and an integer range limitation constraint, wherein the constraints also comprise a constraint that basis functions of the transform are close in norm, and a constraint that there be sufficient headroom.
7. A method of decoding media data encoded as a block of quantized, transform domain values comprising:
dequantizing the transform-domain block; and
performing an inverse transform of the transform-domain block to produce a reconstructed block, the inverse transform being implemented as a sequence of matrix multiplications by a transform matrix composed of integer numbers conforming within a predetermined tolerance to certain constraints, the constraints comprising a scaled integer constraint, a perfect reconstruction constraint, a DCT-like basis constraint, and an integer range limitation constraint, wherein the constraints also comprise a close norms constraint and a sufficient headroom constraint.
8. The method of claim 7 wherein the encoded media data block is norm mismatch compensated at quantization.
9. The method of claim 7 further comprising compensating for any mismatch in basis function norms of the transform at dequantization.
10. The method of claim 7 further comprising compensating for any mismatch in basis function norms of the transform partly at quantization and partly at dequantization.
11. A media decoder for decoding data encoded as a block of quantized, transform domain values, comprising:
a dequantization stage for dequantizing the transform-domain block; and
an inverse transform stage for performing an inverse transform of the transform-domain block to produce a reconstructed block, the inverse transform being implemented as a sequence of matrix multiplications by a transform matrix composed of integer numbers conforming within a predetermined tolerance to certain constraints, the constraints comprising a scaled integer constraint, a perfect reconstruction constraint, a DCT-like basis constraint, and an integer range limitation constraint, wherein the constraints also comprise a close norms constraint and a sufficient headroom constraint.
12. A computer readable storage medium having computer-executable program instructions stored thereon operative upon execution on a computer system to perform a method of decoding media data encoded as a block of quantized, transform domain values, comprising:
dequantizing the transform-domain block; and
performing an inverse transform of the transform-domain block to produce a reconstructed block, the inverse transform being implemented as a sequence of matrix multiplications by a transform matrix composed of integer numbers conforming within a predetermined tolerance to certain constraints, the constraints comprising a scaled integer constraint, a perfect reconstruction constraint, a DCT-like basis constraint, and an integer range limitation constraint, wherein the constraints also comprise a close norms constraint and a sufficient headroom constraint.
13. A method of converting 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:
performing at least one matrix multiplication of the image data block with a transform matrix composed of integer transform coefficients in the form,
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
]
;
and
scaling the resulting matrix product to remain within a bit-range limit;
wherein the image data block is an 8×8 block and the performing at least one matrix multiplication comprises performing row-wise and column-wise matrix multiplications of the image data block with the transform matrix, and wherein the scaling comprises an entry-wise shift operation after each of the row-wise and column-wise matrix multiplications to effect division by a power of two.
14. The method of claim 13 wherein the entry-wise shift operation after a first of the matrix multiplications is a shift by fewer bit positions than after a second of the matrix multiplications.
15. The method of claim 13 wherein the entry-wise shift operations are shifts by an equal number of bit positions after each of the matrix multiplications.
16. A computer readable storage medium having computer executable program instructions stored thereon for execution on a computer to perform a method of converting 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:
performing at least one matrix multiplication of the image data block with a transform matrix composed of integer transform coefficients in the form,
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
]
;
and
sealing the resulting matrix product to remain within a bit-range limit;
wherein the image data block is an 8×8 block and the performing at least one matrix multiplication comprises performing row-wise and column-wise matrix multiplications of the image data block with the transform matrix, and wherein the scaling comprises an entry-wise shift operation after each of the row-wise and column-wise matrix multiplications to effect division by a power of two.
17. A method of converting a two-dimensional block of image data between spatial and transform domain representations, where at least one dimension of the block is 4 points, comprising:
performing at least one matrix multiplication of the image data block with a transform matrix composed of integer transform coefficient in the form,
T
4
=
[
17
17
17
17
22
10
-
10
-
22
17
-
17
-
17
17
10
-
22
22
-
10
]
;
and
scaling the resulting matrix product to remain within a bit-range limit;
wherein the image data block is an 4×4 block and the performing at least one matrix multiplication comprises performing row-wise and column-wise matrix multiplications of the image data block with the transform matrix, and wherein the scaling comprises an entry-wise shift operation after each of the row-wise and column-wise matrix multiplications to effect division by a power of two.
18. The method of claim 17 wherein the entry-wise shift operation after a first of the matrix multiplications is a shift by fewer bit positions than after a second of the matrix multiplications.
19. The method of claim 17 wherein the entry-wise shift operations are shifts by an equal number of bit positions after each of the matrix multiplications.
20. A computer readable storage medium having computer-executable program instructions stored thereon for execution on computer system to perform a method of converting a two-dimensional block of image data between spatial and transform domain representations, where at least one dimension of the block is 4 points, comprising:
performing at least one matrix multiplication of the image data block with a transform matrix composed of integer transform coefficients in the form,
T
4
=
[
17
17
17
17
22
10
-
10
-
22
17
17
-
17
17
10
-
22
22
-
10
]
;
and
scaling the resulting matrix product to remain within a bit-range limit;
wherein the image data block is an 4×4 block and the performing at least one matrix multiplication comprises performing row-wise and column-wise matrix multiplications of the image data block with the transform matrix, and wherein the scaling composes an entry-wise shift operation after each of the row-wise and column-wise matrix multiplications to effect division by a power of two.
21. A computer readable storage medium having computer-executable program instructions stored thereon for execution on computer system to perform a method of converting a two-dimensional block of image data between spatial and transform domain representations, where dimensions of the block are 4 and 8 points, the method comprising:
performing row-wise and column-wise matrix multiplications of the image data block with transform matrices composed of integer transform coefficients in the form,
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
]
and
T
4
=
[
17
17
17
17
22
10
-
10
-
22
17
-
17
-
17
17
10
-
22
22
-
10
]
;
and
scaling the resulting matrix product to remain within a bit-range limit;
wherein the data block has dimensions of 4×8 points, and the act of performing the matrix multiplications is performed according to the relation, Y=(T 8 •X•T′ 4 ), where X represents the data block and Y is the resulting matrix product.
22. A method of converting a two-dimensional block of image data between spatial and transform domain representations, where dimensions of the block are 4 and 8 points, the method comprising:
performing row-wise and column-wise matrix multiplications of the image data block with transform matrices composed of interger transform coefficients in form,
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
]
and
T
4
=
[
17
17
17
17
22
10
-
10
-
22
17
-
17
-
17
17
10
-
22
22
-
10
]
;
and
scaling the resulting matrix product to remain within a bit-range limit;
wherein the data block has dimensions of 4×8 points, and the act of performing the matrix multiplications is performed according to the relation, Y=(T 8 •X•T′ 4 ), where X represents the data block and Y is the resulting matrix product.
23. A method of converting a two-dimensional block of image data between spatial and transform domain representations, where dimensions of the block are 4 and 8 points, the method comprising:
performing row-wise and column-wise matrix multiplications of the image data block with transform matrices composed of integer transform coefficients in the form,
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
]
and
T
4
=
[
17
17
17
17
22
10
-
10
-
22
17
-
17
-
17
17
10
-
22
22
-
10
]
;
and
scaling the resulting matrix product to remain within a bit-range limit;
wherein the data block has dimensions of 8×4 points, and the act of performing the matrix multiplications is performed according to the relation, Y=(T 4 •X•T′ 8 ), where X represents the data block and Y is the resulting matrix product.
24. A computer readable storage medium having computer-executable program instructions stored thereon for execution on computer system to perform a method of converting a two-dimensional block of image data between spatial and transform domain representations, where dimensions of the block are 4 and 8 points, the method comprising:
performing row-wise and column-wise matrix multiplications of the image data block with transform matrices composed of integer transform coefficients in the form,
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
]
and
T
4
=
[
17
17
17
17
22
10
-
10
-
22
17
-
17
-
17
17
10
-
22
22
-
10
]
;
and
scaling the resulting matrix product to remain within a bit-range limit;
wherein the data block has dimensions of 8×4 points, and the act of performing the matrix multiplications is performed according to the relation, Y=(T 4 •X•T′ 8 ), where X represents the data block and Y is the resulting matrix product.
25. A method of transform coding a data block representing media content, comprising:
applying a transform to the data block to produce a transform domain data block representing the media content, the transform comprising a set of transform basis functions having mismatching, yet approximately equal norms; and
sealing values in the transform domain data block according to scaling factors for the respective transform basis functions to compensate for the mismatching norms;
wherein applying the transform comprises a matrix multiplication using a 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
]
;
and
wherein scaling comprises performing a component-wise product using a matrix,
[
f
0
f
1
f
3
f
1
f
0
f
1
f
3
f
1
f
1
f
2
f
4
f
2
f
1
f
2
f
4
f
2
f
3
f
4
f
5
f
4
f
3
f
4
f
5
f
4
f
1
f
2
f
4
f
2
f
1
f
2
f
4
f
2
f
0
f
1
f
3
f
1
f
0
f
1
f
3
f
1
f
1
f
2
f
4
f
2
f
1
f
2
f
4
f
2
f
3
f
4
f
5
f
4
f
3
f
4
f
5
f
4
f
1
f
2
f
4
f
2
f
1
f
2
f
4
f
2
]
where
,
f
0
=
64
288
×
288
f
1
=
64
288
×
289
f
2
=
64
289
×
289
f
3
=
64
288
×
292
f
4
=
64
289
×
292
f
5
=
64
292
×
292
.
26. The method of claim 25 wherein scaling to compensate for the mismatching norms is performed at encoding, so as to reduce computational load at decoding.
27. A method of transform coding a data block representing media content, comprising:
applying a transform to the data block to produce a transform domain data block representing the media content, the transform comprising a set of transform basis functions having mismatching, yet approximately equal norms; and
scaling values in the transform domain data block according to scaling factor for the respective transform basis functions to compensate for the mismatching norms;
wherein applying the transform comprises a matrix multiplication using a 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
]
and
T
4
=
[
17
17
17
17
22
10
-
10
-
22
17
-
17
-
17
17
10
-
22
22
-
10
]
;
and
wherein scaling comprises calculating a component-wise product using a matrix,
[
f
1
f
3
f
1
f
3
f
2
f
4
f
2
f
4
f
4
f
5
f
4
f
5
f
2
f
4
f
2
f
4
f
1
f
3
f
1
f
3
f
2
f
4
f
2
f
4
f
4
f
5
f
4
f
5
f
2
f
4
f
2
f
4
]
where
f
0
=
64
288
×
288
f
1
=
64
288
×
289
f
2
=
64
289
×
289
f
3
=
64
288
×
292
f
4
=
64
289
×
292
f
5
=
64
292
×
292
.
28. The method of claim 27 wherein scaling to compensate for the mismatching norms is performed at decoding, so as to reduce computational load at encoding.
29. A method of transform coding a data block representing media content, comprising:
applying a transform to the data block to produce a transform domain data block representing the media content, the transform comprising a set of transform basis functions having mismatching, yet approximately equal norms; and
scaling values in the transform domain data block according to scaling factors for the respective transform basis functions to compensate for the mismatching norms;
wherein applying the transform comprises matrix multiplications using matrices,
T
4
=
[
17
17
17
17
22
10
-
10
-
22
17
-
17
-
17
17
10
-
22
22
-
10
]
;
and
wherein scaling comprises calculating a component-wise product using a matrix,
[
f
2
f
4
f
2
f
4
f
4
f
5
f
4
f
5
f
2
f
4
f
2
f
4
f
4
f
5
f
4
f
5
]
where
f
2
=
64
289
×
289
f
4
=
64
289
×
292
f
5
=
64
292
×
292
.
30. A computer-readable storage medium having computer-executable program instructions stored thereon for executing on a computer system to perform a method of transform coding a data block representing media content, comprising:
applying a transform to the data block to produce a transform domain data block representing the media content, the transform comprising a set of transform basis functions having mismatching, yet approximately equal norms; and
scaling values in the transform domain data block according to scaling factors for the respective transform basis functions to compensate for the mismatching norms;
wherein applying the transform comprises a matrix multiplication using a 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
]
;
and
wherein scaling comprises performing a component-wise product using a matrix,
[
f
0
f
1
f
3
f
1
f
0
f
1
f
3
f
1
f
1
f
2
f
4
f
2
f
1
f
2
f
4
f
2
f
3
f
4
f
5
f
4
f
3
f
4
f
5
f
4
f
1
f
2
f
4
f
2
f
1
f
2
f
4
f
2
f
0
f
1
f
3
f
1
f
0
f
1
f
3
f
1
f
1
f
2
f
4
f
2
f
1
f
2
f
4
f
2
f
3
f
4
f
5
f
4
f
3
f
4
f
5
f
4
f
1
f
2
f
4
f
2
f
1
f
2
f
4
f
2
]
where
,
f
0
=
64
288
×
288
f
1
=
64
288
×
289
f
2
=
64
289
×
289
f
3
=
64
288
×
292
f
4
=
64
289
×
292
f
5
=
64
292
×
292
.
31. A method of transform coding a data block, D, representing media content, comprising:
calculating a transform of the data block for convening between spatial and transform domain representations of the media block, wherein a result R of the transform is related to the data block D as
R
=
D
·
T
2
y
where T is a matrix of transform basis functions, the calculating comprising:
performing matrix multiplications of the data block with each of first and second transform sub-component matrices, wherein the transform sub-component matrices (T a and T b ) are related to the transform basis function matrix as T=2 x •T a +T b ;
shifting a product of the data block and second sub-component matrix by x bit positions;
summing a product of the data block and first sub-component matrix with the shifted product of the data block and second sub-component matrix; and
shifting a sum of the products by y bit positions to produce the result R;
whereby the headroom of the transform is extended.
32. The method of claim 31 wherein the transform basis function matrix is
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
]
;
and
wherein the transform sub-component matrices are
T
8
e
=
[
6
6
6
6
6
6
6
6
8
7
4
2
-
2
-
4
-
7
-
8
8
3
-
3
-
8
-
8
-
3
3
8
7
-
2
-
8
-
5
5
8
2
-
7
6
-
6
-
6
6
6
-
6
-
6
6
4
-
8
2
7
-
7
-
2
8
-
4
3
-
8
8
-
3
-
3
8
-
8
3
2
-
5
7
-
8
8
-
7
5
-
2
]
T
8
o
=
[
0
0
0
0
0
0
0
0
0
1
1
0
0
-
1
-
1
0
0
0
0
0
0
0
0
0
1
0
0
1
-
1
0
0
-
1
0
0
0
0
0
0
0
0
1
0
0
1
-
1
0
0
-
1
0
0
0
0
0
0
0
0
0
1
1
0
0
-
1
-
1
0
]
.
33. The method of claim 31 wherein the transform basis function matrix is
T
4
=
[
17
17
17
17
22
10
-
10
-
22
17
-
17
-
17
17
10
-
22
22
-
10
]
;
and
wherein the transform sub-component matrices are
T
4
e
=
[
8
8
8
8
11
5
-
5
-
11
8
-
8
-
8
8
5
-
11
11
-
5
]
T
4
o
=
[
1
1
1
1
0
0
0
0
1
-
1
-
1
1
0
0
0
0
]
.
34. A computer-readable storage medium having computer-executable program instructions stored thereon for execution on a computer system to perform a method of transform coding a data block, D, representing media content, comprising:
calculating a transform of the data block for converting between spatial and transform domain representations of the media block, wherein a result R of the transform is related to the data block D as
R
=
D
·
T
2
y
where T is a matrix of transform basis functions, the calculating comprising:
performing matrix multiplications of the data block with each of first and second transform sub-component matrices, wherein the transform sub-component matrices (T a and T b ) are related to the transform basis function matrix as T=2 x •T a +T b ;
shifting a product of the data block and second sub-component matrix by x bit positions;
summing a product of the data block and first sub-component matrix with the shifted product of the data block and second sub-component matrix; and
shifting a sum of the products by y bit positions to produce the result R;
whereby the headroom of the transform is extended.