System and method for trainable nonlinear prediction of transform coefficients in data compression

• US 6,704,718 B2
• Filed: 06/05/2001
• Issued: 03/09/2004
• Est. Priority Date: 06/05/2001
• Status: Expired due to Term

• Current Assignee: ThinkLogix, LLC (Ascend Innovation Management, LLC)
• Original Assignee: Microsoft Corporation
• Inventors: Malvar, Henrique S., Simard, Patrice Y., Burges, Chris J. C.
• Primary Examiner(s): Patel, Ramesh
• Assistant Examiner(s): Hirl, Joseph P.
• Application Number:
  US09/681,789
• Publication Number:
  US 20020184272A1
• Time in Patent Office: 1,008 Days
• Field of Search: 706/21, 706/15, 706/16
• US Class Current: 706/21
• CPC Class Codes: H04N 19/105 Selection of the reference unit for prediction within a chosen coding or prediction mode, e.g. adaptive choice of position and number of pixels used for prediction
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/187 the unit being a scalable video layer
• CPC Class Codes: H04N 19/1883 the unit relating to sub-band structure, e.g. hierarchical level, directional tree, e.g. low-high [LH], high-low [HL], high-high [HH]
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets

Abstract

A system and method for performing trainable nonlinear prediction of transform coefficients in data compression such that the number of bits required to represent the data is reduced. The nonlinear prediction data compression system includes a nonlinear predictor for generating predicted transform coefficients, a nonlinear prediction encoder that uses the predicted transform coefficients to encode original data, and a nonlinear prediction decoder that uses the predicted transform coefficients to decode the encoded bitstream and reconstruct the original data. The nonlinear predictor may be trained using training techniques, including a novel in-loop training technique of the present invention. The present invention also includes a method for using a nonlinear predictor to encode and decode data. The method also includes improving the performance of the nonlinear prediction data compression and decompression using several novel speedup techniques.

Claims

1. A computer-implemented method for encoding data, comprising:

transforming the data to obtain original transform coefficients;

generating predicted transform coefficients using a nonlinear predictor; and

encoding residuals using the original transform coefficients and the predicted transform coefficients.

2. The method as set forth in claim 1, wherein the nonlinear predictor is a trainable nonlinear predictor.

3. The method as set forth in claim 1, wherein the original transform coefficients are original wavelets coefficients and the predicted transform coefficients are predicted wavelet coefficients.

4. The method as set forth in claim 1, wherein the data is image data.

5. The method as set forth in claim 1, further comprising quantizing the residuals to obtain quantized residuals and encoding the quantized residuals.

6. The method as set forth in claim 1, further comprising storing reconstructed transform coefficients, wherein the stored reconstructed transform coefficients are used by the nonlinear predictor to generate future predicted transform coefficients.

7. The method as set forth in claim 6, wherein the reconstructed transform coefficients are obtained by associating the predicted transform coefficients with unquantized residuals.

8. The method as set forth in claim 7, wherein the unquantized residuals are obtained by quantizing the residuals to produce quantized residuals and then unquantizing the quantized residuals.

9. The method as set forth in claim 1, wherein the residuals are obtained by subtracting the predicted transform coefficients from the original transform coefficients.

10. The method as set forth in claim 2, wherein the trainable nonlinear predictor is a neural network.

11. The method as set forth in claim 2, further comprising training the trainable nonlinear predictor using offline training.

12. The method as set forth in claim 2, further comprising training the trainable nonlinear predictor using online training.

13. The method as set forth in claim 12, wherein the online training comprises using reconstructed transform coefficients obtained from the predicted transform coefficients as training data, and wherein training occurs on compressed images.

14. The method as set forth in claim 2, further comprising training the trainable nonlinear predictor using in-loop training.

15. The method as set forth in claim 14, wherein in-loop training comprises:

providing a fixed set of training data to the trainable nonlinear predictor; and

dynamically augmenting the fixed set of training data with reconstructed transform coefficients obtained from the predicted transform coefficients.

16. The method as set forth in claim 1, further comprising:

determining whether the original transform coefficients would quantize to approximately zero.

