Intervalgram representation of audio for melody recognition

• US 8,158,870 B2
• Filed: 06/29/2010
• Issued: 04/17/2012
• Est. Priority Date: 06/29/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Lyon, Richard F., Walters, Thomas C., Ross, David
• Primary Examiner(s): Qin, Jianchun
• Application Number:
  US12/826,623
• Publication Number:
  US 20110314995A1
• Time in Patent Office: 658 Days
• Field of Search: 846/09, 846/10, 379/88.1
• US Class Current: 84/609
• CPC Class Codes: G06F 16/683 using metadata automatically derived from the content
• CPC Class Codes: G10H 1/0008 Associated control or indicating means
• CPC Class Codes: G10H 1/20 for transposition
• CPC Class Codes: G10H 2210/066 for pitch analysis as part of wider processing for musical purposes, e.g. transcription, musical performance evaluation; Pitch recognition, e.g. in polyphonic sounds; Estimation or use of missing fundamental
• CPC Class Codes: G10H 2210/081 for automatic key or tonality recognition, e.g. using musical rules or a knowledge base
• CPC Class Codes: G10H 2240/075 Musical metadata derived from musical analysis or for use in electrophonic musical instruments
• CPC Class Codes: G10H 2240/135 Library retrieval index, i.e. using an indexing scheme to efficiently retrieve a music piece
• 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

Abstract

A system, method, and computer readable storage medium generates an audio fingerprint for an input audio clip that is robust to differences in key, instrumentation, and other performance variations. The audio fingerprint includes a sequence of intervalgrams that represent a melody in an audio clip according pitch intervals between different time points in the audio clip. The fingerprint for an input audio clip can be compared to a set of reference fingerprints in a reference database to determine a matching reference audio clip.

Claims

1. A computer-implemented method for matching audio clips, the method executed by a computer system, and comprising:

receiving an audio chromagram representing an input audio clip, the audio chromagram comprising a sequence of vectors, each vector in the audio chromagram corresponding to a different time point of the input audio clip, and each vector representing a distribution of audio pitches at the corresponding time point of the input audio clip;

selecting a sampling of different reference time points within the audio chromagram;

for each of the selected reference time points, generating a chroma block having a plurality of vectors, each of the plurality of vectors in the chroma block corresponding to a different time sub-period of the input audio clip, and each vector representing a weighted average of distributions of audio pitches within the corresponding time sub-period;

for each of the selected reference time points, generating a reference vector representing a reference distribution of pitches for the selected reference time point in the audio chromagram;

applying a circular cross-correlation of the vectors of each chroma block against the reference vector to produce a sequence of intervalgram blocks for the input audio clip, wherein the sequence of intervalgram blocks comprises an intervalgram representation for the input audio clip, each intervalgram block associated with a different time period within the input audio clip, and each intervalgram block representing a distribution of pitch intervals occurring between different sub-periods within the time period;

comparing the intervalgram representation for the input audio clip to stored intervalgram representations corresponding to reference audio clips in a reference database;

selecting a reference audio clip from the reference database having an intervalgram representation best matching the intervalgram representation for the input audio clip; and

generating a recognition result indicative of the selected reference audio clip.

2. The method of claim 1, wherein generating the chroma block comprises:

extracting a block of chroma vectors from the chromagram, the block of chroma vectors corresponding to one of the different time periods within the input audio clip; and

averaging the chroma vectors in the block of chroma vectors across time into a number of time bins, each time bin corresponding to a different time sub-period in the chroma block.

3. The method of claim 2, wherein averaging the chroma vectors in the block of chroma vectors comprises applying a non-uniform sub-sampling such that time bins near the reference time are narrower than time bins at the edges of the block of chroma vectors.

4. The method of claim 1, wherein generating the reference vector comprises computing a weighted average of a plurality of chroma vectors within a limited time range surrounding the reference time.

5. The method of claim 4, wherein computing the weighted average of the plurality of chroma vectors comprises applying a triangle weighting function to the plurality of chroma vectors.

6. The method of claim 1, further comprising generating the audio chromagram, wherein generating the audio chromagram comprises:

receiving a pitchogram comprising a sequence of vectors, each vector corresponding to a different time point in the input audio clip, and each vector in the pitchogram representing a distribution of pitches at the time point in the input audio clip; and

quantizing and wrapping the distribution of pitches in of the sequence of vectors in the pitchogram into a number of chroma bins according to a weighted smoothing function, wherein each chroma bin represents a pitch independent of octave.

7. The method of claim 1, further comprising storing the intervalgram representation for the input audio clip to the reference database as an additional reference fingerprint.

8. A computer-implemented method for generating a reference database of audio fingerprints representative of melodies in a corresponding set of reference audio clips, the method executed by a computer system, and comprising:

receiving a reference audio clip;

generating an audio chromagram representing the reference audio clip, the audio chromagram comprising a sequence of vectors, each vector in them audio chromagram corresponding to a different time point of the reference audio clip, and each vector representing a distribution of audio pitches at the corresponding time point of the reference audio clip;

selecting a set of different reference time points within the audio chromagram;

for each of the selected reference time points, generating a chroma block having a plurality of vectors, each of the plurality of vectors in the chroma block corresponding to a different time sub-period of the reference audio clip, and each vector representing a weighted average of distributions of audio pitches within the corresponding time sub-period;

