Constant Time Median and Bilateral Filtering

This paper formulates both the median filter and bilateral filter as a cost volume aggregation problem whose computational complexity is independent of the filter kernel size. Unlike most of the previous works, the proposed framework results in a general bilateral filter that can have arbitrary spatial¹ and arbitrary range filter kernels. This bilateral filter takes about 3.5 s to exactly filter a one megapixel 8-bit grayscale image on a 3.2 GHz Intel Core i7 CPU. In practice, the intensity/range and spatial domain can be downsampled to improve the efficiency. This compression can maintain very high accuracy (e.g., 40 dB) but over 100× faster.