Sparsity Averaging for Compressive Imaging

Rafael E. Carrillo, Jason D. McEwen, Dimitri Van De Ville, Jean-Philippe Thiran, Yves Wiaux

Abstract

Compressed sensing (CS) enables the reconstruction of high-resolution signals from a limited set of measurements, provided the signal is sparse in a transform domain. This paper introduces the Sparsity Averaging Reweighted Analysis (SARA) algorithm, which leverages the observation that natural images are simultaneously sparse across multiple wavelet frames. By employing a reweighted $\ell_1$ minimization approach on a concatenated dictionary of Daubechies bases, SARA significantly improves reconstruction quality and reduces visual artifacts compared to standard Total Variation (TV) and single-basis methods.

Introduction

In the field of Compressive Imaging, the goal is to reconstruct a signal from a small number of measurements. This is traditionally achieved by exploiting signal sparsity in a single basis (e.g., wavelets) or the gradient domain (Total Variation). However, natural images are complex; sharp edges may be sparse in one domain, while textures are better represented in another.

We propose that picking a single "best" basis is insufficient. Instead, SARA exploits the fact that images exhibit sparsity across many different frames simultaneously. By promoting "average sparsity" across a redundant dictionary, we can achieve more robust and accurate reconstructions.

Methodology

The SARA algorithm is built on three core pillars:

  1. Redundant Dictionary: The authors concatenate the first eight Daubechies wavelet bases (Db1-Db8) into a single redundant dictionary. Interestingly, the coherence (similarity) between these frames is found to be a feature that strengthens the average sparsity prior.
  2. Analysis Formulation: Unlike synthesis methods that build images from atoms, SARA uses an analysis approach, evaluating the coefficients produced when the image is projected onto the dictionary.
  3. Reweighted $\ell_1$ Minimization: To approximate the computationally difficult $\ell_0$ norm (the true measure of sparsity), SARA uses a sequence of weighted $\ell_1$ problems. Weights are updated iteratively to be the inverse of previous coefficients, effectively pushing small coefficients toward zero and suppressing noise.

The underlying convex optimization problem is solved efficiently using the Douglas-Rachford splitting proximal algorithm.

Experimental Results

SARA was evaluated against standard benchmarks, including the Lena image and MR brain scans. Quantitative results demonstrate that SARA consistently outperforms state-of-the-art methods like TV, BPDb8, and Curvelets, as well as their reweighted counterparts.

Quantitative performance of SARA showing superior SNR across different bases, undersampling ratios (M/N), and noise levels (ISNR).

As shown in the performance plots, SARA achieves SNR gains between 0.9 and 1.9 dB over the next best methods across various undersampling ratios. It also maintains superior performance as measurement noise increases.

Qualitatively, SARA reconstructions show a dramatic reduction in artifacts. While TV often produces "cartoon-like" blocky images due to its piecewise-smoothness prior, SARA preserves fine details and textures much more naturally.

Visual comparison of Lena reconstructions. SARA (right) shows significantly fewer artifacts and better detail preservation than standard reweighted methods.

Conclusion

SARA demonstrates that average sparsity across multiple frames is a powerful prior for compressive imaging. By bridging the gap between $\ell_1$ and $\ell_0$ norms through reweighting, the algorithm effectively "zeros out" artifacts while preserving essential image features. Future work will explore theoretical sampling bounds for concatenated frames and investigate the computational optimization of these redundant dictionaries.

Summary updated

Abstract

We discuss a novel sparsity prior for compressive imaging in the context of the theory of compressed sensing with coherent redundant dictionaries, based on the observation that natural images exhibit strong average sparsity over multiple coherent frames. We test our prior and the associated algorithm, based on an analysis reweighted $\ell_1$ formulation, through extensive numerical simulations on natural images for spread spectrum and random Gaussian acquisition schemes. Our results show that average sparsity outperforms state-of-the-art priors that promote sparsity in a single orthonormal basis or redundant frame, or that promote gradient sparsity. Code and test data are available at https://github.com/basp-group/sopt.
BibTeX
@article{carrillo2012sparsity,
  author = {Rafael E. Carrillo and Jason D. McEwen and Dimitri Van De Ville and Jean-Philippe Thiran and Yves Wiaux},
  title = {{Sparsity Averaging for Compressive Imaging}},
  journal = {IEEE Signal Processing Letters},
  year = {2012},
  doi = {10.1109/lsp.2013.2259813},
}
Figure