Here is a linear time algorithm for a median filter. Note that I haven't
tested this code, it is just an off-the-top-of-my-head solution.

Given a circular buffer:

buff[2N+1]

And the last median value returned:

last_median

Then when you enter a new value into the buffer:

temp = buff[ptr];             // remember value we are deleting
buff[ptr] = new_value;    // insert new value
if ( ++ptr >= 2N+1 )      // circular update of ptr
   ptr = 0;

// if temp == new_value then the median doesn't
// change because we didn't actually change the data

if ( temp != new_value )
{
    if ( temp > new_value)
    {
        // since temp > new_value then we just put a
        // lower valued sample into the buffer. This means
        // that the median must be the same as the old
        // median, or else it is the next lower value in the
        // buffer
        nextlo = min_legal_value;
        count_hi_or_equal = 0
        for (i = 0; i < 2N+1; ++i)
        {
            if (buff[i] >= last_median)
                ++count_hi_or_equal;
            else if (buff[i] > next_lower)
                next_lower = buff[i]
        }
        if (count_hi_or_equal <= N)
            last_median = next_lower;
    }
    else
    {
        // since temp < new_value then we just put a
        // higher value sample into the buffer. This means
        // that the median must be the same as the old
        // median, or else it is the next higher value in the
        // buffer
        nexthi = max_legal_value;       // 0xFF for 8 bit samples
        count_lo_or_equal = 0
        for (i = 0; i < 2N+1; ++i)
        {
            if (buff[i] <= last_median)
                ++count_lo_or_equal;
            else if (buff[i] < next_higher)
                next_higher = buff[i]
        }
        if (count_lo_or_equal <= N)
            last_median = next_higher;
    }
}

----- Original Message -----
From: "Andrew Warren" <aiw@CYPRESS.COM>
To: <PICLIST@MITVMA.MIT.EDU>
Sent: Monday, April 29, 2002 8:05 PM
Subject: Re: [PIC]: Space efficient moving/rolling median filter


> Olin Lathrop <PICLIST@mitvma.mit.edu> wrote:
>
> > It might be better to detect and reject spikes up front, then use
> > a simple filter afterwards.
>
>     That's what Fr. Tom seems to have suggested, as well.
>
>     That approach, however, won't give the same sort of results as a
>     median filter would.  Median filters are WONDERFUL for pulling
>     square-wave pulses out of noise; because a median filter always
>     SELECTS from the sampled data rather than creating new data,
>     pulse edges are REALLY sharp.
>
>     Additionally, the performance of the filter is relatively
>     insensitive to the width of the moving filter window; the
>     filtered output doesn't degrade until the window gets VERY large
>     relative to the width of the pulses you're trying to find.
>
>     If I were Andy Shaw, I'd probably sample data into a circular
>     buffer, then NOT sort it.
>
>     Instead of sorting, I'd find the median value by just comparing
>     each value in the buffer with the others, until I found a value
>     that was greater-than or equal to "x" other values AND less-than
>     or equal to "x" other values, where "x" is (number of samples in
>     the buffer - 1)/2.  I'm assuming an odd number of samples in the
>     buffer, and that the buffer is relatively small... Like 5 to 15
>     samples.
>
>     That process can be really fast, especially if you think a
>     little before implementing the algorithm, and it will let you do
>     the FIFO thing with your circular buffer without requiring any
>     extra RAM for a sorted buffer or array of timestamps.
>
>     -Andy
>
> === Andrew Warren -- aiw@cypress.com
> === Principal Design Engineer
> === Cypress Semiconductor Corporation
> ===
> === Opinions expressed above do not
> === necessarily represent those of
> === Cypress Semiconductor Corporation
>
> --
> http://www.piclist.com hint: The PICList is archived three different
> ways.  See http://www.piclist.com/#archives for details.
>
>

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