A runningMedian Class for Arduino.

Last Modified: November 30, 2013, at 05:40 AM
By: robtillaart
Platforms: All

remarks & comments

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

Intro

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.

RunningMedian library

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

  • first templated version (code and test prg) at the end.
  • added getSize() to see the buffer size.
  • added getCount() to see how far buffer is filled.

new in 0.1.02

  • The standard datatype is set to float (you can easily change it to long)
  • the constructor got a parameter which must be between MEDIAN_MIN and MEDIAN_MAX
  • three new functions have been added (bet these may be removed

new in 0.1.04

  • three functions
  • a conditional #ifdef to keep code and functionality minimal

	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.

Usage

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.

Notes

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.

Version 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 constructor with size and some extra functions, fixed a bug if getMedian was called when nothing was added. Now it returns NAN = Not A Number which is actual a float value.
  • 0.1.04 2013-10-17 added getAverage(uint8_t nMedians) + getSize() + getCount() + #ifdef conditional

  • 0.2.00 2012-05-03 Template version by Ronny

Todo

  • use qsort() from avr lib
  • use malloc for arrays?
  • smarter use of arrays?

Done

  • known BUG: if no values are added or directly after clear(), getMedian() will return an undefined result. This can be solved in the float domain as there exists NaN as value; [SOLVED 0.1.02]
  • do a partial sort as only the lower half+1 is needed [OBSOLETE, the functions getLowest and getHighest use the full sort]
  • add getAverage() [DONE 0.1.02]

Enjoy tinkering,

rob.tillaart@removethisgmail.com

RunningMedian.h

#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: http://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

RunningMedian.cpp

//
//    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

Template version

RunningMedian.h (template version, no cpp version)

#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: http://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);
};


Keywords.txt

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

Share