A Framework for Fast Image Deconvolution With Incomplete Observations

Miguel Simões, Luís B. Almeida, José M. Bioucas-Dias, Jocelyn Chanussot

TL;DR

This paper introduces a novel framework for image deconvolution that efficiently handles incomplete observations (like missing pixels at image boundaries) by iteratively estimating both the sharp image and the missing pixels. This approach allows the use of fast, FFT-based deconvolution methods while avoiding artifacts, achieving state-of-the-art results across various image restoration tasks.

What Problem Does This Paper Address?

Image deconvolution aims to recover a sharp image from a blurred one. A major challenge arises when parts of the blurred image are missing or unobserved, such as at the edges of an image due to sensor limitations or specific processing tasks like inpainting or super-resolution. Traditional methods that use Fast Fourier Transforms (FFTs) for speed rely on assumptions of periodic or known boundary conditions, which can lead to artifacts when these assumptions are violated. Conversely, methods that handle unknown boundaries often use non-diagonalizable operators, making them computationally slow, or employ inexact models that introduce artifacts. This paper addresses the need for a fast, accurate, and general deconvolution method that can handle these incomplete observations without sacrificing image quality.

Methods

The core of the proposed solution is a framework that treats the problem of incomplete observations as an iterative process. Instead of trying to directly deconvolve the observed (incomplete) image, the framework introduces an auxiliary variable representing the unobserved pixels (including boundary regions). The algorithm then alternates between:

  1. Estimating the sharp image (x): This step leverages existing fast deconvolution methods, particularly those that assume circular boundary conditions (which are FFT-friendly).
  2. Estimating the unobserved pixels (z): This step reconstructs the missing parts of the blurred image based on the current estimate of the sharp image.

This iterative estimation of both the sharp image and the missing pixels allows the framework to work with diagonalized operators, thus maintaining computational speed.

For a specific implementation, the authors propose a partial Alternating Direction Method of Multipliers (ADMM). Unlike standard ADMM, which dualizes all variables, their "partial" ADMM only dualizes a subset of variables. This optimization is crucial for computational efficiency, especially when dealing with large matrices. The paper provides a theoretical proof of convergence for this partial ADMM approach.

Datasets

The paper does not introduce new datasets. Instead, it uses standard benchmark images for evaluation:

  • Cameraman: Used for deblurring experiments.
  • Lena: Used for deblurring, inpainting, and super-resolution experiments.
  • Parrot: Used for demosaicing experiments.

These images were blurred using various boxcar and Gaussian filters, and noise was added to simulate realistic scenarios.

Key Insights and Ideas

  • Separating the problem: The key insight is to decouple the estimation of the sharp image from the estimation of the unobserved pixels. This allows the use of efficient, FFT-based deconvolution for the sharp image while explicitly addressing the missing data.
  • Framework generality: The proposed framework is highly general. It can be used to adapt existing deconvolution methods (that assume specific boundary conditions) to handle unknown boundaries, effectively extending their applicability without redesigning them from scratch.
  • Partial ADMM for efficiency: The development of a "partial" ADMM is a significant contribution, enabling efficient optimization by avoiding the full dualization of variables, which is often computationally prohibitive.
  • Avoiding artifacts: By explicitly estimating the unobserved pixels, the method avoids the artifacts that plague techniques relying on artificial boundary extensions or inexact convolution models.

Key Results

  • State-of-the-art performance: The proposed framework, particularly with its partial ADMM implementation, achieved performance comparable to or exceeding existing state-of-the-art methods in terms of image quality.
  • Speed advantage: The framework, by enabling the use of FFT-based deconvolution, offers significant speedups compared to methods that rely on non-diagonalizable operators. For example, in experiments, the proposed method was often faster than other primal-dual methods.
  • Versatility: The framework was successfully applied to four distinct image restoration tasks: deconvolution, deconvolution with inpainting, super-resolution, and demosaicing, all under conditions of incomplete observations.
  • Improved boundary handling: When adapting a state-of-the-art method (IDD-BM3D) using the framework, the resulting deconvolution significantly reduced artifacts and improved image sharpness at the boundaries compared to direct application or simple edge tapering.

Limitations and Future Work

  • Convergence proof for partial ADMM: While a convergence proof is provided for the partial ADMM, it relies on certain assumptions (e.g., D being full column rank) that might not always hold for all regularizers. The authors note that in practice, their method always converged, and they suggest modifications to the regularizer to formally satisfy the convergence conditions.
  • Parameter tuning: Like most optimization algorithms, the proposed method has parameters (e.g., regularization parameter λ, penalty parameter μ) that require tuning. The paper discusses strategies for adaptive parameter setting but acknowledges that optimal tuning can be a complex issue.
  • Computational cost of specific methods: While the framework itself is fast, the performance of specific implementations can vary. For instance, the paper notes that the CM method, while effective, showed significantly lower computational performance compared to ADMM-based approaches.

Future work could explore more advanced regularization techniques, further optimization of the ADMM implementation, and investigation into more robust parameter selection strategies.

Summary updated

Abstract

In image deconvolution problems, the diagonalization of the underlying operators by means of the fast Fourier transform (FFT) usually yields very large speedups. When there are incomplete observations (e.g., in the case of unknown boundaries), standard deconvolution techniques normally involve non-diagonalizable operators, resulting in rather slow methods or, otherwise, use inexact convolution models, resulting in the occurrence of artifacts in the enhanced images. In this paper, we propose a new deconvolution framework for images with incomplete observations that allows us to work with diagonalized convolution operators, and therefore is very fast. We iteratively alternate the estimation of the unknown pixels and of the deconvolved image, using, e.g., an FFT-based deconvolution method. This framework is an efficient, high-quality alternative to existing methods of dealing with the image boundaries, such as edge tapering. It can be used with any fast deconvolution method. We give an example in which a state-of-the-art method that assumes periodic boundary conditions is extended, using this framework, to unknown boundary conditions. Furthermore, we propose a specific implementation of this framework, based on the alternating direction method of multipliers (ADMM). We provide a proof of convergence for the resulting algorithm, which can be seen as a “partial” ADMM, in which not all variables are dualized. We report experimental comparisons with other primal-dual methods, where the proposed one performed at the level of the state of the art. Four different kinds of applications were tested in the experiments: deconvolution, deconvolution with inpainting, superresolution, and demosaicing, all with unknown boundaries.
BibTeX
@article{simoes2016framework,
  author = {Miguel Simões and Luís B. Almeida and José M. Bioucas-Dias and Jocelyn Chanussot},
  title = {{A Framework for Fast Image Deconvolution With Incomplete Observations}},
  journal = {IEEE Trans. Image Process.},
  year = {2016},
  url = {https://openreview.net/forum?id=4sODlk8A5y},
}
Figure