Beat Matching Algorithm

Question

I've recently begun trying to create a mobile app (iOS/Android) that will automatically beat match (http://en.wikipedia.org/wiki/Beatmatching) two songs.

I know that this exists out there, and there have been others who have had some success, but I'm running into issues related to the accuracy of the players.

Specifically, I run into "sync" issues where the "beats" don't line up. The various methods used to date are:

• Calculate the BPM in advance, identify a "beat" (using something like sonicapi.com), and trying to line up appropriately, and begin a mix in with its playback rate adjusted (tempo adjustment)

• Utilizing a bunch of meta data to trigger specific starts and stops

What does NOT work:

• Leveraging echonest's API (it beat matches on the server, we want to do it on the client)
• Something like pydub (does not do it in realtime)

Who uses this algorithm today:

• iwebdj

• Traktor

Does anyone have any suggestions on how to solve this problem? I've seen lots of people do it, but doing it in real time on a mobile device seems to be an issue.

Answer 1

There are lots of methods for solving this problem, some of which work better than others. Matthew Davies has published several papers on the matter, among many others. Glancing at this article seems to break down some of the steps necessary for doing this. I built a beat tracker in Matlab (unfortunately...) with a fellow student and our goal was to create an outro/intro between 2 songs so that the tempo was seamless between them. We wanted to do this for songs that varied in BPM by a small amount (+-7 or so BPM between the two). Our method went sort of like this:

1. Find two songs in our database that had overlapping 'key center'. So lets say 2 songs, both in Am.

2. Find this particular overlap of key centers between the two. Say 30 seconds into song 1 and 60 seconds into song 2

3. Now create a beat map, using an onset-detection algorithm with peak picking; Also, this was helpful for us.

4. Pick the first 'beat' for each track, and overlap the two tracks at that point. Now, since they are slightly different BPM from each other, the beats won't really line up with each other.

5. From this, we created a sort of map that gave us the sample offsets between beats of song A and beats of song B. From this, we wanted to be able to time-stretch the fade-in region of song B so that each one of its onsets (beats in this case) lined up at the correct sample index as the onsets from song A, over ITS fade-out region. So for example, if onset 2 from song B was shown as 5,000 samples ahead of onset 2 from song A, we simply stretched that 5,000 sample region so that onset 2 matched exactly between both songs.

This seems like it would sound weird, but it actually sounded pretty good. Although this was done entirely offline in Matlab, I am also looking for a way to do this in real-time in a mobile app. Not entirely sure about libraries you can use for this in Android world, but I imagine that it would be most efficient in C++.

A couple of libraries I have come across would be good for prototyping something, or at least studying the source code to get a better understanding of how you could do this in a mobile app:

Essentia (great community, open-source) Aubio (also seems to be maintained pretty well, open-source)

Additional things to read up on for doing this kind of stuff in iOS land: vDSP Programming guide This article may also help I came across this project that is doing some beat detection. Although it seems pretty out-dated unfortunately, it may offer some additional insights.

Unfortunately it isn't as simple as just 'pressing play' at the same time to align beats, unless you are assuming very specific aspects about them (exact tempos, etc.).

If you reallllly have some time on your hands, you should check out Tristan Jehan's (founder of Echonest) thesis; it is jam packed with algorithms and methods for beat detection, etc.