Image restoration: Total variation, wavelet frames, and beyond
HTML articles powered by AMS MathViewer
- by Jian-Feng Cai, Bin Dong, Stanley Osher and Zuowei Shen
- J. Amer. Math. Soc. 25 (2012), 1033-1089
- DOI: https://doi.org/10.1090/S0894-0347-2012-00740-1
- Published electronically: May 17, 2012
- PDF | Request permission
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
- L. Rudin, S. Osher, and E. Fatemi, “Nonlinear total variation based noise removal algorithms,” Phys. D, vol. 60, pp. 259–268, 1992.
- Amos Ron and Zuowei Shen, Affine systems in $L_2(\mathbf R^d)$: the analysis of the analysis operator, J. Funct. Anal. 148 (1997), no. 2, 408–447. MR 1469348, DOI 10.1006/jfan.1996.3079
- Ivar Ekeland and Roger Témam, Convex analysis and variational problems, Corrected reprint of the 1976 English edition, Classics in Applied Mathematics, vol. 28, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. Translated from the French. MR 1727362, DOI 10.1137/1.9781611971088
- Gianni Dal Maso, An introduction to $\Gamma$-convergence, Progress in Nonlinear Differential Equations and their Applications, vol. 8, Birkhäuser Boston, Inc., Boston, MA, 1993. MR 1201152, DOI 10.1007/978-1-4612-0327-8
- Yves Meyer, Oscillating patterns in image processing and nonlinear evolution equations, University Lecture Series, vol. 22, American Mathematical Society, Providence, RI, 2001. The fifteenth Dean Jacqueline B. Lewis memorial lectures. MR 1852741, DOI 10.1090/ulect/022
- Bin Dong, Aichi Chien, and Zuowei Shen, Frame based segmentation for medical images, Commun. Math. Sci. 9 (2011), no. 2, 551–559. MR 2815684, DOI 10.4310/CMS.2011.v9.n2.a10
- Bin Dong and Zuowei Shen, Wavelet frame based surface reconstruction from unorganized points, J. Comput. Phys. 230 (2011), no. 22, 8247–8255. MR 2835419, DOI 10.1016/j.jcp.2011.07.022
- Guillermo Sapiro, Geometric partial differential equations and image analysis, Cambridge University Press, Cambridge, 2001. MR 1813971, DOI 10.1017/CBO9780511626319
- Stanley Osher and Ronald Fedkiw, Level set methods and dynamic implicit surfaces, Applied Mathematical Sciences, vol. 153, Springer-Verlag, New York, 2003. MR 1939127, DOI 10.1007/b98879
- Antonio Marquina and Stanley Osher, Explicit algorithms for a new time dependent model based on level set motion for nonlinear deblurring and noise removal, SIAM J. Sci. Comput. 22 (2000), no. 2, 387–405. MR 1780606, DOI 10.1137/S1064827599351751
- C. R. Vogel and M. E. Oman, Iterative methods for total variation denoising, SIAM J. Sci. Comput. 17 (1996), no. 1, 227–238. Special issue on iterative methods in numerical linear algebra (Breckenridge, CO, 1994). MR 1375276, DOI 10.1137/0917016
- Tony F. Chan, Gene H. Golub, and Pep Mulet, A nonlinear primal-dual method for total variation-based image restoration, SIAM J. Sci. Comput. 20 (1999), no. 6, 1964–1977. MR 1694649, DOI 10.1137/S1064827596299767
- Antonin Chambolle, An algorithm for total variation minimization and applications, J. Math. Imaging Vision 20 (2004), no. 1-2, 89–97. Special issue on mathematics and image analysis. MR 2049783, DOI 10.1023/B:JMIV.0000011320.81911.38
- 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.
- M. Zhu, S. Wright, and T. Chan, “Duality-based algorithms for total variation image restoration,” Mathematics Department, UCLA, CAM Report, pp. 08–33, 2008.
- M. Zhu, S. Wright, and T. Chan, “Duality-based algorithms for total-variation-regularized image restoration,” Computational Optimization and Applications, pp. 1–24, 2008.
- 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.
- 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.
- Tom Goldstein and Stanley Osher, The split Bregman method for $L1$-regularized problems, SIAM J. Imaging Sci. 2 (2009), no. 2, 323–343. MR 2496060, DOI 10.1137/080725891
- L. M. Brègman, A relaxation method of finding a common point of convex sets and its application to the solution of problems in convex programming, Ž. Vyčisl. Mat i Mat. Fiz. 7 (1967), 620–631 (Russian). MR 215617
- Jian-Feng Cai, Stanley Osher, and Zuowei Shen, Split Bregman methods and frame based image restoration, Multiscale Model. Simul. 8 (2009/10), no. 2, 337–369. MR 2581025, DOI 10.1137/090753504
- S. Setzer, “Split Bregman algorithm, Douglas-Rachford splitting and frame shrinkage,” Scale Space and Variational Methods in Computer Vision, pp. 464–476, 2009.
- E. Esser, “Applications of Lagrangian-based alternating direction methods and connections to split Bregman,” CAM Report, vol. 9-31, 2009.
- Wolfgang Ring, Structural properties of solutions to total variation regularization problems, M2AN Math. Model. Numer. Anal. 34 (2000), no. 4, 799–810. MR 1784486, DOI 10.1051/m2an:2000104
- Mila Nikolova, Local strong homogeneity of a regularized estimator, SIAM J. Appl. Math. 61 (2000), no. 2, 633–658. MR 1780806, DOI 10.1137/S0036139997327794
- Antonin Chambolle and Pierre-Louis Lions, Image recovery via total variation minimization and related problems, Numer. Math. 76 (1997), no. 2, 167–188. MR 1440119, DOI 10.1007/s002110050258
- 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.
- 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.
- Tony Chan, Antonio Marquina, and Pep Mulet, High-order total variation-based image restoration, SIAM J. Sci. Comput. 22 (2000), no. 2, 503–516. MR 1780611, DOI 10.1137/S1064827598344169
- Kristian Bredies, Karl Kunisch, and Thomas Pock, Total generalized variation, SIAM J. Imaging Sci. 3 (2010), no. 3, 492–526. MR 2736018, DOI 10.1137/090769521
- Ingrid Daubechies, Ten lectures on wavelets, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 61, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1162107, DOI 10.1137/1.9781611970104
- Ingrid Daubechies, Bin Han, Amos Ron, and Zuowei Shen, Framelets: MRA-based constructions of wavelet frames, Appl. Comput. Harmon. Anal. 14 (2003), no. 1, 1–46. MR 1971300, DOI 10.1016/S1063-5203(02)00511-0
- Zuowei Shen, Wavelet frames and image restorations, Proceedings of the International Congress of Mathematicians. Volume IV, Hindustan Book Agency, New Delhi, 2010, pp. 2834–2863. MR 2827995
- 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.
- Anwei Chai and Zuowei Shen, Deconvolution: a wavelet frame approach, Numer. Math. 106 (2007), no. 4, 529–587. MR 2317925, DOI 10.1007/s00211-007-0075-0
- Raymond H. Chan, Tony F. Chan, Lixin Shen, and Zuowei Shen, Wavelet algorithms for high-resolution image reconstruction, SIAM J. Sci. Comput. 24 (2003), no. 4, 1408–1432. MR 1976222, DOI 10.1137/S1064827500383123
- Raymond H. Chan, Sherman D. Riemenschneider, Lixin Shen, and Zuowei Shen, Tight frame: an efficient way for high-resolution image reconstruction, Appl. Comput. Harmon. Anal. 17 (2004), no. 1, 91–115. MR 2067917, DOI 10.1016/j.acha.2004.02.003
- Jian-Feng Cai, Raymond Chan, Lixin Shen, and Zuowei Shen, Restoration of chopped and nodded images by framelets, SIAM J. Sci. Comput. 30 (2008), no. 3, 1205–1227. MR 2398862, DOI 10.1137/040615298
- 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.
- Jian-Feng Cai, Raymond H. Chan, and Zuowei Shen, A framelet-based image inpainting algorithm, Appl. Comput. Harmon. Anal. 24 (2008), no. 2, 131–149. MR 2393979, DOI 10.1016/j.acha.2007.10.002
- Jian-Feng Cai, Raymond H. Chan, and Zuowei Shen, Simultaneous cartoon and texture inpainting, Inverse Probl. Imaging 4 (2010), no. 3, 379–395. MR 2671102, DOI 10.3934/ipi.2010.4.379
- Jian-Feng Cai and Zuowei Shen, Framelet based deconvolution, J. Comput. Math. 28 (2010), no. 3, 289–308. MR 2667297, DOI 10.4208/jcm.2009.10-m1009
- Raymond H. Chan, Zuowei Shen, and Tao Xia, A framelet algorithm for enhancing video stills, Appl. Comput. Harmon. Anal. 23 (2007), no. 2, 153–170. MR 2344608, DOI 10.1016/j.acha.2006.10.003
- Stéphane Mallat, A wavelet tour of signal processing, 3rd ed., Elsevier/Academic Press, Amsterdam, 2009. The sparse way; With contributions from Gabriel Peyré. MR 2479996
- Bin Han and Zuowei Shen, Dual wavelet frames and Riesz bases in Sobolev spaces, Constr. Approx. 29 (2009), no. 3, 369–406. MR 2486376, DOI 10.1007/s00365-008-9027-x
- Ingrid Daubechies, Gerd Teschke, and Luminita Vese, Iteratively solving linear inverse problems under general convex constraints, Inverse Probl. Imaging 1 (2007), no. 1, 29–46. MR 2262744, DOI 10.3934/ipi.2007.1.29
- M. Fadili and J. Starck, “Sparse representations and Bayesian image inpainting,” Proc. SPARS, vol. 5, 2005.
- M. Fadili, J. Starck, and F. Murtagh, “Inpainting and zooming using sparse representations,” The Computer Journal, vol. 52, no. 1, p. 64, 2009.
- Mário A. T. Figueiredo and Robert D. Nowak, An EM algorithm for wavelet-based image restoration, IEEE Trans. Image Process. 12 (2003), no. 8, 906–916. MR 2008658, DOI 10.1109/TIP.2003.814255
- 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.
- M. Elad, J.-L. Starck, P. Querre, and D. L. Donoho, Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA), Appl. Comput. Harmon. Anal. 19 (2005), no. 3, 340–358. MR 2186449, DOI 10.1016/j.acha.2005.03.005
- Jean-Luc Starck, Michael Elad, and David L. Donoho, Image decomposition via the combination of sparse representations and a variational approach, IEEE Trans. Image Process. 14 (2005), no. 10, 1570–1582. MR 2483314, DOI 10.1109/TIP.2005.852206
- Rong-Qing Jia, Spline wavelets on the interval with homogeneous boundary conditions, Adv. Comput. Math. 30 (2009), no. 2, 177–200. MR 2471447, DOI 10.1007/s10444-008-9064-9
- Robert A. Adams, Sobolev spaces, Pure and Applied Mathematics, Vol. 65, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1975. MR 0450957
- A. Cohen, Ingrid Daubechies, and J.-C. Feauveau, Biorthogonal bases of compactly supported wavelets, Comm. Pure Appl. Math. 45 (1992), no. 5, 485–560. MR 1162365, DOI 10.1002/cpa.3160450502
- Z. Shen and Z. Xu, “On B-spline framelets derived from the unitary extension principle,” Arxiv preprint arXiv:1112.5771, 2011.
- Rong-Qing Jia, Approximation with scaled shift-invariant spaces by means of quasi-projection operators, J. Approx. Theory 131 (2004), no. 1, 30–46. MR 2103832, DOI 10.1016/j.jat.2004.07.007
- Rong Qing Jia and Charles A. Micchelli, Using the refinement equations for the construction of pre-wavelets. II. Powers of two, Curves and surfaces (Chamonix-Mont-Blanc, 1990) Academic Press, Boston, MA, 1991, pp. 209–246. MR 1123739
- Gerald B. Folland, Real analysis, Pure and Applied Mathematics (New York), John Wiley & Sons, Inc., New York, 1984. Modern techniques and their applications; A Wiley-Interscience Publication. MR 767633
- Stanley Osher, Martin Burger, Donald Goldfarb, Jinjun Xu, and Wotao Yin, An iterative regularization method for total variation-based image restoration, Multiscale Model. Simul. 4 (2005), no. 2, 460–489. MR 2162864, DOI 10.1137/040605412
- Wotao Yin, Stanley Osher, Donald Goldfarb, and Jerome Darbon, Bregman iterative algorithms for $l_1$-minimization with applications to compressed sensing, SIAM J. Imaging Sci. 1 (2008), no. 1, 143–168. MR 2475828, DOI 10.1137/070703983
- Xiaoqun Zhang, Martin Burger, Xavier Bresson, and Stanley Osher, Bregmanized nonlocal regularization for deconvolution and sparse reconstruction, SIAM J. Imaging Sci. 3 (2010), no. 3, 253–276. MR 2679428, DOI 10.1137/090746379
- 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.
- Roland Glowinski and Patrick Le Tallec, Augmented Lagrangian and operator-splitting methods in nonlinear mechanics, SIAM Studies in Applied Mathematics, vol. 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1989. MR 1060954, DOI 10.1137/1.9781611970838
- David L. Donoho, De-noising by soft-thresholding, IEEE Trans. Inform. Theory 41 (1995), no. 3, 613–627. MR 1331258, DOI 10.1109/18.382009
- Patrick L. Combettes and Valérie R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul. 4 (2005), no. 4, 1168–1200. MR 2203849, DOI 10.1137/050626090
- P. Mrázek and J. Weickert, “Rotationally invariant wavelet shrinkage,” Pattern Recognition, pp. 156–163, 2003.
- 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.
- 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.
- Ronald R. Coifman, Yves Meyer, and Victor Wickerhauser, Wavelet analysis and signal processing, Wavelets and their applications, Jones and Bartlett, Boston, MA, 1992, pp. 153–178. MR 1187341
- R. Coifman and M. Wickerhauser, “Entropy-based algorithms for best basis selection,” Information Theory, IEEE Transactions, vol. 38, no. 2, pp. 713–718, 2002.
- S. Pan, “Tight wavelet frame packets,” Ph.D. thesis at National University of Singapore, 2011.
Bibliographic Information
- Jian-Feng Cai
- Affiliation: Department of Mathematics, The University of Iowa, Iowa City, Iowa 52242-1419
- Email: jianfeng-cai@uiowa.edu
- Bin Dong
- Affiliation: Department of Mathematics, The University of Arizona, 617 North Santa Rita Avenue, Tucson, Arizona 85721-0089
- Email: dongbin@math.arizona.edu
- Stanley Osher
- Affiliation: Department of Mathematics, University of California, Los Angeles, 405 Hilgard Avenue, Los Angeles, California 90095-1555
- Email: sjo@math.ucla.edu
- Zuowei Shen
- Affiliation: Department of Mathematics, National University of Singapore, Block S17, 10 Lower Kent Ridge Road, Singapore 119076
- MR Author ID: 292105
- Email: matzuows@nus.edu.sg
- Received by editor(s): April 3, 2011
- Received by editor(s) in revised form: March 26, 2012
- Published electronically: May 17, 2012
- © Copyright 2012
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: J. Amer. Math. Soc. 25 (2012), 1033-1089
- MSC (2010): Primary 35A15, 41A25, 42C40, 45Q05, 65K10, 68U10
- DOI: https://doi.org/10.1090/S0894-0347-2012-00740-1
- MathSciNet review: 2947945