Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)



Image restoration: Total variation, wavelet frames, and beyond

Authors: Jian-Feng Cai, Bin Dong, Stanley Osher and Zuowei Shen
Journal: J. Amer. Math. Soc. 25 (2012), 1033-1089
MSC (2010): Primary 35A15, 41A25, 42C40, 45Q05, 65K10, 68U10
Published electronically: May 17, 2012
MathSciNet review: 2947945
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The variational techniques (e.g. the total variation based method) are well established and effective for image restoration, as well as many other applications, while the wavelet frame based approach is relatively new and came from a different school. This paper is designed to establish a connection between these two major approaches for image restoration. The main result of this paper shows that when spline wavelet frames of are used, a special model of a wavelet frame method, called the analysis based approach, can be viewed as a discrete approximation at a given resolution to variational methods. A convergence analysis as image resolution increases is given in terms of objective functionals and their approximate minimizers. This analysis goes beyond the establishment of the connections between these two approaches, since it leads to new understandings for both approaches. First, it provides geometric interpretations to the wavelet frame based approach as well as its solutions. On the other hand, for any given variational model, wavelet frame based approaches provide various and flexible discretizations which immediately lead to fast numerical algorithms for both wavelet frame based approaches and the corresponding variational model. Furthermore, the built-in multiresolution structure of wavelet frames can be utilized to adaptively choose proper differential operators in different regions of a given image according to the order of the singularity of the underlying solutions. This is important when multiple orders of differential operators are used in various models that generalize the total variation based method. These observations will enable us to design new methods according to the problems at hand, hence, lead to wider applications of both the variational and wavelet frame based approaches. Links of wavelet frame based approaches to some more general variational methods developed recently will also be discussed.

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

  • 1. L. Rudin, S. Osher, and E. Fatemi, ``Nonlinear total variation based noise removal algorithms,'' Phys. D, vol. 60, pp. 259-268, 1992.
  • 2. A. Ron and Z. Shen, ``Affine Systems in $ L_2(\mathbb{R}^d)$: The Analysis of the Analysis Operator,'' Journal of Functional Analysis, vol. 148, no. 2, pp. 408-447, 1997. MR 1469348 (99g:42043)
  • 3. I. Ekeland and R. Temam, ``Convex analysis and variational problems,'' Classics in Applied Math., vol. 28, SIAM, 1999. MR 1727362 (2000j:49001)
  • 4. G. Dal Maso, Introduction to $ \Gamma $-convergence.
    Birkhäuser, 1993. MR 1201152 (94a:49001)
  • 5. Y. Meyer, Oscillating patterns in image processing and nonlinear evolution equations: the fifteenth Dean Jacqueline B. Lewis memorial lectures.
    American Mathematical Society, 2001. MR 1852741 (2002j:43001)
  • 6. B. Dong, A. Chien, and Z. Shen, ``Frame based segmentation for medical images,'' Communications in Mathematical Sciences, vol. 9(2), pp. 551-559, 2010. MR 2815684
  • 7. B. Dong and Z. Shen, ``Frame based surface reconstruction from unorganized points,'' Journal of Computational Physics, vol. 230, pp. 8247-8255, 2011. MR 2835419
  • 8. G. Sapiro, Geometric partial differential equations and image analysis.
    Cambridge Univ. Press, 2001. MR 1813971 (2002a:68142)
  • 9. S. Osher and R. Fedkiw, Level set methods and dynamic implicit surfaces.
    Springer, 2003. MR 1939127 (2003j:65002)
  • 10. A. Marquina and S. Osher, ``Explicit algorithms for a new time dependent model based on level set motion for nonlinear deblurring and noise removal,'' SIAM Journal on Scientific Computing, vol. 22, no. 4, pp. 387-405, 2000. MR 1780606 (2002d:65078)
  • 11. C. Vogel and M. Oman, ``Iterative methods for total variation denoising,'' SIAM Journal on Scientific Computing, vol. 17, no. 1, pp. 227-238, 1996. MR 1375276
  • 12. T. Chan, G. Golub, and P. Mulet, ``A nonlinear primal-dual method for total variation-based image restoration,'' SIAM Journal on Scientific Computing, vol. 20, no. 6, pp. 1964-1977, 1999. MR 1694649 (2000c:65038)
  • 13. A. Chambolle, ``An algorithm for total variation minimization and applications,'' Journal of Mathematical Imaging and Vision, vol. 20, no. 1, pp. 89-97, 2004. MR 2049783 (2005m:49058)
  • 14. M. Zhu and T. Chan, ``An efficient primal-dual hybrid gradient algorithm for total variation image restoration,'' Mathematics Department, UCLA, CAM Report, pp. 08-34, 2007.
  • 15. M. Zhu, S. Wright, and T. Chan, ``Duality-based algorithms for total variation image restoration,'' Mathematics Department, UCLA, CAM Report, pp. 08-33, 2008.
  • 16. M. Zhu, S. Wright, and T. Chan, ``Duality-based algorithms for total-variation-regularized image restoration,'' Computational Optimization and Applications, pp. 1-24, 2008.
  • 17. T. Pock, D. Cremers, H. Bischof, and A. Chambolle, ``An algorithm for minimizing the Mumford-Shah functional,'' in Computer Vision, 2009 IEEE 12th International Conference, pp. 1133-1140, IEEE, 2010.
  • 18. E. Esser, X. Zhang, and T. Chan, ``A general framework for a class of first order primal-dual algorithms for TV minimization,'' UCLA CAM Report, pp. 09-67, 2009.
  • 19. T. Goldstein and S. Osher, ``The split Bregman algorithm for L1 regularized problems,'' SIAM Journal on Imaging Sciences, vol. 2, no. 2, pp. 323-343, 2009. MR 2496060 (2010e:65087)
  • 20. L. Bregman, ``The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming,'' USSR Computational Mathematics and Mathematical Physics, vol. 7, no. 3, pp. 200-217, 1967. MR 0215617 (35:6457)
  • 21. J. Cai, S. Osher, and Z. Shen, ``Split Bregman methods and frame based image restoration,'' Multiscale Modeling and Simulation: A SIAM Interdisciplinary Journal, vol. 8, no. 2, pp. 337-369, 2009. MR 2581025 (2011a:94016)
  • 22. S. Setzer, ``Split Bregman algorithm, Douglas-Rachford splitting and frame shrinkage,'' Scale Space and Variational Methods in Computer Vision, pp. 464-476, 2009.
  • 23. E. Esser, ``Applications of Lagrangian-based alternating direction methods and connections to split Bregman,'' CAM Report, vol. 9-31, 2009.
  • 24. W. Ring, ``Structural properties of solutions to total variation regularization problems,'' Mathematical modelling and numerical analysis, vol. 34, no. 4, pp. 799-810, 2000. MR 1784486 (2001g:65077)
  • 25. M. Nikolova, ``Local strong homogeneity of a regularized estimator,'' SIAM Journal on Applied Mathematics, vol. 61, no. 2, pp. 633-658, 2000. MR 1780806 (2001g:94005)
  • 26. A. Chambolle and P. Lions, ``Image recovery via total variation minimization and related problems,'' Numerische Mathematik, vol. 76, no. 2, pp. 167-188, 1997. MR 1440119 (98c:65099)
  • 27. T. Chan, S. Esedoglu, and F. Park, ``Image decomposition combining staircase reduction and texture extraction,'' Journal of Visual Communication and Image Representation, vol. 18, no. 6, pp. 464-486, 2007.
  • 28. T. Chan, S. Esedoglu, and F. Park, ``A fourth order dual method for staircase reduction in texture extraction and image restoration problems,'' UCLA CAM Report, pp. 05-28, 2005.
  • 29. T. Chan, A. Marquina, and P. Mulet, ``High-order total variation-based image restoration,'' SIAM J. Sci. Comput., vol. 22, no. 2, pp. 503-516, 2001. MR 1780611 (2001j:94004)
  • 30. K. Bredies, K. Kunisch, and T. Pock, ``Total Generalized Variation,'' SIAM Journal on Imaging Sciences, vol. 3, pp. 492-526, 2010. MR 2736018 (2011k:49029)
  • 31. I. Daubechies, Ten lectures on wavelets, CBMS-NSF Lecture Notes, SIAM, nr. 61.
    Society for Industrial and Applied Mathematics, 1992. MR 1162107 (93e:42045)
  • 32. I. Daubechies, B. Han, A. Ron, and Z. Shen, ``Framelets: MRA-based constructions of wavelet frames,'' Applied and Computational Harmonic Analysis, vol. 14, pp. 1-46, 2003. MR 1971300 (2004a:42046)
  • 33. Z. Shen, ``Wavelet frames and image restorations,'' Proceedings of the International Congress of Mathematicians, Hyderabad, India, 2010. MR 2827995
  • 34. 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.
  • 35. A. Chai and Z. Shen, ``Deconvolution: A wavelet frame approach,'' Numerische Mathematik, vol. 106, no. 4, pp. 529-587, 2007. MR 2317925 (2008i:42067)
  • 36. R. Chan, T. Chan, L. Shen, and Z. Shen, ``Wavelet algorithms for high-resolution image reconstruction,'' SIAM Journal on Scientific Computing, vol. 24, no. 4, pp. 1408-1432, 2003. MR 1976222 (2004e:94003)
  • 37. R. Chan, S. Riemenschneider, L. Shen, and Z. Shen, ``Tight frame: an efficient way for high-resolution image reconstruction,'' Applied and Computational Harmonic Analysis, vol. 17, no. 1, pp. 91-115, 2004. MR 2067917 (2005h:94006)
  • 38. J. Cai, R. Chan, L. Shen, and Z. Shen, ``Restoration of chopped and nodded images by framelets,'' SIAM J. Sci. Comput, vol. 30, no. 3, pp. 1205-1227, 2008. MR 2398862 (2009d:42099)
  • 39. J. Cai, R. Chan, L. Shen, and Z. Shen, ``Convergence analysis of tight framelet approach for missing data recovery,'' Advances in Computational Mathematics, pp. 1-27, 2008.
  • 40. J. Cai, R. Chan, and Z. Shen, ``A framelet-based image inpainting algorithm,'' Applied and Computational Harmonic Analysis, vol. 24, no. 2, pp. 131-149, 2008. MR 2393979 (2009d:94010)
  • 41. J. Cai, R. Chan, and Z. Shen, ``Simultaneous cartoon and texture inpainting,'' Inverse Probl. Imaging, vol. 4, no. 3, pp. 379-395, 2010. MR 2671102 (2011k:94019)
  • 42. J. Cai and Z. Shen, ``Framelet based deconvolution,'' J. Comp. Math., vol. 28, no. 3, pp. 289-308, 2010. MR 2667297 (2011g:65315)
  • 43. R. Chan, Z. Shen, and T. Xia, ``A framelet algorithm for enhancing video stills,'' Applied and Computational Harmonic Analysis, vol. 23, no. 2, pp. 153-170, 2007. MR 2344608 (2008h:94006)
  • 44. S. Mallat, A wavelet tour of signal processing, 2nd ed., New York:
    Academic Press, 1999. MR 2479996 (2010g:94028)
  • 45. B. Han and Z. Shen, ``Dual wavelet frames and Riesz bases in Sobolev spaces,'' Constructive Approximation, vol. 29, no. 3, pp. 369-406, 2009. MR 2486376 (2009m:42065)
  • 46. I. Daubechies, G. Teschke, and L. Vese, ``Iteratively solving linear inverse problems under general convex constraints,'' Inverse Problems and Imaging, vol. 1, no. 1, pp. 29-46, 2007. MR 2262744 (2008e:35204)
  • 47. M. Fadili and J. Starck, ``Sparse representations and Bayesian image inpainting,'' Proc. SPARS, vol. 5, 2005.
  • 48. M. Fadili, J. Starck, and F. Murtagh, ``Inpainting and zooming using sparse representations,'' The Computer Journal, vol. 52, no. 1, p. 64, 2009.
  • 49. M. Figueiredo and R. Nowak, ``An EM algorithm for wavelet-based image restoration,'' IEEE Transactions on Image Processing, vol. 12, no. 8, pp. 906-916, 2003. MR 2008658
  • 50. M. Figueiredo and R. Nowak, ``A bound optimization approach to wavelet-based image deconvolution,'' in Image Processing, 2005. ICIP 2005. IEEE International Conference, vol. 2, pp. II-782, IEEE, 2005.
  • 51. M. Elad, J. Starck, P. Querre, and D. Donoho, ``Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA),'' Applied and Computational Harmonic Analysis, vol. 19, no. 3, pp. 340-358, 2005. MR 2186449 (2007h:94007)
  • 52. J. Starck, M. Elad, and D. Donoho, ``Image decomposition via the combination of sparse representations and a variational approach,'' IEEE transactions on image processing, vol. 14, no. 10, pp. 1570-1582, 2005. MR 2483314
  • 53. R. Jia, ``Spline wavelets on the interval with homogeneous boundary conditions,'' Advances in Computational Mathematics, vol. 30, no. 2, pp. 177-200, 2009. MR 2471447 (2009k:42073)
  • 54. R. Adams, Sobolev Spaces.
    Academic Press, New York, 1975. MR 0450957 (56:9247)
  • 55. A. Cohen, I. Daubechies, and J. Feauveau, ``Biorthogonal bases of compactly supported wavelets,'' Communications on Pure and Applied Mathematics, vol. 45, no. 5, pp. 485-560, 1992. MR 1162365 (93e:42044)
  • 56. Z. Shen and Z. Xu, ``On B-spline framelets derived from the unitary extension principle,'' Arxiv preprint arXiv:1112.5771, 2011.
  • 57. R. Jia, ``Approximation with scaled shift-invariant spaces by means of quasi-projection operators,'' Journal of Approximation Theory, vol. 131, no. 1, pp. 30-46, 2004. MR 2103832 (2005h:41035)
  • 58. R. Jia and C. Micchelli, ``Using the refinement equations for the construction of pre-wavelets II: Powers of two,'' Curves and surfaces, pp. 209-246, 1991. MR 1123739 (93e:65024)
  • 59. G. Folland, Real analysis.
    Wiley, New York, 1984. MR 767633 (86k:28001)
  • 60. S. Osher, M. Burger, D. Goldfarb, J. Xu, and W. Yin, ``An iterative regularization method for total variation-based image restoration,'' Multiscale Model. Simul., vol. 4, no. 2, pp. 460-489, 2005. MR 2162864 (2006c:49051)
  • 61. W. Yin, S. Osher, D. Goldfarb, and J. Darbon, ``Bregman iterative algorithms for $ l_1$-minimization with applications to compressed sensing,'' SIAM J. Imaging Sci., vol. 1, no. 1, pp. 143-168, 2008. MR 2475828 (2010f:90170)
  • 62. X. Zhang, M. Burger, X. Bresson, and S. Osher, ``Bregmanized nonlocal regularization for deconvolution and sparse reconstruction,'' SIAM Journal on Imaging Sciences, vol. 3, no. 3, pp. 253-276, 2010. MR 2679428 (2011m:65135)
  • 63. X. Tai and C. Wu, ``Augmented Lagrangian method, dual methods and split Bregman iteration for ROF model,'' Scale Space and Variational Methods in Computer Vision, pp. 502-513, 2009.
  • 64. R. Glowinski and P. Le Tallec, Augmented Lagrangian and operator-splitting methods in nonlinear mechanics.
    Society for Industrial and Applied Mathematics, vol. 9, 1989. MR 1060954 (91f:73038)
  • 65. D. Donoho, ``De-noising by soft-thresholding,'' IEEE Transactions on Information Theory, vol. 41, no. 3, pp. 613-627, 1995. MR 1331258 (96b:94002)
  • 66. P. Combettes and V. Wajs, ``Signal recovery by proximal forward-backward splitting,'' Multiscale Modeling and Simulation, vol. 4, no. 4, pp. 1168-1200, 2006. MR 2203849 (2007g:94016)
  • 67. P. Mrázek and J. Weickert, ``Rotationally invariant wavelet shrinkage,'' Pattern Recognition, pp. 156-163, 2003.
  • 68. Y. Wang, W. Yin, and Y. Zhang, ``A fast algorithm for image deblurring with total variation regularization,'' Rice University CAAM Technical Report TR07-10, 2007.
  • 69. R. Chan, S. Riemenschneider, L. Shen, and Z. Shen, ``High-resolution image reconstruction with displacement errors: A framelet approach,'' International Journal of Imaging Systems and Technology, vol. 14, no. 3, pp. 91-104, 2004.
  • 70. R. Coifman, Y. Meyer, and V. Wickerhauser, ``Wavelet analysis and signal processing,'' in Wavelets and their Applications, Jones and Bartlett, Boston, MA, 1992. MR 1187341
  • 71. R. Coifman and M. Wickerhauser, ``Entropy-based algorithms for best basis selection,'' Information Theory, IEEE Transactions, vol. 38, no. 2, pp. 713-718, 2002.
  • 72. S. Pan, ``Tight wavelet frame packets,'' Ph.D. thesis at National University of Singapore, 2011.

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2010): 35A15, 41A25, 42C40, 45Q05, 65K10, 68U10

Retrieve articles in all journals with MSC (2010): 35A15, 41A25, 42C40, 45Q05, 65K10, 68U10

Additional Information

Jian-Feng Cai
Affiliation: Department of Mathematics, The University of Iowa, Iowa City, Iowa 52242-1419

Bin Dong
Affiliation: Department of Mathematics, The University of Arizona, 617 North Santa Rita Avenue, Tucson, Arizona 85721-0089

Stanley Osher
Affiliation: Department of Mathematics, University of California, Los Angeles, 405 Hilgard Avenue, Los Angeles, California 90095-1555

Zuowei Shen
Affiliation: Department of Mathematics, National University of Singapore, Block S17, 10 Lower Kent Ridge Road, Singapore 119076

Keywords: Image restoration, total variation, variational method, (tight) wavelet frames, framelets, split Bregman, $Γ$-convergence, pointwise convergence.
Received by editor(s): April 3, 2011
Received by editor(s) in revised form: March 26, 2012
Published electronically: May 17, 2012
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society