Acceleration of Shiftable O (1) Algorithm for Bilateral Filtering and Non-local means

A direct implementation of the bilateral filter requires O (s2) operations per pixel, where sis the (effective) width of the spatial kernel. A fast implementation of the bilateral filter was recently proposed that require O (1) operations per pixel with respect to s. This is done by using trigonometric functions for the range kernel of the bilateral filter, and by exploitingtheir so-called shiftability property. In particular, a fast implementation of the Gaussian bilateralfilter is realized by approximating the Gaussian range kernel using raised cosines. Later, it is demonstrated that this idea could be extended to a larger class of filters, including thepopular non-local means filter. For an image with dynamic range [0, T], the run time scaled as O (T2/r2) with r. This made it difficult to implement narrow range kernels, particularly for images with large dynamic range. This project discusses this problem and propose some advanced methods to accelerate the implementation, in general and for small rin particular and also provides some experimental results to demonstrate the acceleration that is achievedusing these modifications.