Fast covariance matrix generation

• US 8,583,656 B1
• Filed: 09/12/2012
• Issued: 11/12/2013
• Est. Priority Date: 04/23/2009
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kwatra, Vivek
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): VU, THONG H
• Application Number:
  US13/612,824
• Time in Patent Office: 426 Days
• Field of Search: 707/104, 707/3, 707/743, 382/190, 382/159, 382/228, 382/124, 382/132, 382/103
• US Class Current: 707/743
• CPC Class Codes: G06F 16/43 Querying
• CPC Class Codes: G06F 16/45 Clustering; Classification
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 18/2135 based on approximation criteria, e.g. principal component analysis

Abstract

A covariance matrix associated for a set of spatial and/or temporal sub-portions of a media object is populated based on a lookup table of relative displacements and sums of covariance values generated from pairs of data elements in the media object. The lookup table is generated in linear time, providing an efficient method of generating the covariance matrix.

Claims

1. A computer-implemented method of generating a covariance matrix associated with a media object, wherein the covariance matrix describes the covariance between data elements in sub-portions of the media object, the method executed by a computing system including a memory in which the media object is stored, and comprising:

automatically identifying a plurality of relative displacements between pairs of data elements within spatial/temporal data of the media object;

for each one of the plurality of relative displacements, automatically generating a corresponding covariance sum, to produce a plurality of covariance sums;

storing the plurality of covariance sums in a lookup table in the memory, each of the covariance sums stored in the lookup table in association with its corresponding relative displacement to allow retrieval of the covariance sum given the relative displacement;

automatically populating a covariance matrix associated with the media object by retrieving covariance sums from the lookup table using the relative displacements, and writing the retrieved covariance sums to the covariance matrix; and

storing the covariance matrix in the memory of the computing system.

2. The method of claim 1, wherein for each one of the plurality of relative displacements, automatically generating a corresponding covariance sum, to produce a plurality of covariance sums comprises:

identifying a plurality of pairs of data elements within spatial/temporal data of the media object, each pair of data elements having a relative displacement of the plurality of relative displacements;

generating, for each pair of data elements of the plurality of pairs of data elements, a covariance value based on data values associated with each pair of data elements;

identifying, for each of the plurality of relative displacements, a subset of the plurality of pairs of data elements that are associated with the relative displacement; and

generating a covariance sum for each of the plurality of relative displacements by calculating a sum of the covariance values associated with the subset of the plurality of pairs of data elements that are associated with the relative displacement.

3. The method of claim 1, wherein for each one of the plurality of relative displacements, automatically generating a corresponding covariance sum, to produce a plurality of covariance sums comprises generating a fast Fourier transform based on the spatial/temporal data of the media object.

4. The method of claim 1, wherein for each one of the plurality of relative displacements, automatically generating a corresponding covariance sum, to produce a plurality of covariance sums comprises:

identifying a plurality of pairs of data elements within the spatial/temporal data of the media object, each pair of data elements having a relative displacement of the plurality of relative displacements and a location of a plurality of locations;

generating, for each pair of data elements of the plurality of pairs of data elements, a covariance value based on data values associated with each pair of data elements;

identifying, for each of the plurality of relative displacements, a subset of the plurality of pairs of data elements that are associated with the relative displacement and a same location of the plurality of locations; and

generating a covariance sum for each of the plurality of relative displacements by calculating a sum of the covariance values associated with the subset of the plurality of pairs of data elements that are associated with the relative displacement and the same location of the plurality of locations.

5. The method of claim 1, wherein automatically populating a covariance matrix associated with the media object by retrieving covariance sums from the lookup table comprises:

generating an empty covariance matrix, where each entry in the covariance matrix specifies a pair of data elements;

identifying, for each entry in the covariance matrix, a relative displacement between the pair of data elements;

for each entry in the covariance matrix;

retrieving from the lookup table a covariance sum associated with the relative displacement; and

storing the retrieved covariance sum in the entry in the covariance matrix.

6. The method of claim 1, further comprising:

automatically generating a matrix decomposition based on the covariance matrix;

