US2006294173A1PendingUtilityA1
Implementation of a transform and of a subsequent quantization
Est. expiryAug 30, 2021(expired)· nominal 20-yr term from priority
H04N 19/126H04N 19/18G06F 17/147H04N 19/60H04N 19/124
45
PatentIndex Score
0
Cited by
0
References
0
Claims
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
exact text as granted — not AI-modified1 . 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 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:
[
a
a
a
a
b
c
-
c
-
b
a
-
a
-
a
a
c
-
b
b
-
c
]
,
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
=
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:
[
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
]
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
=
1
2
1
1
+
c
b
2
+
d
b
2
+
e
b
2
and
f
=
1
2
1
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 n , 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
[
a
b
a
c
a
c
-
a
-
b
a
-
c
-
a
b
a
-
b
a
-
c
]
,
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
=
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:
[
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
]
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
=
1
2
1
1
+
c
b
2
+
d
b
2
+
e
b
2
and
f
=
1
2
1
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 .Cited by (0)
No later patents cite this yet.
References (0)
No backward citations on record.