PaperlayerView exact revision on arXiv

Source-linked AI summary

Solving Inverse Problems with Piecewise Linear Estimators: From Gaussian Mixture Models to Structured Sparsity

Guoshen Yu, Guillermo Sapiro, Stéphane Mallat

arXiv:1006.3056v1cs.CV

TL;DR

The paper seeks a general and efficient approach to image inverse problems, where existing sparse and structured-sparse methods have limitations. It uses GMMs estimated by MAP-EM and interprets the resulting estimator as structured sparse estimation. Across inpainting, zooming, and deblurring, it reports performance equal to, often better than, or only slightly worse than the best published methods at lower computational cost.

  • Problem

    Existing image inverse-problem methods include computationally expensive and unstable sparse estimations, while structured sparsity is insufficient for some unstable tasks such as zooming and deblurring.

  • Method

    The framework models local image patches with Gaussian mixture models estimated by MAP-EM and connects the resulting piecewise linear estimate to structured sparse estimation.

  • Results

    Across inpainting, zooming, and deblurring, the method produces results equal to, often significantly better than, or only marginally worse than the best published methods, at lower computational cost.

  • Takeaways & Limitations

    The structured-sparse interpretation stabilizes and improves traditional sparse inverse-problem estimation and suggests an effective dictionary-motivated MAP-EM initialization.

Abstract

from arXiv · show

A general framework for solving image inverse problems is introduced in this paper. The approach is based on Gaussian mixture models, estimated via a computationally efficient MAP-EM algorithm. A dual mathematical interpretation of the proposed framework with structured sparse estimation is described, which shows that the resulting piecewise linear estimate stabilizes the estimation when compared to traditional sparse inverse problem techniques. This interpretation also suggests an effective dictionary motivated initialization for the MAP-EM algorithm. We demonstrate that in a number of image inverse problems, including inpainting, zooming, and deblurring, the same algorithm produces either equal, often significantly better, or very small margin worse results than the best published ones, at a lower computational cost.

EDICS: TEC-RST

The paper addresses image inverse problems using local image models and develops a GMM/MAP-EM framework linked to structured sparse estimation. It targets computationally efficient restoration while addressing limitations of learned dictionaries and nonlinear sparse estimation.

  • Problem: Image restoration estimates an original image from observations produced by a non-invertible degradation operator and additive noise.Typical degradation operators include masking, uniform-grid subsampling, and convolution.
  • Limitations of existing approaches: Learned dictionaries adapt well to images and enhance sparsity, but dictionary learning is large-scale, highly non-convex, computationally expensive, and mathematically insufficiently understood.Sparse representations also require expensive nonlinear estimations such as l1 or matching pursuit.
  • Limitations of existing approaches: Structured sparsity reduces possible approximation spaces by selecting blocks of dependent atoms, yet is insufficient for unstable problems such as zooming or deblurring.Directional regularization is described as not general enough to extend to all targeted inverse problems.
  • Proposed framework: The proposed GMM framework uses MAP-EM to produce piecewise linear estimation, whose structured-sparse interpretation stabilizes traditional sparse inverse-problem estimation.The interpretation uses a structured learned overcomplete dictionary formed from a union of PCA bases and collaborative eigenvalue priors, motivating initialization.
  • Evaluation: Applications cover inpainting, zooming, and deblurring, with results reported in the same ballpark as state-of-the-art methods at lower computational cost.The paper presents experiments and comparisons across these image restoration applications.
  • Problem: Local patch models represent natural images through a mixture of Gaussian distributions, with each patch assigned to one generating Gaussian.The model uses Gaussian means and covariances, and estimation includes identifying each patch’s Gaussian component.

B. MAP-EM Algorithm

MAP-EM alternates signal estimation and Gaussian-model selection with Gaussian-parameter updates. Its E-step uses linear Wiener filters, while translation-invariant degradations permit precomputation for efficient iterations.

  • MAP-EM iteratively alternates an E-step for signal estimation and model selection with an M-step for updating Gaussian parameters.
  • The E-step maximizes the posterior over each patch signal and Gaussian model, then uses the selected model to obtain the signal estimate.
  • For a Gaussian signal model, the MAP estimate is computed with a linear Wiener filter matrix.
  • When degradation is translation-invariant, the Wiener filter matrices are identical across patch positions and can be precomputed for all K Gaussian models.
  • The E-step costs 2N^2 floating-point operations for translation-invariant degradation, whereas translation-variant settings require Cholesky-based matrix inversions.The stated translation-variant inversion cost is approximately N^3/3 flops.

