If what you want to do is maintain a running average of
the last n samples, then consider this approach:

Maintain a circular buffer that can hold 8 entries.
Maintain a SPIKE_COUNT.
Maintain a register named OLDEST.
Maintain a register called CURRENT_AVERAGE
Maintain a register set that can hold a value at least
up to 8*256=2048 (if dealing with 8 bit values).
Call this extended register set AVERAGE_8.
Let X be any value from 0 to 255.
Initialize all circular buffer contents to X.
Initialize AVERAGE_8 to 8*X.

You can now begin the Averaging process.
Eliminate "spike" values by comparing them to the
current AVERAGE_8 divided by 8 (simply right-shift
three times). If a spike occurs, increment the
SPIKE_COUNT. If it is NOT a spike, clear the
SPIKE_COUNT. If the SPIKE_COUNT reaches some arbitrary
value n (such as 4), then clear the SPIKE_COUNT and
enter it n times through the NORMAL procedure below.
(This will reject real spikes, but if the values
persist in that range, then they eventually get
accepted).

Normal procedure for GOOD data is as follows:
Point to oldest data element in circular buffer.
Save it in OLDEST.
Place new data into circular buffer, replacing oldest
data.
If new data is larger than old data, add the difference
to AVERAGE_8 register set.
If new data is smaller than old data, subtract the
difference from the AVERAGE_8 data set. Use two's
complement arithmetic with borrow from lower
byte causing a decrement of upper byte.
Right shift *copy* of AVERAGE_8 register set 3 places
to the right (divide by 8). The 8 least significant
bits of the result represent the CURRENT_AVERAGE.
If you have a register pair C_AVG and CURRENT_AVERAGE
allocated in that order, and use them as the *copy*
of the AVERAGE_8 set, then after the bit shifts
the current average will be in CURRENT_AVERAGE.

Fr. Thomas McGahee



----- Original Message -----
From: "Andy Shaw" <andy-pl@GLOOMY-PLACE.COM>
To: <PICLIST@MITVMA.MIT.EDU>
Sent: Sunday, April 28, 2002 4:53 AM
Subject: [PIC]: Space efficient moving/rolling median filter


> Hi,
> Does anyone have any code to implement a median filter for a small number
of
> samples (say 5, 7, 9) that can operate in a "moving/rolling" fashion (i.e.
> results are available after each new data point using the previous n data
> points), that operates in a time and space (I know I'm asking for too much
> here!) efficient way preferably using n (or less!) memory locations for n
> samples. I've looked around but all of the examples I've seen so far end
up
> changing the order of the data set and so make it hard to discard the
oldest
> item in the set.
>
> Note this does not have to be a perfect median filter so an efficient
> implementation that has similar noise removal properties would also work
for
> me.
>
> As always thanks for anything you can do to help!
>
> Andy
>
> PS A general C or pseudo code algorithm would be fine I can code it up!
>
> --
> http://www.piclist.com hint: The list server can filter out subtopics
> (like ads or off topics) for you. See http://www.piclist.com/#topics
>
>

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics