Hierarchical update scheme for extremum location

• US 7,707,213 B2
• Filed: 02/21/2007
• Issued: 04/27/2010
• Est. Priority Date: 02/21/2007
• 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): Vo; Tim T.
• Assistant Examiner(s): Fan; Shiow-Jy
• Application Number:
  US11/677,511
• Publication Number:
  US 20080201352A1
• Time in Patent Office: 1,161 Days
• Field of Search: 707100-101, 707/102, 707/E17.005, 707/791, 375/E7.203
• US Class Current: 707/737
• CPC Class Codes: H04N 19/97 Matching pursuit coding

Abstract

A system and method for determining an extreme value of data in various applications including audio, video and image encoding schemes. The system and method are used to build a hierarchical data structure by partitioning the data values and then constructing a hierarchy using these data values, with the apex containing the extreme value. The system and method allow for changes in the data values in the base level of the hierarchy to ripple through to the apex in an efficient manner.

Claims

1. A method for generating data comprising:

partitioning, by a processing device, data values of a base level into first partitions wherein the data values are stored in memory;

generating, by the processing device, a first level including second partitions, each of the second partitions including a respective extreme data value from each of the first partitions;

generating, by the processing device, an apex including at least one extreme data value from the second partitions of the first level that also corresponds to an extremum of the base level; and

updating, by the processing device, the first level if at least one partition of the first partitions receives a new extreme data value,

wherein the new extreme data value is stored in the apex if the new extreme data value comprises a new extremum of the base level.

2. The method of claim 1, further comprising:

generating, by the processing device, a second level, the second level including third partitions, each of the third partitions including extreme data values of the second partitions.

3. The method of claim 1, wherein the first partitions and the second partitions include different numbers of data values.

4. The method of claim 1, further comprising generating attribute data comprising:

generating, by the processing device, an attribute base level including attributes of data values of the base level;

generating, by the processing device, an attribute first level including attributes of data values of the first level; and

generating, by the processing device, an attribute apex including at least an attribute of an extremum of the base level.

5. The method of claim 4, wherein attributes of data values comprise positions of data values in the base level.

6. The method of claim 4, wherein attributes of data values comprise one of dictionary entries of Atoms, quantized amplitudes of Atoms, sign values, or colors.

7. The method of claim 1, wherein data values of the base level comprise two-dimensional data.

8. The method of claim 7, wherein data values of the base level are representative of image data or video data.

9. The method of claim 1, wherein data values of the base level comprise one-dimensional data.

10. The method of claim 9, wherein data values of the base level are representative of audio data.

11. The method of claim 1, wherein the data comprises a hierarchy of arrays or a tree.

12. The method of claim 1, wherein each of the first partitions include different numbers of data values.

13. The method of claim 1, further comprising:

storing, by the processing device, extreme data values of the first partitions in memory.

14. The method of claim 1, wherein data values of the base level comprise absolute values of inner products determined in a matching pursuits process.

15. The method of claim 1, wherein data values of the base level are representative of a Displaced Frame Difference (DFD) image.

16. A method for generating data, comprising:

partitioning, by a computing device, a base level data set into one or more partitions in memory;

generating, by the computing device, a coarse representation of extrema of each of the one or more partitions of the base level data by finding and storing the extrema of the partitions in memory; and

updating, by the computing device, the coarse representation if one or more data values of the base level data are altered, wherein the updating the coarse representation comprises finding and storing new extrema in memory from one of the one or more partitions of the base level data that includes altered data values.

17. The method of claim 16, further comprising:

generating, by the computing device, a hierarchy of successively coarser representations of extrema, each successive level in the hierarchy formed by finding and storing in memory extrema of a previous level'"'"'s partitions;

updating, by the computing device, the hierarchy from the base level to a highest level for partitions of the base level data containing altered data values; and

identifying, by the computing device, extrema of the base level data by processing data held in the highest level of the hierarchy.

18. The method of claim 17, wherein the hierarchy of successively coarser representations comprises a hierarchy of arrays or a tree.

19. The method of claim 17, wherein the hierarchy of successively coarser representations comprises a hierarchy of levels, wherein each level above the base level includes extrema of a next lower level, the method further comprising:

partitioning, by the computing device, data values of each level, wherein partitions comprise different numbers of values within levels of the hierarchy and between different levels of the hierarchy.

20. The method of claim 17, wherein the partitions include two or more data values.

21. The method of claim 16, further comprising:

generating, by the computing device, a coarse representation of attributes of extrema of partitions of the base level data by finding and storing in memory the attributes of the extrema of the partitions; and

updating, by the computing device, the coarse representation of attributes in response to altering one or more data values of the base level data, wherein updating the coarse representation of attributes comprises finding and storing in memory attributes of new extrema only for corresponding partitions of the base level data that include altered data values.

22. The method of claim 16, wherein the base level data set is representative of at least one of image data, video data, and signal data.

23. The method of claim 22, wherein the signal data comprises audio data.

24. The method of claim 16, wherein the base level data set comprises one-dimensional data.

25. The method of claim 16, wherein the base level data set comprises two-dimensional or more than two-dimensional data.

26. The method of claim 16, wherein the base level data set comprises absolute values of inner products determined by a matching pursuits process.

27. The method of claim 16, wherein the base level data set is representative of a Displaced Frame Difference (DFD) image.

28. A method of encoding, comprising:

partitioning, by a computer-based device, a set of data values into a plurality of first partitions wherein the set of data values are stored in memory;

storing, by the computer-based device, a set of first extrema corresponding to extreme data values of the first partitions;

altering, by the computer-based device, one or more data values to produce one or more altered first partitions; and

