Pitch shift resistant audio matching

• US 9,052,986 B1
• Filed: 04/18/2012
• Issued: 06/09/2015
• Est. Priority Date: 04/18/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Postelnicu, Gheorghe, Sharifi, Matthew
• Primary Examiner(s): Kuntz, Curtis
• Assistant Examiner(s): MAUNG, THOMAS H
• Application Number:
  US13/450,422
• Time in Patent Office: 1,147 Days
• Field of Search: 704/E19.009
• US Class Current: 1/1
• CPC Class Codes: G06F 16/683 using metadata automatically derived from the content
• CPC Class Codes: G06F 17/00 Digital computing or data processing equipment or methods, specially adapted for specific functions information retrieval, database structures or file system structures therefor G06F16/00
• CPC Class Codes: G10H 2240/041 File watermark, i.e. embedding a hidden code in an electrophonic musical instrument file or stream for identification or authentification purposes
• CPC Class Codes: G10H 2240/141 Library retrieval matching, i.e. any of the steps of matching an inputted segment or phrase with musical database contents, e.g. query by humming, singing or playing; the steps may include, e.g. musical analysis of the input, musical feature extraction, query formulation, or details of the retrieval process
• CPC Class Codes: G10L 25/48 specially adapted for particular use

Abstract

Systems and methods are provided herein relating to audio matching. Both melody fingerprints and audio-id fingerprints can be used to improve an audio matching system'"'"'s resistance to pitch shifts. A melody fingerprint can be used to identify a set of potential melody matches. Varying pitch shifted audio-id reference fingerprints can be generated for audio-id fingerprints associated with the potential matches identified in melody matching. Additional pitch shifted audio-id fingerprints of a reference sample are generated and used in matching only if an audio sample has previously been matched to a melody fingerprint of the same reference sample. A reference index need not be expanded to include pitch shifted variations of each reference sample as pitch shifted variations of audio-id fingerprint reference samples are generated and used only if their associated melody fingerprint is deemed a potential match.

Claims

1. A system comprising:

a memory that has stored thereon computer executable components; and

a processor that executes the following computer executable components stored in the memory;

an input component that receives a video sample;

a fingerprint component that generates a melody fingerprint and an audio-id fingerprint based on an audio track of the video sample;

a melody matching component that identifies a set of potential audio matches for the audio track based on comparing the melody fingerprint to reference melody fingerprints for the potential audio matches of the set;

an audio-id matching component that identifies reference audio-id fingerprints respectively associated with the potential audio matches of the set;

a pitch shift evaluation component that determines an estimated amount of pitch shift between the audio track and the reference audio-id fingerprints; and

a pitch variation component that generates sets of pitch modified fingerprints for each of the reference audio-id fingerprints based on the estimated amount of pitch shift,

wherein the audio-id matching component identifies a subset of the set of the potential audio matches based on comparing the audio-id fingerprint to the reference audio-id fingerprints and the sets of the pitch modified fingerprints.

2. The system of claim 1, wherein the pitch variation component generates the sets of the pitch modified fingerprint based on pitch shift resistance thresholds respectively associated with the reference audio-id fingerprints.

3. The system of claim 1, further comprising:

a merging component that identifies a pitch modified fingerprint, included in a set of the sets of pitch modified fingerprints, that has a high matching probability with the audio-id fingerprint relative to the reference audio-id fingerprints and other ones of the pitch modified fingerprints.

4. The system of claim 3, wherein the merging component identifies an audio match included in the subset of the set of potential audio matches that corresponds to the pitch modified fingerprint.

9. The system of claim 1, wherein the melody fingerprint comprises a first set of interest points that correspond to a melody of the audio track and the audio-id fingerprint comprises a second set of interest points that correspond to unique audio characteristics of the audio track, the reference melody fingerprints respectively comprise first sets of interest points that respectively correspond to melodies of the potential audio matches of the set, and the reference audio-id fingerprints respectively comprise second sets of interest points that respectively correspond to unique audio characteristics of the potential audio matches of the set.

