Abstract
In this work, we study the problems of computing spatially continuous cuts, which has many important applications of image processing and computer vision. We focus on the convex relaxed formulations and investigate the corresponding flow-maximization based dual formulations. We propose a series of novel continuous max-flow models based on evaluating different constraints of flow excess, where the classical pre-flow and pseudo-flow models over graphs are re-discovered in the continuous setting and re-interpreted in a new variational manner. We propose a new generalized proximal method, which is based on a specific entropic distance function, to compute the maximum flow. This leads to new algorithms exploring flow-maximization and message-passing simultaneously. We show the proposed algorithms are superior to state of art methods in terms of efficiency.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Appleton, B., Talbot, H.: Globally minimal surfaces by continuous maximal flows. IEEE Transactions on PAMI 28, 106–118 (2006)
Bae, E., Yuan, J., Tai, X.-C.: Global minimization for continuous multiphase partitioning problems using a dual approach. International Journal of Computer Vision 92(1), 112–129 (2011)
Banerjee, A., Merugu, S., Dhillon, I.S., Ghosh, J.: Clustering with bregman divergences. Journal of Machine Learning Research 6, 1705–1749 (2005)
Boykov, Y., Kolmogorov, V.: An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Transactions on PAMI 26, 359–374 (2001)
Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. IEEE Transactions on PAMI 23, 1222 (2001)
Bregman, L.M.: The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Computational Mathematics and Mathematical Physics 7, 200–217 (1967)
Bresson, X., Esedoglu, S., Vandergheynst, P., Thiran, J.P., Osher, S.: Fast global minimization of the active contour/snake model. Journal of Mathematical Imaging and Vision 28(2), 151–167 (2007)
Censor, Y.A., Zenios, S.A.: Parallel Optimization: Theory, Algorithms and Applications. Oxford University Press (1997)
Chambolle, A., Cremers, D., Pock, T.: A convex approach for computing minimal partitions. Technical Report TR-2008-05, University of Bonn (November 2008)
Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of Mathematical Imaging and Vision 40(1), 120–145 (2011)
Esser, E., Zhang, X., Chan, T.F.: A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM J. Imaging Sciences 3(4), 1015–1046 (2010)
Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)
Ford Jr., L.R., Fulkerson, D.R.: Maximal flow through a network. Canad. J. Math. 8, 399–404 (1956)
Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum-flow problem. J. ACM 35(4), 921–940 (1988)
Goldstein, T., Bresson, X., Osher, S.: Geometric applications of the split bregman method: Segmentation and surface reconstruction. J. Sci. Comput. 45(1-3), 272–293 (2010)
Greig, D.M., Porteous, B.T., Seheult, A.H.: Exact maximum a posteriori estimation for binary images. J. Royal Stat. Soc., Series B, 271–279 (1989)
Hochbaum, D.S.: The pseudoflow algorithm: A new algorithm for the maximum-flow problem. Operations Research 56(4), 992–1009 (2008)
Iusem, A.N., Svaiter, B.F., Teboulle, M.: Entropy-like proximal methods in convex programming. Mathematics of Operations Research 19(4), 790–814 (1994)
Kolmogorov, V., Wainwright, M.J.: On the optimality of tree-reweighted max-product message-passing. In: UAI, pp. 316–323 (2005)
Lellmann, J., Kappes, J., Yuan, J., Becker, F., Schnörr, C.: Convex multi-class image labeling by simplex-constrained total variation. In: Tai, X.-C., Mørken, K., Lysaker, M., Lie, K.-A. (eds.) SSVM 2009. LNCS, vol. 5567, pp. 150–162. Springer, Heidelberg (2009)
Nikolova, M., Esedoglu, S., Chan, T.F.: Algorithms for finding global minimizers of image segmentation and denoising models. SIAM J. App. Math. 66(5), 1632–1648 (2006)
Olsson, C., Byröd, M., Overgaard, N.C., Kahl, F.: Extending continuous cuts: Anisotropic metrics and expansion moves. In: ICCV, pp. 405–412 (2009)
Paragios, N., Chen, Y., Faugeras, O.: Handbook of Mathematical Models in Computer Vision. Springer-Verlag New York, Inc., Secaucus (2005)
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)
Rockafellar, R.T.: Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2), 97–116 (1976)
Rockafellar, R.T.: Convex analysis. Princeton Mathematical Series, vol. 28. Princeton University Press, Princeton (1970)
Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optimization 14(5), 877–898 (1976)
Teboulle, M.: Entropic proximal mappings with applications to nonlinear programming. Math. Oper. Res. 17(3), 670–690 (1992)
Teboulle, M.: A unified continuous optimization framework for center-based clustering methods. J. Mach. Learn. Res. 8, 65–102 (2007)
Wainwright, M., Jaakkola, T., Willsky, A.: Map estimation via agreement on (hyper)trees: Message-passing and linear programming approaches. IEEE Transactions on Information Theory 51, 3697–3717 (2002)
Wainwright, M.J., Jaakkola, T., Willsky, A.S.: Map estimation via agreement on trees: message-passing and linear programming. IEEE Transactions on Information Theory 51(11), 3697–3717 (2005)
Yuan, J., Bae, E., Tai, X.C.: A study on continuous max-flow and min-cut approaches. In: CVPR, USA, San Francisco (2010)
Yuan, J., Bae, E., Tai, X.-C., Boykov, Y.: A spatially continuous max-flow and min-cut framework for binary labeling problems. Numerische Mathematik 126, 559–587 (2013)
Zach, C., Gallup, D., Frahm, J.-M., Niethammer, M.: Fast global labeling for real-time stereo using multiple plane sweeps. In: VMV 2008 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Bae, E., Tai, XC., Yuan, J. (2015). Maximizing Flows with Message-Passing: Computing Spatially Continuous Min-Cuts. In: Tai, XC., Bae, E., Chan, T.F., Lysaker, M. (eds) Energy Minimization Methods in Computer Vision and Pattern Recognition. EMMCVPR 2015. Lecture Notes in Computer Science, vol 8932. Springer, Cham. https://doi.org/10.1007/978-3-319-14612-6_2
Download citation
DOI: https://doi.org/10.1007/978-3-319-14612-6_2
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-14611-9
Online ISBN: 978-3-319-14612-6
eBook Packages: Computer ScienceComputer Science (R0)