PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Adaptive Bilateral Filtering

Ruturaj G. Gavaskar, Kunal N. Chaudhury

arXiv:1811.02308v1cs.CV

TL;DR

Adaptive bilateral filtering varies range-kernel parameters by pixel, but its brute-force implementation is computationally costly. The paper approximates local histograms with moment-matched polynomials and reports at least 20× speedup, demonstrating applications in sharpening, deblocking, and texture filtering.

  • Problem

    Adaptive bilateral filtering varies range-kernel width by pixel for greater texture-filtering flexibility, while brute-force timing increases with ρ.

    Source: A. Adaptive bilateral filter · p. 1, §III · p. 7

  • Method

    The algorithm approximates local histograms with polynomials fitted by matching their moments to histogram moments computed using convolutions.

    Source: D. Contributions · p. 3

  • Results

    At least 20× faster than the brute-force implementation, with speedups often reaching 60×.

    Source: §III · p. 7

  • Takeaways & Limitations

    The proposed texture-filtering method is competitive with state-of-the-art methods in runtime and performance.

    Source: §V · p. 10

Abstract

from arXiv · show

In the classical bilateral filter, a fixed Gaussian range kernel is used along with a spatial kernel for edge-preserving smoothing. We consider a generalization of this filter, the so-called adaptive bilateral filter, where the center and width of the Gaussian range kernel is allowed to change from pixel to pixel. Though this variant was originally proposed for sharpening and noise removal, it can also be used for other applications such as artifact removal and texture filtering. Similar to the bilateral filter, the brute-force implementation of its adaptive counterpart requires intense computations. While several fast algorithms have been proposed in the literature for bilateral filtering, most of them work only with a fixed range kernel. In this paper, we propose a fast algorithm for adaptive bilateral filtering, whose complexity does not scale with the spatial filter width. This is based on the observation that the concerned filtering can be performed purely in range space using an appropriately defined local histogram. We show that by replacing the histogram with a polynomial and the finite range-space sum with an integral, we can approximate the filter using analytic functions. In particular, an efficient algorithm is derived using the following innovations: the polynomial is fitted by matching its moments to those of the target histogram (this is done using fast convolutions), and the analytic functions are recursively computed using integration-by-parts. Our algorithm can accelerate the brute-force implementation by at least $20 \times$, without perceptible distortions in the visual quality. We demonstrate the effectiveness of our algorithm for sharpening, JPEG deblocking, and texture filtering.

I. INTRODUCTION

Bilateral filtering preserves edges by downweighting neighbors with large intensity differences, but this makes it computationally intensive. The adaptive variant changes range-kernel parameters across pixels, supporting more flexible filtering, while motivating a fast implementation.

I. INTRODUCTION

  • Large intensity differences receive small range-kernel weights, limiting the mixing of pixels across edges.The filter combines a range kernel with a spatial kernel, usually both Gaussian.Source: §I · p. 1

A. Adaptive bilateral filter

  • Adaptive range-kernel parameters support sharpening and noise removal, and variable-width kernels have also been used for compression and registration artifact removal.The center and width control the amount of sharpening and noise removal at each pixel.Source: §I · p. 1
  • Fast adaptive filtering has received little attention; the proposed algorithm is independent of window size for box or Gaussian spatial kernels and accelerates brute force by at least 20×.The paper also notes that the algorithm can work with other spatial kernels.Source: A. Adaptive bilateral filter · pp. 1–2
  • The adaptive bilateral filter locally changes its range-kernel width to smooth coarse textures while preserving sharp edges.A fixed narrow width leaves coarse textures, while a large width blurs edges.Source: A. Adaptive bilateral filter · p. 1, Figure 1 · p. 2

B. Fast bilateral filter

The paper develops a fast adaptive bilateral filter by approximating local histograms and using integrals to compute the filtering. It reports window-width-independent complexity and at least 20× acceleration, alongside applications including sharpening, deblocking, and texture filtering.

B. Fast bilateral filter

  • Quantization, fixed-range-kernel decompositions, and high-dimensional convolution methods cannot directly accelerate adaptive filtering when range parameters vary by pixel.These methods rely on fixed range kernels or on expressing the filtering as a convolution.Source: B. Fast bilateral filter · p. 2

C. Speedup using histogram approximation

D. Contributions

  • The algorithm is demonstrated for sharpening, JPEG deblocking, and texture filtering.The paper presents its applications as examples of the proposed algorithm's utility.Source: D. Contributions · p. 3
  • Matching polynomial moments to local-histogram moments uses convolutions, while integration-by-parts recursion computes the resulting integrals efficiently.The method transforms local range data so the matrix to invert is shared across pixels and has a closed-form inverse.Source: D. Contributions · p. 3
  • At least 20× acceleration over brute force is reported, with acceptable approximation accuracy (PSNR ≥40 dB).The theoretical complexity is O(1) with respect to spatial filter width ρ.Source: D. Contributions · p. 3

B. Polynomial fitting

The local histogram is approximated by a polynomial fitted through moment matching after affine domain stretching. This enables a shared closed-form inversion for fitting and analytic integral approximations of the filter.

B. Polynomial fitting

  • Moment matching fits a degree-N polynomial to the first N + 1 moments of the local histogram.The histogram moments can be computed without explicitly forming the histogram, avoiding a computation that otherwise requires O(ρ^2) operations.Source: B. Polynomial fitting · p. 4
  • The polynomial approximation drops the non-negativity requirement because the polynomial appears in both the filter numerator and denominator.Although the approximation is empirically non-negative in most cases, this is not imposed as a constraint.Source: B. Polynomial fitting · p. 4
  • Affine domain stretching maps each local histogram domain to [0, 1], allowing moment matching to use one closed-form matrix inversion.The inverse of the resulting Hilbert matrix has a closed-form expression.Source: B. Polynomial fitting · p. 4
  • The filter is approximated by replacing finite range-space sums with integrals over the stretched histogram domain.The polynomial representation makes these integrals computable in the proposed approximation.Source: B. Polynomial fitting · pp. 4–5
  • Figure 2 illustrates the affine stretching of a local histogram from [0.15, 0.79] to [0, 1] and a fifth-degree moment-matched polynomial.The plotted polynomial coefficients are scaled for display.Source: Figure 2 · p. 5

C. Recursive computation of integrals

The required integrals are computed recursively using integration by parts. The recursion starts with I0 and I1, which are evaluated using standard functions.

C. Recursive computation of integrals

  • Integration by parts gives a recursive formula for computing I2 through IN+1 from I0 and I1.The ratio of successive integrands is t, which is proportional to the derivative of the exponential's argument after affine scaling.Source: C. Recursive computation of integrals · p. 5
  • I0 and I1 are initialized using two error-function evaluations and two exponential-function evaluations.The recurrence then supplies the remaining integrals needed by the approximation.Source: C. Recursive computation of integrals · p. 5
  • Algorithm 1 combines the computed integrals with polynomial coefficients to form T1 and T2, then estimates the output as αi + (βi − αi)(T1/T2).When αi = βi, the output is set directly to f(i).Source: C. Recursive computation of integrals · p. 6

D. Algorithm and implementation

The implementation uses convolutions and recursive integral computations to produce the adaptive bilateral filtering approximation. Its per-pixel complexity is independent of spatial width ρ.

D. Algorithm and implementation

  • The inverse matrix is common to all pixels, so the coefficients c can be computed for all pixels with one matrix-vector multiplication.A closed-form inverse avoids a separate matrix inversion at each pixel.Source: D. Algorithm and implementation · p. 6
  • The algorithm requires four transcendental-function evaluations per pixel, compared with O(ρ^2) evaluations for brute force.These are two evaluations each of the error and exponential functions.Source: D. Algorithm and implementation · p. 6
  • For fixed N, the algorithm has O(1) complexity with respect to spatial width ρ.The Gaussian convolutions dominate runtime; the implementation used imfilter, whose runtime scales with ρ for practical values.Source: D. Algorithm and implementation · p. 6

III. COMPARISONS AND DISCUSSION

The proposed algorithm is at least 20× faster than brute force and often reaches 60× speedup, with timing largely unchanged as ρ varies. Its approximation accuracy improves with polynomial order, and the reported comparison finds it more accurate than in PSNR.

III. COMPARISONS AND DISCUSSION

  • Approximation accuracy is assessed using PSNR between the approximate and brute-force filterings, with 40 dB or higher considered satisfactory.The speedup experiment sets θ(i) = f(i) and uses fixed σ0 for all pixels.Source: §III · p. 6
  • The N = 0 method and fit constant functions over different intervals, which is the only difference between those approaches.For the proposed method the intervals are [αi, βi]; for they are [f(i), 2 f̄(i) − f(i)].Source: §III · pp. 6–7
  • PSNR progressively increases with N, and using the exact αi and βi values yields a few dBs improvement over in the displayed comparison.Figure 3 compares approximations with brute-force bilateral filtering for ρ = 5 and σ0 = 40.Source: §III · p. 7, Figure 3 · p. 7
  • At N = 5, speedup over brute force is at least 20× and often as much as 60×; timing varies little with ρ for fixed N.The timing comparison uses a 512 × 512 image; brute-force timing increases with ρ.Source: §III · p. 7, Table II · p. 7

IV. APPLICATIONS

The section demonstrates adaptive bilateral filtering in sharpening and noise removal, JPEG deblocking, and texture filtering. The texture-filtering method is novel, with results described as competitive with state-of-the-art methods.

IV. APPLICATIONS

  • The algorithm is applied to image sharpening and noise removal, JPEG deblocking, and texture filtering.The first application follows, and the second is a minor modification of.Source: §IV · p. 7
  • The texture-filtering application proposes a new method for texture removal.Its results are described as competitive with state-of-the-art methods.Source: §IV · p. 7
  • For sharpening and JPEG deblocking, the paper identifies speedup from its algorithm as the essential contribution.The sharpening application follows, while the deblocking application is a minor modification of.Source: §IV · p. 7

A. Image sharpening and noise removal

The adaptive bilateral filter is applied to sharpening and noise removal using a per-pixel center and width. The fast result is visually indistinguishable from brute force while running about 40 times faster.

A. Image sharpening and noise removal

B. JPEG deblocking

For JPEG deblocking, the method adapts the range-kernel width using block discontinuities while keeping the center at the input image. Its results are faster than brute force and several alternatives, with a stated quality trade-off against optimization methods.

B. JPEG deblocking

  • The method adapts only the range-kernel width; adapting the spatial-kernel width is beyond its scope.The paper reports satisfactory blocking removal from changing the range width alone.Source: B. JPEG deblocking · p. 8
  • The discontinuity map B(i) uses intensity differences across 8 × 8 block edges, zeros at the four center pixels, and linear interpolation elsewhere.The width σ(i) is set from this map; the center θ(i) is the input JPEG image.Source: B. JPEG deblocking · p. 8
  • About 20× faster than brute-force adaptive bilateral filtering, Algorithm 1 is also faster and performs better than.Its PSNR is about 0.8–1.5 dB below and, which perform best among the compared methods but are quite slow.Source: B. JPEG deblocking · pp. 8–9

C. Texture filtering

The section adapts bilateral filtering for texture removal by using mRTV to set the range-kernel width, smoothing textures while protecting sharp edges. Across three images, the proposed method preserves selected structures and is faster than all but the rolling guidance filter.

C. Texture filtering

  • Setting θ(i) = f(i) and adjusting σ(i) using mRTV makes smoothing aggressive in textured regions while protecting sharp edges.mRTV is high near sharp edges and low in textured regions; σ(i) is computed from a grayscale version of the color image.Source: C. Texture filtering · p. 9
  • To remove coarse textures, the method smooths twice, reducing σ(i) by a factor of 0.8 on the second pass, then sharpens the result.The images are processed channel by channel.Source: C. Texture filtering · p. 9
  • The evaluation compares six methods on three images, using default parameters where possible and otherwise tuning for the best visual output.The methods are,,,,, and.Source: C. Texture filtering · p. 10
  • The method preserves the eye structure in the second image and small-scale structures in the third, while competing methods show edge smearing or residual texture.In the first image, and produce the best filtering, though the proposed method comes close; loses shading, leaves texture, looks blurry, and leaves residual texture near edges.Source: C. Texture filtering · p. 10, Figure 10 · p. 10
  • About 2× faster than, about 5× than, about 3× than, and more than 20× than and; only is faster.The three-image comparison reports timings in Figure 10’s captions.Source: C. Texture filtering · p. 10, Figure 10 · p. 10

V. CONCLUSION

The paper introduces polynomial histogram approximation for fast adaptive bilateral filtering and applies it to sharpening, JPEG deblocking, and texture filtering. The method is at least 20× faster than brute force, while broader applications require a suitable rule for adapting local σ(i).

V. CONCLUSION

  • At least 20× faster than brute force, the polynomial-histogram algorithm can achieve O(1) cost with respect to spatial-filter size when an O(1) spatial-filter implementation is available.The algorithm also works with any spatial filter, not only Gaussians.Source: §V · p. 10
  • The algorithm is demonstrated for sharpening, JPEG deblocking, and texture filtering, with visually similar deblocking outputs to iterative optimization and competitive texture-filtering runtime and performance.The sharpening results are accurate enough to perform image sharpening as proposed in.Source: §V · p. 10
  • Broader application depends on finding a suitable rule for adapting local σ(i); processing color images in joint color space remains an open question.Source: §V · p. 11

VII. APPENDIX

The appendix explains a fixed-cost Gaussian-convolution step and derives an expression by transforming and dividing the numerator and denominator.

A. Proof of Proposition II.2

C. Proof of Proposition II.5

Loading 1811.02308v1…