Reduced dimension wavelet matching pursuits coding and decoding

• US 7,848,584 B2
• Filed: 09/08/2005
• Issued: 12/07/2010
• Est. Priority Date: 09/08/2005
• Status: Expired due to Fees

• Current Assignee: Rateze Remote Mgmt. L.L.C. (Intellectual Ventures LLC)
• Original Assignee: Pan Pacific Plasma LLC (Intellectual Ventures LLC)
• Inventors: Monro, Donald M.
• Primary Examiner(s): Ge; Yuzhen
• Application Number:
  US11/222,665
• Publication Number:
  US 20070053597A1
• Time in Patent Office: 1,916 Days
• Field of Search: None
• US Class Current: 382/240
• CPC Class Codes: H04N 19/129 Scanning of coding units, e.g. zig-zag scan of transform coefficients or flexible macroblock ordering [FMO]
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/619 the transform being operated outside the prediction loop
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/97 Matching pursuit coding

Abstract

Embodiments related to coding and/or decoding data, including for example image data, using wavelet transform and matching pursuits are disclosed. In some embodiments, a wavelet transform is applied to data to produce transformed data. The transformed data is scanned to produce reduced dimension data, and a matching pursuit is performed in the reduced dimension data.

Claims

1. A method performed by a computing system having a processor and memory, the method comprising:

applying by the computing system a wavelet transform to data to produce transformed data in a plurality of sub bands, wherein the transformed data includes data representing a still image and a displaced frame difference image generated by a motion compensation operation;

scanning at least two of the sub bands of the transformed data in a predetermined order to produce reduced dimension data, wherein the scanning includes scanning at least a first sub band in a first pattern and scanning at least a second sub band in a second pattern different from the first pattern, the first sub band and the second sub band not overlapping; and

performing a matching pursuit process on the reduced dimension data.

2. The method of claim 1, wherein applying a wavelet transform to the data includes applying a two-dimensional wavelet transform to the data.

3. The method of claim 2, wherein applying a two dimensional wavelet transform to the data includes using two or more levels of wavelet decomposition.

4. The method of claim 2, wherein the data comprises image data.

5. The method of claim 1, wherein the transformed data comprises two dimensional data and further where scanning the transformed data produces one dimensional data.

6. The method of claim 1, wherein the data comprises multidimensional data.

7. A method, performed by a computing system having a processor and memory, comprising:

decoding by the computing system a plurality of matching pursuit atom parameters;

generating a plurality of wavelet transform coefficients from the plurality of atom parameters;

generating first data based at least in part on a generated wavelet transform coefficient;

performing a reverse-scanning process on the generated first data to produce greater-dimensional data, wherein the reverse-scanning process comprises;

reverse-scanning, in a first pattern, a first portion of the first data corresponding to a first sub band, and

reverse-scanning, in a second pattern, a second portion of the first data corresponding to a second sub band, wherein the first portion and the second portion are not overlapping; and

performing an inverse wavelet transform on the greater-dimensional data, wherein performing the inverse wavelet transform comprises producing image data wherein the image data comprises data representing a still image and a displaced frame difference image data.

8. The method of claim 7, wherein the greater-dimensional data comprises two-dimensional data.

9. The method of claim 7, wherein performing an inverse wavelet transform includes applying a two-dimensional inverse wavelet transform.

10. An apparatus, comprising:

a component that, when executed, applies a wavelet transform to data to produce transformed data, wherein the transformed data includes data representing a still image and a displaced frame difference image generated by a motion compensation operation and further wherein the transformed data includes a plurality of non-overlapping sub bands;

a component that, when executed, scans the transformed data to produce reduced dimension data including scanning, in a horizontal pattern, a first portion of the transformed data corresponding to a first sub band and scanning, in a vertical pattern, a second portion of the transformed data corresponding to a second sub band; and

a component that, when executed, performs a matching pursuit algorithm on the reduced dimension data.

11. The apparatus of claim 10 further comprising a component that, when executed, applies a two-dimensional wavelet transform to the data.

12. The apparatus of claim 11 further comprising a component that, when executed, applies two levels of wavelet decomposition.

13. The apparatus of claim 11, wherein the data comprises image data.

14. The apparatus of claim 10 further comprising a component that, when executed, produces transformed data comprising two dimensional data and a component configured to scan the transformed data to produce one dimensional data.

