Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



$ \ell_0$ Minimization for wavelet frame based image restoration

Authors: Yong Zhang, Bin Dong and Zhaosong Lu
Journal: Math. Comp. 82 (2013), 995-1015
MSC (2010): Primary 80M50, 90C26, 42C40, 68U10
Published electronically: August 15, 2012
MathSciNet review: 3008846
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The theory of (tight) wavelet frames has been extensively studied in the past twenty years and they are currently widely used for image restoration and other image processing and analysis problems. The success of wavelet frame based models, including balanced approach and analysis based approach, is due to their capability of sparsely approximating piecewise smooth functions like images. Motivated by the balanced approach and analysis based approach, we shall propose a wavelet frame based $ \ell _0$ minimization model, where the $ \ell _0$ ``norm'' of the frame coefficients is penalized. We adapt the penalty decomposition (PD) method of Lu and Zhang to solve the proposed optimization problem. Some convergence analysis of the adapted PD method will also be provided. Numerical results showed that the proposed model solved by the PD method can generate images with better quality than those obtained by either analysis based approach or balanced approach in terms of restoring sharp features as well as maintaining smoothness of the recovered images.

References [Enhancements On Off] (What's this?)

  • 1. A. Antoniadis and J. Fan.
    Regularization of wavelet approximations.
    Journal of the American Statistical Association, 96(455):939-967, 2001. MR 1946364 (2003k:62098)
  • 2. G. Aubert and P. Kornprobst.
    Mathematical problems in image processing: partial differential equations and the calculus of variations.
    Springer, 2006. MR 2244145 (2007j:94004)
  • 3. A. Beck and M. Teboulle.
    A fast iterative shrinkage-thresholding algorithm for linear inverse problems.
    SIAM Journal on Imaging Sciences, 2(1):183-202, 2009. MR 2486527 (2010d:35390)
  • 4. E.G. Birgin, J.M. Martínez, and M. Raydan.
    Nonmonotone spectral projected gradient methods on convex sets.
    SIAM Journal on Optimization, 10(4):1196-1211, 2000. MR 1777088 (2001e:90143)
  • 5. T. Blumensath and M.E. Davies.
    Iterative thresholding for sparse approximations.
    Journal of Fourier Analysis and Applications, 14(5):629-654, 2008. MR 2461601 (2009j:68077)
  • 6. T. Blumensath and M.E. Davies.
    Iterative hard thresholding for compressed sensing.
    Applied and Computational Harmonic Analysis, 27(3):265-274, 2009. MR 2559726 (2010i:94048)
  • 7. J.F. Cai, R.H. Chan, L. Shen, and Z. Shen.
    Convergence analysis of tight framelet approach for missing data recovery.
    Advances in Computational Mathematics, 31(1):87-113, 2009. MR 2511575 (2010c:42070)
  • 8. J.F. Cai, R.H. Chan, and Z. Shen.
    Simultaneous cartoon and texture inpainting.
    Inverse Problems and Imaging 4(3):379-395, 2010. MR 2671102 (2011k:94019)
  • 9. J.F. Cai, B. Dong, S. Osher, and Z. Shen.
    Image restorations: Total variation, wavelet frames and beyond.
    J. Amer. Math. Soc. 25(4):1033-1089, 2012. MR 2947945
  • 10. J.F. Cai, S. Osher, and Z. Shen.
    Linearized Bregman iterations for frame-based image deblurring.
    SIAM Journal on Imaging Sciences, 2(1):226-252, 2009. MR 2486529 (2010h:94041)
  • 11. J.F. Cai, S. Osher, and Z. Shen.
    Split Bregman methods and frame based image restoration.
    Multiscale Modeling and Simulation: A SIAM Interdisciplinary Journal, 8(2):337-369, 2009. MR 2581025 (2011a:94016)
  • 12. E.J. Candes, Y.C. Eldar, D. Needell, and P. Randall.
    Compressed sensing with coherent and redundant dictionaries.
    Applied and Computational Harmonic Analysis, 2010. MR 2795875
  • 13. E.J. Candès, J. Romberg, and T. Tao.
    Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information.
    IEEE Transactions on Information Theory, 52(2):489-509, 2006. MR 2236170 (2007e:94020)
  • 14. E.J. Candes and T. Tao.
    Decoding by linear programming.
    IEEE Transactions on Information Theory, 51(12):4203-4215, 2005. MR 2243152 (2007b:94313)
  • 15. E.J. Candes and T. Tao.
    Near-optimal signal recovery from random projections: Universal encoding strategies?
    IEEE Transactions on Information Theory, 52(12):5406-5425, 2006. MR 2300700 (2008c:94009)
  • 16. A. Chai and Z. Shen.
    Deconvolution: A wavelet frame approach.
    Numerische Mathematik, 106(4):529-587, 2007. MR 2317925 (2008i:42067)
  • 17. A. Chambolle and P.L. Lions.
    Image recovery via total variation minimization and related problems.
    Numerische Mathematik, 76(2):167-188, 1997. MR 1440119 (98c:65099)
  • 18. R.H. Chan, T.F. Chan, L. Shen, and Z. Shen.
    Wavelet algorithms for high-resolution image reconstruction.
    SIAM Journal on Scientific Computing, 24(4):1408-1432, 2003. MR 1976222 (2004e:94003)
  • 19. R.H. Chan, S.D. Riemenschneider, L. Shen, and Z. Shen.
    Tight frame: an efficient way for high-resolution image reconstruction.
    Applied and Computational Harmonic Analysis, 17(1):91-115, 2004. MR 2067917 (2005h:94006)
  • 20. R.H. Chan, L. Shen, and Z. Shen.
    A framelet-based approach for image inpainting.
    technical report, 4:325, 2005.
  • 21. R.H. Chan, Z. Shen, and T. Xia.
    A framelet algorithm for enhancing video stills.
    Applied and Computational Harmonic Analysis, 23(2):153-170, 2007. MR 2344608 (2008h:94006)
  • 22. T. Chan, S. Esedoglu, F. Park, and A. Yip.
    Total variation image restoration: Overview and recent developments.
    Handbook of mathematical models in computer vision, pages 17-31, 2006. MR 2232522
  • 23. T.F. Chan and J. Shen.
    Image processing and analysis: variational, PDE, wavelet, and stochastic methods.
    Society for Industrial Mathematics, 2005. MR 2143289 (2007c:94011)
  • 24. I. Daubechies.
    Ten lectures on wavelets, volume CBMS-NSF Lecture Notes, SIAM, nr. 61.
    Society for Industrial Mathematics, 1992. MR 1162107 (93e:42045)
  • 25. I. Daubechies, B. Han, A. Ron, and Z. Shen.
    Framelets: MRA-based constructions of wavelet frames.
    Applied and Computational Harmonic Analysis, 14(1):1-46, 2003. MR 1971300 (2004a:42046)
  • 26. I. Daubechies, G. Teschke, and L. Vese.
    Iteratively solving linear inverse problems under general convex constraints.
    Inverse Problems and Imaging, 1(1):29-46, 2007. MR 2262744 (2008e:35204)
  • 27. B. Dong, A. Chien, and Z. Shen.
    Frame based segmentation for medical images.
    Communications in Mathematical Sciences, 9(2):551-559, 2010. MR 2815684
  • 28. B. Dong and Z. Shen.
    MRA based wavelet frames and applications.
    IAS Lecture Notes Series, Summer Program on ``The Mathematics of Image Processing'', Park City Mathematics Institute, 2010.
  • 29. B. Dong and Z. Shen.
    Frame based surface reconstruction from unorganized points.
    J. Comput. Phys., 230(22), 8247-8255, 2011. MR 2835419 (2012j:65058)
  • 30. D.L. Donoho.
    Compressed sensing.
    IEEE Transactions on Information Theory, 52:1289-1306, 2006. MR 2241189 (2007e:94013)
  • 31. M. Elad, J.L. Starck, P. Querre, and D.L. Donoho.
    Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA).
    Applied and Computational Harmonic Analysis, 19(3):340-358, 2005. MR 2186449 (2007h:94007)
  • 32. M.J. Fadili and J.L. Starck.
    Sparse representations and bayesian image inpainting.
    Proceedings of SPARS, 2005.
  • 33. M.J. Fadili, J.L. Starck, and F. Murtagh.
    Inpainting and zooming using sparse representations.
    The Computer Journal, 52(1):64, 2009.
  • 34. M.A.T. Figueiredo and R.D. Nowak.
    An EM algorithm for wavelet-based image restoration.
    IEEE Transactions on Image Processing, 12(8):906-916, 2003. MR 2008658
  • 35. M.A.T. Figueiredo and R.D. Nowak.
    A bound optimization approach to wavelet-based image deconvolution.
    IEEE International Conference on Image Processing, 2005.
  • 36. D. Geman and C. Yang.
    Nonlinear image recovery with half-quadratic regularization.
    Image Processing, IEEE Transactions on, 4(7):932-946, 1995.
  • 37. T. Goldstein and S. Osher.
    The split Bregman algorithm for L1 regularized problems.
    SIAM Journal on Imaging Sciences, 2(2):323-343, 2009. MR 2496060 (2010e:65087)
  • 38. K.K. Herrity, A.C. Gilbert, and J.A. Tropp.
    Sparse approximation via iterative thresholding.
    IEEE International Conference on Acoustics, Speech and Signal Processing, 2006.
  • 39. X. Jia, Y. Lou, B. Dong, and S. Jiang.
    GPU-based iterative cone beam CT reconstruction using tight frame regularization.
    Phys. Med. Biol. 56(13):3787-3807, 2011.
  • 40. Z. Lu and Y. Zhang.
    Penalty decomposition methods for $ l_0$-norm minimization.
    preprint, 2010.
  • 41. Y. Meyer.
    Oscillating patterns in image processing and nonlinear evolution equations: the fifteenth Dean Jacqueline B. Lewis memorial lectures, volume 22.
    Amer Mathematical Society, 2001. MR 1852741 (2002j:43001)
  • 42. S. Osher and R.P. Fedkiw.
    Level set methods and dynamic implicit surfaces.
    Springer, 2003. MR 1939127 (2003j:65002)
  • 43. R.T. Rockafellar and J.B.W. Roger.
    Variational analysis, volume 317.
    Springer, 2004. MR 1491362 (98m:49001)
  • 44. A. Ron and Z. Shen.
    Affine Systems in $ L_2(\mathbb{R}^d)$: The Analysis of the Analysis Operator.
    Journal of Functional Analysis, 148(2):408-447, 1997. MR 1469348 (99g:42043)
  • 45. L. Rudin, S. Osher, and E. Fatemi.
    Nonlinear total variation based noise removal algorithms.
    Journal of Physics D, 60:259-268, 1992.
  • 46. G. Sapiro.
    Geometric partial differential equations and image analysis.
    Cambridge Univ. Press, 2001. MR 1813971 (2002a:68142)
  • 47. Z. Shen.
    Wavelet frames and image restorations.
    Proceedings of the International Congress of Mathematicians, Hyderabad, India, 2010.
  • 48. Z. Shen, K. C. Toh, and S. Yun.
    An accelerated proximal gradient algorithm for frame based image restorations via the balanced approach.
    SIAM Journal on Imaging Sciences, 4(2):573-596, 2011. MR 2810898
  • 49. R.L. Siddon.
    Fast calculation of the exact radiological path for a three-dimensional CT array.
    Medical Physics, 12:252-255, 1985.
  • 50. J.L. Starck, M. Elad, and D.L. Donoho.
    Image decomposition via the combination of sparse representations and a variational approach.
    IEEE Transactions on Image Processing, 14(10):1570-1582, 2005. MR 2483314
  • 51. G. Steidl, J. Weickert, T. Brox, P. Mrázek, and M. Welk.
    On the equivalence of soft wavelet shrinkage, total variation diffusion, total variation regularization, and sides.
    SIAM Journal on Numerical Analysis, pages 686-713, 2005. MR 2084232 (2006d:94018)
  • 52. P. Tseng.
    Convergence of a block coordinate descent method for nondifferentiable minimization.
    Journal of optimization theory and applications, 109(3):475-494, 2001. MR 1835069 (2002b:90079)
  • 53. Y. Wang, J. Yang, W. Yin, and Y. Zhang.
    A new alternating minimization algorithm for total variation image reconstruction.
    SIAM Journal on Imaging Sciences, 1(3):248-272, 2008. MR 2486032 (2010e:68198)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 80M50, 90C26, 42C40, 68U10

Retrieve articles in all journals with MSC (2010): 80M50, 90C26, 42C40, 68U10

Additional Information

Yong Zhang
Affiliation: Department of Mathematics, Simon Fraser University, Burnaby, BC, V5A 1S6, Canada.

Bin Dong
Affiliation: Department of Mathematics, The University of Arizona, 617 N. Santa Rita Ave., Tucson, Arizona, 85721-0089

Zhaosong Lu
Affiliation: Department of Mathematics, Simon Fraser University, Burnaby, BC, V5A 1S6, Canada.

Keywords: $ℓ_{0}$ minimization, hard thresholding, wavelet frame, image restoration.
Received by editor(s): May 17, 2011
Received by editor(s) in revised form: September 2, 2011, and October 6, 2011
Published electronically: August 15, 2012
Additional Notes: The first and third authors were supported in part by NSERC Discovery Grant.
Article copyright: © Copyright 2012 American Mathematical Society

American Mathematical Society