standalone beat detection.

hey guys,

I’m brand new to the arduino community, so go easy on me =). While i’ve been waiting for my brand new arduino that i bought off of ebay to arrive, I’ve been dabbling with the arduino language, in particularly, beat detection algorithms. I did some searching on this forum (and elsewhere) and while i realized there are many techniques available for beat detection, not many of them are standalone (most of them require being tethered to a computer or require libraries). Below i’ve included the code that i plan on testing once my arduino arrives. In the meantime, i want to see what the rest of this community thinks, whether it’s functional or not, check the syntax and determine whether I’m on the right path.

UPDATED CODE (8/31/2010) (v2):

/*
      Standalone Music Beat Detector v1.0

      This code uses the the 'Simple sound energy algorithm #3' found at GameDev.com 
        (http://www.gamedev.net/reference/programming/features/beatdetection/) to detect high energy
        beats in audio.  This code can be adapted to fit various anolog sources for audio and outputs.
 
      The circuit:
      * Pin 2 will serve as an input for the analog sound data
        * Pin 3 is an undefined output pin (to be updated in later versions...)
        * Pin 4 is an undefined input button (to be updated in later versions...)
      * Pint 13 is an LED that will turn on when a beat is detected and off when not in use

      Created 3/8/2010
      By Michael Czigler
        
      Modified 3/8/2010
      Michael Czigler

      URL: (tutorial coming soon...)

        Frequently Asked Questions:
        
        1. Where did you get the numbers 43 and 256?
        
        I'll try to be brief.  First, 43 is not a number i came up with.  It's just the number of 
        local energy values that the source website for the algorithm chose to store in a history 
        buffer.  256, on the otherhand, is a number that corresponds to the fact that i am using a 
        lower sampling rate than suggested in algorithm source.  On their website, they use of 
        sampling rate of 44,032.  They analyze new data and calculate local energies in 1024 sample 
        chunks  (about 0.05 seconds), so:

                   44032/1024 = 43 bins/elements stored in the local energy history buffer

        From what i've read, the arduino is only able to sample a max rate 10000 samples/sec 
        (although i'm not sure if this is correct).    Rather than messing with the number of bins in 
        the history buffer or how how long they sample , i decided to just decrease the sampling rate. 

                            10,000/43 = 232.56 samples per local energy value


        Precision wasn't one of my biggest concerns (i don't think it matters if i sample slightly 
        longer than 0.05 seconds), so i decided to with 256 which is a power of 2 =D .

*/


int ledPin = 13; // light to indicate the detected beat in the song (temporary)
int inputPin = 2; // incoming song data
int outputPin = 3; // not yet included in the code, but will be used to detect the current
int buttonPin = 4; // not yet included in code, but will serve as a start/stop button for the beat detector

const int hist_length = 43; // length of the energy history buffer
float history[hist_length]; // buffer for the previous 43 computed local energies, shifts out oldest energy 
                            // value and shift in the newest with every iteration
int i;
int index = 0; // index of the history buffer
float e_local; // local energy for the sampled incoming signal
float variance; // variance of the local energy history buffer and the newest local energy value
float c; // dynamic threshold constant
float avg = 0; // average of the local energy history buffer

void setup() 
{
  pinMode(ledPin, OUTPUT); 
  pinMode(outputPin, OUTPUT);
  pinMode(inputPin, INPUT);
  pinMode(buttonPin, INPUT);
}

void loop() 
{ 

  // Collect Data from input pin and the calculate local energy value from the newest 256 point 
  // data stream
  e_local = 0;
  for (i = 0; i < 256; i++){  
    e_local += abs(analogRead(inputPin))*abs(analogRead(inputPin))y  ;
  }
  // Calculate variance of the energies,
  for (i = 0; i < hist_length; i++){
    variance += ((history[i]-e_local)*(history[i]-e_local))/hist_length;
  }
  // determine constant, then compare to average energy of the history. if newest local energy > avg*c, 
  // then turn on light to indicate a detected beat 
  c = (-0.0025714*variance)+1.5142857;
  if (e_local-c*avg > 0)
  {
    digitalWrite(ledPin, HIGH);
    delay(50); // not sure what a good value for this is... ?
    digitalWrite(ledPin, LOW);
  }
  // Remove oldest history and shift in the newest, calculate average of history buffer energys
  history[index] = e_local;
  index = (index + 1) % hist_length;
  avg = (avg*hist_length - history[index]*history[index] + e_local*e_local)/hist_length;
}

like i said before, THIS CODE HAS NOT BEEN TESTED. I verified that i could compile and that is all.

Thanks in advance.

The output from analogRead is an integer value. Storing ints in float variables is a waste of space.

