Source-linked AI summary
Image Compressive Sensing Recovery Using Adaptively Learned Sparsifying Basis via L0 Minimization
Jian Zhang, Chen Zhao, Debin Zhao, Wen Gao
TL;DR
The paper addresses poor image CS recovery from fixed sparsifying domains that do not fit non-stationary natural images. It uses adaptively learned bases for overlapped patch representations with L0 minimization, solved by split Bregman iterations, and reports significant improvements over many state-of-the-art schemes with good convergence. The authors note that the non-convex objective prevents a theoretical proof of global convergence.
Problem
Fixed DCT, wavelet, and gradient domains are not adaptive to non-stationary natural images and therefore do not achieve sufficiently high sparsity for image CS recovery.
Method
The framework sparsely represents overlapped image patches with an adaptively learned sparsifying basis under L0 minimization and solves the non-convex problem using split Bregman iterations.
Results
The algorithm achieves significant performance improvements over many current state-of-the-art schemes and exhibits good convergence on a wide range of natural images.
Takeaways & Limitations
Adaptive redundant patch-based sparse representation provides the paper’s basis for characterizing natural-image sparsity in CS recovery.
Takeaways & Limitations
Because the objective is non-convex, the paper does not provide a theoretical proof of global convergence.
Abstract
from arXiv · showhide
From many fewer acquired measurements than suggested by the Nyquist sampling theory, compressive sensing (CS) theory demonstrates that, a signal can be reconstructed with high probability when it exhibits sparsity in some domain. Most of the conventional CS recovery approaches, however, exploited a set of fixed bases (e.g. DCT, wavelet and gradient domain) for the entirety of a signal, which are irrespective of the non-stationarity of natural signals and cannot achieve high enough degree of sparsity, thus resulting in poor CS recovery performance. In this paper, we propose a new framework for image compressive sensing recovery using adaptively learned sparsifying basis via L0 minimization. The intrinsic sparsity of natural images is enforced substantially by sparsely representing overlapped image patches using the adaptively learned sparsifying basis in the form of L0 norm, greatly reducing blocking artifacts and confining the CS solution space. To make our proposed scheme tractable and robust, a split Bregman iteration based technique is developed to solve the non-convex L0 minimization problem efficiently. Experimental results on a wide range of natural images for CS recovery have shown that our proposed algorithm achieves significant performance improvements over many current state-of-the-art schemes and exhibits good convergence property.
1. Introduction
Image compressive sensing seeks recovery from far fewer measurements, but fixed sparsifying domains do not adapt to non-stationary natural images. The paper proposes adaptive learned patch bases with L0 minimization and reports competitive recovery performance.
- Motivation: CS can reconstruct sparse signals from many fewer measurements than Nyquist sampling requires.The sampling process is signal-independent and computationally inexpensive, though reconstruction is more complex.
- Problem: Higher signal sparsity improves CS recovery quality, making the search for a sufficiently sparse domain a central challenge.Natural images are typically non-stationary, so no universal domain makes every part sparse.
- Problem: Most existing image CS methods use fixed DCT, wavelet, or gradient domains that are signal-independent or non-adaptive, resulting in poor recovery performance.These fixed domains do not adequately reflect the varying structure of natural images.
- Proposed framework: The proposed framework sparsely represents overlapped image patches using an adaptively learned sparsifying basis in the L0 norm.The resulting redundant sparse representation is incorporated into whole-image CS recovery.
- Optimization and results: The method uses split Bregman iterations to solve the non-convex L0 minimization problem efficiently, while reducing blocking artifacts and confining the CS solution space.The paper reports results on a wide range of natural images that are competitive with state-of-the-art methods.
2. Background
The background introduces CS recovery as sparse optimization from undersampled linear measurements and motivates split Bregman iteration as an efficient solver for constrained minimization.
- Compressive sensing: CS recovers a signal x from linear measurements y using an M×N measurement matrix with M much smaller than N.The subrate is S = M/N, and recovery exploits sparsity in a transform domain.
- Compressive sensing: A signal is sparse in a domain when most transform coefficients are zero or close to zero.The sparsity level corresponds to the number of significant elements in the coefficient vector.
- Optimization formulation: CS recovery commonly minimizes a sparsity-regularized objective in which p is typically set to 1 or 0.The L1 norm sums absolute coefficient values, whereas the L0 norm counts nonzero entries.
- Split Bregman iteration: Split Bregman iteration converts an unconstrained minimization problem into a constrained one through variable splitting and then applies Bregman iteration.The method is described as fast, memory-efficient, and attractive for large-scale problems.
- Split Bregman iteration: The background formulates constrained minimization as minimizing f(u) + g(v) subject to a linear relation between u and v.This formulation introduces the variables and operator used by the subsequent split Bregman updates.
2. Repeat
The split Bregman procedure alternates updates of the primal variables and then updates the Bregman variable before repeating.
- Iteration updates: The first update minimizes f(u) plus a quadratic penalty enforcing agreement between u and Gv.The penalty uses the current v and Bregman variable b.
- Iteration updates: The second update minimizes g(v) plus a quadratic penalty enforcing agreement between Gv and the updated u.This alternation separates the contributions of f and g.
- Iteration updates: The Bregman variable is updated from the residual between the updated u and Gv.The residual measures constraint mismatch after the two minimization steps.
- Iteration updates: The procedure increments the iteration index after completing the variable and Bregman updates.The displayed algorithm therefore defines a repeatable update cycle.
7. Until stopping criterion is satisfied
The implementation fixes the split Bregman penalty parameter and relates convergence to Douglas–Rachford splitting applied to the dual problem.
- Parameter choice: The split Bregman parameter μ is fixed rather than selected from a sequence tending to infinity, avoiding numerical instability.The paper presents this as its parameter choice for the iteration.
- Convergence: Split Bregman convergence can be established through its equivalence to Douglas–Rachford splitting applied to the dual problem.This connects the iteration to a known splitting framework.
3. Image CS recovery using adaptively learned sparsifying basis via L0 minimization
The framework represents images through overlapping patches and adaptively learned sparsifying bases, then incorporates these sparse codes into an image-level L0-minimization recovery model. Split Bregman-based optimization is used to make the non-convex formulation tractable, with experiments reporting effectiveness and convergence.
- 3.2 Image CS Recovery via L0 Minimization: The proposed framework uses an adaptively learned sparsifying basis with the patch-based representation in an image compressive-sensing recovery objective.The framework is explicitly formulated for adaptive learned sparsifying basis recovery via L0 minimization.
- 3.1 Patch-based Redundant Sparse Representation: Overlapping patches provide a redundant sparse representation of the whole image, with patch extraction and aggregation operators linking patches to the image.The representation is over-determined because patches overlap, enabling least-squares image recovery from patch estimates.
- 3.1 Patch-based Redundant Sparse Representation: Each image patch is sparsely coded over a sparsifying basis, and the collection of patch codes represents the entire image.The sparse codes are formed for all patches and concatenated into a whole-image representation.
- 3.2 Image CS Recovery via L0 Minimization: L0 minimization is non-convex and NP-hard, so the method applies a split Bregman-based strategy to solve the formulation directly through tractable subproblems.The cited passages contrast direct L0 minimization with usual convex approximations and motivate the proposed optimization approach.
- 3.2 Image CS Recovery via L0 Minimization: Experimental results demonstrate the effectiveness and convergence of the proposed approach.The supplied section passages report these outcomes without specifying numerical values.
4. Optimization for Proposed L0 minimization
The optimization framework splits the L0 problem into subproblems and uses split Bregman iteration to obtain efficient updates. Adaptive basis learning alternates between image estimation and dictionary learning from patches, while assumptions support the patchwise decomposition.
- 4. Optimization Framework: Split Bregman iteration transforms the original minimization into two subproblems, making the overall optimization easier to solve.The paper introduces an auxiliary variable and separates the original problem into subproblems for efficient solution.
- 4.1 Image Update: The image-update subproblem is a strictly convex quadratic minimization, but random projection structure makes direct matrix inversion costly.Gradient descent is used to avoid computing the matrix inverse associated with the closed-form solution.
- 4.2 Sparse Coding: The approximation used for patchwise optimization assumes independent, zero-mean errors with common variance, without requiring a Gaussian distribution.This assumption supports the relationship between the original image and its patchwise approximation.
- 4.2 Sparse Coding: The sparse-coding subproblem is solved patch by patch, with constrained sparse coding implemented using orthogonal matching pursuit.The patchwise formulation is applied to all overlapped patches to solve the corresponding subproblem.
- 4.3 Adaptive Sparsifying Basis Learning: Adaptive basis learning alternates image estimation and basis estimation because the original image is unavailable and only compressive-sensing measurements are observed.The current residual-like estimate supplies patches for K-SVD-based adaptive sparsifying-basis learning.
- 4.4 Complete Algorithm: The resulting separated subproblems provide an efficient and effective solution procedure for the complete adaptive-basis L0 recovery algorithm.The section states that the derivations yield an efficient solution and reports fast convergence relative to IST in experiments.
5. Experimental results
The experiments evaluate adaptive patch processing, sparsifying-basis selection, optimization, and comparisons with established CS recovery methods. The proposed approach generally improves reconstruction quality, preserves details, and exhibits stable empirical convergence.
- Effect of Overlapped Step Size: Smaller overlapped step sizes produce higher-quality images by generating more patch estimates and exploiting patch redundancy to reduce blocking artifacts.An overlapped step size of one means adjacent patches differ by only one column or row.
- Effect of Sparsifying Basis Selection: Adaptive basis learning yields the best House reconstruction at subrate=20%, preserving sharper edges and finer details than global or fixed DCT bases.The comparison includes fixed over-complete DCT, globally learned, and adaptively learned bases.
- Comparison between SBI and IST: SBI is more efficient and effective than IST for the proposed L0 minimization, with gains exceeding 2 dB for Leaves and 3 dB for Vessels.The visual comparison also reports lower recovery error for SBI on Leaves.
- Comparison with State-of-the-Art Algorithms: The proposed algorithm achieves the highest PSNR and FSIM in most cases across six gray images at measurement rates from 20% to 40%.PSNR measures objective image quality, while FSIM evaluates perceptual quality.
- Comparison with State-of-the-Art Algorithms: Average PSNR improvements are roughly 6.2 dB, 5.5 dB, 2.6 dB, and 2.0 dB over DWT, TV, MH, and CoS, respectively.MH and CoS are identified as current state-of-the-art image CS recovery algorithms.
- Comparison with State-of-the-Art Algorithms: Recovered images show fewer ringing effects, sharper edges, and finer details than competing methods.DWT and TV produce the weakest perceptual results, while MH and CoS retain ringing artifacts and lose details.
- Algorithm Convergence: All PSNR curves increase monotonically and eventually become flat and stable, although non-convexity introduces some perturbations.The paper describes this behavior as a good convergence property but does not provide a theoretical global-convergence proof.
6. Conclusion
The paper characterizes natural-image sparsity through patch-based redundant representations with adaptively learned sparsifying bases, formulated as a non-convex L0 minimization problem. A split Bregman iteration technique makes the optimization efficient, and experiments report improved performance and good convergence.
- Patch-based redundant sparse representation with adaptively learned sparsifying bases is used to characterize the intrinsic sparsity of natural images.
- The adaptive sparse representation is formulated through non-convex L0 minimization for image compressive sensing recovery.
- A split Bregman iteration based technique efficiently solves the proposed non-convex minimization problem.
- Experiments on a wide range of natural images show significant performance improvements over many current state-of-the-art schemes.
- The proposed algorithm exhibits good convergence property.
D b b u
The section presents the proposed framework’s experimental evaluation, including basis choices, recovery quality, convergence behavior, and comparisons across image-recovery methods and measurements.
- Table 2 reports PSNR comparisons among various CS recovery methods, measured in dB.
- Table 3 reports FSIM comparisons among various CS recovery methods.
- Table 4 compares the computational time of various algorithms in seconds.
- Figure 3 contrasts fixed over-complete DCT, globally learned, and adaptively learned sparsifying bases.
- For House at subrate=20%, PSNR increases from 33.97dB with over-complete DCT to 35.86dB with adaptive learning.
- At subrate=20%, the proposed method reaches 31.61dB PSNR on Barbara, 35.86dB on House, and 30.14dB on Vessels.
- At subrate=30%, the proposed method reaches 31.10dB PSNR on Leaves and 31.48dB on Monarch.
- Figure 12 tracks proposed-algorithm PSNR across iterations for four test images at subrate=30% and subrate=40%.