Low-complexity 2-power transform for image/video compression
View Patent ↗To encode image and video data using a transform having low computational complexity and high compression efficiency, all elements of the matrix can be expressed with power-of-2 elements, with a template of the matrix approximating a DCT matrix.
1. A method for image data compression, comprising:
Approximating at least one non-power-of-2 element of a base matrix as a power-of-2 element such that all elements of a resultant matrix T 2 are power-of-2 elements, wherein the resultant matrix T 2 is:
T
2
=
(
1
1
1
1
1
1
1
1
a
b
c
d
-
d
-
c
-
b
-
a
e
f
-
f
-
e
-
e
-
f
f
e
c
d
-
a
-
b
b
a
-
d
-
c
1
-
1
-
1
1
1
-
1
-
1
1
b
-
a
-
d
c
-
c
d
a
-
b
f
-
e
e
-
f
-
f
e
-
e
f
d
-
c
b
-
a
a
-
b
c
-
d
)
wherein further, for floating point coefficients a, b, c, d, e, and f:
a≧b≧c≧d and e≧f,
a=2, b=2, c=1, all d=½ or all d=¼, e=2 and f=1; and
encoding video data using the resultant matrix T 2 .
2. A method according to claim 1 , wherein the base matrix is a DCT (discrete cosine transform) matrix.
3. A method according to claim 1 , wherein the approximating includes manipulating an order of the one or more elements in a particular row of the base matrix.
4. A method according to claim 1 , wherein the approximating includes manipulating the signs of the one or more elements in a particular row of the base matrix.
5. A method according to claim 1 , wherein the approximating includes manipulating an order and the signs of the one or more elements in a particular row of the base matrix.
6. A method according to claim 1 , wherein the approximating includes approximating floating point coefficients as power-of-2 coefficients to preserve a threshold relationship between the floating point coefficients.
7. A method according to claim 1 , wherein the approximating includes approximating floating point coefficients as power-of-2 coefficients to preserve a relative ratio among the floating point coefficients.
8. A method according to claim 1 , wherein the row vectors of the resultant matrix T 2 are orthogonal.
9. A method according to claim 1 , wherein multiplication for non-integer d is implemented by a two-bit right shift.
10. An image data encoding apparatus, comprising:
a transformer to perform a 2-power transform on an incoming array of pixels, the transformer to perform the 2-power transform using a symmetrical matrix in which all elements are expressed as power-of-2 elements, wherein the resulting matrix T 2 is:
T
2
=
(
1
1
1
1
1
1
1
1
a
b
c
d
-
d
-
c
-
b
-
a
e
f
-
f
-
e
-
e
-
f
f
e
c
d
-
a
-
b
b
a
-
d
-
c
1
-
1
-
1
1
1
-
1
-
1
1
b
-
a
-
d
c
-
c
d
a
-
b
f
-
e
e
-
f
-
f
e
-
e
f
d
-
c
b
-
a
a
-
b
c
-
d
)
wherein further, for floating point coefficients a, b, c, d, e, and f:
a≧b≧c≧d and e≧f,
a=2, b=2, c=1, all d=½ or all d=¼, e=2 and f=1;
a quantizer to quantize the transformer result; and
an inverse transformer to perform an inverse 2-power transform on the quantizer result.
11. An apparatus according to claim 10 , wherein an order of two or more elements in a particular row of the symmetrical matrix have been changed within the resulting matrix T 2 .
12. An apparatus according to claim 10 , wherein the signs of one or more elements in a particular row of the symmetrical matrix have been changed within the resulting matrix T 2 .
13. An apparatus according to claim 10 , wherein the symmetrical matrix is a DCT matrix template.
14. An apparatus according to claim 10 , wherein the row vectors of the resulting matrix T 2 are orthogonal.
15. A computer-readable storage medium encoded with one or more computer-executable instructions, the one or more computer-executable instructions configured to cause one or more processors to:
create a matrix such that all elements in the matrix are expressed as power-of-2 coefficients, wherein the resultant matrix T 2 is:
T
2
=
(
1
1
1
1
1
1
1
1
a
b
c
d
-
d
-
c
-
b
-
a
e
f
-
f
-
e
-
e
-
f
f
e
c
d
-
a
-
b
b
a
-
d
-
c
1
-
1
-
1
1
1
-
1
-
1
1
b
-
a
-
d
c
-
c
d
a
-
b
f
-
e
e
-
f
-
f
e
-
e
f
d
-
c
b
-
a
a
-
b
c
-
d
)
wherein further the floating point coefficients are:
a=2, b=2, c=1, all d= 1/2 or all d=¼, e=2 and f=1; and
encode video data using the resultant matrix T 2 .
16. A computer-readable storage medium according to claim 15 , wherein to create the matrix is to change at least one of an order of one or more elements in a particular row of a template matrix.
17. A computer-readable storage medium according to claim 15 , wherein to create the matrix is to change the sign of at least one element in a particular row of a template matrix.
18. A computer-readable storage medium according to claim 17 , wherein the template matrix is a DCT matrix.
19. A computer-readable storage medium according to claim 16 , wherein the template matrix is a DCT matrix.
20. A computer-readable storage medium according to claim 15 , wherein the row vectors of the resultant matrix T 2 are orthogonal.
21. An image data encoding apparatus, comprising:
means for performing a 2-power transform on an incoming array of pixels, wherein all elements of the 2-power transform are equal to power-of-2 elements such that the resulting transform matrix T 2 is:
T
2
=
(
1
1
1
1
1
1
1
1
a
b
c
d
-
d
-
c
-
b
-
a
e
f
-
f
-
e
-
e
-
f
f
e
c
d
-
a
-
b
b
a
-
d
-
c
1
-
1
-
1
1
1
-
1
-
1
1
b
-
a
-
d
c
-
c
d
a
-
b
f
-
e
e
-
f
-
f
e
-
e
f
d
-
c
b
-
a
a
-
b
c
-
d
)
wherein further the floating point coefficients are:
a=2, b=2, c=1, all d=½ or all d=¼, e=2 and f=1;
means for quantizing the transformer result; and
means for performing an inverse 2-power transform on the quantizer result.