PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph-Based Blind Image Deblurring From a Single Photograph

Yuanchao Bai, Gene Cheung, Xianming Liu, Wen Gao

arXiv:1802.07929v1cs.CV

TL;DR

Blind image deblurring must recover both a sharp image and unknown blur kernel from a blurry observation, an ill-posed task. The paper uses a graph-based RGTV prior and alternating skeleton/kernel estimation, with graph spectral analysis and Gaussian speedups. Experiments across artificial, real-motion, and Gaussian cases report visually and numerically better reconstructions than state-of-the-art methods.

  • Problem

    Blind image deblurring seeks to recover a latent sharp image without knowing the blur kernel, while existing priors have limitations including sensitivity, assumptions, or high computational cost.

  • Method

    The paper models image patches as weighted-graph signals, uses RGTV to promote skeleton-image edge structure, and alternately estimates the skeleton image and blur kernel through graph spectral filtering.

  • Results

    The proposed algorithm performs competitively or better than state-of-the-art methods across artificial, real-motion, and Gaussian blur experiments, with visually and numerically better reconstructions.

  • Takeaways & Limitations

    RGTV provides an adaptive graph prior with robustness to noise and blur, strong piecewise-smooth filtering, and sharpness promotion for blind deblurring.

Abstract

from arXiv · show

Blind image deblurring, i.e., deblurring without knowledge of the blur kernel, is a highly ill-posed problem. The problem can be solved in two parts: i) estimate a blur kernel from the blurry image, and ii) given estimated blur kernel, de-convolve blurry input to restore the target image. In this paper, we propose a graph-based blind image deblurring algorithm by interpreting an image patch as a signal on a weighted graph. Specifically, we first argue that a skeleton image---a proxy that retains the strong gradients of the target but smooths out the details---can be used to accurately estimate the blur kernel and has a unique bi-modal edge weight distribution. Then, we design a reweighted graph total variation (RGTV) prior that can efficiently promote a bi-modal edge weight distribution given a blurry patch. Further, to analyze RGTV in the graph frequency domain, we introduce a new weight function to represent RGTV as a graph $l_1$-Laplacian regularizer. This leads to a graph spectral filtering interpretation of the prior with desirable properties, including robustness to noise and blur, strong piecewise smooth (PWS) filtering and sharpness promotion. Minimizing a blind image deblurring objective with RGTV results in a non-convex non-differentiable optimization problem. We leverage the new graph spectral interpretation for RGTV to design an efficient algorithm that solves for the skeleton image and the blur kernel alternately. Specifically for Gaussian blur, we propose a further speedup strategy for blind Gaussian deblurring using accelerated graph spectral filtering. Finally, with the computed blur kernel, recent non-blind image deblurring algorithms can be applied to restore the target image. Experimental results demonstrate that our algorithm successfully restores latent sharp images and outperforms state-of-the-art methods quantitatively and qualitatively.

I. INTRODUCTION

Blind image deblurring must jointly recover an unknown sharp image and blur kernel from a single blurry observation, making it unstable and non-unique. The paper introduces an adaptive graph prior and an alternating algorithm that estimates a skeleton image and kernel before non-blind restoration.

  • Problem: Blind deblurring jointly estimates the latent sharp image and unknown blur kernel from one blurry image, making the problem unstable and non-unique.The observation model includes blur and noise, while the inverse problem seeks the latent sharp image.
  • Motivation: Conventional gradient-based priors can favor blurry, low-frequency solutions, motivating more sophisticated priors for blind deblurring.Existing alternatives include l0-norm, sparse-coding, low-rank, dark-channel, and graph-based priors, each with stated limitations.
  • Proposed prior: RGTV promotes a bi-modal edge-weight distribution by reconstructing a piecewise-smooth skeleton image that retains strong gradients while smoothing details.The skeleton image is used as a proxy for estimating the blur kernel rather than directly computing the natural image.
  • Graph spectral interpretation: A new graph weight function expresses GTV and RGTV as graph l1-Laplacian regularizers, enabling a graph-frequency interpretation with robustness to noise and blur and strong PWS filtering.This interpretation also supports sharpness promotion and fast graph spectral filtering.
  • Algorithm: The proposed algorithm alternately solves for the skeleton image and blur kernel, with an additional accelerated graph-filtering strategy for Gaussian blur.The alternating optimization addresses a non-convex, non-differentiable objective; the estimated kernel is then used by a non-blind deblurring method.

