Implementation of a transform and of a subsequent quantization

• US 20060294173A1
• Filed: 01/27/2006
• Published: 12/28/2006
• Est. Priority Date: 08/30/2001
• Status: Abandoned Application

• Current Assignee: Antti Hallapuro, Kim Simelius
• Original Assignee: Antti Hallapuro, Kim Simelius
• Inventors: Hallapuro, Antti, Simelius, Kim
• Application Number:
  US11/342,258
• Publication Number:
  US 20060294173A1
• Time in Patent Office: Days
• US Class Current: 708/402
• 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/126 Details of normalisation or weighting functions, e.g. normalisation matrices or variable uniform quantisers
• CPC Class Codes: H04N 19/18 the unit being a set of transform coefficients
• CPC Class Codes: H04N 19/60 using transform coding

Abstract

The invention relates to an approximation of a DCT and a quantization which are to be applied subsequently to digital data for compression of this digital data. In order to improve the transform, it is proposed to simplify a predetermined transform matrix to require less operations when applied to digital data. In addition, elements of the simplified transform matrix constituting irrational numbers are approximated by rational numbers. These measures are compensated by extending a predetermined quantization to include the operations which were removed in the simplification of the predetermined transform matrix. The included operations are further adjusted to compensate for the approximation of elements of the simplified transform matrix by rational numbers. If the simplified transform matrix and the extended quantization are used as basis for implementation, a fast transform with a good resulting quality can be achieved. An approximation of an IDCT employed in decompression of compressed digital data can be simplified correspondingly.

Claims

1. A method for implementing an approximation of a discrete cosine transform (DCT) and a quantization, which transform and which quantization are to be applied subsequently to digital data for compression of said digital data, said method comprising:

simplifying a predetermined transform matrix to require less operations when applied to digital data;

approximating elements of said simplified transform matrix constituting irrational numbers by rational numbers;

extending a predetermined quantization to include said operations which were removed in said simplification of said predetermined transform matrix, which included operations are adjusted to compensate for said approximation of elements of said simplified transform matrix by rational numbers; and

employing said simplified transform matrix with said approximated elements and said extended quantization as basis for implementing said sequence of a transform and a quantization which are to be applied to digital data.

2. A method according to claim 1, wherein said step of simplifying said predetermined transform matrix to require less operations when applied to digital data comprises factoring said predetermined transform matrix into a diagonal matrix to be used for extending said predetermined quantization and a simplified transform matrix.

3. A method according to claim 1, wherein said rational numbers can be represented by fractions having a denominator equal to 2², wherein n is an integer.

4. A method according to claim 3, wherein in said transform implementation divisions are realized by bit-shifting.

5. A method according to claim 1, wherein said approximation is adjusted in a way ensuring that a resulting transform has an inverse transform, i.e. that a transpose of said predetermined transform matrix, including said approximations, multiplied by said predetermined transform matrix, including said approximations, is equal to an identity matrix.

6. A method according to claim 1, wherein said predetermined transform matrix is a 4×

4 matrix of a form;

$\left[\begin{array}{cccc}a& a& a& a\\ b& c& -c& -b\\ a& -a& -a& a\\ c& -b& b& -c\end{array}\right],$

wherein a=½

, b=√

{square root over (1/2)}·

cos(π

/8), c=√

{square root over (1/2)}·

cos(3π

/8), wherein ‘

c’

is substituted in said matrix according to an equation d=c/b, and wherein said predetermined transform matrix is simplified by factoring said predetermined transform matrix into a diagonal matrix comprising diagonal values {a, b, a, b} and a simplified transform matrix comprising only elements having absolute values of ‘

1’ and

‘

d’

, which diagonal matrix is to be used for extending said predetermined quantization.

7. A method according to claim 6, wherein in said simplified transform matrix said value ‘

d’

is approximated by a rational number 7/16.

8. A method according to claim 6, wherein in said simplified transform matrix said value ‘

d’

is approximated by a rational number, and wherein in said diagonal matrix said value ‘

b’

is adjusted to

$b=\sqrt{\frac{0.5}{1+d^2}},$

‘

d’

being in said equation said rational number.

9. A method according to claim 6, wherein in said simplified transform matrix said value ‘

d’

is approximated by a rational number 7/16, and wherein said transform is implemented for a transform of a one-dimensional sequence of four values X[0], X[1], X[2], X[3] respectively with the following equations;

e=X[0]+X[3],
f=X[1]+X[2],
Y[0]=e+f,
Y[2]=e−

f,
e=X[0]−

X[3],
f=X[1]−

