| Last Modified: | November 25, 2014, at 01:57 PM |
| By: | robtillaart |
| Platforms: | All |
A really fast version is made by rkail is discussed here. It is O(n) where the implementation below is O(n^2) - due to difference in strategy. Depending on the usage many adds seldom getMedian() or few adds() and many getMedian() the one or the other performs better.
an application to use runningMedian to handle degrees - compass
One of the main applications for the Arduino board is reading and logging of sensor data. For instance one monitors the CO concentration every second of the day. As samples may fluctuate and generate "spikes" in the graphs one can make multple measurements and take the median as "working" value. As the measurements are not static in time what one often wants is the median of a last defined period, a sort of "running median".
The median is defined as the middle value of an array of sorted values. The two main advantages of using the median above average is that it is not influenced by a single outlier and it allways represent a real measurement. On the other hand by averaging one could create extra precision.
The RunningMedian library is a small class that can have multiple instances in a sketch. Please note that every instance adds its own internal array to hold measurements, and that this adds up to the memory usage. The interface of the class is kept small but has grown a bit.
new in 0.2.00
new in 0.1.02
new in 0.1.04
RunningMedian(uint8_t size); // constructor RunningMedian(); // constructor void clear(); // clears internal state void add(float); // add a measurement float getMedian(); // returns the running Median float getAverage(); float getHighest(); float getLowest(); float getAverage(nMedians); // middle n numbers int getSize(); int getCount();
The class initializes a runningMedian of a certain size. Then it uses add() to fill a small internal array with measurements, these are kept in chronological order. If a new value is added and the array is full the oldest is overwritten. Simple circular buffer. If getMedian() is called the work begins, all values in the internal array are copied to a temp array and sorted. Then the middle element is returned. Clear() resets all internal counters to there initial values, to start over again.
A small sketch shows how it can be used. e.g connect a potmeter to the analog A0 pin.
//
// FILE: RunningMedian2.ino
// AUTHOR: Rob Tillaart ( kudos to Sembazuru)
// VERSION: 0.1.00
// PURPOSE: demo
// DATE: 2013-10-17
// URL:
//
// Released to the public domain
//
#include "RunningMedian.h"
RunningMedian samples = RunningMedian(15);
long count = 0;
void setup()
{
Serial.begin(115200);
Serial.print(F("Running Median Version: "));
Serial.println(RUNNING_MEDIAN_VERSION);
}
void loop()
{
test1();
}
void test1()
{
if (count % 20 == 0) Serial.println(F("\nmsec \tAnR \tSize \tCnt \tLow \tAvg \tAvg(3) \tMed \tHigh"));
count++;
long x = analogRead(A0);
samples.add(x);
float l = samples.getLowest();
float m = samples.getMedian();
float a = samples.getAverage();
float a3 = samples.getAverage(3);
float h = samples.getHighest();
int s = samples.getSize();
int c = samples.getCount();
Serial.print(millis());
Serial.print('\t');
Serial.print(x);
Serial.print('\t');
Serial.print(s);
Serial.print('\t');
Serial.print(c);
Serial.print('\t');
Serial.print(l);
Serial.print('\t');
Serial.print(a, 2);
Serial.print('\t');
Serial.print(a3, 2);
Serial.print('\t');
Serial.print(m);
Serial.print('\t');
Serial.println(h);
delay(100);
}
In loop() first a sample is read from an analog sensor. It is added to the running median class. Then the median of the set sofar is fetched and displayed. Because after every analogRead a median can be fetched from the class there is no need to do multiple samples every time.
To use the library, make a folder in your SKETCHBOOKPATH\libaries with the name RunningMedian and put the .h and .cpp there. Optionally make a examples subdirectory to place the sample app.
Enjoy tinkering,
rob.tillaart@removethisgmail.com
#ifndef RunningMedian_h
#define RunningMedian_h
//
// FILE: RunningMedian.h
// AUTHOR: Rob dot Tillaart at gmail dot com
// PURPOSE: RunningMedian library for Arduino
// VERSION: 0.1.04
// URL: https://arduino.cc/playground/Main/RunningMedian
// HISTORY: See RunningMedian.cpp
//
// Released to the public domain
//
#if defined(ARDUINO) && ARDUINO >= 100
#include "Arduino.h"
#else
#include "WProgram.h"
#endif
#include <inttypes.h>
#define RUNNING_MEDIAN_VERSION "0.1.04"
// should at least be 5 to be practical
#define MEDIAN_MIN_SIZE 1
#define MEDIAN_MAX_SIZE 19
#define MEDIAN_DEF_SIZE 5
// conditional compile to minimize lib
#define RUNNING_MEDIAN_ALL
class RunningMedian
{
public:
RunningMedian(uint8_t);
RunningMedian();
void clear();
void add(float);
float getMedian();
#ifdef RUNNING_MEDIAN_ALL
float getAverage();
float getAverage(uint8_t);
float getHighest();
float getLowest();
uint8_t getSize();
uint8_t getCount();
#endif
protected:
boolean _sorted;
uint8_t _size;
uint8_t _cnt;
uint8_t _idx;
float _ar[MEDIAN_MAX_SIZE];
float _as[MEDIAN_MAX_SIZE];
void sort();
};
#endif
// END OF FILE
//
// FILE: RunningMedian.cpp
// AUTHOR: Rob dot Tillaart at gmail dot com
// VERSION: 0.1.04
// PURPOSE: RunningMedian library for Arduino
//
// HISTORY:
// 0.1.00 - 2011-02-16 initial version
// 0.1.01 - 2011-02-22 added remarks from CodingBadly
// 0.1.02 - 2012-03-15 added
// 0.1.03 - 2013-09-30 added _sorted flag, minor refactor
// 0.1.04 - 2013-10-17 added getAverage(uint8_t) - kudo's to Sembazuru
//
// Released to the public domain
//
#include "RunningMedian.h"
RunningMedian::RunningMedian(uint8_t size)
{
_size = constrain(size, MEDIAN_MIN_SIZE, MEDIAN_MAX_SIZE);
// array's could be allocated by malloc here,
// but using fixed size is easier.
clear();
}
RunningMedian::RunningMedian()
{
_size = MEDIAN_DEF_SIZE;
clear();
}
// resets all counters
void RunningMedian::clear()
{
_cnt = 0;
_idx = 0;
_sorted = false;
}
// adds a new value to the data-set
// or overwrites the oldest if full.
void RunningMedian::add(float value)
{
_ar[_idx++] = value;
if (_idx >= _size) _idx = 0; // wrap around
if (_cnt < _size) _cnt++;
_sorted = false;
}
float RunningMedian::getMedian()
{
if (_cnt > 0)
{
if (_sorted == false) sort();
return _as[_cnt/2];
}
return NAN;
}
#ifdef RUNNING_MEDIAN_ALL
float RunningMedian::getHighest()
{
if (_cnt > 0)
{
if (_sorted == false) sort();
return _as[_cnt-1];
}
return NAN;
}
float RunningMedian::getLowest()
{
if (_cnt > 0)
{
if (_sorted == false) sort();
return _as[0];
}
return NAN;
}
float RunningMedian::getAverage()
{
if (_cnt > 0)
{
float sum = 0;
for (uint8_t i=0; i< _cnt; i++) sum += _ar[i];
return sum / _cnt;
}
return NAN;
}
float RunningMedian::getAverage(uint8_t nMedians)
{
if ((_cnt > 0) && (nMedians > 0))
{
if (_cnt < nMedians) nMedians = _cnt; // when filling the array for first time
uint8_t start = ((_cnt - nMedians)/2);
uint8_t stop = start + nMedians;
sort();
float sum = 0;
for (uint8_t i = start; i < stop; i++) sum += _as[i];
return sum / nMedians;
}
return NAN;
}
uint8_t RunningMedian::getSize() { return _size; };
uint8_t RunningMedian::getCount() { return _cnt; };
#endif
void RunningMedian::sort()
{
// copy
for (uint8_t i=0; i< _cnt; i++) _as[i] = _ar[i];
// sort all
for (uint8_t i=0; i< _cnt-1; i++)
{
uint8_t m = i;
for (uint8_t j=i+1; j< _cnt; j++)
{
if (_as[j] < _as[m]) m = j;
}
if (m != i)
{
float t = _as[m]; // PATCH from 0.1.05 (was long)
_as[m] = _as[i];
_as[i] = t;
}
}
_sorted = true;
}
// END OF FILE
#ifndef RunningMedian_h
#define RunningMedian_h
//
// FILE: RunningMedian.h
// AUTHOR: Rob dot Tillaart at gmail dot com
// PURPOSE: RunningMedian library for Arduino
// VERSION: 0.2.00 - template edition
// URL: https://arduino.cc/playground/Main/RunningMedian
// HISTORY: 0.2.00 first template version by Ronny
// 0.2.01 added getAverage(uint8_t nMedians, float val)
//
// Released to the public domain
//
#include <inttypes.h>
template <typename T, int N> class RunningMedian {
public:
enum STATUS {OK = 0, NOK = 1};
RunningMedian() {
_size = N;
clear();
};
void clear() {
_cnt = 0;
_idx = 0;
};
void add(T value) {
_ar[_idx++] = value;
if (_idx >= _size) _idx = 0; // wrap around
if (_cnt < _size) _cnt++;
};
STATUS getMedian(T& value) {
if (_cnt > 0) {
sort();
value = _as[_cnt/2];
return OK;
}
return NOK;
};
STATUS getAverage(float &value) {
if (_cnt > 0) {
float sum = 0;
for (uint8_t i=0; i< _cnt; i++) sum += _ar[i];
value = sum / _cnt;
return OK;
}
return NOK;
};
STATUS getAverage(uint8_t nMedians, float &value) {
if ((_cnt > 0) && (nMedians > 0))
{
if (_cnt < nMedians) nMedians = _cnt; // when filling the array for first time
uint8_t start = ((_cnt - nMedians)/2);
uint8_t stop = start + nMedians;
sort();
float sum = 0;
for (uint8_t i = start; i < stop; i++) sum += _as[i];
value = sum / nMedians;
return OK;
}
return NOK;
}
STATUS getHighest(T& value) {
if (_cnt > 0) {
sort();
value = _as[_cnt-1];
return OK;
}
return NOK;
};
STATUS getLowest(T& value) {
if (_cnt > 0) {
sort();
value = _as[0];
return OK;
}
return NOK;
};
unsigned getSize() {
return _size;
};
unsigned getCount() {
return _cnt;
}
STATUS getStatus() {
return (_cnt > 0 ? OK : NOK);
};
private:
uint8_t _size;
uint8_t _cnt;
uint8_t _idx;
T _ar[N];
T _as[N];
void sort() {
// copy
for (uint8_t i=0; i< _cnt; i++) _as[i] = _ar[i];
// sort all
for (uint8_t i=0; i< _cnt-1; i++) {
uint8_t m = i;
for (uint8_t j=i+1; j< _cnt; j++) {
if (_as[j] < _as[m]) m = j;
}
if (m != i) {
T t = _as[m];
_as[m] = _as[i];
_as[i] = t;
}
}
};
};
#endif
// --- END OF FILE ---
Test program for templated version
#include "RunningMedian.h"
const int SENSOR_PIN = A0;
RunningMedian<unsigned int,32> myMedian;
void setup ()
{
Serial.begin(9600);
pinMode(SENSOR_PIN, INPUT);
};
void loop()
{
unsigned _median;
unsigned _lowest;
unsigned _highest;
float _average;
float _averageN;
Serial.print(myMedian.getCount());
Serial.print(":");
// one way of working is that we ask for the status before getting data.
if (myMedian.getStatus() == myMedian.OK) {
myMedian.getMedian(_median);
Serial.print("Median = ");
Serial.print(_median);
Serial.println(" ");
}
else { // myMedian.NOK
Serial.println("No median. ");
}
Serial.print(myMedian.getCount());
Serial.print(":");
// The other way is that we check the return before relying on the data.
if (myMedian.getMedian(_median) == myMedian.OK) {
Serial.print(" Median = ");
Serial.print(_median);
}
else { // myMedian.NOK
Serial.print(" No median, ");
}
if (myMedian.getAverage(_average) == myMedian.OK) {
Serial.print(" Average = ");
Serial.print(_average);
}
else { // myMedian.NOK
Serial.print("No average, ");
}
if (myMedian.getAverage(5, _average) == myMedian.OK) {
Serial.print(" Average 2 = ");
Serial.print(_average);
}
else { // myMedian.NOK
Serial.print("No average, ");
}
if (myMedian.getLowest(_lowest) == myMedian.OK) {
Serial.print(" lowest = ");
Serial.print(_lowest);
}
else { // myMedian.NOK
Serial.print("No lowest, ");
}
if (myMedian.getHighest(_highest) == myMedian.OK) {
Serial.print(" highest = ");
Serial.println(_highest);
}
else { // myMedian.NOK
Serial.println(" No highest. ");
}
// now.. add some sensor-data and loop...
myMedian.add(analogRead(SENSOR_PIN));
delay(500);
};
usable for both versions
####################################### # Syntax Coloring Map for RunningMedian # "traditional" and template variant ####################################### ####################################### # Datatypes (KEYWORD1) ####################################### RunningMedian KEYWORD1 ####################################### # Methods and Functions (KEYWORD2) ####################################### add KEYWORD2 clear KEYWORD2 getMedian KEYWORD2 getAverage KEYWORD2 getHighest KEYWORD2 getLowest KEYWORD2 getSize KEYWORD2 getCount KEYWORD2 getStatus KEYWORD2 ####################################### # Constants (LITERAL1) ####################################### OK KEYWORD1 NOK KEYWORD1