Fixing my own post:
  Just a couple of small code tweaks -- correcting spelling errors and
adding a few notes.

> 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
>
> Also, note that this algorithm assumes that the filter has been
> magically preloaded with valid data. This could be as simple
> as just setting the entire buffer to zero (or midscale) and
> setting the 'last_median' variable to match.
>
> Then to enter a new value into the buffer:
>
> temp = buff[ptr];             // remember value we are replacing
> 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
>         next_lower = min_legal_value;    // = 0x00 probably
>         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
>         next_higher = 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;
>     }
> }
>
> and the result is available in 'last_median'.


Bob Ammerman
RAm Systems

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