Real-time o(1) bilateral filtering

We propose a new bilateral filtering algorithm with com-putational complexity invariant to filter kernel size, so-called O(1) or constant time in the literature. By showing that a bilateral filter can be decomposed into a number of constant time spatial filters, our method yields a new class of constant time bilateral filters that can have arbitrary spa-tial1 and arbitrary range kernels. In contrast, the current available constant time algorithm requires the use of spe-cific spatial or specific range kernels. Also, our algorithm lends itself to a parallel implementation leading to the first real-time O(1) algorithm that we know of. Meanwhile, our algorithm yields higher quality results since we are effec-tively quantizing the range function instead of quantizing both the range function and the input image. Empirical ex-periments show that our algorithm not only gives higher PSNR, but is about 10 × faster than the state-of-the-art. It also has a small memory footprint, needed only 2 % of the memory required by the state-of-the-art for obtaining the same quality as exact using 8-bit images. We also show that our algorithm can be easily extended for O(1) median filtering. Our bilateral filtering algorithm was tested in a number of applications, including HD video conferencing, video abstraction, highlight removal, and multi-focus imag-ing. 1