How to explore the patch  space

Jose-Luis Lisani; Antoni Buades; Jean-Michel Morel

doi:10.3934/ipi.2013.7.813

Article Contents

2013, Volume 7, Issue 3: 813-838. Doi: 10.3934/ipi.2013.7.813

This issue Previous Article Recent results on lower bounds of eigenvalue problems by nonconforming finite element methods Next Article Video stabilization of atmospheric turbulence distortion

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: December 31, 2012

Revised: March 31, 2013

Published: July 2013

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: 68.

Citation:

Related Papers

Cited by

References

[1]	M. Aharon, Michael Elad and A. Bruckstein, K-SVD: Design of dictionaries for sparse representation, IEEE Transactions on Image Processing, (2005), pages 9-12.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-4322.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 "International Conference on Imaging Theory and Applications," 2011.
[4]	A. J. Bell and T. J. Sejnowski, The independent components of natural scenes are edge filters, Vision Research, 37 (1997), 3327-3338.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-530.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-42.http://dx.doi.org/10.5201/ipol.2013.16
[7]	J. Canny, A computational approach to edge detection, IEEE Trans. Pattern Analysis and Machine Intelligence, 8 (1986), 679-698.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-1649.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 "Vision, Image and Signal Processing, IEE Proceedings," 146 (1999), 235-244.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-2095.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-21.doi: 10.1016/j.jneumeth.2003.10.009.
[12]	A. Efros and T. Leung, Texture synthesis by non parametric sampling, In "Proc. Int. Conf. Computer Vision," 2 (1999), 1033-1038.doi: 10.1109/ICCV.1999.790383.
[13]	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.
[14]	A. Foi and G. Boracchi, Foveated self-similarity in nonlocal image filtering, In "IS&T/SPIE Electronic Imaging," pages 829110-829110. International Society for Optics and Photonics, 2012.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-741.
[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-130.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. http://dx.doi.org/10.5201/ipol.2011.ys-dct.
[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-634.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-5.
[21]	A. Hyvarinen and E. Oja, Independent component analysis: Algorithms and applications, Neural Networks, 13 (2000), 411-430.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-1244.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-547.doi: 10.1198/1061860032148.
[24]	M. Lebrun, M. Colom, A. Buades and JM Morel, Secrets of image denoising cuisine, Acta Numerica, 21 (2012), 475-576.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-103.
[26]	M. S. Lewicki and T. J. Sejnowski, Learning overcomplete representations, Neural computation, 12 (2000), 337-365.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-71.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-60.
[29]	J. Mairal, F. Bach, J. Ponce, G. Sapiro and A. Zisserman, Non-local sparse models for image restoration, In "Computer Vision, 2009 IEEE 12th International Conference on," pages 2272-2279. IEEE, (2009).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 "Proc. 8th Int'l Conf. Computer Vision," 2 (2001), 416-423.doi: 10.1109/ICCV.2001.937655.
[31]	Y. Meyer, "Wavelets-Algorithms and Applications," Wavelets-Algorithms and applications Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 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-3326.doi: 10.1016/S0042-6989(97)00169-7.
[33]	L. U. Perrinet, Role of homeostasis in learning sparse representations, Neural computation, 22 (2010), 1812-1836.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-1351.doi: 10.1109/TIP.2003.818640.
[35]	W. H. Richardson, Bayesian-based iterative method of image restoration, JOSA, 62 (1972), 55-59.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-1309.doi: 10.1049/el.2009.2406.
[37]	L. Yaroslavsky and M. Eden, "Fundamentals of Digital Optics," Birkhäuser, Boston, 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 "Image Processing (ICIP), 2010 17th IEEE International Conference on," pages 1641-1644. IEEE, (2010).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-2499.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 "Proc. 2008 International Workshop on Local and Non-Local Approximation in Image Processing," (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), http://dx.doi.org/10.3389/neuro.11.008.2008.
[42]	D. Zoran and Y. Weiss, From learning models of natural image patches to whole image restoration, In "Computer Vision (ICCV), 2011 IEEE International Conference on," pages 479-486. IEEE, (2011).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-286.doi: 10.1198/106186006X113430.