PaperlayerView exact revision on arXiv

Source-linked AI summary

Group-based Sparse Representation for Image Restoration

Jian Zhang, Debin Zhao, Wen Gao

arXiv:1405.3351v1cs.CV

TL;DR

Patch-based sparse representation faces computationally expensive dictionary learning and ignores relationships among similar patches. The paper proposes group-based sparse representation, with adaptive group dictionaries and split Bregman optimization, and reports superior restoration across inpainting, deblurring, and compressive sensing recovery.

  • Problem

    Patch-based sparse representation requires computationally expensive dictionary learning and independently processes patches, ignoring relationships among similar patches.

  • Method

    GSR represents natural images using groups of similar nonlocal patches, jointly enforcing local sparsity and nonlocal self-similarity with adaptive dictionaries and split Bregman optimization.

  • Results

    GSR outperforms many current state-of-the-art schemes across image inpainting, deblurring, and compressive sensing recovery.

  • Takeaways & Limitations

    The paper establishes a general group-based framework for high-quality image restoration and reports good stability across the evaluated applications.

Abstract

from arXiv · show

Traditional patch-based sparse representation modeling of natural images usually suffer from two problems. First, it has to solve a large-scale optimization problem with high computational complexity in dictionary learning. Second, each patch is considered independently in dictionary learning and sparse coding, which ignores the relationship among patches, resulting in inaccurate sparse coding coefficients. In this paper, instead of using patch as the basic unit of sparse representation, we exploit the concept of group as the basic unit of sparse representation, which is composed of nonlocal patches with similar structures, and establish a novel sparse representation modeling of natural images, called group-based sparse representation (GSR). The proposed GSR is able to sparsely represent natural images in the domain of group, which enforces the intrinsic local sparsity and nonlocal self-similarity of images simultaneously in a unified framework. Moreover, an effective self-adaptive dictionary learning method for each group with low complexity is designed, rather than dictionary learning from natural images. To make GSR tractable and robust, a split Bregman based technique is developed to solve the proposed GSR-driven minimization problem for image restoration efficiently. Extensive experiments on image inpainting, image deblurring and image compressive sensing recovery manifest that the proposed GSR modeling outperforms many current state-of-the-art schemes in both PSNR and visual perception.

I. INTRODUCTION

The paper identifies computational and modeling weaknesses in patch-based sparse representation and proposes group-based sparse representation (GSR) to jointly exploit local sparsity and nonlocal self-similarity for image restoration.

  • Related limitations: Classical local regularizers preserve edges and smooth regions but usually smear image details and fail on fine structures.
  • Motivation: Patch-based sparse representation requires large-scale, highly non-convex dictionary learning with high computational complexity.
  • Motivation: Independent patch processing ignores relationships among similar patches, making sparse coding coefficients inaccurate and potentially unstable.
  • Related limitations: Nonlocal regularization produces sharper edges and more details, but inaccurate graph weights can still cause disturbance and recovery errors.
  • Proposed approach: GSR uses groups of similar nonlocal patches as the sparse-representation unit, jointly modeling local sparsity and nonlocal self-similarity.
  • Proposed approach: The method adds low-complexity self-adaptive group dictionary learning and a split Bregman algorithm for efficient image-restoration optimization.
  • Results: Experiments on inpainting, deblurring, and compressive sensing recovery report that GSR outperforms many current state-of-the-art schemes.

II. TRADITIONAL PATCH-BASED SPARSE REPRESENTATION

Traditional sparse representation models natural images with independently processed patches and learned dictionaries, but dictionary learning is computationally demanding and patch independence overlooks self-similarity.

  • Patch-based sparse representation treats the patch as the basic unit for representing natural images.
  • Each patch is sparsely represented by selecting a few dictionary atoms, and overlapping patches are averaged during image reconstruction.
  • The 0-norm sparsity formulation is non-convex and usually NP-hard, motivating greedy algorithms or convex 1-norm approximations.
  • The traditional restoration model combines a degradation-data term with a patch-based sparsity regularizer.
  • Dictionary learning jointly optimizes the dictionary and representation coefficients, producing a large-scale, highly non-convex problem even with the convex 1-norm.
  • Independent patch processing ignores relationships among similar patches, including nonlocal self-similarity, while dictionary-learning approximations require high computational complexity.