for each of the selected reference time points, generating a reference vector representing a reference distribution of pitches for the selected reference time point in the audio chromagram;

applying a circular cross-correlation of the vectors of each chroma block against the reference vector to produce a sequence of intervalgram blocks for the reference audio clip, wherein the sequence of intervalgram blocks comprises an intervalgram representation for the reference audio clip, each intervalgram block associated with a different time period within the reference audio clip, and each intervalgram block representing a distribution of pitch intervals occurring between different sub-periods within the time period; and

storing the intervalgram representation as a reference fingerprint in the reference database.

9. The method of claim 8, wherein storing the intervalgram representation as the reference fingerprint in the reference database comprises:

indexing the reference fingerprint according to features of the reference fingerprint.

10. A non-transitory computer readable storage medium storing computer-executable program instructions for matching audio clips, the program instructions when executed cause a processor to perform steps of:

receiving an audio chromagram representing an input audio clip, the audio chromagram comprising a sequence of vectors, each vector in the audio chromagram corresponding to a different time point of the input audio clip, and each vector representing a distribution of audio pitches at the corresponding time point of the input audio clip;

selecting a sampling of different reference time points within the audio chromagram;

for each of the selected reference time points, generating a chroma block having a plurality of vectors, each of the plurality of vectors in the chroma block corresponding to a different time sub-period of the input audio clip, and each vector representing a weighted average of distributions of audio pitches within the corresponding time sub-period;

for each of the selected reference time points, generating a reference vector representing a reference distribution of pitches for the selected reference time point in the audio chromagram;

applying a circular cross-correlation of the vectors of each chroma block against the reference vector to produce a sequence of intervalgram blocks for the input audio clip, wherein the sequence of intervalgram blocks comprises an intervalgram representation for the input audio clip, each intervalgram block associated with a different time period within the input audio clip, and each intervalgram block representing a distribution of pitch intervals occurring between different sub-periods within the time period;

comparing the intervalgram representation for the input audio clip to stored intervalgram representations corresponding to reference audio clips in a reference database;

selecting a reference audio clip from the reference database having an intervalgram representation best matching the intervalgram representation for the input audio clip; and

generating a recognition result indicative of the selected reference audio clip.

11. The computer-readable storage medium of claim 10, wherein generating the chroma block comprises:

extracting a block of chroma vectors from the chromagram, the block of chroma vectors corresponding to one of the different time periods within the input audio clip; and

averaging the chroma vectors in the block of chroma vectors across time into a number of time bins, each time bin corresponding to a different time sub-period in the chroma block.

12. The computer-readable storage medium of claim 11, wherein averaging the chroma vectors in the block of chroma vectors comprises applying a non-uniform sub-sampling such that time bins near the reference time are narrower than time bins at the edges of the block of chroma vectors.

13. The computer-readable storage medium of claim 10, wherein generating the reference vector comprises computing a weighted average of a plurality of chroma vectors within a limited time range surrounding the reference time.

14. The computer-readable storage medium of claim 13, wherein computing the weighted average of the plurality of chroma vectors comprises applying a triangle weighting function to the plurality of chroma vectors.

15. The computer-readable storage medium of claim 10, further comprising program instructions for generating the audio chromagram, wherein generating the audio chromagram comprises:

receiving a pitchogram comprising a sequence of vectors, each of the vectors corresponding to a different time point in the input audio clip, and each vector in the pitchogram representing a distribution of pitches at the time point in the input audio clip; and

quantizing and wrapping the distribution of pitches in of the sequence of vectors in the pitchogram into a number of chroma bins according to a weighted smoothing function, wherein each chroma bin represents a pitch independent of octave.

16. The computer-readable storage medium 10, further comprising storing the intervalgram representation for the input audio clip to the reference database as an additional reference fingerprint.

17. A non-transitory computer readable storage medium storing computer-executable program instructions for generating a reference database of audio fingerprints representative of melodies in a corresponding set of reference audio clip, the program instructions when executed cause a processor to perform steps of:

receiving a reference audio clip;

generating an audio chromagram representing the reference audio clip, the audio chromagram comprising a sequence of vectors, each vector in them audio chromagram corresponding to a different time point of the reference audio clip, and each vector representing a distribution of audio pitches at the corresponding time point of the reference audio clip;

selecting a set of different reference time points within the audio chromagram;

for each of the selected reference time points, generating a chroma block having a plurality of vectors, each of the plurality of vectors in the chroma block corresponding to a different time sub-period of the reference audio clip, and each vector representing a weighted average of distributions of audio pitches within the corresponding time sub-period;

for each of the selected reference time points, generating a reference vector representing a reference distribution of pitches for the selected reference time point in the audio chromagram;

applying a circular cross-correlation of the vectors of each chroma block against the reference vector to produce a sequence of intervalgram blocks for the reference audio clip, wherein the sequence of intervalgram blocks comprises an intervalgram representation for the reference audio clip, each intervalgram block associated with a different time period within the reference audio clip, and each intervalgram block representing a distribution of pitch intervals occurring between different sub-periods within the time period; and

storing the intervalgram representation as a reference fingerprint in the reference database.

18. The computer-readable storage medium of claim 17, wherein storing the intervalgram representation as the reference fingerprint in the reference database comprises:

indexing the reference fingerprint according to features of the reference fingerprint.