Hierarchical recursive running median
Alexander Alekseychuk · 2012
Median filter was long known in image processing for its high computational costs. Recently, an algorithm was developed which is able to compute median on integer-valued images in a roughly constant average time. A new O(1) algorithm presented here further improves the aforementioned one, being at the time of writing the lowest theoretical complexity algorithm for calculation of 2D and higher dimensional median filters. The algorithm scales naturally to higher precision (e.g. 16-bit) integer data without any modifications. Its adaptive version offers additional speed-up for images showing compact modes in gray-value distribution. The algorithm will be useful for high bit depth data or on hardware without SIMD extensions. A C/C++ implementation is available under GPL for research purposes.