Matching pursuits coding of data

• US 7,689,049 B2
• Filed: 08/31/2006
• Issued: 03/30/2010
• Est. Priority Date: 08/31/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): Couso; Jose L
• Application Number:
  US11/469,198
• Publication Number:
  US 20080056346A1
• Time in Patent Office: 1,307 Days
• Field of Search: 382232-233, 382238-240, 382244-251, 375/240.11, 37524018-24021, 348/395.1, 348/398.1, 341/50
• US Class Current: 382/232
• CPC Class Codes: H04N 19/97 Matching pursuit coding

Abstract

Briefly, in accordance with one embodiment, an approach to employing Matching Pursuits coding of data is described.

Claims

1. A method, comprising:

receiving, using a computer, multidimensional data; and

coding the multidimensional data, using a codebook of basis functions and the computer, wherein the codebook is applied as a mask to a basis function dictionary, and the basis function dictionary comprises separable combinations of one-dimensional basis function dictionaries.

2. The method of claim 1, further comprising:

sending the one-dimensional basis function dictionaries to a decoder.

3. The method of claim 1, further comprising:

determining a sampled value from a subset of the basis function dictionary; and

transmitting the sampled value to a decoder.

4. The method of claim 1, further comprising:

determining a parameter of the basis function dictionary; and

transmitting the parameter to a decoder.

5. The method of claim 1, further comprising:

generating the mask from the codebook; and

transmitting the mask to a decoder.

6. The method of claim 1, further comprising:

using two-dimensional data as the multidimensional data; and

using a two-dimensional basis function dictionary as the basis function dictionary.

7. The method of claim 6, wherein the using two dimensional data comprises using a digital image as the two-dimensional data.

8. The method of claim 1, further comprising:

using three-dimensional data as the multidimensional data; and

using a three-dimensional basis function dictionary as the basis function dictionary.

9. The method of claim 8, wherein the using the three-dimensional basis function dictionary comprises using a basis function dictionary having two spatial dimensions and one temporal dimension as the three-dimensional basis function dictionary.

10. The method of claim 8, wherein the using the three-dimensional basis function dictionary comprises using a basis function dictionary having three spatial dimensions as the three-dimensional basis function dictionary.

11. The method of claim 1, wherein the coding the multidimensional data using the codebook comprises using a basis function dictionary having more than three spatial dimensions as the basis function dictionary.

12. The method of claim 11, wherein the coding the multidimensional data using the codebook further comprises using a basis function dictionary having a temporal dimension as the basis function dictionary.

13. The method of claim 1, further comprising:

using data having more dimensions than a quantity of dimensions of the codebook as the multidimensional data; and

performing a matching pursuits process on portions of the multidimensional data having dimensions that are substantially equal to or lower in number than a respective codebook dimension.

14. The method of claim 1, further comprising:

applying a transform to the multidimensional data; and

performing a matching pursuits process on the multidimensional data.

15. The method of claim 14, wherein the applying comprises using a wavelet transform as the transform.

16. The method of claim 14, wherein the applying comprises using a discrete cosine transform as the transform.

17. The method of claim 1, further comprising:

storing the multidimensional data.

18. The method of claim 1, wherein the receiving further comprises receiving the multidimensional data from a storage.

19. A method, comprising:

receiving, using a computer, multidimensional data; and

decoding the multidimensional data, using a codebook of basis functions and the computer, wherein the codebook is applied as a mask to a basis function dictionary, and wherein the basis function dictionary comprises separable combinations of one-dimensional basis function dictionaries.

20. The method of claim 19, further comprising:

receiving the one-dimensional basis function dictionaries from a coder.

21. The method of claim 19, further comprising:

receiving a sampled value of a subset of the basis function dictionary from a coder.

22. The method of claim 19, further comprising:

receiving a parameter of the basis function dictionary from a coder.

23. The method of claim 19, further comprising:

receiving the mask generated from the codebook from a coder.

24. The method of claim 19, further comprising:

using two-dimensional data as the multidimensional data; and

using a two-dimensional basis function dictionary as the basis function dictionary.

25. The method of claim 24, wherein the using the two-dimensional data comprises using a digital image as the two-dimensional data.

26. The method of claim 19, further comprising:

using three-dimensional data as the multidimensional data; and

using a three-dimensional basis function dictionary as the basis function dictionary.