III. GROUP-BASED SPARSE REPRESENTATION (GSR)

GSR replaces individual patches with groups of similar nonlocal patches, jointly exploiting local sparsity and nonlocal self-similarity while using self-adaptive group dictionaries.

  • GSR uses groups rather than patches as the sparse-representation unit to exploit local sparsity and nonlocal self-similarity in one framework.
  • Group construction: A group is a matrix formed by stacking patches with similar structures, found by searching for best matches within a training window.
  • Group construction: Each patch corresponds to a group, and group construction explicitly exploits image self-similarity.
  • Model formulation: The group-domain restoration formulation uses sparse coding and a 0-norm regularizer, but its non-convex optimization requires an efficient solution strategy.
  • Advantages: Compared with patch-based modeling, GSR uses groupwise self-similarity and low-complexity dictionary learning that avoids large-scale optimization.
  • Model formulation: GSR assigns a self-adaptive dictionary to each group instead of learning one general dictionary for all patches.

C. Self-Adaptive Group Dictionary Learning

The self-adaptive dictionary is learned separately for each group from its estimated group, using SVD to provide a shared, efficient, and unitary representation basis.

  • Learning a separate dictionary for each group addresses the limitations of a single image-level dictionary that neglects group-specific patch patterns.
  • The proposed method learns each group dictionary directly from an estimated group because the original image is unavailable during restoration.
  • After obtaining an estimated group, the method applies SVD to derive its adaptive dictionary.
  • The paper contrasts its groupwise SVD learning with prior patchwise PCA learning, emphasizing shared group atoms and computational efficiency.
  • All patches within a group use the same dictionary and share its atoms, requiring only one SVD per group.
  • Because the group dictionary is unitary, sparse coding is described as efficient, stable, and precise.

D. Discussions

The discussion connects GSR with group sparsity and low-rank modeling: under the SVD-based dictionary, both can be derived as related special cases of the same group representation framework.

  • GSR, group sparsity, and low-rank modeling all operate on sets of similar patches to exploit natural-image self-similarity.
  • Model relationships: The group sparsity view requires similar patches to share dictionary elements in their sparse decomposition.
  • Model relationships: The low-rank view seeks a low-rank approximation of each group to obtain a robust estimate.
  • Model relationships: With the paper’s SVD-based dictionary learning, one group sparsity model and one low-rank model can be derived from GSR.
  • GSR formulation: For a noisy group estimate, GSR sparsely represents the group with a dictionary and coefficient matrix before reconstructing the group.
  • GSR formulation: The formulation uses the group dictionary’s left singular vectors for sparse coding and reconstructs the group from the estimated coefficients.

IV. OPTIMIZATION FOR GSR-DRIVEN

The GSR-driven restoration problem is difficult to optimize directly, so the paper reformulates it and applies split Bregman iteration to obtain efficient subproblem updates.

  • Optimization framework: The proposed GSR-driven minimization is non-convex and NP-hard, motivating solution through its optimal convex approximation.Under some conditions, the l1 minimization is equivalent to the l0 formulation.
  • Experimental verification: The authors report that the proposed approach is effective and convergent, and that solving Eq. (12) is superior to solving Eq. (21) experimentally.They also report SBI as more effective than IST in their experiments.
  • Split Bregman iteration: The SBI scheme uses a fixed parameter μ to avoid numerical instabilities associated with predefined parameter sequences.The resulting updates alternate between the separated subproblems and the Bregman variable.
  • Split Bregman iteration: Split Bregman iteration transforms the constrained restoration problem into two subproblems that are easier to minimize separately.The reformulation introduces an auxiliary variable and separates the data-fidelity and regularization terms.

