efficient running median

[Janto Dreijer]

On Oct 13, 8:29 pm, Dale Dalrymple <d... at ieee.org> wrote:
> On Oct 13, 8:22 am, Janto Dreijer <jan... at gmail.com> wrote:
>
> > 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).
> > ...
> >  Any suggestions?
>
> For a reference try:
>
>  Comparison of algorithms for standard median filtering
> Juhola, M.   Katajainen, J.   Raita, T.
> Signal Processing, IEEE Transactions on
> Jan. 1991, Volume: 39 , Issue: 1, page(s): 204 - 208
> Abstract
>
> An algorithm I have used comes from:
>
>  On computation of the running median
> Astola, J.T.   Campbell, T.G.
> Acoustics, Speech and Signal Processing, IEEE Transactions on
> Apr 1989, Volume: 37,  Issue: 4, page(s): 572-574
>
> This is a dual heap approach. No code though. There are some obvious
> (yeah, right) errors in their pseudo-code.
>
> The point of the dual heap algorithm (loosely put) is to reduce the
> computation to slide the window 1 element to be proportional to 2
> bubble sorts of log window size instead of a window size sort.
>
> Good luck.
>
> Dale B. Dalrymple

Thanks. I'll have a look.

I found a PDF by Soumya D. Mohanty entitled "Efficient Algorithm for
computing a Running Median" (2003) by Googling. It has code snippets
at the end, but it's not going to be a simple cut-and-paste job. It
will take some work figuring out the missing parts.

Regards
Janto