Searching \ for 'Median Filter Code' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/logic/dsps.htm?key=filter
Search entire site for: 'Median Filter Code'.

Truncated match.
PICList Thread
'Median Filter Code'
1998\10\07@153548 by Bob Shaver

flavicon
face
This message thread was "Re: A/D Filtering"

On Friday, October 02, 1998 7:50 AM, Lawrence Lile
[SMTP:spam_OUTlilelTakeThisOuTspamTOASTMASTER.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.

1998\10\07@160729 by Bob Shaver

flavicon
face
On Wednesday, October 07, 1998 3:44 PM, John Payson
[SMTP:.....supercatKILLspamspam@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.

1998\10\07@171741 by Scott Dattalo

face
flavicon
face
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

1998\10\08@110921 by John Sanderson

flavicon
face
Hello PIC.ers,

Sorry if this post is a little long, but it seems there's enough interest.
..
{Quote hidden}

..
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

1998\10\08@124020 by Loferer Klaus

flavicon
face
Hello John,

I am interested in your solution.
Thank you.
Best regards
Klaus Loferer
eMail: Klaus.Lofererspamspam_OUTfossil.de

1998\10\08@133936 by lilel

flavicon
face
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

1998\10\08@134321 by lilel

flavicon
face
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

1998\10\08@135750 by John Payson

flavicon
face
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.

1998\10\08@144117 by Scott Dattalo

face
flavicon
face
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.

More... (looser matching)
- Last day of these posts
- In 1998 , 1999 only
- Today
- New search...