A tale of two bases: local-nonlocal regularization on image patches with convolution framelets. (English) Zbl 1375.94029

Yin, Rujie; Gao, Tingran; Lu, Yue M.; Daubechies, Ingrid

SIAM J. Imaging Sci. 10, No. 2, 711-750 (2017).

Summary: We propose an image representation scheme combining the local and nonlocal characterization of patches in an image. Our representation scheme can be shown to be equivalent to a tight frame constructed from convolving local bases (e.g., wavelet frames, discrete cosine transforms, etc.) with nonlocal bases (e.g., spectral basis induced by nonlinear dimension reduction on patches), and we call the resulting frame elements convolution framelets. Insight gained from analyzing the proposed representation leads to a novel interpretation of a recent high-performance patch-based image processing algorithm using the point integral method (PIM) and the low dimensional manifold model (LDMM) [S. Osher, Z. Shi and W. Zhu, “Low dimensional manifold model for image processing”, Tech. Rep., CAM report 16-04, UCLA, Los Angeles, CA (2016)]. In particular, we show that LDMM is a weighted \(\ell_2\)-regularization on the coefficients obtained by decomposing images into linear combinations of convolution framelets; based on this understanding, we extend the original LDMM to a reweighted version that yields further improved results. In addition, we establish the energy concentration property of convolution framelet coefficients for the setting where the local basis is constructed from a given nonlocal basis via a linear reconstruction framework; a generalization of this framework to unions of local embeddings can provide a natural setting for interpreting BM3D, one of the state-of-the-art image denoising algorithms.

MSC:

94A08	Image processing (compression, reconstruction, etc.) in information and communication theory
68Q25	Analysis of algorithms and problem complexity
68U10	Computing methodologies for image processing

Keywords:

image patches; convolution framelets; regularization; nonlocal methods; inpainting

Software:

darch; IPOL; t-SNE

References:

[1]	Y. Aflalo, H. Brezis, and R. Kimmel, {\it On the optimality of shape and data representation in the spectral domain}, SIAM J. Imaging Sci., 8 (2015), pp. 1141-1160, . · Zbl 1360.94038
[2]	M. Aharon, M. Elad, and A. M. Bruckstein, {\it On the uniqueness of overcomplete dictionaries, and a practical way to retrieve them}, Linear Algebra Appl., 416 (2006), pp. 48-67. · Zbl 1096.68042
[3]	N. Ahmed, T. Natarajan, and K. R. Rao, {\it Discrete cosine transform}, IEEE Trans. Comput., C-23 (1974), pp. 90-93, . · Zbl 0273.65097
[4]	M. F. Barnsley and A. D. Sloan, {\it Methods and Apparatus for Image Compression by Iterated Function System}, US Patent 4,941,193, July 10, 1990.
[5]	M. Belkin and P. Niyogi, {\it Laplacian eigenmaps for dimensionality reduction and data representation}, Neural Comput., 15 (2003), pp. 1373-1396. · Zbl 1085.68119
[6]	M. Belkin and P. Niyogi, {\it Convergence of Laplacian eigenmaps}, Adv. Neural Inform. Process. Syst., 19 (2007), p. 129. · Zbl 1085.68119
[7]	A. Buades, B. Coll, and J.-M. Morel, {\it A non-local algorithm for image denoising}, in IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), Vol. 2, IEEE, Washington, DC, 2005, pp. 60-65. · Zbl 1108.94004
[8]	A. Buades, B. Coll, and J. M. Morel, {\it A review of image denoising algorithms, with a new one}, Multiscale Model. Simul., 4 (2005), pp. 490-530, . · Zbl 1108.94004
[9]	G. Carlsson, T. Ishkhanov, V. De Silva, and A. Zomorodian, {\it On the local behavior of spaces of natural images}, Int. J. Comput. Vision, 76 (2008), pp. 1-12. · Zbl 1477.68463
[10]	P. Chatterjee and P. Milanfar, {\it Clustering-based denoising with locally learned dictionaries}, IEEE Trans. Image Process., 18 (2009), pp. 1438-1451. · Zbl 1371.94081
[11]	P. Chatterjee and P. Milanfar, {\it Patch-based near-optimal image denoising}, IEEE Trans. Image Process., 21 (2012), pp. 1635-1649. · Zbl 1373.94069
[12]	A. Cohen and J.-P. D’Ales, {\it Nonlinear approximation of random functions}, SIAM J. Appl. Math., 57 (1997), pp. 518-540, . · Zbl 0876.42029
[13]	R. R. Coifman and S. Lafon, {\it Diffusion maps}, Appl. Comput. Harmon. Anal., 21 (2006), pp. 5-30. · Zbl 1095.68094
[14]	R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner, and S. W. Zucker, {\it Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps}, Proc. Natl. Acad. Sci. USA, 102 (2005), pp. 7426-7431, . · Zbl 1405.42043
[15]	R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner, and S. W. Zucker, {\it Geometric diffusions as a tool for harmonic analysis and structure definition of data: Multiscale methods}, Proc. Natl. Acad. Sci. USA, 102 (2005), pp. 7432-7437, . · Zbl 1405.42044
[16]	K. Dabov, A. Foi, V. Katkovnik, and K. Egiazarian, {\it Image denoising by sparse \textup3-D transform-domain collaborative filtering}, IEEE Trans. Image Process., 16 (2007), pp. 2080-2095.
[17]	K. Dabov, A. Foi, V. Katkovnik, and K. Egiazarian, {\it BM3D image denoising with shape-adaptive principal component analysis}, in SPARS’09, Signal Processing with Adaptive Sparse Structured Representations, Saint Malo, France, 2009.
[18]	I. Daubechies, {\it Ten Lectures on Wavelets}, CBMS-NSF Regional Conf. Ser. in Appl. Math. 61, SIAM, Philadelphia, 1992. · Zbl 0776.42018
[19]	D. L. Donoho, I. M. Johnstone, G. Kerkyacharian, and D. Picard, {\it Wavelet shrinkage: Asymptopia?}, J. Roy. Statist. Soc. Ser. B, 57 (1995), pp. 301-369. · Zbl 0827.62035
[20]	D. L. Donoho and J. M. Johnstone, {\it Ideal spatial adaptation by wavelet shrinkage}, Biometrika, 81 (1994), pp. 425-455, . · Zbl 0815.62019
[21]	M. Elad and M. Aharon, {\it Image denoising via sparse and redundant representations over learned dictionaries}, IEEE Trans. Image Process., 15 (2006), pp. 3736-3745.
[22]	K. Engan, S. O. Aase, and J. Hakon Husoy, {\it Method of optimal directions for frame design}, in Proceedings of the 1999 IEEE International Conference on Acoustics, Speech, and Signal Processing, Vol. 5, IEEE, Washington, DC, 1999, pp. 2443-2446.
[23]	G. Gilboa and S. Osher, {\it Nonlocal linear image regularization and supervised segmentation}, Multiscale Model. Simul., 6 (2007), pp. 595-630, . · Zbl 1140.68517
[24]	G. Gilboa and S. Osher, {\it Nonlocal operators with applications to image processing}, Multiscale Model. Simul., 7 (2008), pp. 1005-1028, . · Zbl 1181.35006
[25]	N. Halko, P. G. Martinsson, and J. A. Tropp, {\it Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions}, SIAM Rev., 53 (2011), pp. 217-288, . · Zbl 1269.65043
[26]	G. E. Hinton and R. R. Salakhutdinov, {\it Reducing the dimensionality of data with neural networks}, Science, 313 (2006), pp. 504-507, . · Zbl 1226.68083
[27]	R. Izbicki and A. B. Lee, {\it Nonparametric conditional density estimation in a high-dimensional regression setting}, J. Comput. Graph. Statist., 25 (2016), pp. 1297-1316, .
[28]	A. E. Jacquin, {\it Image coding based on a fractal theory of iterated contractive image transformations}, IEEE Trans. Image Process., 1 (1992), pp. 18-30, .
[29]	K. H. Jin and J. C. Ye, {\it Annihilating filter-based low-rank Hankel matrix approach for image inpainting}, IEEE Trans. Image Process., 24 (2015), pp. 3498-3511. · Zbl 1408.94291
[30]	A. Kheradmand and P. Milanfar, {\it A general framework for regularized, similarity-based image restoration}, IEEE Trans. Image Process., 23 (2014), pp. 5136-5151. · Zbl 1374.94174
[31]	K. Kreutz-Delgado, J. F. Murray, B. D. Rao, K. Engan, T. S. Lee, and T. J. Sejnowski, {\it Dictionary learning algorithms for sparse representation}, Neural Comput., 15 (2003), pp. 349-396. · Zbl 1047.68101
[32]	K. Kreutz-Delgado and B. D. Rao, {\it FOCUSS-based dictionary learning algorithms}, in International Symposium on Optical Science and Technology, International Society for Optics and Photonics, Bellingham, WA, 2000, pp. 459-473.
[33]	S. S. Lafon, {\it Diffusion Maps and Geometric Harmonics}, Ph.D. thesis, Yale University, New Haven, CT, 2004.
[34]	A. B. Lee and R. Izbicki, {\it A spectral series approach to high-dimensional nonparametric regression}, Electron. J. Stat., 10 (2016), pp. 423-463. · Zbl 1332.62133
[35]	A. B. Lee, K. S. Pedersen, and D. Mumford, {\it The nonlinear statistics of high-contrast patches in natural images}, Internat. J. Comput. Vision, 54 (2003), pp. 83-103. · Zbl 1070.68661
[36]	J. A. Lee and M. Verleysen, {\it Nonlinear Dimensionality Reduction}, Springer, New York, 2007. · Zbl 1128.68024
[37]	S. Lesage, R. Gribonval, F. Bimbot, and L. Benaroya, {\it Learning unions of orthonormal bases with thresholded singular value decomposition}, in Proceedings of the 2005 IEEE International Conference on Acoustics, Speech, and Signal Processing, IEEE, Washington, DC, 2005, pp. v-293.
[38]	Z. Li, Z. Shi, and J. Sun, {\it Point Integral Method for Solving Poisson-Type Equations on Manifolds from Point Clouds with Convergence Guarantees}, preprint, , 2014.
[39]	A. V. Little, M. Maggioni, and L. Rosasco, {\it Multiscale geometric methods for data sets I: Multiscale SVD, noise and curvature}, Appl. Comput. Harmon. Anal., to appear, . · Zbl 06770640
[40]	L. v. d. Maaten and G. Hinton, {\it Visualizing data using t-SNE}, J. Mach. Learn. Res., 9 (2008), pp. 2579-2605. · Zbl 1225.68219
[41]	J. Mairal, F. Bach, J. Ponce, G. Sapiro, and A. Zisserman, {\it Non-local sparse models for image restoration}, in Proceedings of the 12th IEEE International Conference on Computer Vision, IEEE, Washington, DC, 2009, pp. 2272-2279.
[42]	S. Mallat, {\it A Wavelet Tour of Signal Processing: The Sparse Way}, Academic Press, New York, 2008. · Zbl 1170.94003
[43]	A. Newson, A. Almansa, Y. Gousseau, and P. Pérez, {\it Non-local patch-based image inpainting}, Image Processing On Line (IPOL), preprint, 2015. · Zbl 1320.68204
[44]	B. A. Olshausen and D. J. Field, {\it Sparse coding with an overcomplete basis set: A strategy employed by V1?}, Vision Res., 37 (1997), pp. 3311-3325.
[45]	S. Osher, Z. Shi, and W. Zhu, {\it Low Dimensional Manifold Model for Image Processing}, Tech. Rep., CAM report 16-04, UCLA, Los Angeles, CA, 2016. · Zbl 1401.49042
[46]	K. Pearson, {\it On lines and planes of closest fit to systems of point in space}, Philos. Mag., 2 (1901), pp. 559-572. · JFM 32.0246.07
[47]	J. A. Perea and G. Carlsson, {\it A Klein-bottle-based dictionary for texture representation}, Internat. J. Comput. Vision, 107 (2014), pp. 75-97. · Zbl 1328.68279
[48]	G. Peyré, {\it Image processing with nonlocal spectral bases}, Multiscale Model. Simul., 7 (2008), pp. 703-730, . · Zbl 1177.41016
[49]	G. Peyré, {\it A review of adaptive image representations}, IEEE J. Sel. Topics Signal Process., 5 (2011), pp. 896-911.
[50]	X. Qi, {\it Vector Nonlocal Mean Filter}, Ph.D. thesis, University of Toronto, Toronto, Canada, 2015.
[51]	L. Rosasco, {\it Data Representation: From Signal Processing to Machine Learning}, Mini-Tutorial, SIAM Conference on Image Science, Albuquerque, NM, 2016, .
[52]	S. T. Roweis and L. K. Saul, {\it Nonlinear dimensionality reduction by locally linear embedding}, Science, 290 (2000), pp. 2323-2326, .
[53]	L. I. Rudin, S. Osher, and E. Fatemi, {\it Nonlinear total variation based noise removal algorithms}, Phys. D, 60 (1992), pp. 259-268. · Zbl 0780.49028
[54]	B. Schölkopf and A. J. Smola, {\it Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond}, MIT Press, Cambridge, MA, 2002.
[55]	R. N. Shepard, {\it The analysis of proximities: Multidimensional scaling with an unknown distance function. I}, Psychometrika, 27 (1962), pp. 125-140. · Zbl 0129.12103
[56]	Z. Shi, S. Osher, and W. Zhu, {\it Low Dimensional Manifold Model with Semi-local Patches}, Technical Report, CAM report 16-63, UCLA, Los Angeles, CA, 2016.
[57]	Z. Shi and J. Sun, {\it Convergence of the Point Integral Method for the Poisson Equation with Dirichlet Boundary on Point Cloud}, preprint, , 2013.
[58]	Z. Shi and J. Sun, {\it Convergence of the Point Integral Method for Poisson Equation on Point Cloud}, preprint, , 2014.
[59]	A. Singer, Y. Shkolnisky, and B. Nadler, {\it Diffusion interpretation of nonlocal neighborhood filters for signal denoising}, SIAM J. Imaging Sci., 2 (2009), pp. 118-139, . · Zbl 1175.62102
[60]	A. Singer and H.-t. Wu, {\it Spectral Convergence of the Connection Laplacian from Random Samples}, preprint, , 2013.
[61]	A. Skodras, C. Christopoulos, and T. Ebrahimi, {\it The JPEG 2000 still image compression standard}, IEEE Signal Process. Mag., 18 (2001), pp. 36-58. · Zbl 0990.68071
[62]	S. Smale, T. Poggio, A. Caponnetto, and J. Bouvrie, {\it Derived distance: Towards a mathematical theory of visual cortex}, Artificial Intelligence (2007). · Zbl 1185.68813
[63]	A. D. Szlam, M. Maggioni, and R. R. Coifman, {\it Regularization on graphs with function-adapted diffusion processes}, J. Mach. Learn. Res., 9 (2008), pp. 1711-1739. · Zbl 1225.68217
[64]	H. Talebi and P. Milanfar, {\it Global image denoising}, IEEE Trans. Image Process., 23 (2014), pp. 755-768. · Zbl 1374.94365
[65]	J. B. Tenenbaum, V. d. Silva, and J. C. Langford, {\it A global geometric framework for nonlinear dimensionality reduction}, Science, 290 (2000), pp. 2319-2323, .
[66]	W. S. Torgerson, {\it Multidimensional scaling: I. Theory and method}, Psychometrika, 17 (1952), pp. 401-419. · Zbl 0049.37603
[67]	G. K. Wallace, {\it The JPEG still picture compression standard}, IEEE Trans. Consumer Electron., 38 (1992), pp. xviii-xxxiv.