November  2011, 5(4): 815-841. doi: 10.3934/ipi.2011.5.815

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

1. 

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

Received  February 2010 Revised  July 2011 Published  November 2011

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.
Citation: 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
References:
[1]

IEEE Trans. Signal Process., 54 (2006), 4311-4322. doi: 10.1109/TSP.2006.881199.  Google Scholar

[2]

John Wiley & Sons, 2005. Google Scholar

[3]

Neural Comput., 7 (1995), 1129-1159. doi: 10.1162/neco.1995.7.6.1129.  Google Scholar

[4]

Vision Research, 37 (1997), 3327-3338. doi: 10.1016/S0042-6989(97)00121-1.  Google Scholar

[5]

in "Proceedings of the 27th 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.  Google Scholar

[6]

IEEE Trans. Image Process., 12 (2003), 882-889. doi: 10.1109/TIP.2003.815261.  Google Scholar

[7]

J. Opt. Soc. Amer. A, 23 (2006), 1253-1268. doi: 10.1364/JOSAA.23.001253.  Google Scholar

[8]

IEEE J. Sel. Top. Signal Process., 4 (2010), 298-309. doi: 10.1109/JSTSP.2010.2042411.  Google Scholar

[9]

Signal Proc., 81 (2001), 2353-2362. doi: 10.1016/S0165-1684(01)00120-7.  Google Scholar

[10]

SIAM Rev., 51 (2009), 34-81. doi: 10.1137/060657704.  Google Scholar

[11]

J. of Fourier Anal. Appl., 14 (2008), 877-905. doi: 10.1007/s00041-008-9045-x.  Google Scholar

[12]

IEEE Signal Process. Lett., 14 (2007), 707-710. doi: 10.1109/LSP.2007.898300.  Google Scholar

[13]

J. VLSI Signal Process. Sys., 26 (2000), 25-38. doi: 10.1023/A:1008135131269.  Google Scholar

[14]

Appl. Comput. Harmon. Anal., 19 (2005), 340-358. doi: 10.1016/j.acha.2005.03.005.  Google Scholar

[15]

IEEE Trans. Image Proc., 15 (2006), 3736-3745. doi: 10.1109/TIP.2006.881969.  Google Scholar

[16]

Signal Process., 80 (2000), 2121-2140. doi: 10.1016/S0165-1684(00)00072-4.  Google Scholar

[17]

Dig. Signal Process., 17 (2007), 32-49. doi: 10.1016/j.dsp.2006.02.002.  Google Scholar

[18]

Neural Comput., 16 (2004), 1235-1252. doi: 10.1162/089976604773717595.  Google Scholar

[19]

Appl. Comput. Harmon. Anal., 26 (2009), 395-407. doi: 10.1016/j.acha.2008.09.001.  Google Scholar

[20]

IEEE Trans. Neural Netw., 16 (2005), 992-996. doi: 10.1109/TNN.2005.849840.  Google Scholar

[21]

EURASIP J. Appl. Signal Process., 1 (2002), 4-20. doi: 10.1155/S1110865702000483.  Google Scholar

[22]

IEEE Trans. Signal Process., 45 (1997), 600-616. doi: 10.1109/78.558475.  Google Scholar

[23]

IEEE Trans. Image Process., 15 (2006), 539-554. doi: 10.1109/TIP.2005.863057.  Google Scholar

[24]

IEEE Trans. Image Process., 15 (2006), 555-571. doi: 10.1109/TIP.2005.863055.  Google Scholar

[25]

in "Proc. Int. Joint Conf. on Neural Networks," Washington, D.C., USA, (1999), 894-899. doi: 10.1109/IJCNN.1999.831071.  Google Scholar

[26]

John Wiley & Sons, 2001. Google Scholar

[27]

Neural Comput., 9 (1997), 1483-1492. doi: 10.1162/neco.1997.9.7.1483.  Google Scholar

[28]

