Local Kernels That Approximate Bayesian Regularization and Proximal Operators

Frank Ong, Peyman Milanfar, Pascal Getreuer

TL;DR

This paper builds a mathematical bridge between slow, iterative global optimization (Bayesian regularization) and fast, one-shot local image filtering. By leveraging the graph Laplacian operator, the authors show how to derive specific local kernels that approximate complex global priors, enabling high-quality image restoration at speeds suitable for mobile devices.

What Problem Does This Paper Address?

In image processing, there are two dominant but historically separate worlds:

  1. Variational/Bayesian Methods: These use explicit "priors" (like Total Variation) to define what a "clean" image should look like. They are mathematically elegant and powerful but require slow, iterative global optimization to solve.
  2. Kernel-based Filtering: These are intuitive, local operations like the Bilateral Filter or Non-Local Means. They are incredibly fast and "one-shot," but they often lack a formal statistical justification—we use them because they work, not necessarily because they minimize a specific global energy function.

The challenge is: Can we get the best of both worlds? Can we take a sophisticated global prior and implement it as a fast, local filter? Or, conversely, can we look at a popular local filter and understand exactly what global objective it is implicitly trying to solve?

Methods

The authors establish a formal connection using the concept of proximal operators and the graph Laplacian.

  • The "Shrinkage" Approximation: For small noise levels ($\sigma^2$), the authors show that the Maximum A Posteriori (MAP) estimate—which usually requires many iterations—can be approximated by a single "explicit Euler step": $\hat{x} \approx x - \sigma^2 \nabla \phi(x)$, where $\phi$ is the regularization function.
  • The Laplacian Link: The core innovation is relating the gradient of the loss function ($\nabla \phi$) to the graph Laplacian ($L$). They propose a First-Order Relationship: $\nabla \phi(x) \approx \frac{1}{\sigma^2} L(x)x$. Since the Laplacian is defined by the filter weights ($L = I - W$), this allows them to map a specific loss function directly to a specific kernel.
  • Isotropic Mapping: For a wide class of "isotropic" losses (those that only care about the magnitude of differences, not direction), they provide a closed-form formula to convert a loss function $\rho(t)$ into a kernel $k(t)$.
  • Second-Order Analysis: They also explore a second-order relationship where the Hessian of the loss function relates to the Laplacian, providing a geometric interpretation: the filter weights are essentially assigned by the local curvature of the loss function.

Datasets

The paper focuses on theoretical framework validation rather than large-scale benchmarking. It uses standard image processing test cases:

  • Standard Images: "Butterfly," "Parrots," and "Lighthouse" are used to qualitatively and quantitatively compare the approximations against exact global solutions.
  • Synthetic Noise: Images are corrupted with zero-mean Gaussian white noise to test denoising performance.

Key Insights and Ideas

  • Common Kernels are "Robust": One of the most striking "aha moments" is that the most common kernel in image processing—the Gaussian kernel—actually implies a "robust" loss function known as the Welsch loss. This explains why Gaussian-based filters like Non-Local Means are so good at ignoring outliers.
  • Total Variation as a Local Filter: The authors show that the famous (but computationally expensive) Total Variation (TV) prior can be implemented as a local filter using a $1/|t|$ kernel.
  • The "One-Shot" Advantage: For small regularization parameters, you don't need to iterate. A single pass of a "kernelized" version of a global prior behaves almost identically to the ideal global solution.
  • Reverse Engineering: The framework allows researchers to take an ad hoc filter and "unmask" its underlying Bayesian prior, providing a principled way to analyze and improve existing heuristics.

Key Results

  • TV Approximation: In a denoising experiment, the first-order local approximation of Huber-Total Variation achieved a PSNR of 37.10 dB, which is qualitatively and quantitatively very close to the iterative global solution, despite being a non-iterative local operation.
  • Bilateral Filter Accuracy: When approximating the Bilateral Filter as a MAP problem, the first-order approximation achieved a high PSNR of 48.48 dB (for $\sigma=30$), significantly outperforming the second-order approximation (42.75 dB).
  • Efficiency: The paper demonstrates that for small $\sigma$, the approximation error is bounded by the Hessian of the loss, proving that local operations are sufficient for many practical restoration tasks.

Limitations and Future Work

  • Small Noise Assumption: The "one-shot" approximation relies on $\sigma^2$ being relatively small. As noise or regularization strength increases, the approximation becomes less accurate, and iterations may still be required.
  • The Inverse Problem: While going from a loss to a kernel is straightforward for isotropic cases, the reverse—finding a valid loss function for an arbitrary kernel—is a much harder "Monge-Ampère" type problem that remains an open question in high dimensions.
  • Non-Isotropic Losses: The second-order analysis, while theoretically interesting for non-isotropic cases, proved to be less accurate in practice than the first-order approach. Future work could refine these higher-order approximations.

Summary updated

Abstract

In this paper, we broadly connect kernel-based filtering (e.g., approaches such as the bilateral filter and non-local means, but also many more) with general variational formulations of Bayesian regularized least squares and the related concept of proximal operators. Variational/Bayesian/proximal formulations often result in optimization problems that do not have closed-form solutions and therefore typically require global iterative solutions. Our main contribution here is to establish how one can approximate the solution of the resulting global optimization problems using locally adaptive filters with specific kernels. Our results are valid for small regularization strength (i.e., weak noise), but the approach is powerful enough to be useful for a wide range of applications because we expose how to derive a “kernelized” solution to these problems that approximates the global solution in one shot, using only local operations. As another side benefit in the reverse direction, given a local data-adaptive filter constructed with a particular choice of kernel, we enable the interpretation of such filters in the variational/Bayesian/proximal framework.
BibTeX
@article{ong2019local,
  author = {Frank Ong and Peyman Milanfar and Pascal Getreuer},
  title = {{Local Kernels That Approximate Bayesian Regularization and Proximal Operators}},
  journal = {IEEE Trans. Image Process.},
  year = {2019},
  url = {https://openreview.net/forum?id=fie8RuUTqs},
}

Loading related content...

Figure