A. u Sub-problem

The u subproblem is handled as a quadratic optimization, while a residual-distribution assumption makes the group-related computation tractable.

  • Quadratic update: The u subproblem is a strictly convex quadratic minimization problem with a closed-form solution obtained by setting its gradient to zero.For inpainting and deblurring, the associated inverse can be computed efficiently because of the structure of H.
  • Quadratic update: For compressive sensing recovery, gradient descent avoids directly computing the matrix inverse required by the u update.The random projection matrix H lacks the special structure available in inpainting and deblurring.
  • Residual model: For image Parrots deblurring, estimated residual variances are 25.70 at t = 3, 23.40 at t = 5, and 23.16 at t = 7.The corresponding group-transformed variances are 25.21, 23.15, and 23.07, respectively, supporting the assumption especially at larger t.

G G G

The group-coefficient subproblem is decomposed across groups and solved efficiently using self-adaptive dictionaries, unitary structure, and hard thresholding within the complete GSR algorithm.

  • Group sparse coding: The group-coefficient optimization decomposes into n independent subproblems, one for each group G_k.This decomposition enables efficient minimization of the group-domain objective.
  • Group sparse coding: Each group dictionary D_Gk is learned self-adaptively from the corresponding group residual r_Gk.The group subproblem can therefore be treated as a sparse coding problem.
  • Group sparse coding: The group update has a closed-form solution using element-wise hard thresholding under the unitary dictionary property.The thresholding operation is applied across all groups to obtain the updated group coefficients.
  • Algorithm summary: The complete algorithm alternates image, residual, dictionary, coefficient, and Bregman updates until the maximum iteration number is reached.The final output is the restored image.

V. EXPERIMENTAL RESULTS

Experiments evaluate GSR on inpainting, deblurring, and compressive sensing recovery using PSNR and FSIM, with both quantitative and visual comparisons against five representative methods.

  • Experimental setup: The experiments cover image inpainting, image deblurring, and image compressive sensing recovery, using PSNR and FSIM to assess reconstruction quality.Higher FSIM indicates better visual quality.
  • Image inpainting: For Barbara with only 20% random samples, GSR achieves PSNR=31.32dB and FSIM=0.9598, exceeding the listed competing methods.The listed baselines include SKR, NLTV, BPFA, HSR, and SAIST.
  • Image inpainting: For House with only 20% random samples, GSR achieves PSNR=35.61dB and FSIM=0.9594, while SAIST achieves PSNR=35.73dB and FSIM=0.9615.GSR is therefore numerically close to SAIST for this case.
  • Image deblurring: For the reported deblurring comparison, GSR achieves PSNR=40.86dB and FSIM=0.9936, higher than the listed competing methods.The listed competitors include SKR, NLTV, BPFA, HSR, and SAIST.
  • Visual comparisons: Visually, GSR and SAIST restore edges and textures better than the other competing methods, while GSR provides more detail on the texture-rich Barbara image.The paper reports that GSR is nearly equivalent to SAIST for House with 20% random samples and better for text removal.

B. Image Deblurring

The experiments evaluate GSR for image deblurring and compressive sensing recovery against established competing methods. GSR achieves strong numerical and visual performance across the tested restoration settings.

  • Image Deblurring: GSR is compared with TVMM, L0_ABS, NCSR, and IDDBM3D in two sets of image-deblurring experiments.The experiments use six gray test images in the first set and six typical deblurring experiments in the second set.
  • Image Deblurring: GSR outperforms L0_ABS by 1.5 dB for uniform blur and 1.4 dB for Gaussian blur in average PSNR.The comparison is reported for the first deblurring experiment set.
  • Image Deblurring: GSR exceeds IDDBM3D and NCSR by (0.22 dB, 0.21 dB) and (0.18 dB, 0.17 dB), respectively, for the two blur kernels.The paired values report average PSNR/FSIM improvements.
  • Image Deblurring: GSR achieves the highest ISNR in most second-set deblurring cases and exceeds NCSR and IDDBM3D by more than 1 dB for Barbara in scenarios 1–3.Barbara is described as having rich textures.
  • Image Compressive Sensing Recovery: GSR obtains the highest PSNR and FSIM across six comparative CS recovery algorithms for measurement ratios of 20%, 30%, and 40%.Average improvements are roughly 7.9 dB, 7.3 dB, 4.4 dB, and 3.7 dB over DWT, TV, MH, and CoS, respectively.
  • Image Compressive Sensing Recovery: GSR removes ringing effects while preserving sharper edges and finer details than competing CS recovery methods.The visual comparisons report poorer perceptual results for DWT and TV and artifacts in MH and CoS.

D. Effect of Number of Best Matched Patches

The paper studies how the number of best-matched patches and other algorithm parameters affect GSR performance, runtime, and stability. Performance is relatively insensitive to the patch-group size, while sparsity tuning balances denoising and detail preservation.

  • Effect of Number of Best Matched Patches: GSR performance is not quite sensitive to c because the curves remain almost flat across tested values from 20 to 120.The highest performance is usually achieved with c in [40, 80], and c is empirically set to 60.
  • Effect of Sparsity Parameter: An optimal λ balances image-noise suppression with preservation of image details.Too-small λ leaves noise insufficiently suppressed, whereas too-large λ loses image details.
  • Effect of Sparsity Parameter: The optimal λ is almost the same across test images within each case, with reported values of 12.2 for one case and 0.8 for another.The paper connects larger noise variance with larger λ.
  • Algorithm Complexity and Computational Time: For 256×256 images, GSR requires about 8–9 minutes for inpainting, 6–7 minutes for deblurring, and 7–8 minutes for CS recovery.These timings were measured on an Intel Core2 Duo 2.96G PC under Matlab R2011a.
  • Algorithm Stability: PSNR curves increase monotonically and eventually become flat and stable as the iteration number grows.The observation covers image deblurring with a uniform blur kernel and CS recovery with ratio=0.3.
  • GSR-Driven Minimization: SBI+L0 achieves more than 1.5 dB higher average performance than SBI+L1 in the compared deblurring cases.The comparison is used to evaluate the proposed GSR-driven minimization.

I. Comparison between SBI and IST

The paper compares split Bregman iteration with iterative shrinkage/thresholding for solving the GSR-driven minimization problem. SBI is reported to be more efficient and effective in the tested CS recovery examples.

  • Comparison between SBI and IST: The SBI and IST comparison uses CS recovery with ratio=0.3 on Monarch and Leaves.The progression curves plot PSNR results against iteration number.
  • Comparison between SBI and IST: SBI is more efficient and effective than IST for solving the proposed GSR-driven minimization problem.The paper denotes the two results as SBI+L0 and IST+L0.
  • Conclusions: The paper presents GSR as a general framework that represents natural images using groups and jointly characterizes local sparsity and nonlocal self-similarity.It also designs a low-complexity self-adaptive dictionary-learning technique for each group.
  • Conclusions: Experiments on inpainting, deblurring, and CS recovery report performance improvements over many state-of-the-art schemes and good stability.The conclusion separately emphasizes improved CS recovery results.
  • Conclusions: Future work includes mixed Gaussian and impulse-noise deblurring and video restoration.These applications are identified as extensions of GSR.

APPENDIX A

The appendix proves a probability result under independence and zero-mean assumptions using the Law of Large Numbers. The result establishes the stated limiting relation.

  • Proof of Theorem 1: The variance of the sum of N independent elements is derived as Nσ^2.The appendix states the corresponding expectation and variance calculation.
  • Proof of Theorem 1: The Law of Large Numbers is invoked to obtain the limiting probability relation in Eq. (42).The proof then concludes by combining Eqs. (42) and (43) to establish Eq. (34).
  • Proof of Theorem 1: The proof assumes independent elements with zero mean and variance σ^2.The concatenated group elements are treated under this independence assumption.
Loading 1405.3351v1…