Fast and memory-efficient quantile filter for data in three and higher dimensions

Quantile and median filters are usually implemented by accumulating a histogram in a mask with side length 2r + 1, and then selecting the desired quantile from the histogram. Fully updating the histogram for every pixel in a d-dimensional image leads to an O(r^d) algorithm per pixel. Huang et al. proposed to shift the histogram pixel-by-pixel to reduce the complexity to O(r^d-1) per pixel. We also show how to transfer their algorithm to higher dimensions, in this contribution. Perreault and Hébert extended this idea to reach O(1) runtime per pixel in arbitrary dimension. Thus, from an algorithmic point of view, quantile filtering of d-dimensional data is a solved problem. But the memory requirements of that algorithm grow with a power of D - 1. In this contribution, we therefore propose a novel hybrid quantile filter algorithm which is situated between the two aforementioned methods in terms of memory requirements, and which is faster for a wide range of mask sizes due to reduced overhead.