A fast patch-dictionary method for whole image recovery

DOI10.3934/IPI.2016012zbMATH Open1395.94071arXiv1408.3740OpenAlexW2963349467MaRDI QIDQ326397FDOQ326397

Wotao Yin, Yangyang Xu

Publication date: 12 October 2016

Published in: Inverse Problems and Imaging (Search for Journal in Brave)

Abstract: Various algorithms have been proposed for dictionary learning. Among those for image processing, many use image patches to form dictionaries. This paper focuses on whole-image recovery from corrupted linear measurements. We address the open issue of representing an image by overlapping patches: the overlapping leads to an excessive number of dictionary coefficients to determine. With very few exceptions, this issue has limited the applications of image-patch methods to the local kind of tasks such as denoising, inpainting, cartoon-texture decomposition, super-resolution, and image deblurring, for which one can process a few patches at a time. Our focus is global imaging tasks such as compressive sensing and medical image recovery, where the whole image is encoded together, making it either impossible or very ineffective to update a few patches at a time. Our strategy is to divide the sparse recovery into multiple subproblems, each of which handles a subset of non-overlapping patches, and then the results of the subproblems are averaged to yield the final recovery. This simple strategy is surprisingly effective in terms of both quality and speed. In addition, we accelerate computation of the learned dictionary by applying a recent block proximal-gradient method, which not only has a lower per-iteration complexity but also takes fewer iterations to converge, compared to the current state-of-the-art. We also establish that our algorithm globally converges to a stationary point. Numerical results on synthetic data demonstrate that our algorithm can recover a more faithful dictionary than two state-of-the-art methods. Combining our whole-image recovery and dictionary-learning methods, we numerically simulate image inpainting, compressive sensing recovery, and deblurring. Our recovery is more faithful than those of a total variation method and a method based on overlapping patches.

Full work available at URL: https://arxiv.org/abs/1408.3740

zbMATH Keywords

non-convex optimizationsparse representationdictionary learningnon-overlapping patcheswhole-image recovery

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• $rm K$-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation
• Convergence of a block coordinate descent method for nondifferentiable minimization
• Image Deblurring and Super-Resolution by Adaptive Sparse Domain Selection and Adaptive Regularization
• Semianalytic and subanalytic sets
• A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion
• On semi- and subanalytic geometry
• The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
• Dictionary Learning Algorithms for Sparse Representation
• Multi-frame compression: theory and design.
• Recursive Least Squares Dictionary Learning Algorithm
• Learning circulant sensing kernels

Cited In (9)

• Smoothing techniques and difference of convex functions algorithms for image reconstructions
• Title not available (Why is that?)
• Patch-Based Holographic Image Sensing
• A dictionary learning algorithm for compression and reconstruction of streaming data in preset order
• Truncated Nuclear Norm Minimization Based Group Sparse Representation for Image Restoration
• A globally convergent algorithm for nonconvex optimization based on block coordinate update
• Block Bregman Majorization Minimization with Extrapolation
• First- and Second-Order Methods for Online Convolutional Dictionary Learning
• Geological facies recovery based on weighted \(\ell_1\)-regularization

Uses Software

• Matlab
• Yall1

This page was built for publication: A fast patch-dictionary method for whole image recovery

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q326397)