X[2],
Y[1]=e+(f−

f/8)/2,
and
Y[3]=(e−

e/8)/2−

f,

wherein Y[0], Y[1], Y[2], Y[3] is a one-dimensional sequence of four transformed values, and wherein e and f are auxiliary variables.

10. A method according to claim 1, wherein said predetermined transform matrix is a 8×

8 matrix of a form;

$\left[\begin{array}{cccccccc}a& a& a& a& a& a& a& a\\ b& c& d& e& -e& -d& -c& -b\\ f& g& -g& -f& -f& -g& g& f\\ c& -e& -b& -d& d& b& e& -c\\ a& -a& -a& a& a& -a& -a& a\\ d& -b& e& c& -c& -e& b& -d\\ g& -f& f& -g& -g& f& -f& g\\ e& -d& c& -b& b& -c& d& -e\end{array}\right]$

wherein a=1/(2√

{square root over (2)}), b=½

·

cos(π

/16), c−

½

·

cos(3π

/16),

d=½

·

cos(5π

/16), e=½

·

cos(7π

/16), f=½

·

cos(π

/8),

g=½

·

cos(3π

/8), wherein ‘

c’

is substituted in said matrix according to an equation c_b=c/b, wherein ‘

d’

is substituted in said matrix according to an equation d_b=d/b, wherein ‘

e’

is substituted in said matrix according to an equation e_b=e/b, wherein ‘

g’

is substituted in said matrix according to an equation g_f=g/f, and wherein said predetermined transform matrix is simplified by factoring said predetermined transform matrix into a diagonal matrix comprising diagonal values {a, b, f, b, a, b, f, b} and a simplified transform matrix comprising only elements having absolute values of ‘

1’

, ‘

c_b’

, ‘

d_b’

, ‘

e_b’ and

‘

g_f’

, which diagonal matrix is to be used for extending said predetermined quantization.

11. A method according to claim 10, wherein in said simplified transform matrix said value ‘

c_b’

is approximated by a rational number 15/16, said value ‘

d_b’

is approximated by a rational number 9/16, said value ‘

e_b’

is approximated by a rational number ¼

, and said value ‘

g_f’

is approximated by a rational number 7/16.

12. A method according to claim 10, wherein in said simplified transform matrix said values ‘

c_b’

, ‘

d_b’

, ‘

e_b’ and

‘

g_f’

are approximated by rational numbers, and wherein in said diagonal matrix said values ‘

b’ and

‘

f’

are adjusted to

$b=\frac{1}{\sqrt{2}}<br><br>\frac{1}{\sqrt{1+c_b^2+d_b^2+e_b^2}}$ $\mathrm{and}$ $f=\frac{1}{2}<br><br>\frac{1}{\sqrt{1+g_f^2}},$

values ‘

c_b’

, ‘

d_b’

, ‘

e_b’ and

‘

g_f’

being in said equation said rational numbers.

13. A method according to claim 1, wherein for a two-dimensional transform to be applied to two-dimensional digital data, said simplified predetermined transform matrix with said approximated elements and a transpose of said simplified transform matrix with said approximated elements are employed as basis for implementing said transform, said extended quantization including operations removed from both of said matrices, which operations are adjusted to compensate for said approximations in both of said matrices.

14. A method according to claim 1, wherein for quantization, a quantization matrix is determined by multiplying a predetermined sequence of quantization coefficients with a matrix extracted from said predetermined transform matrix for simplifying said predetermined transform matrix, which extracted matrix comprises said operations removed from said predetermined transform matrix, and which extracted matrix is adjusted to compensate for said approximation of elements of said simplified transform matrix by rational numbers.

15. A method for implementing a dequantization and an approximation of an inverse discrete cosine transform (IDCT), wherein for decompression of digital data said quantization is to be applied in sequence with said inverse transform to compressed digital data, said method comprising:

simplifying a predetermined inverse transform matrix to require less operations when applied to digital data;

approximating elements of said simplified inverse transform matrix constituting irrational numbers by rational numbers;

extending a predetermined dequantization to include said operations which were removed in said simplification of said predetermined inverse transform matrix, which included operations are adjusted to compensate for said approximation of elements of said simplified inverse transform matrix by rational numbers; and

employing said extended dequantization and said simplified inverse transform matrix with said approximated elements as basis for implementing said sequence of a dequantization and an inverse transform which are to be applied to compressed digital data.

16. A method according to claim 15, wherein for dequantization, a dequantization matrix is determined by multiplying a predetermined sequence of dequantization coefficients with a matrix extracted from said predetermined inverse transform matrix for simplifying said predetermined inverse transform matrix, which extracted matrix comprises said operations removed from said predetermined inverse transform matrix, and which extracted matrix is adjusted to compensate for said approximation of elements of said simplified inverse transform matrix by rational numbers.

