System and method for inferring similarities between media objects

• US 20060080356A1
• Filed: 10/13/2004
• Published: 04/13/2006
• Est. Priority Date: 10/13/2004
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Platt, John, Herley, Cormac, Burges, Chris
• Application Number:
  US10/965,604
• Publication Number:
  US 20060080356A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/48 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually

Abstract

A “similarity quantifier” automatically infers similarity between media objects which have no inherent measure of distance between them. For example, a human listener can easily determine that a song like Solsbury Hill by Peter Gabriel is more similar to Everybody Hurts by R.E.M. than it is to Highway to Hell by AC/DC. However, automatic determination of this similarity is typically a more difficult problem. This problem is addressed by using a combination of techniques for inferring similarities between media objects thereby facilitating media object filing, retrieval, classification, playlist construction, etc. Specifically, a combination of audio fingerprinting and repeat object detection is used for gathering statistics on broadcast media streams. These statistics include each media objects identity and positions within the media stream. Similarities between media objects are then inferred based on the observation that objects appearing closer together in an authored stream are more likely to be similar.

Claims

1. A system for inferring similarities between media objects in an authored media stream, comprising using a computing device to:

identify media objects and relative positions of the media objects within at least one media stream;

generate at least one ordered list representing relative positions of the media objects within the at least one media stream;

infer a similarity score between a plurality of media objects as a function of the at least one ordered list.

2. The system of claim 1 wherein inferring a similarity score between a plurality of media objects further comprises:

constructing an adjacency graph from at least one of the ordered lists,

wherein vertices in the adjacency graph represent identified media objects and edges in the graph represent adjacency; and

using the adjacency graph for computing the similarity score between a plurality of media objects.

3. The system of claim 1 wherein identifying media objects and relative positions of the media objects within at least one media stream comprises analyzing metadata embedded in the media stream to explicitly determine the media object identities and relative positions within the stream.

4. The system of claim 1 wherein identifying media objects and relative positions of the media objects within at least one media stream comprises computing audio fingerprints from sampled portions of the at least one media stream and comparing the computed audio fingerprints to a fingerprint database to explicitly determine the media object identities and relative positions within the stream.

5. The system of claim 1 wherein identifying media objects and relative positions of the media objects within at least one media stream comprises locating repeating instances of unique media objects within the media stream and implicitly determining the media object identities and relative positions through a direct comparison of multiple portions of the media stream centered around the repeating instances of each particular unique media object within the stream.

6. The system of claim 1 further comprising automatically recommending media objects to a user by identifying a set of one or more media objects that are similar to a user selection of one or more media objects based on the inferred similarity scores.

7. The system of claim 1 further comprising using the inferred similarity scores for automatically generating a similarity-based media object playlist given one or more user selected seed media objects.

8. The system of claim 7, wherein automatically generating a similarity-based media object playlist comprises simulating a Markov chain.

9. The system of claim 1 further comprising automatically determining media object endpoints for the media objects identified in the at least one media stream.

10. The system of claim 9 further comprising copying at least one individual media object from the at least one media stream to a media object library along with the identity information of each copied media object.

11. The system of claim 10 further comprising using the inferred similarity scores for replacing at least one media object in an at least partially buffered media stream during playback of that media stream with at least one replacement media object from the media object library that is sufficiently similar to any media objects preceding or succeeding the at least one replacement media object.

12. The system of claim 1 further comprising weighting at least a portion of one of the ordered lists prior to inferring a similarity score between a plurality of media objects.

13. The system of claim 1 further comprising combining one or more of the ordered lists to create a composite ordered list prior to inferring a similarity score between a plurality of media objects.

14. A computer-readable medium having computer executable instructions for computing statistical similarity scores between discrete music objects in an authored media stream, comprising:

receiving at least one authored media stream containing at least some music objects;

identifying music objects and relative positions of each identified music object within the at least one authored media stream;

populating at least one ordered list with the identification and relative position information of the music objects; and

computing similarity scores for measuring a similarity between a plurality of identified music objects in the at least one authored media stream through a statistical analysis of the relative position information of the one or more identified music objects relative to each other of the one or more identified music objects.

15. The computer-readable medium of claim 14 wherein identifying music objects and relative positions of each identified music object within the at least one authored media stream comprises at least one of:

analyzing embedded metadata to explicitly determine the music object identities and relative positions;

comparing audio fingerprints from computed from samples of the at least one authored media stream to a fingerprint database to explicitly determine the music object identities and relative positions; and

implicitly determining unique music object identities and relative positions by locating repeating instances of the unique media objects within the media stream through a direct comparison of multiple portions of the media stream centered around repeating instances of each particular unique media object within the stream.

16. The computer-readable medium of claim 14 wherein computing similarity scores further comprises:

constructing an adjacency graph from at least one of the ordered lists, wherein vertices in the adjacency graph represent identified music objects and edges in the graph represent adjacency observations; and

computing the similarity scores between a plurality of music objects from the edges and vertices of the adjacency graph.

17. The computer-readable medium of claim 14 further comprising weighting at least a portion of one or more of the ordered lists.

18. The computer-readable medium of claim 16 further comprising weighting one or more of the edges of the adjacency graph.

19. The computer-readable medium of claim 14 further comprising using the similarity scores to generate musical playlists by simulating a Markov chain.

20. A computer-implemented process for inferring similarities between individual songs in broadcast media streams, comprising:

receiving at least one media stream broadcast;

explicitly identifying one or more songs within the at least one media stream through a comparison of sampled portions of the media stream to a fingerprint database comprised of information characterizing a set of known songs;

implicitly identifying one or more songs not already identified through the comparison to the fingerprint database by locating repeating instances of unique unidentified songs within the at least one media stream through a direct comparison of multiple portions of the at least one media stream centered around repeating instances of each particular unique unidentified song within the at least one media stream;

constructing at least one ordered list including at least the identity and a relative position of each explicitly and implicitly identified song; and

inferring a similarity score between a plurality of songs in each ordered list as a function of the at least one ordered list.

21. The computer-implemented process of claim 20 further comprising using available metadata for explicitly identifying songs that were not already identified, and including the identity and relative positions of the songs identified using the metadata in the at least one ordered list.

22. The computer-implemented process of claim 20 wherein inferring a similarity score between a plurality of songs in each ordered list further comprises:

constructing an adjacency graph from at least one of the ordered lists, wherein vertices in the adjacency graph represent identified songs and edges in the graph represent observations of adjacency between the identified songs; and

using the adjacency graph for inferring a similarity score between a plurality of songs in each ordered list.

23. The computer-implemented process of claim 20 further comprising weighting at least a portion of one or more of the ordered lists.

24. The computer-implemented process of claim 22 further comprising weighting one or more of the edges of the adjacency graph.

25. The computer-implemented process of claim 20 further comprising automatically recommending one or more songs to a user by identifying a set of one or more songs that are similar to a user selection of one or more songs based on the inferred similarity scores.

26. The computer-implemented process of claim 20 further comprising using the inferred similarity scores for automatically generating a similarity-based song playlist given one or more user selected seed songs.

27. The computer-implemented process of claim 26, wherein automatically generating a similarity-based song playlist comprises simulating a Markov chain.

28. The computer-implemented process of claim 20 further comprising automatically determining endpoints of the identified songs.

29. The computer-implemented process of claim 28 further comprising copying at least one individual song from the at least one media stream to a song library along with the identity information of each copied song.

30. The computer-implemented process of claim 29 further comprising using the inferred similarity scores for inserting one or more songs into a media stream by providing a least one inserted song which is sufficiently similar to any songs immediately preceding and immediately succeeding an insertion point in the media stream.