PaperlayerView exact revision on arXiv

Source-linked AI summary

BM3D Frames and Variational Image Deblurring

Aram Danielyan, Vladimir Katkovnik, Karen Egiazarian

arXiv:1106.6180v1math.OC

TL;DR

The paper addresses variational deblurring of blurry, noisy images using BM3D image modeling. It constructs analysis and synthesis frames and develops iterative algorithms, including a Nash-equilibrium formulation that decouples denoising and deblurring. Simulations report the decoupled algorithm as having the best numerical and visual reconstruction results and state-of-the-art performance.

  • Problem

    The paper seeks effective variational reconstruction from blurry and noisy observations while extending BM3D nonlocal image modeling into a formal frame-based framework.

  • Method

    The paper constructs analysis and synthesis BM3D-frames and develops iterative deblurring algorithms from single-objective and Nash-equilibrium formulations.

  • Results

    The Nash-equilibrium formulation decouples denoising and deblurring, and simulations report the best numerical and visual reconstruction results for this algorithm.

  • Takeaways & Limitations

    BM3D-frames provide an advanced image-modeling tool for variational reconstruction, with the decoupled algorithm reported as state of the art.

  • Takeaways & Limitations

    For non-tight frames, the paper treats single-objective reconstruction as valid under stated assumptions and proposes Nash equilibrium as an alternative formulation.

Abstract

from arXiv · show

A family of the Block Matching 3-D (BM3D) algorithms for various imaging problems has been recently proposed within the framework of nonlocal patch-wise image modeling [1], [2]. In this paper we construct analysis and synthesis frames, formalizing the BM3D image modeling and use these frames to develop novel iterative deblurring algorithms. We consider two different formulations of the deblurring problem: one given by minimization of the single objective function and another based on the Nash equilibrium balance of two objective functions. The latter results in an algorithm where the denoising and deblurring operations are decoupled. The convergence of the developed algorithms is proved. Simulation experiments show that the decoupled algorithm derived from the Nash equilibrium formulation demonstrates the best numerical and visual results and shows superiority with respect to the state of the art in the field, confirming a valuable potential of BM3D-frames as an advanced image modeling tool.

I. INTRODUCTION

The paper formalizes BM3D nonlocal image modeling with analysis and synthesis frames, then applies these models to variational image deblurring. It develops iterative formulations including a Nash-equilibrium approach that decouples denoising from deblurring.

  • Motivation: Image restoration reconstructs a true image from a blurry, noisy observation using a blur model, Gaussian-noise assumption, and variational fidelity and penalty terms.The fidelity term enforces agreement with the observation, while the penalty regularizes the reconstruction through an image prior.
  • Contributions: The paper formalizes BM3D as an overcomplete sparse frame representation and constructs both analysis and synthesis BM3D-frames.The frame interpretation treats BM3D analysis and synthesis as sparse image modeling applicable to variational image-processing formulations.
  • Contributions: Two deblurring formulations are considered: minimization of a single objective function and a Nash-equilibrium formulation that decouples denoising and deblurring.The decoupled formulation separates the two operations through a balance of two objective functions.
  • BM3D modeling: BM3D groups similar image blocks, transforms each 3-D group, thresholds its spectrum, and aggregates inverse-transformed block estimates by weighted averaging.The grouped spectra create an overcomplete representation whose redundancy supports BM3D modeling effectiveness.
  • Frame construction: The analysis and synthesis operations are represented explicitly by matrices Φ and Ψ, with grouping, transforms, block placement, and weighted aggregation encoded in these operators.The synthesis estimate is y = Ψω = W−1 · [g1Ψ1, . . . , gRΨR] · ω.

B. Frame interpretation

The BM3D operators form non-tight analysis and synthesis frames whose construction is data adaptive. The analysis frame and synthesis frame are dual, while the analysis frame is canonical only under equal group weights.

  • Frame properties: Proposition 1 establishes equations for the analysis matrix Φ and synthesis matrix Ψ used to represent BM3D operations.The proof is provided in Appendix A.
  • Frame properties: The rows of Φ constitute a frame in R^N, with frame bounds determined by the minimum and maximum diagonal values of the block-incidence matrix.The frame inequality follows from the analysis relation ω = Φy.
  • Frame properties: The analysis frame is non-tight because different pixels belong to different numbers of similar-block groups.Pixels in more similar blocks participate in more groups, producing unequal diagonal values.
  • Frame properties: The columns of Ψ form a non-tight frame dual to the frame formed by the rows of Φ.The analysis frame becomes the canonical dual only when all group weights gr are equal.
  • Adaptivity and scope: Because groups and weights are selected adaptively from the data, the constructed BM3D frames are also data adaptive.This frame interpretation extends BM3D modeling to variational image reconstruction techniques.

III. VARIATIONAL IMAGE DEBLURRING

The paper formulates variational deblurring using either BM3D analysis or synthesis variables. Although the formulations are algebraically similar, they generally produce different solutions.

  • Analysis formulation: The analysis formulation links image y and spectrum variables ω through ω = Φy and expresses deblurring as a constrained optimization problem.The objective combines Gaussian data fidelity with an lp-norm penalty on the spectrum variables.
  • Synthesis formulation: The synthesis formulation links the image and spectrum variables through y = Ψω and yields a different constrained optimization problem.Its unconstrained form minimizes in the spectrum domain after eliminating the image variable.
  • Equivalent forms: Both constrained problems have equivalent unconstrained forms obtained by eliminating the auxiliary image or spectrum variables.The analysis problem becomes an image-domain minimization, whereas the synthesis problem becomes a spectrum-domain minimization.
  • Comparison: Despite algebraic similarity, analysis and synthesis formulations generally lead to different solutions.The paper notes that their nontrivial connections have been studied separately.
  • Solution strategy: The paper adopts augmented-Lagrangian methods related to split Bregman, iterative-shrinkage, ADMM, and majorization-minimization algorithms.The discussion focuses on formulations with lp penalties, including non-differentiable cases for p ≤ 1.

A. Analysis-based reconstruction

The analysis-based algorithm alternates image updates, spectrum thresholding, and multiplier updates to solve the constrained formulation. Hard or soft thresholding is selected according to the lp penalty.

  • Algorithm: The analysis augmented-Lagrangian saddle problem is solved by alternating minimization over y and ω and maximization over the multiplier λ.The iterative scheme updates these variables in succession until convergence.
  • Image update: The image update solves a linear equation because the analysis Lagrangian is quadratic in y.The resulting solution is represented by the operator Ŷa(ω, λ).
  • Spectrum update: For p = 0 and p = 1, the spectrum update has analytical thresholding solutions, using hard or soft thresholding respectively.The thresholding operator acts elementwise, with hard and soft thresholds calculated differently for a given parameter.
  • Initialization: The algorithm is initialized from z, A, and an initial image, which is used to construct Φ and ΦT before iterations begin.The procedure is presented as the analysis-based deblurring algorithm in Figure 1.
  • Iteration: Each iteration first applies linear filtering to the image estimate, then thresholds Φy − λ, and finally updates the Lagrange multipliers.Iterations stop when consecutive image estimates differ by a sufficiently small amount.

B. Synthesis-based reconstruction

The synthesis formulation uses a splitting variable and alternating optimization to update the image, spectrum estimate, and multipliers. The resulting iterative algorithm combines linear updates with thresholding until convergence.

  • Synthesis formulation: The synthesis formulation introduces a splitting variable u as an auxiliary estimate of the spectrum ω.This modification addresses the Ψ factor in the quadratic spectrum term, which prevents direct application of the standard thresholding formula.
  • Initialization: The algorithm is initialized from z, A, and yinit by constructing the synthesis operators Ψ and ΨT.The initialization uses the provided starting image to construct the operators required by the synthesis reconstruction.
  • Iterative algorithm: The synthesis-based algorithm alternates updates of y, u, ω, and the Lagrange multipliers.The image and splitting variable are updated by solving linear problems, ω is thresholded, and the multipliers follow the gradient y^t+1−Ψu^t+1.
  • Algorithm overview: The synthesis-based iterative deblurring algorithm is presented in Figure 2.The procedure repeats its variable updates until a convergence criterion is satisfied.

IV. DECOUPLING OF BLUR INVERSION AND DENOISING

The Nash-equilibrium formulation separates deblurring into blur inversion and denoising subproblems. Its resulting IDD-BM3D algorithm performs these operations in a decoupled iterative procedure, with convergence to a fixed point established for the iterations.

  • Decoupled formulation: The Nash-equilibrium formulation splits deblurring into sequential blur inversion and denoising subproblems.The equilibrium balances reconstruction fidelity against model complexity rather than combining both terms in a single criterion.
  • Advantages: Decoupled algorithms simplify design and parameter selection, permit FFT-based blur inversion, and allow denoisers to be selected independently.The paper also states that such algorithms can outperform approaches that jointly perform deblurring and denoising.
  • Nash equilibrium: The two objective functions represent a noncooperative interaction between the image variable y and spectrum variable ω.A Nash equilibrium defines the fixed point balancing the objectives associated with inversion and denoising.
  • IDD-BM3D algorithm: The IDD-BM3D iterations update the image through regularized blur inversion and update the spectrum through thresholding.The blur inversion and denoising steps are fully decoupled in the resulting algorithm.
  • IDD-BM3D algorithm: The resulting algorithm is called Iterative Decoupled Deblurring BM3D (IDD-BM3D) and is presented in Figure 3.The iterations converge to the fixed point of the Nash-equilibrium formulation.

V. CONVERGENCE

The analysis- and synthesis-based algorithms converge when the corresponding augmented Lagrangian has a saddle point, while the IDD-BM3D algorithm converges to a fixed point when it exists. These guarantees are conditional: without the required point, certain sequences may be unbounded.

  • Analysis and synthesis-based algorithms: For the analysis formulation, the image, auxiliary variable, and multipliers converge to a saddle point when one exists.
  • Analysis and synthesis-based algorithms: For the synthesis formulation, the image, splitting variable, auxiliary variable, and multipliers likewise converge when a saddle point exists.
  • Analysis and synthesis-based algorithms: If no corresponding saddle point exists, at least one image or multiplier sequence must be unbounded.
  • IDD-BM3D algorithm: The IDD-BM3D sequence converges to the fixed point specified by its equations for any parameters, provided that fixed point exists.
  • IDD-BM3D algorithm: The fixed point need not be unique, so different starting points can produce different limit points satisfying the fixed-point equations.

VII. EXPERIMENTS

Experiments evaluate BM3D-frame deblurring across benchmark scenarios and compare formulations, showing strong performance for the decoupled IDD-BM3D algorithm and explaining its advantage over analysis-based reconstruction for non-tight frames.

  • Experiments: Six benchmark deblurring scenarios were tested on Cameraman, Lena, House, and Barbara images, with the proposed algorithms evaluated under multiple thresholding and weighting settings.IDD-BM3D was tested with unit and adaptive group weights, using soft and hard thresholding.
  • Experiment 1: Adaptive weights improve restoration, while hard thresholding combined with adaptive weights produces the best results among the considered proposed algorithms for Cameraman.The comparison is based on output ISNR values in Table II.
  • Experiment 2: IDD-BM3D provides the best results with significant advantage over closest competitors, outperforming the two-stage BM3DDEB approach.The authors attribute this to more effective exploitation of BM3D modeling by the decoupled formulation.
  • Visual comparison: The proposed method suppresses ringing artifacts better than BM3DDEB and produces sharper image edges, partly because it uses a smaller block size.Figures 5 and 6 provide visual comparisons with CGMK, L0-AbS, and BM3DDEB.
  • Discussion: Although IDD-BM3D and the analysis-based algorithm are almost identical for tight frames, experiments show a clear IDD-BM3D advantage.For non-tight frames, variation in pixel group counts makes ΦT Φ poorly conditioned, degrading analysis-based reconstruction.
  • Discussion: The Nash-equilibrium formulation avoids unavoidable ΦT Φ terms by assigning norms from only one domain to each objective criterion.This formulation decouples blur inversion and denoising and supports the reported reconstruction behavior.

APPENDIX A

The appendix presents matrix identities and proof steps supporting the BM3D-frame analysis, alongside experimental figures and tables reporting deblurring comparisons and image-quality measures.

  • Proof tools: The proofs use Kronecker-product identities, including transpose and inverse rules, to establish the stated frame-related formulas.The Kronecker product dimensions and columnwise vectorization of matrix equations are also specified.
  • Experimental figures: Figure 5 compares Cameraman deblurring in scenario 3 across the original, blurred noisy input, three competing methods, and IDD-BM3D.The reported ISNR values are 9.15 for CGMK, 9.10 for L0-AbS, 8.34 for DEB-BM3D, and 10.45 for IDD-BM3D.
  • Experimental figures: Figure 6 compares Lena deblurring in scenario 2 using the same image ordering and reports ISNR values for three competing methods and IDD-BM3D.The reported values are 5.37 for CGMK, 5.71 for L0-AbS, 6.53 for DEB-BM3D, and 6.61 for IDD-BM3D.
  • Experimental tables: Table II compares output ISNR in decibels for the proposed deblurring algorithms and includes an input-PSNR row.The caption identifies the table as a comparison of output ISNR [dB].
  • Notation and derivations: Additional appendix material includes variance and blurred signal-to-noise-ratio notation, proof statements, and matrix expressions used in the derivations.The supplied passages include a variance definition and a separate table caption for deconvolution-method comparisons.

A. Proof of Proposition 2

The proof applies a generalized Eckstein–Bertsekas convergence theorem to the analysis- and synthesis-based formulations. Under the stated convexity, rank, accuracy, and saddle-point conditions, the corresponding algorithms converge.

  • General convergence theorem: The proposed convergence analysis uses a generalized Eckstein–Bertsekas theorem for linear links between the main variable u and auxiliary variable v.The general constraint is Cv + Du = b; the adapted theorem handles cases where this relation cannot be resolved directly for v.
  • General convergence theorem: The theorem assumes closed proper convex functions, full column rank of C, and strict convexity of f(u) + ∥Du∥2.It also introduces arbitrary initial variables, a positive penalty parameter β, and sequences satisfying the required approximation conditions.
  • General convergence theorem: If a saddle point exists, the sequences v_t, u_t, and λ_t converge to the corresponding saddle point; otherwise, at least one of {u_t} or {λ_t} is unbounded.The result concerns approximate solutions at each optimization step, with accuracy parameters required to asymptotically improve.
  • Analysis formulation: For the analysis formulation, C = I_M has full column rank and the required objective term is strictly convex, so the algorithm converges to an augmented-Lagrangian saddle point if one exists.The proof identifies the data-fidelity term through f(u) = 1/(2σ^2)∥z − Ay∥2^2 and represents the constraint as ω − Φy = 0.
  • Synthesis formulation: For the synthesis formulation, the constraint relations are y − Ψu = 0 and ω − u = 0, while the associated matrix and objective satisfy the theorem’s rank and strong-convexity requirements.Consequently, the theorem’s conditions are fulfilled for the synthesis-based algorithm as well.

B. Proof of Proposition 3

The proof establishes convergence of the decoupling algorithm by showing that its component operators are nonexpansive. Eigenvalue bounds yield nonexpansiveness for the deblurring operator, after which bounded iterates converge to a fixed point.

  • Operator framework: The decoupling algorithm is analyzed through nonexpansive operators, a class whose outputs do not increase distances between inputs.Soft thresholding is used as one such operator in the convergence argument.
  • Deblurring operator: The deblurring operator O_d is studied through the eigenvalues of ΦM^-1Ψ, whose nonzero eigenvalues coincide with those of M^-1.The proof obtains this correspondence by substituting Φv and multiplying by W^-1Φ^T, using W^-1Φ^TΦ = I.
  • Deblurring operator: The eigenvalues of M^-1 are positive and at most 1, so all eigenvalues of ΦM^-1Ψ are nonnegative and at most 1.This establishes the required spectral bound for the operator analysis.
  • Operator framework: The matrix norm ρ is at most one, making O_d nonexpansive; together with nonexpansive thresholding, this supports the convergence proof.The algorithm’s iteration is expressed using the deblurring and thresholding operators.
  • Fixed-point convergence: The iterates remain bounded around fixed points, and continuity implies that their limit points are themselves fixed points.Distances between successive error sequences do not increase, placing the iterates in a compact region with convergent subsequences.
  • Fixed-point convergence: The decoupling algorithm converges: along the convergent subsequences, both ω_t and y_t approach fixed-point limits.The proof concludes with lim_k→∞∥ω_tk − ω̃∥ = 0 and lim_k→∞∥y_tk − ỹ∥ = 0.
Loading 1106.6180v1…