  It was recently demonstrated in [5] that the non-linear bilateral filter [14]
can be efficiently implemented using a constant-time or O(1) algorithm. At the
heart of this algorithm was the idea of approximating the Gaussian range kernel
of the bilateral filter using trigonometric functions. In this letter, we
explain how the idea in [5] can be extended to few other linear and non-linear
filters [14, 17, 2]. While some of these filters have received a lot of
attention in recent years, they are known to be computationally intensive. To
extend the idea in [5], we identify a central property of trigonometric
functions, called shiftability, that allows us to exploit the redundancy
inherent in the filtering operations. In particular, using shiftable kernels,
we show how certain complex filtering can be reduced to simply that of
computing the moving sum of a stack of images. Each image in the stack is
obtained through an elementary pointwise transform of the input image. This has
a two-fold advantage. First, we can use fast recursive algorithms for computing
the moving sum [15, 6], and, secondly, we can use parallel computation to
further speed up the computation. We also show how shiftable kernels can also
be used to approximate the (non-shiftable) Gaussian kernel that is ubiquitously
used in image filtering.
