Image restoration: Total variation, wavelet frames, and beyond

Cai, Jian-Feng¹ ; Dong, Bin² ; Osher, Stanley³ ; Shen, Zuowei⁴

¹ Department of Mathematics, The University of Iowa, Iowa City, Iowa 52242-1419
² Department of Mathematics, The University of Arizona, 617 North Santa Rita Avenue, Tucson, Arizona 85721-0089
³ Department of Mathematics, University of California, Los Angeles, 405 Hilgard Avenue, Los Angeles, California 90095-1555
⁴ Department of Mathematics, National University of Singapore, Block S17, 10 Lower Kent Ridge Road, Singapore 119076

Journal of the American Mathematical Society, Tome 25 (2012) no. 4, pp. 1033-1089

Résumé

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.

Détail

DOI : 10.1090/S0894-0347-2012-00740-1

Bibliographie

[1] Ron, Amos, Shen, Zuowei Affine systems in 𝐿₂(𝐑^{𝐝}): the analysis of the analysis operator J. Funct. Anal. 1997 408 447

[2] Ekeland, Ivar, Tã©Mam, Roger Convex analysis and variational problems 1999

[3] Dal Maso, Gianni An introduction to Γ-convergence 1993

[4] Meyer, Yves Oscillating patterns in image processing and nonlinear evolution equations 2001

[5] Dong, Bin, Chien, Aichi, Shen, Zuowei Frame based segmentation for medical images Commun. Math. Sci. 2011 551 559

[6] Dong, Bin, Shen, Zuowei Wavelet frame based surface reconstruction from unorganized points J. Comput. Phys. 2011 8247 8255

[7] Sapiro, Guillermo Geometric partial differential equations and image analysis 2001

[8] Osher, Stanley, Fedkiw, Ronald Level set methods and dynamic implicit surfaces 2003

[9] Marquina, Antonio, Osher, Stanley Explicit algorithms for a new time dependent model based on level set motion for nonlinear deblurring and noise removal SIAM J. Sci. Comput. 2000 387 405

[10] Vogel, C. R., Oman, M. E. Iterative methods for total variation denoising SIAM J. Sci. Comput. 1996 227 238

[11] Chan, Tony F., Golub, Gene H., Mulet, Pep A nonlinear primal-dual method for total variation-based image restoration SIAM J. Sci. Comput. 1999 1964 1977

[12] Chambolle, Antonin An algorithm for total variation minimization and applications J. Math. Imaging Vision 2004 89 97

[13] Goldstein, Tom, Osher, Stanley The split Bregman method for 𝐿1-regularized problems SIAM J. Imaging Sci. 2009 323 343

[14] Brã¨Gman, L. M. 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. 1967 620 631

[15] Cai, Jian-Feng, Osher, Stanley, Shen, Zuowei Split Bregman methods and frame based image restoration Multiscale Model. Simul. 2009/10 337 369

[16] Ring, Wolfgang Structural properties of solutions to total variation regularization problems M2AN Math. Model. Numer. Anal. 2000 799 810

[17] Nikolova, Mila Local strong homogeneity of a regularized estimator SIAM J. Appl. Math. 2000 633 658

[18] Chambolle, Antonin, Lions, Pierre-Louis Image recovery via total variation minimization and related problems Numer. Math. 1997 167 188

[19] Chan, Tony, Marquina, Antonio, Mulet, Pep High-order total variation-based image restoration SIAM J. Sci. Comput. 2000 503 516

[20] Bredies, Kristian, Kunisch, Karl, Pock, Thomas Total generalized variation SIAM J. Imaging Sci. 2010 492 526

[21] Daubechies, Ingrid Ten lectures on wavelets 1992

[22] Daubechies, Ingrid, Han, Bin, Ron, Amos, Shen, Zuowei Framelets: MRA-based constructions of wavelet frames Appl. Comput. Harmon. Anal. 2003 1 46

[23] Shen, Zuowei Wavelet frames and image restorations 2010 2834 2863

[24] Chai, Anwei, Shen, Zuowei Deconvolution: a wavelet frame approach Numer. Math. 2007 529 587

