A fast patch-dictionary method for whole image recovery

Yangyang Xu; Wotao Yin

doi:10.3934/ipi.2016012

Article Contents

2016, Volume 10, Issue 2: 563-583. Doi: 10.3934/ipi.2016012

This issue Previous Article The relationship between backprojection and best linear unbiased estimation in synthetic-aperture radar imaging Next Article

A fast patch-dictionary method for whole image recovery

Yangyang Xu^1, and
Wotao Yin^2,

1.
Department of Computational and Applied Mathematics, Rice University, Houston, TX 77005
2.
Department of Mathematics, University of California, Los Angeles, CA 90095-1555

Received: May 31, 2014

Revised: August 31, 2015

Published: April 2016

Abstract Related Papers Cited by

Abstract

Many dictionary based methods in image processing use dictionary to represent all the patches of an image. We address the open issue of modeling an image by its overlapping patches: due to overlapping, there are a large number of patches, and to recover these patches, one must determine an excessive number of their dictionary coefficients. With very few exceptions, this issue has limited the applications of image-patch methods to the ``local'' tasks such as denoising, inpainting, cartoon-texture decomposition, super-resolution, and image deblurring, where one can process a few patches at a time. Our focus is the global imaging tasks such as compressive sensing and medical image recovery, where the whole image is encoded together in each measurement, 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 image-recovery and dictionary-learning methods, we numerically simulate image inpainting, compressive sensing recovery, and deblurring. Our recovery is more faithful than those by a total variation method and a method based on overlapping patches. Our Matlab code is competitive in terms of both speed and quality.

Keywords:

Mathematics Subject Classification: Primary: 94A08, 94A12; Secondary: 90C90.

Citation:

Related Papers

Cited by

References

[1]	M. Aharon, M. Elad and A. Bruckstein, K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation, Signal Processing, IEEE Transactions on, 54 (2006), 4311-4322.
[2]	G. Anbarjafari and H. Demirel, Image super resolution based on interpolation of wavelet domain high frequency subbands and the spatial domain input image, ETRI J, 32 (2010), 390-394.doi: 10.4218/etrij.10.0109.0303.
[3]	A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM Journal on Imaging Sciences, 2 (2009), 183-202.doi: 10.1137/080716542.
[4]	E. Bierstone and P. D. Milman, Semianalytic and subanalytic sets, Publications Mathématiques de l'IHÉS, 67 (1988), 5-42.
[5]	J. Bolte, A. Daniilidis and A. Lewis, The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM Journal on Optimization, 17 (2007), 1205-1223.doi: 10.1137/050644641.
[6]	W. Dong, L. Zhang, G. Shi and X. Wu, Image deblurring and super-resolution by adaptive sparse domain selection and adaptive regularization, Image Processing, IEEE Transactions on, 20 (2011), 1838-1857.doi: 10.1109/TIP.2011.2108306.
[7]	M. Elad and M. Aharon, Image denoising via sparse and redundant representations over learned dictionaries, Image Processing, IEEE Transactions on, 15 (2006), 3736-3745.doi: 10.1109/TIP.2006.881969.
[8]	K. Engan, S. O. Aase and J. H. Husøy, Multi-frame compression: Theory and design, Signal Processing, 80 (2000), 2121-2140.doi: 10.1016/S0165-1684(00)00072-4.
[9]	L. Fang, S. Li, Q. Nie, J. A. Izatt, C. A. Toth and S. Farsiu, Sparsity based denoising of spectral domain optical coherence tomography images, Biomedical optics express, 3 (2012), 927-942.doi: 10.1364/BOE.3.000927.
[10]	K. Kreutz-Delgado, J. F. Murray, B. D. Rao, K. Engan, T.-W. Lee and T. J. Sejnowski, Dictionary learning algorithms for sparse representation, Neural computation, 15 (2003), 349-396.doi: 10.1162/089976603762552951.
[11]	C. Li, W. Yin and Y. Zhang, TVAL3: TV minimization by augmented lagrangian and alternating direction algorithms, 2009.
[12]	S. Łojasiewicz, Sur la géométrie semi-et sous-analytique, Ann. Inst. Fourier (Grenoble), 43 (1993), 1575-1595.doi: 10.5802/aif.1384.
[13]	J. Mairal, F. Bach and J. Ponce, Task-driven dictionary learning, Pattern Analysis and Machine Intelligence, IEEE Transactions on, 34 (2012), 791-804.doi: 10.1109/TPAMI.2011.156.
[14]	J. Mairal, F. Bach, J. Ponce and G. Sapiro, Online dictionary learning for sparse coding, in Proceedings of the 26th Annual International Conference on Machine Learning, ACM, 2009, 689-696.doi: 10.1145/1553374.1553463.
[15]	J. Mairal, F. Bach, J. Ponce, G. Sapiro and A. Zisserman, Supervised dictionary learning, arXiv preprint, arXiv:0809.3083, 2008.
[16]	D. Martin, C. Fowlkes, D. Tal and J. Malik, A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics, in Computer Vision, 2001. ICCV 2001. Proceedings. Eighth IEEE International Conference on, IEEE, 2 (2001), 416-423.doi: 10.1109/ICCV.2001.937655.
[17]	I. Ramirez, P. Sprechmann and G. Sapiro, Classification and clustering via dictionary learning with structured incoherence and shared features, in Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on, IEEE, 2010, 3501-3508.doi: 10.1109/CVPR.2010.5539964.
[18]	S. Ravishankar and Y. Bresler, Mr image reconstruction from highly undersampled k-space data by dictionary learning, Medical Imaging, IEEE Transactions on, 30 (2011), 1028-1041.doi: 10.1109/TMI.2010.2090538.
[19]	K. Skretting and K. Engan, Recursive least squares dictionary learning algorithm, Signal Processing, IEEE Transactions on, 58 (2010), 2121-2130.doi: 10.1109/TSP.2010.2040671.
[20]	I. Tosic and P. Frossard, Dictionary learning, Signal Processing Magazine, IEEE, 28 (2011), 27-38.doi: 10.1109/MSP.2010.939537.
[21]	P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization, Journal of Optimization Theory and Applications, 109 (2001), 475-494.doi: 10.1023/A:1017501703105.
[22]	Y. Xu and W. Yin, A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion, SIAM Journal on Imaging Sciences, 6 (2013), 1758-1789.doi: 10.1137/120887795.
[23]	Y. Xu, W. Yin and S. Osher, Learning circulant sensing kernels, Inverse Problems and Imaging, 8 (2014), 901-923.doi: 10.3934/ipi.2014.8.901.
[24]	Y Zhang, J. Yang and Wotao Yin, YALL1: Your Algorithms for l1, MATLAB software, http://yall1.blogs.rice.edu/, (2010).
[25]	Y. Zhao, J. Yang, Q. Zhang, L. Song, Y. Cheng and Q. Pan, Hyperspectral imagery super-resolution by sparse representation and spectral regularization, EURASIP Journal on Advances in Signal Processing, 2011 (2011), 1-10.doi: 10.1186/1687-6180-2011-87.