Abstract
Markov random fields (MRF) and the Potts model have many applications in different areas. Especially, conditional random fields (CRF) and Potts model have been used in connection with classifiers. In this work, we focus on the Potts model and use image segmentation and data classification as examples to show some new techniques and fast algorithms for this model. We survey different piecewise constant representation techniques. Many of these representations can be interpreted as min-cut and max-flow problems on some special graphs. We will concentrate especially on the continuous setting and formulate continuous min-cut and max-flow models. When the min-cut/max-flow models are discretized, they give corresponding discrete min-cut/max-flow models on grids. Using these connections, we are able to turn the non-convex Potts model into some simple convex minimization problems with solutions that can be obtained by properly designed fast algorithms. In this survey, we will start by introducing some widely studied variational segmentation models and the classical level-set approaches to solve them. Then, we will describe three different piecewise constant representations for the general Potts model and their corresponding convex relaxations and fast algorithms. In the end, we will also generalize the method to a graph setting for high-dimensional data classifications. This survey presents the different techniques and algorithms in an integrated and self-contained manner.
Similar content being viewed by others
References
Acar, R., Vogel, C.R.: Analysis of bounded variation penalty methods for ill-posed problems. Inverse Problems 10(6), 1217 (1994)
Appleton, B., Talbot, H.: Globally optimal surfaces by continuous maximal flows. In: Digital Image Computing: Techniques and Applications: Proceedings of the VIIth Biennial Australian Pattern Recognition Society Conference, DICTA 2003, pp. 987–996. CSIRO PUBLISHING (2003)
Bae, E., Merkurjev, E.: Convex variational methods on graphs for multiclass segmentation of high-dimensional data and point clouds. J. Math. Imaging Vis. 58, 468493 (2017)
Bae, E., Tai, X.-C.: Efficient global minimization for the multiphase Chan-Vese model of image segmentation. In: Proceedings of the 7th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition. LNCS, vol. 5681, pp. 28–41. Springer (2009a)
Bae, E., Tai, X.-C.: Graph cut optimization for the piecewise constant level set method applied to multiphase image segmentation. In: Scale Space and Variational Methods in Computer Vision, second international conference, SSVM 2009, Voss, 1–5 June. Proceedings, pp. 1–13 (2009b)
Bae, E., Tai, X.-C.: Efficient global minimization methods for image segmentation models with four regions. J. Math. Imaging Vis. 51(1), 71–97 (2015)
Bae, E., Yuan, J., Tai, X.-C., Boykov, Y.: A fast continuous max-flow approach to non-convex multilabeling problems. UCLA CAM Report 10–62 (2010)
Bae, E., Yuan, J., Tai, X.-C.: Global minimization for continuous multiphase partitioning problems using a dual approach. Int. J. Comput. Vis. 92(1), 112–129 (2011)
Bae, E., Lellmann, J., Tai, X.-C.: Convex relaxations for a generalized Chan-Vese model. In: International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition, pp. 223–236. Springer (2013)
Bae, E., Yuan, J., Tai, X.-C., Boykov, Y.: A fast continuous max-flow approach to non-convex multi-labeling problems. In: Bruhn, A., Pock, T., Tai, X.-C. (eds.) Efficient Algorithms for Global Optimization Methods in Computer Vision. Lecture Notes in Computer Science, vol. 8293, pp. 134–154. Springer, Berlin/Heidelberg (2014)
Barzilai, J., Borwein, J.M.: Two-point step size gradient methods. IMA J. Numer. Anal. 8(1), 141–148 (1988)
Bertozzi, A.L., Flenner, A.: Diffuse interface models on graphs for classification of high dimensional data. Multiscale Model. Simul. 10(3), 1090–1118 (2012)
Bertsekas, D.P.: On the Goldstein-Levitin-Polyak gradient projection method. IEEE Trans. Autom. Control 21(2), 174–184 (1976)
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)
Boykov, Y., Veksler, O., Zabih, R.: Markov random fields with efficient approximations. In: Proceedings. 1998 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Cat. No. 98CB36231), pp. 648–655. IEEE (1998)
Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell. 23, 1222–1239 (2001)
Boyle, J.P., Dykstra, R.L.: A method for finding projections onto the intersection of convex sets in Hilbert spaces. In: Advances in Order Restricted Statistical Inference, pp. 28–47. Springer, New York (1986)
Bresson, X., Laurent, T., Uminsky, D., von Brecht, J.: Convergence and energy landscape for Cheeger cut clustering. In: Advances in Neural Information Processing Systems (NIPS), p. 13941402 (2012)
Bühler, T., Hein, M.: Spectral clustering based on the graph p-Laplacian. In: Proceedings of the 26th Annual International Conference on Machine Learning, pp. 81–88. ACM (2009)
Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Imaging Vis. 20(1–2), 89–97 (2004)
Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40(1), 120–145 (2011)
Chambolle, A., Caselles, V., Cremers, D., Novaga, M., Pock, T.: An introduction to total variation for image analysis. Theor. Found. Numer. Methods Sparse Recovery 9(263–340), 227 (2010)
Chambolle, A., Cremers, D., Pock, T.: A convex approach to minimal partitions. SIAM J. Imaging Sci. 5(4), 1113–1158 (2012)
Chan, T., Vese, L.: Active contours without edges. IEEE Trans. Image Process. 10(2), 266–277 (2001)
Chan, T.F., Esedoglu, S., Nikolova, M.: Algorithms for finding global minimizers of image segmentation and denoising models. SIAM J. Appl. Math. 66(5), 1632–1648 (2006)
Chung, F.R., Graham, F.C.: Spectral Graph Theory, vol. 92. American Mathematical Society, Providence (1997)
Couprie, C., Grady, L., Talbot, H., Najman, L.: Combinatorial continuous maximum flow. SIAM J. Imaging Sci. 4(3), 905930 (2011)
Cour, T., Benezit, F., Shi, J.: Spectral segmentation with multiscale graph decomposition. In: 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05), vol. 2, pp. 1124–1131. IEEE (2005)
Dai, Y.-H., Fletcher, R.: Projected barzilai-borwein methods for large-scale box-constrained quadratic programming. Numerische Mathematik 100(1), 21–47 (2005)
Darbon, J., Sigelle, M.: Image restoration with discrete constrained total variation part I: Fast and exact optimization. J. Math. Imaging Vis. 26(3), 261–276 (2006)
Darbon, J., Sigelle, M.: Image restoration with discrete constrained total variation part II: Levelable functions, convex priors and non-convex cases. J. Math. Imaging Vis. 26(3), 277–291 (2006)
Ekeland, I., Temam, R.: Convex Analysis and Variational Problems, vol. 28. SIAM, Philadelphia (1999)
Elmoataz, A., Lezoray, O., Bougleux, S.: Nonlocal discrete regularization on weighted graphs: a framework for image and manifold processing. IEEE Trans. Image Process. 17(7), 1047–1060 (2008)
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 Sci. 3(4), 1015–1046 (2010)
Fleming, W.H., Rishel, R.: An integral formula for total gradient variation. Archiv der Mathematik 11, 218–222 (1960)
Garcia-Cardona, C., Merkurjev, E., Bertozzi, A., Flenner, A., Percus, A.: Multiclass data segmentation using diffuse interface methods on graphs. IEEE Trans. Pattern Anal. Mach. Intell. 36(8), 1600–1613 (2014)
Geman, S., Geman, D.: Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Trans. Pattern Anal. Mach. Intell. 6, 721–741 (1984)
Gilboa, G., Osher, S.: Nonlocal operators with applications to image processing. Multiscale Model. Simul. 7(3), 1005–1028 (2008)
Hu, H., Laurent, T., Porter, M.A., Bertozzi, A.L.: A method based on total variation for network modularity optimization using the MBO scheme. SIAM J. Appl. Math. 73(6), 2224–2246 (2013)
Ishikawa, H.: Exact optimization for Markov random fields with convex priors. IEEE Trans. Pattern Anal. Mach. Intell. 25(10), 1333–1336 (2003)
Krähenbühl, P., Koltun, V.: Efficient inference in fully connected crfs with Gaussian edge potentials. In: Advances in Neural Information Processing Systems, pp. 109–117 (2011)
Lafferty, J., McCallum, A., Pereira, F.C.: Conditional random fields: probabilistic models for segmenting and labeling sequence data (2001)
Lellmann, J., Kappes, J., Yuan, J., Becker, F., Schnörr, C. Convex multi-class image labeling by simplex-constrained total variation. In: International Conference on Scale Space and Variational Methods in Computer Vision, pp. 150–162. Springer (2009)
Lie, J., Lysaker, M., Tai, X.-C.: Piecewise constant level set methods and image segmentation. In: International Conference on Scale-Space Theories in Computer Vision, pp. 573–584. Springer (2005)
Lie, J., Lysaker, M., Tai, X.-C.: A binary level set model and some applications to Mumford-Shah image segmentation. IEEE Trans. Image Process. 15(5), 1171–1181 (2006a)
Lie, J., Lysaker, M., Tai, X.-C.: A variant of the level set method and applications to image segmentation. AMS Math. Comput. 75(255), 1155–1174 (2006)
Liu, J., Tai, X.-C., Leung, S., Huang, H.: A new continuous max-flow algorithm for multiphase image segmentation using super-level set functions. J. Vis. Commun. Image Represent. 25(6), 1472–1488 (2014)
Lozes, O.L.F., Elmoataz, A.: Partial difference operators on weighted graphs for image processing on surfaces and point clouds. IEEE Trans. Image Process. 23, 3896–3909 (2014)
Merkurjev, E., Kostic, T., Bertozzi, A.L.: An MBO scheme on graphs for classification and image processing. SIAM J. Imaging Sci. 6(4), 1903–1930 (2013)
Merkurjev, E., Bae, E., Bertozzi, A.L., Tai, X.-C.: Global binary optimization on graphs for classification of high-dimensional data. J. Math. Imaging Vis. 52(3), 414–435 (2015)
Michelot, C.: A finite algorithm for finding the projection of a point onto the canonical simplex of n. J. Optim. Theory Appl. 50(1), 195–200 (1986)
Mumford, D., Shah, J.: Optimal approximations by piecewise smooth functions and associated variational problems. Commun. Pure Appl. Math. 42(5), 577–685 (1989)
Osher, S., Fedkiw, R.: Level Set Methods and Dynamic Implicit Surfaces. Applied Mathematical Sciences, vol. 153. Springer, New York (2003)
Osting, B., White, C.D., Oudet, É.: Minimal Dirichlet energy partitions for graphs. SIAM J. Sci. Comput. 36(4), A1635–A1651 (2014)
Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Courier Corporation. Dover Publications, Inc, Mineola (1998)
Pock, T., Schoenemann, T., Graber, G., Bischof, H., Cremers, D.: A convex formulation of multi-label problems. In: European Conference on Computer Vision, pp. 792–805. Springer (2008)
Pock, T., Chambolle, A., Cremers, D., Bischof, H.: A convex relaxation approach for computing minimal partitions. In: 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 810–817. IEEE (2009)
Potts, R.B.: Some generalized order-disorder transformations. In: Mathematical Proceedings of the Cambridge Philosophical Society, vol. 48, pp. 106–109. Cambridge University Press (1952)
Rudin, L.I., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Phys. D: Nonlinear Phenom. 60(1–4), 259–268 (1992)
Schölkopf, B., Tsuda, K., Vert, J.-P.: Kernel Methods in Computational Biology. MIT Press, Cambridge (2004)
Schrijver, A.: On the history of the transportation and maximum flow problems. Math. Program. 91(3), 437–445 (2002)
Singhal, A., et al: Modern information retrieval: a brief overview. IEEE Data Eng. Bull. 24(4), 35–43 (2001)
Strang, G.: Maximal flow through a domain. Math. Program. 26, 123–143 (1983)
Sussman, M., Smereka, P., Osher, S.: A level set approach for computing solutions to incompressible two-phase flow. J. Comput. Phys. 114(1), 146–159 (1994)
Szeliski, R., Zabih, R., Scharstein, D., Veksler, O., Agarwala, A., Rother, C.: A comparative study of energy minimization methods for Markov random fields. In: ECCV, pp. 16–29 (2006)
Toutain, M., Elmoataz, A., Lzoray, O.: Geometric pdes on weighted graphs for semi-supervised classification. In: 13th International Conference on Machine Learning and Applications (ICMLA), pp. 231–236 (2014)
van Gennip, Y., Bertozzi, A.: Gamma-convergence of graph Ginzburg-Landau functionals. Adv. Differ. Equ. 17(11–12), 1115–1180 (2012)
Vese, L.A., Chan, T.F.: A multiphase level set framework for image segmentation using the Mumford and Shah model. Int. J. Comput. Vis. 50(3), 271–293 (2002)
Wu, C., Tai, X.-C.: Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, vectorial TV, and high order models. SIAM J. Imaging Sci. 3, 300–339 (2010)
Yin, K., Tai, X.-C.: An effective region force for some variational models for learning and clustering. J. Sci. Comput. 74(1), 175–196 (2018)
Yuan, J., Bae, E., Tai, X.-C., Boykov, Y.: A continuous max-flow approach to Potts model. In: European Conference on Computer Vision, pp. 379–392. Springer (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(3), 559–587 (2014)
Zach, C., Gallup, D., Frahm, J.-M., Niethammer, M.: Fast global labeling for real-time stereo using multiple plane sweeps. In: Vision, Modeling and Visualization, pp. 243–252 (2008)
Zelnik-Manor, L., Perona, P.: Self-tuning spectral clustering. In: Advances in Neural Information Processing Systems, pp. 1601–1608 (2005)
Zhao, H., Chan, T., Merriman, B., Osher, S.: A variational level set approach to multiphase motion. J. Comput. Phys. 127(1), 179–195 (1996)
Zhu, M., Chan, T.F.: Fast numerical algorithms for total variation based image restoration. PhD thesis, University of California, Los Angeles (2008)
Acknowledgements
The work was supported by RG(R)-RC/17-18/02-MATH, HKBU 12300819, NSF/RGC Grant N-HKBU214-19, ANR/RGC Joint Research Scheme (A-HKBU203-19) and RC-FNRA-IG/19-20/SCI/01.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Section Editor information
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this entry
Cite this entry
Tai, X., Li, L., Bae, E. (2021). The Potts Model with Different Piecewise Constant Representations and Fast Algorithms: A Survey. In: Chen, K., Schönlieb, CB., Tai, XC., Younces, L. (eds) Handbook of Mathematical Models and Algorithms in Computer Vision and Imaging. Springer, Cham. https://doi.org/10.1007/978-3-030-03009-4_90-2
Download citation
DOI: https://doi.org/10.1007/978-3-030-03009-4_90-2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-03009-4
Online ISBN: 978-3-030-03009-4
eBook Packages: Springer Reference MathematicsReference Module Computer Science and Engineering
Publish with us
Chapter history
-
Latest
The Potts Model with Different Piecewise Constant Representations and Fast Algorithms: A Survey- Published:
- 08 October 2023
DOI: https://doi.org/10.1007/978-3-030-03009-4_90-3
-
The Potts Model with Different Piecewise Constant Representations and Fast Algorithms: A Survey
- Published:
- 16 September 2021
DOI: https://doi.org/10.1007/978-3-030-03009-4_90-2
-
Original
The Potts Model with Different Piecewise Constant Representations and Fast Algorithms: A Survey- Published:
- 28 May 2021
DOI: https://doi.org/10.1007/978-3-030-03009-4_90-1