# Random Walk Graph Laplacian based Smoothness Prior for Soft Decoding of JPEG Images

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jul 2016.

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

- [NTIRE 2021 Challenge on Image Deblurring](https://mlsanity.com/paper/2104.14854/) (2021)
- [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)
- [Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment](https://mlsanity.com/paper/2208.08726/) (2022)
- [Efficient Learning of Balanced Signed Graphs via Iterative Linear Programming](https://mlsanity.com/paper/2409.07794/) (2024)
- [Retinex-based Image Denoising / Contrast Enhancement using Gradient Graph Laplacian Regularizer](https://mlsanity.com/paper/2307.02625/) (2023)
- [Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment](https://mlsanity.com/paper/2110.11420/) (2021)
- [Fast Computation of Generalized Eigenvectors for Manifold Graph Embedding](https://mlsanity.com/paper/2112.07862/) (2021)
- [Graph Unfolding and Sampling for Transitory Video Keyframe Selection via Gershgorin Disc Alignment](https://mlsanity.com/paper/2408.01859/) (2024)
- [Constructing an Interpretable Deep Denoiser by Unrolling Graph Laplacian Regularizer](https://mlsanity.com/paper/2409.06676/) (2024)
- [Unrolling Nonconvex Graph Total Variation for Image Denoising](https://mlsanity.com/paper/2506.02381/) (2025)
- [Low-rank Updates in Slowly Time-varying Graphs for Spatial-Temporal Signal Interpolation](https://mlsanity.com/paper/2606.24011/) (2026)

## Abstract (arXiv)

Given the prevalence of JPEG compressed images, optimizing image reconstruction from the compressed format remains an important problem. Instead of simply reconstructing a pixel block from the centers of indexed DCT coefficient quantization bins (hard decoding), soft decoding reconstructs a block by selecting appropriate coefficient values within the indexed bins with the help of signal priors. The challenge thus lies in how to define suitable priors and apply them effectively. In this paper, we combine three image priors---Laplacian prior for DCT coefficients, sparsity prior and graph-signal smoothness prior for image patches---to construct an efficient JPEG soft decoding algorithm. Specifically, we first use the Laplacian prior to compute a minimum mean square error (MMSE) initial solution for each code block. Next, we show that while the sparsity prior can reduce block artifacts, limiting the size of the over-complete dictionary (to lower computation) would lead to poor recovery of high DCT frequencies. To alleviate this problem, we design a new graph-signal smoothness prior (desired signal has mainly low graph frequencies) based on the left eigenvectors of the random walk graph Laplacian matrix (LERaG). Compared to previous graph-signal smoothness priors, LERaG has desirable image filtering properties with low computation overhead. We demonstrate how LERaG can facilitate recovery of high DCT frequencies of a piecewise smooth (PWS) signal via an interpretation of low graph frequency components as relaxed solutions to normalized cut in spectral clustering. Finally, we construct a soft decoding algorithm using the three signal priors with appropriate prior weights. Experimental results show that our proposal outperforms state-of-the-art soft decoding algorithms in both objective and subjective evaluations noticeably.