Fast Image Deconvolution using Hyper-Laplacian Priors

Dilip Krishnan, Rob FergusNeurIPS 2009 · OpenReview

TL;DR

This paper introduces a breakthrough in image deblurring by making high-quality "hyper-Laplacian" priors computationally practical. By using a clever "half-quadratic splitting" technique, the authors achieve a 100x to 350x speedup over existing methods, deconvolving megapixel images in seconds rather than minutes without sacrificing image quality.

What Problem Does This Paper Address?

In the world of image processing, "deconvolution" is the task of reversing blur (like camera shake) to recover a sharp image. To do this well, algorithms need a prior—a mathematical model of what a "natural" image looks like.

Researchers have long known that natural image gradients follow a "heavy-tailed" distribution. While Gaussian or Laplacian ($\ell_1$) priors are mathematically convenient and fast to solve, they don't perfectly capture these statistics, often resulting in mediocre reconstructions.

Log probability plot of image gradients

The "Hyper-Laplacian" distribution ($|x|^\alpha$ where $0.5 \le \alpha \le 0.8$) is a much better fit for real-world scenes, as seen in the empirical data. However, using it makes the optimization problem non-convex, which historically meant using agonizingly slow iterative solvers (like Iteratively Reweighted Least Squares, or IRLS) that could take 20 minutes to process a single 1-megapixel photo.

Methods

The authors propose a fast alternating minimization scheme based on half-quadratic splitting. They break the complex deconvolution cost function into two simpler sub-problems that are solved iteratively:

  1. The $x$-subproblem: This handles the global structure of the image. Because it is quadratic, it can be solved extremely efficiently in the frequency domain using Fast Fourier Transforms (FFTs).
  2. The $w$-subproblem: This handles the non-convex hyper-Laplacian prior. Crucially, this step is separable, meaning it can be solved independently for every single pixel.

The "secret sauce" of the paper lies in how they solve this $w$-subproblem. They offer two novel paths:

  • Lookup Tables (LUT): Since the sub-problem only depends on two variables, they precompute the solutions and store them in a table. This allows for near-instantaneous solving for any value of $\alpha$.
  • Analytic Solutions: They demonstrate that for specific values of $\alpha$ (1/2 and 2/3), the problem can be solved exactly by finding the roots of cubic and quartic polynomials, respectively.

Datasets

The authors evaluated their algorithm using:

  • Test Images: 7 in-focus grayscale real-world images.
  • Blur Kernels: 8 different real-world camera shake kernels (ranging from $13 \times 13$ to $41 \times 41$ pixels) sourced from previous literature.
  • Noise: They added 1% Gaussian noise and quantized the images to 255 levels to simulate realistic digital camera output.

Key Insights and Ideas

  • Separability is the Solution: The primary insight is realizing that the non-convexity of the hyper-Laplacian prior is only a bottleneck if it's coupled with the blur kernel. By splitting the variables, the non-convexity becomes a 1D per-pixel problem that is trivial to solve.
  • Mathematical Shortcuts: Identifying that $\alpha=1/2$ and $\alpha=2/3$ lead to solvable polynomials provides a rigorous alternative to numerical approximation.
  • Speed-Quality Tradeoff: The paper proves that you don't have to choose between the high quality of sparse priors and the speed of simple filters. Their method achieves Signal-to-Noise Ratio (SNR) levels comparable to the "gold standard" IRLS but at a fraction of the time.

Key Results

  • Massive Speedup: For a 1-megapixel image, the proposed method takes roughly 3 seconds, compared to 20 minutes for the standard IRLS approach.
  • Performance Scaling: The speedup factor (70x to 350x) remains consistent regardless of image size.
Deconvolved image using the proposed method
  • Superior Quality: In quantitative tests, the hyper-Laplacian approach (e.g., $\alpha=2/3$) consistently outperformed standard $\ell_2$ (Gaussian) and $\ell_1$ (Laplacian/TV) methods in terms of SNR gain. As shown above, the proposed method achieves high visual quality and competitive SNR in just over a second, whereas traditional IRLS methods take hundreds of seconds for similar output.

Limitations and Future Work

  • Boundary Artifacts: Like many FFT-based methods, the algorithm assumes "circular" boundary conditions. This can lead to artifacts at the edges of the image, though standard edge-tapering techniques can mitigate this.
  • Non-Blind Only: This paper focuses on non-blind deconvolution, where the blur kernel is already known. While the authors suggest their fast solver could be used inside a "blind" deconvolution loop (where the kernel is unknown), they do not demonstrate that application here.
  • Generalization: The framework could easily be adapted to other tasks like image denoising or super-resolution, which remains a promising direction for future implementation.

Summary updated

Abstract

The heavy-tailed distribution of gradients in natural scenes have proven effective priors for a range of problems such as denoising, deblurring and super-resolution. However, the use of sparse distributions makes the problem non-convex and impractically slow to solve for multi-megapixel images. In this paper we describe a deconvolution approach that is several orders of magnitude faster than existing techniques that use hyper-Laplacian priors. We adopt an alternating minimization scheme where one of the two phases is a non-convex problem that is separable over pixels. This per-pixel sub-problem may be solved with a lookup table (LUT). Alternatively, for two specific values of α, 1/2 and 2/3 an analytic solution can be found, by finding the roots of a cubic and quartic polynomial, respectively. Our approach (using either LUTs or analytic formulae) is able to deconvolve a 1 megapixel image in less than ∼3 seconds, achieving comparable quality to existing methods such as iteratively reweighted least squares (IRLS) that take ∼20 minutes. Furthermore, our method is quite general and can easily be extended to related image processing problems, beyond the deconvolution application demonstrated.
BibTeX
@inproceedings{krishnan2009fast,
  author = {Dilip Krishnan and Rob Fergus},
  title = {{Fast Image Deconvolution using Hyper-Laplacian Priors}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=HkbJzDbObr},
}
Figure