Blind Image Deblurring via Reweighted Graph Total Variation

Yuanchao Bai, Gene Cheung, Xianming Liu, Wen Gao

Blind image deblurring remains a classic "chicken-and-egg" problem in computer vision. To recover a sharp image, the blur kernel (representing motion or focus loss) must be known; conversely, to estimate the kernel accurately, a sharp image is typically required. Mathematically, this problem is highly ill-posed, as infinitely many image-kernel pairs can produce the same blurry observation. Traditional approaches rely on statistical priors—assumptions about natural image properties—to regularize the solution. However, many standard priors inadvertently favor blurry images because they possess lower overall energy in the frequency domain.

Methodology: Reweighted Graph Total Variation (RGTV)

This paper introduces a novel approach leveraging Graph Signal Processing (GSP) to overcome these limitations. The authors propose a two-stage framework: first, estimating the blur kernel using a simplified "skeleton" version of the image, and second, applying this kernel with standard non-blind deblurring tools to restore the final image.

The core innovation is the Reweighted Graph Total Variation (RGTV) prior. In this model, the image is represented as a graph where pixels serve as nodes and edges represent similarities between them. Unlike standard Graph Total Variation (GTV) which uses fixed weights, RGTV employs weights that are functions of the image itself. This creates a feedback loop during optimization: as the algorithm progresses, it pushes edge weights toward a bi-modal distribution—either very high for smooth regions or very low for sharp structural boundaries. This mechanism effectively prevents the "mushy" gradients typical of blurred images.

Evolution of the skeleton image and edge characteristics during deblurring.

The "skeleton image" acts as a piecewise smooth proxy. It retains strong structural edges while smoothing out fine textures and noise, providing a more reliable guide for kernel estimation than a full reconstruction. The optimization uses an alternating minimization scheme in a coarse-to-fine strategy, allowing the system to handle large blur kernels robustly.

Key Insights: The Bi-modal Signature

A critical observation of this research is that sharp images (and their skeletonized versions) possess a unique statistical signature in their graph edge weights. In a sharp image, neighboring pixels are either very similar (within smooth regions) or significantly different (across edges). Blurry images lack this clear separation, showing a broad distribution of intermediate differences.

RGTV is specifically designed to enforce this bi-modality. The authors demonstrate that while a Reweighted Graph Laplacian could theoretically achieve similar results, RGTV provides significantly faster and more stable convergence, making it practical for real-world deblurring tasks.

Results and Performance

The proposed method was evaluated on challenging natural images with significant motion blur, including well-known test cases such as "Flower," "Picasso," and "Roma." The RGTV method demonstrated remarkable robustness, successfully estimating kernels as large as 95x95 pixels—a range where many traditional gradient-based methods fail.

Qualitatively, the resulting images exhibit fewer "ringing" artifacts and sharper edges compared to contemporary state-of-the-art methods. By simply replacing traditional priors with RGTV, the authors achieved results competitive with or superior to more complex techniques like Dark Channel Priors or internal patch recurrence.

Limitations and Future Directions

Despite its effectiveness, the method is computationally intensive due to the alternating optimization and primal-dual algorithms required for the RGTV sub-problem. Additionally, like most optimization-based approaches, it requires careful tuning of hyperparameters. Because the final restoration depends on a separate non-blind deblurring step, any artifacts introduced by that secondary tool remain outside the control of the RGTV kernel estimation. Future research may explore integrating RGTV into end-to-end deep learning frameworks to combine the strengths of graph-based priors with neural network efficiency.

Summary updated

Abstract

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, by interpreting an image patch as a signal on a weighted graph, 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. We then design a reweighted graph total variation (RGTV) prior that can efficiently promote bi-modal edge weight distribution given a blurry patch. However, minimizing a blind image deblurring objective with RGTV results in a non-convex non-differentiable optimization problem. We propose a fast algorithm that solves for the skeleton image and the blur kernel alternately. Finally with the computed blur kernel, recent non-blind image deblurring algorithms can be applied to restore the target image. Experimental results show that our algorithm can robustly estimate the blur kernel with large kernel size, and the reconstructed sharp image is competitive against the state-of-the-art methods.
BibTeX
@inproceedings{bai2017blind,
  author = {Yuanchao Bai and Gene Cheung and Xianming Liu and Wen Gao},
  title = {{Blind Image Deblurring via Reweighted Graph Total Variation}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2017},
  doi = {10.1109/icassp.2018.8462255},
}
Figure