Post by thread:Median Filter Code

This message thread was "Re: A/D Filtering" On Friday, October 02, 1998 7:50 AM, Lawrence Lile [SMTP:spam_OUTlilelTakeThisOuTTOASTMASTER.COM] wrote: > I've loaded a nice median routine on my web page cited below - take a > look at it. > > -- Lawrence Lile > => Median Filter Source Code > => AutoCad blocks for electrical drafting > > at: http://home1.gte.net/llile/index.htm Lawrence, I looked at your median filter code (a very quick look, only a couple of minutes) and was wondering how you handle inputting data samples once you fill up the filter array. The current code simply overwrites the 1st element (i.e. the highest sorted value) with the new data. I believe the program needs to keep an un-sorted array that acts as a FIFO (first-in first-out) for storing the 16 most-recent data samples. Then sort this data into another array to pick the median value. Am I missing something in your existing code? Bob Shaver Practical Micro Design, Inc.

On Wednesday, October 07, 1998 3:44 PM, John Payson [SMTP:.....supercatKILLspam@spam@circad.com] wrote: > From my reading, he reads sixteen input samples for each output sample > he produces, rewriting the entire array. For some applications this is > fine (esp. if you can read the sensors much faster than you need to show > the data). For other applications, the data 'delay' would be too much. I had not thought of that, but it makes sense if the app can handle the over-sampling rate. > BTW, I was pondering... how well would it work if one were to read one > item at a time, and alternately overwrite the minimum and maximum values > in the array? It would seem that wouldn't be as good as doing a true > FIFO, but might be simpler. This is an interesting idea! Sounds like it might be OK. Probably worth modeling before actually using it (or in my incredible amount of spare time <G>). Bob.

Bob Shaver wrote: {Quote hidden}> > This message thread was "Re: A/D Filtering" > > On Friday, October 02, 1998 7:50 AM, Lawrence Lile > [SMTP:lilelKILLspamTOASTMASTER.COM] wrote: > > I've loaded a nice median routine on my web page cited below - take a > > look at it. > > > > -- Lawrence Lile > > => Median Filter Source Code > > => AutoCad blocks for electrical drafting > > > > at: http://home1.gte.net/llile/index.htm > > Lawrence, > > I looked at your median filter code (a very quick look, only a couple of > minutes) and was wondering how you handle inputting data samples once you > fill up the filter array. The current code simply overwrites the 1st > element (i.e. the highest sorted value) with the new data. I believe the > program needs to keep an un-sorted array that acts as a FIFO (first-in > first-out) for storing the 16 most-recent data samples. Then sort this > data into another array to pick the median value. 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

Hello PIC.ers, Sorry if this post is a little long, but it seems there's enough interest. .. {Quote hidden}>Date: Wed, 7 Oct 1998 15:32:58 -0400 >From: Bob Shaver <.....bobsKILLspam.....PMDINC.COM> >Subject: Median Filter Code >On Friday, October 02, 1998 7:50 AM, Lawrence Lile >[SMTP:EraseMElilelspam_OUTTakeThisOuTTOASTMASTER.COM] wrote: >> I've loaded a nice median routine on my web page cited below - take a >> look at it. >> >> -- Lawrence Lile >Lawrence, >I looked at your median filter code (a very quick look, only a couple of >minutes) and was wondering how you handle inputting data samples once you >fill up the filter array. The current code simply overwrites the 1st >element (i.e. the highest sorted value) with the new data. I believe the >program needs to keep an un-sorted array that acts as a FIFO (first-in >first-out) for storing the 16 most-recent data samples. Then sort this >data into another array to pick the median value. >Am I missing something in your existing code? >Bob Shaver >Practical Micro Design, Inc. .. Bob's point here was taken up by me @~11pm last night. i.e. how does Lawrence's code handle the following situation? :- The filter is trying to track a moving signal, say one which is on a positive ramp (+dS/dt, for purists), and is already quite clean and free from jitter. .. Raw values read in, go only to the upper end of the range, while the output of the filter keeps returning the median value... but... the median doesn't change at all, even tho' the signal can be running awa y. As it stands, this filter will *depend* on having a guaranteed amount of noise fed into it. .. So far, having searched my archives, I've found Andy Warren's post from 9 Feb 1998 to be a very neat implementation of the same function - it's good for an array up to 5 or so values- I think it would get unwieldy at the 15 that Lawrence tackles. Still, Andy's doesn't address the *stuck median* issue above, <I can re-post his solution here, but I think I ought to let him do that> .. Given an n-word array, I think the problem disappears if the new input value is written over the previously-found output median, in the middle of the n-word range Then re-sort, pick the next median, etc., etc. Would this cover all bases? .. FWIW. I've modified these codes to accept a 16 bit x 5 word array, for my own purposes. So far it's not tested against real, living h/w but if anyone's interested, mail me separately. Best regards, John .. email from John Sanderson at JS Controls, PO Box 1887, Boksburg 1460, Rep. South Africa Manufacturer & purveyor of laboratory force testing apparatus and related products and services. Tel/fax: Johannesburg 893 4154 Cellphone 082 453 4815

