# American Institue of Mathematical Sciences

2013, 7(3): 813-838. doi: 10.3934/ipi.2013.7.813

## How to explore the patch space

 1 Universitat de les Illes Balears, Crta. de Valldemossa, km 7.5, 07122 Palma de Mallorca 2 Universitat de les Illes Balears, Ctra Valldemossa km 7.5, Palma de Mallorca, 07122 3 CMLA, ENS Cachan, 61 avenue du Président Wilson, 94235 Cachan Cedex

Received  January 2013 Revised  April 2013 Published  September 2013

Patches are small images (typically $8\times 8$ to $12\times 12$) extracted from natural images. The patch space'' is the set of all observable patches extracted from digital images in the world. This observable space is huge and should permit a sophisticated statistical analysis. In the past ten years, statistical inquiries and applications involving the patch space'' have tried to explore its structure on several levels. The first attempts have invalidated models based on PCA or Fourier analysis. Redundant bases (or patch dictionaries) obtained by independent component analysis (ICA) or related processes have tried to find a reduced set of patches on which every other patch obtains a sparse decomposition. Optimization algorithms such as EM have been used to explore the patch space as a Gaussian mixture. The goal of the present paper is to review this literature, and to extend its methodology to gain more insight on the independent components of the patch space.
The conclusion of our analysis is that the sophisticated ICA tools introduced to analyze the patch space require a previous geometric normalization step to yield non trivial results. Indeed, we demonstrate by a simple experimental setup and by the analysis of the literature that, without this normalization, the patch space structure is actually hidden by the rotations, translations, and contrast changes. Thus, ICA models applied on a random set of patches boil down to segmenting the patch space depending on insignificant dimensions such as the patch orientation or the position of its gradient barycenter. When, instead of exploring the raw patches, one decides to explore the quotient of the set of patches by these action groups, a geometrically interpretable patch structure is revealed.
Citation: Jose-Luis Lisani, Antoni Buades, Jean-Michel Morel. How to explore the patch space. Inverse Problems & Imaging, 2013, 7 (3) : 813-838. doi: 10.3934/ipi.2013.7.813
##### References:
 [1] M. Aharon, Michael Elad and A. Bruckstein, K-SVD: Design of dictionaries for sparse representation,, IEEE Transactions on Image Processing, (2005), 9. doi: 10.1109/TSP.2006.881199. [2] Michal Aharon, Michael Elad and Alfred Bruckstein, K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation,, IEEE Transactions on Signal Processing, 54 (2006), 4311. doi: 10.1109/TSP.2006.881199. [3] C. V. Angelino, E. Debreuve and M. Barlaud, et al, Confidence-based denoising relying on a transformation-invariant, robust patch similarity exploring ways to improve patch synchronous summation,, In, (2011). [4] A. J. Bell and T. J. Sejnowski, The independent components of natural scenes are edge filters,, Vision Research, 37 (1997), 3327. doi: 10.1016/S0042-6989(97)00121-1. [5] A. Buades, B. Coll and J. M. Morel, A review of image denoising algorithms, with a new one,, Multiscale Modeling Simulation, 4 (2005), 490. doi: 10.1137/040616024. [6] A. Buades, M. Lebrun and J. M. Morel, Implementation of the "non-local bayes'' image denoising algorithm,, Image Processing On Line (http:www.ipol.im), (2012), 1. [7] J. Canny, A computational approach to edge detection,, IEEE Trans. Pattern Analysis and Machine Intelligence, 8 (1986), 679. doi: 10.1109/TPAMI.1986.4767851. [8] P. Chatterjee and P. Milanfar, Patch-based near-optimal image denoising,, IEEE Transactions on Image Processing: A Publication of the IEEE Signal Processing Society, 21 (2011), 1635. doi: 10.1109/TIP.2011.2172799. [9] S. F. Cotter, R. Adler, R. D. Rao and K. Kreutz-Delgado, Forward sequential algorithms for best basis selection,, In, 146 (1999), 235. doi: 10.1049/ip-vis:19990445. [10] K. Dabov, A. Foi, V. Katkovnik and K. Egiazarian, Image denoising by sparse 3-D transform-domain collaborative filtering,, IEEE Transactions on Image Processing, 16 (2007), 2080. doi: 10.1109/TIP.2007.901238. [11] A. Delorme and Makeig S, Eeglab: An open source toolbox for analysis of single-trial eeg dynamics,, Journal of Neuroscience Methods, 134 (2004), 9. doi: 10.1016/j.jneumeth.2003.10.009. [12] A. Efros and T. Leung, Texture synthesis by non parametric sampling,, In, 2 (1999), 1033. doi: 10.1109/ICCV.1999.790383. [13] 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. [14] A. Foi and G. Boracchi, Foveated self-similarity in nonlocal image filtering,, In, (8291), 829110. doi: 10.1117/12.912217. [15] S. Geman and D. Geman, Stochastic relaxation, gibbs distributions and the bayesian restoration of images,, IEEE Pat. Anal. Mach. Intell., 6 (1984), 721. [16] S. Grewenig, S. Zimmer and J. Weickert, Rotationally invariant similarity measures for nonlocal image denoising,, Journal of Visual Communication and Image Representation, 22 (2011), 117. doi: 10.1016/j.jvcir.2010.11.001. [17] Guillermo Sapiro Guoshen Yu, DCT image denoising: A simple and effective image denoising algorithm,, Image Processing On Line, (2011). [18] David H Hubel, "Eye, Brain, and Vision,", Scientific American Library New York, (1988). [19] A. Hyvarinen, Fast and robust fixed-point algorithms for independent component analysis,, IEEE Transactions on Neural Networks, 10 (1999), 626. doi: 10.1109/72.761722. [20] A. Hyvarinen, The fixed-point algorithm and maximum likelihood estimation for independent component analysis,, Neural Processing Letters, 10 (1999), 1. [21] A. Hyvarinen and E. Oja, Independent component analysis: Algorithms and applications,, Neural Networks, 13 (2000), 411. doi: 10.1016/S0893-6080(00)00026-5. [22] Z. Ji, Q. Chen, Q. S. Sun and D. S. Xia, A moment-based nonlocal-means algorithm for image denoising,, Information Processing Letters, 109 (2009), 1238. doi: 10.1016/j.ipl.2009.09.007. [23] I. T. Jolliffe, N. T. Trendafilov and M. Uddin, A modified principal component technique based on the Lasso,, Journal of Computational and Graphical Statistics, 12 (2003), 531. doi: 10.1198/1061860032148. [24] M. Lebrun, M. Colom, A. Buades and JM Morel, Secrets of image denoising cuisine,, Acta Numerica, 21 (2012), 475. doi: 10.1017/S0962492912000062. [25] A. B. Lee, K. S. Pedersen and D. Mumford, The nonlinear statistics of high-contrast patches in natural images,, International Journal of Computer Vision, 54 (2003), 83. [26] M. S. Lewicki and T. J. Sejnowski, Learning overcomplete representations,, Neural computation, 12 (2000), 337. doi: 10.1162/089976600300015826. [27] Y. Lou, P. Favaro, S. Soatto and A. Bertozzi, Nonlocal similarity image filtering,, Image Analysis and Processing-ICIAP 2009, 5716 (2009), 62. doi: 10.1007/978-3-642-04146-4_9. [28] J. Mairal, F. Bach, J. Ponce and G. Sapiro, Online learning for matrix factorization and sparse coding,, The Journal of Machine Learning Research, 11 (2010), 19. [29] J. Mairal, F. Bach, J. Ponce, G. Sapiro and A. Zisserman, Non-local sparse models for image restoration,, In, (2009), 2272. doi: 10.1109/ICCV.2009.5459452. [30] 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, 2 (2001), 416. doi: 10.1109/ICCV.2001.937655. [31] Y. Meyer, "Wavelets-Algorithms and Applications,", Wavelets-Algorithms and applications Society for Industrial and Applied Mathematics (SIAM), (1993). [32] B. A. Olshausen, D. J. Field, et al, Sparse coding with an overcomplete basis set: A strategy employed by V1,, Vision research, 37 (1997), 3311. doi: 10.1016/S0042-6989(97)00169-7. [33] L. U. Perrinet, Role of homeostasis in learning sparse representations,, Neural computation, 22 (2010), 1812. doi: 10.1162/neco.2010.05-08-795. [34] Javier Portilla, Vasily Strela, Martin J. Wainwright and Eero P. Simoncelli, Image denoising using scale mixtures of gaussians in the wavelet domain,, IEEE Trans. Image Process, 12 (2003), 1338. doi: 10.1109/TIP.2003.818640. [35] W. H. Richardson, Bayesian-based iterative method of image restoration,, JOSA, 62 (1972), 55. doi: 10.1364/JOSA.62.000055. [36] WF Sun, YH Peng and WL Hwang, Modified similarity metric for non-local means algorithm,, Electronics Letters, 45 (2009), 1307. doi: 10.1049/el.2009.2406. [37] L. Yaroslavsky and M. Eden, "Fundamentals of Digital Optics,", Birkhäuser, (2003). doi: 10.1007/978-1-4612-0845-7. [38] G. Yu, G. Sapiro and S. Mallat, Image modeling and enhancement via structured sparse model selection,, In, (2010), 1641. doi: 10.1109/ICIP.2010.5653853. [39] G. Yu, G. Sapiro and S. Mallat, Solving inverse problems with piecewise linear estimators: From gaussian mixture models to structured sparsity,, IEEE Trans. Image Process, 21 (2012), 2481. doi: 10.1109/TIP.2011.2176743. [40] S. Zimmer, S. Didas and J. Weickert, A rotationally invariant block matching strategy improving image denoising with non-local means,, In, (2008). [41] T. Zito, N. Wilbert, L. Wiskott and P. Berkes, Modular toolkit for data processing (MDP): A python data processing frame work,, Front. Neuroinform., 2 (2008). [42] D. Zoran and Y. Weiss, From learning models of natural image patches to whole image restoration,, In, (2011), 479. doi: 10.1109/ICCV.2011.6126278. [43] H. Zou, T. Hastie and R. Tibshirani, Sparse principal component analysis,, Journal of Computational and Graphical Statistics, 15 (2006), 265. doi: 10.1198/106186006X113430.