27. The method a claim 26, wherein the using the three-dimensional basis function dictionary comprises using a basis function dictionary having two spatial dimensions and one temporal dimension as the three-dimensional basis function dictionary.

28. The method of claim 26, wherein the using the three-dimensional basis function dictionary comprises using a basis function dictionary having three spatial dimensions as the three-dimensional basis function dictionary.

29. The method of claim 19, wherein the decoding comprises using a basis function dictionary having more than three spatial dimensions as the basis function dictionary.

30. The method of claim 29, wherein the decoding further comprises using a basis function dictionary having a temporal dimension as the basis function dictionary.

31. The method of claim 19, further comprising:

using data having more dimensions than a quantity of dimensions of the codebook as the multidimensional data; and

performing a matching pursuits process on portions of the multidimensional data having dimensions that are substantially equal to or lower in number than a respective codebook dimension.

32. The method of claim 19, further comprising:

applying a transform to the multidimensional data; and

performing a matching pursuits process on the multidimensional data.

33. The method of claim 32, wherein the applying comprises using a wavelet transform as the transform.

34. The method of claim 32, wherein the applying comprises using a discrete cosine transform as the transform.

35. The method of claim 19, further comprising:

storing the multidimensional data.

36. The method of claim 19, wherein the receiving further comprises receiving the multidimensional data from storage.

37. A tangible computer-readable medium having stored thereon computer-executable instructions that, if executed by a computer, causes the computer to perform a method comprising:

receiving multidimensional data; and

coding the multidimensional data using a codebook of basis functions, wherein the codebook is applied as a mask to a basis function dictionary, and wherein the basis function dictionary comprises separable combinations of one-dimensional basis function dictionaries.

38. The computer-readable medium of claim 37, wherein the instructions further cause the computer to:

send the one-dimensional basis function dictionaries to a decoder.

39. The computer-readable medium of claim 37, wherein the instructions further cause the computer to:

determine a sampled value from a subset of the basis function dictionary; and

transmit the sampled value to a decoder.

40. The computer-readable medium of claim 37, wherein the instructions further cause the computer to:

determine a parameter of the basis function dictionary; and

transmit the parameter to a decoder.

41. The computer-readable medium of claim 37, wherein the instructions further cause the computer to:

generate the mask from the codebook; and

transmit the mask to a decoder.

42. The computer-readable medium of claim 37, wherein the instructions further cause the computer to:

use two-dimensional data as the multidimensional data; and

use a two-dimensional basis function dictionary as the basis function dictionary.

43. The computer-readable medium of claim 42, wherein the using the two-dimensional data comprises using a digital image as the two-dimensional data.

44. The computer-readable medium of claim 37, wherein the instructions further cause the computer to:

use three-dimensional data as the multidimensional data; and

use a three-dimensional basis function dictionary as the basis function dictionary.

45. The computer-readable medium of claim 44, wherein the using the three-dimensional basis function dictionary comprises using a basis function dictionary having two spatial dimensions and one temporal dimension as the three-dimensional basis function dictionary.

46. The computer-readable medium of claim 44, wherein the using the three-dimensional basis function dictionary comprises using a basis function dictionary having three spatial dimensions as the three-dimensional basis function dictionary.

47. The computer-readable medium of claim 37, wherein the coding comprises using a basis function dictionary having more than three spatial dimensions as the basis function dictionary.

48. The computer-readable medium of claim 37, wherein the coding further comprises using a basis function dictionary having a temporal dimension as the basis function dictionary.

49. The computer-readable medium of claim 37, wherein the instructions further cause the computer to:

use data having more dimensions than a quantity of dimensions of the codebook as the multidimensional data; and

perform a matching pursuits process on portions of the multidimensional data having dimensions that are substantially equal to or lower in number than a respective codebook dimension.

50. The computer-readable medium of claim 37, wherein the instructions further cause the computer to:

apply a transform to the multidimensional data; and

perform a matching pursuits process on the multidimensional data.

51. The computer-readable medium of claim 50, wherein the applying the transform comprises using a wavelet transform as the transform.

52. The computer-readable medium of claim 50, wherein the applying the transform comprises using a discrete cosine transform as the transform.

53. The computer-readable medium of claim 37, wherein the instructions further cause the computer to:

store the multidimensional data.

54. The computer-readable medium of claim 37, wherein the receiving further comprises receiving the multidimensional data from a storage.

