Matching pursuits subband coding of data

• US 7,508,325 B2
• Filed: 09/06/2006
• Issued: 03/24/2009
• Est. Priority Date: 09/06/2006
• Status: Active Grant

• Current Assignee: Xylon LLC (Intellectual Ventures LLC)
• Original Assignee: Intellectual Ventures Holding 35 LLC (Intellectual Ventures LLC)
• Inventors: Monro, Donald Martin
• Primary Examiner(s): WILLIAMS, HOWARD L
• Application Number:
  US11/470,611
• Publication Number:
  US 20080055120A1
• Time in Patent Office: 930 Days
• Field of Search: 341/50, 375/240.11, 375/240.18, 375/240.19, 382/248, 382/253
• US Class Current: 341/50
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H04N 19/122 Selection of transform size, e.g. 8x8 or 2x4x8 DCT; Selection of sub-band transforms of varying structure or type
• CPC Class Codes: H04N 19/635 characterised by filter definition or implementation details
• CPC Class Codes: H04N 19/97 Matching pursuit coding

Abstract

A method, system, and computer program product are used for coding multi-dimensional data using a codebook of basis functions. A transform is applied to the multi-dimensional data to create transform coefficients. Groups of transform coefficients are formed. Different groups of transform coefficients are coded with non-identical dictionaries of basis functions from the codebook.

Claims

1. A method for coding multi-dimensional data using a codebook of basis functions, comprising:

(a) applying a transform to the multi-dimensional data to create transform coefficients, wherein the multi-dimensional data has a total number of dimensions greater than a total number of dimensions of the codebook of basis functions;

(b) forming groups of the transform coefficients; and

(c) coding different ones of the groups of the transform coefficients using matching pursuits coding with non-identical dictionaries of basis functions from the codebook of basis functions.

2. The method of claim 1, wherein step (c) comprises using subsets of a master basis dictionary in the non-identical dictionaries of basis functions.

3. The method of claim 2, wherein step (c) comprises using non-overlapping subsets of the master basis dictionary in the non-identical dictionaries of basis functions.

4. The method of claim 2, wherein step (c) comprises using overlapping subsets of the master basis dictionary in the non-identical dictionaries of basis functions.

5. The method of claim 2, wherein step (c) comprises using data indicative of the subsets of the master basis dictionary.

6. The method of claim 2, further comprising:

(d) communicating the subsets with a decoder.

7. The method of claim 2, further comprising:

(d) communicating the subsets in a form of a sampled value of a function with a decoder.

8. The method of claim 2, further comprising:

(d) communicating data indicative of the subsets with a decoder.

9. The method of claim 2, further comprising:

(d) using a mask applied to the master basis dictionary to identify the subsets.

10. The method of claim 1, wherein:

step (a) comprises using two-dimensional data for the multi-dimensional data; and

step (c) comprises using two-dimensional dictionaries as the non-identical dictionaries of basis functions.

11. The method of claim 10, wherein step (a) comprises using a digital image as the two-dimensional data.

12. The method of claim 1, wherein:

step (a) comprises using three-dimensional data as the multi-dimensional data; and

step (c) comprises using three-dimensional dictionaries as the non-identical dictionaries of basis functions.

13. The method of claim 12, wherein step (a) comprises using data having two spatial dimensions and one temporal dimension as the multi-dimensional data.

14. The method of claim 12, wherein step (a) comprises using three-dimensional data having three spatial dimensions.

15. The method of claim 1, wherein:

step (a) comprises using three-dimensional data as the multi-dimensional data; and

step (c) comprises using dictionaries having more than three dimensions as the non-identical dictionaries of basis functions.

16. The method of claim 15, wherein step (a) comprises using data having at least one temporal dimension as the multi-dimensional data.

17. The method of claim 1, further comprising:

wherein step (c) further comprises performing a matching pursuits process on the multi-dimensional data; and

(d) applying a transform to at least one dimension of the multi-dimensional data prior to step (c).

18. The method of claim 17, wherein step (a) comprises using a wavelet transform as the transform.