B. Graph Based Image Prior

The paper models image patches as graph signals whose edge weights reflect pixel similarity, and uses skeleton images because they preserve sharp structure while smoothing details. Skeleton and natural patches exhibit bi-modal edge-weight distributions unlike blurred patches, motivating a graph-based prior for blind deblurring.

  • A. Definitions in GSP: Graph signal processing represents pixels as graph nodes connected by weighted edges that measure inter-pixel similarity.The graph uses an adjacency matrix whose weights are computed from pixel intensities with a Gaussian kernel.
  • A. Definitions in GSP: Graph Laplacian eigenvalues act as graph frequencies, while eigenvectors provide the corresponding graph-frequency components.The graph Laplacian is positive semidefinite when edge weights are nonnegative.
  • B. Skeleton Image and its Bi-modal Weight Distribution: A skeleton image is a piecewise-smooth proxy that retains strong gradients while smoothing minor details, remaining sharper than the blurred image.The paper uses this proxy instead of directly reconstructing the full natural image for blur-kernel estimation.
  • B. Skeleton Image and its Bi-modal Weight Distribution: Natural and skeleton patches have bi-modal edge-weight distributions, whereas blurred patches do not because blur applies low-pass filtering.Bi-modality corresponds to very small or very large inter-pixel differences and therefore indicates a piecewise-smooth patch.
  • B. Skeleton Image and its Bi-modal Weight Distribution: This statistical distinction motivates designing a signal prior that promotes bi-modal edge weights from a blurry observation.The skeleton patch is described as easier to reconstruct from a blurry patch while remaining valuable for estimating the blur kernel.

IV. GRAPH-BASED IMAGE PRIOR AND ANALYSIS

RGTV extends graph total variation by making graph weights depend on the signal, thereby promoting the bi-modal edge-weight structure associated with sharp, piecewise-smooth patches. Its pairwise regularizer differs fundamentally from fixed-weight GTV, which only encourages smoothing.

  • A. Reweighted Graph Total Variation Prior: RGTV is proposed to promote a bi-modal edge-weight distribution in a target pixel patch.The prior is introduced as the graph-based regularizer for reconstructing a skeleton patch from a blurry observation.
  • A. Reweighted Graph Total Variation Prior: Fixed-weight GTV minimizes a linear pairwise penalty wi,jd with its sole minimum at d = 0, pushing the image toward smoothing.Here d denotes the absolute intensity difference between two nodes.
  • A. Reweighted Graph Total Variation Prior: RGTV makes weights functions of the signal, giving each pair the penalty exp(−d^2/σ^2) · d instead of a fixed-weight linear penalty.This signal-dependent weighting is the central design change from conventional GTV.
  • A. Reweighted Graph Total Variation Prior: The RGTV pairwise penalty has a maximum at σ/2 and minima at 0 and +∞, promoting the desired bi-modal edge-weight distribution.The regularizer reduces d when d is below σ/2, while its overall shape favors very small or very large differences.
  • A. Reweighted Graph Total Variation Prior: The RGTV prior is then used to formulate the blind image-deblurring optimization problem.The paper introduces the optimization function after analyzing the prior’s pairwise behavior.

B. Comparisons with Graph Laplacian Prior