Bob wrote: > I looked at your median filter code (a very quick look, only a > couple of minutes) and was wondering how you handle inputting data > samples once you fill up the filter array. The current code simply > overwrites the 1st element (i.e. the highest sorted value) with the > new data. I believe the program needs to keep an un-sorted array > that acts as a FIFO (first-in first-out) for storing the 16 > most-recent data samples. Then sort this data into another array to > pick the median value. > > Am I missing something in your existing code? > Good point. The current scheme works like this. 1. acquire new data point in an array of zeroes. 2. New data point overwrites first location. 3. Sort the entire array, New data popint ends up at last location 4. acquire new data point overwriting first location, which is still zero 5. sort the array, new data goes to last or second to last location 6. acquire new data point overwriting first location which is still zero. . . . 99. After the data array is full, take the median number. 100. clear the array so it's all zeroes <<< answering BOB's question 101. Do it ad nauseum. So you are never overwriting any data. I tried to write one that would always write over the oldest data point, but it got too complex. Your Idea of storing the values in an FIFO buffer, then storing the sort info somewhere else might have merit. -- Lawrence Lile "Nyquist was an optimist." => Median Filter Source Code => AutoCad blocks for electrical drafting at: http://home1.gte.net/llile/index.htm

John Wrote: > Bob's point here was taken up by me @~11pm last night. > i.e. how does Lawrence's code handle the following situation? :- The > filter is trying to track a moving signal, say one which is on a > positive ramp (+dS/dt, for purists), and is already quite clean and > free from jitter. .. Raw values read in, go only to the upper end > of the range, while the output of the filter keeps returning the > median value... but... the median doesn't change at all, even tho' > the signal can be running away. As it stands, this filter will > *depend* on having a guaranteed amount of noise fed into it. . I suppose the median code I use is only good for the case that your input signal is changing much slower than your sample rate. I am sampling an item 64 times a second and I expect to change states based on a setpoint once in a second. So I get 64 samples, or four bufferfulls before I need to change my output. No stuck median problem there. My code depends of flushing ALL old values out of the array every 16 samples. That's not always appropriate. If you need to change your output before you have sampled 16 inputs, then that's a different can of worms altogether. You could use a smaller median array (simple solution) or begin replacing the oldest data first. -- Lawrence Lile "Nyquist was an optimist." => Median Filter Source Code => AutoCad blocks for electrical drafting at: http://home1.gte.net/llile/index.htm

part 0 838 bytes If I'm understanding you correctly, the algorithm you describe would degenerate into the array holding essentially the following: min min min min min min min min NEW max max max max max max max where "min" is the lowest value ever seen, "max" is the highest value, and "NEW" is the most recent value. Once this happens the median routine will be pretty useless. I think the best approach probably is to keep a buffer of the last few samples (e.g. six) and then continuously take the average of the middle four (i.e. sum all six and subtract the minimum and maximum). This would weed out single extreme points while providing more smoothing than simply doing median-of-three. Note that finding the minimum and maximum of a set of 8-bit numbers is very quick; for longer sizes things are a bit harder.

John Payson wrote: > I think the best approach probably is to keep a buffer of the last few > samples (e.g. six) and then continuously take the average of the middle > four (i.e. sum all six and subtract the minimum and maximum). This would > weed out single extreme points while providing more smoothing than simply > doing median-of-three. Note that finding the minimum and maximum of a > set of 8-bit numbers is very quick; for longer sizes things are a bit > harder. BINGO! This is what I tried to say yesterday (obviously not too well). I used this type of algorithm for part of that DTMF decoder we continually elude to. However, like the DTMF decoder, I can't divulge the median/averaging combo filter. All I can say is that it works.