2-D transforms for image and video coding

• US 7,242,713 B2
• Filed: 02/28/2003
• Issued: 07/10/2007
• Est. Priority Date: 05/02/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Srinivasan, Sridhar, Regunathan, Shankar
• Primary Examiner(s): An; Shawn S.
• Application Number:
  US10/376,147
• Publication Number:
  US 20030206582A1
• Time in Patent Office: 1,593 Days
• Field of Search: 375/240.01, 375/240.2, 375/240.18, 375/240.03, 375/240.25, 375/240.24, 375/240.26, 382/250, 382/248, 382/251, 382/233, 382/235
• US Class Current: 375/240.01
• 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: G06T 9/007 Transform coding, e.g. discrete cosine transform

Abstract

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.

Claims

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=\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];<br><br>\mathrm{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=[<br><br>\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}<br><br>];<br><br>\mathrm{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=\left[\begin{array}{cccc}17& 17& 17& 17\\ 22& 10& -10& -22\\ 17& -17& -17& 17\\ 10& -22& 22& -10\end{array}\right];<br><br>\mathrm{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=[<br><br>\begin{array}{cccc}17& 17& 17& 17\\ 22& 10& -10& -22\\ 17& 17& -17& 17\\ 10& -22& 22& -10\end{array}<br><br>];<br><br>\mathrm{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,

$\begin{array}{c}{T}_8=<br><br>\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]<br><br><br><br>\mathrm{and}\\ T_4=<br><br>\left[\begin{array}{cccc}17& 17& 17& 17\\ 22& 10& -10& -22\\ 17& -17& -17& 17\\ 10& -22& 22& -10\end{array}\right];<br><br>\mathrm{and}\end{array}$

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₈•

X•

T′

₄), 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=[<br><br>\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}<br><br>]<br><br>\mathrm{and}$ $T_4=[<br><br>\begin{array}{cccc}17& 17& 17& 17\\ 22& 10& -10& -22\\ 17& -17& -17& 17\\ 10& -22& 22& -10\end{array}<br><br>];<br><br>\mathrm{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₈•

X•

T′

₄), 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=[<br><br>\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}<br><br>]<br><br>\mathrm{and}$ $T_4=[<br><br>\begin{array}{cccc}17& 17& 17& 17\\ 22& 10& -10& -22\\ 17& -17& -17& 17\\ 10& -22& 22& -10\end{array}<br><br>];<br><br>\mathrm{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₄•

X•

T′

₈), 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=[<br><br>\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}<br><br>]<br><br>\mathrm{and}$ $T_4=[<br><br>\begin{array}{cccc}17& 17& 17& 17\\ 22& 10& -10& -22\\ 17& -17& -17& 17\\ 10& -22& 22& -10\end{array}<br><br>];<br><br>\mathrm{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₄•

X•

T′

₈), 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=[<br><br>\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}<br><br>];<br><br>\mathrm{and}$

wherein scaling comprises performing a component-wise product using a matrix,

$\left[\begin{array}{cccccccc}{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<br><br>}& 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\end{array}\right]$ $\mathrm{where},$ $\begin{array}{c}{f}_0=<br><br>\frac{64}{288\times <br><br>288}\\ f_1=<br><br>\frac{64}{288\times <br><br>289}\\ f_2=<br><br>\frac{64}{289\times <br><br>289}\\ f_3=<br><br>\frac{64}{288\times <br><br>292}\\ f_4=<br><br>\frac{64}{289\times <br><br>292}\\ f_5=<br><br>\frac{64}{292\times <br><br>292}.\end{array}$

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=\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]<br><br><br><br>\mathrm{and}$ $T_4=\left[\begin{array}{cccc}17& 17& 17& 17\\ 22& 10& -10& -22\\ 17& -17& -17& 17\\ 10& -22& 22& -10\end{array}\right]<br><br>;<br><br>\mathrm{and}$

wherein scaling comprises calculating a component-wise product using a matrix,

$\left[\begin{array}{cccc}{f}_1& f_3& f_1& <br><br>f_3\\ f_2& f_4& f_2& f_4\\ <br><br>f_4& f_5& f_4& f_5\\ f_2& f_4& f_2& f_4\\ f_1& f_3& f_1& <br><br>f_3\\ f_2& f_4& f_2& f_4\\ <br><br>f_4& f_5& f_4& f_5\\ f_2& f_4& f_2& f_4\end{array}\right]<br><br><br><br>\mathrm{where}<br><br>\begin{array}{c}{f}_0=\frac{64}{288\times <br><br>288}\\ f_1=\frac{64}{288\times <br><br>289}\\ f_2=\frac{64}{289\times <br><br>289}\\ f_3=\frac{64}{288\times <br><br>292}\\ f_4=\frac{64}{289\times <br><br>292}\\ f_5=\frac{64}{292\times <br><br>292}.\end{array}$

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=\left[\begin{array}{cccc}17& 17& 17& 17\\ 22& 10& -10& -22\\ 17& -17& -17& 17\\ 10& -22& 22& -10\end{array}\right];<br><br>\mathrm{and}<br><br>$

wherein scaling comprises calculating a component-wise product using a matrix,

$\left[\begin{array}{cccc}{f}_2& f_4& f_2& f_4\\ <br><br>f_4& f_5& f_4& f_5\\ f_2& f_4& f_2& f_4\\ f_4& f_5& f_4& <br><br>f_5\end{array}\right]<br><br><br><br>\mathrm{where}<br><br><br><br>\begin{array}{c}{f}_2=\frac{64}{289\times <br><br>289}\\ f_4=\frac{64}{289\times <br><br>292}\\ f_5=\frac{64}{292\times <br><br>292}\end{array}.$

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=\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]<br><br>;<br><br>\mathrm{and}<br><br>$

wherein scaling comprises performing a component-wise product using a matrix,

$[<br><br>\begin{array}{cccccccc}{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\end{array}<br><br>]$ $\mathrm{where},<br><br>\begin{array}{c}{f}_0=<br><br>\frac{64}{288\times <br><br>288}\\ f_1=<br><br>\frac{64}{288\times <br><br>289}\\ f_2=<br><br>\frac{64}{289\times <br><br>289}\\ f_3=<br><br>\frac{64}{288\times <br><br>292}\\ f_4=<br><br>\frac{64}{289\times <br><br>292}\\ f_5=<br><br>\frac{64}{292\times <br><br>292}.\end{array}$

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=\frac{D·<br><br>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=[\; <li></li>\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}<br><br>];<br><br>\mathrm{and}$

wherein the transform sub-component matrices are

$\begin{array}{c}{T}_8^e=\left[\begin{array}{cccccccc}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\end{array}\right]<br><br>\\ T_8^o=\left[\begin{array}{cccccccc}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\end{array}\right].\end{array}$

33. The method of claim 31 wherein the transform basis function matrix is

$T_4=\left[\begin{array}{cccc}17& 17& 17& 17\\ 22& 10& -10& -22\\ 17& -17& -17& 17\\ 10& -22& 22& -10\end{array}\right];$

and

wherein the transform sub-component matrices are

$\begin{array}{c}{T}_4^e=\left[\begin{array}{cccc}8& 8& 8& 8\\ 11& 5& -5& -11\\ 8& -8& -8& 8\\ 5& -11& 11& -5\end{array}\right]\\ T_4^o=\left[\begin{array}{cccc}1& 1& 1& 1\\ 0& 0& 0& 0\\ 1& -1& -1& 1\\ 0& 0& 0& 0\end{array}\right].\end{array}$

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=\frac{D·<br><br>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.