Methods and systems for arranging and searching a database of media content recordings

• US 9,390,170 B2
• Filed: 03/15/2013
• Issued: 07/12/2016
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Shazam Ivestments Ltd. (Apple Inc.)
• Inventors: Wang, Avery Li-Chun, Woodhead, Ira Joseph, Elsen, Erich Konrad
• Primary Examiner(s): Ruiz, Angelica
• Application Number:
  US13/837,284
• Publication Number:
  US 20140280233A1
• Time in Patent Office: 1,215 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/634 Query by example, e.g. query by humming
• CPC Class Codes: G06F 16/783 using metadata automatically derived from the content

Abstract

Methods and systems for arranging and searching a database of media content recordings are provided. In one example, a method is provided that comprises receiving a sample of media content, and performing, by a computing device, a content recognition of the sample of media content using a data file including a concatenation of representations for each of a plurality of media content recordings. In other examples, another method is provided that comprises receiving media content recordings, determining a representation for each media content recording, concatenating by a computing device the representation for each media content recording as a data file, and storing by the computing device a mapping between an identifier for a respective media content recording and a global position in the data file that corresponds to the representation of the respective media content recording.

Claims

1. A method comprising:

receiving a sample of media content; and

performing, by a computing device, a content recognition of the sample of media content using a data structure including a concatenation of representations for each of a plurality of indexed media content recordings, wherein the data structure has associated sound identifiers per representations for each of the plurality of indexed media content recordings.

2. The method of claim 1, wherein the concatenation includes a plurality of respective representations per media content recording and arranged in sequential time order per media content recording in the data structure.

3. The method of claim 1, wherein the representation for a given media content recording comprises a set of fingerprints at respective landmark positions within the given media content recording, wherein each fingerprint corresponds to a global position within the data structure.

4. The method of claim 3, wherein performing the content recognition comprises:

determining fingerprints in the data structure that match to one or more fingerprints of the sample of media content; and

pairing corresponding global positions of the matching fingerprints with corresponding respective landmark positions of the one or more fingerprints in the sample of media content to provide global position-landmark position pairs.

5. The method of claim 4, further comprising:

sorting the global position-landmark position pairs;

determining clusters of the global position-landmark position pairs that are linearly related; and

identifying a matching media content recording to the sample of media content as a media content recording having a cluster with a largest number of global position-landmark position pairs that are linearly related.

6. The method of claim 5, wherein sorting the global position-landmark position pairs comprises using a radix sorting method.

7. The method of claim 5, wherein a sound identifier of the given media content recording is associated with global positions of representations of the given media content recording in the data structure, and the method further comprises determining the sound identifier of the matching media content recording based on one of the corresponding global positions of the matching fingerprints in the data structure.

8. The method of claim 3, wherein a sound identifier of the given media content recording is associated with global positions of representations of the given media content recording in the data structure, and the method further comprises:

determining fingerprints in the data structure that match to one or more fingerprints of the sample of media content;

determining corresponding global positions of the matching fingerprints;

determining time offset pair differences between the corresponding global positions and corresponding landmark positions of the one or more fingerprints of the sample of media content;

identifying a matching media content recording to the sample of media content as a media content recording corresponding to a set of given global positions resulting in a largest number of matching time offset pair differences; and

determining a respective sound identifier associated with the given global position.

9. The method of claim 1, wherein receiving the sample of media content comprises receiving, at the computing device, the sample of media content from an ambient environment of the computing device.

10. The method of claim 1, wherein receiving the sample of media content comprises receiving, at the computing device, the sample of media content from a second computing device.

11. The method of claim 1, further comprising determining an identification of the sample of media content based on a mapping between a sound identifier for a respective media content recording and a global position in the data structure that corresponds to a given representation of the respective media content recording that matches a portion of the sample of media content.

12. The method of claim 1, wherein performing the content recognition comprises:

identifying, within the data structure of the concatenation of representations for each of the plurality of media content recordings, a matching representation to a respective representation of the sample of media content; and

determining a global position in the data structure corresponding to the matching representation.

13. The method of claim 12, wherein the representations for each of the plurality of media content recordings have associated global starting positions within the data structure so as to segment a global timeline of the data structure according to the plurality of media content recordings, and the method further comprises determining a global starting position in the data structure associated with the matching representation at the global position.

14. The method of claim 13, further comprising determining a local position within a given media content recording corresponding to the sample of media content based on the global position and the global starting position.

15. The method of claim 1, further comprising:

receiving a plurality of samples of media content, wherein the plurality of samples include samples of different media content; and

performing, by the computing device, multiple simultaneous content recognitions of the plurality of samples of media content using the data structure.

16. The method of claim 15, wherein performing the multiple simultaneous content recognitions of the plurality of samples of media content using the data structure comprises:

identifying, within the data structure of the concatenation of representations for each of the plurality of media content recordings, a matching representation for each of respective representations of the plurality of samples of media content;

determining global positions in the data structure corresponding to the matching representation for each of the respective representations of the plurality of samples of media content;

generating respective data representations for the global positions including, for each data representative, an identifier as upper bits and a given global position as lower bits; and

processing the respective data representations to identify matching media recordings to the plurality of samples of media content, wherein the upper bits are indicative of a sub-search to the data representation belongs and the lower bits are indicative of a matching media content recording to which the respective sample matched.

17. A non-transitory computer readable medium having stored therein instructions, that when executed by a computing device, cause the computing device to perform functions comprising:

receiving a sample of media content; and

performing a content recognition of the sample of media content using a data structure including a concatenation of representations for each of a plurality of indexed media content recordings, wherein the data structure has associated sound identifiers per representations for each of the plurality of indexed media content recordings.

18. The non-transitory computer readable medium of claim 17, wherein the representation for a given media content recording comprises a set of fingerprints at respective landmark positions within the given media content recording, wherein each fingerprint corresponds to a global position within the data structure.

19. The non-transitory computer readable medium of claim 18, wherein performing the content recognition comprises:

determining fingerprints in the data structure that match to one or more fingerprints of the sample of media content; and

pairing corresponding global positions of the matching fingerprints with corresponding respective landmark positions of the one or more fingerprints in the sample of media content to provide global position-landmark position pairs.

20. The non-transitory computer readable medium of claim 19, wherein the functions further comprise:

sorting the global position-landmark position pairs;

determining clusters of the global position-landmark position pairs that are linearly related; and

identifying a matching media content recording to the sample of media content as a media content recording having a cluster with a largest number of global position-landmark position pairs that are linearly related.

21. The non-transitory computer readable medium of claim 20, wherein sorting the global position-landmark position pairs comprises using a radix sorting method.

22. The non-transitory computer readable medium of claim 20, wherein a sound identifier of the given media content recording is associated with global positions of representations of the given media content recording in the data structure, and the functions further comprise determining the sound identifier of the matching media content recording based on one of the corresponding global positions of the matching fingerprints in the data structure.

23. The non-transitory computer readable medium of claim 18, wherein a sound identifier of the given media content recording is associated with global positions of representations of the given media content recording in the data structure, and the functions further comprise:

determining fingerprints in the data structure that match to one or more fingerprints of the sample of media content;

determining corresponding global positions of the matching fingerprints;

determining time offset pair differences between the corresponding global positions and corresponding landmark positions of the one or more fingerprints of the sample of media content;

identifying a matching media content recording to the sample of media content as a media content recording corresponding to a set of given global positions resulting in a largest number of matching time offset pair differences; and

determining a respective sound identifier associated with the given global position.

24. The non-transitory computer readable medium of claim 17, wherein the functions further comprise determining an identification of the sample of media content based on a mapping between a sound identifier for a respective media content recording and a global position in the data structure that corresponds to a given representation of the respective media content recording that matches a portion of the sample of media content.

25. The non-transitory computer readable medium of claim 17, wherein performing the content recognition comprises:

identifying, within the data structure of the concatenation of representations for each of the plurality of media content recordings, a matching representation to a respective representation of the sample of media content; and

determining a global position in the data structure corresponding to the matching representation.

26. The non-transitory computer readable medium of claim 25, wherein the representations for each of the plurality of media content recordings have associated global starting positions within the data structure so as to segment a global timeline of the data structure according to the plurality of media content recordings, and the functions further comprise determining a global starting position in the data structure associated with the matching representation at the global position.

27. The non-transitory computer readable medium of claim 17, wherein the functions further comprise:

receiving a plurality of samples of media content, wherein the plurality of samples include samples of different media content; and

performing multiple simultaneous content recognitions of the plurality of samples of media content using the data structure.