17. A method according to claim 15, wherein said step of simplifying said predetermined inverse transform matrix to require less operations when applied to digital data comprises factoring said predetermined inverse transform matrix into a diagonal matrix to be used for extending said predetermined dequantization and a simplified inverse transform matrix.

18. A method according to claim 15, wherein said rational numbers can be represented by fractions having a denominator equal to 2ⁿ, wherein n is an integer.

19. A method according to claim 18, wherein in said inverse transform implementation divisions are realized by bit-shifting.

20. A method according to claim 15, wherein said approximation is adjusted in a way ensuring that a resulting inverse transform corresponds to a transform, i.e. that said predetermined inverse transform matrix, including said approximations, multiplied by a transpose of said predetermined inverse transform matrix, including said approximations, is equal to an identity matrix.

21. A method according to claim 15, wherein said predetermined inverse transform matrix is a 4×

4 matrix of a form

$\left[\begin{array}{cccc}a& b& a& c\\ a& c& -a& -b\\ a& -c& -a& b\\ a& -b& a& -c\end{array}\right],$

wherein a=½

, b=√

{square root over (1/2)}·

cos(π

/8), c=√

{square root over (1/2)}·

cos(3π

/8), wherein ‘

c’

is substituted in said matrix according to an equation d=c/b, and wherein said predetermined inverse transform matrix is simplified by factoring said predetermined inverse transform matrix into a diagonal matrix comprising diagonal values {a, b, a, b} and a simplified inverse transform matrix comprising only elements having absolute values of ‘

1’ and

‘

d’

, which diagonal matrix is to be used for extending said predetermined quantization.

22. A method according to claim 21, wherein in said simplified inverse transform matrix said value ‘

d’

is approximated by a rational number 7/16.

23. A method according to claim 21, wherein in said simplified inverse transform matrix said value ‘

d’

is approximated by a rational number, and wherein in said diagonal matrix said value ‘

b’

is adjusted to

$b=\sqrt{\frac{0.5}{1+d^2}},$

‘

d’

being in said equation said rational number.

24. A method according to claim 21, wherein in said simplified inverse transform matrix said value ‘

d’

is approximated by a rational number 7/16, and wherein said inverse is implemented for a transform of a one-dimensional sequence of four values X[0], X[1], X[2], X[3] respectively with the following equations;

e=X[0]+X[3],
f=X[1]+X[2],
Y[0]=e+f,
Y[2]=e−

f,
e=X[0]−

X[3],
f=X[1]−

X[2],
Y[1]=e+(f−

f/8)/2,
and
Y[3]=(e−

e/8)/2−

f,

wherein Y[0], Y[1], Y[2], Y[3] is a one-dimensional sequence of four transformed values, and wherein e and f are auxiliary variables.

25. A method according to claim 15, wherein said predetermined transform matrix is a 8×

8 matrix of a form;

$\left[\begin{array}{cccccccc}a& a& a& a& a& a& a& a\\ b& c& d& e& -e& -d& -c& -b\\ f& g& -g& -f& -f& -g& g& f\\ c& -e& -b& -d& d& b& e& -c\\ a& -a& -a& a& a& -a& -a& a\\ d& -b& e& c& -c& -e& b& -d\\ g& -f& f& -g& -g& f& -f& g\\ e& -d& c& -b& b& -c& d& -e\end{array}\right]$

wherein a=1/(2√

{square root over (2)}), b=½

·

cos(π

/16), c−

½

·

cos(3π

/16),

d=½

·

cos(5π

/16), e=½

·

cos(7π

/16), f=½

·

cos(π

/8),

g=½

·

cos(3π

/8), wherein ‘

c’

is substituted in said matrix according to an equation c_b=c/b, wherein ‘

d’

is substituted in said matrix according to an equation d_b=d/b, wherein ‘

e’

is substituted in said matrix according to an equation e_b=e/b, wherein ‘

g’

is substituted in said matrix according to an equation g_f=g/f, and wherein said predetermined transform matrix is simplified by factoring said predetermined transform matrix into a diagonal matrix comprising diagonal values {a, b, f, b, a, b, f, b} and a simplified transform matrix comprising only elements having absolute values of ‘

1’

, ‘

c_b’

, ‘

d_b’

, ‘

e_b’ and

‘

g_f’

, which diagonal matrix is to be used for extending said predetermined quantization.

26. A method according to claim 25, wherein in said simplified transform matrix said value ‘

c_b’

