Invariant \(\varphi \)-minimal sets and total variation denoising on graphs. (English) Zbl 1439.49066
Based on some recent results regarding invariant \(\varphi\)-minimal sets, the minimizer associated with the corresponding Rudin-Osher-Fatemi (ROF) model on the graph is investigated. More precisely, it is established that it has the same universal minimality property as in the one-dimensional setting. However, if \(J\) is replaced by the discrete isotropic total variation, this property is lost. Moreover, the ROF minimizer is related with the solution of the gradient flow for \(J\). Some conditions for equivalence between these two problems are formulated.
Reviewer: Savin Treanta (Bucharest)
MSC:
| 49N45 | Inverse problems in optimal control |
| 68U10 | Computing methodologies for image processing |
| 46N10 | Applications of functional analysis in optimization, convex analysis, mathematical programming, economics |
Keywords:
denoising; taut string; invariant \(\varphi \)-minimal sets; Rudin-Osher-Fatemi model; total variation flowReferences:
| [1] | F. Andreu, V. Caselles, J. I. Díaz, and J. M. Mazón, Some qualitative properties for the total variation flow, J. Funct. Anal., 188 (2002), pp. 516-547, https://doi.org/10.1006/jfan.2001.3829. · Zbl 1042.35018 |
| [2] | J.-F. Aujol, G. Aubert, L. Blanc-Féraud, and A. Chambolle, Image decomposition into a bounded variation component and an oscillating component, J. Math. Imaging Vision, 22 (2005), pp. 71-88, https://doi.org/10.1007/s10851-005-4783-8. · Zbl 1371.94031 |
| [3] | J.-F. Aujol, G. Gilboa, T. Chan, and S. Osher, Structure-texture image decomposition–modeling, algorithms, and parameter selection, Int. J. Comput. Vis., 67 (2006), pp. 111-136, https://doi.org/10.1007/s11263-006-4331-z. · Zbl 1287.94011 |
| [4] | F. Bach, Learning with submodular functions: A convex optimization perspective, Found. Trends Machine Learning, 6 (2013), pp. 145-373, https://doi.org/10.1561/2200000039. · Zbl 1280.68001 |
| [5] | V. Barbu, Nonlinear Differential Equations of Monotone Types in Banach Spaces, Springer Monogr. Math., Springer, New York, 2010, https://doi.org/10.1007/978-1-4419-5542-5. · Zbl 1197.35002 |
| [6] | G. Bellettini, V. Caselles, and M. Novaga, The total variation flow in \(\mathbb R\sp N\), J. Differential Equations, 184 (2002), pp. 475-525, https://doi.org/10.1006/jdeq.2001.4150. · Zbl 1036.35099 |
| [7] | M. Benning and M. Burger, Ground states and singular vectors of convex variational regularization methods, Methods Appl. Anal., 20 (2013), pp. 295-334, https://doi.org/10.4310/MAA.2013.v20.n4.a1. · Zbl 1294.49020 |
| [8] | B. Berkels, M. Burger, M. Droske, O. Nemitz, and M. Rumpf, Cartoon extraction based on anisotropic image classification, in Vision, Modeling, and Visualization Proceedings, 2006, pp. 293-300. |
| [9] | M. Burger, G. Gilboa, M. Moeller, L. Eckardt, and D. Cremers, Spectral decompositions using one-homogeneous functionals, SIAM J. Imaging Sci., 9 (2016), pp. 1374-1408, https://doi.org/10.1137/15M1054687. · Zbl 1361.35123 |
| [10] | V. Caselles, A. Chambolle, and M. Novaga, The discontinuity set of solutions of the TV denoising problem and some extensions, Multiscale Model. Simul., 6 (2007), pp. 879-894, https://doi.org/10.1137/070683003. · Zbl 1145.49024 |
| [11] | A. Chambolle, An algorithm for total variation minimization and applications, J. Math. Imaging Vision, 20 (2004), pp. 89-97, https://doi.org/10.1023/B:JMIV.0000011325.36760.1e. · Zbl 1366.94048 |
| [12] | A. Chambolle, Total variation minimization and a class of binary MRF models, in Energy Minimization Methods in Computer Vision and Pattern Recognition, A. Rangarajan, B. Vemuri, and A. L. Yuille, eds., Lecture Notes Comput. Vision 3757, Springer, Berlin, 2005, pp. 136-152, https://doi.org/10.1007/11585978_10. |
| [13] | A. Chambolle and J. Darbon, On total variation minimization and surface evolution using parametric maximum flows, Int. J. Comput. Vis., 84 (2009), pp. 288-307, https://doi.org/10.1007/s11263-009-0238-9. · Zbl 1371.94073 |
| [14] | G. Chartrand, L. Lesniak, and P. Zhang, Graphs & Digraphs, Chapman and Hall/CRC, Boca Raton, FL, 2010. |
| [15] | R. Choksi, Y. van Gennip, and A. Oberman, Anisotropic total variation regularized \(L^1\) approximation and denoising/deblurring of \(2\) D bar codes, Inverse Problems Imaging, 5 (2011), pp. 591-617, https://doi.org/10.3934/ipi.2011.5.591. · Zbl 1226.49034 |
| [16] | J. Darbon and M. Sigelle, Image restoration with discrete constrained total variation. Part I: Fast and exact optimization, J. Math. Imaging Vision, 26 (2006), pp. 261-276, https://doi.org/10.1007/s10851-006-8803-0. · Zbl 1478.94026 |
| [17] | I. Ekeland and R. Temam, Convex Analysis and Variational Problems, North-Holland, Amsterdam, 1976. · Zbl 0322.90046 |
| [18] | S. Fujishige, Submodular Functions and Optimization, 2nd ed., Ann. Discrete Math. 58, Elsevier, Amsterdam, 2005. · Zbl 1119.90044 |
| [19] | G. Gilboa, A total variation spectral framework for scale and texture analysis, SIAM J. Imaging Sci., 7 (2014), pp. 1937-1961, https://doi.org/10.1137/130930704. · Zbl 1361.94014 |
| [20] | M. Grasmair, The equivalence of the taut string algorithm and BV-regularization, J. Math. Imaging Vision, 27 (2007), pp. 59-66, https://doi.org/10.1007/s10851-006-9796-4. · Zbl 1478.94041 |
| [21] | M. Grasmair and A. Obereder, Generalizations of the taut string method, Numer. Funct. Anal. Optim., 29 (2008), pp. 346-361, https://doi.org/10.1080/01630560801998211. · Zbl 1142.65013 |
| [22] | B. Grünbaum, Convex Polytopes, Pure Appl. Math. 16, Wiley, London, 1967. · Zbl 0163.16603 |
| [23] | W. Hinterberger, M. Hintermüller, K. Kunisch, M. von Oehsen, and O. Scherzer, Tube methods for BV regularization, J. Math. Imaging Vision, 19 (2003), pp. 219-235, https://doi.org/10.1023/A:1026276804745. · Zbl 1101.68927 |
| [24] | D. S. Hochbaum, An efficient algorithm for image segmentation, Markov random fields and related problems, J. ACM, 48 (2001), pp. 686-701, https://doi.org/10.1145/502090.502093. · Zbl 1127.68474 |
| [25] | K. Jalalzai, Some remarks on the staircasing phenomenon in total variation-based image denoising, J. Math. Imaging Vision, 54 (2016), pp. 256-268, https://doi.org/10.1007/s10851-015-0600-1. · Zbl 1338.94008 |
| [26] | N. Kruglyak and E. Setterqvist, Discrete taut strings and real interpolation, J. Funct. Anal., 270 (2016), pp. 671-704, https://doi.org/10.1016/j.jfa.2015.10.012. · Zbl 1390.46022 |
| [27] | N. Kruglyak and E. Setterqvist, Invariant \({K} \)-minimal sets in the discrete and continuous settings, J. Fourier Anal. Appl., 23 (2017), pp. 672-711, https://doi.org/10.1007/s00041-016-9479-5. · Zbl 1379.46021 |
| [28] | M. Łasica, S. Moll, and P. B. Mucha, Total variation denoising in \(\ell^1\) anisotropy, SIAM J. Imaging Sci., 10 (2017), pp. 1691-1723, https://doi.org/10.1137/16M1103610. · Zbl 1451.94011 |
| [29] | E. Mammen and S. van de Geer, Locally adaptive regression splines, Ann. Statist., 25 (1997), pp. 387-413, https://doi.org/10.1214/aos/1034276635. · Zbl 0871.62040 |
| [30] | F. Modigliani and F. E. Hohn, Production planning over time and the nature of the expectation and planning horizon, Econometrica, 23 (1955), pp. 46-66, https://doi.org/10.2307/1905580. · Zbl 0064.39504 |
| [31] | L. Rudin, S. Osher, and E. Fatemi, Nonlinear total variation based noise removal algorithms, Phys. D, 60 (1992), pp. 259-268, https://doi.org/10.1016/0167-2789(92)90242-F. · Zbl 0780.49028 |
| [32] | J. D. Salehi, Z.-L. Zhang, J. Kurose, and D. Towsley, Supporting stored video: Reducing rate variability and end-to-end resource requirements through optimal smoothing, IEEE/ACM Trans. Networking, 6 (1998), pp. 397-410, https://doi.org/10.1109/90.720873. |
| [33] | S. J. Sanabria, E. Ozkan, M. Rominger, and O. Goksel, Spatial domain reconstruction for imaging speed-of-sound with pulse-echo ultrasound: Simulation and in vivo study, Phys. Med. Biol., 63 (2018), 215015, https://doi.org/10.1088/1361-6560/aae2fb. |
| [34] | F. Santambrogio, \Euclidean, metric, and Wassersteingradient flows: An overview, Bull. Math. Sci., 7 (2017), pp. 87-154, https://doi.org/10.1007/s13373-017-0101-1. · Zbl 1369.34084 |
| [35] | O. Scherzer, M. Grasmair, H. Grossauer, M. Haltmeier, and F. Lenzen, Variational Methods in Imaging, Applied Mathematical Sciences, 167, Springer, New York, 2009, https://doi.org/10.1007/978-0-387-69277-7. · Zbl 1177.68245 |
| [36] | S. Setzer, G. Steidl, and T. Teuber, Restoration of images with rotated shapes, Numer. Algorithms, 48 (2008), pp. 49-66, https://doi.org/10.1007/s11075-008-9182-y. · Zbl 1151.94320 |
| [37] | G. Steidl, J. Weickert, T. Brox, P. Mrázek, and M. Welk, On the equivalence of soft wavelet shrinkage, total variation diffusion, total variation regularization, and SIDEs, SIAM J. Numer. Anal., 42 (2004), pp. 686-713, https://doi.org/10.1137/S0036142903422429. · Zbl 1083.94001 |
| [38] | J. Yang and S. Ulukus, Optimal packet scheduling in an energy harvesting communication system, IEEE Trans. Commun., 60 (2012), pp. 220-230, https://doi.org/10.1109/TCOMM.2011.112811.100349. |
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.
