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 and 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.

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

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.

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

[1]

Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial and 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 and 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 and Applied Analysis, 2018, 17 (3) : 959-985. doi: 10.3934/cpaa.2018047

[4]

Mourad Nachaoui, Lekbir Afraites, Aissam Hadri, Amine Laghrib. A non-convex non-smooth bi-level parameter learning for impulse and Gaussian noise mixture removing. Communications on Pure and Applied Analysis, 2022, 21 (4) : 1249-1291. doi: 10.3934/cpaa.2022018

[5]

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 and Applied Analysis, 2006, 5 (1) : 181-200. doi: 10.3934/cpaa.2006.5.181

[6]

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

[7]

Qilin Wang, Liu He, Shengjie Li. Higher-order weak radial epiderivatives and non-convex set-valued optimization problems. Journal of Industrial and Management Optimization, 2019, 15 (2) : 465-480. doi: 10.3934/jimo.2018051

[8]

Meixia Li, Changyu Wang, Biao Qu. Non-convex semi-infinite min-max optimization with noncompact sets. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1859-1881. doi: 10.3934/jimo.2017022

[9]

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

[10]

Yoon Mo Jung, Taeuk Jeong, Sangwoon Yun. Non-convex TV denoising corrupted by impulse noise. Inverse Problems and Imaging, 2017, 11 (4) : 689-702. doi: 10.3934/ipi.2017032

[11]

Pavel Krejčí, Giselle Antunes Monteiro, Vincenzo Recupero. Non-convex sweeping processes in the space of regulated functions. Communications on Pure and Applied Analysis, , () : -. doi: 10.3934/cpaa.2022087

[12]

Tong Li, Hui Yin. Convergence rate to strong boundary layer solutions for generalized BBM-Burgers equations with non-convex flux. Communications on Pure and Applied Analysis, 2014, 13 (2) : 835-858. doi: 10.3934/cpaa.2014.13.835

[13]

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 and Imaging, 2021, 15 (1) : 159-183. doi: 10.3934/ipi.2020076

[14]

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

[15]

. Adimurthi, Siddhartha Mishra, G.D. Veerappa Gowda. Existence and stability of entropy solutions for a conservation law with discontinuous non-convex fluxes. Networks and Heterogeneous Media, 2007, 2 (1) : 127-157. doi: 10.3934/nhm.2007.2.127

[16]

Alfonso Castro, Rosa Pardo. A priori estimates for positive solutions to subcritical elliptic problems in a class of non-convex regions. Discrete and Continuous Dynamical Systems - B, 2017, 22 (3) : 783-790. doi: 10.3934/dcdsb.2017038

[17]

Jingang Xiong, Jiguang Bao. The obstacle problem for Monge-Ampère type equations in non-convex domains. Communications on Pure and Applied Analysis, 2011, 10 (1) : 59-68. doi: 10.3934/cpaa.2011.10.59

[18]

Lekbir Afraites, Aissam Hadri, Amine Laghrib, Mourad Nachaoui. A non-convex denoising model for impulse and Gaussian noise mixture removing using bi-level parameter identification. Inverse Problems and Imaging, , () : -. doi: 10.3934/ipi.2022001

[19]

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 and Optimization, 2021  doi: 10.3934/naco.2021020

[20]

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 and Imaging, 2020, 14 (2) : 339-361. doi: 10.3934/ipi.2020015

2020 Impact Factor: 1.639

Metrics

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

Other articles
by authors

[Back to Top]