19. The method of claim 18, wherein step (c) comprises using transform coefficient groupings that comprise sub-bands of the wavelet transform.

20. The method of claim 18, wherein step (a) comprises using a multi-dimensional wavelet transform as the wavelet transform.

21. The method of claim 20, wherein step (a) comprises using a discrete cosine transform as the multi-dimensional wavelet transform.

22. The method of claim 20, wherein the non-identical dictionaries of basis functions in step (c) further comprise a transpose of basis functions applied to at least one other transform coefficient grouping.

23. The method of claim 1, further comprising:

(d) using audio data as the multi-dimensional data.

24. The method of claim 1, further comprising:

(d) using video data as the multi-dimensional data.

25. A method for decoding multi-dimensional data using a codebook of basis functions, comprising:

(a) decoding different groupings of transform coefficients with non-identical dictionaries of basis functions having more than three dimensions from the codebook to create decoded multi-dimensional data having more than three dimensions; and

(b) applying a transform to the decoded multi-dimensional data.

26. The method of claim 25, wherein step (a) comprises using subsets of a master basis dictionary in the non-identical dictionaries of basis functions.

27. The method of claim 26, further comprising:

(c) communicating the subsets of the master basis dictionary in a form of a sampled value of a function with a coder.

28. The method of claim 26, further comprising:

(c) communicating the subsets of the master basis dictionary with a coder.

29. The method of claim 26, further comprising:

(c) communicating data indicative of the subsets of the master basis dictionary with a coder.

30. The method of claim 26, further comprising:

(c) applying a mask to the master basis dictionary to identify the subsets of the master basis dictionary.

31. The method of claim 25, wherein step (a) comprises using two-dimensional data as the multi-dimensional data and two-dimensional dictionaries as the non-identical dictionaries of basis functions.

32. The method of claim 31, wherein step (a) comprises using two-dimensional data that comprises a digital image as the multi-dimensional data.

33. The method of claim 25, wherein step (a) comprises using three-dimensional data as the multi-dimensional data and three-dimensional dictionaries as the non-identical dictionaries of basis functions.

34. The method a claim 33, wherein step (a) comprises using data having two spatial dimensions and one temporal dimension as the multi-dimensional data.

35. The method of claim 25, wherein step (a) comprises using data having three spatial dimensions as the multi-dimensional data.

36. The method of claim 25, wherein step (a) comprises using data having at least one temporal dimension as the multi-dimensional data.

37. The method of claim 25, wherein step (a) comprises using data having a total number of dimensions that is higher than a total number of dimensions of the codebook as the multi-dimensional data;

and the decoding further comprises applying a matching pursuits process to the multi-dimensional data.

38. The method of claim 25, wherein step (b) comprises using an inverse wavelet transform as the transform.

39. The method of claim 38, wherein step (b) comprises using an inverse discrete cosine transform as the transform.

40. The method of claim 25, further comprising:

(c) using audio data as the multi-dimensional data.

41. The method of claim 25, further comprising:

(c) using video data as the multi-dimensional data.

42. A computer-readable medium containing instructions that, when executed by a processor, causes the processor to:

(a) apply a transform to multi-dimensional data to create transform coefficients, wherein the multi-dimensional data has a total number of dimensions higher than a total number of dimensions of a codebook of basis functions;

(b) form groups of transform coefficients; and

(c) code different ones of the groups of transform coefficients using matching pursuits coding with non-identical dictionaries of basis functions from the codebook of basis functions.

43. The computer-readable medium of claim 42, wherein the method further causes the processor to use subsets of a master basis dictionary in the non-identical dictionaries of basis functions.

44. The computer-readable medium of claim 43, wherein the method further causes the processor to use overlapping subsets of the master basis dictionary in the non-identical dictionaries of basis functions.

45. The computer-readable medium of claim 42, wherein the method further causes the processor to:

(d) communicate the subsets with a decoder.

46. The computer-readable medium of claim 42, wherein the method further causes the processor to:

(d) communicate the subsets in a form of a sampled value of a function with a decoder.