5. A method, comprising:

using a processor to execute computer executable components stored on a computer readable medium to perform the following acts;

receiving a video sample;

generating a melody fingerprint based on an audio track of the video sample;

generating an audio-id fingerprint based on the audio track of the video sample

identifying a set of potential audio matches for the audio track based on comparing the melody fingerprint to reference melody fingerprints for the potential audio matches of the set;

identifying a set of reference audio-id fingerprints respectively associated with the potential audio matches of the set;

determining an estimated amount of pitch shift between the audio track and the reference audio-id fingerprints;

generating sets of pitch modified fingerprints for each of the reference audio-id fingerprints based on the estimated amount of pitch shift; and

identifying a subset of the set of the potential audio-id matches based on comparing the audio-id fingerprint to the reference audio-id fingerprints and the sets of the pitch modified fingerprints.

6. The method of claim 5, wherein generating the sets of the pitch modified fingerprints is based on pitch shift resistance thresholds respectively associated with the reference audio-id fingerprints.

7. The method of claim 5, further comprising:

identifying a pitch modified fingerprint, included in a set of the sets of pitch modified fingerprints, that has a high matching probability with the audio-id fingerprint relative to the reference audio-id fingerprints and other ones of the pitch modified fingerprints.

8. The method of claim 7, further comprising:

identifying an audio match included in the subset of the set of potential audio matches that corresponds to the pitch modified fingerprint.

10. The method of claim 5, wherein the melody fingerprint comprises a first set of interest points that correspond to a melody of the audio track and the audio-id fingerprint comprises a second set of interest points that correspond to unique audio characteristics of the audio track, the reference melody fingerprints respectively comprise first sets of interest points that respectively correspond to melodies of the potential audio matches of the set, and the reference audio-id fingerprints respectively comprise second sets of interest points that respectively correspond to unique audio characteristics of the potential audio matches of the set.

11. A tangible computer-readable storage medium comprising computer-readable instructions that, in response to execution, cause a computing system to perform operations, comprising:

receiving, from a device, a melody fingerprint and an audio-id fingerprint associated with an audio track;

identifying a set of potential audio matches for the audio track based on comparing the melody fingerprint to reference melody fingerprints for the potential audio matches of the set;

identifying a set of reference audio-id fingerprints respectively associated with the potential audio matches of the set;

determining an estimated amount of pitch shift between the audio track and the reference audio-id fingerprints;

generating sets of pitch modified fingerprints for each of the reference audio-id fingerprints based on the estimated amount of pitch shift; and

identifying a subset of the set of the potential audio-id matches based on comparing the audio-id fingerprint to the reference audio-id fingerprints and the sets of the pitch modified fingerprints.

12. The tangible computer-readable storage medium of claim 11, wherein generating the sets of the pitch modified fingerprints is based on pitch shift resistance thresholds respectively associated with the reference audio-id fingerprints.

13. The tangible computer-readable storage medium of claim 11, the operations further comprising:

identifying a pitch modified fingerprint, included in a set of the sets of pitch modified fingerprints, that has a high matching probability with the audio-id fingerprint relative to the reference audio-id fingerprints and other ones of the pitch modified fingerprints; and

identifying an audio match included in the subset of the set of potential audio matches that corresponds to the pitch modified fingerprint.

14. The tangible computer-readable storage medium of claim 11, the operations further comprising:

sending information identifying the audio match to the device.

15. The tangible computer-readable storage medium of claim 11, wherein the melody fingerprint comprises a first set of interest points that correspond to a melody of the audio track and the audio-id fingerprint comprises a second set of interest points that correspond to unique audio characteristics of the audio track, the reference melody fingerprints respectively comprise first sets of interest points that respectively correspond to melodies of the potential audio matches of the set, and the reference audio-id fingerprints respectively comprise second sets of interest points that respectively correspond to unique audio characteristics of the potential audio matches of the set.