Torben Moving Median

Median filtering is a commonly used technique in signal processing. Typically used on signals that may contain outliers skewing the usual statistical estimators, it is usually considered too expensive to be implemented in real-time or CPU-intensive applications.

Let us define the median of N numerical values by:

• The median of a list of N values is found by sorting the input array in increasing order, and taking the middle value.
• The median of a list of N values has the property that in the list there are as many greater as smaller values than this element.

Example:

Torben’s method

This method was pointed out by Torben Mogensen.

It is certainly not the fastest way of finding a median, but it has the very interesting property that it does not modify the input array when looking for the median. It becomes extremely powerful when the number of elements to consider starts to be large, and copying the input array may cause enormous overheads. For read-only input sets of several hundred megabytes in size, it is the solution of choice, also because it accesses elements sequentially and not randomly. Beware that it needs to read the array several times though: a first pass is only looking for min and max values, further passes go through the array and come out with the median.

Credits to Fast median search: an ANSI C implementation.

PRT implementation

I have translated that C implementation by N. Devillard of Torben Mogensen algorithm in PRT, obtaining this moving median indicator:

Share this