A General Framework for Fast Image Deconvolution with Incomplete Observations. Applications to Unknown Boundaries, Inpainting, Superresolution, and Demosaicing

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, such as image boundaries, by explicitly estimating these missing pixels. This approach allows for the use of fast, FFT-based deconvolution methods while avoiding artifacts, and is demonstrated to be effective across various image restoration tasks like inpainting, super-resolution, and demosaicing.

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 unobserved, for instance, at the image boundaries, or in applications like inpainting, super-resolution, and demosaicing. Traditional methods that assume complete observations often rely on approximations (like periodic boundary conditions) leading to artifacts, or use exact models with non-diagonalizable operators, resulting in slow computations. This paper tackles the problem of performing fast and artifact-free deconvolution when faced with these incomplete observations.

Methods

The core contribution is a general framework for deconvolution with incomplete observations. This framework works by iteratively alternating between estimating the sharp image and the unobserved pixels. Crucially, it allows the use of existing fast deconvolution methods (which often assume diagonal operators, e.g., via FFT) for estimating the sharp image, while simultaneously estimating the missing pixels.

A specific implementation of this framework is proposed using the Alternating Direction Method of Multipliers (ADMM). This implementation is a "partial" ADMM, meaning not all variables are dualized, which leads to improved computational efficiency. The authors provide a proof of convergence for this partial ADMM. The framework is designed to be flexible, allowing integration with various deconvolution techniques.

Datasets

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

  • Cameraman image: Used for deblurring experiments.
  • Lena image: Used for deblurring and inpainting experiments.
  • Pavia hyperspectral image (crop): Used for super-resolution experiments.
  • Parrot image (crop): Used for demosaicing experiments.

These images are blurred using synthetic kernels (boxcar and Gaussian filters) and corrupted with additive Gaussian noise to simulate real-world scenarios.

Key Insights and Ideas

  • Explicitly estimating unobserved pixels is key: Instead of making assumptions or masking out missing data, the framework directly estimates these pixels, leading to more accurate and artifact-free results.
  • Framework flexibility: The proposed framework acts as a wrapper, enabling existing fast deconvolution methods (that rely on diagonal operators) to handle incomplete observations without modification.
  • Partial ADMM for efficiency: By applying ADMM selectively, the authors achieve a computationally efficient algorithm that still guarantees convergence.
  • Unified approach for diverse problems: The framework demonstrates its versatility by successfully addressing deconvolution, inpainting, super-resolution, and demosaicing under a single conceptual umbrella.

Key Results

  • Artifact Reduction: The proposed framework, when used with existing methods like IDD-BM3D, significantly reduces artifacts compared to direct application or edge tapering, producing sharp images all the way to the borders.
  • Competitive Performance: The proposed ADMM-based method (Proposed-AD) achieved performance comparable to state-of-the-art methods like AM in terms of image quality.
  • Computational Efficiency: The Proposed-AD method was often faster than other methods, particularly AM, especially for smaller blur sizes. For example, in Table I, for cameraman with Gaussian blurs, Proposed-AD was faster than AM.
  • Broad Applicability: The framework and its ADMM implementation were successfully applied to deconvolution, deconvolution with inpainting, super-resolution, and demosaicing, all with unknown boundaries, yielding visually indistinguishable results from other methods in many cases.

Limitations and Future Work

  • Convergence Guarantee Nuances: While a convergence proof is provided for the partial ADMM, it relies on certain assumptions (e.g., D being full column rank). The authors note that in their specific implementation with isotropic TV regularization, D is not full column rank, meaning the formal guarantee doesn't strictly apply. However, they observed consistent convergence in practice. They suggest potential ways to address this, such as modifying the regularizer or adding small epsilon terms.
  • Parameter Tuning: Like most optimization-based methods, the proposed approach requires careful tuning of parameters (e.g., regularization parameter λ, penalty parameter μ). The paper discusses strategies for setting these parameters, including adaptive methods.
  • Future Work: The paper implicitly suggests future work by demonstrating the framework's broad applicability. Further exploration of different regularization techniques and optimization strategies within the framework could lead to even more refined algorithms. The authors also mention that their method is a "partial" ADMM, hinting at potential for further ADMM-based extensions.

Summary updated

Abstract

In image deconvolution problems, the diagonalization of the underlying operators by means of the 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, through the use of 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{simoes2016general,
  author = {Miguel Simões and Luís B. Almeida and José M. Bioucas-Dias and Jocelyn Chanussot},
  title = {{A General Framework for Fast Image Deconvolution with Incomplete Observations. Applications to Unknown Boundaries, Inpainting, Superresolution, and Demosaicing}},
  journal = {IEEE Trans. Image Process.},
  year = {2016},
  url = {https://openreview.net/forum?id=4sODlk8A5y},
}
Figure