  To date, the histogram-based running median filter of Perreault and H\'ebert
is considered the fastest for 8-bit images, being roughly O(1) in average case.
We present here another approximately constant time algorithm which further
improves the aforementioned one and exhibits lower associated constant, 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 experimental comparison
to the previous constant-time algorithm defines the application domain of this
new development, besides theoretical interest, as high bit depth data and/or
hardware without SIMD extensions. The C/C++ implementation of the algorithm is
available under GPL for research purposes.
