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, IEEE Transactions on, 54 (2006), 4311-4322. 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-394. 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-202. 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-42.  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-1223. 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, IEEE Transactions on, 20 (2011), 1838-1857. 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, IEEE Transactions on, 15 (2006), 3736-3745. 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-2140. 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-942. 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-396. 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-1595. doi: 10.5802/aif.1384.  Google Scholar

[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.  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, ACM, 2009, 689-696. doi: 10.1145/1553374.1553463.  Google Scholar

[15]

J. Mairal, F. Bach, J. Ponce, G. Sapiro and A. Zisserman, Supervised dictionary learning, arXiv preprint, arXiv:0809.3083, 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, 2001. ICCV 2001. Proceedings. Eighth IEEE International Conference on, IEEE, 2 (2001), 416-423. 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 IEEE Conference on, IEEE, 2010, 3501-3508. 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, IEEE Transactions on, 30 (2011), 1028-1041. doi: 10.1109/TMI.2010.2090538.  Google Scholar

[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.  Google Scholar

[20]

I. Tosic and P. Frossard, Dictionary learning, Signal Processing Magazine, IEEE, 28 (2011), 27-38. 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-494. 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-1789. 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-923. doi: 10.3934/ipi.2014.8.901.  Google Scholar

[24]

Y Zhang, J. Yang and Wotao Yin, YALL1: Your Algorithms for l1, MATLAB software, http://yall1.blogs.rice.edu/, (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-10. 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, IEEE Transactions on, 54 (2006), 4311-4322. 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-394. 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-202. 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-42.  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-1223. 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, IEEE Transactions on, 20 (2011), 1838-1857. 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, IEEE Transactions on, 15 (2006), 3736-3745. 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-2140. 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-942. 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-396. 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-1595. doi: 10.5802/aif.1384.  Google Scholar

[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.  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, ACM, 2009, 689-696. doi: 10.1145/1553374.1553463.  Google Scholar

[15]

J. Mairal, F. Bach, J. Ponce, G. Sapiro and A. Zisserman, Supervised dictionary learning, arXiv preprint, arXiv:0809.3083, 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, 2001. ICCV 2001. Proceedings. Eighth IEEE International Conference on, IEEE, 2 (2001), 416-423. 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 IEEE Conference on, IEEE, 2010, 3501-3508. 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, IEEE Transactions on, 30 (2011), 1028-1041. doi: 10.1109/TMI.2010.2090538.  Google Scholar

[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.  Google Scholar

[20]

I. Tosic and P. Frossard, Dictionary learning, Signal Processing Magazine, IEEE, 28 (2011), 27-38. 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-494. 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-1789. 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-923. doi: 10.3934/ipi.2014.8.901.  Google Scholar

[24]

Y Zhang, J. Yang and Wotao Yin, YALL1: Your Algorithms for l1, MATLAB software, http://yall1.blogs.rice.edu/, (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-10. 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, 2020, 10 (3) : 317-330. 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]

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

[6]

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

[7]

Hang Xu, Song Li. Analysis non-sparse recovery for relaxed ALASSO. Communications on Pure & Applied Analysis, 2020, 19 (8) : 4055-4068. doi: 10.3934/cpaa.2020179

[8]

Changming Song, Yun Wang. Nonlocal latent low rank sparse representation for single image super resolution via self-similarity learning. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021017

[9]

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

[10]

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

[11]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, 2021, 15 (1) : 159-183. doi: 10.3934/ipi.2020076

[12]

Asadollah Aghajani. Regularity of extremal solutions of semilinear elliptic problems with non-convex nonlinearities on general domains. Discrete & Continuous Dynamical Systems, 2017, 37 (7) : 3521-3530. doi: 10.3934/dcds.2017150

[13]

. 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

[14]

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

[15]

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

[16]

Kamran Jalilian, Kameleh Nasiri Pirbazari. Convex optimization without convexity of constraints on non-necessarily convex sets and its applications in customer satisfaction in automotive industry. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021020

[17]

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

[18]

Richard Archibald, Hoang Tran. A dictionary learning algorithm for compression and reconstruction of streaming data in preset order. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021102

[19]

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

[20]

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

2020 Impact Factor: 1.639

Metrics

  • PDF downloads (146)
  • HTML views (0)
  • Cited by (16)

Other articles
by authors

[Back to Top]