I have experimented with median filters a lot.  Usually the simplest way to
code them is to take N samples, sort them into an ordered list, take the
median, THROW THEM ALL AWAY, and start over. (Throw-them-all out median
scheme)  Like others have said, any scheme that tries to add only one item
to the list and throw another away suffers from the fatal flaw of not
throwing away the oldest data each time unless it is pretty tricky.  You
can't get away with just throwing out the smallest, nor the biggest, nor the
medianest, because all of these schemes will get you in the end with wrong
median results.

One way I can think of to accomplish this is to keep a separate list of the
age of each reading, and then look up the oldest reading and throw it out.

Another way might be to keep two arrays:  One array is incoming data stream,
FIFO order.  The other array is a copy of the first array, which is then
sorted to find the median, and then flushed.  You could then throw out the
last item in the FIFO list, add another new item, and copy the array again.

None of these are very efficient algorithms, IMHO.  The alst algorithm takes
up at least 10-12 memory locations for a 5 median list.  What a memory hog.
For that much RAM, you could just take 9 readings and then flush the array
and put in all new readings.

Is there any advantage to keeping the old readings in a FIFO median scheme?
In the flush-em-all scheme, you never have any data older than N readings,
and median readings are updated every N readings.  In a FIFO median scheme,
you never have any data older then N readings, but you get a median redaing
on every single sample.  This seems better on the face, because you are
updating your median number faster.  But why do you take a median in the
first place?  Because you *don't* want the result to change too fast,
Because you are trying to find a stable result!   So the FIFO mmedian scheme
actually works against the purposes of readiong medians in the first place!

Most of my applications with median filters read samples on the orders of
milliseconds apart, and need results on the order of seconds apart.  I try
to read 15  times over the course of two AC cycles, to filter out the most
common kind of noise, 60 cycles hum.  So the simple throw-them-all-out
scheme works fine.

OTOH if you really really need to know the median every sample, you might
actually need the FIFO median scheme.  But I would argue that what you
really need is a faster sample rate!

--Lawrence

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.