On computation of the running median
Jaakko T. Astola, T. George Campbell · IEEE Transactions on Acoustics Speech and Signal Processing · 1989
A fast median filtering algorithm with logarithmic time complexity is presented that is based on a special data structure, a double heap, which naturally supports the median. With slight modification, the approach can be used to implement any rank-order filter. A complete implementation of the algorithm has been tested as a global Modula-2 module and has the expected performance and correctness.>