updating, by the computer-based device, extreme data values of the set of first extrema corresponding to the one or more altered first partitions.

29. The method of claim 28, wherein storing the set of first extrema comprises:

storing, by the computer-based device, the extreme data values of the first partitions in memory.

30. The method of claim 29, wherein updating extreme data values comprises:

replacing, by the computer-based device, one or more of the extreme data values of the first partitions in memory.

31. The method of claim 28, further comprising:

partitioning, by the computer-based device, the set of first extrema into a plurality of second partitions; and

storing, by the computer-based device, a set of second extrema corresponding to extreme data values of the second partitions.

32. The method of claim 31, wherein altering one or more data values produces one or more altered second partitions, the method further comprising:

updating, by the computer-based device, extrema values of the set of second extrema corresponding to the one or more altered second partitions.

33. The method of claim 28, wherein updating extreme data values of the set of first extrema comprises comparing data values of the one or more altered first partitions.

34. The method of claim 28, wherein updating extreme data values of the set of first extrema comprises replacing one or more extreme data values of the set of first extrema with one or more new extrema of the one or more altered first partitions.

35. The method of claim 28, further comprising:

storing, by the computer-based device, a set of attributes corresponding to the set of first extrema;

altering, by the computer-based device, one or more data values to produce one or more altered first partitions; and

updating, by the computer-based device, the set of attributes in response to new extrema associated with the one or more altered first partitions.

36. The method of claim 28, wherein the set of data values is representative of at least one of image data, video data, and audio data.

37. The method of claim 28, wherein the set of data values comprises one-dimensional data, two-dimensional data, or more than two-dimensional data.

38. The method of claim 28, wherein the set of data values is representative of a Displaced Frame Difference (DFD) image.

39. An apparatus, comprising:

an encoder, including a digital device, configured to use a hierarchical data structure to identify an extremum of a data set, wherein the hierarchical data structure comprises;

a base level including data values of the data set partitioned into first partitions;

a first level including second partitions, corresponding ones of the second partitions including respective extreme data values of the first partitions;

an apex including an extreme data value of the first level corresponding to an extremum of the base level; and

wherein the encoder is further configured to update the hierarchical data structure in response to a new extremum being saved in the base level.

40. The apparatus of claim 39, wherein the encoder is further configured to update the hierarchical data structure in response to a new extremum of the data set by, at least in part, storing the new extreme data value in the first level.

41. The apparatus of claim 39, wherein the encoder is further configured to update the hierarchical data structure in response to a new extremum of the data set by storing the new extreme data value in the apex if the new extreme data value comprises a new extremum of the base level.

42. The apparatus of claim 39, wherein the first level is partitioned into second partitions, and the first partitions and the second partitions include different numbers of data values.

43. The apparatus of claim 39, wherein the encoder is further configured to use an attribute data structure comprising:

an attribute base level including attributes of data values of the base level of the hierarchical data structure;

an attribute first level including attributes of data values of the first level of the hierarchical data structure; and

an attribute apex including at least an attribute of an extremum of the base level of the hierarchical data structure.

44. The apparatus of claim 41, wherein attributes of data values comprise positions of data values in the base level of the hierarchical data structure.

45. The apparatus of claim 43, wherein attributes of data values comprise one of dictionary entries of Atoms, quantized amplitudes of Atoms, sign values, or colors.

46. The apparatus of claim 39, wherein data values of the base level are representative of one of image data, video data, or audio data.

47. The apparatus of claim 39, wherein data values of the base level comprise one of one-dimensional data, two-dimensional data, three-dimensional data, or greater-than-three-dimensional data.

48. The apparatus of claim 39, wherein the first partitions include different numbers of data values.

49. The apparatus of claim 39, further comprising:

memory, wherein the encoder is further configured to store extreme data values of the first partitions in the memory.

50. The apparatus of claim 39, wherein data values of the base level comprise absolute values of inner products determined in a matching pursuits process.

51. The apparatus of claim 39, wherein the hierarchical data structure comprises a hierarchy of arrays or a tree.

52. The apparatus of claim 39, wherein data values of the base level are representative of a Displaced Frame Difference (DFD) image.

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

partitioning data values of a base level into first partitions;

generating a first level including second partitions, each of the second partitions including a respective extreme data value of corresponding ones of the first partitions;

generating an apex including an extreme data value of the first level corresponding to an extremum of the base level; and

modifying the first level in response to at least one of the first partitions receiving a new extreme data value, wherein the new extreme data value is stored in the apex if the new extreme data value comprises a new extremum of the base level.

54. The tangible computer-readable medium of claim 53, containing further computer-executable instructions that, if executed by the machine, cause the machine to perform a method comprising:

generating a second level of the data including third partitions, each of the third partitions including respective extreme data values of a corresponding one of the second partitions.

55. The tangible computer-readable medium of claim 53, containing further computer-executable instructions that, if executed by the machine, cause the machine to perform a method comprising generating attribute data comprising:

generating an attribute base level including attributes of data values of the base level;

generating an attribute first level including attributes of data values of the first level; and

generating an attribute apex including at least an attribute of an extremum of the base level.

56. The tangible computer-readable medium of claim 55, wherein attributes of data values comprise positions of data values in the base level of the data structure.

57. The tangible computer-readable medium of claim 55, wherein attributes of data values comprise one of dictionary entries of Atoms, quantized amplitudes of Atoms, sign values, or colors.

58. The tangible computer-readable medium of claim 53, containing further computer-executable instructions that, if executed by the machine, cause the machine to perform a method comprising:

storing extreme data values of the first partitions in memory.

59. The tangible computer-readable medium of claim 53, wherein data values of the base level comprise absolute values of inner products determined in a matching pursuits process.