HIERARCHICAL UPDATE SCHEME FOR EXTREMUM LOCATION

• US 20080201352A1
• 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,213 B2
• Time in Patent Office: Days
• US Class Current: 707/102
• CPC Class Codes: H04N 19/97 Matching pursuit coding

Abstract

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

Claims

1. A method for generating data comprising:

partitioning data values of a base level into first partitions;

generating a first level including extreme data values of the first partitions;

generating an apex including at least one 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 having a new extreme data value through storing the new extreme data value in the first level, 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:

partitioning the first level into second partitions; and

generating a second level, the second level including extreme data values of the second partitions.

3. The method of claim 2, 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 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.

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 the first partitions include different numbers of data values.

13. The method of claim 1, further comprising:

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

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

15. A method for generating data, comprising:

partitioning a base level data set;

forming a coarse representation of extrema of partitions of the base level data by finding and storing the extrema of the partitions in memory; and

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

16. The method of claim 15, further comprising:

forming 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;

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

identifying extrema of the base level data by processing data 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 extrema of a next lower level, the method further comprising:

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

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

20. The method of claim 15, further comprising:

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

21. The method of claim 15, wherein the base level data set is representative of at least one of an image, of video data, or of a signal.

22. The method of claim 21, wherein the signal comprises an audio signal.

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

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

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

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

26. A method of encoding, comprising:

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

storing a set of first extrema corresponding to extreme data values of the first partitions;

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

updating extreme data values of the set of first extrema corresponding to the one or more altered first partitions.

27. The method of claim 26, wherein storing the set of first extrema comprises:

placing the extreme data values of the first partitions in memory.

28. The method of claim 27, wherein updating extreme data values comprises:

replacing one or more of the extreme data values of the first partitions in memory.

29. The method of claim 26, further comprising:

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

storing a set of second extrema corresponding to extreme data values of the second partitions.

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

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

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

32. The method of claim 26, 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.

33. The method of claim 26, further comprising:

storing a set of attributes corresponding to the set of first extrema;

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

updating the set of attributes in response to new extrema associated with the one or more altered first partitions.

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

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

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

34. An apparatus, comprising:

an encoder adapted to use a hierarchical data structure to identify an extremum of a data set.

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

36. The apparatus of claim 34, wherein the hierarchical data structure comprises:

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

a first level including extreme data values of the first partitions; and

an apex including at least one extreme data value of the first level corresponding to an extremum of the base level.

37. The apparatus of claim 36, wherein the encoder is further adapted to update the hierarchical data structure in response to a new extremum of the data set by, at least in part, placing the new extreme data value in the first level.

38. The apparatus of claim 36, wherein the encoder is further adapted to update the hierarchical data structure in response to a new extremum of the data set by placing the new extreme data value in the apex if the new extreme data value comprises a new extremum of the base level.

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

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

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

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

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

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

45. The apparatus of claim 36, wherein the first partitions include different numbers of data values.

46. The apparatus of claim 36, further comprising:

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

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

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

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

49. A computer-readable medium containing instructions for controlling at least one processor by a method comprising:

partitioning data values of a base level into first partitions;

generating a first level including extreme data values of the first partitions;

generating an apex including at least one 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 having a new extreme data value through storing the new extreme data value in the first level, 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.

50. The computer-readable medium of claim 49, containing further instructions for controlling at least one processor by a method comprising:

partitioning the first level into second partitions; and

generating a second level of the data, the second level including extreme data values of the second partitions.

51. The computer-readable medium of claim 49, containing further instructions for controlling at least one processor by a method comprising generating an 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.

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

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

54. The computer-readable medium of claim 49, containing further instructions for controlling at least one processor by a method comprising:

storing extreme data values of the first partitions in memory.

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