17. The method as set forth in claim 16, further comprising skipping the generation of predicted transform coefficients by the nonlinear predictor if all of the reconstructed transform coefficients used as inputs to the nonlinear predictor would quantize to zero.

18. The method as set forth in claim 1, further comprising:

selecting an original transform coefficient to be predicted from the original transform coefficients; and

determining whether neighboring reconstructed transform coefficients in the causal context around the original transform coefficient to be predicted would quantize to zero.

19. The method as set forth in claim 18, further comprising omitting the generation of predicted transform coefficients by the nonlinear predictor if all of the neighboring reconstructed transform coefficients would quantize to zero.

20. The method as set forth in claim 18, further comprising omitting the generation of predicted transform coefficients by the nonlinear predictor if a specifically chosen subset of the neighboring reconstructed transform coefficients would quantize to zero.

21. A computer-readable medium having computer-executable instructions for encoding data, comprising:

transforming the data to obtain original transform coefficients;

generating predicted transform coefficients using a nonlinear predictor; and

encoding residuals using the original transform coefficients and the predicted transform coefficients.

22. A computer-implemented method for decoding data, comprising:

receiving residuals of the data;

generating predicted transform coefficients using a nonlinear predictor;

generating reconstructed transform coefficients using the predicted transform coefficients and the residuals; and

using the reconstructed transform coefficients to reconstruct the data.

23. The method as set forth in claim 22, wherein the reconstructed transform coefficients are used by the nonlinear predictor to generate future predicted transform coefficients.

24. The method as set forth in claim 22, wherein the nonlinear predictor may be trained.

25. The method as set forth in claim 24, further comprising training the nonlinear predictor using at least one of:

(a) offline training;

(b) online training;

(c) in-loop training.

26. A computer-readable medium having computer-executable instructions for decoding data, comprising:

receiving residuals of the data;

generating predicted transform coefficients using a nonlinear predictor;

generating reconstructed transform coefficients using the predicted transform coefficients and the residuals; and

using the reconstructed transform coefficients to reconstruct the data.

27. A nonlinear prediction encoder for encoding data, comprising:

a transformation module that performs a transformation on the data to produce original transform coefficients;

a nonlinear predictor that produces predicted transform coefficients;

a prediction module that generates residuals from the original transform coefficients and the predicted transform coefficients; and

an entropy coder that encodes the residuals to produce an encoded representation of the data.

28. The nonlinear prediction encoder as set forth in claim 27, wherein the nonlinear predictor is a neural network.

29. The nonlinear prediction encoder as set forth in claim 27, wherein the prediction module further comprises an inverse quantizer that receives quantized residuals and outputs unquantized residuals.

30. The nonlinear prediction encoder as set forth in claim 27, wherein the prediction module further comprises a store containing reconstructed transform coefficients that are used by the nonlinear predictor.

31. The nonlinear prediction encoder as set forth in claim 30, wherein the reconstructed transform coefficients are obtained by associating the predicted transform coefficients and the unquantized residuals.

32. A nonlinear prediction decoder for decoding data, comprising:

an entropy decoder that decodes an encoded bitstream to produce quantized residuals;

an inverse quantizer that unquantizes the quantized residuals to produce unquantized residuals;

a nonlinear predictor that generates predicted transform coefficients; and

an inverse prediction module that uses the predicted transform coefficients and the unquantized residuals to obtain reconstructed transform coefficients that are used to reconstruct the data.

33. A nonlinear prediction data compression system, comprising:

a nonlinear predictor for generating predicted transform coefficients;

a nonlinear prediction encoder that uses the predicted transform coefficients to encode original data to produce an encoded bitstream; and

a nonlinear prediction decoder that uses the predicted transform coefficients to decode the encoded bitstream and reconstruct the original data.

34. A nonlinear prediction encoder for encoding image data, comprising:

a transformation module that generates original transform coefficients from the image data;

a nonlinear predictor that generates nonlinear predictions of the original transform coefficients and produces residuals using the nonlinear predictions and the original transform coefficients; and

an entropy coder that encodes the residuals;

wherein the nonlinear predictions reduce the entropy of the residuals that the entropy coder must encode.