15. The apparatus of claim 10, wherein the data comprises multidimensional data.

16. An apparatus, comprising:

a component that, when executed, decodes a plurality of matching pursuit atom parameters;

a component that, when executed, generates a plurality of wavelet transform coefficients from the plurality of atom parameters;

a component that, when executed, generates initial data based at least in part on a generated wavelet transform coefficient, the initial data comprising a plurality of non-overlapping sub band regions;

a component that, when executed, performs a reverse-scanning process on the generated initial data to produce greater-dimensional data at least in part by reverse-scanning a first sub band region according to a first pattern and reverse-scanning a second sub band region according to a second pattern different from the first pattern; and

a component that, when executed, performs an inverse wavelet transform on the greater-dimensional data, wherein the inverse wavelet transform produces image data wherein the image data comprises data representing a still image and a displaced frame difference image data.

17. The apparatus of claim 16, wherein the greater-dimensional data comprises two-dimensional data.

18. The apparatus of claim 16 further comprising a component that, when executed, performs an inverse wavelet transform including applying a two-dimensional inverse wavelet transform.

19. A non-transitory computer-readable storage medium having stored thereon computer-executable instructions, the instructions comprising:

instructions for applying a wavelet transform to data representing one or more images to produce transformed data;

instructions for scanning the transformed data to produce reduced dimension data including instructions for scanning a first portion of the transformed data in a first pattern and instructions for scanning a second portion of the transformed data in a second pattern, wherein the first portion and the second portion are non-overlapping and further wherein the first pattern is different from the second pattern; and

instructions for performing a matching pursuit algorithm on the reduced dimension data, wherein the transformed data includes data representing a still image and a displaced frame difference image generated by a motion compensation operation.

20. The non-transitory computer-readable storage medium of claim 19, wherein the instructions for applying a wavelet transform to the data include instructions for applying a two-dimensional wavelet transform to the data.

21. The non-transitory computer-readable storage medium of claim 20, wherein the instructions for applying a two dimensional wavelet transform to the data include instructions for using two levels of wavelet decomposition.

22. The non-transitory computer-readable storage medium of claim 20, wherein the data comprises image data.

23. The non-transitory computer-readable storage medium of claim 19, wherein the transformed data comprises two dimensional data and further wherein scanning the transformed data produces one dimensional data.

24. The non-transitory computer-readable storage medium of claim 19, wherein the data comprises a displaced frame difference image generated by a motion compensation operation.

25. A non-transitory computer-readable storage medium having stored thereon computer-executable instructions, the instructions comprising:

instructions for decoding a plurality of matching pursuit atom parameters;

instructions for generating a plurality of wavelet transform coefficients from the plurality of atom parameters;

instructions for generating reduced-dimension image data based on at least one of the generated wavelet transform coefficients;

instructions for performing a reverse-scanning process on the reduced-dimension image data to produce greater-dimensional data, the reverse-scanning process including;

reverse-scanning a first sub band region according to a first pattern, and

reverse-scanning a second sub band region according to a second pattern different from the first pattern,

wherein the first sub band region and the second sub band region do not overlap; and

instructions for performing an inverse wavelet transform on the greater-dimensional data, wherein performing the inverse wavelet transform comprises producing image data wherein the image data comprises data representing a still image and a displaced frame difference image data.

26. The non-transitory computer-readable storage medium of claim 25, wherein the greater-dimensional data comprises two-dimensional data.

27. The non-transitory computer-readable storage medium of claim 26, wherein the inverse wavelet transform produces image data.

28. The non-transitory computer-readable storage medium of claim 25, wherein the instructions for performing an inverse wavelet transform include instructions for applying a two-dimensional inverse wavelet transform.

29. An apparatus, comprising:

means for applying a wavelet transform to data to produce transformed data, wherein the transformed data includes data representing a still image and a displaced frame difference image generated by a motion compensation operation;

means for scanning a first portion of the transformed data in a horizontal pattern to produce first reduced dimension data;

means for scanning a second portion of the transformed data in a vertical pattern to produce second reduced dimension data, wherein the first portion and the second portion do not overlap;

means for scanning a third portion of the transformed data in a diagonal pattern to produce third reduced dimension data, wherein the first and third portions do not overlap, and wherein the second and third portions do not overlap; and

means for performing a matching pursuit process on the first, second, and third reduced dimension data.