A posteriori error control for the binary Mumford-Shah model

Berkels, Benjamin; Effland, Alexander; Rumpf, Martin

doi:10.1090/mcom/3138

A posteriori error control for the binary Mumford-Shah model
HTML articles powered by AMS MathViewer

by Benjamin Berkels, Alexander Effland and Martin Rumpf PDF

Math. Comp. 86 (2017), 1769-1791 Request permission

Abstract:

The binary Mumford-Shah model is a widespread tool for image segmentation and can be considered as a basic model in shape optimization with a broad range of applications in computer vision, ranging from basic segmentation and labeling to object reconstruction. This paper presents robust a posteriori error estimates for a natural error quantity, namely the area of the non-properly segmented region. To this end, a suitable uniformly convex and non-constrained relaxation of the originally non-convex functional is investigated and Repin’s functional approach for a posteriori error estimation is used to control the numerical error for the relaxed problem in the $L^2$-norm. In combination with a suitable cut out argument, fully practical estimates for the area mismatch are derived. This estimate is incorporated in an adaptive mesh refinement strategy. Two different adaptive primal-dual finite element schemes, a dual gradient descent scheme, and the most frequently used finite difference discretization are investigated and compared. Numerical experiments show qualitative and quantitative properties of the estimates and demonstrate their usefulness in practical applications.

References

