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(rd) algorithm per pixel. Huang et al. proposed to shift the histogram pixel-by-pixel to reduce the complexity to O(rd-1) per pixel. We also show how to transfer their algorithm to higher dimensions, in this contribution. Perreault and He&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.