automatically identifying a set of lower-order components based on the matrix decomposition of the covariance matrix; and

storing the set of lower-order components in the memory.

7. The method of claim 6, further comprising:

generating a plurality of covariance matrices;

weighting each covariance matrix of the plurality of covariance matrices based on a number of pairs of data elements used to generate a covariance sum associated with an entry in the covariance matrix;

generating a combined covariance matrix based on an average of the weighted plurality of covariance matrices; and

generating a matrix decomposition based on the combined covariance matrix.

8. The method of claim 6, further comprising

generating a feature vector associated with a sub-portion of the media object;

and

generating a set of features associated with the sub-portion of the media object based on the feature vector and the set of lower-order components.

9. The method of claim 8, further comprising:

generating a plurality of sets of features for a plurality of media objects; and

generating a search index based on the plurality of sets of features for the plurality of media objects.

10. The method of claim 9, further comprising:

identifying a set of media objects that match an input media object based on the search index.

11. The method of claim 8, further comprising:

generating a plurality of sets of features associated with a plurality of media objects in association with a plurality of classes associated with the plurality of media objects; and

generating a media object classifier based on the plurality of sets of features associated with the plurality of media objects in and the plurality of classes associated with the plurality of media objects.

12. The method of claim 11, further comprising:

generating a value which specifies the likelihood that an input media object is associated with a class of media objects responsive to applying the media object classifier to a set of features associated with the input media object.

13. The method of claim 1, wherein the data elements are pixels, the media object is a digital image and the relative displacement is a two-dimensional coordinate pair based on the pixels.

14. The method of claim 1, wherein the data elements are time points, the media object is an audio file and the relative displacement is a time interval between time points.

15. The method of claim 1, wherein the data elements are three-dimensional coordinates in a coordinate system, the media object comprises geographic data and the relative displacement is a vector in the coordinate system.

16. A non-transitory computer-readable storage medium encoded with executable computer program code for generating a covariance matrix associated with a media object, wherein the covariance matrix describes the covariance between data elements in sub-portions of the media object, the program code comprising instructions for:

automatically identifying a plurality of relative displacements between pairs of data elements within spatial/temporal data of the media object;

for each one of the plurality of relative displacements, automatically generating a corresponding covariance sum, to produce a plurality of covariance sums;

storing the plurality of covariance sums in a lookup table in a memory, each of the covariance sums stored in the lookup table in association with its corresponding relative displacement to allow retrieval of the covariance sum given the relative displacement;

automatically populating a covariance matrix associated with the media object by retrieving covariance sums directly from the lookup table using the relative displacements, and writing the retrieved covariance sums to the covariance matrix; and

storing the covariance matrix in the memory.

17. The medium of claim 16, wherein the program code for automatically generating a covariance sum for each one of the plurality of relative displacements to produce a plurality of covariance sums comprises program code for:

identifying a plurality of pairs of data elements within spatial/temporal data of the media object, each pair of data elements having a relative displacement of the plurality of relative displacements;

generating, for each pair of data elements of the plurality of pairs of data elements, a covariance value based on data values associated with each pair of data elements;

identifying, for each of the plurality of relative displacements, a subset of the plurality of pairs of data elements that are associated with the relative displacement; and

generating a covariance sum for each of the plurality of relative displacements by calculating a sum of the covariance values associated with the subset of the plurality of pairs of data elements that are associated with the relative displacement.

18. The medium of claim 16, wherein the program code for automatically generating a covariance sum for each one of the plurality of relative displacements to produce a plurality of covariance sums comprises program code for generating a fast Fourier transform based on the spatial/temporal data of the media object.

19. The medium of claim 16, wherein the program code for automatically generating a covariance sum for each one of the plurality of relative displacements to produce a plurality of covariance sums comprises program code for:

identifying a plurality of pairs of data elements within the spatial/temporal data of the media object, each pair of data elements having a relative displacement of the plurality of relative displacements and a location of a plurality of locations;

generating, for each pair of data elements of the plurality of pairs of data elements, a covariance value based on data values associated with each pair of data elements;

