Revision 0:9bd415456089, committed 2014-01-31

Comitter:

networker

Date:

Fri Jan 31 10:36:45 2014 +0000

Commit message:

An efficient implementation of a sliding window median filter

Changed in this revision

diff -r 000000000000 -r 9bd415456089 filter.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/filter.cpp	Fri Jan 31 10:36:45 2014 +0000
@@ -0,0 +1,81 @@
+#include <float.h>
+#include "filter.h"
+
+medianFilter::medianFilter(int window): N(window) {
+    big = new bool[N];
+    val = new float[N];
+    big = new bool[N];
+    i = 0;
+    for (int j = 0; j < N; j++) {
+        val[j] = 0;
+        big[j] = j > N/2;
+    }
+    med = 0;
+    median=0;
+}
+
+int medianFilter::findmax() {
+    float m = -FLT_MAX;
+    int n = -1;
+    for (int j = 0; j < N; j++) {
+        if (j == med) continue;
+        if (!big[j]) { //find max
+            if (val[j] > m) {
+                m = val[j];
+                n = j;
+            }
+        }
+    }
+    return n;
+}
+
+int medianFilter::findmin() {
+    float m = FLT_MAX;
+    int n = -1;
+    for (int j = 0; j < N; j++) {
+        if (big[j]) { //find min
+            if (val[j] < m) {
+                m = val[j];
+                n = j;
+            }
+        }
+    }
+    return n;
+}
+
+float medianFilter::process(float in) {
+    //the value at position 'i' is to be replaced by 'in' and the new median is computed
+    //var 'median' refers to the old median
+    //  val[j] <= median <= val[k]
+    //by convention the mediam is considered small
+    val[i] = in;
+    if (i == med) { //the median itself is removed (not the value but the actual sample)
+        if (in <= median) { //the new value is smaller than or equal to the old median and may be the new median
+            med = -1;  //hack to include the median cell in the comparison
+            med = findmax(); //the largest small value is the new median
+        } else { //the new value is larger than the old median and may be the new median
+            big[i] = true; //add the new val to the big set, which is now 1 too large
+            med = findmin();
+            big[med] = false;
+        }
+    } else if (!big[i]) {//old value is removed from small values
+        if (in <= median) {
+            //replace small with small, median not affected
+        } else { //the new value is large
+            big[i] = true;
+            med = findmin();
+            big[med] = false;
+        }
+    } else  { //old value is large
+        if (in <= median) { //but the new value is small
+            big[i] = false;
+            big[med] = true;
+            med = findmax();
+        } else {//new value is also large
+            //replace large with large, median not affected
+        }
+    }
+    if (++i >= N) i = 0;
+    median = val[med];
+    return median;
+}

diff -r 000000000000 -r 9bd415456089 filter.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/filter.h	Fri Jan 31 10:36:45 2014 +0000
@@ -0,0 +1,24 @@
+#ifndef FILTER_H
+#define FILTER_H
+
+class filter {
+public:
+    virtual float process(float in) {
+        return in;
+    }
+};
+
+class medianFilter: public filter {
+    int N;
+    float *val;
+    bool *big;
+    int med, i;
+    float median;
+    int findmax();
+    int findmin();
+public:
+    medianFilter(int window = 3); //every window >= 1 is allowed but the behaviour for even window sizes is not well defined
+    virtual float process(float);
+};
+
+#endif
\ No newline at end of file