Giovanni Alberti, Guy Bouchitté, and Gianni Dal Maso, The calibration method for the Mumford-Shah functional and free-discontinuity problems, Calc. Var. Partial Differential Equations 16 (2003), no. 3, 299–333. MR 2001706, DOI 10.1007/s005260100152
Luigi Ambrosio, Variational problems in $\textrm {SBV}$ and image segmentation, Acta Appl. Math. 17 (1989), no. 1, 1–40. MR 1029833, DOI 10.1007/BF00052492
Luigi Ambrosio and V. M. Tortorelli, On the approximation of free discontinuity problems, Boll. Un. Mat. Ital. B (7) 6 (1992), no. 1, 105–123 (English, with Italian summary). MR 1164940
Luigi Ambrosio, Nicola Fusco, and Diego Pallara, Functions of bounded variation and free discontinuity problems, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 2000. MR 1857292
Sören Bartels, Error control and adaptivity for a variational model problem defined on functions of bounded variation, Math. Comp. 84 (2015), no. 293, 1217–1240. MR 3315506, DOI 10.1090/S0025-5718-2014-02893-7
Sören Bartels, Broken Sobolev space iteration for total variation regularized minimization problems, IMA J. Numer. Anal. 36 (2016), no. 2, 493–502. MR 3483094, DOI 10.1093/imanum/drv023
B. Berkels, An unconstrained multiphase thresholding approach for image segmentation, Proceedings of the Second International Conference on Scale Space Methods and Variational Methods in Computer Vision (SSVM 2009), Lecture Notes in Computer Science, vol. 5567, Springer, 2009, pp. 26–37.
B. Berkels, Joint methods in imaging based on diffuse image representations, Dissertation, University of Bonn, 2010.
Blaise Bourdin and Antonin Chambolle, Implementation of an adaptive finite-element approximation of the Mumford-Shah functional, Numer. Math. 85 (2000), no. 4, 609–646. MR 1771782, DOI 10.1007/PL00005394
S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning 3 (2010), 1–122.
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
Paul H. Calamai and Jorge J. Moré, Projected gradient methods for linearly constrained problems, Math. Programming 39 (1987), no. 1, 93–116. MR 909010, DOI 10.1007/BF02592073
Antonin Chambolle, Image segmentation by variational methods: Mumford and Shah functional and the discrete approximations, SIAM J. Appl. Math. 55 (1995), no. 3, 827–863. MR 1331589, DOI 10.1137/S0036139993257132
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
A. Chambolle, Total variation minimization and a class of binary MRF models, Energy Minimization Methods in Computer Vision and Pattern Recognition (A. Rangarajan et al., eds.), Lecture Notes in Computer Science, vol. 3757, Springer, 2005, pp. 136–152.
A. Chambolle, D. Cremers, and T. Pock, A convex approach for computing minimal partitions, Tech. Report 649, École Polytechnique, Centre de Mathématiques Appliquées, UMR CNRS 7641, November 2008.
Antonin Chambolle, Daniel Cremers, and Thomas Pock, A convex approach to minimal partitions, SIAM J. Imaging Sci. 5 (2012), no. 4, 1113–1158. MR 3022190, DOI 10.1137/110856733
Antonin Chambolle and Gianni Dal Maso, Discrete approximation of the Mumford-Shah functional in dimension two, M2AN Math. Model. Numer. Anal. 33 (1999), no. 4, 651–672 (English, with English and French summaries). MR 1726478, DOI 10.1051/m2an:1999156
A. Chambolle and J. Darbon, On total variation minimization and surface evolution using parametric maximum flows, International Journal of Computer Vision 84 (2009), no. 3, 288–307.
Antonin Chambolle and Thomas Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision 40 (2011), no. 1, 120–145. MR 2782122, DOI 10.1007/s10851-010-0251-1
Tony F. Chan, Selim Esedoḡlu, and Mila Nikolova, Algorithms for finding global minimizers of image segmentation and denoising models, SIAM J. Appl. Math. 66 (2006), no. 5, 1632–1648. MR 2246072, DOI 10.1137/040615286
T. F. Chan and L. A. Vese, A level set algorithm for minimizing the Mumford-Shah functional in image processing, IEEE/Computer Society Proceedings of the 1st IEEE Workshop on Variational and Level Set Methods in Computer Vision, 2001, pp. 161–168.
Yanqing Chen, Timothy A. Davis, William W. Hager, and Sivasankaran Rajamanickam, Algorithm 887: CHOLMOD, supernodal sparse Cholesky factorization and update/downdate, ACM Trans. Math. Software 35 (2008), no. 3, Art. 22, 14. MR 2738209, DOI 10.1145/1391989.1391995
David C. Dobson and Curtis R. Vogel, Convergence of an iterative method for total variation denoising, SIAM J. Numer. Anal. 34 (1997), no. 5, 1779–1791. MR 1472196, DOI 10.1137/S003614299528701X
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
Lawrence C. Evans and Ronald F. Gariepy, Measure theory and fine properties of functions, Studies in Advanced Mathematics, CRC Press, Boca Raton, FL, 1992. MR 1158660
Xiaobing Feng and Andreas Prohl, Analysis of total variation flow and its finite element approximations, M2AN Math. Model. Numer. Anal. 37 (2003), no. 3, 533–556. MR 1994316, DOI 10.1051/m2an:2003041
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
Weimin Han, A posteriori error analysis via duality theory, Advances in Mechanics and Mathematics, vol. 8, Springer-Verlag, New York, 2005. With applications in modeling and numerical approximations. MR 2101057
M. Hintermüller and K. Kunisch, Path-following methods for a class of constrained minimization problems in function space, Tech. report, Department of Computational and Applied Mathematics, Rice University, Houston, Texas, July 2004.
M. Hintermüller and K. Kunisch, Total bounded variation regularization as a bilaterally constrained optimization problem, SIAM J. Appl. Math. 64 (2004), no. 4, 1311–1333. MR 2068672, DOI 10.1137/S0036139903422784
K. Jalalzai, Discontinuities of the minimizers of the weighted or anisotropic total variation for image reconstruction, arXiv:1402.0026, 2014.
Stuart P. Lloyd, Least squares quantization in PCM, IEEE Trans. Inform. Theory 28 (1982), no. 2, 129–137. MR 651807, DOI 10.1109/TIT.1982.1056489
Luciano Modica and Stefano Mortola, Un esempio di $\Gamma ^{-}$-convergenza, Boll. Un. Mat. Ital. B (5) 14 (1977), no. 1, 285–299 (Italian, with English summary). MR 0445362
Jean-Michel Morel and Sergio Solimini, Variational methods in image segmentation, Progress in Nonlinear Differential Equations and their Applications, vol. 14, Birkhäuser Boston, Inc., Boston, MA, 1995. With seven image processing experiments. MR 1321598, DOI 10.1007/978-1-4684-0567-5
David Mumford and Jayant Shah, Optimal approximations by piecewise smooth functions and associated variational problems, Comm. Pure Appl. Math. 42 (1989), no. 5, 577–685. MR 997568, DOI 10.1002/cpa.3160420503
S. Özışık, Beatrice Riviere, and Tim Warburton, On the constants in inverse inequalities in $L^2$, Tech. Report 10-19, Department of Computational & Applied Mathematics, Rice University, 2010.
T. Pock, T. Schoenemann, G. Graber, H. Bischof, and D. Cremers, A convex formulation of continuous multi-label problems, ECCV08, 2008, pp. III: 792–805.
T. Pock, Diagonal preconditioning for first order primal-dual algorithms in convex optimization, IEEE International Conference on Computer Vision (ICCV), 2011, pp. 1762 – 1769.
T. Pock, D. Cremers, H. Bischof, and A. Chambolle, An algorithm for minimizing the Mumford-Shah functional, IEEE 12th International Conference on Computer Vision, 2009.
Thomas Pock, Daniel Cremers, Horst Bischof, and Antonin Chambolle, Global solutions of variational models with convex regularization, SIAM J. Imaging Sci. 3 (2010), no. 4, 1122–1145. MR 2763711, DOI 10.1137/090757617
Sergey I. Repin, A posteriori error estimation for variational problems with uniformly convex functionals, Math. Comp. 69 (2000), no. 230, 481–500. MR 1681096, DOI 10.1090/S0025-5718-99-01190-4
Sergey Repin, A posteriori estimates for partial differential equations, Radon Series on Computational and Applied Mathematics, vol. 4, Walter de Gruyter GmbH & Co. KG, Berlin, 2008. MR 2458008, DOI 10.1515/9783110203042
R. Tyrrell Rockafellar, Convex analysis, Princeton Landmarks in Mathematics, Princeton University Press, Princeton, NJ, 1997. Reprint of the 1970 original; Princeton Paperbacks. MR 1451876
Leonid I. Rudin, Stanley Osher, and Emad Fatemi, Nonlinear total variation based noise removal algorithms, Phys. D 60 (1992), no. 1-4, 259–268. Experimental mathematics: computational issues in nonlinear science (Los Alamos, NM, 1991). MR 3363401, DOI 10.1016/0167-2789(92)90242-F
J. Shen, ${\Gamma }$-convergence approximation to piecewise constant Mumford-Shah segmentation, Proceedings of the 7th International Conference on Advanced Concepts for Intelligent Vision Systems (ACIVS 2005), Lecture Notes in Computer Science, vol. 3708, Springer, 2005, pp. 499–506.
Jingyue Wang and Bradley J. Lucier, Error bounds for finite-difference methods for Rudin-Osher-Fatemi image smoothing, SIAM J. Numer. Anal. 49 (2011), no. 2, 845–868. MR 2792398, DOI 10.1137/090769594