A comparison of dictionary based approaches to inpainting and denoising with an emphasis to independent component analysis learned dictionaries

Marko Filipović; Ivica Kopriva

doi:10.3934/ipi.2011.5.815

Article Contents

2011, Volume 5, Issue 4: 815-841. Doi: 10.3934/ipi.2011.5.815

This issue Previous Article Uniqueness in inverse transmission scattering problems for multilayered obstacles Next Article Spectral shift functions in the fixed energy inverse scattering

A comparison of dictionary based approaches to inpainting and denoising with an emphasis to independent component analysis learned dictionaries

Marko Filipović^1, and
Ivica Kopriva^1,

1.
Division of Laser and Atomic Research and Development, Rudjer Bošković Institute, Bijenička cesta 54, P.O. Box 180, 10002, Zagreb

Received: February 2010

Revised: July 2011

Published: November 2011

Abstract / Introduction Related Papers Cited by

Abstract

The first contribution of this paper is the comparison of learned dictionary based approaches to inpainting and denoising of images in natural scenes, where emphasis is given on the use of complete and overcomplete dictionary learned by independent component analysis. The second contribution of the paper relates to the formulation of a problem of denoising an image corrupted by a salt and pepper type of noise (this problem is equivalent to estimating saturated pixel values), as a noiseless inpainting problem, whereupon noise corrupted pixels are treated as missing pixels. A maximum a posteriori (MAP) approach to image denoising is not applicable in such a case due to the fact that variance of the impulsive noise is infinite and the MAP based estimation relies on solving an optimization problem with an inequality constraint that depends on the variance of the additive noise. Through extensive comparative performance analysis of the inpainting task, it is demonstrated that ICA-learned basis outperforms K-SVD and morphological component analysis approaches in terms of visual quality. It yielded similar performance as a field of experts method but with more than two orders of magnitude lower computational complexity. On the same problems, Fourier and wavelet bases as representatives of fixed bases, exhibited the poorest performance. It is also demonstrated that noiseless inpainting-based approach to image denoising (estimation of the saturated pixel values) greatly outperforms denoising based on two-dimensional myriad filtering that is a theoretically optimal solution for this class of additive impulsive noise.

Keywords:

Mathematics Subject Classification: Primary: 68U10.

Citation:

Related Papers

Cited by

References

