ENCODING VIDEO DATA USING REVERSIBLE INTEGER APPROXIMATIONS OF ORTHONORMAL TRANSFORMS

• US 20140348221A1
• Filed: 04/25/2014
• Published: 11/27/2014
• Est. Priority Date: 04/25/2013
• Status: Active Grant

• Current Assignee: Mozilla
• Original Assignee: Mozilla
• Inventors: Terriberry, Timothy B.
• Granted Patent: US 9,665,541 B2
• Time in Patent Office: Days
• US Class Current: 375/240.2
• 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/625 using discrete cosine transform [DCT]
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets

Abstract

An apparatus and method for lossless encoding of video data is provided, including a reversible transform, connected to a plurality of inputs, having a same plurality of orthonormal outputs, wherein the reversible transform comprises rotations combined with internally cancelled scalings that are connected to said orthonormal outputs.

Claims

1. A method for lossless encoding of data, comprising:

receiving the data; and

applying a reversible transform having orthonormal outputs to the received data,

wherein the reversible transform combines rotations with internally cancelled scalings to achieve said orthonormal outputs.

2. The method of claim 1 wherein the data comprises image data.

3. The method of claim 1 wherein the data comprises video data.

4. The method of claim 1 wherein:

the transform is a 4-point Discrete Cosine Transform (DCT) having four inputs and four orthonormal outputs;

two of the inputs are connected to a butterfly-type first transform stage having two outputs, which are scaled by ½ and

connected to a second transform stage having two outputs; and

the outputs of the transform stages comprise the orthonormal outputs of the transform.

5. The method of claim 1 wherein:

the transform is an 8-point Discrete Cosine Transform (DCT) having eight inputs and eight orthonormal outputs;

a first two of the inputs are connected to a butterfly-type first transform stage, the outputs of which are scaled by ½ and

connected to a second transform stage;

a second two of the inputs are connected to the second transform stage, the outputs of which are scaled by ½ and

connected to a third transform stage;

a third two of the inputs are connected to the third transform stage, the outputs of which are scaled by ½ and

connected to a fourth transform stage having two outputs; and

the outputs of the transform stages comprise the orthonormal outputs of the transform.

6. The method of claim 1 wherein:

the transform is an 2ⁿ point Discrete Cosine Transform (DCT) having 2ⁿ inputs and 2ⁿ orthonormal outputs, where n is an integer;

each pair of the 2ⁿ inputs are connected to a respective transform stage, the outputs from all but the last of which are scaled by a factor of ½ and

connected to at least one further transform stage that collectively cancels the factor; and

the outputs of the transform stages comprise the orthonormal outputs of the transform.

7. The method of claim 1 wherein:

the transform is a 4-point Walsh-Hadamard Transform (WHT) having four inputs and four orthonormal outputs;

two of the inputs are connected to a butterfly-type first transform stage having two outputs, which are scaled by ½ and

connected to a second transform stage having two outputs; and

the outputs of the transform stages comprise the orthonormal outputs of the transform.

8. The method of claim 1 wherein the transform is a Haar Wavelet Transform.

9. The method of claim 1 wherein:

the transform is a 2ⁿ point reversible transform having 2ⁿ inputs and 2ⁿ orthonormal outputs, where n is an integer;

each pair of the 2ⁿ inputs are connected to a respective transform stage, the outputs from all but the last of which are scaled by an asymmetrical factor and connected to at least one further transform stage that collectively cancels the asymmetrical factor; and

the outputs of the transform stages comprise the orthonormal outputs of the transform.

10. An apparatus for lossless encoding of data, comprising:

a plurality of inputs for receiving the data; and

a reversible transform, connected to the inputs, having a same plurality of orthonormal outputs,

wherein the reversible transform comprises rotations combined with internally cancelled scalings that are connected to said orthonormal outputs.

11. The apparatus of claim 10 wherein the data comprises image data.

12. The apparatus of claim 10 wherein the data comprises video data.

13. The apparatus of claim 10 wherein:

the transform is a 4-point Discrete Cosine Transform (DCT) having four inputs and four orthonormal outputs;

two of the inputs are connected to a butterfly-type first transform stage having two outputs, which are scaled by ½ and

connected to a second transform stage having two outputs; and

the outputs of the transform stages comprise the orthonormal outputs of the transform.

14. The apparatus of claim 10 wherein:

the transform is an 8-point Discrete Cosine Transform (DCT) having eight inputs and eight orthonormal outputs;

a first two of the inputs are connected to a butterfly-type first transform stage, the outputs of which are scaled by ½ and

connected to a second transform stage;

a second two of the inputs are connected to the second transform stage, the outputs of which are scaled by ½ and

connected to a third transform stage;

a third two of the inputs are connected to the third transform stage, the outputs of which are scaled by ½ and

connected to a fourth transform stage having two outputs; and

the outputs of the transform stages comprise the orthonormal outputs of the transform.

15. The apparatus of claim 10 wherein:

the transform is an 2ⁿ point Discrete Cosine Transform (DCT) having 2ⁿ inputs and 2ⁿ orthonormal outputs, where n is an integer;

each pair of the 2ⁿ inputs are connected to a respective transform stage, the outputs from all but the last of which are scaled by a factor of ½ and

connected to at least one further transform stage that collectively cancels the factor; and

the outputs of the transform stages comprise the orthonormal outputs of the transform.

16. The apparatus of claim 10 wherein:

the transform is at least a 4-point Walsh-Hadamard Transform (WHT) having four inputs and four orthonormal outputs;

two of the inputs are connected to a butterfly-type first transform stage having two outputs, which are scaled by ½ and

connected to a second transform stage having two outputs; and

the outputs of the transform stages comprise the orthonormal outputs of the transform.

17. The apparatus of claim 10 wherein the transform is a Haar Wavelet Transform.

18. The apparatus of claim 10 wherein:

the transform is a 2ⁿ point reversible transform having 2ⁿ inputs and 2ⁿ orthonormal outputs, where n is an integer;

each pair of the 2ⁿ inputs are connected to a respective transform stage, the outputs from all but the last of which are scaled by an asymmetrical factor and connected to at least one further transform stage that collectively cancels the asymmetrical factor; and

the outputs of the transform stages comprise the orthonormal outputs of the transform.

19. A computer program product for lossless encoding of data, comprising a non-transitory computer-readable medium having a computer-readable program code embodied therein to be executed by one or more processors, the program code including instructions to:

receive the data; and

apply a reversible transform having orthonormal outputs to the received data,

wherein the reversible transform combines rotations with internally cancelled scalings to achieve said orthonormal outputs.

20. The computer program product of claim 19, wherein:

the transform is a 2ⁿ point reversible transform having 2ⁿ inputs and 2ⁿ orthonormal outputs, where n is an integer;

each pair of the 2ⁿ inputs are connected to a respective transform stage, the outputs from all but the last of which are scaled by an asymmetrical factor and connected to at least one further transform stage that collectively cancels the asymmetrical factor; and

the outputs of the transform stages comprise the orthonormal outputs of the transform.