Image restoration: Total variation, wavelet frames, and beyond
Tóm tắt
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.
Từ khóa
Tài liệu tham khảo
L. Rudin, S. Osher, and E. Fatemi, “Nonlinear total variation based noise removal algorithms,” Phys. D, vol. 60, pp. 259–268, 1992.
Ron, Amos, 1997, Affine systems in 𝐿₂(𝐑^{𝐝}): the analysis of the analysis operator, J. Funct. Anal., 148, 408, 10.1006/jfan.1996.3079
Meyer, Yves, 2001, Oscillating patterns in image processing and nonlinear evolution equations, 22, 10.1090/ulect/022
Dong, Bin, 2011, Frame based segmentation for medical images, Commun. Math. Sci., 9, 551, 10.4310/CMS.2011.v9.n2.a10
Dong, Bin, 2011, Wavelet frame based surface reconstruction from unorganized points, J. Comput. Phys., 230, 8247, 10.1016/j.jcp.2011.07.022
Sapiro, Guillermo, 2001, Geometric partial differential equations and image analysis, 10.1017/CBO9780511626319
Marquina, Antonio, 2000, Explicit algorithms for a new time dependent model based on level set motion for nonlinear deblurring and noise removal, SIAM J. Sci. Comput., 22, 387, 10.1137/S1064827599351751
Vogel, C. R., 1996, Iterative methods for total variation denoising, SIAM J. Sci. Comput., 17, 227, 10.1137/0917016
Chan, Tony F., 1999, A nonlinear primal-dual method for total variation-based image restoration, SIAM J. Sci. Comput., 20, 1964, 10.1137/S1064827596299767
Chambolle, Antonin, 2004, An algorithm for total variation minimization and applications, J. Math. Imaging Vision, 20, 89, 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.
Goldstein, Tom, 2009, The split Bregman method for 𝐿1-regularized problems, SIAM J. Imaging Sci., 2, 323, 10.1137/080725891
Brègman, L. M., 1967, A relaxation method of finding a common point of convex sets and its application to the solution of problems in convex programming, \v{Z}. Vy\v{c}isl. Mat i Mat. Fiz., 7, 620
Cai, Jian-Feng, 2009, Split Bregman methods and frame based image restoration, Multiscale Model. Simul., 8, 337, 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.
Ring, Wolfgang, 2000, Structural properties of solutions to total variation regularization problems, M2AN Math. Model. Numer. Anal., 34, 799, 10.1051/m2an:2000104
Nikolova, Mila, 2000, Local strong homogeneity of a regularized estimator, SIAM J. Appl. Math., 61, 633, 10.1137/S0036139997327794
Chambolle, Antonin, 1997, Image recovery via total variation minimization and related problems, Numer. Math., 76, 167, 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.
Chan, Tony, 2000, High-order total variation-based image restoration, SIAM J. Sci. Comput., 22, 503, 10.1137/S1064827598344169
Bredies, Kristian, 2010, Total generalized variation, SIAM J. Imaging Sci., 3, 492, 10.1137/090769521
Daubechies, Ingrid, 2003, Framelets: MRA-based constructions of wavelet frames, Appl. Comput. Harmon. Anal., 14, 1, 10.1016/S1063-5203(02)00511-0
Shen, Zuowei, 2010, Wavelet frames and image restorations, 2834
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.
Chai, Anwei, 2007, Deconvolution: a wavelet frame approach, Numer. Math., 106, 529, 10.1007/s00211-007-0075-0
Chan, Raymond H., 2003, Wavelet algorithms for high-resolution image reconstruction, SIAM J. Sci. Comput., 24, 1408, 10.1137/S1064827500383123
Chan, Raymond H., 2004, Tight frame: an efficient way for high-resolution image reconstruction, Appl. Comput. Harmon. Anal., 17, 91, 10.1016/j.acha.2004.02.003
Cai, Jian-Feng, 2008, Restoration of chopped and nodded images by framelets, SIAM J. Sci. Comput., 30, 1205, 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.
Cai, Jian-Feng, 2008, A framelet-based image inpainting algorithm, Appl. Comput. Harmon. Anal., 24, 131, 10.1016/j.acha.2007.10.002
Cai, Jian-Feng, 2010, Simultaneous cartoon and texture inpainting, Inverse Probl. Imaging, 4, 379, 10.3934/ipi.2010.4.379
Cai, Jian-Feng, 2010, Framelet based deconvolution, J. Comput. Math., 28, 289, 10.4208/jcm.2009.10-m1009
Chan, Raymond H., 2007, A framelet algorithm for enhancing video stills, Appl. Comput. Harmon. Anal., 23, 153, 10.1016/j.acha.2006.10.003
Mallat, Stéphane, 2009, A wavelet tour of signal processing, 3
Han, Bin, 2009, Dual wavelet frames and Riesz bases in Sobolev spaces, Constr. Approx., 29, 369, 10.1007/s00365-008-9027-x
Daubechies, Ingrid, 2007, Iteratively solving linear inverse problems under general convex constraints, Inverse Probl. Imaging, 1, 29, 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.
Figueiredo, Mário A. T., 2003, An EM algorithm for wavelet-based image restoration, IEEE Trans. Image Process., 12, 906, 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.
Elad, M., 2005, Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA), Appl. Comput. Harmon. Anal., 19, 340, 10.1016/j.acha.2005.03.005
Starck, Jean-Luc, 2005, Image decomposition via the combination of sparse representations and a variational approach, IEEE Trans. Image Process., 14, 1570, 10.1109/TIP.2005.852206
Jia, Rong-Qing, 2009, Spline wavelets on the interval with homogeneous boundary conditions, Adv. Comput. Math., 30, 177, 10.1007/s10444-008-9064-9
Adams, Robert A., 1975, Sobolev spaces
Cohen, A., 1992, Biorthogonal bases of compactly supported wavelets, Comm. Pure Appl. Math., 45, 485, 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.
Jia, Rong-Qing, 2004, Approximation with scaled shift-invariant spaces by means of quasi-projection operators, J. Approx. Theory, 131, 30, 10.1016/j.jat.2004.07.007
Jia, Rong Qing, 1991, Using the refinement equations for the construction of pre-wavelets. II. Powers of two, 209
Folland, Gerald B., 1984, Real analysis
Osher, Stanley, 2005, An iterative regularization method for total variation-based image restoration, Multiscale Model. Simul., 4, 460, 10.1137/040605412
Yin, Wotao, 2008, Bregman iterative algorithms for 𝑙₁-minimization with applications to compressed sensing, SIAM J. Imaging Sci., 1, 143, 10.1137/070703983
Zhang, Xiaoqun, 2010, Bregmanized nonlocal regularization for deconvolution and sparse reconstruction, SIAM J. Imaging Sci., 3, 253, 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.
Glowinski, Roland, 1989, Augmented Lagrangian and operator-splitting methods in nonlinear mechanics, 9, 10.1137/1.9781611970838
Donoho, David L., 1995, De-noising by soft-thresholding, IEEE Trans. Inform. Theory, 41, 613, 10.1109/18.382009
Combettes, Patrick L., 2005, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., 4, 1168, 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.
Coifman, Ronald R., 1992, Wavelet analysis and signal processing, 153
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.