Image restoration: Total variation, wavelet frames, and beyond

Cai, Jian-Feng; Dong, Bin; Osher, Stanley; Shen, Zuowei

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

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.