efficient running median

[Dale Dalrymple]

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