Encoding video data using reversible integer approximations of orthonormal transforms

• US 9,665,541 B2
• Filed: 04/25/2014
• Issued: 05/30/2017
• Est. Priority Date: 04/25/2013
• Status: Active Grant

• Current Assignee: Mozilla
• Original Assignee: Mozilla
• Inventors: Terriberry, Timothy B.
• Primary Examiner(s): Kelley, Christopher S
• Assistant Examiner(s): Messmore, Jonathan
• Application Number:
  US14/262,626
• Publication Number:
  US 20140348221A1
• Time in Patent Office: 1,131 Days
• Field of Search: 3752402
• 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 approximation having orthonormally scaled outputs to the received data, wherein the reversible transform approximation comprises, the data comprising at least one of image data and video data;

a first operation that receives the data as inputs and scales outputs asymmetrically;

a second operation that receives outputs from the first operation as inputs, and cancels the asymmetric scaling; and

a third operation that applies a rotation to outputs received from the second operation as inputs, wherein outputs of the third operation are orthonormally scaled compared to the inputs of the first operation.

2. The method of claim 1 wherein:

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

the first operation is a butterfly-type transform stage receiving two of the DCT inputs, further wherein two outputs of the first operation are scaled by ½ and

connected to the second operation, the second operation having two outputs.

3. The method of claim 1 wherein:

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

the first operation is a butterfly-type transform stage receiving a first two of the DCT inputs, the outputs of the first operation being scaled by ½ and

connected to the second operation;

the second operation receives a second two of the inputs, the outputs of the second operation being scaled by ½ and

connected to the third operation; and

the third operation comprising a third transform stage and a fourth transform stage, where 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.

4. The method of claim 1 wherein:

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

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.

5. The method of claim 1 wherein:

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

the first operation is a butterfly-type transform stage receiving two of the WHT inputs, further wherein two outputs of the first operation are scaled by ½ and

connected to the second operation, the second operation having two outputs.

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

7. The method of claim 1 wherein:

the transform approximation is of a 2ⁿ point reversible transform having 2ⁿ inputs and 2ⁿ orthonormally scaled 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 orthonormally scaled outputs of the transform.

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

a plurality of inputs for receiving the data, the data comprising at least one of image data and video data; and

a reversible transform approximation block, connected to the inputs, having a same plurality of orthonormally scaled outputs,

wherein the reversible transform approximation block comprises;

a first operation that receives the data as inputs and scales outputs asymmetrically;

a second operation that receives outputs from the first operation as inputs, and cancels the asymmetric scaling; and

a third operation that applies a rotation to outputs received from the second operation as inputs, wherein outputs of the third operation are orthonormally scaled compared to the inputs of the first operation.

9. The apparatus of claim 8 wherein:

the transform approximation block approximates a 4-point Discrete Cosine Transform (DCT) having four inputs and four outputs; and

the first operation is a butterfly-type transform stage receiving two of the DCT inputs, further wherein two outputs of the first operation are scaled by ½ and

connected to the second operation, the second operation having two outputs.

10. The apparatus of claim 8 wherein:

the transform approximation block approximates an 8-point Discrete Cosine Transform (DCT) having eight inputs and eight outputs;

the first operation is a butterfly-type transform stage receiving a first two of the DCT inputs, the outputs of the first operation being scaled by ½ and

connected to the second operation;

the second operation receives a second two of the inputs, the outputs of the second operation being scaled by ½ and

connected to the third operation; and

the third operation comprising a third transform stage and a fourth transform stage, where 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.

11. The apparatus of claim 8 wherein:

the transform approximation block approximates an 2ⁿ point Discrete Cosine Transform (DCT) having 2ⁿ inputs and 2ⁿ orthonormally scaled 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 orthonormally scaled outputs of the transform approximation block.

12. The apparatus of claim 8 wherein:

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

the first operation is a butterfly-type transform stage receiving two of the WHT inputs, further wherein two outputs of the first operation are scaled by ½ and

connected to the second operation, the second operation having two outputs.

13. The apparatus of claim 8 wherein the transform approximation block approximates a Haar Wavelet Transform.

14. The apparatus of claim 8 wherein:

the transform approximation block approximates a 2ⁿ point reversible transform having 2ⁿ inputs and 2ⁿ orthonormally scaled 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 orthonormally scaled outputs of the transform approximation block.

15. 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, the data comprising at least one of image data and video data; and

apply a reversible transform approximation having orthonormally scaled outputs to the received data, wherein the reversible transform approximation comprises;

a first operation that receives the data as inputs and scales outputs asymmetrically;

a second operation that receives outputs from the first operation as inputs, and cancels the asymmetric scaling; and

a third operation that applies a rotation to outputs received from the second operation as inputs, wherein outputs of the third operation are orthonormally scaled compared to the inputs of the first operation.

16. The computer program product of claim 15, wherein:

the transform approximation is a 2ⁿ point reversible transform having 2ⁿ inputs and 2ⁿ orthonormally scaled 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 orthonormally scaled outputs of the transform.