is approximated by a rational number 15/16, said value ‘

d_b’

is approximated by a rational number 9/16, said value ‘

e_b’

is approximated by a rational number ¼

, and said value ‘

g_f’

is approximated by a rational number 7/16.

27. A method according to claim 25, wherein in said simplified transform matrix said values ‘

c_b’

, ‘

d_b’

, ‘

e_b’ and

‘

g_f’

are approximated by rational numbers, and wherein in said diagonal matrix said values ‘

b’ and

‘

f’

are adjusted to

$b=\frac{1}{\sqrt{2}}<br><br>\frac{1}{\sqrt{1+c_b^2+d_b^2+e_b^2}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}<br><br>\text{\hspace{1em}<br><br>}<br><br>f=\frac{1}{2}<br><br>\frac{1}{\sqrt{1+g_f^2}},$

values ‘

c_b’

, ‘

e_b’ and

‘

g_f’

being in said equation said rational numbers.

28. A method according to claim 15, wherein for a two-dimensional inverse transform to be applied to two-dimensional dequantized digital data, said simplified predetermined inverse transform matrix with said approximated elements and a transpose of said simplified inverse transform matrix with said approximated elements are employed as basis for implementing said inverse transform, said extended dequantization including operations removed from both of said matrices, which operations are adjusted to compensate for said approximations in both of said matrices.

29. An encoder for compressing digital data comprising:

a transformer approximating a discrete cosine transform (DCT) for transforming digital data by applying a simplified transform matrix to said digital data, which simplified transform matrix is obtained by simplifying a predetermined transform matrix to require less operations when applied to digital data, and in which simplified transform matrix elements constituting irrational numbers are approximated by rational numbers; and

a quantization means coupled to an output of said transformer for quantizing said transformed digital data with an extended quantization, which extended quantization is obtained from a predetermined quantization by including said operations which are removed in said simplification of said predetermined transform matrix, said operations being adjusted to compensate for said approximation of elements of said simplified transform matrix.

30. A decoder for decompressing digital data compressed by a discrete cosine transform (DCT) or an approximation of a discrete cosine transform (DCT) and a subsequent quantization, said decoder comprising:

a dequantization means for dequantizing compressed digital data with an extended dequantization; and

a transformer approximating an inverse discrete cosine transform (IDCT) coupled to an output of said dequantization means for transforming dequantized digital data by applying a simplified inverse transform matrix, which simplified inverse transform matrix is obtained by simplifying a predetermined inverse transform matrix to require less operations when applied to digital data, and in which simplified transform matrix elements constituting irrational numbers are approximated by rational numbers;

wherein said extended dequantization applied by said dequantization means is obtained from a predetermined dequantization by including said operations which are removed in said simplification of said predetermined inverse transform matrix, said operations being adjusted to compensate for said approximation of elements of said simplified inverse transform matrix.

31. A method of implementing an approximation of a discrete cosine transform and implementing a quantization operation, the method comprising:

factorizing a discrete cosine transform matrix to extract a diagonal matrix, thereby obtaining a simplified transform matrix;

approximating elements of the simplified transform matrix constituting irrational numbers by rational numbers;

adjusting a predetermined set of quantization coefficients to absorb the effect of extracting said diagonal matrix and to compensate for approximating elements of the simplified transform matrix constituting irrational numbers by rational numbers; and

employing the simplified transform matrix with said approximated elements and the adjusted set of quantization coefficients as a basis for implementing a sequence of a discrete cosine transform and a quantization operation.

32. A method of encoding digital data, the method comprising:

applying a set of equations representing an approximated discrete cosine transform to a set of source values to obtain a corresponding set of approximated transform coefficients, the approximated discrete cosine transform having a matrix representation CXC^T, where X is a matrix comprising the set of source values, C is a matrix of approximate discrete cosine transform basis functions and C^T is the transpose of C, the approximated discrete cosine transform approximating a discrete cosine transform having a matrix representation AXA^T, where A is a matrix of discrete cosine transform basis functions and A^T is the transpose of matrix A, matrix C being related to matrix A by factorization of matrix A to extract a diagonal matrix B and a simplified transform matrix, and approximating elements of the simplified transform matrix constituting irrational numbers by rational numbers, matrix C^T being similarly related to matrix A^T; and

quantising the set of approximated transform coefficients by applying a set of quantization coefficients to the set of approximated transform coefficients to obtain a set of quantized transform coefficients, the set of quantization coefficients having values that absorb the effect of extracting said diagonal matrix B from both of matrices A and A^T and further compensate for the effect of approximating irrational numbers by rational numbers in both of matrices C and C^T.