Fast multiplierless integer invertible transforms

• US 20070196025A1
• Filed: 01/04/2007
• Published: 08/23/2007
• Est. Priority Date: 01/05/2006
• Status: Active Grant

• Current Assignee: FastVDO LLC
• Original Assignee: FastVDO LLC
• Inventors: Liu, Lijie, Tran, Trac, Topiwala, Pankai
• Granted Patent: US 8,548,265 B2
• Time in Patent Office: Days
• US Class Current: 382/250
• 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/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/45 performing compensation of the inverse transform mismatch, e.g. Inverse Discrete Cosine Transform [IDCT] mismatch
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

This invention relates to the design and implementation of a large family of fast, efficient, hardware-friendly fixed-point multiplierless inverse discrete cosine transforms (IDCT) and the corresponding forward transform counterparts. All of the proposed structures comprises of butterflies and dyadic-rational lifting steps that can be implemented using only shift-and-add operations. The approach also allows the computational scalability with different accuracy-versus-complexity trade-offs. Furthermore, the lifting construction allows a simple construction of the corresponding multiplierless forward DCT, providing bit-exact reconstruction if properly pairing with our proposed IDCT. With appropriately-chosen parameters, all of the disclosed structures can easily pass IEEE-1180 test. The high-accuracy algorithm of the present invention is over 100 times more accurate than IEEE-1180 specifications, leading to practically drifting-free reconstruction in popular MPEG-2 and MPEG-4 codecs even at the lowest quantization setting.

Claims

1-10. -10. (canceled)

11. An apparatus for block coding of windows of digitally represented signal elements of block size M, where M is any integer greater than unity, chosen from one of the dimensionalities of the signal, comprising an invertible transformation of the signal elements, wherein the invertible transformation is representable by a series of at least one of the following elements:

i) butterfly steps;

ii) lifting steps, wherein the choice of coefficients is complex;

iii) planar rotations;

iv) scaling; and

v) reflections.

12. The apparatus of claim 11 wherein the invertible transformation is a unitary transform.

13. The apparatus of claim 11 wherein the invertible transformation is an approximation of a unitary transform.

14. The apparatus of claim 11 wherein the invertible transformation is an approximation of a forward discrete cosine transform.

15. The apparatus of claim 11 wherein the invertible transformation is an approximation of an inverse discrete cosine transform.

16. The apparatus of claim 11 wherein the lifting steps have real coefficients.

17. The apparatus of claim 11 wherein the lifting steps have real rational coefficients.

18. The apparatus of claim 11 wherein the lifting steps have dyadic rational coefficients in the form of

$\frac{k}{2^n}$

where k and n are integers.

19. The apparatus of claim 11 wherein the lifting steps have coefficients selected within a

$\pm$

1 8

range from their theoretical values listed in Tables 1, 2, or 3 of this application.

20. The apparatus of claim 11 wherein the invertible transform is representable using only butterflies and lifting steps.

21. The apparatus of claim 20 wherein the lifting steps have rational coefficients.

22. The apparatus of claim 20 wherein the lifting steps have dyadic rational coefficients.

23. The apparatus of claim 11 wherein the lifting steps are implemented as a series of binary-shift-and-add operations.

24. The apparatus of claim 12 wherein the invertible transformation is modified with permutations, sign changes, and scaling changes of either inputs, outputs or intermediate values.

25. A method for coding, storing, transmitting, or decoding length M blocks of digitally represented signal elements comprising the following steps, wherein at least one of steps (b) and (g) is applied:

a. pre-processing signal elements to modify the signal elements;

b. forward transforming the modified signal elements;

c. quantizing and entropy coding transform output coefficients;

d. transmitting or storing entropy coded data;

e. decoding the entropy coded data;

f. dequantizing the quantized transform output coefficients;

g. inverse transforming the dequantized transform output coefficients to reconstruct the modified signal elements; and

h. post-processing of the modified signal elements to reconstruct the modified signal elements.

26. An apparatus for block coding of windows of digitally represented signal elements of block size M, where M is any integer greater than unity, chosen from one of the dimensionalities of the signal, comprising an invertible transformation of the signal elements, wherein

a) the invertible transformation is an approximation of a discrete cosine transform (DCT) or an inverse discrete cosine transform (IDCT);

and

b) the approximation is representable by a series of at least one of the following elements;

i) butterfly steps;

ii) lifting steps, wherein the choice of coefficients is real; and

iii) planar rotations.

27. The apparatus of claim 26 wherein the lifting steps have rational coefficients.

28. The apparatus of claim 26 wherein the lifting steps have dyadic rational coefficients in the form of

$\frac{k}{2^n}$

where k and n are integers.

29. The apparatus of claim 28 wherein the lifting steps have coefficients selected within a

$\pm$

1 8

range from their theoretical values listed in Tables 1, 2, or 3 of this application.

30. The apparatus of claim 26 wherein the approximate transform is representable using only butterflies and lifting steps.

31. The apparatus of claim 30 wherein the lifting steps have rational coefficients.

32. The apparatus of claim 30 wherein the lifting steps have dyadic rational coefficients.

33. The apparatus of claim 26 wherein the dyadic lifting steps are implemented as a series of binary-shift-and-add operations.

34. The apparatus of claim 26 wherein the transformation is modified with permutations, sign changes, and scaling changes of either inputs, outputs or intermediate values.