55. A tangible computer-readable medium having stored thereon instructions that, if executed by a computer, cause the computer to perform a method comprising:

receiving multidimensional data; and

decoding the multidimensional data using a codebook of basis functions, wherein the codebook is applied as a mask to a basis function dictionary, and wherein the basis function dictionary comprises separable combinations of one-dimensional basis function dictionaries.

56. The computer-readable medium of claim 55, wherein the instructions further cause the computer to:

receive the one-dimensional basis function dictionaries from a coder.

57. The computer-readable medium of claim 55, wherein the instructions further cause the computer to:

receive a sampled value of a subset of the basis function dictionary from a coder.

58. The computer-readable medium of claim 55, wherein the instructions further cause the computer to:

receive a parameter of the basis function dictionary from a coder.

59. The computer-readable medium of claim 55, wherein the instructions further cause the computer to:

receive the mask generated from the codebook from a coder.

60. The computer-readable medium of claim 55, wherein the instructions further cause the computer to:

use two-dimensional data as the multidimensional data; and

use a two-dimensional basis function dictionary as the basis function dictionary.

61. The computer-readable medium of claim 60, wherein the using the two-dimensional data comprises using a digital image as the two-dimensional data.

62. The computer-readable medium of claim 55, wherein the instructions further cause the computer to:

use three-dimensional data as the multidimensional data; and

use a three-dimensional basis function dictionary as the basis function dictionary.

63. The computer-readable medium of claim 62, wherein the using the three-dimensional basis function dictionary comprises using a basis function dictionary having two spatial dimensions and one temporal dimension as the three-dimensional basis function dictionary.

64. The computer-readable medium of claim 62, wherein the using the three-dimensional basis function dictionary comprises using a basis function dictionary having three spatial dimensions as the three-dimensional basis function dictionary.

65. The computer-readable medium of claim 55, wherein the decoding comprises using a basis function dictionary having more than three spatial dimensions as the basis function dictionary.

66. The computer-readable medium of claim 65, wherein the decoding further comprises using a basis function dictionary having a temporal dimension as the basis function dictionary.

67. The computer-readable medium of claim 55, wherein the instructions further cause the computer to:

use data having more dimensions than a quantity of dimensions of the codebook as the multidimensional data; and

perform a matching pursuits process on portions of the multidimensional data having dimensions that are substantially equal to or lower in number than a respective codebook dimension.

68. The computer-readable medium of claim 55, wherein the instructions further cause the computer to:

apply a transform to the multidimensional data; and

perform a matching pursuits process on the multidimensional data.

69. The computer-readable medium of claim 68, wherein the applying the transform comprises using a wavelet transform as the transform.

70. The computer-readable medium of claim 69, wherein the applying the transform comprises using a discrete cosine transform as the transform.

71. The computer-readable medium of claim 57, wherein the instructions further cause the computer to:

store the multidimensional data.

72. The computer-readable medium of claim 57, wherein the receiving further includes receiving the multidimensional data from storage.

73. An apparatus, comprising:

a computer configured to;

receive multidimensional data; and

code the multidimensional data using a codebook of basis functions, wherein the codebook is applied as a mask to a basis function dictionary, and wherein the basis function dictionary comprises separable combinations of one-dimensional basis function dictionaries.

74. The apparatus of claim 73, wherein the computer is further configured to send the one-dimensional basis function dictionaries to a decoder.

75. The apparatus of claim 73, wherein the computer is further configured to:

determine a sampled value from a subset of the basis function dictionary; and

transmit the sampled value to a decoder.

76. The apparatus of claim 73, wherein the computer is further configured to:

determine a parameter of the basis function dictionary; and

transmit the parameter to a decoder.

77. The apparatus of claim 73, wherein the computer is further configured to:

generate the mask from the codebook; and

transmit the mask to a decoder.

78. The apparatus of claim 73, wherein the computer is further configured to:

use two-dimensional data as the multidimensional data; and

use a two-dimensional basis function dictionary as the basis function dictionary.

79. The apparatus of claim 78, wherein the computer is further configured to use the two-dimensional data as the multidimensional data by using a digital image as the two-dimensional data.

80. The apparatus of claim 73, wherein the computer is further configured to:

use three-dimensional data as the multidimensional data; and

use a three-dimensional basis function dictionary as the basis function dictionary.

81. The apparatus of claim 78, wherein the computer is further configured to use the three-dimensional basis function dictionary as the basis function dictionary by using a basis function dictionary having two spatial dimensions and one temporal dimension as the three-dimensional basis function dictionary.