show all references

##### References:
 [1] M. Aharon, Michael Elad and A. Bruckstein, K-SVD: Design of dictionaries for sparse representation,, IEEE Transactions on Image Processing, (2005), 9. doi: 10.1109/TSP.2006.881199. [2] Michal Aharon, Michael Elad and Alfred Bruckstein, K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation,, IEEE Transactions on Signal Processing, 54 (2006), 4311. doi: 10.1109/TSP.2006.881199. [3] C. V. Angelino, E. Debreuve and M. Barlaud, et al, Confidence-based denoising relying on a transformation-invariant, robust patch similarity exploring ways to improve patch synchronous summation,, In, (2011). [4] A. J. Bell and T. J. Sejnowski, The independent components of natural scenes are edge filters,, Vision Research, 37 (1997), 3327. doi: 10.1016/S0042-6989(97)00121-1. [5] A. Buades, B. Coll and J. M. Morel, A review of image denoising algorithms, with a new one,, Multiscale Modeling Simulation, 4 (2005), 490. doi: 10.1137/040616024. [6] A. Buades, M. Lebrun and J. M. Morel, Implementation of the "non-local bayes'' image denoising algorithm,, Image Processing On Line (http:www.ipol.im), (2012), 1. [7] J. Canny, A computational approach to edge detection,, IEEE Trans. Pattern Analysis and Machine Intelligence, 8 (1986), 679. doi: 10.1109/TPAMI.1986.4767851. [8] P. Chatterjee and P. Milanfar, Patch-based near-optimal image denoising,, IEEE Transactions on Image Processing: A Publication of the IEEE Signal Processing Society, 21 (2011), 1635. doi: 10.1109/TIP.2011.2172799. [9] S. F. Cotter, R. Adler, R. D. Rao and K. Kreutz-Delgado, Forward sequential algorithms for best basis selection,, In, 146 (1999), 235. doi: 10.1049/ip-vis:19990445. [10] K. Dabov, A. Foi, V. Katkovnik and K. Egiazarian, Image denoising by sparse 3-D transform-domain collaborative filtering,, IEEE Transactions on Image Processing, 16 (2007), 2080. doi: 10.1109/TIP.2007.901238. [11] A. Delorme and Makeig S, Eeglab: An open source toolbox for analysis of single-trial eeg dynamics,, Journal of Neuroscience Methods, 134 (2004), 9. doi: 10.1016/j.jneumeth.2003.10.009. [12] A. Efros and T. Leung, Texture synthesis by non parametric sampling,, In, 2 (1999), 1033. doi: 10.1109/ICCV.1999.790383. [13] 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. [14] A. Foi and G. Boracchi, Foveated self-similarity in nonlocal image filtering,, In, (8291), 829110. doi: 10.1117/12.912217. [15] S. Geman and D. Geman, Stochastic relaxation, gibbs distributions and the bayesian restoration of images,, IEEE Pat. Anal. Mach. Intell., 6 (1984), 721. [16] S. Grewenig, S. Zimmer and J. Weickert, Rotationally invariant similarity measures for nonlocal image denoising,, Journal of Visual Communication and Image Representation, 22 (2011), 117. doi: 10.1016/j.jvcir.2010.11.001. [17] Guillermo Sapiro Guoshen Yu, DCT image denoising: A simple and effective image denoising algorithm,, Image Processing On Line, (2011). [18] David H Hubel, "Eye, Brain, and Vision,", Scientific American Library New York, (1988). [19] A. Hyvarinen, Fast and robust fixed-point algorithms for independent component analysis,, IEEE Transactions on Neural Networks, 10 (1999), 626. doi: 10.1109/72.761722. [20] A. Hyvarinen, The fixed-point algorithm and maximum likelihood estimation for independent component analysis,, Neural Processing Letters, 10 (1999), 1. [21] A. Hyvarinen and E. Oja, Independent component analysis: Algorithms and applications,, Neural Networks, 13 (2000), 411. doi: 10.1016/S0893-6080(00)00026-5. [22] Z. Ji, Q. Chen, Q. S. Sun and D. S. Xia, A moment-based nonlocal-means algorithm for image denoising,, Information Processing Letters, 109 (2009), 1238. doi: 10.1016/j.ipl.2009.09.007. [23] I. T. Jolliffe, N. T. Trendafilov and M. Uddin, A modified principal component technique based on the Lasso,, Journal of Computational and Graphical Statistics, 12 (2003), 531. doi: 10.1198/1061860032148. [24] M. Lebrun, M. Colom, A. Buades and JM Morel, Secrets of image denoising cuisine,, Acta Numerica, 21 (2012), 475. doi: 10.1017/S0962492912000062. [25] A. B. Lee, K. S. Pedersen and D. Mumford, The nonlinear statistics of high-contrast patches in natural images,, International Journal of Computer Vision, 54 (2003), 83. [26] M. S. Lewicki and T. J. Sejnowski, Learning overcomplete representations,, Neural computation, 12 (2000), 337. doi: 10.1162/089976600300015826. [27] Y. Lou, P. Favaro, S. Soatto and A. Bertozzi, Nonlocal similarity image filtering,, Image Analysis and Processing-ICIAP 2009, 5716 (2009), 62. doi: 10.1007/978-3-642-04146-4_9. [28] J. Mairal, F. Bach, J. Ponce and G. Sapiro, Online learning for matrix factorization and sparse coding,, The Journal of Machine Learning Research, 11 (2010), 19. [29] J. Mairal, F. Bach, J. Ponce, G. Sapiro and A. Zisserman, Non-local sparse models for image restoration,, In, (2009), 2272. doi: 10.1109/ICCV.2009.5459452. [30] 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, 2 (2001), 416. doi: 10.1109/ICCV.2001.937655. [31] Y. Meyer, "Wavelets-Algorithms and Applications,", Wavelets-Algorithms and applications Society for Industrial and Applied Mathematics (SIAM), (1993). [32] B. A. Olshausen, D. J. Field, et al, Sparse coding with an overcomplete basis set: A strategy employed by V1,, Vision research, 37 (1997), 3311. doi: 10.1016/S0042-6989(97)00169-7. [33] L. U. Perrinet, Role of homeostasis in learning sparse representations,, Neural computation, 22 (2010), 1812. doi: 10.1162/neco.2010.05-08-795. [34] Javier Portilla, Vasily Strela, Martin J. Wainwright and Eero P. Simoncelli, Image denoising using scale mixtures of gaussians in the wavelet domain,, IEEE Trans. Image Process, 12 (2003), 1338. doi: 10.1109/TIP.2003.818640. [35] W. H. Richardson, Bayesian-based iterative method of image restoration,, JOSA, 62 (1972), 55. doi: 10.1364/JOSA.62.000055. [36] WF Sun, YH Peng and WL Hwang, Modified similarity metric for non-local means algorithm,, Electronics Letters, 45 (2009), 1307. doi: 10.1049/el.2009.2406. [37] L. Yaroslavsky and M. Eden, "Fundamentals of Digital Optics,", Birkhäuser, (2003). doi: 10.1007/978-1-4612-0845-7. [38] G. Yu, G. Sapiro and S. Mallat, Image modeling and enhancement via structured sparse model selection,, In, (2010), 1641. doi: 10.1109/ICIP.2010.5653853. [39] G. Yu, G. Sapiro and S. Mallat, Solving inverse problems with piecewise linear estimators: From gaussian mixture models to structured sparsity,, IEEE Trans. Image Process, 21 (2012), 2481. doi: 10.1109/TIP.2011.2176743. [40] S. Zimmer, S. Didas and J. Weickert, A rotationally invariant block matching strategy improving image denoising with non-local means,, In, (2008). [41] T. Zito, N. Wilbert, L. Wiskott and P. Berkes, Modular toolkit for data processing (MDP): A python data processing frame work,, Front. Neuroinform., 2 (2008). [42] D. Zoran and Y. Weiss, From learning models of natural image patches to whole image restoration,, In, (2011), 479. doi: 10.1109/ICCV.2011.6126278. [43] H. Zou, T. Hastie and R. Tibshirani, Sparse principal component analysis,, Journal of Computational and Graphical Statistics, 15 (2006), 265. doi: 10.1198/106186006X113430.
 [1] Hui Zhang, Jian-Feng Cai, Lizhi Cheng, Jubo Zhu. Strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems & Imaging, 2012, 6 (2) : 357-372. doi: 10.3934/ipi.2012.6.357 [2] Eitan Tadmor, Prashant Athavale. Multiscale image representation using novel integro-differential equations. Inverse Problems & Imaging, 2009, 3 (4) : 693-710. doi: 10.3934/ipi.2009.3.693 [3] Marko Filipović, Ivica Kopriva. A comparison of dictionary based approaches to inpainting and denoising with an emphasis to independent component analysis learned dictionaries. Inverse Problems & Imaging, 2011, 5 (4) : 815-841. doi: 10.3934/ipi.2011.5.815 [4] Qingshan You, Qun Wan, Yipeng Liu. A short note on strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems & Imaging, 2013, 7 (1) : 305-306. doi: 10.3934/ipi.2013.7.305 [5] 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 [6] Jianjun Zhang, Yunyi Hu, James G. Nagy. A scaled gradient method for digital tomographic image reconstruction. Inverse Problems & Imaging, 2018, 12 (1) : 239-259. doi: 10.3934/ipi.2018010 [7] G. Mastroeni, L. Pellegrini. On the image space analysis for vector variational inequalities. Journal of Industrial & Management Optimization, 2005, 1 (1) : 123-132. doi: 10.3934/jimo.2005.1.123 [8] Shouhong Yang. Semidefinite programming via image space analysis. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1187-1197. doi: 10.3934/jimo.2016.12.1187 [9] Dominique Duncan, Thomas Strohmer. Classification of Alzheimer's disease using unsupervised diffusion component analysis. Mathematical Biosciences & Engineering, 2016, 13 (6) : 1119-1130. doi: 10.3934/mbe.2016033 [10] 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 [11] Bilal Saad, Mazen Saad. Numerical analysis of a non equilibrium two-component two-compressible flow in porous media. Discrete & Continuous Dynamical Systems - S, 2014, 7 (2) : 317-346. doi: 10.3934/dcdss.2014.7.317 [12] Dominique Duncan, Paul Vespa, Arthur W. Toga. Detecting features of epileptogenesis in EEG after TBI using unsupervised diffusion component analysis. Discrete & Continuous Dynamical Systems - B, 2018, 23 (1) : 161-172. doi: 10.3934/dcdsb.2018010 [13] Shuhua Xu, Fei Gao. Weighted two-phase supervised sparse representation based on Gaussian for face recognition. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1385-1400. doi: 10.3934/dcdss.2015.8.1385 [14] Dieter Bothe, Jan Prüss. Modeling and analysis of reactive multi-component two-phase flows with mass transfer and phase transition -- The isothermal incompressible case. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 673-696. doi: 10.3934/dcdss.2017034 [15] Augusto Visintin. On the variational representation of monotone operators. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 909-918. doi: 10.3934/dcdss.2017046 [16] Pengwen Chen, Changfeng Gui. Alpha divergences based mass transport models for image matching problems. Inverse Problems & Imaging, 2011, 5 (3) : 551-590. doi: 10.3934/ipi.2011.5.551 [17] Bartomeu Coll, Joan Duran, Catalina Sbert. Half-linear regularization for nonconvex image restoration models. Inverse Problems & Imaging, 2015, 9 (2) : 337-370. doi: 10.3934/ipi.2015.9.337 [18] Atsushi Katsuda, Yaroslav Kurylev, Matti Lassas. Stability of boundary distance representation and reconstruction of Riemannian manifolds. Inverse Problems & Imaging, 2007, 1 (1) : 135-157. doi: 10.3934/ipi.2007.1.135 [19] Wael Bahsoun, Christopher Bose, Anthony Quas. Deterministic representation for position dependent random maps. Discrete & Continuous Dynamical Systems - A, 2008, 22 (3) : 529-540. doi: 10.3934/dcds.2008.22.529 [20] L. Bakker. A reducible representation of the generalized symmetry group of a quasiperiodic flow. Conference Publications, 2003, 2003 (Special) : 68-77. doi: 10.3934/proc.2003.2003.68

2016 Impact Factor: 1.094