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:


What (class of) algorithm would fit appropriately this application?
Is there any implementation available that could be readily integrated in a Arduino project?
I did one very simple bpm calculation in matlab and maybe it can help you!

source

Steps:


Decompose the signal in six frequency bands (six level) using DWT
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


Autocorrelation