HIERARCHICAL UPDATE SCHEME FOR EXTREMUM LOCATION WITH INDIRECT ADDRESSING

• US 20080201346A1
• Filed: 02/21/2007
• Published: 08/21/2008
• 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
• Granted Patent: US 7,707,214 B2
• Time in Patent Office: Days
• US Class Current: 707/101
• 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

Implementations related to hierarchical update schemes for extremum location with indirect addressing are disclosed.

Claims

1. A method for generating data comprising:

(a) partitioning a base level of data values into first partitions;

(b) generating a first level including indices indicating positions of extreme data values of the first partitions;

(c) generating an apex including at least one extreme index of the first level corresponding to an extreme data value of the base level; and

(d) modifying the first level in response to altering at least one data value of the base level, by storing a new index in the first level, 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:

partitioning the first level into second partitions; and

generating a second level, the second level including extreme indices 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 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.

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

56. 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.

13. A method, comprising:

(a) partitioning a set of data values;

(b) generating a coarse representation of extrema of partitions of the set of data values and storing indices indicative of locations of extrema in the partitions in memory; and

(c) updating the coarse representation in response to altering one or more data values of the set of data values,

wherein step (c) comprises storing in memory indices indicative of locations of any new extrema in partitions corresponding to partitions of the set of data values that include altered data values.

14. The method of claim 13, further comprising:

generating a hierarchy of successively coarser representations of extrema by storing in memory indices indicative of locations of extrema of a previous level'"'"'s partitions;

selectively updating the hierarchy from a base level to a highest level for partitions of a base level data containing altered data values; and

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

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

16. The method of claim 14, 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 each level, wherein partitions comprise different numbers of indices within levels of the hierarchy and between different levels of the hierarchy.

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

18. The method of claim 13, wherein the set of data values comprise data values representative of at least one of an image, of video data, or of a signal.

19. The method of claim 18, wherein the signal comprises an audio signal.

20. The method of claim 13, wherein the set of data values comprise one-dimensional data.

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

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

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

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

23. A method, comprising:

(a) partitioning a set of data values into a plurality of first partitions;

(b) storing a set of first indices corresponding to positions of extreme data values of the first partitions;

(c) altering one or more data values to produce one or more altered first partitions; and

(d) updating indices of the set of first indices corresponding to the one or more altered first partitions.

24. The method of claim 23, wherein step (b) comprises:

storing the set of first indices in memory.

25. The method of claim 23, wherein step (d) comprises:

by storing one or more of indices of the set of first indices in memory.

26. The method of claim 23, further comprising:

partitioning the set of first indices into a plurality of second partitions; and

storing a set of second indices corresponding to indices of the second partitions associated with extreme data values.

27. The method of claim 26, wherein step (c) further comprises:

updating indices of the set of second indices corresponding to the one or more altered second partitions.

28. The method of claim 23, wherein step (d) comprises comparing data values of the one or more altered first partitions.

29. The method of claim 23, wherein step (d) 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.

59. The method of claim 23, wherein the set of data values is representative of at least one of image data, video data, or audio data.

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

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

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

30. An apparatus, comprising:

an encoder adapted 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.

31. The apparatus of claim 30, wherein the encoder is further adapted to update the hierarchical data structure in response to a new extremum of the data set.

32. The apparatus of claim 30, 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; and

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.

33. The apparatus of claim 32, wherein the encoder is further adapted 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.

34. The apparatus of claim 32, wherein the encoder is further adapted 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.

35. The apparatus of claim 32, wherein the encoder is further adapted 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.

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

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

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

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

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

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

42. The apparatus of claim 32, further comprising:

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

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

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

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

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

partition a base level of data values into first partitions;

generate a first level including indices indicating positions of extreme data values of the first partitions;

generate an apex including at least one extreme index of the first level corresponding to an extreme data value of the base level; and

modify the first level in response to altering at least one data value of the base level, by storing a new index in the first level, 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.

46. The computer-readable medium of claim 45, containing further instructions that, when executed by a processor, causes the processor to:

partition the first level into second partitions; and

form a second level, the second level including extreme indices of the second partitions.

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

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

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

50. The computer-readable medium of claim 45, wherein the base level comprises data values representative of one of image data, video data, or audio data.

51. The computer-readable medium of claim 45, wherein the data structure comprises a hierarchy of arrays or a tree.

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

53. The computer-readable medium of claim 45, containing further instructions that, when executed by a processor, causes the processor to:

store indices of the second partitions in memory.

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