Crowdsourcing Algorithms
Looking for information in the noise: a contest to crowdsource a better algorithm for accelerometer data.
With the invention of triple-axis accelerometers and open source libraries, it’s becoming pretty easy to gather data. I can generate a tremendous amount of data using an Arduino and an OpenLog to log it. The problem is always the same: What do you do with all that data?
So here’s a real world example: A few years ago I built a Speed Bag Counter. For those who don’t frequent a boxing gym, the speed bag is the teardrop-shaped bag that boxers hit in quick unison to strengthen their shoulders and develop their hand-eye coordination. A standard round is three minutes, and because of the speed at which the bag bounces it’s pretty much impossible to keep count. I decided to build a counter so I could keep track of my improvement over time. Just hook up an accelerometer and a display to an Arduino, and you’re good to go, right? As they say, the devil’s in the algorithm.
Pictured above is one of the datasets I captured when I was trying to validate the system. Real-world data is noisy.
But wait, we should be able to see periodicity and other key traits, right?
Unfortunately, even with logging at 500Hz, the data is not self-explanatory. With this data I did my best to try to create a system that could count hits.
/*
BeatBag - A Speed Bag Counter
Nathan Seidle
SparkFun Electronics
2/23/2013
License: This code is public domain but you buy me a beer if you use this and we meet someday (Beerware license).
BeatBag is a speed bag counter that uses an accelerometer to counts the number hits.
It's easily installed ontop of speed bag platform only needing an accelerometer attached to the top of platform.
You don't have to alter the hitting surface or change out the swivel.
I combine X/Y/Z into one vector and look only at the magnitude.
I use a fourth order filter to see the impacts (accelerometer peaks) from the speed bag. It works pretty well.
It's very reproducible but I'm not entirely sure how accurate it is. I can detect both bag hits (forward/backward) then
I divide by two to get the number displayed to the user.
I arrived at the peak detection algorithm using video and raw data recordings. After a fourth filtering I could glean the
peaks. There is probably a much better way to do the math on the peak detection but it's not one of my strength.
Hardware setup:
5V from wall supply goes into barrel jack on Redboard. Trace cut to diode.
RedBoard barel jack is wired to power switch then to Vin diode
Display gets power from Vin and data from I2C pins
Vcc/Gnd from RedBoard goes into Bread Board Power supply that supplies 3.3V to accelerometer. Future
versions should get power from 3.3V rail on RedBoard.
MMA8452 Breakout ------------ Arduino
3.3V --------------------- 3.3V
SDA(yellow) -------^^(330)^^------- A4
SCL(blue) -------^^(330)^^------- A5
GND ---------------------- GND
The MMA8452 is 3.3V so we recommend using 330 or 1k resistors between a 5V Arduino and the MMA8452 breakout.
The MMA8452 has built in pull-up resistors for I2C so you do not need additional pull-ups.
3/2/2013 - Got data from Hugo and myself, 3 rounds, on 2g setting. Very noisy but mostly worked
12/19/15 - Segment burned out. Power down display after 10 minutes of non-use.
Use I2C, see if we can avoid the 'multiply by 10' display problem.
1/23/16 - Accel not reliable. Because the display is now also on the I2C the pull-up resistors on the accel where
not enough. Swapped out to new accel. Added 100 ohm inline resistors to accel and 4.7k resistors from SDA/SCL to 5V.
Reinforced connection from accel to RedBoard.
*/
#include <avr/wdt.h> //We need watch dog for this program
#include <Wire.h> // Used for I2C
#define DISPLAY_ADDRESS 0x71 //I2C address of OpenSegment display
int hitCounter = 0; //Keeps track of the number of hits
const int resetButton = 6; //Button that resets the display and counter
const int LED = 13; //Status LED on D3
long lastPrint; //Used for printing updates every second
boolean displayOn; //Used to track if display is turned off or not
//Used in the new algorithm
float lastMagnitude = 0;
float lastFirstPass = 0;
float lastSecondPass = 0;
float lastThirdPass = 0;
long lastHitTime = 0;
int secondsCounter = 0;
//This was found using a spreadsheet to view raw data and filter it
const float WEIGHT = 0.9;
//This was found using a spreadsheet to view raw data and filter it
const int MIN_MAGNITUDE_THRESHOLD = 1000; //350 is good
//This is the minimum number of ms between possible hits
//We use this to filter out peaks that are too close together
const int MIN_TIME_BETWEEN_HITS = 90; //100 works well
//This is the number of miliseconds before we turn off the display
long TIME_TO_DISPLAY_OFF = 60L * 1000L * 5L; //5 minutes of no use
int DEFAULT_BRIGHTNESS = 50; //50% brightness to avoid burning out segments after 3 years of use
unsigned long currentTime; //Used for millis checking
void setup()
{
wdt_reset(); //Pet the dog
wdt_disable(); //We don't want the watchdog during init
pinMode(resetButton, INPUT_PULLUP);
pinMode(LED, OUTPUT);
//By default .begin() will set I2C SCL to Standard Speed mode of 100kHz
Wire.setClock(400000); //Optional - set I2C SCL to High Speed Mode of 400kHz
Wire.begin(); //Join the bus as a master
Serial.begin(115200);
Serial.println("Speed Bag Counter");
initDisplay();
clearDisplay();
Wire.beginTransmission(DISPLAY_ADDRESS);
Wire.print("Accl"); //Display an error until accel comes online
Wire.endTransmission();
while(!initMMA8452()) //Test and intialize the MMA8452
; //Do nothing
clearDisplay();
Wire.beginTransmission(DISPLAY_ADDRESS);
Wire.print("0000");
Wire.endTransmission();
lastPrint = millis();
lastHitTime = millis();
wdt_enable(WDTO_250MS); //Unleash the beast
}
void loop()
{
wdt_reset(); //Pet the dog
currentTime = millis();
if ((unsigned long)(currentTime - lastPrint) >= 1000)
{
if (digitalRead(LED) == LOW)
digitalWrite(LED, HIGH);
else
digitalWrite(LED, LOW);
lastPrint = millis();
}
//See if we should power down the display due to inactivity
if (displayOn == true)
{
currentTime = millis();
if ((unsigned long)(currentTime - lastHitTime) >= TIME_TO_DISPLAY_OFF)
{
Serial.println("Power save");
hitCounter = 0; //Reset the count
clearDisplay(); //Clear to save power
displayOn = false;
}
}
//Check the accelerometer
float currentMagnitude = getAccelData();
//Send this value through four (yes four) high pass filters
float firstPass = currentMagnitude - (lastMagnitude * WEIGHT) - (currentMagnitude * (1 - WEIGHT));
lastMagnitude = currentMagnitude; //Remember this for next time around
float secondPass = firstPass - (lastFirstPass * WEIGHT) - (firstPass * (1 - WEIGHT));
lastFirstPass = firstPass; //Remember this for next time around
float thirdPass = secondPass - (lastSecondPass * WEIGHT) - (secondPass * (1 - WEIGHT));
lastSecondPass = secondPass; //Remember this for next time around
float fourthPass = thirdPass - (lastThirdPass * WEIGHT) - (thirdPass * (1 - WEIGHT));
lastThirdPass = thirdPass; //Remember this for next time around
//End high pass filtering
fourthPass = abs(fourthPass); //Get the absolute value of this heavily filtered value
//See if this magnitude is large enough to care
if (fourthPass > MIN_MAGNITUDE_THRESHOLD)
{
//We have a potential hit!
currentTime = millis();
if ((unsigned long)(currentTime - lastHitTime) >= MIN_TIME_BETWEEN_HITS)
{
//We really do have a hit!
hitCounter++;
lastHitTime = millis();
//Serial.print("Hit: ");
//Serial.println(hitCounter);
if (displayOn == false) displayOn = true;
printHits(); //Updates the display
}
}
//Check if we need to reset the counter and display
if (digitalRead(resetButton) == LOW)
{
//This breaks the file up so we can see where we hit the reset button
Serial.println();
Serial.println();
Serial.println("Reset!");
Serial.println();
Serial.println();
hitCounter = 0;
resetDisplay(); //Forces cursor to beginning of display
printHits(); //Updates the display
while (digitalRead(resetButton) == LOW) wdt_reset(); //Pet the dog while we wait for you to remove finger
//Do nothing for 250ms after you press the button, a sort of debounce
for (int x = 0 ; x < 25 ; x++)
{
wdt_reset(); //Pet the dog
delay(10);
}
}
}
//This function makes sure the display is at 57600
void initDisplay()
{
resetDisplay(); //Forces cursor to beginning of display
printHits(); //Update display with current hit count
displayOn = true;
setBrightness(DEFAULT_BRIGHTNESS);
}
//Set brightness of display
void setBrightness(int brightness)
{
Wire.beginTransmission(DISPLAY_ADDRESS);
Wire.write(0x7A); // Brightness control command
Wire.write(brightness); // Set brightness level: 0% to 100%
Wire.endTransmission();
}
void resetDisplay()
{
//Send the reset command to the display - this forces the cursor to return to the beginning of the display
Wire.beginTransmission(DISPLAY_ADDRESS);
Wire.write('v');
Wire.endTransmission();
if (displayOn == false)
{
setBrightness(DEFAULT_BRIGHTNESS); //Power up display
displayOn = true;
lastHitTime = millis();
}
}
//Push the current hit counter to the display
void printHits()
{
int tempCounter = hitCounter / 2; //Cut in half
Wire.beginTransmission(DISPLAY_ADDRESS);
Wire.write(0x79); //Move cursor
Wire.write(4); //To right most position
Wire.write(tempCounter / 1000); //Send the left most digit
tempCounter %= 1000; //Now remove the left most digit from the number we want to display
Wire.write(tempCounter / 100);
tempCounter %= 100;
Wire.write(tempCounter / 10);
tempCounter %= 10;
Wire.write(tempCounter); //Send the right most digit
Wire.endTransmission(); //Stop I2C transmission
}
//Clear display to save power (a screen saver of sorts)
void clearDisplay()
{
Wire.beginTransmission(DISPLAY_ADDRESS);
Wire.write(0x79); //Move cursor
Wire.write(4); //To right most position
Wire.write(' ');
Wire.write(' ');
Wire.write(' ');
Wire.write(' ');
Wire.endTransmission(); //Stop I2C transmission
}
Above is my very amateur attempt at a filter to suppress the noise and look for peaks. I arrived at this by loading the log into LibreOffice and throwing math at it until I was able to get a reasonable hit value from it. I learned two things:
- I know very little about algorithms.
- My approach is not very accurate. I’m about 28 percent off, on average. I think it’s because there are some harmonic frequencies wreaking havoc when the boxer gets into a rhythm.
I’m pretty sure you can do a lot better. So here’s the deal: We’re going to have a little contest so that we can all learn from the experts about how to do this "for reals." You can get the raw datasets here. The names of the logs contain the number of hits in each. If you don’t believe me, you can view the videos and datasets here.
If you think you can more accurately calculate speed bag hits:
- Write an algorithm that correctly outputs the number of hits contained within the datasets (get them here).
- Implement your algorithm on a microcontroller (8-bit and 32-bit micros are OK; no FPGAs; PLCs, you’re crazy.
- The most important step: Document the heck out of how you approached the problem, how you filtered the data, and ultimately how you arrived at a solution. We’re here to learn from you.
- Put your code and documentation into a public repo or website.
- Use your algorithm to tell us how many hits are contained in Mystery Dataset #1 and Mystery Dataset #2. We have videos of these sessions that we’ll post once the contest is over.
We believe in the fundamentals of Open Source Hardware. Your work must be released under an open source license of your choice. No -NC exclusions allowed. I don’t plan to make this into a product, but you must be OK with it when someone releases an accelerometer-based speed bag counter. And sells it. For money.
How do I enter?
Post a link to your repo or website in the comments. We'll be running the contest through the end of the month (6/30), and I’ll test the solutions on the counter in the gym as they come in. There are very smart people in this world, so if there are multiple successful solutions we’ll randomly select a winner, who will be announced after the contest ends and all the entries are tested.
Wait, wait. So what do I win?
We’ll fly you and a +1 to Denver, and put you up in a hotel in Boulder. I’ll show you around SparkFun, take you to the Front Range Boxing Academy so you can see your code in action and do a dinner around Boulder. If you’re out of the USA, we will pay for a plane ticket for one person instead of two.
And whoa, Billy Bitzer is way better at this than me.
Update July 5th, 2016: Thanks for all the entries! Consider the contest closed. It will take us a bit to try to implement everyone's solutions. Many look great! Please bare with us; we'll post an update and a winner as soon as we can.
Winner! You can read the winner's post as well as Barry Hannigan's amazing tutorial on his solution.
