piclist 1998\10\07\171741a >
www.piclist.com/techref/logic/dsps.htm?key=filter
BY : Scott Dattalo email (remove spam text)

Bob Shaver wrote:
{Quote hidden}

I haven't looked at Lawrence's code, but here's an algorithm I have used
that combines a median filter with a good ol' fashioned averaging one:

o as data samples are acquired, place them into a circular array.
o as a new sample is inserted, add it to the cumulative sum of all the
elements and at the same time subtract the value that's being over
written. This saves the time consuming task of summing the elements each
time to find the average.
o maintain a list of pointers to each element of the array and sort
the pointer list (and not the elements)
o apply the 'median operator' by subtracting from the cumulative sum
those values that are at the extremes of the sorted list.

For example, you could have a circular buffer of 8 elements. When
sorted, you may decide to discard the top two and the bottom two -
leaving you with 4. After each pass through the above algorithm, you
would shift the cumulative sum right 2 positions (i.e. divide by 4) to
get the average.

The 'pointers' only need to be nibbles for small buffers (the typical
case), so the storage over head is no too sever. Keeping the sorted list
of pointers means that you only have to make one pass through the sorter
each time a sample is acquire. (alternatively, you have to make a ~n^2
sorta computation if you sort the entire array each time a new sample is
acquired.)

BTW. I used something like this in that caller ID project. It kills two
stones with one bird - it smoothes the sampled data by averaging and at
the same time discards unwanted spikes. Also it's relatively fast...

Scott

<361B75C6.D2460FB7@unix.sri.com> 7bit