Using the pow function to raise a value to the power of 2 is a waste of resources. The function expects a float argument, and isn’t optimized for squaring a number. A simple buffer_buffer will be much faster. Since the square of a number is always positive, using the abs function is not needed._
i = i + 1 in a for loop, as well as most other cases, is usually written i++.
delay(5); will keep the LED on for 0.005 seconds. Don’t blink. You’ll miss it.
43 is used a lot throughout the code. What does this magic number mean? What happens if you want to change it? More common would be to use #define:
_
*_ <em>*#define WHATEVER43MEANS 43*</em> _**_
Then, replace 43 every (except this line) with WHATEVER43MEANS.
This is what I noticed on first looking at the code. I have no idea what this is trying to accomplish, and there are not enough comments to help me understand it (especially at the top, where you would define the purpose of the program).

Sorry for the lack of detail. I was in the middle of a class =). also, this is my first arduino code and first time posting on a forum so i expected it to be pret bad. Anyways, the algorithm that i was attempting to implement was the following:

http://www.gamedev.net/reference/programming/features/beatdetection/

The steps can be summarized as follows:

  1. Collects 0.05seconds worth of data (~250 data points)
  • Compute the instant sound energy
  • Compute the average local energy with the sound energy history buffer (which includes local energy values for a total of ~1 second of time)[/color]
  • Compute the variance ‘V’ of the energies
  • Compute the ‘C’ constant using a linear degression of ‘C’ with ‘V’
  • Shift the sound energy history buffer (E) of 1 index to the right. We make room for the new energy value and flush the oldest.
  • Pile in the new energy value
  • Compare ‘e’ to ‘C*’, if superior we have a beat!

Not sure if this made sense, but i basically copied and pasted exactly what the the website said.

Thanks again paul for the criticism. I’ll repost the code as soon as i make the needed changes.

let’s see if this helps. So i added TONS of comments to hopefully clear up the specific purpose of this project. The wording may not be very precise, but i’ll be working on improving it. I’ve also made all the changes Paul suggested (thanks again! ;D).

/*
      Standalone Music Beat Detector v1.0

      This code uses the the 'Simple sound energy algorithm #3' found at GameDev.com 
        (http://www.gamedev.net/reference/programming/features/beatdetection/) to detect high energy
        beats in audio.  This code can be adapted to fit various anolog sources for audio.

      The circuit:
      * Pin 2 will serve as an input for the analog sound data
        * Pin 3 is an undefined output pin (to be updated in later versions...)
        * Pin 4 is an undefined input button (to be updated in later versions...)
      * Pint 13 is an LED that will turn on when a beat is detected and off when not in use

      Created 3/8/2010
      By Michael Czigler
        
      Modified 3/8/2010
      Michael Czigler

      URL: (tutorial coming soon...)

*/


int ledPin = 13; // light to indicate the detected beat in the song (temporary)
int inputPin = 2; // incoming song data
int outputPin = 3; // not yet included in the code, but will be used to detect the current
int buttonPin = 4; // not yet included in code, but will serve as a start/stop button for the beat detector

int buffer[256]; // buffer for the incoming data, refreshed every iteration through the program, size is ~0.05seconds of data
float history[43]; // buffer for the previous 43 computed local energies, shifts out oldest energy value and shift in the newest with every iteration
int i;
int index = 0; // index of the energy history buffer, (1-43)
float e_local; // local energy for the sampled incoming signal
float variance; // variance of the local energy history buffer and the newest local energy value
float c; // dynamic threshold constant
float avg = 0; // average of the local energy history buffer
const int hist_length = 43; // length of the energy history buffer

void setup() 
{
  pinMode(ledPin, OUTPUT); 
  pinMode(outputPin, OUTPUT);
  pinMode(inputPin, INPUT);
  pinMode(buttonPin, INPUT);
}

void loop() 
{ 

  // Collect Data from input pin and the calculate local energy value from the newest data stream
  e_local = 0;
  for (i = 0; i < 256; i++){ 
    buffer[i] = analogRead(inputPin); 
    e_local = e_local + pow(abs(buffer[i]),2);
  }
  // Calculate variance of the energies,
  for (i = 0; i < hist_length; i++){
    variance = variance + (pow((history[i]-e_local),2))/hist_length;
  }
  // determine constant, then compare to average energy of the history. if newest local energy > avg*c, then turn on light to indicate a detected beat 
  c = (-0.0025714*variance)+1.5142857;
  if (e_local-c*avg > 0)
  {
    digitalWrite(ledPin, HIGH);
    delay(50); // not sure what a good value for this is... ?
    digitalWrite(ledPin, LOW);
  }
  // Remove oldest history and shift in the newest, calculate average of history buffer energys
  history[index] = e_local;
  index = (index + 1) % hist_length;
  avg = (avg*hist_length - pow(history[index],2) + pow(e_local,2))/hist_length;
}

