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

(Abstract and MATLAB code)

Abstract (of [1]):

The alternating direction method of multipliers (ADMM) has recently sparked interest as a flexible and efficient optimization tool for inverse problems, namely, image 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.

References:

[1] M. S. C. Almeida and M. A. T. Figueiredo, “Deconvolving images with Unknown Boundaries using the Alternating Direction Method of Multipliers”, IEEE Trans. Image Processing, vol. 22, No. 8, pp. 3074-3086, 2013. (available at http://arxiv.org/abs/1210.2687).

[2] M. S. C. Almeida and M. A. T. Figueiredo, “Frame-based image deblurring with unknown boundary conditions using the Alternating Direction Method of Multipliers", IEEE International Conf. on Image Processing – ICIP’2013, Melbourne, Australia, September, 2013.

MATLAB Code: Deblurring with UBC using ADMM.

If you find any bug, please report it to me: M. S. C. Almeida. Thank you!

License:  This code is copyright of Mário A. T. Figueiredo and Mariana S.C. Almeida. Free permission is given for their use for nonprofit research purposes. Any other use is prohibited, unless a license is previously obtained.

This package is compressed with 7-zip.

ACKNOWLEDGEMENTS: This work was partially supported by Fundação para a Ciência e Tecnologia (FCT), under grants PTDC/EEA-TEL/104515/2008, PEst-OE/EEI/LA0008/2011, PEst-OE/EEI/LA0008/2013, PTDC/EEI-PRO/1470/2012, and the fellowship SFRH/BPD/69344/2010.