FFT algorithm for beat detection?

Hey Guys,

So i've been playing around with everyone favorite topic: beat detection.

My goal is to detect when the "beat" hits (which seems to be a hard concept to define), and use that to kick of some bit of code (flash some lights, iterate on a loop, that sort of bit).

My first attempt was something similar to this (i think it's "amplitude based detection" or something like that, im no sound engineer): http://arduino.cc/forum/index.php?topic=50021.0

It worked ok sometimes, but was generally unreliable (doesn't catch all the beats or hits too often).

Now im fiddling around with FFT analysis, which some quick reading suggests might give me accurate results (someone please correct me if im wrong here). I used the FFT lib for arduino here: http://arduino.cc/forum/index.php/topic,37751.0.html

I got it all hooked up, and i can print to console a nice set of data. Now the fun part; reverse engineering the whole FFT bit and getting an algorithm to detect the beat.

Looking at the code, it seems that it will slice up a amp of the music, from 150 to 9615 Hz, into 64 item array which i get to play with.

I am hoping someone can point me at a good algorithm (or hopefully library) that can help me analyze this data for the elusive beat. My rough idea is to keep track of an average of the lower frequencies (this little guy is going to the club) to see when they spike, and use that as my indicator, though i think in principle thats just a software implementation of a low pass filter (which im cool with, im a CS guy, and the hardware version of that was scaring me).

Does anyone have any awesome sage insight into this? or at the very least, am i right in my understand of whats going on so far?

I did a lot with FFT in past but beat detection is something new to me :) Do you mean this? http://www.clear.rice.edu/elec301/Projects01/beat_sync/beatalgo.html I am a little bit in doubt the arduino paltform is the best hw for such signal processing. When talking mcu's use dspic33 instead, it has dsp stuff in so that could be doable then.. br /p.

Yeah, just like that in principle. I actually saw that in my research, though its matlab code so wasn't directly useful (and was way beyond me to port over).

Yeah an arduino definitely doesn't seem like the best place to be doing this, however its what i am currently working with. This is basically attached to a mobile arduino powered ball, lined with lasers, that currently shoots the lasers off in a variety of patterns. I would like to expand it to fire the patterns based on the music, and dont have enough time to scrap everything to go with a different processor (plus a teensy is the only thing that i found which will fit).

I'll admit, i dont know jack about music. When i was thinking of something to "respond to music", i jumped on beat (since thats what i would do as a human, flick a switch or something in time to a beat), but maybe thats not the best attribute to be basing my processing off of?

Some projects I did recently, Tears of Rainbow - rainfall, varying speed based on spectrum of music, VU meter, color organ. All with radix-4 FFT. http://coolarduino.wordpress.com/2012/06/21/tears-of-rainbow/ Sorry, no library, though wouldn't be an issue for software professional

I don’t think FFT is going to help you… I’ve seen BPM meters built into DJ mixers and DJ software. I don’t know how these work, but you might be able to find a “BPM” or “beat dector” algorithm somewhere. But, I doubt there is any software that’s as good as a human. :wink:

I’ll tell you what I’ve done and make some suggestions for improving-on what I’ve done…

I’ve done some crude beat detection for lighting effects, basically triggering off the “loudness” of the signal. In this application, I find that it’s more interesting if the lights respond to the changes in the actual music, rather than just blinking exactly to the “boring” 1-2-3-4 beat.

1. My signal runs through a [u]Peak Detector[/u] with a decay time of somewhere between 01. and 0.3 seconds.

2. I take several readings to get a peak and “average”. In my particular application (which has several different lighting-effect modes), my main loop takes a reading once per second and saves the last 20 readings (20 seconds) in an array. Once per second, I take a reading and find the new peak and the new average in the array. Since there is an analog peak detector it’s an “average of peaks” rather than a true average. Likewise, the peak in the array isn’t necessarily a true-peak… It’s just the biggest value in my array.

3. I get the maximum from the array, and that becomes my starting peak/beat reference. (For beat detection, you can actualy skip the whole array thing and pick any reading for your reference, because it’s going to self-adjust anyway.)

4. I wait about 1/4 of a second, and then read the input, looking for a level that’s greater or equal to my reference. I also start reducing the reference, in case the next beat is not quiet as strong as the previous one. When the input matches (or exceeds) the reference, I’ve found a beat.

5. I save the new input-trigger level as my new reference and start-over with the ~1/4 second delay before looking for the next beat. (In this mode, I am no longer using my 20-second array.)

Some suggestions for improvement…
**1.**You can try a low-pass filter (hardware). This may or may-not help, depending on the type of music… The beat/rhythm is not always dominated by bass.

2. Some kind of filter for the loudness-envelope (in hardware or software) That is… You don’t want to follow all of the “waves” that make-up the audio, but rather you want to follow the ups & downs of the moment-to-moment loudness. For example, if you open an audio file in an audio editor and look at a view for few seconds of audio, you’ll see the envelope. If you zoom-in to look at a few miliseconds of audio, you will see the detailed waveform and perhaps the individual samples.

So, you might have a ~100Hz audio filter to filter -out everything except the bass, plus a ~1/2Hz bandpass envelope filter to “tune-in” the beat.

The idea would be to “tune” the filter to magnify (or pass) envelope changes near the expected beat frequency (i.e. a few beats per second) and reduce (or block) envelope changes that are too-fast or too-slow for any reasonable beat.

The peak detector circuit actually makes it impossible to follow detailed the audio waveform, and I think you could make a modification to slow-down the attack to “tune” the detector. (The decay is already slow).

Following the loudness envelope, rather than the actual waveform (and possible doing FFT analysis), means that there is much less demand on the processor… You can take several ADC readings per second instead of many-thousands of readings per second.

3. Some sort of averaging or “fuzzy logic” to keep track of the on-going beat. For example, if you’ve been getting 1, 2, 3, 4… 1,2,3,4… and you get 1… 3, 4…, You’d probably want to fill-in the "missing’ (or weak) beat, just as a human would do.

The problem with using an FFT for beat detection is that you have to sample for long enough to actually get some beats in the FFT window. This pushes up the memory requirements and thus the processing requirements, unless you have a fairly heave low pass filter on the front end.

Then say you sample three beats worth of sound, any measure is going to be delayed. Then you have the problem of synchronising these beats with your action. Say you get a measure of 60 BPM, how do you hit the beat with this information?