# American Institute of Mathematical Sciences

May  2016, 10(2): 563-583. doi: 10.3934/ipi.2016012

## A fast patch-dictionary method for whole image recovery

 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  June 2014 Revised  September 2015 Published  May 2016

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.
Citation: Yangyang Xu, Wotao Yin. A fast patch-dictionary method for whole image recovery. Inverse Problems & Imaging, 2016, 10 (2) : 563-583. doi: 10.3934/ipi.2016012
##### References:
 [1] M. Aharon, M. Elad and A. Bruckstein, K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation,, Signal Processing, 54 (2006), 4311.   Google Scholar [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.  doi: 10.4218/etrij.10.0109.0303.  Google Scholar [3] A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems,, SIAM Journal on Imaging Sciences, 2 (2009), 183.  doi: 10.1137/080716542.  Google Scholar [4] E. Bierstone and P. D. Milman, Semianalytic and subanalytic sets,, Publications Mathématiques de l'IHÉS, 67 (1988), 5.   Google Scholar [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.  doi: 10.1137/050644641.  Google Scholar [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, 20 (2011), 1838.  doi: 10.1109/TIP.2011.2108306.  Google Scholar [7] M. Elad and M. Aharon, Image denoising via sparse and redundant representations over learned dictionaries,, Image Processing, 15 (2006), 3736.  doi: 10.1109/TIP.2006.881969.  Google Scholar [8] K. Engan, S. O. Aase and J. H. Husøy, Multi-frame compression: Theory and design,, Signal Processing, 80 (2000), 2121.  doi: 10.1016/S0165-1684(00)00072-4.  Google Scholar [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.  doi: 10.1364/BOE.3.000927.  Google Scholar [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.  doi: 10.1162/089976603762552951.  Google Scholar [11] C. Li, W. Yin and Y. Zhang, TVAL3: TV minimization by augmented lagrangian and alternating direction algorithms,, 2009., ().   Google Scholar [12] S. Łojasiewicz, Sur la géométrie semi-et sous-analytique,, Ann. Inst. Fourier (Grenoble), 43 (1993), 1575.  doi: 10.5802/aif.1384.  Google Scholar [13] J. Mairal, F. Bach and J. Ponce, Task-driven dictionary learning,, Pattern Analysis and Machine Intelligence, 34 (2012), 791.  doi: 10.1109/TPAMI.2011.156.  Google Scholar [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, (2009), 689.  doi: 10.1145/1553374.1553463.  Google Scholar [15] J. Mairal, F. Bach, J. Ponce, G. Sapiro and A. Zisserman, Supervised dictionary learning,, arXiv preprint, (2008).   Google Scholar [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, 2 (2001), 416.  doi: 10.1109/ICCV.2001.937655.  Google Scholar [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), 3501.  doi: 10.1109/CVPR.2010.5539964.  Google Scholar [18] S. Ravishankar and Y. Bresler, Mr image reconstruction from highly undersampled k-space data by dictionary learning,, Medical Imaging, 30 (2011), 1028.  doi: 10.1109/TMI.2010.2090538.  Google Scholar [19] K. Skretting and K. Engan, Recursive least squares dictionary learning algorithm,, Signal Processing, 58 (2010), 2121.  doi: 10.1109/TSP.2010.2040671.  Google Scholar [20] I. Tosic and P. Frossard, Dictionary learning,, Signal Processing Magazine, 28 (2011), 27.  doi: 10.1109/MSP.2010.939537.  Google Scholar [21] P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization,, Journal of Optimization Theory and Applications, 109 (2001), 475.  doi: 10.1023/A:1017501703105.  Google Scholar [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.  doi: 10.1137/120887795.  Google Scholar [23] Y. Xu, W. Yin and S. Osher, Learning circulant sensing kernels,, Inverse Problems and Imaging, 8 (2014), 901.  doi: 10.3934/ipi.2014.8.901.  Google Scholar [24] Y Zhang, J. Yang and Wotao Yin, YALL1: Your Algorithms for l1,, MATLAB software, (2010).   Google Scholar [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.  doi: 10.1186/1687-6180-2011-87.  Google Scholar

show all references

##### References:
 [1] M. Aharon, M. Elad and A. Bruckstein, K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation,, Signal Processing, 54 (2006), 4311.   Google Scholar [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.  doi: 10.4218/etrij.10.0109.0303.  Google Scholar [3] A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems,, SIAM Journal on Imaging Sciences, 2 (2009), 183.  doi: 10.1137/080716542.  Google Scholar [4] E. Bierstone and P. D. Milman, Semianalytic and subanalytic sets,, Publications Mathématiques de l'IHÉS, 67 (1988), 5.   Google Scholar [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.  doi: 10.1137/050644641.  Google Scholar [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, 20 (2011), 1838.  doi: 10.1109/TIP.2011.2108306.  Google Scholar [7] M. Elad and M. Aharon, Image denoising via sparse and redundant representations over learned dictionaries,, Image Processing, 15 (2006), 3736.  doi: 10.1109/TIP.2006.881969.  Google Scholar [8] K. Engan, S. O. Aase and J. H. Husøy, Multi-frame compression: Theory and design,, Signal Processing, 80 (2000), 2121.  doi: 10.1016/S0165-1684(00)00072-4.  Google Scholar [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.  doi: 10.1364/BOE.3.000927.  Google Scholar [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.  doi: 10.1162/089976603762552951.  Google Scholar [11] C. Li, W. Yin and Y. Zhang, TVAL3: TV minimization by augmented lagrangian and alternating direction algorithms,, 2009., ().   Google Scholar [12] S. Łojasiewicz, Sur la géométrie semi-et sous-analytique,, Ann. Inst. Fourier (Grenoble), 43 (1993), 1575.  doi: 10.5802/aif.1384.  Google Scholar [13] J. Mairal, F. Bach and J. Ponce, Task-driven dictionary learning,, Pattern Analysis and Machine Intelligence, 34 (2012), 791.  doi: 10.1109/TPAMI.2011.156.  Google Scholar [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, (2009), 689.  doi: 10.1145/1553374.1553463.  Google Scholar [15] J. Mairal, F. Bach, J. Ponce, G. Sapiro and A. Zisserman, Supervised dictionary learning,, arXiv preprint, (2008).   Google Scholar [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, 2 (2001), 416.  doi: 10.1109/ICCV.2001.937655.  Google Scholar [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), 3501.  doi: 10.1109/CVPR.2010.5539964.  Google Scholar [18] S. Ravishankar and Y. Bresler, Mr image reconstruction from highly undersampled k-space data by dictionary learning,, Medical Imaging, 30 (2011), 1028.  doi: 10.1109/TMI.2010.2090538.  Google Scholar [19] K. Skretting and K. Engan, Recursive least squares dictionary learning algorithm,, Signal Processing, 58 (2010), 2121.  doi: 10.1109/TSP.2010.2040671.  Google Scholar [20] I. Tosic and P. Frossard, Dictionary learning,, Signal Processing Magazine, 28 (2011), 27.  doi: 10.1109/MSP.2010.939537.  Google Scholar [21] P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization,, Journal of Optimization Theory and Applications, 109 (2001), 475.  doi: 10.1023/A:1017501703105.  Google Scholar [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.  doi: 10.1137/120887795.  Google Scholar [23] Y. Xu, W. Yin and S. Osher, Learning circulant sensing kernels,, Inverse Problems and Imaging, 8 (2014), 901.  doi: 10.3934/ipi.2014.8.901.  Google Scholar [24] Y Zhang, J. Yang and Wotao Yin, YALL1: Your Algorithms for l1,, MATLAB software, (2010).   Google Scholar [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.  doi: 10.1186/1687-6180-2011-87.  Google Scholar
 [1] Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial & Management Optimization, 2019, 15 (4) : 2009-2021. doi: 10.3934/jimo.2018134 [2] Nurullah Yilmaz, Ahmet Sahiner. On a New Smoothing Technique for Non-smooth, Non-convex Optimization. Numerical Algebra, Control & Optimization, 2019, 0 (0) : 0-0. doi: 10.3934/naco.2020004 [3] Tong Li, Jeungeun Park. Stability of traveling waves of models for image processing with non-convex nonlinearity. Communications on Pure & Applied Analysis, 2018, 17 (3) : 959-985. doi: 10.3934/cpaa.2018047 [4] C. M. Elliott, B. Gawron, S. Maier-Paape, E. S. Van Vleck. Discrete dynamics for convex and non-convex smoothing functionals in PDE based image restoration. Communications on Pure & Applied Analysis, 2006, 5 (1) : 181-200. doi: 10.3934/cpaa.2006.5.181 [5] Meixia Li, Changyu Wang, Biao Qu. Non-convex semi-infinite min-max optimization with noncompact sets. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1859-1881. doi: 10.3934/jimo.2017022 [6] Qilin Wang, Liu He, Shengjie Li. Higher-order weak radial epiderivatives and non-convex set-valued optimization problems. Journal of Industrial & Management Optimization, 2019, 15 (2) : 465-480. doi: 10.3934/jimo.2018051 [7] Yoon Mo Jung, Taeuk Jeong, Sangwoon Yun. Non-convex TV denoising corrupted by impulse noise. Inverse Problems & Imaging, 2017, 11 (4) : 689-702. doi: 10.3934/ipi.2017032 [8] Tong Li, Hui Yin. Convergence rate to strong boundary layer solutions for generalized BBM-Burgers equations with non-convex flux. Communications on Pure & Applied Analysis, 2014, 13 (2) : 835-858. doi: 10.3934/cpaa.2014.13.835 [9] Asadollah Aghajani. Regularity of extremal solutions of semilinear elliptic problems with non-convex nonlinearities on general domains. Discrete & Continuous Dynamical Systems - A, 2017, 37 (7) : 3521-3530. doi: 10.3934/dcds.2017150 [10] Jingang Xiong, Jiguang Bao. The obstacle problem for Monge-Ampère type equations in non-convex domains. Communications on Pure & Applied Analysis, 2011, 10 (1) : 59-68. doi: 10.3934/cpaa.2011.10.59 [11] . Adimurthi, Siddhartha Mishra, G.D. Veerappa Gowda. Existence and stability of entropy solutions for a conservation law with discontinuous non-convex fluxes. Networks & Heterogeneous Media, 2007, 2 (1) : 127-157. doi: 10.3934/nhm.2007.2.127 [12] Alfonso Castro, Rosa Pardo. A priori estimates for positive solutions to subcritical elliptic problems in a class of non-convex regions. Discrete & Continuous Dynamical Systems - B, 2017, 22 (3) : 783-790. doi: 10.3934/dcdsb.2017038 [13] Wei Wan, Weihong Guo, Jun Liu, Haiyang Huang. Non-local blind hyperspectral image super-resolution via 4d sparse tensor factorization and low-rank. Inverse Problems & Imaging, 2020, 14 (2) : 339-361. doi: 10.3934/ipi.2020015 [14] Juan Carlos De los Reyes, Carola-Bibiane Schönlieb. Image denoising: Learning the noise model via nonsmooth PDE-constrained optimization. Inverse Problems & Imaging, 2013, 7 (4) : 1183-1214. doi: 10.3934/ipi.2013.7.1183 [15] Andrea Braides, Valeria Chiadò Piat. Non convex homogenization problems for singular structures. Networks & Heterogeneous Media, 2008, 3 (3) : 489-508. doi: 10.3934/nhm.2008.3.489 [16] Lingchen Kong, Naihua Xiu, Guokai Liu. Partial $S$-goodness for partially sparse signal recovery. Numerical Algebra, Control & Optimization, 2014, 4 (1) : 25-38. doi: 10.3934/naco.2014.4.25 [17] Kanghui Guo and Demetrio Labate. Sparse shearlet representation of Fourier integral operators. Electronic Research Announcements, 2007, 14: 7-19. doi: 10.3934/era.2007.14.7 [18] Wanyou Cheng, Zixin Chen, Donghui Li. Nomonotone spectral gradient method for sparse recovery. Inverse Problems & Imaging, 2015, 9 (3) : 815-833. doi: 10.3934/ipi.2015.9.815 [19] Robert M. Strain. Optimal time decay of the non cut-off Boltzmann equation in the whole space. Kinetic & Related Models, 2012, 5 (3) : 583-613. doi: 10.3934/krm.2012.5.583 [20] Fatemeh Ahangari. Conformal deformations of a specific class of lorentzian manifolds with non-irreducible holonomy representation. Numerical Algebra, Control & Optimization, 2019, 9 (4) : 401-412. doi: 10.3934/naco.2019039

2018 Impact Factor: 1.469

## Metrics

• PDF downloads (43)
• HTML views (0)
• Cited by (8)

## Other articlesby authors

• on AIMS
• on Google Scholar

[Back to Top]