Source-linked AI summary
Fast O(1) bilateral filtering using trigonometric range kernels
Kunal Narayan Chaudhury, Daniel Sage, Michael Unser
TL;DR
The bilateral filter’s intensity-dependent range kernel preserves edges but makes filtering nonlinear and expensive, especially with large spatial kernels. The paper uses trigonometric range kernels to extend constant-time averaging methods to bilateral filtering. These kernels provide exact computation for raised cosines and better Gaussian approximations than polynomial kernels for a fixed number of terms.
Problem
The bilateral filter’s range kernel makes intensity-aware averaging nonlinear and computationally intensive, while existing efficient methods do not scale well with large spatial kernels.
Method
The paper locally linearizes the bilateral filter with self-shiftable trigonometric range kernels, enabling O(1) averaging through linear convolutions of pointwise image transforms.
Results
Trigonometric kernels yield exact bilateral filtering for raised cosines and better local Gaussian approximations than polynomials for a fixed number of terms.
Takeaways & Limitations
Raised-cosine trigonometric kernels combine constant-time computation with accurate bilateral-filter approximation without range-kernel quantization.
Takeaways & Limitations
The raised-cosine family requires suitable scaling because its pointwise limit otherwise vanishes away from node points as degree increases.
Abstract
from arXiv · showhide
It is well-known that spatial averaging can be realized (in space or frequency domain) using algorithms whose complexity does not depend on the size or shape of the filter. These fast algorithms are generally referred to as constant-time or O(1) algorithms in the image processing literature. Along with the spatial filter, the edge-preserving bilateral filter [Tomasi1998] involves an additional range kernel. This is used to restrict the averaging to those neighborhood pixels whose intensity are similar or close to that of the pixel of interest. The range kernel operates by acting on the pixel intensities. This makes the averaging process non-linear and computationally intensive, especially when the spatial filter is large. In this paper, we show how the O(1) averaging algorithms can be leveraged for realizing the bilateral filter in constant-time, by using trigonometric range kernels. This is done by generalizing the idea in [Porikli2008] of using polynomial range kernels. The class of trigonometric kernels turns out to be sufficiently rich, allowing for the approximation of the standard Gaussian bilateral filter. The attractive feature of our approach is that, for a fixed number of terms, the quality of approximation achieved using trigonometric kernels is much superior to that obtained in [Porikli2008] using polynomials.
1 Introduction
The bilateral filter preserves edges by restricting averaging according to intensity similarity, but its range kernel makes direct computation nonlinear and costly. The paper extends Porikli’s constant-time approach with trigonometric range kernels.
- 1 Introduction: The normalizing factor preserves constants, including the local mean, while the spatial kernel determines the averaging neighborhood.
- 1 Introduction: Translation-invariant spatial kernels and symmetric difference-based range kernels define the unbiased bilateral-filter form considered here.
- 1 Introduction: The bilateral filter combines spatial proximity with intensity similarity to restrict averaging near edges.It averages neighboring pixels on the same side of an edge more strongly than pixels across the edge.
- 1 Introduction: Direct bilateral filtering is computationally intensive, and several real-time schemes do not scale well with spatial-kernel size.
- 1 Introduction: The paper extends Porikli’s O(1) algorithm to an exact bilateral-filter implementation using trigonometric range kernels.The approach exploits the fact that translating a trigonometric function preserves its degree, enabling local linearization.
2 Constant-time bilateral filter
The paper makes bilateral filtering constant-time by expressing trigonometric range kernels through a fixed number of linear spatial averages on pointwise-transformed images. Raised cosines provide valid range kernels and approximate Gaussian kernels more accurately than equal-term Taylor polynomials.
- 2.1 The main idea: The range term φ(f(x−y)−f(x)) makes bilateral filtering nonlinear, whereas constant φ reduces it to ordinary spatial averaging.Fast averaging algorithms can therefore be reused once the range term is linearized.
- 2.2 General trigonometric kernels: Raised cosines satisfy symmetry, non-negativity, and monotonic decay, making them valid range kernels over the restricted cosine half-period.For image dynamic range within [0,T], setting γ = π/2T keeps γs within [−π/2,π/2].
- 2.1 The main idea: The method computes O(1) bilateral filtering by averaging each auxiliary image and combining the results, with specialized spatial kernels reducing an M × M image to O(M2) operations.Fourier-based averaging costs O(M2 log2 M), while specialized kernels can achieve O(M2).
- 2.3 Raised cosines: A raised cosine of degree N expands into 2(N + 1) auxiliary images, with one fewer when N is even because the central term is constant.The expansion follows from representing cosine with complex exponentials and applying the binomial theorem.
- 2.4 Approximation of Gaussian kernels: Raised cosines converge to Gaussian kernels after normalization, and their convergence is faster than Taylor-polynomial approximation with the same number of terms.For σ = 80, a degree-4 raised cosine using three terms approximates the Gaussian better than the corresponding three-term Taylor polynomial, whose curve blows up beyond |x| > 100.
- 2.5 Control of the width of range kernel: The analysis yields an O(1) algorithm for approximating Gaussian bilateral filtering when both spatial and range filters are Gaussian.The raised-cosine family can be scaled to control variance, although reducing variance requires increasing the cosine degree enough to preserve kernel validity.
3 Experiments
Experiments show that the proposed implementation processes bilateral-filtered grayscale and color images efficiently, while closely matching direct filtering and avoiding polynomial-kernel artifacts.
- Implementation: The algorithm was implemented in Java as an ImageJ plugin using multithreaded recursive O(1) spatial averaging.Auxiliary images were processed in parallel on a Mac OS X 2× Quad core 2.66 GHz machine.
- Runtime: Processing was generally much faster than direct bilateral filtering, whose runtime increased substantially with spatial-filter size.Direct filtering on a 512 × 512 image took 4 seconds for σs = 3 and almost 10 seconds for σs = 10.
- Runtime: For narrow Gaussian range kernels with σr < 15, the proposed runtime increased sharply because approximating them required a large degree N.The authors mention an additional approximation scheme for this regime but leave it outside the paper’s scope.
- Grayscale results: On a natural grayscale image, the proposed output closely resembled direct filtering, whereas the polynomial approximation produced visible artifacts.The authors also report that the polynomial method was slightly faster because it used half as many auxiliary images for a given degree.
- Color results: The implementation was also tested on RGB images by processing the red, green, and blue channels independently.Results were shown for Greekdome and Tulip using different spatial and range-filter settings.
4 Discussion
The paper presents trigonometric range kernels as a constant-time bilateral-filter framework with exact raised-cosine implementations and stronger Gaussian approximations than polynomial kernels. Its main practical boundary is that very narrow Gaussians require many terms.
- Contribution: The method computes bilateral filtering in constant time by using trigonometric range kernels with fast averaging algorithms.Raised cosines provide a feasible family of range kernels within this framework.
- Accuracy: For raised-cosine kernels, the method is exact and avoids range-kernel quantization and exponentially growing auxiliary-image dynamic ranges.These properties reduce numerical-error concerns for large degrees compared with the polynomial approach.
- Speed: The algorithm supports parallel implementation in addition to O(1) complexity.Parallel processing can further accelerate the spatial averages of the auxiliary images.
- Approximation: Trigonometric functions provide better local Gaussian approximations than Taylor polynomials, producing artifact-free outputs that closely resemble the true result.Figure 3 compares the proposed output with direct filtering and a polynomial-kernel output.
- Limitation: A large number of terms is required to approximate very narrow Gaussians over large intervals.This is identified as the principal limitation of the approach and is also noted for the polynomial method.
- Color application: Color experiments processed the RGB channels independently for Greekdome and Tulip.The processed images are shown alongside their originals in Figure 4.