My Specific Questions:
Does it work?
Am i clear enough defining variables, inputs, outputs, etc?
Are there ways to improve the execution time of this code?
Is my sampling size in too small?

I’ve also made all the changes Paul suggested

Well, maybe not ALL of them…

    e_local = e_local + pow(abs(buffer[i]),2);
    variance = variance + (pow((history[i]-e_local),2))/hist_length;

Does it work?

Only one way to really know. Upload it and see.

Am i clear enough defining variables, inputs, outputs, etc?

Mostly. The reason for using 43 as the size of the history buffer isn’t clear to me. It might be, for someone familiar with the algorithm. If so, then there’s no problem. If not, the reason for 43 should be explained in the comments.

Are there ways to improve the execution time of this code?

Yes. See above.

Is my sampling size in too small?

Only you can answer that, after some testing. If you get false positives, it probably is. If you miss some beats, it probably is.

The problem is that you are limited in the number of values that you can store. One way to improve that is to note that although you store a bunch of values in buffer, you only actually ever use the last value stored. This means that you don’t really need to store them.

Thanks again PaulS! I just have one comment about what you said…

Mostly. The reason for using 43 as the size of the history buffer isn’t clear to me. It might be, for someone familiar with the algorithm. If so, then there’s no problem. If not, the reason for 43 should be explained in the comments

I’ll try to be brief. First, 43 is not a number i came up with. It’s just the number of local energy values that the source website for the algorithm chose to store in a history buffer. 256, on the otherhand, is a number that corresponds to the fact that i am using a lower sampling rate than suggested in algorithm source. On their website, they use of sampling rate of 44,032. They analyze new data and calculate local energies in 1024 sample chunks (about 0.05 seconds), so:
44032/1024 = 43 bins/elements stored in the local energy history buffer
From what i’ve read, the arduino is only able to sample a max rate 10000 samples/sec (although i’m not sure if this is correct). Rather than messing with the number of bins in the history buffer or how how long they sample , i decided to just decrease the sampling rate.
10,000/43 = 232.56 samples per local energy value
Precision wasn’t one of my biggest concerns (i don’t think it matters if i sample slightly longer than 0.05 seconds), so i decided to with 256 which is a power of 2 ;D.
Did any of what i just said make sense? :o I tend not too…

Anyways, I’ll edit the very first post with the updated script and comments so people don’t have to keep scrolling to the bottom. I know a lot of the bugs won’t get worked until i test it, but right now i’m still waiting for my Arduino to arrive, so i guess all i can really do is keep optimizing it. My biggest concern is making sure that there isn’t a significant lag time between sampling and performing calculations.

I’ll probably post the results sometime before the end of this week.

Did any of what i just said make sense?

Sure it does. How much of that will YOU remember 6 months from now, when you want to revise the code?

Comments do not translate into used memory on the Arduino, so use lots of them.

As for as the number of samples to take, you are not limited to what will fit in the Arduino's memory since, as I mentioned, you never use the stored values so there is no reason to store them.

You could use millis() to sample for a fixed period of time (50 milliseconds?) rather than a specific number of samples.

You could use millis() to sample for a fixed period of time (50 milliseconds?) rather than a specific number of samples.

I thought about doing this but i ran into two problems. First, i couldn't find a quick and easy way of doing this. I wanted to minimize the number of variables and size of my code. i figured i would have to use a float var to keep track of the sampling time frame instead of an int var for just collecting specific number of data points, so i went with the int var for the smaller footprint. Second, sampling time does not always translate exactly to equal sample sizes. This could potentially throw off my local energy values (although i don't think that it's significant enough to matter).

also, i just changed to the code at the top of the page to show my current progress. I'm still trying to figure out how i could eliminate the use of a for loop for calculating the history buffer variances.... but besides that, the code looks ALOT better than what i had started out with :slight_smile:

i figured i would have to use a float var to keep track of the sampling time frame

All times are measured in milliseconds (millis()) or microseconds (micros()). Both are integer values (unsigned long, to be specific).

The number 43 still occurs two places outside of the comments. Move this line

const int hist_length = 43; // length of the energy history buffer

before this line

float history[43]; // buffer for the previous 43 computed local energies, shifts out oldest energy value and shift in the newest with every iteration

Then, change the 43 in the brackets to hist_length.

Comments can be split onto multiple lines, to avoid the need to scroll back and forth as well as up and down.

Still can get rid of pow, huh?

Still can get rid of pow, huh?

AHhhhhhhhh, i don't know how i missed this the first time you when mentioned it! I fixed it this time! :smiley: (I updated the code in the first post)

As for time v. # of samples thing, i'll mess with it once my arduino arrives

For the 100th time, thanks again PaulS! :slight_smile: