PaperlayerView exact revision on arXiv

Source-linked AI summary

Deconvolving Images with Unknown Boundaries Using the Alternating Direction Method of Multipliers

Mariana S. C. Almeida, Mário A. T. Figueiredo

arXiv:1210.2687v2math.OCcs.CV

TL;DR

The paper addresses the mismatch between efficient but unrealistic periodic-boundary deconvolution and imaging systems with unknown boundaries or missing pixels. It develops ADMM methods that decouple masking from convolution and preserve efficient computation and convergence guarantees. Experiments demonstrate non-periodic deblurring and combined deblurring-inpainting with TV and frame-based regularization.

  • Problem

    Existing ADMM deconvolution methods rely on periodic boundary conditions for efficient FFT-based inversion, although real boundaries may be unknown and pixels may be missing.

  • Method

    The paper models observations as masked convolutions and uses ADMM variants that decouple masking and convolution for TV and frame-based regularization.

  • Results

    The resulting algorithms retain efficient updates and formal convergence guarantees, and experiments show advantages over edgetaper in SNR and over a recent strategy in speed.

  • Takeaways & Limitations

    The approach extends fast ADMM deconvolution to unknown-boundary problems and also handles deblurring combined with inpainting.

Abstract

from arXiv · show

The alternating direction method of multipliers (ADMM) has recently sparked interest as a flexible and efficient optimization tool for imaging inverse problems, namely deconvolution and reconstruction under non-smooth convex regularization. ADMM achieves state-of-the-art speed by adopting a divide and conquer strategy, wherein a hard problem is split into simpler, efficiently solvable sub-problems (e.g., using fast Fourier or wavelet transforms, or simple proximity operators). In deconvolution, one of these sub-problems involves a matrix inversion (i.e., solving a linear system), which can be done efficiently (in the discrete Fourier domain) if the observation operator is circulant, i.e., under periodic boundary conditions. This paper extends ADMM-based image deconvolution to the more realistic scenario of unknown boundary, where the observation operator is modeled as the composition of a convolution (with arbitrary boundary conditions) with a spatial mask that keeps only pixels that do not depend on the unknown boundary. The proposed approach also handles, at no extra cost, problems that combine the recovery of missing pixels (i.e., inpainting) with deconvolution. We show that the resulting algorithms inherit the convergence guarantees of ADMM and illustrate its performance on non-periodic deblurring (with and without inpainting of interior pixels) under total-variation and frame-based regularization.

I. INTRODUCTION

ADMM deconvolution is computationally efficient under periodic boundary conditions, but those assumptions are often unrealistic and can produce boundary artifacts. This paper models unknown boundaries explicitly, extends ADMM to non-periodic deconvolution and inpainting, and provides convergence guarantees with TV and frame-based regularization.

  • Motivation: ADMM is efficient for imaging inverse problems because variable splitting separates difficult optimization into simpler subproblems, including TV- and frame-based regularization.Its matrix inversion can exploit second-order information and is often faster than IST methods.
  • Motivation: Periodic boundary conditions make convolution matrices circulant and diagonalizable by the DFT, enabling efficient FFT-based matrix inversion.This computational convenience is a major reason periodic BCs are commonly used.
  • Motivation: Periodic, zero, reflexive, and anti-reflexive boundary conditions impose assumptions that generally do not correspond to realistic imaging systems.The periodicity mismatch can produce ringing artifacts near image boundaries.
  • Motivation: Zero-boundary convolution can be embedded into a larger periodic convolution, but zero-padding prevents the ADMM matrix inversion from being efficiently computed via the FFT.Thus, zero BCs address neither the modeling mismatch nor the central computational issue.
  • Proposed direction: The paper treats unknown external boundary pixels as a simultaneous deconvolution-and-inpainting problem using a masked convolution with arbitrary boundary conditions.The mask retains pixels whose blurred values do not depend on the unknown boundary.
  • Proposed direction: The proposed ADMM algorithms decouple masking and convolution, retain efficient updates without inner iterations, provide formal convergence guarantees, and support TV plus frame-based synthesis and analysis regularization.Experiments report improved SNR over edgetaper and greater speed than an adaptation of a recent alternative, including combined deblurring and inpainting.

A. The Standard ADMM Algorithm

ADMM splits convex optimization problems into simpler subproblems, often yielding efficient updates and convergence under stated assumptions. For multiple regularizers, separability enables independent proximity operations, while matrix inversion remains the main computational bottleneck.

  • Problem formulation: ADMM applies to convex problems by splitting variables and separating functions through a linear constraint.The formulation uses convex functions f and g, a matrix G, and auxiliary variables.
  • Convergence: When G has full column rank and the problem has a solution, ADMM converges under closed, proper, convex-function assumptions.The convergence theorem allows arbitrary positive penalty parameter µ and suitable error sequences.
  • Multiple regularizers: Multiple-function ADMM stacks the linear operators and separates the regularizers, producing independent minimizations for each function.The quadratic update becomes a structured problem, while each regularizer is handled by its own proximity operator.
  • Proximity operators: Simple proximity operators, including soft-thresholding for the ℓ1 norm, make the regularizer updates explicit.The soft-threshold function acts component-wise on the input.
  • Computational bottleneck: The matrix inversion in the quadratic update is the computational bottleneck, and FFT-based efficiency requires compatible operator structure such as circulant matrices.This structural requirement limited earlier methods to periodic-boundary deconvolution.

III. IMAGE DECONVOLUTION WITH PERIODIC BC

This section reviews ADMM deconvolution with periodic boundary conditions using TV and frame-based regularization before extending the approach to unknown boundaries.

  • Section scope: Periodic-boundary deconvolution is formulated with TV-based and frame-based regularization, which are standard regularizers for imaging inverse problems.The subsequent development extends this ADMM framework to unknown boundaries.

A. Frame-Based Synthesis Formulation

The frame-based synthesis formulation represents the image through sparse frame coefficients and uses ADMM updates that are efficient under periodic convolution. FFT and frame transforms give O(n log n) iterations, with convergence guaranteed for the stated convex formulation.

  • Model: The synthesis model represents the estimated image as a linear combination of wavelet-frame elements, with an ℓ1 penalty encouraging sparse coefficients.The formulation uses x = Wz and combines a data-fidelity term with coefficient regularization.
  • Model: The observation model uses periodic convolution applied to the synthesized image, with additive white Gaussian noise.The noise has unit variance, with other variance values absorbable into the regularization parameter.
  • ADMM updates: ADMM separates the convolutional data term from the frame-coefficient regularizer, whose proximity update has a simple soft-thresholding form.The matrix update exploits the structure of the periodic convolution operator.
  • Efficient inversion: For Parseval frames, the Sherman–Morrison–Woodbury formula reduces the matrix inverse to operations involving the frame and convolution operators.The periodic convolution matrix is diagonalized by the DFT, enabling FFT-based computation.
  • Complexity: O(n log n) is the per-iteration cost under periodic boundaries for a large class of frames with fast analysis and synthesis transforms.The cost comes from FFT-based convolution operations and frame transforms.
  • Convergence: The synthesis-formulation ADMM instance converges to a solution under the stated convexity and frame assumptions.The proposition invokes the general ADMM convergence result after establishing existence and full-column-rank conditions.

B. Frame-Based Analysis Formulation

The frame-based analysis formulation optimizes the image directly through frame coefficients generated by an analysis operator. Under Parseval-frame and periodic-convolution structure, its ADMM iterations remain FFT-efficient and converge under the stated assumptions.

  • Model: The analysis formulation defines the optimization directly over the unknown image rather than synthesis coefficients.Its regularization is applied through an analysis operator P.
  • Frame assumptions: The analysis operator P is associated with a Parseval frame satisfying P*P = I, with normalization covering the more general tight-frame case.The operator may be redundant, so PP* need not equal I.
  • ADMM updates: The analysis formulation retains the same proximity operators as the synthesis case but changes the quadratic matrix-update expression.The difference is concentrated in line 4 of the ADMM algorithm.
  • Efficient inversion: Periodic convolution and the Parseval-frame identity reduce the matrix inverse to diagonal DFT-domain operations computable with the FFT.The resulting products by the DFT and inverse DFT have O(n log n) cost.
  • Complexity: Each analysis-formulation ADMM iteration has O(n log n) cost for the stated class of periodic-boundary problems.This complexity follows from the diagonalized inverse and FFT implementation.
  • Convergence: The analysis-formulation ADMM instance converges to a solution under the proposition’s frame, convexity, and existence conditions.The proof relies on full column rank of the analysis operator and the general ADMM convergence proposition.

C. Total Variation

The TV formulation uses ADMM to split data fidelity and total-variation terms, with periodic-boundary linear algebra enabling FFT-based updates and convergence under a mild condition on the blur operator.

  • The TV deconvolution problem is expressed in ADMM form using one data-fidelity function and one vector-norm function for each pixel’s gradient.The mappings use g_i(v) = λ ∥v∥2 and H(i) = D_i−1 for i = 2, ..., n+1.
  • TV(x) is defined as the sum of the Euclidean norms of horizontal and vertical differences at every pixel.This is the isotropic discrete approximation of continuous total variation.
  • Periodic boundary conditions diagonalize the convolution and difference operators, reducing the required matrix inversion to diagonal inversion plus DFT transforms.The inverse uses diagonal matrices and products by the direct and inverse DFT.
  • The resulting inverse has O(n) diagonal cost, while the FFT-based DFT products have O(n log n) cost.Products involving local horizontal and vertical differences cost O(n).
  • The ADMM updates use the data-fidelity proximity operator and vector-soft proximity operators for the gradient variables.The zero-vector convention is 0/∥0∥2 = 0.
  • Algorithm 3 converges to a solution of the TV problem when the constant vector is not in the kernel of A.The condition also ensures coercivity and existence of minimizers; it is satisfied by common low-pass blur filters.

A. The Observation Model

The observation model treats boundary pixels as unobserved and masks the convolved image so that retained observations do not depend on the unknown boundary. This yields a hybrid deconvolution–inpainting formulation that can also represent additional missing pixels.

  • Unknown boundaries are handled by modifying the observation model to y = MAx, where M selects observed pixels from the convolved image.The masking matrix has binary entries and fewer rows than columns.
  • M retains only image-domain locations where Ax does not depend on boundary pixels, making the convolution’s assumed boundary condition irrelevant.Periodic boundary conditions can therefore be adopted for computational convenience.
  • For a blur with support (1+2l)×(1+2l), masking removes an outer band of width l from the full convolved image.The construction assumes square images and a limited-support blurring filter.
  • The model combines deconvolution with inpainting: M = I gives periodic deconvolution, while A = I gives pure inpainting.The unobserved boundary pixels are estimated together with the deconvolved image.
  • The same formulation supports additional missing pixels beyond the unknown boundary, including generic inpainting problems.The paper applies the model to non-cyclic deblurring followed by pixel loss.

B. Frame-Based Synthesis Formulation

For frame-based synthesis, mask decoupling separates the spatial mask from the periodic convolution so ADMM retains FFT-based updates and convergence guarantees. A second approach uses a smaller conjugate-gradient system but lacks a formal convergence proof.

  • 1) Mask Decoupling (MD):: Directly incorporating MA into ADMM destroys the circulant structure needed for the original FFT-based matrix inversion.The difficulty comes from composing a spatial mask with a circulant convolution operator.
  • 1) Mask Decoupling (MD):: Mask decoupling introduces separate operations so the ADMM matrix inversion remains the periodic FFT-based inversion, changing only the proximity operator.
  • 1) Mask Decoupling (MD):: The new proximity update has O(n) cost because M∗M is diagonal and M∗y extends the observations with zeros.These quantities can be precomputed when µ1 remains constant.
  • 1) Mask Decoupling (MD):: FS-MD has leading per-iteration cost O(n log n) and converges to a solution of the frame-based synthesis problem.
  • 2) Using the Reeves-ˇSorel Technique:: The Reeves–Sorel approach reduces the inversion to an FFT-computed matrix and a smaller system whose dimension equals the number of unknown boundary pixels.The smaller system is solved with conjugate gradients.
  • 2) Using the Reeves-ˇSorel Technique:: FS-CG approximately solves the ADMM linear step with warm-started CG iterations, making convergence harder to analyze and leaving no formal proof presented.The authors rely on experimentally supported summability of error sequences in a related problem.

C. Frame-Based Analysis Formulation

The frame-based analysis formulation applies the same mask-decoupling idea to the analysis regularizer, preserving FFT-based computation and convergence. Its alternative CG implementation again uses an approximate smaller-system solve.

  • C. Frame-Based Analysis Formulation: The frame-based analysis problem combines masked data fidelity with an ℓ1 penalty on the analysis coefficients Px.
  • 1) Mask Decoupling (MD):: Mask decoupling maps the analysis problem into ADMM using the masked data-fidelity function while retaining the periodic-case auxiliary functions.
  • 1) Mask Decoupling (MD):: FA-MD changes only the proximity operator associated with the new masked data-fidelity function.
  • 1) Mask Decoupling (MD):: FA-MD has O(n log n) cost per iteration, matching the periodic-boundary case, and converges to a solution of the analysis problem.
  • D. TV-Based Deconvolution with Unknown Boundaries: The analysis formulation uses the observation model y = MAx for TV-based deconvolution with unknown boundaries.
  • 2) Using the Reeves-ˇSorel Technique:: For the analysis CG variant, MA is not circulant, so the inversion is rewritten using an FFT-computable matrix involving A and a smaller correction system.
  • 2) Using the Reeves-ˇSorel Technique:: FA-CG computes the correction inverse approximately with one warm-started CG iteration, while the FFT computes the circulant component.

1) Mask Decoupling (MD):

The mask-decoupling approach enables ADMM deconvolution with unknown boundaries and supports simultaneous non-periodic deblurring and inpainting. Experiments report artifact-free reconstructions, comparable quality to CG variants, and faster computation without inner CG iterations.

  • Mask Decoupling (MD): TV-MD converges to a solution under the mild condition 1̸ ∈ker(MA).The same condition is satisfied for low-pass blurs when at least one pixel is observed.
  • Mask Decoupling (MD): Mask decoupling models unknown boundaries by retaining the valid observed region and estimating the surrounding boundary pixels.The setup uses 238 × 238 observations from 256 × 256 images, leaving 8892 unknown boundary pixels.
  • Mask Decoupling (MD): Unknown-boundary TV-MD and frame-based methods avoid the severe artifacts produced by incorrectly assuming periodic boundary conditions.On Lena and cameraman, the proposed methods recover boundary pixels and produce deconvolved images without boundary artifacts, whereas periodic assumptions can fail badly.
  • Mask Decoupling (MD): MD variants are roughly 1.5 to 2 times faster than CG-based counterparts while achieving similar ISNR values.Average time per iteration is roughly 1.6 to 1.8 times faster, and MD avoids inner CG iterations.
  • Mask Decoupling (MD): The proposed methods also handle simultaneous non-periodic deblurring and inpainting with 20% randomly missing pixels.Periodic-boundary methods cannot be used in this setting, but the paper notes that the experiment is not a full assessment of inpainting effectiveness.

VI. CONCLUSIONS AND FUTURE WORK

The paper extends fast ADMM deconvolution to unknown boundaries and broader degradation models that include pixel loss. It provides convergence guarantees, validates TV and frame-based formulations experimentally, and identifies several future extensions.

  • The proposed ADMM strategy handles deconvolution with unknown boundaries, beyond earlier methods limited to periodic boundary conditions.
  • The degradation model also accommodates loss of pixels, enabling joint treatment of deconvolution and image inpainting.
  • The study covers total-variation regularization and frame-based analysis and synthesis formulations, with convergence guarantees for the proposed algorithms.
  • Experiments with large blur filters and several noise levels support the adequacy of the proposed approach.
  • Future work includes video deblurring, image and video super-resolution, spatially varying regularization, and iterative blind deconvolution.
Loading 1210.2687v2…