IEEE Signal Process. Mag., 25 (2007), 86-104. doi: 10.1109/MSP.2007.4286567.  Google Scholar

[29]

IEEE Signal Process. Mag., 25 (2007), 115-125. doi: 10.1109/MSP.2007.904809.  Google Scholar

[30]

Neural Comput., 15 (2003), 349-396. doi: 10.1162/089976603762552951.  Google Scholar

[31]

J. Opt. Soc. Amer. A, 16 (1999), 1587-1601. doi: 10.1364/JOSAA.16.001587.  Google Scholar

[32]

Neural Comput., 12 (2000), 337-365. doi: 10.1162/089976600300015826.  Google Scholar

[33]

in "Proceedings of the 7th 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. Google Scholar

[34]

IEEE Trans. Image Process., 17 (2008), 53-69. doi: 10.1109/TIP.2007.911828.  Google Scholar

[35]

J. Mach. Learn. Res., 11 (2010), 19-60.  Google Scholar

[36]

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.  Google Scholar

[37]

IEEE Trans. Signal Process., 57 (2009), 289-301. doi: 10.1109/TSP.2008.2007606.  Google Scholar

[38]

Nature, 381 (1996), 607-609. doi: 10.1038/381607a0.  Google Scholar

[39]

IEEE Trans. Signal Process., 45 (1997), 1712-1725. doi: 10.1109/78.599941.  Google Scholar

[40]

Int. J. Computer Vision, 82 (2009), 205-229. doi: 10.1007/s11263-008-0197-6.  Google Scholar

[41]

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.  Google Scholar

[42]

in "Proc. IEEE Int. Conf. Image Process.," Singapore, (2004), 1819-1822. doi: 10.1109/ICIP.2004.1421429.  Google Scholar

[43]

SIAM News, 36 (2003). Google Scholar

[44]

Signal Process., 86 (2006), 117-126. doi: 10.1016/j.sigpro.2005.04.013.  Google Scholar

[45]

Proc. of the IEEE, 98 (2010), 948-958. doi: 10.1109/JPROC.2010.2044010.  Google Scholar

[46]

IEEE Signal Process. Mag., 26 (2009), 98-117. doi: 10.1109/MSP.2008.930649.  Google Scholar

[47]

IEEE Trans. Image Process., 13 (2004), 600-612. doi: 10.1109/TIP.2003.819861.  Google Scholar

[48]

J. Opt. Soc. Amer. A, 21 (2004), 2301-2310. doi: 10.1364/JOSAA.21.002301.  Google Scholar

[49]

IEEE Trans. Neural Net., 15 (2004), 233-244. doi: 10.1109/TNN.2004.824420.  Google Scholar

show all references

References:
[1]

IEEE Trans. Signal Process., 54 (2006), 4311-4322. doi: 10.1109/TSP.2006.881199.  Google Scholar

[2]

John Wiley & Sons, 2005. Google Scholar

[3]

Neural Comput., 7 (1995), 1129-1159. doi: 10.1162/neco.1995.7.6.1129.  Google Scholar

[4]

Vision Research, 37 (1997), 3327-3338. doi: 10.1016/S0042-6989(97)00121-1.  Google Scholar

[5]

in "Proceedings of the 27th 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.  Google Scholar

[6]

IEEE Trans. Image Process., 12 (2003), 882-889. doi: 10.1109/TIP.2003.815261.  Google Scholar

[7]

J. Opt. Soc. Amer. A, 23 (2006), 1253-1268. doi: 10.1364/JOSAA.23.001253.  Google Scholar

[8]

IEEE J. Sel. Top. Signal Process., 4 (2010), 298-309. doi: 10.1109/JSTSP.2010.2042411.  Google Scholar

[9]

Signal Proc., 81 (2001), 2353-2362. doi: 10.1016/S0165-1684(01)00120-7.  Google Scholar

[10]

SIAM Rev., 51 (2009), 34-81. doi: 10.1137/060657704.  Google Scholar