The paper contrasts conventional and reweighted graph Laplacian priors with GTV and RGTV, emphasizing RGTV’s stronger edge-sharpness and spectral filtering properties. Its graph-frequency formulation explains robustness to noise and blur and stronger PWS preservation.

  • Graph Laplacian comparison: Fixed graph Laplacian weights produce a quadratic penalty minimized only at zero inter-pixel difference, so they smooth images instead of promoting bi-modal edge weights.
  • Graph Laplacian comparison: Reweighted graph Laplacian promotes bi-modal edge weights through two minima, but its derivative vanishes near zero, slowing that promotion in practice.
  • RGTV advantage: RGTV retains a derivative limit of 1 near zero and experimentally restores a sharper skeleton image than reweighted graph Laplacian.
  • Spectral interpretation: Rewriting GTV with an l1-Laplacian operator supplies a graph-frequency interpretation and shows that GTV penalizes high graph frequencies more severely than graph Laplacian regularization.
  • Spectral interpretation: GTV’s lowest AC frequency component is more robust to noise and blur and provides stronger PWS filtering than the conventional graph Laplacian regularizer.
  • RGTV spectral behavior: RGTV inherits GTV’s spectral robustness and PWS filtering while promoting bi-modal edge weights, with iterative filtering increasing edge sharpness.

V. BLIND IMAGE DEBLURRING ALGORITHM

The blind deblurring algorithm formulates data fidelity and RGTV-based regularization jointly, then solves the non-convex problem across an image pyramid. It alternates skeleton-image and kernel estimation before applying non-blind restoration.

  • Objective: The proposed blind deblurring objective combines convolutional data fidelity with RGTV regularization for the image and l2 regularization for the blur kernel.
  • Optimization strategy: Because the objective is non-convex and non-differentiable, the method uses a coarse-to-fine image pyramid and alternates image and kernel estimation at each scale.
  • Optimization strategy: Each scale initializes the kernel from a delta function or coarser result, repeatedly updates the skeleton image and kernel, and decreases β by 1.1 until convergence.
  • Restoration pipeline: The estimated skeleton image serves as a PWS proxy for obtaining a suitable blur kernel, after which recent non-blind methods restore the natural sharp image.

A. Skeleton Image Restoration

With the blur kernel fixed, skeleton restoration becomes a quadratic graph-regularized problem. The solver alternates linear-system updates with graph-operator reweighting and uses conjugate gradients plus convolutional acceleration.

  • Restoration subproblem: Fixing the estimated kernel converts skeleton restoration into a non-blind deblurring problem with a graph Laplacian regularizer.
  • Restoration subproblem: The resulting quadratic convex optimization is equivalent to solving a linear system involving the convolution operator and l1-Laplacian matrix.
  • Numerical solution: The system matrix is real symmetric positive definite, and its condition number can be checked numerically for stability.
  • Numerical solution: Conjugate Gradient solves the system efficiently, while FFT implements convolution and local graph filtering avoids explicit matrix computation.
  • Alternating updates: The algorithm alternates updates of the skeleton image and l1-Laplacian operator, recomputing graph weights from the current image until convergence.

B. Blur Kernel Estimation

The blur kernel is estimated in the gradient domain from the restored skeleton image, using a convex quadratic problem with a closed-form FFT-accelerated solver.

  • The kernel subproblem is modified to the gradient domain to avoid artifacts during blur-kernel estimation.
  • The resulting optimization is quadratic and convex, enabling a closed-form deconvolution-like solver accelerated with FFT.
  • Kernel estimation is over-determined because the blur kernel is much smaller than the image, so restored sharp edges in the skeleton suffice.

C. Acceleration for Specific Gaussian Blur Deblurring

For Gaussian blur, the method approximates convolution with a graph filter and accelerates skeleton restoration through shared graph-frequency bases and Lanczos filtering.

  • The Gaussian-blur acceleration replaces the estimated kernel with the smoothing graph filter I + a · LΓ, initialized using an unweighted graph Laplacian.
  • The filter parameter is learned as a = −0.07 from sharp and Gaussian-blurred image pairs using least squares.
  • The modified skeleton-restoration objective uses (I + a · LΓ)x − b with an RGTV regularizer.
  • Sharing graph-frequency bases makes the solution a polynomial graph filter that can be implemented with accelerated Lanczos iterations.
  • Algorithm 3 iteratively updates the skeleton image, graph Laplacian, and filter parameter, then estimates the kernel and outputs both results.

VI. EXPERIMENTS AND DISCUSSIONS