47. The computer-readable medium of claim 42, wherein the method further causes the processor to:

(d) communicate data indicative of the subsets with a decoder.

48. The computer-readable medium of claim 42, wherein the method further causes the processor to:

(d) use audio data as the multi-dimensional data.

49. The computer-readable medium of claim 42, wherein the method further causes the processor to:

(d) use video data as the multi-dimensional data.

50. A computer-readable medium containing instructions that, when executed by a processor, causes the processor to:

(a) decode different groupings of transform coefficients with non-identical dictionaries of basis functions having more than three dimensions from a codebook to create decoded multi-dimensional data having more than three dimensions; and

(b) apply a transform to the decoded multi-dimensional data.

51. The computer-readable medium of claim 50, wherein the method further causes the processor to use subsets of a master basis dictionary in the non-identical dictionaries of basis functions.

52. The computer-readable medium of claim 51, wherein the method further causes the processor to use overlapping subsets of the master basis dictionary in the non-identical dictionaries of basis functions.

53. The computer-readable medium of claim 50, wherein the method further causes the processor to:

(c) communicate the subsets of the master basis dictionary with a coder.

54. The computer-readable medium of claim 50, wherein the method further causes the processor to:

(c) communicate the subsets of the master basis dictionary in a form of a sampled value of a function with a coder.

55. The computer-readable medium of claim 50, wherein the method further causes the processor to:

(c) use audio data as the multi-dimensional data.

56. The computer-readable medium of claim 50, wherein the method further causes the processor to:

(c) use video data as the multi-dimensional data.

57. An apparatus, comprising:

a coder configured to encode multi-dimensional data using a codebook of basis functions, wherein the multi-dimensional data has a total number of dimensions higher than a total number of dimensions of the codebook of basis functions;

wherein said coder is configured to apply a transform to the multi-dimensional data to create transform coefficients, form groups of transform coefficients, and code different ones of the groups of transform coefficients using matching pursuits coding with non-identical dictionaries of basis functions from the codebook of basis functions.

58. The apparatus of claim 57, wherein the coder is further configured to code the different ones of the groups of transform coefficients using subsets of a master basis dictionary in the non-identical dictionaries of basis functions.

59. The apparatus of claim 58, wherein the coder is further configured to code the different ones of the groups of transform coefficients using overlapping subsets of the master basis dictionary in the non-identical dictionaries of basis functions.

60. The apparatus of claim 58, wherein the coder is further configured to communicate the subsets with a decoder.

61. The apparatus of claim 58, wherein the coder is further configured to communicate the subsets with a decoder in a form of a sampled value of a function.

62. The apparatus of claim 58, wherein the coder is further configured to communicate data indicative of the subsets with a decoder.

63. The apparatus of claim 57, wherein the multi-dimensional data comprises audio data.

64. The apparatus of claim 57, wherein the multi-dimensional data comprises video data.

65. An apparatus, comprising:

a decoder configured to decode multi-dimensional data using a codebook of basis functions;

wherein said decoder decodes different groupings of transform coefficients with non-identical dictionaries of basis functions having more than three dimensions from the codebook to create decoded multi-dimensional data having more than three dimensions and applies a transform to the decoded multi-dimensional data.

66. The apparatus of claim 65, wherein the decoder is further configured to decode the different ones of the groups of transform coefficients using subsets of a master basis dictionary in the non-identical dictionaries of basis functions.

67. The apparatus of claim 66, wherein the decoder is further configured to decode the different ones of the groups of transform coefficients using overlapping subsets of the master basis dictionary in the non-identical dictionaries of basis functions.

68. The apparatus of claim 66, wherein the decoder is further configured to communicate the subsets of the master basis dictionary with a coder.

69. The apparatus of claim 66, wherein the decoder is further configured to communicate the subsets of the master basis dictionary in a form of a sampled value of a function with a coder.

70. The apparatus of claim 65, wherein the multi-dimensional data comprises audio data.

71. The apparatus of claim 65, wherein the multi-dimensional data comprises video data.