Abstract
We propose a unified graph cut based global minimization method for multiphase image segmentation by convexifying the non-convex image segmentation cost functionals. As examples, we shall apply this method to the non-convex multiphase Chan-Vese (CV) model and piecewise constant level set method (PCLSM). Both continuous and discretized formulations will be treated. For the discrete models, we propose a unified graph cut algorithm to implement the CV and PCLSM models, which extends the result of Bae and Tai [1] to any phases CV model. Moreover, in the continuous case, we further improve the model to be convex without any conditions using a number of techniques that are unique to the continuous segmentation models. With the convex relaxation and the dual method, the related continuous dual model is convex and we can mathematically show that the global minimization can be achieved. The corresponding continuous max-flow algorithm is easy and stable. Experimental results show that our model is very efficient.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Bae, E., Tai, X.C.: Efficient global minimization methods for image segmentation models with four regions. Technical Report 11-82, UCLA CAM Report (2011)
Vese, L.A., Chan, T.F.: A multiphase level set framework for image segmentation using the mumford and shah model. International Journal of Computer Vision 50(3), 271–293 (2002)
Lie, J., Lysaker, M., Tai, X.C.: A variant of the level set method and applications to image segmentation. Mathematics of Computation 75(255), 1155–1174 (2006)
Lie, J., Lysaker, M., Tai, X.C.: A binary level set model and some applications to mumford-shah image segmentation. IEEE Transactions on Image Processing 15(5), 1171–1181 (2006)
Kolmogorov, V., Zabih, R.: What energy functions can be minimized via grah cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence 26(2), 147–159 (2004)
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 Mehotds in Computer Vision, pp. 1–13 (2009)
Ishikawa, H.: Exact optimization for markov random fields with convex priors. IEEE Transactions on Pattern Analysis and Machine Intelligence 25(10), 1333–1336 (2003)
Bae, E., Tai, X.-C.: Efficient global minimization for the multiphase chan-vese model of image segmentation. In: Cremers, D., Boykov, Y., Blake, A., Schmidt, F.R. (eds.) EMMCVPR 2009. LNCS, vol. 5681, pp. 28–41. Springer, Heidelberg (2009)
Chan, T.F., Esedoglu, S., Nikolova, M.: Algorithms for finding global minimizers of image segmentation and denoising models. SIAM Journal on Applied Mathematics 66(5), 1632–1648 (2006)
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)
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 Workshop, VMV (2008)
Pock, T., Chambolle, A., Cremers, D., Bischof, H.: A convex relaxation approach for computing minimal partitions. In: IEEE CVPR 2009 (2009)
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)
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)
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)
Brown, E.S., Chan, T.F., Bresson, X.: Completely convex formulation of the chan-vese image segmentation model. International Journal of Computer Vision 98, 103–121 (2012)
Claudia, N., Eno, T., Daniel, C.: A survey and comparison of discrete and continuous multi-label optimization approaches for the potts model. International Journal of Computer Vision, 1–18 (2013)
Bae, E., Lellmann, J., Tai, X.-C.: Convex relaxations for a generalized chan-vese model. In: Heyden, A., Kahl, F., Olsson, C., Oskarsson, M., Tai, X.-C., Chairs, P. (eds.) EMMCVPR 2013. LNCS, vol. 8081, pp. 223–236. Springer, Heidelberg (2013)
Ekeland, I., Temam, R.: Convex Analysis and Variational Problems. SIAM Classics in Applied Mathematics. SIAM, Philadelphia (1999)
Goldluecke, B., Cremers, D.: Convex relaxation for multilabel problems with product label spaces. In: Daniilidis, K., Maragos, P., Paragios, N. (eds.) ECCV 2010, Part V. LNCS, vol. 6315, pp. 225–238. Springer, Heidelberg (2010)
Fleming, W., Rishel, R.: An integral formula for total gradient variation. Archiv der Mathematik 11, 218–222 (1960)
Chan, T.F., Vese, L.A.: Active contours without edges. IEEE Transactions on Image Processing 10(2), 266–277 (2001)
Yuan, J., Bae, E., Tai, X.C.: A study on continuous max-flow and min-cut approaches. In: IEEE Conference on Computer Vision and Pattern Recognition (CVPR), San Francisco, USA, pp. 2217–2224 (2010)
Liu, J., Tai, X.C., Leung, S., Huang, H.: A new continuous max-flow algorithm for multiphase image segmentation using super-level set functions. Technical report, UCLA report 12-81 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Liu, J., Tai, XC., Leung, S. (2013). A Generic Convexification and Graph Cut Method for Multiphase Image Segmentation. In: Heyden, A., Kahl, F., Olsson, C., Oskarsson, M., Tai, XC. (eds) Energy Minimization Methods in Computer Vision and Pattern Recognition. EMMCVPR 2013. Lecture Notes in Computer Science, vol 8081. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40395-8_19
Download citation
DOI: https://doi.org/10.1007/978-3-642-40395-8_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40394-1
Online ISBN: 978-3-642-40395-8
eBook Packages: Computer ScienceComputer Science (R0)