# Graph-Based Blind Image Deblurring From a Single Photograph

arXiv: https://arxiv.org/abs/1802.07929 · HTML: https://mlsanity.com/paper/1802.07929/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Feb 2018.

## Built on by (most cited first, 24 of 24)

- [Deep Point Set Resampling via Gradient Fields](https://mlsanity.com/paper/2111.02045/) (2021)
- [Interpretable Lightweight Transformer via Unrolling of Learned Graph Smoothness Priors](https://mlsanity.com/paper/2406.04090/) (2024)
- [Total Variation Graph Neural Networks](https://mlsanity.com/paper/2211.06218/) (2022)
- [Unfolding Taylor's Approximations for Image Restoration](https://mlsanity.com/paper/2109.03442/) (2021)
- [Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment](https://mlsanity.com/paper/2208.08726/) (2022)
- [GeodesicPSIM: Predicting the Quality of Static Mesh with Texture Map via Geodesic Patch Similarity](https://mlsanity.com/paper/2308.04928/) (2023)
- [Training Adaptive Reconstruction Networks for Blind Inverse Problems](https://mlsanity.com/paper/2202.11342/) (2022)
- [Blind Image Deblurring based on Kernel Mixture](https://mlsanity.com/paper/2101.06241/) (2021)
- [Monitoring and Adapting the Physical State of a Camera for Autonomous Vehicles](https://mlsanity.com/paper/2112.05456/) (2021)
- [Retinex-based Image Denoising / Contrast Enhancement using Gradient Graph Laplacian Regularizer](https://mlsanity.com/paper/2307.02625/) (2023)
- [A Comprehensive Survey on Deep Neural Image Deblurring](https://mlsanity.com/paper/2310.04719/) (2023)
- [Efficient Concertormer for Image Deblurring and Beyond](https://mlsanity.com/paper/2404.06135/) (2024)
- [Blind Image Deblurring with FFT-ReLU Sparsity Prior](https://mlsanity.com/paper/2406.08344/) (2024)
- [Graph-Based Depth Denoising & Dequantization for Point Cloud Enhancement](https://mlsanity.com/paper/2111.04946/) (2021)
- [PI-AstroDeconv: A Physics-Informed Unsupervised Learning Method for Astronomical Image Deconvolution](https://mlsanity.com/paper/2403.01692/) (2024)
- [Unsupervised Graph Spectral Feature Denoising for Crop Yield Prediction](https://mlsanity.com/paper/2208.02714/) (2022)
- [Random Weights Networks Work as Loss Prior Constraint for Image Restoration](https://mlsanity.com/paper/2303.16438/) (2023)
- [Constructing an Interpretable Deep Denoiser by Unrolling Graph Laplacian Regularizer](https://mlsanity.com/paper/2409.06676/) (2024)
- [Lightweight and Interpretable Transformer via Mixed Graph Algorithm Unrolling for Traffic Forecast](https://mlsanity.com/paper/2505.13102/) (2025)
- [Unrolling Nonconvex Graph Total Variation for Image Denoising](https://mlsanity.com/paper/2506.02381/) (2025)
- [Unrolling Graph-based Douglas-Rachford Algorithm for Image Interpolation with Informed Initialization](https://mlsanity.com/paper/2509.11926/) (2025)
- [Saturation-Aware Space-Variant Blind Image Deblurring](https://mlsanity.com/paper/2604.16200/) (2026)
- [See Silhouettes in Motion with Neuromorphic Vision](https://mlsanity.com/paper/2605.17984/) (2026)
- [Low-rank Updates in Slowly Time-varying Graphs for Spatial-Temporal Signal Interpolation](https://mlsanity.com/paper/2606.24011/) (2026)

## Abstract (arXiv)

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 l1-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.