Abstract
We propose a deblurring algorithm that explicitly takes into account the sparse characteristics of natural images and does not entail solving a numerically ill-conditioned backward-diffusion. The key observation is that the sparse coefficients that encode a given image with respect to an over-complete basis are the same that encode a blurred version of the image with respect to a modified basis. Following an “analysis-by-synthesis” approach, an explicit generative model is used to compute a sparse representation of the blurred image, and its coefficients are used to combine elements of the original basis to yield a restored image.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aharon, M., Elad, M., Bruckstein, A.: K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation. IEEE Trans. Signal Process. 54(11), 4311–4322 (2006)
Andrews, H.C., Hunt, B.R.: Digital Image Restoration. Prentice-Hall, Englewood Cliffs (1977)
Cai, J., Ji, H., Liu, C., Shen, Z.: Blind motion deblurring from a single image using sparse approximation. In: Intl. Conf. on Comp. Vis. and Patt. Recog. (CVPR), Miami, Florida, USA, 2009
Dabov, K., Foi, A., Katkovnik, V., Egiazarian, K.: Image denoising by sparse 3D transform-domain collaborative filtering. IEEE Trans. Image Process. 16(8) (2007)
Dabov, K., Foi, A., Egiazarian, K.: Image restoration by sparse 3D transform-domain collaborative filtering. In: Proc. SPIE Electronic Imaging, vol. 6812-07, San Jose, California, USA, January 2008
Datsenko, D., Elad, M.: Example-based single document image super-resolution: a global map approach with outlier rejection. Multidimens. Syst. Signal Process. 18(2–3), 103–121 (2007)
Dias, J.M.B.: Fast GEM wavelet-based image deconvolution algorithm. In: Intl. Conf. on Image Process. (ICIP), vol. 3, pp. 961–964 (2003)
Dobrosotskaya, J.A., Bertozzi, A.L.: A wavelet-Laplace variational technique for image deconvolution and inpainting. IEEE Trans. Image Process. 17(5), 657–663 (2003)
Efros, A.A., Leung, T.K.: Texture synthesis by non-parameteric sampling. In: Intl. Conf. Computer Vision (ICCV), vol. 2, pp. 1033–1038 (1999)
Elad, M., Aharon, M.: Image denoising via sparse and redundant representations over learned dictionaries. IEEE Trans. Image Process. 15(12), 3736–3745 (2006)
Favaro, P., Soatto, S., Vese, L., Osher, S.J.: Shape from anisotropic diffusion. In: Intl. Conf. on Comp. Vis. and Patt. Recog. (CVPR), pp. 179–186 (June 2003)
Figueiredo, M., Nowak, R.: An EM algorithm for wavelet-based image restoration. IEEE Trans. Image Process. 12, 906–916 (2003)
Figueiredo, M., Nowak, R.: A bound optimization approach to wavelet-based image deconvolution. In: Intl. Conf. on Image Process. (ICIP), vol. 2, pp. 782–785 (2005)
Foi, A., Dabov, K., Katkovnik, V., Egiazarian, K.: Shape-adaptive DCT for denoising and image reconstruction. In: Proc. of SPIE Electronic Imaging, Image Processing: Algorithms and Systems V. 6064, 6064N (2006)
Freeman, W.T., Jones, T.R., Pasztor, E.C.: Example-based super-resolution. In: IEEE Computer Graphics and Applications, 2002
Grenander, U.: General Pattern Theory: A Mathematical Study of Regular Structures. Cambridge University Press, Cambridge (1993)
Guerrero-Colon, J.A., Mancera, L., Portilla, J.: Image restoration using space-variant Gaussian scale mixtures in overcomplete pyramids. IEEE Trans. Image Process. 17(1), 27–41 (2008)
Huang, J., Mumford, D.: Statistics of natural images and models. In: Intl. Conf. on Comp. Vis. and Patt. Recog. (CVPR), pp. 541–547 (1999)
Lewicki, M.S., Olshausen, B.A.: Inferring sparse, overcomplete image codes using an efficient coding framework. In: Advances in Neural Information Processing 10 (Proc. NIPS ’97), pp. 815–821 (1998)
Ma, J., Le Dimet, F.-X.: Deblurring from highly incomplete measurements for remote sensing. IEEE Trans. Geosci. Remote Sens. 47(3), 792–802 (2009)
Mairal, J., Elad, M., Sapiro, G.: Learning multiscale sparse representations for image and video restoration. IEEE Trans. Image Process. 17(1), 53–69 (2008)
Martin, D., Fowlkes, C., Tal, D., Malik, J.: A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In: Intl. Conf. Computer Vision (ICCV), vol. 2, pp. 416–423 (2001)
Mignotte, M.: A segmentation-based regularization term for image deconvolution. IEEE Trans. Image Process. 15(7), 1973–1984 (2006)
Neelamani, R., Choi, H., Baraniuk, R.G.: ForWaRD: Fourier-wavelet regularized deconvolution for ill-conditioned systems. IEEE Trans. Signal Process. 52(2), 418–433 (2004)
Portilla, J., Strela, V., Wainwright, M., Simoncelli, E.P.: Image denoising using scale mixtures of Gaussians in the wavelet domain. IEEE Trans. Image Process. 12(11), 1338–1351 (2003)
Protter, M., Elad, M., Takeda, H., Milanfar, P.: Generalizing the non-local-means to super-resolution reconstruction. IEEE Trans. Image Process 36 (2009)
Rudin, L., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60, 259–268 (1992)
Takeda, H., Farsiu, S., Milanfar, P.: Kernel regression for image processing and reconstruction. IEEE Trans. Image Process. 16(2), 347–364 (2007)
Takeda, H., Farsiu, S., Milanfar, P.: Deblurring using regularized locally adaptive kernel regression. IEEE Trans. Image Process. 17(4), 550–563 (2008)
Tikhonov, A., Arsenin, V.: Solution of Ill-Posed Problems. Wiley, New York (1977)
Tropp, J.A.: Greed is good: Algorithmic results for sparse approximation. IEEE Trans. Inf. Theory 50, 2231–2242 (2004)
Yang, J., Wright, J., Huang, T., Ma, Y.: Image super-resolution as sparse representation of raw image patches. In: Intl. Conf. on Comp. Vis. and Patt. Recog. (CVPR), 2008
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Lou, Y., Bertozzi, A.L. & Soatto, S. Direct Sparse Deblurring. J Math Imaging Vis 39, 1–12 (2011). https://doi.org/10.1007/s10851-010-0220-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10851-010-0220-8