# Simple beat detection algorithm for microcontroller

For the purpose of controlling DIY disco lighting, I'm looking at implementing beat detection in a microcontroller with limited computing power (i.e. Arduino Uno). While detecting all beats would be a plus (for one, it would allow measuring BPM, which could be used to adjust the light to the style of music), it's not absolutely needed for this application since light setting must be typically changed at a much lower frequency than the beat. So what I'm really looking at is to detect "conspicuous" events in the music (beat, resume after blank, etc.) to synchronise light change, but without 100% reliability.

The constraints are the following:

• Limited computing power is available. The Uno is based on a ATmega328 8-bit 16MHz MCU. If this is too constraining, I could consider moving to a Due, which is based on a AT91SAM3X8E, 32-bit 84MHz Cortex-M3 MCU.
• Noisy sound input. Ideally, the sound would be captured with a small, cheap microphone. I'm not sure yet what sampling rate can be achieved with the Uno. In any case, I expect the signal to be fairly noisy. If that proved the be required, I could possibly consider implementing a proper sound input (e.g. with the rugged audio shield) but I'd rather avoid that if possible because of the constraint of hooking the music playing devices (there may be several) to the light control electronics.
• Ideally, the algorithm would have a parameter to adjust sensitivity to beat event detection. That way, the sensitivity could be automatically increased to make sure events are detected even in bad conditions (low music volume, noise from conversations, etc.)

My questions are thus:

1. What (class of) algorithm would fit appropriately this application?
2. Is there any implementation available that could be readily integrated in a Arduino project?
• It sounds like you are satisfied with detecting events that might constitute beats rather than needing to actually do full fledged beat detection. Is that right? – Bjorn Roche Jun 10 '13 at 14:06
• Yes that's correct. The idea is to synchronise light change (color, animation scheme or even motion direction for motorised lights) to events in the music, to reinforce the effect of both music and light. As I said, BPM measurement would be a plus :) – abey Jun 10 '13 at 15:19
• How much analog electronics are you willing to build? – endolith Jun 11 '13 at 15:57
• @endolith: I'm not against doing some. I'm not against buying some either, if you know boards that would be suitable :) – abey Jun 11 '13 at 16:48
• @abey: Hmmm... Something that works well on computers is to auto-correlate the STFT in the time dimension only, which is equivalent to making a bandpass filter bank, autocorrelating each band, and then summing them together. I'm trying to think if there's a crude way to do something like this, like with a 3-band filter or something. – endolith Jun 11 '13 at 17:24

I did one very simple bpm calculation in matlab and maybe it can help you!

source

Steps:

1. Decompose the signal in six frequency bands (six level) using DWT

2. Extrac the Envelope from all sub-bands

• To make the Envelope Calculation do you need:
• Apply Full Wave Rectification
• Apply Low Pass Filter
• Apply Downsample
• Apply Mean Removal
3. Autocorrelation

I think you can accomplish this pretty easily:

• start with a low sample rate (simply because there is no reason for a high sample rate).
• use a low pass filter to eliminate signal above ~100 Hz. (You'll have to experiment to find the right cuttoff frequency).
• Create an envelope (optional). Doing this will help ensure that each beat looks like a single beat, rather than lots of separate hits.
• Threshold the signal -- anything above a certain level is a "beat", below is not. Adjusting the threshold is your sensitivity control.

For more on low pass filtering, see my blog entry on the audio eq: http://blog.bjornroche.com/2012/08/basic-audio-eqs.html

To create an envelope, you just need to take the absolute value (or square) of each sample, and do something like

$$y[i]=\lbrace\begin{matrix}x[i], x[i]>y[i-1]\\y[i-1]*.99,x[i]<=y[i-1]\end{matrix}$$

• With a low sampling rate, would you expect aliasing due to high frequency sounds (assuming no analog low pass on the mic)? Or this just doesn't happen in practice? – abey Jun 10 '13 at 18:17
• Hopefully your S/R converter takes care of this. If not, it is broken. – Bjorn Roche Jun 10 '13 at 19:09
• @abey: The answer is a bit vague on that point. Yes, you will want to band limit the signal appropriately for the 100 Hz sample rate. You would either do this by running your ADC at that rate, in which case you would need an analog filter somewhere ahead of the sampler, or you can sample at a higher rate and convert the rate digitally, in which case your sample rate converter should include the filtering required to enforce this condition. – Jason R Jun 10 '13 at 21:59
• Excuse me: in my comment I meant that your ADC should take care of this (I erroneously said S/R converter). Sorry. At any rate, when you get audio at a given sample rate, as a rule of thumb, the audio should already be filtered for you, whether by sample rate conversion or by ADC. If not, something is broken. – Bjorn Roche Jun 11 '13 at 1:00
• @BjornRoche: I don't think the ADC in a micro will take care of anything. It just samples the input when you tell it to, using successive approximation. You need an analog anti-aliasing filter if you want to prevent aliasing. – endolith Jun 11 '13 at 15:54