[11]

J. of Fourier Anal. Appl., 14 (2008), 877-905. doi: 10.1007/s00041-008-9045-x.  Google Scholar

[12]

IEEE Signal Process. Lett., 14 (2007), 707-710. doi: 10.1109/LSP.2007.898300.  Google Scholar

[13]

J. VLSI Signal Process. Sys., 26 (2000), 25-38. doi: 10.1023/A:1008135131269.  Google Scholar

[14]

Appl. Comput. Harmon. Anal., 19 (2005), 340-358. doi: 10.1016/j.acha.2005.03.005.  Google Scholar

[15]

IEEE Trans. Image Proc., 15 (2006), 3736-3745. doi: 10.1109/TIP.2006.881969.  Google Scholar

[16]

Signal Process., 80 (2000), 2121-2140. doi: 10.1016/S0165-1684(00)00072-4.  Google Scholar

[17]

Dig. Signal Process., 17 (2007), 32-49. doi: 10.1016/j.dsp.2006.02.002.  Google Scholar

[18]

Neural Comput., 16 (2004), 1235-1252. doi: 10.1162/089976604773717595.  Google Scholar

[19]

Appl. Comput. Harmon. Anal., 26 (2009), 395-407. doi: 10.1016/j.acha.2008.09.001.  Google Scholar

[20]

IEEE Trans. Neural Netw., 16 (2005), 992-996. doi: 10.1109/TNN.2005.849840.  Google Scholar

[21]

EURASIP J. Appl. Signal Process., 1 (2002), 4-20. doi: 10.1155/S1110865702000483.  Google Scholar

[22]

IEEE Trans. Signal Process., 45 (1997), 600-616. doi: 10.1109/78.558475.  Google Scholar

[23]

IEEE Trans. Image Process., 15 (2006), 539-554. doi: 10.1109/TIP.2005.863057.  Google Scholar

[24]

IEEE Trans. Image Process., 15 (2006), 555-571. doi: 10.1109/TIP.2005.863055.  Google Scholar

[25]

in "Proc. Int. Joint Conf. on Neural Networks," Washington, D.C., USA, (1999), 894-899. doi: 10.1109/IJCNN.1999.831071.  Google Scholar

[26]

John Wiley & Sons, 2001. Google Scholar

[27]

Neural Comput., 9 (1997), 1483-1492. doi: 10.1162/neco.1997.9.7.1483.  Google Scholar

[28]

IEEE Signal Process. Mag., 25 (2007), 86-104. doi: 10.1109/MSP.2007.4286567.  Google Scholar

[29]

IEEE Signal Process. Mag., 25 (2007), 115-125. doi: 10.1109/MSP.2007.904809.  Google Scholar

[30]

Neural Comput., 15 (2003), 349-396. doi: 10.1162/089976603762552951.  Google Scholar

[31]

J. Opt. Soc. Amer. A, 16 (1999), 1587-1601. doi: 10.1364/JOSAA.16.001587.  Google Scholar

[32]

Neural Comput., 12 (2000), 337-365. doi: 10.1162/089976600300015826.  Google Scholar

[33]

in "Proceedings of the 7th 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. Google Scholar

[34]

IEEE Trans. Image Process., 17 (2008), 53-69. doi: 10.1109/TIP.2007.911828.  Google Scholar

[35]

J. Mach. Learn. Res., 11 (2010), 19-60.  Google Scholar

[36]

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.  Google Scholar

[37]

IEEE Trans. Signal Process., 57 (2009), 289-301. doi: 10.1109/TSP.2008.2007606.  Google Scholar

[38]

Nature, 381 (1996), 607-609. doi: 10.1038/381607a0.  Google Scholar

[39]

IEEE Trans. Signal Process., 45 (1997), 1712-1725. doi: 10.1109/78.599941.  Google Scholar

[40]

Int. J. Computer Vision, 82 (2009), 205-229. doi: 10.1007/s11263-008-0197-6.  Google Scholar