2) M-step: Model Estimation:

The paper motivates structured estimation by identifying instability in traditional sparse inverse problems and introduces a piecewise-linear framework linked to MAP-EM. It also describes covariance updates, convergence, and the conditions governing recoverability and stability.

  • 2) M-step: Model Estimation:: The M-step estimates each Gaussian model using all patches assigned to that model, with covariance regularization improving estimates when data are scarce.Adding εI_d makes each covariance full-rank and keeps the Wiener filter well defined.
  • 2) M-step: Model Estimation:: MAP-EM increases the posterior probability of the observed signals through coordinate-descent-like E- and M-steps, with convergence of clustering and PSNR observed experimentally.
  • A. Sparse Inverse Problem Estimation: The proposed PLE framework addresses these issues through a structured sparse interpretation of MAP-EM and a dictionary-motivated initialization.
  • A. Sparse Inverse Problem Estimation: Traditional sparse inversion can be unstable because a non-invertible degradation makes the transformed dictionary redundant and permits infinitely many decompositions.
  • A. Sparse Inverse Problem Estimation: Uniform-grid subsampling and convolution do not satisfy the stated sufficient isometry condition, so precision and stability depend on the poorly understood support geometry.
  • A. Sparse Inverse Problem Estimation: Sparse recovery requires sparse representations, recoverable transformed atoms, and sufficient incoherence among transformed dictionary columns.

B. Structured Sparse Estimation in PCA bases

The PCA-basis formulation interprets MAP-EM as structured sparse estimation: each patch selects one PCA basis, performs linear estimation within it, and uses eigenvalue ordering to regularize coefficients.

  • Comparing the PCA formulation with traditional sparse estimation shows that MAP-EM implements structured sparse estimation.
  • The proposed overcomplete dictionary is a union of PCA bases adapted through Gaussian-model estimation, producing a more structured piecewise linear estimator.
  • Nonlinear block sparsity: Each patch selects one of K PCA bases, reducing nonlinear model-selection freedom from arbitrary atom selection to K choices.
  • Linear collaborative filtering: Within each PCA basis, eigenvalue ordering concentrates representation on principal directions and weights coefficients by their associated eigenvalues.
  • Linear collaborative filtering: The eigenvalue weighting performs collaborative filtering by incorporating information from all signals assigned to the same Gaussian cluster.
  • For translation-invariant degradation, MAP-EM has complexity O(2LKN^2) and is typically one or two orders of magnitude faster than sparse estimation.The algorithm typically converges in L = 3 to 5 iterations.

C. Initialization of MAP-EM

The initialization uses directional PCA bases derived from synthetic edges, with eigenvalues and means set to provide sparse, direction-aware Gaussian models. Experiments show that multiple directions improve PSNR and stabilize around K = 36.

  • Directional PCA initialization uses uniformly sampled angles from 0 to π, with one PCA basis computed per angle from patches touching a synthetic edge.
  • The resulting PCA atoms resemble directional cosine functions while avoiding the periodic-boundary issue of Fourier vectors.
  • The covariance initialization uses these eigenvalues, while Gaussian means are initialized to zero.
  • Directional PCAs provide sparse representations for contours and also capture textures sharing the same directionality.
  • Fast eigenvalue decay indicates that leading atoms absorb most energy in local patterns with a common direction.
  • There is a significant average PSNR gain when K increases from 0 to 3, with gains stabilizing at about K = 36; K = 18 is selected as a complexity compromise.

2) Recoverability:

Recoverability depends on matching PCA bases to the degradation operator: localized position bases support convolution, whereas oscillatory atoms with concentrated Fourier support violate the condition. The resulting directional and position bases organize patches by orientation and location.

  • Recoverability: For convolution operators, oscillatory atoms with Dirac-supported Fourier spectra violate the recoverability condition.Convolution requires atoms with spread Fourier spectra, hence spatial localization.
  • Patch organization: Directional and position PCA bases assign densely overlapping patches to orientation or position models, respectively.Figure 3 uses K = 19 directional models and P = 12 position models for 8 × 8 patches.
  • Position PCA bases: Position PCA bases provide localized atoms with different polarities and scales for edge-touching patches.They are constructed from synthetic edge images with varying blur and organized across positions for each direction.
  • Position PCA bases: Rainbow-like transitions at edges indicate that position bases fit spatial locations accurately.The position labels vary smoothly across edge regions after initialization.

3) Wiener Filtering Interpretation:

The MAP estimator yields interpretable isotropic or directional Wiener filters, while initialization quality governs convergence across inverse problems. Directional initialization is effective for inpainting and zooming, but position PCA bases are needed for deblurring because directional bases violate recoverability.

  • Wiener filtering interpretation: MAP-generated filters act as isotropic or directional interpolators for zooming and deblurring filters for convolution.DCT-based PCA produces isotropic filters, while directional PCA produces filters aligned with a 30° direction.
  • Initialization: For inpainting, random initialization converges about 0.4 dB below the proposed initialization and takes longer.The difference is moderate for random masking, whereas structured operators produce larger initialization failures or gaps.
  • Initialization: Initialization strongly affects MAP-EM: random initialization fails for zooming and can become trapped in poor deblurring minima.For deblurring, directional PCA initialization converges 1.5 dB below position PCA initialization because recoverability is violated.
  • Initialization: On zooming, MAP-EM improves substantially over bicubic initialization but remains about 0.5 dB below the proposed initialization after slower convergence.The proposed directional PCA initialization is more effective than bicubic initialization.
  • Initialization: The sparse-coding interpretation helps derive effective initializations for different inverse problems.The experiments identify initialization as important for solving inverse problems with MAP-EM.

B. Evolution of Representations

MAP-EM progressively refines patch clustering and PCA representations, especially for textured regions, while contour regions can be well estimated from directional initialization. Structured, collaboratively weighted estimation improves accuracy over conventional sparse methods at lower computational cost.

  • B. Evolution of Representations: On Barbara’s textured cloth, MAP-EM cleans the clustering and promotes high-frequency atoms, improving PSNR by more than 3 dB.The updated representation better captures oscillatory texture patterns.
  • B. Evolution of Representations: On Lena’s contours, PSNR changes little after initialization because directional PCA bases already estimate the structure accurately.The bases are calculated from synthetic contour images and retain fast-decaying eigenvalues during iteration.
  • C. Estimation Methods: The proposed block weighted l2 estimator forms a stable, computationally efficient piecewise linear estimate.It replaces weighted l1 regularization with weighted l2 regularization.
  • C. Estimation Methods: In super-resolution, global l1 and OMP create contour artifacts, while block methods improve the results.Adding collaborative weights yields a very significant improvement over block l1, and block weighted l2 further improves accuracy at lower cost.
  • Applications: The framework applies PLE to inpainting, zooming, and deblurring on standard gray-level and color images.The experiments use image regions and can process regions separately because image content is often more coherent semi-locally than globally.

V. INPAINTING

PLE inpainting is evaluated under random masking on gray-level and color images against several restoration methods. It achieves the strongest reported gray-level results and surpasses the prior best color result, while preserving both contours and textures at reduced computational complexity.

  • Gray-level inpainting: PLE outperforms competing methods on all gray-level inpainting cases, improving PSNR by about 2 dB on average over the second-best algorithms.The comparison includes BP, FOE, MCA, ASR, ECM, KR, and K-SVD under multiple available-data ratios.
  • Gray-level inpainting: PLE restores directional structures and textures accurately, producing the best visual quality and highest PSNRs in Figure 10.MCA captures contours and textures but can generate elongated curvelet-like artifacts when atoms are selected incorrectly.
  • Color inpainting: For Castle with 20% available data, PLE reaches 30.07 dB, exceeding the literature’s best reported 29.65 dB from K-SVD.The result is obtained with much reduced computational complexity, while color redundancy supports inpainting.

VI. INTERPOLATION ZOOMING

Interpolation zooming is treated as a special inpainting case under regular subsampling, with PLE evaluated against linear, adaptive, and sparse methods on gray-level and color images.

  • Interpolation zooming is a special case of inpainting with regular subsampling on uniform grids.
  • Accurate sparse estimation is more difficult for interpolation zooming than for inpainting with random masks.
  • The experiments use gray-level and color images down-sampled by 2 × 2 without anti-aliasing, producing aliased low-resolution images.
  • PLE is compared with linear interpolators, adaptive directional methods, generic inpainting algorithms, and sparse estimators including SAI and SME.
  • PLE gives moderately higher PSNRs than SME and SAI for all images except one, where SAI is slightly higher.
  • PLE produces higher image quality than bicubic, NEDI, DFDF, KR, and FOE, while SR can introduce contour artifacts when atoms are incorrectly selected.
  • PLE restores regular geometrical structures and fine lines slightly better than SAI and SME in the illustrated zooming example.

VII. DEBLURRING

The deblurring procedure uses hierarchical PLE model selection and enlarges local supports to address convolutional boundary effects.

  • Image deblurring estimates f from a blurred and noisy observation y = Uf+w, where U is a convolution operator.
  • Hierarchical PLE: Hierarchical PLE selects a directional PCA basis first and then a position PCA basis within that direction.
  • Hierarchical PLE: The hierarchical calculation reduces computational complexity from O(KP) to O(K +P).
  • Boundary treatment: Patch-boundary deconvolution is handled by extending the patch, composing convolution with masking, and discarding extrapolated boundary pixels.
  • Boundary treatment: The method is less accurate when the blur-kernel support is large relative to patch size; experiments use 8×8 patches, 12×12 extended supports, and 5×5 kernels.

B. Deblurring Experiments

Deblurring experiments compare PLE with established deconvolution and sparse methods, while a separate zooming-deblurring procedure first interpolates and then deconvolves.

  • Deblurring: Deblurring experiments use gray-level images and compare PLE with ForWaRD, TVB, TwIST, SA-DCT, BM3D, SP, and DSD.
  • Deblurring: The tests use Gaussian blur with σb = 1 or 2, truncated to 5×5 support, and white Gaussian noise with σn = 5.
  • Deblurring results: BM3D has the highest ISNR, while SA-DCT and PLE are comparable and moderately higher than SP on average.
  • Deblurring results: Without empirical Wiener post-processing, PLE outperforms BM3D and SA-DCT on average; the post-processing boosts ISNR by near 1 dB.
  • Zooming deblurring: For intermediate anti-aliasing blur, zooming is performed by linear interpolation followed by PLE deconvolution of U rather than direct inversion of SU.
  • Zooming deblurring: Deconvolving the interpolated image produces accurate zooming estimates because inverting U is simpler than inverting the compounded operator SU.
  • Zooming deblurring: On Lena, PLE improves PSNR by 3.12 dB over cubic-spline interpolation and produces a sharper image without noticeable artifacts.

VIII. CONCLUSION AND FUTURE WORKS

The paper presents GMM/MAP-EM PLE as a general, computationally efficient framework whose structured-sparse interpretation supports stabilization and initialization, with competitive restoration results.

  • GMMs estimated by MAP-EM provide general and computationally efficient solutions for image inverse problems.
  • The framework has a dual mathematical interpretation as structured sparse estimation, yielding a piecewise linear estimate that stabilizes and improves traditional sparse estimation.
  • This connection suggests a dictionary-motivated initialization for the MAP-EM algorithm.
  • Across inpainting, zooming, and deblurring, the same algorithm achieves equal, often better, or only slightly worse results than the best published methods at lower computational cost.
  • For denoising, the results are on average just 0.1 dB lower than BM3D, while the reported complexity is typically one or two orders of magnitude smaller than l1 sparse estimations.
  • Future improvements may use stochastic EM and more advanced covariance regularization, at the cost of higher computational complexity.
Loading 1006.3056v1…