efficient running median

[Janto Dreijer]

On Oct 13, 6:33 pm, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
> Janto Dreijer <jan... at gmail.com> writes:
> > I'm looking for code that will calculate the running median of a
> > sequence, efficiently. (I'm trying to subtract the running median from
> > a signal to correct for gradual drift).
>
> Is that a known and valid technique of correcting for drift?  Maybe
> what you really want is a high-pass filter, to remove very low
> frequency components (drift) from the signal.  You can do that with
> standard digital filters.  Using something depending on ordering
> within the samples (i.e. the median) seems weird to me, but I'm no
> expert.

Well, I don't have a lot of theoretical reasoning behind wanting to
use a median filter. I have some experience applying it to images with
very good results, so that was the first thing I tried. It felt right
at the time and the results looked good. Also, most of the elements in
the sequence are supposed to be near zero, so the median is supposed
to give the amount of drift.

That said, you're probably right. I should have first tried to apply a
HPF.

> The obvious way to compute a running median involves a tree structure
> so you can quickly insert and delete elements, and find the median.
> That would be asymtotically O(n log n) but messy to implement.

Messy. Yes. I tried and failed :P

Thanks
Janto