Abstract
This paper studies continuous image labeling problems with an arbitrary data term and a total variation regularizer, where the labels are constrained to a finite set of real numbers. Inspired by Ishikawa’s multi-layered graph construction for the same labeling problem over a discrete image domain, we propose a novel continuous max-flow model and build up its duality to a convex relaxed formulation of image labeling under a new variational perspective. Via such continuous max-flow formulations, we show that exact and global optimizers can be obtained to the original non-convex labeling problem. We also extend the studies to problems with continuous-valued labels and introduce a new theory to this problem. Finally, we show the proposed continuous max-flow models directly lead to new fast flow-maximization algorithmic schemes which outperform previous approaches in terms of efficiency. Such continuous max-flow based algorithms can be validated by convex optimization theories and accelerated by modern parallel computational hardware.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell. 23, 1222–1239 (2001)
Appleton, B., Talbot, H.: Globally optimal surfaces by continuous maximal flows. In: DICTA, pp. 987–996 (2003)
Kolmogorov, V., Zabih, R.: Multi-camera scene reconstruction via graph cuts. In: Heyden, A., Sparr, G., Nielsen, M., Johansen, P. (eds.) ECCV 2002, Part III. LNCS, vol. 2352, pp. 82–96. Springer, Heidelberg (2002)
Kolmogorov, V., Zabih, R.: What energy functions can be minimized via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell. 26, 65–81 (2004)
Lempitsky, V., Boykov, Y.: Global optimization for shape fitting. In: CVPR (2007)
Ishikawa, H.: Exact optimization for markov random fields with convex priors. IEEE Trans. Pattern Anal. Mach. Intell. 25, 1333–1336 (2003)
Kohli, P., Kumar, M.P., Torr, P.H.: \(p^3\) and beyond: move making algorithms for solving higher order functions. IEEE Trans. Pattern Anal. Mach. Intell. 31, 1645–1656 (2009)
Chan, T.F., Esedoḡlu, S., Nikolova, M.: Algorithms for finding global minimizers of image segmentation and denoising models. SIAM J. Appl. Math. 66, 1632–1648 (2006). (electronic)
Pock, T., Schoenemann, T., Graber, G., Bischof, H., Cremers, D.: A convex formulation of continuous multi-label problems. In: Forsyth, D., Torr, P., Zisserman, A. (eds.) ECCV 2008, Part III. LNCS, vol. 5304, pp. 792–805. Springer, Heidelberg (2008)
Pock, T., Cremers, D., Bischof, H., Chambolle, A.: Global solutions of variational models with convex regularization. Technical report, Institute for Computer Graphics and Vision, Graz University of Technology (2010)
Bouchitt’e, G.: Recent convexity arguments in the calculus of variations. In: Lecture Notes from the 3rd International Summer School on the Calculus of Variations, Pisa (1998)
Alberti, G., Bouchitté, G., Maso, G.D.: The calibration method for the mumford-shah functional and free-discontinuity problems. Calc. Var. Partial Differ. Eqn. 16, 299–333 (2003)
Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)
Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Can. J. Math. 8, 399–404 (1956)
Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum-flow problem. J. ACM 35, 921–940 (1988)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)
Strang, G.: Maximal flow through a domain. Math. Program. 26, 123–143 (1983)
Appleton, B., Talbot, H.: Globally minimal surfaces by continuous maximal flows. IEEE Trans. Pattern Anal. Mach. Intell. 28, 106–118 (2006)
Yuan, J., Bae, E., Tai, X.: A study on continuous max-flow and min-cut approaches. In: IEEE Conference on Computer Vision and Pattern Recognition, San Francisco, USA, pp. 2217–2224 (2010)
Yuan, J., Bae, E., Tai, X., Boykov, Y.: A study on continuous max-flow and min-cut approaches. Technical report CAM10-61, UCLA, CAM (2010)
Yuan, J., Bae, E., Tai, X.-C., Boykov, Y.: A continuous max-flow approach to potts model. In: Daniilidis, K., Maragos, P., Paragios, N. (eds.) ECCV 2010, Part VI. LNCS, vol. 6316, pp. 379–392. Springer, Heidelberg (2010)
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)
Bae, E., Yuan, J., Tai, X., Boykov, Y.: A fast continuous max-flow approach to non-convex multilabeling problems. Technical report, UCLA, CAM-report 10-62 (2010)
Bae, E., Tai, X.-C.: Graph cut optimization for the piecewise constant level set method applied to multiphase image segmentation. In: Tai, X.-C., Mørken, K., Lysaker, M., Lie, K.-A. (eds.) SSVM 2009. LNCS, vol. 5567, pp. 1–13. Springer, Heidelberg (2009)
Bae, E., Yuan, J., Tai, X.C.: Global minimization for continuous multiphase partitioning problems using a dual approach. Int. J. Comput. Vision 92, 112–129 (2011)
Giaquinta, M., Modica, G., Soucek, J.: Cartesian Currents in the Calculus of Variations I. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge A Series of Modern Surveys in Mathematics, vol. 37. Springer, Heidelberg (1998)
Giaquinta, M., Modica, G., Soucek, J.: Cartesian Currents in the Calculus of Variations II. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge A Series of Modern Surveys in Mathematics, vol. 38. Springer, Heidelberg (1998)
Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Imaging Vis. 20, 89–97 (2004)
Bertsekas, D.P.: Nonlinear Programming. Athena Scientific, Belmont (1999)
Esser, J.E.: Primal dual algorithms for convex models and applications to image restoration, registration and nonlocal inpainting (2010)
Hyman, J.M., Shashkov, M.J.: Natural discretizations for the divergence, gradient, and curl on logically rectangular grids. Comput. Math. Appl. 33, 81–104 (1997)
Hyman, J.M., Shashkov, M.J.: Adjoint operators for the natural discretizations of the divergence, gradient and curl on logically rectangular grids. Appl. Numer. Math. 25, 413–442 (1997)
Boykov, Y., Kolmogorov, V.: An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Trans. Pattern Anal. Mach. Intell. 26, 359–374 (2001)
Acknowledgements
This research has been supported by the Norwegian Research Council eVita project 214889 and eVita project 166075 and Natural Sciences and Engineering Research Council of Canada (NSERC) Accelerator Grant R3584A04.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bae, E., Yuan, J., Tai, XC., Boykov, Y. (2014). A Fast Continuous Max-Flow Approach to Non-convex Multi-labeling Problems. In: Bruhn, A., Pock, T., Tai, XC. (eds) Efficient Algorithms for Global Optimization Methods in Computer Vision. Lecture Notes in Computer Science(), vol 8293. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-54774-4_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-54774-4_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-54773-7
Online ISBN: 978-3-642-54774-4
eBook Packages: Computer ScienceComputer Science (R0)