82. The apparatus of claim 78, wherein the computer is further configured to use the three-dimensional basis function dictionary as the basis function dictionary by using a basis function dictionary having three spatial dimensions as the three-dimensional basis function dictionary.

83. The apparatus of claim 73, wherein the computer is further configured to code the multidimensional data by using a basis function dictionary having more than three spatial dimensions as the basis function dictionary.

84. The apparatus of claim 73, wherein the computer is further configured to code the multidimensional data by using a basis function dictionary having a temporal dimension as the basis function dictionary.

85. The apparatus of claim 73, wherein the computer is further configured to:

use data having more dimensions than a quantity of dimensions of the codebook as the multidimensional data; and

perform a matching pursuits process on portions of the multidimensional data having dimensions that are substantially equal to or lower in number than a respective codebook dimension.

86. The apparatus of claim 73, wherein the computer is further configured to:

apply a transform to the multidimensional data; and

perform a matching pursuits process on the multidimensional data.

87. The apparatus of claim 86, wherein the computer is further configured to apply the transform to the multidimensional data by using a wavelet transform as the transform.

88. The apparatus of claim 86, wherein the computer is further configured to apply the transform to the multidimensional data by using a discrete cosine transform as the transform.

89. The apparatus of claim 73, wherein the computer is further configured to:

store the multidimensional data.

90. The apparatus of claim 73, further comprising a storage device to store the multidimensional data coupled to the computer.

91. An apparatus, comprising:

a computer configured to;

receive multidimensional data; and

decode the multidimensional data using a codebook of basis functions, wherein the codebook is applied as a mask to a basis function dictionary, and wherein the basis function dictionary comprises separable combinations of one-dimensional basis function dictionaries.

92. The apparatus of claim 91, wherein the computer is further configured to:

receive the one-dimensional basis function dictionaries from a coder.

93. The apparatus of claim 91, wherein the computer is further configured to:

receive a sampled value of a subset of the basis function dictionary from a coder.

94. The apparatus of claim 91, wherein the computer is further configured to:

receive a parameter of the basis function dictionary from a coder.

95. The apparatus of claim 91, wherein the computer is further configured to:

receive the mask generated from the codebook from a coder.

96. The apparatus of claim 91, wherein the computer is further configured to:

use two-dimensional data as the multidimensional data; and

use a two-dimensional basis function dictionary as the basis function dictionary.

97. The apparatus of claim 96, wherein the computer is further configured to use two-dimensional data as the multidimensional data by using a digital image as the two-dimensional data.

98. The apparatus of claim 91, wherein the computer is further configured to:

use three-dimensional data as the multidimensional data; and

use a three-dimensional basis function dictionary as the basis function dictionary.

99. The apparatus of claim 98, wherein the computer is further configured to use the three-dimensional basis function dictionary by using a basis function dictionary having two spatial dimensions and one temporal dimension as the three-dimensional basis function dictionary.

100. The apparatus of claim 98, wherein the computer is further configured to use the three-dimensional basis function dictionary by using a basis function dictionary having three spatial dimensions as the three-dimensional basis function dictionary.

101. The apparatus of claim 91, wherein the computer is further configured to decode the multidimensional data by using a basis function dictionary having more than three spatial dimensions as the basis function dictionary.

102. The apparatus of claim 101, wherein the computer is further configured to decode the multidimensional data by using a basis function dictionary having a temporal dimension as the basis function dictionary.

103. The apparatus of claim 91, wherein the computer is further configured to:

use data having more dimensions than a quantity of dimensions of the codebook as the multidimensional data; and

perform a matching pursuits process on portions of the multidimensional data having dimensions that are substantially equal to or lower in number than a respective codebook dimension.

104. The apparatus of claim 91, wherein the computer is further configured to:

apply a transform to the multidimensional data; and

perform a matching pursuits process on the multidimensional data.

105. The apparatus of claim 104, wherein the computer is further configured to decode the multidimensional data by using a wavelet transform as the transform.

106. The apparatus of claim 104, wherein the computer is further configured to decode the multidimensional data by using a discrete cosine transform as the transform.

107. The apparatus of claim 91, wherein the computer is further configured to:

store the multidimensional data.

108. The apparatus of claim 91, further comprising a storage device to store the multidimensional data coupled to the computer.