Experiments evaluate the proposed algorithms on artificial, real-motion, and Gaussian-blurred images using qualitative and quantitative comparisons with existing blind deblurring methods.

  • The evaluation covers artificial, real-motion, and Gaussian-blurred cases, comparing the proposed algorithms with leading existing blind deblurring methods.
  • The artificial database contains 640 grayscale blurry images generated from 80 sharp images, eight blur kernels, and 1% white Gaussian noise.
  • The comparison uses error ratios, where r ≥ 1 and smaller values indicate better restoration; r ≤ 5 defines successful deblurring.
  • The proposed algorithm is superior across mean error ratio, worst error ratio, and success rate, while producing more robust results on challenging examples.

B. Real Motion Blurred Images

On real motion-blurred and Gaussian-like images, the proposed methods robustly estimate kernels, reduce artifacts, and achieve competitive or better restoration than compared methods, with Gaussian acceleration improving speed.

  • B. Real Motion Blurred Images: Real motion experiments include varying depth of field, mixed human-and-scene images, and more complex or severe motions.
  • B. Real Motion Blurred Images: The proposed method robustly estimates blur kernels and produces fewer artifacts, outperforming several methods visually while remaining competitive with Pan et al.
  • C. Gaussian Blurred Images: For Gaussian-like blur, Algorithm 3 estimates kernels similar to ground truth and sharpens images without artifacts.
  • C. Gaussian Blurred Images: Algorithm 3 is significantly faster than competing algorithms at the same or slightly better PSNR, while both proposed algorithms outperform competitors in these experiments.
  • VII. CONCLUSION: The RGTV framework is mainly scoped to uniform blur following the convolution model, with non-uniform camera-motion deblurring identified as future work.

APPENDIX A DERIVATION OF WEIGHT FUNCTION OF GTV

The appendix stabilizes the GTV sub-derivative near equal neighboring values and establishes bounded spectral behavior for the associated graph Laplacian.

  • Weight-function derivation: GTV’s non-differentiability is handled by taking its sub-differential.The resulting expression motivates the subsequent numerical approximation.
  • Weight-function derivation: When |x_i−x_j|<ϵ, the sub-differential weight is approximated for numerical stability using a small constant ϵ.This replaces the unstable denominator as neighboring signal values approach one another.
  • Weight-function derivation: The approximation is the derivative of an upper-bound function, which defines the adjacency weights used for GTV spectral analysis.The upper-bound construction agrees with GTV except in the ϵ-neighborhood and converges as ϵ approaches zero.
  • Spectral bounds: The graph Laplacian is positive semidefinite, so zero is its lowest eigenvalue with the constant vector as an eigenvector.Its upper boundedness is established using the Gershgorin Circle Theorem; since node degree d_i≤n, λ is bounded for fixed ϵ.
  • Spectral bounds: Because d_i≤n, the relevant eigenvalue λ is upper-bounded for fixed ϵ.This provides the stated finite spectral bound for the graph construction.

APPENDIX C PROOF OF POSITIVE DEFINITENESS

The proof shows that the combined blur and graph-Laplacian quadratic form is positive definite when the blur kernel and graph satisfy the stated conditions.

  • Positive definiteness: Therefore, the combined matrix ˆK^TˆK+2βL_Γ is positive definite for β>0.The proof sets β=0.5 without loss of generality.
  • Positive semidefiniteness: The sum of the blur Gram matrix and graph Laplacian is positive semidefinite because both quadratic forms are nonnegative.The graph term is nonnegative when graph weights γ_i,j are nonnegative.
  • Positive definiteness: Strict positivity follows by proving that the nullspaces of the two positive semidefinite matrices do not intersect.The proof defines the corresponding zero sets S1 and S2 and establishes S1∩S2=∅.
  • Positive definiteness: For a connected graph Laplacian, the zero-eigenspace consists only of the constant vector 1.The multiplicity of the zero eigenvalue is one.
  • Positive definiteness: A normalized nonnegative blur kernel preserves the constant vector, so 1 is an eigenvector of the blur operator with eigenvalue 1 and cannot belong to S1.This uses the assumptions k_i≥0 and Σ_i k_i=1, together with suitable boundary conditions.
Loading 1802.07929v1…