Hierarchical update scheme for extremum location with indirect addressing

• US 7,707,214 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,515
• Publication Number:
  US 20080201346A1
• Time in Patent Office: 1,161 Days
• Field of Search: 707100-101, 707/102, 707/E17.005, 707/791, 707/E17.002, 375/E7.203
• US Class Current: 707/737
• CPC Class Codes: G06F 7/544 for evaluating functions by calculation G06F7/4824 takes precedence
• 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 generate a hierarchical data structure by partitioning the data values and then generating a hierarchy using indices of these data values, with the apex containing the index of the extreme value. The system and method allow for changes in the data values in the base level of the hierarchy to result in the ripple through of the indices to the apex in an efficient manner.

Claims

1. A method for generating data comprising:

partitioning, by a processing device, a base level of data values 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 an index indicating a position of an extreme data value from each of the first partitions;

generating, by the processing device, an apex including at least one extreme index from the second partitions of the first level that also corresponds to an extreme data value 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 index is stored in the apex if altering at least one data value results in a new extreme data value 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 respective one of the third partitions including extreme indices of corresponding ones of the second partitions.

3. The method of claim 1, wherein the indices are associated with attributes of the data values of the base level.

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

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

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

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

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

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

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

11. The method of claim 1, further comprising:

storing, by the processing device, indices of the second partitions in memory.

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

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

14. The method of claim 1, wherein the data values of the base level comprise one of three-dimensional data or greater-than-three-dimensional data.

15. A method, comprising:

partitioning, by a computing device, a set of data values 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 set of data values and storing indices indicative of locations of extrema in the partitions in memory; and

updating, by the computing device, the coarse representation in response to altering one or more data values of the set of data values,

wherein the updating comprises storing in memory indices indicative of locations of any new extrema in partitions from the one or more partitions of the set of data values that include altered data values.

16. The method of claim 15, further comprising:

generating, by the computing device, a hierarchy of successively coarser representations of extrema;

storing in memory indices indicative of locations of extrema of a previous level'"'"'s partitions;

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

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

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

18. The method of claim 16, wherein the hierarchy of successively coarser representations comprises a hierarchy of levels, wherein each level above the base level includes indices indicative of locations of extrema of a next lower level, the method further comprising:

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

19. The method of claim 15, wherein the partitions include two or more data values.

20. The method of claim 15, wherein the set of data values comprise data values representative of at least one of image data, video data, and signal data.

21. The method of claim 20, wherein the signal data comprises audio data.

22. The method of claim 15, wherein the set of data values comprise one-dimensional data.

23. The method of claim 15, wherein the set of data values comprise two-dimensional or more than two-dimensional data.

24. The method of claim 15, wherein the set of data values comprise absolute values of inner products determined by a matching pursuits process.

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

26. The method of claim 15, wherein the set of data values comprises one of dictionary entries of Atoms, quantized amplitudes of Atoms, sign values, or color values.

27. A method, comprising:

partitioning, by a computer-based device, a set of data values into a plurality of first partitions;

storing, by the computer-based device, a set of first indices corresponding to positions of 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, indices of the set of first indices corresponding to the one or more altered first partitions.

28. The method of claim 27, wherein the storing comprises:

storing, by the computer-based device, the set of first indices in memory.

29. The method of claim 27, wherein the updating comprises:

storing, by the computer-based device, one or more of indices of the set of first indices in memory.

30. The method of claim 27, further comprising:

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

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

31. The method of claim 30, wherein the altering comprises:

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

32. The method of claim 27, wherein the updating comprises comparing data values of the one or more altered first partitions.

33. The method of claim 27, wherein the updating comprises replacing one or more indices of the set of first indices with one or more new indices corresponding to positions of extreme data values in the one or more altered first partitions.

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

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

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

37. The method of claim 27, wherein the set of data values comprises one of dictionary entries of Atoms, quantized amplitudes of Atoms, sign values, or color values.

38. 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 holds indices corresponding to extreme data values of the data set, and wherein the hierarchical data structure comprises;

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

a first level including indices pointing to extreme data values of the first partitions;

an apex including at least one index pointing to 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.

39. The apparatus of claim 38, wherein the encoder is further configured to update the hierarchical data structure in response to a new extremum of the data set by storing an index associated with the new extreme data value in the first level.

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

41. The apparatus of claim 38, wherein the encoder is further configured to:

partition the first level into second partitions; and

generate a second level of the hierarchical data structure, the second level including extreme indices of the second partitions.

42. The apparatus of claim 38, wherein the base level comprises data values representative of one of image data, video data, or audio data.

43. The apparatus of claim 38, wherein the base level comprises one of one-dimensional data, two-dimensional data, or three-dimensional data.

44. The apparatus of claim 38, wherein the first partitions include different numbers of the data values.

45. The apparatus of claim 38, wherein the indices are associated with attributes of the data values of the base level of the hierarchical data structure.

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

47. The apparatus of claim 45, wherein the attributes of data values comprise positions of data values in the base level.

48. The apparatus of claim 38, further comprising:

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

49. The apparatus of claim 38, wherein the base level comprises absolute values of inner products determined in a matching pursuits process.

50. The apparatus of claim 38, wherein the hierarchical data structure further comprises a hierarchy of arrays or a tree.

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

52. 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 a base level of data values into first partitions;

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

generating an apex including an extreme index of the first level corresponding to an extreme data value 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 index is stored in the apex if the new extreme data value results in a new extreme data value of the base level.

53. The tangible computer-readable medium of claim 52, 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 indices of a corresponding one of the second partitions.

54. The tangible computer-readable medium of claim 52, wherein the indices are associated with attributes of the data values of the base level.

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

56. The tangible computer-readable medium of claim 54, 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 52, wherein the base level comprises data values representative of one of image data, video data, or audio data.

58. The tangible computer-readable medium of claim 52, wherein the data structure comprises a hierarchy of arrays or a tree.

59. The tangible computer-readable medium of claim 52, wherein the first partitions include different numbers of data values.

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

storing indices of the second partitions in memory.

61. The tangible computer-readable medium of claim 52, wherein the base level comprises absolute values of inner products determined in a matching pursuits process.