[25] Chan, Raymond H., Chan, Tony F., Shen, Lixin, Shen, Zuowei Wavelet algorithms for high-resolution image reconstruction SIAM J. Sci. Comput. 2003 1408 1432

[26] Chan, Raymond H., Riemenschneider, Sherman D., Shen, Lixin, Shen, Zuowei Tight frame: an efficient way for high-resolution image reconstruction Appl. Comput. Harmon. Anal. 2004 91 115

[27] Cai, Jian-Feng, Chan, Raymond, Shen, Lixin, Shen, Zuowei Restoration of chopped and nodded images by framelets SIAM J. Sci. Comput. 2008 1205 1227

[28] Cai, Jian-Feng, Chan, Raymond H., Shen, Zuowei A framelet-based image inpainting algorithm Appl. Comput. Harmon. Anal. 2008 131 149

[29] Cai, Jian-Feng, Chan, Raymond H., Shen, Zuowei Simultaneous cartoon and texture inpainting Inverse Probl. Imaging 2010 379 395

[30] Cai, Jian-Feng, Shen, Zuowei Framelet based deconvolution J. Comput. Math. 2010 289 308

[31] Chan, Raymond H., Shen, Zuowei, Xia, Tao A framelet algorithm for enhancing video stills Appl. Comput. Harmon. Anal. 2007 153 170

[32] Mallat, Stã©Phane A wavelet tour of signal processing 2009

[33] Han, Bin, Shen, Zuowei Dual wavelet frames and Riesz bases in Sobolev spaces Constr. Approx. 2009 369 406

[34] Daubechies, Ingrid, Teschke, Gerd, Vese, Luminita Iteratively solving linear inverse problems under general convex constraints Inverse Probl. Imaging 2007 29 46

[35] Figueiredo, Mã¡Rio A. T., Nowak, Robert D. An EM algorithm for wavelet-based image restoration IEEE Trans. Image Process. 2003 906 916

[36] Elad, M., Starck, J.-L., Querre, P., Donoho, D. L. Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA) Appl. Comput. Harmon. Anal. 2005 340 358

[37] Starck, Jean-Luc, Elad, Michael, Donoho, David L. Image decomposition via the combination of sparse representations and a variational approach IEEE Trans. Image Process. 2005 1570 1582

[38] Jia, Rong-Qing Spline wavelets on the interval with homogeneous boundary conditions Adv. Comput. Math. 2009 177 200

[39] Adams, Robert A. Sobolev spaces 1975

[40] Cohen, A., Daubechies, Ingrid, Feauveau, J.-C. Biorthogonal bases of compactly supported wavelets Comm. Pure Appl. Math. 1992 485 560

[41] Jia, Rong-Qing Approximation with scaled shift-invariant spaces by means of quasi-projection operators J. Approx. Theory 2004 30 46

[42] Jia, Rong Qing, Micchelli, Charles A. Using the refinement equations for the construction of pre-wavelets. II. Powers of two 1991 209 246

[43] Folland, Gerald B. Real analysis 1984

[44] Osher, Stanley, Burger, Martin, Goldfarb, Donald, Xu, Jinjun, Yin, Wotao An iterative regularization method for total variation-based image restoration Multiscale Model. Simul. 2005 460 489

[45] Yin, Wotao, Osher, Stanley, Goldfarb, Donald, Darbon, Jerome Bregman iterative algorithms for 𝑙₁-minimization with applications to compressed sensing SIAM J. Imaging Sci. 2008 143 168

[46] Zhang, Xiaoqun, Burger, Martin, Bresson, Xavier, Osher, Stanley Bregmanized nonlocal regularization for deconvolution and sparse reconstruction SIAM J. Imaging Sci. 2010 253 276

[47] Glowinski, Roland, Le Tallec, Patrick Augmented Lagrangian and operator-splitting methods in nonlinear mechanics 1989

[48] Donoho, David L. De-noising by soft-thresholding IEEE Trans. Inform. Theory 1995 613 627

[49] Combettes, Patrick L., Wajs, Valã©Rie R. Signal recovery by proximal forward-backward splitting Multiscale Model. Simul. 2005 1168 1200

[50] Coifman, Ronald R., Meyer, Yves, Wickerhauser, Victor Wavelet analysis and signal processing 1992 153 178