Acceleration of the shiftable O(1) algorithm for bilateral filtering and non-local means

Abstract

A direct implementation of the bilateral filter [1] requires O(σ_s^2) operations per pixel, where σ_s is the (effective) width of the spatial kernel. A fast implementation of the bilateral filter was recently proposed in [2] that required O(1) operations per pixel with respect to σ_s. This was done by using trigonometric functions for the range kernel of the bilateral filter, and by exploiting their so-called shiftability property. In particular, a fast implementation of the Gaussian bilateral filter was realized by approximating the Gaussian range kernel using raised cosines. Later, it was demonstrated in [3] that this idea could be extended to a larger class of filters, including the popular non-local means filter [4]. As already observed in [2], a flip side of this approach was that the run time depended on the width σ_r of the range kernel. For an image with (local) intensity variations in the range [0,T], the run time scaled as O(T^2/σ^2_r) with σ_r. This made it difficult to implement narrow range kernels, particularly for images with large dynamic range. We discuss this problem in this note, and propose some simple steps to accelerate the implementation in general, and for small σ_r in particular. [1] C. Tomasi and R. Manduchi, "Bilateral filtering for gray and color images", Proc. IEEE International Conference on Computer Vision, 1998. [2] K.N. Chaudhury, Daniel Sage, and M. Unser, "Fast O(1) bilateral filtering using trigonometric range kernels", IEEE Transactions on Image Processing, 2011. [3] K.N. Chaudhury, "Constant-time filtering using shiftable kernels", IEEE Signal Processing Letters, 2011. [4] A. Buades, B. Coll, and J.M. Morel, "A review of image denoising algorithms, with a new one", Multiscale Modeling and Simulation, 2005.

10 figures, 6 tables

Cited by in corpus (18)

• Fast Adaptive Bilateral Filtering
• Fast and Provably Accurate Bilateral Filtering
• James-Stein Type Center Pixel Weights for Non-Local Means Image Denoising
• Probabilistic Non-Local Means
• On Fast Bilateral Filtering using Fourier Kernels
• Fast High-Dimensional Bilateral and Nonlocal Means Filtering
• Gaussian Fourier Pyramid for Local Laplacian Filter
• Speeding Up the Bilateral Filter: A Joint Acceleration Way
• Fast and Accurate Bilateral Filtering using Gauss-Polynomial Decomposition
• Accurate Vision-based Vehicle Localization using Satellite Imagery
• Blockwise SURE Shrinkage for Non-Local Means
• Image Denoising using Optimally Weighted Bilateral Filters: A Sure and Fast Approach
• An FPGA-Based Fully Pipelined Bilateral Grid for Real-Time Image Denoising
• Precision Enhancement of 3D Surfaces from Multiple Compressed Depth Maps
• Accelerated graph-based nonlinear denoising filters
• Accelerated graph-based spectral polynomial filters
• Matlab Implementation of Machine Vision Algorithm on Ballast Degradation Evaluation
• An Approach for Reducing Outliers of Non Local Means Image Denoising Filter