Find similar Music using FFT Spectrums

Question

I have been experimenting some weeks to find a way to match/find similar Songs in a Library containing different Genres of Music.

My first try was to Detect Features like Tempo or how much Bass there is in Songs to form groups, but I didnt get far with this approach (Volume Changes Based Beat Detection) since on about 20% of the Songs Beat dont have to be counted always, sometimes 1/2 or 1/3 of them and I couldnt implement that.

After some weeks of failed trying I got a new idea which is described later in this Post. Simply put it works by taking Spectrum Samples of Files, making something like an "Average Spectrum" of Files to compare them. The Idea behind was that for example Hardstyle has a lot more Bass than average Rock Music, I also verified this by looking at some Spectrums in Audacity.

• File 1: Take full File FFT Spectrums (2048 Sample Size atm,Amplitudes Log. scaled)
• Sum all Spectrum Arrays, take Averages of each Bin
• Do the same some other Files, store all Results
• Make List of FFT Values Differencies between File 1 and other Files
• Make Average of Differencies between File 1 and File X
• Sort Ascending by these Averages
• Songs with the Lowest "Difference Value" are considered to be Similar.

Can some of you who have good knowledge tell me if this would be the right/good way to implement my Idea?

Answer 1

What you are trying to do has been tried over and over by hundreds of researchers and there is quite a large body of work about this. Check the proceedings of the ISMIR conference. Even if it is not up to date, read Elias Pampalk's thesis : http://www.ofai.at/~elias.pampalk/publications/pampalk06thesis.pdf

To quickly orient you on the right track:

Music can be similar according to many dimensions: a) timbre/texture/genre ; b) rhythmic pattern ; c) melody/chord progression... and more! From your message it's not clear what you want to measure!

• If you are interested in a) the features you might want to look at are MFCC (Mel Frequency Cepstrum Coefficients), since they somehow capture the way human hearing works (frequency warping, log scale), since they are decorrelated (making modeling easier), and since they have lower dimensionality (13 coefficients vs 2048).
• If you are interested in b), look at a feature called "Fluctuation Patterns" (Pampalk, in short autocorrelation of the signal in the 0.1 .. 10 Hz range over a few bands) ; or Whitman's "Penny" features (FFT of the MFCC along the time axis).
• If you are interested in c), look at chromagrams. Start with Ellis' chromagram code (http://labrosa.ee.columbia.edu/matlab/chroma-ansyn/) then move up to Mauch's implementation if you need something more robust (http://isophonics.net/nnls-chroma).

That's for the features. Now you'll have to think of a better way to compare your songs once they have been represented as a sequence of those features. Computing pairwise differences between sequences is not very smart - eg: comparing a song and the same song offset by some silence will yield a difference while it is exactly the same! You'd rather compare the distribution of those features ; for example compute the mean / standard deviation of the features over song A and the mean / standard deviation of the features over song B and then take a probabilistic distance (KL, Bhattacharyya over those).

Last point, but which will matter later: computing the distance between a song and the rest of the corpus to find the nearest matches is quite inefficient. When dealing with large collections, techniques like LSH or Ball trees allow such nearest neighbors queries to be performed without explicit comparison with the whole corpus.

As an aside, tempo detection is an entirely different matter. If you want to look into it, best performance / accessibility paper on the topic is Ellis' Beat Tracking by Dynamic Programming. http://www.ee.columbia.edu/~dpwe/pubs/Ellis07-beattrack.pdf . It's incredibly simple but is close to state of the art algorithms.