Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

A posteriori error control for the binary Mumford-Shah model


Authors: Benjamin Berkels, Alexander Effland and Martin Rumpf
Journal: Math. Comp. 86 (2017), 1769-1791
MSC (2010): Primary 49M25, 53C22, 65D18, 65L20
DOI: https://doi.org/10.1090/mcom/3138
Published electronically: October 20, 2016
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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 (2004k:49029), https://doi.org/10.1007/s005260100152
  • [2] Luigi Ambrosio, Variational problems in $ {\rm SBV}$ and image segmentation, Acta Appl. Math. 17 (1989), no. 1, 1-40. MR 1029833 (91d:49003), https://doi.org/10.1007/BF00052492
  • [3] 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 (93e:49010)
  • [4] 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 (2003a:49002)
  • [5] 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, https://doi.org/10.1090/S0025-5718-2014-02893-7
  • [6] 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, https://doi.org/10.1093/imanum/drv023
  • [7] 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.
  • [8] B. Berkels, Joint methods in imaging based on diffuse image representations, Dissertation, University of Bonn, 2010.
  • [9] 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 (2001g:65151), https://doi.org/10.1007/PL00005394
  • [10] 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.
  • [11] 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, Z. Vyčisl. Mat. i Mat. Fiz. 7 (1967), 620-631 (Russian). MR 0215617 (35 #6457)
  • [12] Paul H. Calamai and Jorge J. Moré, Projected gradient methods for linearly constrained problems, Math. Programming 39 (1987), no. 1, 93-116. MR 909010 (89f:90132), https://doi.org/10.1007/BF02592073
  • [13] 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 (96h:68216), https://doi.org/10.1137/S0036139993257132
  • [14] 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 (2005m:49058), https://doi.org/10.1023/B:JMIV.0000011320.81911.38
  • [15] 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.
  • [16] 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.
  • [17] 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, https://doi.org/10.1137/110856733
  • [18] 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 (2000j:49045), https://doi.org/10.1051/m2an:1999156
  • [19] 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.
  • [20] 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 (2012b:94004), https://doi.org/10.1007/s10851-010-0251-1
  • [21] T. F. Chan, S. Esedoglu, 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 (2007k:94012), https://doi.org/10.1137/040615286
  • [22] 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.
  • [23] 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, https://doi.org/10.1145/1391989.1391995
  • [24] 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 (99a:65081), https://doi.org/10.1137/S003614299528701X
  • [25] 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 (2000j:49001)
  • [26] 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 (93f:28001)
  • [27] 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 (2004f:65149), https://doi.org/10.1051/m2an:2003041
  • [28] 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 (2010e:65087), https://doi.org/10.1137/080725891
  • [29] Weimin Han, A Posteriori Error Analysis via Duality Theory: With Applications in Modeling and Numerical Approximations, Advances in Mechanics and Mathematics, vol. 8, Springer-Verlag, New York, 2005. MR 2101057 (2005k:65003)
  • [30] 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.
  • [31] 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 (2005b:49062), https://doi.org/10.1137/S0036139903422784
  • [32] K. Jalalzai, Discontinuities of the minimizers of the weighted or anisotropic total variation for image reconstruction, arXiv:1402.0026, 2014.
  • [33] Stuart P. Lloyd, Least squares quantization in PCM, IEEE Trans. Inform. Theory 28 (1982), no. 2, 129-137. MR 651807 (84a:94012), https://doi.org/10.1109/TIT.1982.1056489
  • [34] 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 (56 #3704)
  • [35] Jean-Michel Morel and Sergio Solimini, Variational Methods in Image Segmentation: With Seven Image Processing Experiments, Progress in Nonlinear Differential Equations and their Applications, 14, Birkhäuser Boston, Inc., Boston, MA, 1995. MR 1321598
  • [36] 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 (90g:49033), https://doi.org/10.1002/cpa.3160420503
  • [37] 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.
  • [38] 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.
  • [39] T. Pock, Diagonal preconditioning for first order primal-dual algorithms in convex optimization, IEEE International Conference on Computer Vision (ICCV), 2011, pp. 1762 - 1769.
  • [40] 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.
  • [41] 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 (2012e:49063), https://doi.org/10.1137/090757617
  • [42] Sergey I. Repin, A posteriori error estimation for variational problems with uniformly convex functionals, Math. Comp. 69 (2000), no. 230, 481-500. MR 1681096 (2000i:49046), https://doi.org/10.1090/S0025-5718-99-01190-4
  • [43] Sergey I. 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
  • [44] R. Tyrrell Rockafellar, Convex Analysis, Princeton Landmarks in Mathematics, Princeton University Press, Princeton, NJ, 1997. Reprint of the 1970 original; Princeton Paperbacks. MR 1451876 (97m:49001)
  • [45] 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
  • [46] 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.
  • [47] 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 (2012h:65244), https://doi.org/10.1137/090769594

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 49M25, 53C22, 65D18, 65L20

Retrieve articles in all journals with MSC (2010): 49M25, 53C22, 65D18, 65L20


Additional Information

Benjamin Berkels
Affiliation: AICES Graduate School, RWTH Aachen University, 52062 Aachen, Germany
Email: berkels@aices.rwth-aachen.de

Alexander Effland
Affiliation: Institute for Numerical Simulation, University of Bonn, 53115 Bonn, Germany
Email: alexander.effland@ins.uni-bonn.de

Martin Rumpf
Affiliation: Institute for Numerical Simulation, University of Bonn, 53115 Bonn, Germany
Email: martin.rumpf@ins.uni-bonn.de

DOI: https://doi.org/10.1090/mcom/3138
Received by editor(s): May 19, 2015
Received by editor(s) in revised form: December 8, 2015, and December 17, 2015
Published electronically: October 20, 2016
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society