Abstract
We propose an algorithm for efficiently minimizing the piecewise smooth Mumford-Shah functional. The algorithm is based on an extension of a recent primal-dual algorithm from convex to non-convex optimization problems. The key idea is to rewrite the proximal operator in the primal-dual algorithm using Moreau’s identity. The resulting algorithm computes piecewise smooth approximations of color images at 15-20 frames per second at VGA resolution using GPU acceleration. Compared to convex relaxation approaches [18], it is orders of magnitude faster and does not require a discretization of color values. In contrast to the popular Ambrosio-Tortorelli approach [2], it naturally combines piecewise smooth and piecewise constant approximations, it does not require an epsilon-approximation and it is not based on an alternation scheme. The achieved energies are in practice at most 5% off the optimal value for one-dimensional problems. Numerous experiments demonstrate that the proposed algorithm is well-suited to perform discontinuity-preserving smoothing and real-time video cartooning.
Chapter PDF
Similar content being viewed by others
References
Alberti, G., Bouchitté, G., Dal Maso, G.: The calibration method for the Mumford-Shah functional and free-discontinuity problems. Calc. Var. Partial Differential Equations 16(3), 299–333 (2003)
Ambrosio, L., Tortorelli, V.M.: Approximation of functionals depending on jumps by elliptic functionals via Γ–convergence. Comm. Pure Appl. Math. 43, 999–1036 (1990)
Blake, A., Zisserman, A.: Visual Reconstruction. MIT Press (1987)
Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. IEEE Trans. on Patt. Anal. and Mach. Intell. 23(11), 1222–1239 (2001)
Brook, A., Kimmel, R., Sochen, N.A.: Variational restoration and edge detection for color images. Journal of Mathematical Imaging and Vision 18(3), 247–268 (2003)
Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Im. Vis. 20(1-2), 89–97 (2004)
Chambolle, A., Cremers, D., Pock, T.: A convex approach to minimal partitions. SIAM Journal on Imaging Sciences 5(4), 1113–1158 (2012)
Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40, 120–145 (2011)
Chambolle, A.: Image segmentation by variational methods: Mumford and Shah functional and the discrete approximations. SIAM J. Appl. Math. 55(3), 827–863 (1995)
Giaquinta, M., Modica, G., Souček, J.: Cartesian currents in the calculus of variations I, II., Ergebnisse der Mathematik und ihrer Grenzgebiete. 3, vol. 37-38, pp. 37–38. Springer, Berlin (1998)
Grady, L., Alvino, C.: The piecewise smooth Mumford-Shah functional on an arbitrary graph. IEEE Transactions on Image Processing 18(11) (2009)
Komodakis, N., Tziritas, G.: Approximate labeling via graph-cuts based on linear programming. IEEE Trans. on Patt. Anal. and Mach. Intell. 29(8), 1436–1453 (2007)
Lellmann, J., Schnörr, C.: Continuous multiclass labeling approaches and algorithms. SIAM J. Imaging Sciences 4(4), 1049–1096 (2011)
Morel, J.M., Solimini, S.: Variational Methods in Image Segmentation. Birkhäuser, Boston (1995)
Mumford, D., Shah, J.: Optimal approximations by piecewise smooth functions and associated variational problems. Comm. Pure Appl. Math. 42(5), 577–685 (1989)
Pock, T., Cremers, D., Bischof, H., Chambolle, A.: An algorithm for minimizing the piecewise smooth Mumford-Shah functional. In: ICCV (2009)
Rockafellar, R.T.: Convex Analysis. Princeton University Press (1996)
Strekalovskiy, E., Chambolle, A., Cremers, D.: A convex representation for the vectorial Mumford-Shah functional. In: CVPR (June 2012)
Veksler, O.: Graph cut based optimization for mrfs with truncated convex priors. In: CVPR (2007)
Vese, L., Chan, T.: A multiphase level set framework for image processing using the Mumford–Shah functional. Int. J. of Computer Vision 50(3), 271–293 (2002)
Xu, L., Lu, C., Xu, Y., Jia, J.: Image smoothing via l 0 gradient minimization. In: Proceedings of SIGGRAPH Asia, pp. 174:1–174:12. ACM (2011)
Zach, C., Hane, C., Pollefeys, M.: What is optimized in convex relaxations for multilabel problems: Connecting discrete and continuously inspired map inference. IEEE Transactions on Pattern Analysis and Machine Intelligence 36(1), 157–170 (2014)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Strekalovskiy, E., Cremers, D. (2014). Real-Time Minimization of the Piecewise Smooth Mumford-Shah Functional. In: Fleet, D., Pajdla, T., Schiele, B., Tuytelaars, T. (eds) Computer Vision – ECCV 2014. ECCV 2014. Lecture Notes in Computer Science, vol 8690. Springer, Cham. https://doi.org/10.1007/978-3-319-10605-2_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-10605-2_9
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-10604-5
Online ISBN: 978-3-319-10605-2
eBook Packages: Computer ScienceComputer Science (R0)