×

Discrete total variation: new definition and minimization. (English) Zbl 1379.68330

Summary: We propose a new definition for the gradient field of a discrete image defined on a twice finer grid. The differentiation process from an image to its gradient field is viewed as the inverse operation of linear integration, and the proposed mapping is nonlinear. Then, we define the total variation of an image as the \(\ell_1\) norm of its gradient field amplitude. This new definition of the total variation yields sharp edges and has better isotropy than the classical definition.

MSC:

68U10 Computing methodologies for image processing
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory

Software:

UNLocBoX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] L. Rudin, S. Osher, and E. Fatemi, {\it Nonlinear total variation based noise removal algorithms}, Phys. D, 60 (1992), pp. 259-268. · Zbl 0780.49028
[2] A. Chambolle, V. Caselles, D. Cremers, M. Novaga, and T. Pock, {\it An introduction to total variation for image analysis}, in Theoretical Foundations and Numerical Methods for Sparse Recovery, Radon Ser. Comput. Appl. Math. 9, Walter de Gruyter, Berlin, 2010, pp. 263-340. · Zbl 1209.94004
[3] A. Chambolle and T. Pock, {\it A first-order primal-dual algorithm for convex problems with applications to imaging}, J. Math. Imaging Vision, 40 (2011), pp. 120-145. · Zbl 1255.68217
[4] M. Burger and S. Osher, {\it A guide to the TV zoo}, in Level Set and PDE Based Reconstruction Methods in Imaging, Lecture Notes in Math. 2090, Springer, Cham, Switzerland, 2013, pp. 1-70. · Zbl 1342.94014
[5] T. Goldstein, X. Bresson, and S. Osher, {\it Geometric applications of the split Bregman method: Segmentation and surface reconstruction}, J. Sci. Comput., 45 (2010), pp. 272-293. · Zbl 1203.65044
[6] A. Chambolle, D. Cremers, and T. Pock, {\it A convex approach to minimal partitions}, SIAM J. Imaging Sci., 5 (2012), pp. 1113-1158, . · Zbl 1256.49040
[7] C. Couprie, L. Grady, L. Najman, J.-C. Pesquet, and H. Talbot, {\it Dual constrained TV-based regularization on graphs}, SIAM J. Imaging Sci., 6 (2013), pp. 1246-1273, . · Zbl 1279.68323
[8] T. Goldstein and S. Osher, {\it The split Bregman method for L\textup1-regularized problems}, SIAM J. Imaging Sci., 2 (2009), pp. 323-343, . · Zbl 1177.65088
[9] M. K. Ng, P. Weiss, and X. Yuan, {\it Solving constrained total-variation image restoration and reconstruction problems via alternating direction methods}, SIAM J. Sci. Comput., 32 (2010), pp. 2710-2736, . · Zbl 1217.65071
[10] M. Afonso, J. Bioucas-Dias, and M. Figueiredo, {\it Fast image recovery using variable splitting and constrained optimization}, IEEE Trans. Image Process., 19 (2010), pp. 2345-2356. · Zbl 1371.94018
[11] P. L. Combettes, D. Du͂ng, and B. C. Vu͂, {\it Dualization of signal recovery problems}, Set-Valued Var. Anal., 18 (2010), pp. 373-404. · Zbl 1229.90123
[12] X. Zhang, M. Burger, and S. Osher, {\it A unified primal-dual algorithm framework based on Bregman iteration}, J. Sci. Comput., 46 (2011), pp. 20-46. · Zbl 1227.65052
[13] L. M. Bricen͂o-Arias and P. L. Combettes, {\it A monotone+skew splitting model for composite monotone inclusions in duality}, SIAM J. Optim., 21 (2011), pp. 1230-1250, . · Zbl 1239.47053
[14] L. M. Bricen͂o-Arias, P. L. Combettes, J.-C. Pesquet, and N. Pustelnik, {\it Proximal algorithms for multicomponent image recovery problems}, J. Math. Imaging Vision, 41 (2011), pp. 3-22. · Zbl 1255.68213
[15] P. L. Combettes, D. Du͂ng, and B. C. Vu͂, {\it Proximity for sums of composite functions}, J. Math. Anal. Appl., 380 (2011), pp. 680-688. · Zbl 1223.47120
[16] B. C. Vu͂, {\it A splitting algorithm for dual monotone inclusions involving cocoercive operators}, Adv. Comput. Math., 38 (2013), pp. 667-681. · Zbl 1284.47045
[17] L. Condat, {\it A generic proximal algorithm for convex optimization–Application to total variation minimization}, IEEE Signal Processing Lett., 21 (2014), pp. 1054-1057.
[18] P. L. Combettes, L. Condat, J.-C. Pesquet, and B. C. Vu͂, {\it A forward-backward view of some primal-dual optimization methods in image recovery}, in Proceedings of 21st International Conference on Signal Processing, Paris, France, 2014, pp. 49-52, .
[19] N. Komodakis and J.-C. Pesquet, {\it Playing with duality: An overview of recent primal-dual approaches for solving large-scale optimization problems}, IEEE Signal Processing Mag., 32 (2015), pp. 31-54.
[20] U. R. Alim, T. Möller, and L. Condat, {\it Gradient estimation revitalized}, IEEE Trans. Vis. Comput. Graph., 16 (2010), pp. 1494-1503.
[21] Z. Hossain, U. R. Alim, and T. Möller, {\it Towards high quality gradient estimation on regular lattices}, IEEE Trans. Vis. Comput. Graph., 17 (2011), pp. 426-439.
[22] A. Chambolle, S. E. Levine, and B. J. Lucier, {\it An upwind finite-difference method for total variation-based image smoothing}, SIAM J. Imaging Sci., 4 (2011), pp. 277-299, . · Zbl 1213.65030
[23] R. Abergel and L. Moisan, {\it The Shannon total variation}, J. Math. Imaging Vis., 2017, in press, . · Zbl 1382.94005
[24] D. Alleysson, S. Süsstrunk, and J. Hérault, {\it Linear demosaicing inspired by the human visual system}, IEEE Trans. Image Process., 14 (2005), pp. 439-449.
[25] L. Condat and S. Mosaddegh, {\it Joint demosaicking and denoising by total variation minimization}, in Proceedings of the 19th International Conference on Image Processing, Orlando, FL, 2012, pp. 2781-2784, .
[26] F. H. Harlow and J. E. Welch, {\it Numerical calculation of time-dependent viscous incompressible flow of fluid with free surface}, Phys. Fluids, 8 (1965), pp. 2182-2189. · Zbl 1180.76043
[27] P. B. Bochev and J. M. Hyman, {\it Principles of mimetic discretizations of differential operators}, in Compatible Spatial Discretizations, IMA Vol. Math. Appl. 142, Springer, New York, 2006, pp. 89-119. · Zbl 1110.65103
[28] C. Bazan, M. Abouali, J. Castillo, and P. Blomgren, {\it Mimetic finite difference methods in image processing}, Comput. Appl. Math., 30 (2011), pp. 701-720. · Zbl 1252.68328
[29] J. F. Garamendi, F. J. Gaspar, N. Malpica, and E. Schiavi, {\it Box relaxation schemes in staggered discretizations for the dual formulation of total variation minimization}, IEEE Trans. Image Process., 22 (2013), pp. 2030-2043. · Zbl 1373.94133
[30] M. Hintermüller, C. N. Rautenberg, and J. Hahn, {\it Functional-analytic and numerical issues in splitting methods for total variation-based image reconstruction}, Inverse Problems, 30 (2014), 055014. · Zbl 1293.94015
[31] H. H. Bauschke and P. L. Combettes, {\it Convex Analysis and Monotone Operator Theory in Hilbert Spaces}, Springer, New York, 2011. · Zbl 1218.47001
[32] L. Condat, {\it A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms}, J. Optim. Theory Appl., 158 (2013), pp. 460-479. · Zbl 1272.90110
[33] P. L. Combettes and J.-C. Pesquet, {\it Proximal splitting methods in signal processing}, in Fixed-Point Algorithms for Inverse Problems in Science and Engineering, Springer Optim. Appl. 49, H. H. Bauschke, R. Burachik, P. L. Combettes, V. Elser, D. R. Luke, and H. Wolkowicz, eds., Springer, New York, 2011, pp. 185-212. · Zbl 1242.90160
[34] S. Ma, {\it Alternating proximal gradient method for convex minimization}, J. Sci. Comput., 68 (2016), pp. 546-572. · Zbl 1371.65056
[35] W. Deng and W. Yin, {\it On the global and linear convergence of the generalized alternating direction method of multipliers}, J. Sci. Comput., 66 (2015), pp. 889-916. · Zbl 1379.65036
[36] P. Combettes and J.-C. Pesquet, {\it Image restoration subject to a total variation constraint}, IEEE Trans. Image Process., 13 (2004), pp. 1213-1222.
[37] J. M. Fadili and G. Peyré, {\it Total variation projection with first order schemes}, IEEE Trans. Image Process., 20 (2011), pp. 657-669. · Zbl 1372.94077
[38] W. Ring, {\it Structural properties of solutions to total variation regularization problems}, M2AN Math. Model. Numer. Anal., 34 (2000), pp. 799-810. · Zbl 1018.49021
[39] F. Alter, V. Caselles, and A. Chambolle, {\it Evolution of characteristic functions of convex sets in the plane by the minimizing total variation flow}, Interfaces Free Bound., 7 (2005), pp. 29-53. · Zbl 1084.49003
[40] W. K. Allard, {\it Total variation regularization for image denoising. I. Geometric theory}, SIAM J. Math. Anal., 39 (2008), pp. 1150-1190, . · Zbl 1185.49047
[41] L. Condat, {\it Fast projection onto the simplex and the l1 ball}, Math. Program., 158 (2016), pp. 575-585. · Zbl 1347.49050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.