Go Down

Topic: runningMedian class on playground (Read 9 times) previous topic - next topic

robtillaart

#5
Mar 15, 2012, 10:47 pm Last Edit: Mar 15, 2012, 10:54 pm by robtillaart Reason: 1
Updated the RunningMedian library to 0.1.02 on the playground - http://arduino.cc/playground/Main/RunningMedian - today:

+ constructor with size which should be between 1 and 19, if no param is given it defaults to size =5;
 (fized size arrays internally)

+ default type to float (can be made long quite easily)

+ extra functions getLowest() and getHighest()
+ extra function getAverage() of the buffer
+ a test if no values are added, the functions will return NAN to indicate error.

The new functions can easily be commented out (in .h and .CPP) to minimize the footprint of the class.

as allways remarks are welcome
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

Clemens

Hi Rob, that is great, thanks a lot!

robtillaart

#7
May 03, 2012, 11:40 am Last Edit: May 03, 2012, 11:42 am by robtillaart Reason: 1
Updated the RunningMedian library to 0.2.00 on the playground - http://arduino.cc/playground/Main/RunningMedian - today:

Thanks go to Ronny for his work on the new templated version!

changes:
+ added a template version so it can be used for any datatype (to be tested more thoroughly :)
+ added int getSize() to see the buffer size.
+ added int getCount() to see how far the internal buffer is filled.

There are differences between the versions, breaking backwards compatibility.

The 0.1.02 version (non template) is still available.

as allways remarks are welcome
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

rkail

Hello,

I did a new implementation using the same ideas, less features but with improved performance.

Code: [Select]

//
// Released to the public domain
//
// Remarks:
// This is a lean but fast version.
// Initially, the buffer is filled with a "default_value". To get real median values
// you have to fill the object with N values, where N is the size of the sliding window.
// For example: for(int i=0; i < 32; i++) myMedian.addValue(readSensor());
//
// Constructor:
// FastRunningMedian<datatype_of_content, size_of_sliding_window, default_value>
// maximim size_of_sliding_window is 255
// Methods:
// addValue(val) adds a new value to the buffers (and kicks the oldest)
// getMedian() returns the current median value
//
//
// Usage:
// #include "FastRunningMedian.h"
// FastRunningMedian<unsigned int,32, 0> myMedian;
// ....
// myMedian.addValue(value); // adds a value
// m = myMedian.getMedian(); // retieves the median
//

#include <inttypes.h>

template <typename T, uint8_t N, T default_value> class FastRunningMedian {

public:
FastRunningMedian() {
_buffer_ptr = N;
_window_size = N;
_median_ptr = N/2;

// Init buffers
uint8_t i = _window_size;
while( i > 0 ) {
i--;
_inbuffer[i] = default_value;
_sortbuffer[i] = default_value;
}
};

T getMedian() {
// buffers are always sorted.
return _sortbuffer[_median_ptr];
}


void addValue(T new_value) {
// comparision with 0 is fast, so we decrement _buffer_ptr
if (_buffer_ptr == 0)
_buffer_ptr = _window_size;

_buffer_ptr--;

T old_value = _inbuffer[_buffer_ptr]; // retrieve the old value to be replaced
if (new_value == old_value)   // if the value is unchanged, do nothing
return;

_inbuffer[_buffer_ptr] = new_value;  // fill the new value in the cyclic buffer

// search the old_value in the sorted buffer
uint8_t i = _window_size;
while(i > 0) {
i--;
if (old_value == _sortbuffer[i])
break;
}

// i is the index of the old_value in the sorted buffer
_sortbuffer[i] = new_value; // replace the value

// the sortbuffer is always sorted, except the [i]-element..
if (new_value > old_value) {
//  if the new value is bigger than the old one, make a bubble sort upwards
for(uint8_t p=i, q=i+1; q < _window_size; p++, q++) {
// bubble sort step
if (_sortbuffer[p] > _sortbuffer[q]) {
T tmp = _sortbuffer[p];
_sortbuffer[p] = _sortbuffer[q];
_sortbuffer[q] = tmp;
} else {
// done ! - found the right place
return;
}
}
} else {
// else new_value is smaller than the old one, bubble downwards
for(int p=i-1, q=i; q > 0; p--, q--) {
if (_sortbuffer[p] > _sortbuffer[q]) {
T tmp = _sortbuffer[p];
_sortbuffer[p] = _sortbuffer[q];
_sortbuffer[q] = tmp;
} else {
// done !
return;
}
}
}
}

private:
// Pointer to the last added element in _inbuffer
uint8_t _buffer_ptr;
// sliding window size
uint8_t _window_size;
// position of the median value in _sortbuffer
uint8_t _median_ptr;

// cyclic buffer for incoming values
T _inbuffer[N];
// sorted buffer
T _sortbuffer[N];
};

#endif
// --- END OF FILE ---


test code:

Code: [Select]

#include "FastRunningMedian.h"
#include "RunningMedianStatic.h"

unsigned int value = 0;

FastRunningMedian<unsigned int,32, 0> newMedian;
RunningMedianStatic staticMedian = RunningMedianStatic(32);

void setup ()
{
  while (!Serial) ;
  Serial.begin(9600);
  Serial.println("Starting....");
};

void loop()
{
  unsigned int xmedian;
  unsigned int cmedian;

  // us measurement overhead is 4 us.
  value = random(0, 255);
  unsigned long loopstart = micros();
  newMedian.addValue(value);
  xmedian = newMedian.getMedian();
  unsigned long loopstop = micros();

  unsigned long fastdelay = loopstop - loopstart;
 
  loopstart = micros();
  staticMedian.add(value);
  cmedian = staticMedian.getMedian();
  loopstop = micros();
 
  unsigned long slowdelay = loopstop - loopstart;
   
  Serial.print("Loop FastTime(us)=");
  Serial.print(fastdelay);
  Serial.print(" SlowTime(us)=");
  Serial.print(slowdelay);
  Serial.print("  value=");
  Serial.print(value);
  Serial.print(" median=");
  Serial.print(xmedian);
  Serial.print(" excactmedian=");
  Serial.print(cmedian);
  Serial.println();

  delay(500);
};


Enjoy !

robtillaart

thanks for sharing,

I do not have time to test it , 3 questions:

Can you post the output ?
how about the footprint? smaller / larger same?
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

Go Up