Methods, Systems, and Media for Identifying Similar Songs Using Two-Dimensional Fourier Transform Magnitudes

• US 20130226957A1
• Filed: 02/27/2013
• Published: 08/29/2013
• Est. Priority Date: 02/27/2012
• Status: Abandoned Application

• Current Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Original Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Inventors: Ellis, Daniel P.W., Bertin-Mahieux, Thierry
• Application Number:
  US13/779,594
• Publication Number:
  US 20130226957A1
• Time in Patent Office: Days
• US Class Current: 707/769
• CPC Class Codes: G06F 16/433 using audio data
• CPC Class Codes: G06F 16/634 Query by example, e.g. query by humming
• CPC Class Codes: G10H 1/0008 Associated control or indicating means
• CPC Class Codes: G10H 2210/061 for extraction of musical phrases, isolation of musically relevant segments, e.g. musical thumbnail generation, or for temporal structure analysis of a musical piece, e.g. determination of the movement sequence of a musical work
• 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/076 for extraction of timing, tempo; Beat detection
• 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

Methods, systems, and media for identifying cover songs using two-dimensional Fourier transform magnitudes are provided. In some embodiments, methods for identifying a cover song from a query song are provided, the methods comprising: identifying a query song vector for the query song, wherein the query song vector is indicative of a two-dimensional Fourier transform based on the query song; identifying a plurality of reference song vectors that each correspond to one of a plurality of reference songs, wherein each of the plurality of reference song vectors is indicative of a two-dimensional Fourier transform created based on the corresponding reference song; determining a distance between the query song vector and each of the plurality of reference song vectors; generating an indication that a reference song corresponding to a reference song vector with a shortest distance to the query song vector is a similar song to the query song.

Claims

1. A method for identifying a similar song from a query song, the method comprising:

identifying, using at least one hardware processor, a query song vector for the query song, wherein the query song vector is indicative of a two-dimensional Fourier transform based on the query song;

identifying a plurality of reference song vectors that each correspond to one of a plurality of reference songs, wherein each of the plurality of reference song vectors is indicative of a two-dimensional Fourier transform created based on the corresponding reference song;

determining a distance between the query song vector and each of the plurality of reference song vectors;

generating an indication that a reference song corresponding to a reference song vector with a shortest distance to the query song vector is a similar song to the query song.

2. The method of claim 1, wherein identifying a vector further comprises:

generating a beat-synchronized chroma matrix of a plurality of chroma vectors each having a plurality of chroma bins for a portion of a song;

generating one or more two-dimensional Fourier transform patches based on the beat-synchronized chroma matrix;

calculating one or more principal components using a principal component analysis based on the one or more two-dimensional Fourier transform patches; and

calculating the vector based on values of the one or more principal components.

3. The method of claim 2, further comprising raising a value in each of the chroma bins by an exponent.

4. The method of claim 3, wherein the exponent is chosen from a range of 0.25 to 3.

5. The method of claim 2, wherein each of the one or more two-dimensional Fourier transform patches is based on a patch of the beat-synchronized chroma matrix of a particular length.

6. The method of claim 5, wherein the beat-synchronized chroma matrix patch has a size defined by the particular length and the number of chroma bins in each chroma vector and has a total number of chroma bins equal to the particular length times the number of chroma bins in each chroma vector, and wherein the two-dimensional Fourier transform patch has a number of components equal to the number of chroma bins in the beat-synchronized chroma patch and is the same size as the beat-synchronized chroma matrix patch upon which it is based.

7. The method of claim 6, further comprising:

determining magnitude components of the one or more two-dimensional Fourier transform patches and generating two-dimensional Fourier transform magnitude patches based on the magnitudes;

generating a median two-dimensional Fourier transform magnitude patch based on a median of the magnitude components at each position in the two-dimensional Fourier transform magnitude patches; and

wherein the principal component analysis is performed based on values of the median two-dimensional Fourier transform magnitude patch.

8. The method of claim 2, wherein the vector is based on a subset of the calculated principal components.

9. The method of claim 8, wherein the vector is based on a predetermined number of the first principal components, wherein the predetermined number is chosen from a range often to two hundred principal components.

10. The method of claim 1, wherein the distance is a Euclidian distance.

11. The method of claim 1, wherein identifying a vector further comprises receiving a vector from a server.

12. A system for identifying a similar song from a query song, the system comprising:

a hardware processor configured to;

identify a query song vector for the query song, wherein the query song vector is indicative of a two-dimensional Fourier transform based on the query song;

identify a plurality of reference song vectors that each correspond to one of a plurality of reference songs, wherein each of the plurality of reference song vectors is indicative of a two-dimensional Fourier transform created based on the corresponding reference song;

determine a distance between the query song vector and each of the plurality of reference song vectors;

generate an indication that a reference song corresponding to a reference song vector with a shortest distance to the query song vector is a similar song to the query song.

13. The system of claim 12, wherein the hardware processor is further configured to:

generate a beat-synchronized chroma matrix of a plurality of chroma vectors each, having a plurality of chroma bins for a portion of a song;

generate one or more two-dimensional Fourier transform patches based on the beat-synchronized chroma matrix;

calculate one or more principal components using a principal component analysis based on the one or more two-dimensional Fourier transform patches; and

calculate the vector based on values of the one or more principal components.

14. The system of claim 13, wherein the hardware processor is further configured to raise a value in each of the chroma bins by an exponent.

15. The system of claim 14, wherein the exponent is chosen from a range of 0.25 to 3.

16. The system of claim 13, wherein each, of the one or more two-dimensional Fourier transform patches is based on a patch of the beat-synchronized chroma matrix of a particular length.

17. The system of claim 16, wherein the beat-synchronized chroma matrix patch has a size defined by the particular length and the number of chroma bins in each chroma vector and has a total number of chroma bins equal to the particular length times the number of chroma bins in each chroma vector, and wherein the two-dimensional Fourier transform patch has a number of components equal to the number of chroma bins in the beat-synchronized chroma patch and is the same size as the beat-synchronized chroma matrix patch upon which it is based.

18. The system of claim 17, wherein the hardware processor is further configured to:

determine magnitude components of the one or more two-dimensional Fourier transform patches and generating two-dimensional Fourier transform magnitude patches based on the magnitudes;

generate a median two-dimensional Fourier transform magnitude patch based on a median of the magnitude components at each position in the two-dimensional Fourier transform magnitude patches; and

wherein the principal component analysis is performed based on values of the median two-dimensional Fourier transform magnitude patch.

19. The system of claim 13, wherein the vector is based on a subset of the calculated principal components.

20. The system of claim 19, wherein the vector is based on a predetermined number of the first principal components, wherein the predetermined number is chosen from a range of ten to two hundred principal components.

21. The system of claim 12, wherein the distance is a Euclidian distance.

22. The system of claim 12, wherein the hardware processor is further configured to receive a vector from a server.

23. A non-transitory computer readable medium containing computer executable instructions that, when executed by a processor, cause the processor to perform a method for identifying a similar song from a query song, the method comprising:

identifying a query song vector for the query song, wherein the query song vector is indicative of a two-dimensional Fourier transform based on the query song;

identifying a plurality of reference song vectors that each correspond to one of a plurality of reference songs, wherein each of the plurality of reference song vectors is indicative of a two-dimensional Fourier transform created based on the corresponding reference song;

determining a distance between the query song vector and each of the plurality of reference song vectors;

generating an indication that a reference song corresponding to a reference song vector with a shortest distance to the query song vector is a similar song to the query song.

24. The non-transitory computer-readable medium of claim 23, wherein identifying a vector further comprises:

generating a beat-synchronized chroma matrix of a plurality of chroma vectors each having a plurality of chroma bins for a portion of a song;

generating one or more two-dimensional Fourier transform patches based on the beat-synchronized chroma, matrix;

calculating one or more principal components using a principal component analysis based on the one or more two-dimensional Fourier transform, patches; and

calculating the vector based on values of the one or more principal components.

25. The non-transitory computer-readable medium of claim 24, wherein the method further comprises raising a value in each of the chroma bins by an exponent.

26. The non-transitory computer-readable medium of claim 25, wherein the exponent is chosen from a range of 0.25 to 3.

27. The non-transitory computer-readable medium of claim 24, wherein each of the one or more two-dimensional Fourier transform patches is based on a patch of the beat-synchronized chroma matrix of a particular length.

28. The non-transitory computer-readable medium of claim 27, wherein the beat-synchronized chroma matrix patch has a size defined by the particular length and the number of chroma bins in each chroma vector and has a total number of chroma bins equal to the particular length times the number of chroma bins in each chroma vector, and wherein the two-dimensional Fourier transform patch has a number of components equal to the number of chroma bins in the beat-synchronized chroma patch and is the same size as the beat-synchronized chroma matrix patch upon which it is based.

29. The non-transitory computer-readable medium of claim 28, wherein the method further comprises:

determining magnitude components of the one or more two-dimensional Fourier transform patches and generating two-dimensional Fourier transform magnitude patches based on the magnitudes;

generating a median two-dimensional Fourier transform magnitude patch based on a median of the magnitude components at each position in the two-dimensional Fourier transform magnitude patches; and

wherein the principal component analysis is performed based on values of the median two-dimensional Fourier transform magnitude patch.

30. The non-transitory computer-readable medium of claim 24, wherein the vector is based on a subset of the calculated principal components.

31. The non-transitory computer-readable medium of claim 30, wherein the vector is based on a predetermined number of the first principal components, wherein the predetermined number is chosen from a range often to two hundred principal components.

32. The non-transitory computer-readable medium of claim 23, wherein the distance is a Euclidian distance.

33. The non-transitory computer-readable medium of claim 23, wherein identifying a vector further comprises receiving a vector from a server.