28. The non-transitory computer readable medium of claim 27, wherein performing the multiple simultaneous content recognitions of the plurality of samples of media content using the data structure comprises:

identifying, within the data structure of the concatenation of representations for each of the plurality of media content recordings, a matching representation for each of respective representations of the plurality of samples of media content;

determining global positions in the data structure corresponding to the matching representation for each of the respective representations of the plurality of samples of media content;

generating respective data representations for the global positions including, for each data representative, an identifier as upper bits and a given global position as lower bits; and

processing the respective data representations to identify matching media recordings to the plurality of samples of media content, wherein the upper bits are indicative of a sub-search to the data representation belongs and the lower bits are indicative of a matching media content recording to which the respective sample matched.

29. A system comprising:

at least one processor; and

data storage configured to store instructions that when executed by the at least one processor cause the system to perform functions comprising;

receiving a sample of media content;

performing a content recognition of the sample of media content by matching a portion of the sample of media content to a respective media content recording in a data structure, wherein the data structure includes a concatenation of representations for each of a plurality of media content recordings, and wherein the data structure has associated identifiers per groupings of the representations for each of the plurality of media content recordings; and

determining an identification of the sample of media content based on a mapping between an identifier for a respective media content recording in the data structure and a global position in the data structure that corresponds to a given representation of the respective media content recording that matches a portion of the sample of media content.

30. The system of claim 29, wherein the representation for a given media content recording comprises a set of fingerprints at respective landmark positions within the given media content recording, wherein each fingerprint corresponds to a global position within the data structure.

31. The system of claim 30, wherein performing the content recognition comprises:

determining fingerprints in the data structure that match to one or more fingerprints of the sample of media content; and

pairing corresponding global positions of the matching fingerprints with corresponding respective landmark positions of the one or more fingerprints in the sample of media content to provide global position-landmark position pairs.

32. The system of claim 31, wherein the functions further comprise:

sorting the global position-landmark position pairs;

determining clusters of the global position-landmark position pairs that are linearly related; and

identifying a matching media content recording to the sample of media content as a media content recording having a cluster with a largest number of global position-landmark position pairs that are linearly related.

33. The system of claim 32, wherein a sound identifier of the given media content recording is associated with global positions of representations of the given media content recording in the data structure, and the functions further comprise determining the sound identifier of the matching media content recording based on one of the corresponding global positions of the matching fingerprints in the data structure.

34. The system of claim 30, wherein a sound identifier of the given media content recording is associated with global positions of representations of the given media content recording in the data structure, and the functions further comprise:

determining fingerprints in the data structure that match to one or more fingerprints of the sample of media content;

determining corresponding global positions of the matching fingerprints;

determining time offset pair differences between the corresponding global positions and corresponding landmark positions of the one or more fingerprints of the sample of media content;

identifying a matching media content recording to the sample of media content as a media content recording corresponding to a set of given global positions resulting in a largest number of matching time offset pair differences; and

determining a respective sound identifier associated with the given global position.

35. The system of claim 29, wherein performing the content recognition comprises:

identifying, within the data structure of the concatenation of representations for each of the plurality of media content recordings, a matching representation to a respective representation of the sample of media content; and

determining a global position in the data structure corresponding to the matching representation.

36. The system of claim 35, wherein the representations for each of the plurality of media content recordings have associated global starting positions within the data structure so as to segment a global timeline of the data structure according to the plurality of media content recordings, and the functions further comprise determining a global starting position in the data structure associated with the matching representation at the global position.

37. The system of claim 29, wherein the functions further comprise:

receiving a plurality of samples of media content, wherein the plurality of samples include samples of different media content; and

performing multiple simultaneous content recognitions of the plurality of samples of media content using the data structure.

38. The system of claim 37, wherein performing the multiple simultaneous content recognitions of the plurality of samples of media content using the data structure comprises:

identifying, within the data structure of the concatenation of representations for each of the plurality of media content recordings, a matching representation for each of respective representations of the plurality of samples of media content;

determining global positions in the data structure corresponding to the matching representation for each of the respective representations of the plurality of samples of media content;

generating respective data representations for the global positions including, for each data representative, an identifier as upper bits and a given global position as lower bits; and

processing the respective data representations to identify matching media recordings to the plurality of samples of media content, wherein the upper bits are indicative of a sub-search to the data representation belongs and the lower bits are indicative of a matching media content recording to which the respective sample matched.