Call for Paper - May 2023 Edition
IJCA solicits original research papers for the May 2023 Edition. Last date of manuscript submission is April 20, 2023. Read More

A Novel Inpainting Algorithm based on Sparse Representation

International Journal of Computer Applications
© 2013 by IJCA Journal
Volume 74 - Number 6
Year of Publication: 2013
C. Ramya
S. Subha Rani

C Ramya and Subha S Rani. Article: A Novel Inpainting Algorithm based on Sparse Representation. International Journal of Computer Applications 74(6):31-37, July 2013. Full text available. BibTeX

	author = {C. Ramya and S. Subha Rani},
	title = {Article: A Novel Inpainting Algorithm based on Sparse Representation},
	journal = {International Journal of Computer Applications},
	year = {2013},
	volume = {74},
	number = {6},
	pages = {31-37},
	month = {July},
	note = {Full text available}


Recent studies in sparse representations show a variety of applications in the field of image processing. Such as in image denoising, inpainting, compression and more. But always the size of the dictionary has a trade off between the approximation speed and accuracy. In this paper, a moving k-means based dictionary pruning algorithm is applied to the patches of the dictionary to discover an optimum number of dictionary elements for a given data set. This optimized dictionary size feature, will improve the convergence speed of the decomposition algorithm without compromising its approximation accuracy. It also increases the performance of the decomposition algorithm. Simulation results show that the proposed optimized dictionary selection with KSVD (K-means singular value decomposition) yield better image inpainting than traditional KSVD.


  • Marcelo Bertalmio, Guillermo Sapiro, Vicent Caselles, Coloma Ballester, "Image inpainting", in Proceedings of 27th SIGGRAPH, Louisiana USA, pp. 417-424,2000.
  • Manuel Oliveira, Brian. Bowen, Richard McKenna, Yu-Sung Chang, "Fast digital inpainting", In Proceedings of International Conference on Visualization, Imaging and Image Processing, pp. 261-266,2001.
  • Tony Chan, Jianhong Shen, "Mathematical models for local nontexture inpaintings", SIAM Journal on Applied Math, Vol. 62, pp. 1019-1043,2001.
  • Coloma Ballester, Marcelo Bertalmio, Vicent Caselles, Guillermo Sapiro, Joan Verdera, "Fillingin by joint interpolation of vector fields and gray levels", IEEE Transactions on Image Processing, Vol. 10, pp. 1200–1211,2001.
  • Zhaoxia Wang, Quan Wang, CS Chang, Ming bai, Zhen Sun, Ting Yang, "Image Inpainting Method based on Evolutionary Algorithm", International Journal of Digital Content Technology and its Applications, Vol. 5, pp. 187-193,2011.
  • Alexei Efros, Thomas Lung, "Texture synthesis by non-parametric sampling", In Proceeding of International Conference on Computer Vision,Greece, pp. 1033-1038,1999.
  • Antonio Criminisi, Patrick Pérez, Kentaro Toyama, "Region filling and object removal by exemplar-based image inpainting", IEEE Transactions on Image Processing, Vol. 13, pp. 1200-1212,2004.
  • Ubiratã Ignácio, Cláudio Jung, "Block-based image inpainting in the wavelet domain", The VisualComputer, Vol. 23, pp. 733-741,2007.
  • Jian Sun, Lu Yuan, Jiaya Jia, Heung-Yeung Shum "Image completion with structure propagation", ACM Transactions on Graphics, Vol. 24, pp. 861-868,2005.
  • Nikos Komodakis, Georgios Tziritas "Image completion using efficient belief propagation via priority scheduling and dynamic pruning", IEEE Transactions on Image Processing, Vol. 16, pp. 2649–2661,2007.
  • Priyam Chaterjee, Prof. Peyman Milanfar, "K-SVD Algorithm for Denoising of Gray-Scale Images", Spring ,pp. 1-12,2007.
  • M. J. Mairal &G. Sapiro,"Sparse representation for color image restoration. IEEE Trans. Image Process", Vol. 17, pp. 53–69,2008.
  • M. j. Fadili, j. -l. Starck and f. Murtagh, "Inpainting and zooming using Sparse representations", The computer journal, vol. 52 ,pp. 64-67,2009.
  • Ming Zhao, Shutao Li," Hybrid Inpainting Algorithm Based on Sparse Representation and Fast Inpainting Method", International Journal of Digital Content Technology and its Applications. Vol. 5, pp. 239-347,2011.
  • S. Mallat, G. Davis, & Z. Zhang,"Adaptive time-frequency decompositions, PIE Journal of Optical Engineering",vol. 33, pp. 2183–2191,1994.
  • Y. Pati, R. Rezaiifar, and P. Krishnaprasad, "Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition",in Asilomar conference on signals system and computers, pp. 1-3,1993.
  • S. Mallat and Z. Zhang, "Matching pursuits with time-frequency dictionaries", IEEE Transactions on Signal Processing, vol. 41,pp. 3397–3415,1993.
  • David L. Donoho, Michael Elad, and Vladimir Temlyakov. " Stable re-covery of sparse overcomplete representations in the presence of noise",IEEE Transactions on Information Theory, vol. 52,pp6-18,2006
  • Michal Aharon, Michael Elad, and Alfred Bruckstein. "K-svd: An algorithm for designing overcomplete dictionaries for sparse representation". IEEE Transactions on Signal Processing, vol. 54,pp. 4311–4322,2006.
  • Manuel M. Oliveira Brian Bowen Richard McKenna Yu-Sung Chang," Fast Digital Image Inpainting", in the International Conference on Visualization, Imaging and Image Processing (VIIP 2001), Marbella, Spain,pp1-6, 2001.
  • C Ramya ,S Subha Rani," Video denoising without motion estimation using K-means clustering,journal of scientific and industrial research", Vol. 70, pp. 251-255,2011.