identifying, for each of the plurality of relative displacements, a subset of the plurality of pairs of data elements that are associated with the relative displacement and a same location of the plurality of locations; and

generating a covariance sum for each of the plurality of relative displacements by calculating a sum of the covariance values associated with the subset of the plurality of pairs of data elements that are associated with the relative displacement and the same location of the plurality of locations.

20. The medium of claim 16, wherein program code for automatically populating a covariance matrix associated with the media object by retrieving covariance sums from the lookup table comprises program code for:

generating an empty covariance matrix, where each entry in the covariance matrix specifies a pair of data elements;

identifying, for each entry in the covariance matrix, a relative displacement between the pair of data elements;

for each entry in the covariance matrix;

retrieving from the lookup table a covariance sum associated with the relative displacement; and

storing the retrieved covariance sum in the entry in the covariance matrix.

21. The medium of claim 16, further comprising program code for:

automatically generating a matrix decomposition based on the covariance matrix;

automatically identifying a set of lower-order components based on the matrix decomposition of the covariance matrix; and

storing the set of lower-order components.

22. The medium of claim 21, further comprising program code for:

generating a plurality of covariance matrices;

weighting each covariance matrix of the plurality of covariance matrices based on a number of pairs of data elements used to generate a covariance sum associated with an entry in the covariance matrix;

generating a combined covariance matrix based on an average of the weighted plurality of covariance matrices; and

generating a matrix decomposition based on the combined covariance matrix.

23. The medium of claim 21, further comprising program code for:

generating a feature vector associated with a sub-portion of the media object; and

generating a set of features associated with the sub-portion of the media object based on the feature vector and the set of lower-order components.

24. The medium of claim 23, further comprising program code for:

generating a plurality of sets of features for a plurality of media objects; and

generating a search index based on the plurality of sets of features for the plurality of media objects.

25. The medium of claim 24, further comprising program code for:

identifying a set of media objects that match an input media object based on the search index.

26. The medium of claim 23, further comprising program code for:

generating a plurality of sets of features associated with a plurality of media objects in association with a plurality of classes associated with the plurality of media objects; and

generating a media object classifier based on the plurality of sets of features associated with the plurality of media objects in and the plurality of classes associated with the plurality of media objects.

27. The medium of claim 26, further comprising program code for:

generating a value which specifies the likelihood that an input media object is associated with a class of media objects responsive to applying the media object classifier to a set of features associated with the input media object.

28. The medium of claim 16, wherein the data elements are pixels, the media object is a digital image and the relative displacement is a two-dimensional coordinate pair based on the pixels.

29. The medium of claim 16, wherein the data elements are time points, the media object is an audio file and the relative displacement is a time interval between time points.

30. The medium of claim 16, wherein the data elements are three-dimensional coordinates in a coordinate system, the media object comprises geographic data and the relative displacement is a vector in the coordinate system.

31. A computer system for generating a covariance matrix associated with a media object, wherein the covariance matrix describes the covariance between data elements in sub-portions of the media object, the computer system comprising:

a memory;

a processor;

a covariance matrix generation module configured to;

automatically identify a plurality of relative displacements between pairs of data elements within spatial/temporal data of the media object;

for each one of the plurality of relative displacements, automatically generate a corresponding covariance sum, to produce a plurality of covariance sums;

store the plurality of covariance sums in a lookup table in the memory, each of the covariance sums stored in the lookup table in association with its corresponding relative displacement to allow retrieval of the covariance sum given the relative displacement;

automatically populate a covariance matrix associated with the media object by retrieving covariance sums from the lookup table using the relative displacement, and write the retrieved covariance sums to the covariance matrix; and

store the covariance matrix in the memory.

32. The system of claim 31, wherein for each one of the plurality of relative displacements, automatically generating a corresponding covariance sum, to produce a plurality of covariance sums comprises:

identifying a plurality of pairs of data elements within spatial/temporal data of the media object, each pair of data elements having a relative displacement of the plurality of relative displacements;