[41]

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.  Google Scholar

[42]

in "Proc. IEEE Int. Conf. Image Process.," Singapore, (2004), 1819-1822. doi: 10.1109/ICIP.2004.1421429.  Google Scholar

[43]

SIAM News, 36 (2003). Google Scholar

[44]

Signal Process., 86 (2006), 117-126. doi: 10.1016/j.sigpro.2005.04.013.  Google Scholar

[45]

Proc. of the IEEE, 98 (2010), 948-958. doi: 10.1109/JPROC.2010.2044010.  Google Scholar

[46]

IEEE Signal Process. Mag., 26 (2009), 98-117. doi: 10.1109/MSP.2008.930649.  Google Scholar

[47]

IEEE Trans. Image Process., 13 (2004), 600-612. doi: 10.1109/TIP.2003.819861.  Google Scholar

[48]

J. Opt. Soc. Amer. A, 21 (2004), 2301-2310. doi: 10.1364/JOSAA.21.002301.  Google Scholar

[49]

IEEE Trans. Neural Net., 15 (2004), 233-244. doi: 10.1109/TNN.2004.824420.  Google Scholar

[1]

Xuemei Chen, Julia Dobrosotskaya. Inpainting via sparse recovery with directional constraints. Mathematical Foundations of Computing, 2020, 3 (4) : 229-247. doi: 10.3934/mfc.2020025

[2]

Haixia Liu, Jian-Feng Cai, Yang Wang. Subspace clustering by (k,k)-sparse matrix factorization. Inverse Problems & Imaging, 2017, 11 (3) : 539-551. doi: 10.3934/ipi.2017025

[3]

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

[4]

Riccardo March, Giuseppe Riey. Analysis of a variational model for motion compensated inpainting. Inverse Problems & Imaging, 2017, 11 (6) : 997-1025. doi: 10.3934/ipi.2017046

[5]

Tyrus Berry, Timothy Sauer. Consistent manifold representation for topological data analysis. Foundations of Data Science, 2019, 1 (1) : 1-38. doi: 10.3934/fods.2019001

[6]

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

[7]

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

[8]

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

[9]

Yitong Guo, Bingo Wing-Kuen Ling. Principal component analysis with drop rank covariance matrix. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020072

[10]

Jia Cai, Junyi Huo. Sparse generalized canonical correlation analysis via linearized Bregman method. Communications on Pure & Applied Analysis, 2020, 19 (8) : 3933-3945. doi: 10.3934/cpaa.2020173

[11]

Ningyu Sha, Lei Shi, Ming Yan. Fast algorithms for robust principal component analysis with an upper bound on the rank. Inverse Problems & Imaging, 2021, 15 (1) : 109-128. doi: 10.3934/ipi.2020067

[12]

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

[13]

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

[14]

Lok Ming Lui, Chengfeng Wen, Xianfeng Gu. A conformal approach for surface inpainting. Inverse Problems & Imaging, 2013, 7 (3) : 863-884. doi: 10.3934/ipi.2013.7.863

[15]

Jian-Feng Cai, Raymond H. Chan, Zuowei Shen. Simultaneous cartoon and texture inpainting. Inverse Problems & Imaging, 2010, 4 (3) : 379-395. doi: 10.3934/ipi.2010.4.379

[16]

Yuhong Dai, Nobuo Yamashita. Convergence analysis of sparse quasi-Newton updates with positive definite matrix completion for two-dimensional functions. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 61-69. doi: 10.3934/naco.2011.1.61

[17]

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

[18]

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

[19]

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

[20]

Xiaoqun Zhang, Tony F. Chan. Wavelet inpainting by nonlocal total variation. Inverse Problems & Imaging, 2010, 4 (1) : 191-210. doi: 10.3934/ipi.2010.4.191

2019 Impact Factor: 1.373

Metrics

  • PDF downloads (103)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]