efficient running median
Dale Dalrymple
dbd at ieee.org
Tue Oct 13 14:29:30 EDT 2009
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
More information about the Python-list
mailing list