generating, for each pair of data elements of the plurality of pairs of data elements, a covariance value based on data values associated with each pair of data elements;

identifying, for each of the plurality of relative displacements, a subset of the plurality of pairs of data elements that are associated with the relative displacement; and

generating a covariance sum for each of the plurality of relative displacements by calculating a sum of the covariance values associated with the subset of the plurality of pairs of data elements that are associated with the relative displacement.

33. The system of claim 31, wherein for each one of the plurality of relative displacements, automatically generating a corresponding covariance sum, to produce a plurality of covariance sums comprises generating a fast Fourier transform based on the spatial/temporal data of the media object.

34. The system of claim 31, wherein for each one of the plurality of relative displacements, automatically generating a corresponding covariance sum, to produce a plurality of covariance sums comprises:

identifying a plurality of pairs of data elements within the spatial/temporal data of the media object, each pair of data elements having a relative displacement of the plurality of relative displacements and a location of a plurality of locations;

generating, for each pair of data elements of the plurality of pairs of data elements, a covariance value based on data values associated with each pair of data elements;

identifying, for each of the plurality of relative displacements, a subset of the plurality of pairs of data elements that are associated with the relative displacement and a same location of the plurality of locations; and

generating a covariance sum for each of the plurality of relative displacements by calculating a sum of the covariance values associated with the subset of the plurality of pairs of data elements that are associated with the relative displacement and the same location of the plurality of locations.

35. The system of claim 31, wherein the covariance matrix generation module is further configured to:

generate an empty covariance matrix, where each entry in the covariance matrix specifies a pair of data elements;

identify, for each entry in the covariance matrix, a relative displacement between the pair of data elements;

for each entry in the covariance matrix;

retrieve from the lookup table a covariance sum associated with the relative displacement; and

store the retrieved covariance sum in the entry of the covariance matrix.

36. The system of claim 31, further comprising a matrix decomposition module stored in the memory and configured to:

automatically generate a matrix decomposition based on the covariance matrix;

automatically identify a set of lower-order components based on the matrix decomposition of the covariance matrix; and

store the set of lower-order components.

37. The system of claim 36, wherein the matrix decomposition module is further configured to:

generate a plurality of covariance matrices;

weight each covariance matrix of the plurality of covariance matrices based on a number of pairs of data elements used to generate a covariance sum associated with an entry in the covariance matrix;

generate a combined covariance matrix based on an average of the weighted plurality of covariance matrices; and

generate a matrix decomposition based on the combined covariance matrix.

38. The system of claim 36, further comprising for a feature generation module stored in the memory and configured to:

generate a feature vector associated with a sub-portion of the media object; and

generate a set of features associated with the sub-portion of the media object based on the feature vector and the set of lower-order components.

39. The system of claim 38, wherein the feature generation module is further configured to:

generate a plurality of sets of features for a plurality of media object; and

wherein the computing system further comprises an indexing module configured to generate a search index based on the plurality of sets of features for the plurality of media objects.

40. The system of claim 39, further comprising a search module configured to:

identify a set of media objects that match an input media object based on the search index.

41. The system of claim 38, wherein the feature generation module is further configured to:

generate a plurality of sets of features associated with a plurality of media objects in association with a plurality of classes associated with the plurality of media objects; and

wherein the computing system further comprises a classifier generation module configured to generate a media object classifier based on the plurality of sets of features associated with the plurality of media objects in and the plurality of classes associated with the plurality of media objects.

42. The system of claim 41, further comprising a classification module configured to:

generate a value which specifies the likelihood that an input media object is associated with a class of media objects responsive to applying the media object classifier to a set of features associated with the input media object.

43. The system of claim 31, wherein the data elements are pixels, the media object is a digital image and the relative displacement is a two-dimensional coordinate pair based on the pixels.

44. The system of claim 31, wherein the data elements are time points, the media object is an audio file and the relative displacement is a time interval between time points.

45. The system of claim 31, wherein the data elements are three-dimensional coordinates in a coordinate system, the media object comprises geographic data and the relative displacement is a vector in the coordinate system.