[1]	M. Aharon, M. Elad and A. M. Bruckstein, K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation, IEEE Trans. Signal Process., 54 (2006), 4311-4322.doi: 10.1109/TSP.2006.881199.
[2]	G. R. Arce, "Nonlinear Signal Processing - A Statistical Approach," John Wiley & Sons, 2005.
[3]	A. J. Bell and T. J. Sejnowski, An information-maximization approach to blind separation and blind deconvolution, Neural Comput., 7 (1995), 1129-1159.doi: 10.1162/neco.1995.7.6.1129.
[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]	M. Bertalmio, G. Sapiro, V. Caselles and C. Ballester, Image inpainting, in "Proceedings of the 27^th Annual Conference on Computer Graphics and Interactive Techniques," ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, (2000), 417-424.doi: 10.1145/344779.344972.
[6]	M. Bertalmio, L. Vese, G. Sapiro and S. Osher, Simultaneous structure and texture image inpainting, IEEE Trans. Image Process., 12 (2003), 882-889.doi: 10.1109/TIP.2003.815261.
[7]	M. Bethge, Factorial coding of natural images: how effective are linear models in removing higher-order dependencies?, J. Opt. Soc. Amer. A, 23 (2006), 1253-1268.doi: 10.1364/JOSAA.23.001253.
[8]	T. Blumensath and M. E. Davies, Normalised iterative hard thresholding; guaranteed stability and performance, IEEE J. Sel. Top. Signal Process., 4 (2010), 298-309.doi: 10.1109/JSTSP.2010.2042411.
[9]	P. Bofill and M. Zibulevsky, Underdetermined blind source separation using sparse representations, Signal Proc., 81 (2001), 2353-2362.doi: 10.1016/S0165-1684(01)00120-7.
[10]	A. M. Bruckstein, M. Elad and D. L. Donoho, From sparse solutions of systems of equations to sparse modeling of signals and images, SIAM Rev., 51 (2009), 34-81.doi: 10.1137/060657704.
[11]	E. Candès, M. B. Wakin and S. Boyd, Enhancing sparsity by reweighted ℓ$_1$ minimization, J. of Fourier Anal. Appl., 14 (2008), 877-905.doi: 10.1007/s00041-008-9045-x.
[12]	R. Chartrand, Exact reconstructions of sparse signals via nonconvex minimization, IEEE Signal Process. Lett., 14 (2007), 707-710.doi: 10.1109/LSP.2007.898300.
[13]	S. Choi, A. Cichocki and S.-i. Amari, Flexible independent component analysis, J. VLSI Signal Process. Sys., 26 (2000), 25-38.doi: 10.1023/A:1008135131269.
[14]	M. Elad, J.-L. Starck, P. Querre and D. L. Donoho, Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA), Appl. Comput. Harmon. Anal., 19 (2005), 340-358.doi: 10.1016/j.acha.2005.03.005.
[15]	M. Elad and M. Aharon, Image denoising via sparse and redundant representations over learned dictionaries, IEEE Trans. Image Proc., 15 (2006), 3736-3745.doi: 10.1109/TIP.2006.881969.
[16]	K. Engan, S. O. Aase and J. H. Husoy, Multi-frame compression: Theory and design, Signal Process., 80 (2000), 2121-2140.doi: 10.1016/S0165-1684(00)00072-4.
[17]	K. Engan, K. Skretting and J. H. Husoy, Family of iterative LS-based dictionary learning algorithms, ILS-DLA, for sparse signal representation, Dig. Signal Process., 17 (2007), 32-49.doi: 10.1016/j.dsp.2006.02.002.
[18]	D. Erdogmus, K. E. Hild II, Y. N. Rao and J. C. Principe, Minimax mutual information approach for independent component analysis, Neural Comput., 16 (2004), 1235-1252.doi: 10.1162/089976604773717595.
[19]	S. Foucart and M.-J. Lai, Sparsest solution of underdetermined linear systems via ℓ$_q$ minimization for $0 < q \leq 1$, Appl. Comput. Harmon. Anal., 26 (2009), 395-407.doi: 10.1016/j.acha.2008.09.001.
[20]	P. Georgiev, F. Theis and A. Cichocki, Sparse component analysis and blind source separation of underdetermined mixtures, IEEE Trans. Neural Netw., 16 (2005), 992-996.doi: 10.1109/TNN.2005.849840.
[21]	J. G. Gonzalez and G. R. Arce, Statistically-efficient filtering in impulsive environments: Weighted myriad filters, EURASIP J. Appl. Signal Process., 1 (2002), 4-20.doi: 10.1155/S1110865702000483.
[22]	I. F. Gorodnitsky and B. D. Rao, Sparse signal reconstruction from limited data using FOCUSS: a re-weighted norm minimization algorithm, IEEE Trans. Signal Process., 45 (1997), 600-616.doi: 10.1109/78.558475.
[23]	O. G. Guleryuz, Nonlinear approximation based image recovery using adaptive sparse reconstructions and iterated denoising: Part I - Theory, IEEE Trans. Image Process., 15 (2006), 539-554.doi: 10.1109/TIP.2005.863057.
[24]	O. G. Guleryuz, Nonlinear approximation based image recovery using adaptive sparse reconstructions and iterated denoising: Part II - Adaptive algorithms, IEEE Trans. Image Process., 15 (2006), 555-571.doi: 10.1109/TIP.2005.863055.
[25]	A. Hyvärinen, R. Cristescu and E. Oja, A fast algorithm for estimating overcomplete ICA bases for image windows, in "Proc. Int. Joint Conf. on Neural Networks," Washington, D.C., USA, (1999), 894-899.doi: 10.1109/IJCNN.1999.831071.
[26]	A. Hyvärinen, J. Karhunen and E. Oja, "Independent Component Analysis," John Wiley & Sons, 2001.
[27]	A. Hyvärinen and E. Oja, A fast fixed-point algorithm for independent component analysis, Neural Comput., 9 (1997), 1483-1492.doi: 10.1162/neco.1997.9.7.1483.
[28]	J. Kovačević and A. Chebira, Life beyond bases: The advent of frames (Part I), IEEE Signal Process. Mag., 25 (2007), 86-104.doi: 10.1109/MSP.2007.4286567.
[29]	J. Kovačević and A. Chebira, Life beyond bases: The advent of frames (Part II), IEEE Signal Process. Mag., 25 (2007), 115-125.doi: 10.1109/MSP.2007.904809.
[30]	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 Comput., 15 (2003), 349-396.doi: 10.1162/089976603762552951.
[31]	M. S. Lewicki and B. A. Olshausen, Probabilistic framework for the adaptation and comparison of image codes, J. Opt. Soc. Amer. A, 16 (1999), 1587-1601.doi: 10.1364/JOSAA.16.001587.
[32]	M. S. Lewicki and T. J. Sejnowski, Learning overcomplete representations, Neural Comput., 12 (2000), 337-365.doi: 10.1162/089976600300015826.
[33]	L. Ma and Y. Zhang, Bayesian estimation of overcomplete independent feature subspaces for natural images, in "Proceedings of the 7^th International Conference on Independent Component Analysis and Signal Separation," London, UK, (2007), 746-753. Available from: http://portal.acm.org/citation.cfm?id=1776684.1776783.
[34]	J. Mairal, G. Sapiro and M. Elad, Sparse representation for color image restoration, IEEE Trans. Image Process., 17 (2008), 53-69.doi: 10.1109/TIP.2007.911828.
[35]	J. Mairal, F. Bach, J. Ponce and G. Sapiro, Online learning for matrix factorization and sparse coding, J. Mach. Learn. Res., 11 (2010), 19-60.
[36]	H. Mansour, R. Saab, P. Nasiopoulos and R. Ward, Color image desaturation using sparse reconstruction, in "Proceedings of the 2010 IEEE International Conference on Acoustics, Speech and Signal Processing," Dallas, TX, USA, (2010), 778-781.doi: 10.1109/ICASSP.2010.5494984.
[37]	H. Mohimani, M. Babaie-Zadeh and C. Jutten, A fast approach for overcomplete sparse decomposition based on smoothed ℓ$_0$ norm, IEEE Trans. Signal Process., 57 (2009), 289-301.doi: 10.1109/TSP.2008.2007606.
[38]	B. A. Olshausen and D. J. Field, Emergence of simple-cell receptive field properties by learning a sparse code for natural images, Nature, 381 (1996), 607-609.doi: 10.1038/381607a0.
[39]	D. T. Pham and P. Garat, Blind separation of mixtures of independent sources through a quasimaximum likelihood approach, IEEE Trans. Signal Process., 45 (1997), 1712-1725.doi: 10.1109/78.599941.
[40]	S. Roth and M. J. Black, Fields of experts, Int. J. Computer Vision, 82 (2009), 205-229.doi: 10.1007/s11263-008-0197-6.
[41]	U. Schmidt, Q. Gao and S. Roth, A generative perspective on Markov random fields in low-level vision, in "Proc. Of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)," San Francisco, CA, USA, (2010), 1751-1758.doi: 10.1109/CVPR.2010.5539844.
[42]	I. W. Selesnick, R. V. Slyke and O. G. Guleryuz, Pixel recovery via ℓ$_1$ minimization in wavelet domain, in "Proc. IEEE Int. Conf. Image Process.," Singapore, (2004), 1819-1822.doi: 10.1109/ICIP.2004.1421429.
[43]	J. Shen, Inpainting and the fundamental problem of image processing, SIAM News, 36 (2003).
[44]	K. Skretting, J. H. Husoy and S. O. Aase, General design algorithm for sparse frame expansions, Signal Process., 86 (2006), 117-126.doi: 10.1016/j.sigpro.2005.04.013.
[45]	J. Tropp and S. J. Wright, Computational methods for sparse solution of linear inverse problems, Proc. of the IEEE, 98 (2010), 948-958.doi: 10.1109/JPROC.2010.2044010.
[46]	Z. Wang and A. Bovik, Mean squared error: Love it or leave it? A new look at signal fidelity measures, IEEE Signal Process. Mag., 26 (2009), 98-117.doi: 10.1109/MSP.2008.930649.
[47]	Z. Wang, A. C. Bovik, H. R. Sheikh and E. P. Simoncelli, Image quality assessment: From error visibility to structural similarity, IEEE Trans. Image Process., 13 (2004), 600-612.doi: 10.1109/TIP.2003.819861.
[48]	X. Zhang and D. H. Brainard, Estimation of saturated pixel values in digital color imaging, J. Opt. Soc. Amer. A, 21 (2004), 2301-2310.doi: 10.1364/JOSAA.21.002301.
[49]	L. Zhang, A. Cichocki and S.-i. Amari, Self-adaptive blind source separation based on activation function adaptation, IEEE Trans. Neural Net., 15 (2004), 233-244.doi: 10.1109/TNN.2004.824420.