(a.k.a. sliding window median, running median filter, and rolling median filter)
Benchmarking median filter algorithms, see: http://arxiv.org/abs/1406.1717
If you are looking for a practical median filter algorithm for 1D and 2D data, see: https://github.com/suomela/mf2d
Input:
- vector x with n elements
- window size k
Output:
- vector y with n-k+1 elements
- y[i] is the median of x[i], x[i+1], ..., x[i+k−1].
See: http://en.wikipedia.org/wiki/Median_filter
-
"sort": O(n log k): sort blocks, do linear-time post-processing
-
"heap": O(n log k): maintain a maxheap + minheap pair
-
"tree": O(n log k): maintain balanced search trees
-
"move": O(n k): maintain a sorted vector
This algorithm is described here:
The basic idea is to maintain a maxheap + minheap pair, see:
- http://dx.doi.org/10.1109/29.17539
- http://dx.doi.org/10.1109/78.80784
- http://dx.doi.org/10.2307/2986349
The present implementation is by AShelly:
It was further adapted by Colin Raffel, and this is the version that we use (almost verbatim):
The software is written in C++11. To compile it, you will need a recent C++ compiler. For example, the following compilers should work fine:
-
g++ (GCC 4.7.3 or later). Tested with these versions:
g++-4.7 (Ubuntu/Linaro 4.7.3-2ubuntu1~12.04) 4.7.3 g++-4.8 (GCC) 4.8.2 g++-4.9 (GCC) 4.9.0
-
clang++ (LLVM 3.4 or later). Tested with these versions:
Apple LLVM version 5.1 (clang-503.0.40) (based on LLVM 3.4svn)
For OS X 10.9.2, you can get the right versions of the compilers from the following sources:
- clang++: from Apple
- g++-4.9: from Homebrew ("brew install gcc49")
Depending on your C++ compiler and operating system, use one of the following scripts to compile this software.
OS X:
- "bin/build-clang": compiles with "clang++"
- "bin/build-gcc-4.8-osx": compiles with "g++-4.8"
- "bin/build-gcc-4.9-osx": compiles with "g++-4.9"
Linux:
- "bin/build-gcc": compiles with "g++"
- "bin/build-gcc-4.7": compiles with "g++-4.7"
- "bin/build-gcc-4.8": compiles with "g++-4.8"
- "bin/build-gcc-4.9": compiles with "g++-4.9"
You can also try to use "scons" to compile everything. The build scripts are configured for OS X platforms that have both clang++ and g++-4.9 installed. You can get both scons and g++-4.9 from Homebrew.
- build-clang-short: compiled with Clang, 32-bit data
- build-clang-long: compiled with Clang, 64-bit data
- build-gcc-short: compiled with GCC, 32-bit data
- build-gcc-long: compiled with GCC, 64-bit data
verify: does some sanity-checking and makes sure that all three algorithms produce the same output. Use the command line parameter for larger tests, and another parameter to skip the slowest algorithm. Examples:
build-gcc-short/verify
build-gcc-short/verify 10
build-gcc-short/verify 100 x
tester: benchmarking with different parameter values and different input data generators. Run without command line parameters for brief usage instructions.
See "bin/examples"
Output (fastest algorithms marked with a star):
sort 10 500000 r-asc 1 0.37903
heap 10 500000 r-asc 1 0.33694 *
tree 10 500000 r-asc 1 1.92399
move 10 500000 r-asc 1 0.61234
sort 10 500000 r-large 1 0.40114
heap 10 500000 r-large 1 0.33726 *
tree 10 500000 r-large 1 1.97069
move 10 500000 r-large 1 0.59606
sort 100000 5 r-asc 1 0.08125 *
heap 100000 5 r-asc 1 0.23712
tree 100000 5 r-asc 1 0.66017
move 100000 5 r-asc 1 26.93506
sort 100000 5 r-large 1 0.08979 *
heap 100000 5 r-large 1 0.09957
tree 100000 5 r-large 1 1.53184
move 100000 5 r-large 1 9.01672
sort 1000000 5 r-asc 1 0.91729 *
heap 1000000 5 r-asc 1 3.73655
tree 1000000 5 r-asc 1 8.75793
sort 1000000 5 r-large 1 1.48117
heap 1000000 5 r-large 1 1.32437 *
tree 1000000 5 r-large 1 29.67124
sort 10000000 5 r-asc 1 9.27875 *
heap 10000000 5 r-asc 1 44.77312
tree 10000000 5 r-asc 1 95.78014
sort 10000000 5 r-large 1 23.72148
heap 10000000 5 r-large 1 14.37096 *
tree 10000000 5 r-large 1 441.65488
Columns:
- algorithm
- h, the half-window size
- b, the number of blocks
- input data generator
- random seed
- time in seconds
Here window size is k = 2h + 1. Input data is a vector with n = bk elements.
In this example we used the following generators:
- "r-asc": monotonically incresing sequence + random noise
- "r-large": large random numbers
- x axis: half-window size
- y axis: running time
- blue: "sort" algorithm
- green: "heap" algorithm
- red: "tree" algorithm
- black: "move" algorithm
- solid curve = median
- shaded area = 10% ... 90% region
Copyright (c) 2014, Jukka Suomela.
You can distribute and use this software under the MIT license: http://opensource.org/licenses/MIT
To contact the author, see https://jukkasuomela.fi/
Based on: https://github.com/craffel/median-filter (file Mediator.h)
Sliding median filter
Created 2012 by Colin Raffel
Portions Copyright (c) 2011 ashelly.myopenid.com under
<http://www.opensource.org/licenses/mit-license>
Computer resources were provided by the Aalto University School of Science "Science-IT" project.
Thanks to David Eppstein, Geoffrey Irving, Pat Morin, and Saeed for comments and discussions here: