Skip to main content
Erschienen in: International Journal of Computer Vision 3/2013

01.09.2013

Combinatorial Optimization of the Discretized Multiphase Mumford–Shah Functional

Erschienen in: International Journal of Computer Vision | Ausgabe 3/2013

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The Mumford–Shah model has been one of the most influential models in image segmentation and denoising. The optimization of the multiphase Mumford–Shah energy functional has been performed using level sets methods that optimize the Mumford–Shah energy by evolving the level sets via the gradient descent. These methods are very slow and prone to getting stuck in local optima due to the use of gradient descent. After the reformulation of the 2-phase Mumford–Shah functional on a graph, several groups investigated the hierarchical extension of the graph representation to multi class. The discrete hierarchical approaches are more effective than hierarchical (or direct) multiphase formulation using level sets. However, they provide approximate solutions and can diverge away from the optimal solution. In this paper, we present a discrete alternating optimization for the discretized Vese–Chan approximation of the piecewise constant multiphase Mumford–Shah functional that directly minimizes the multiphase functional without recursive bisection on the labels. Our approach handles the nonsubmodularity of the multiphase energy function and provides a global optimum if the image estimation data term is known apriori.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literatur
Zurück zum Zitat Badshah, N., & Chen, K. (2009). On two multigrid algorithms for modeling variational multiphase image segmentation. IEEE Transaction on Image Processing, 18(5), 1097–1106.MathSciNetCrossRef Badshah, N., & Chen, K. (2009). On two multigrid algorithms for modeling variational multiphase image segmentation. IEEE Transaction on Image Processing, 18(5), 1097–1106.MathSciNetCrossRef
Zurück zum Zitat Bae, E., & Tai, X. C. (2009). Efficient global minimization for the multiphase Chan–Vese model of image segmentation. In International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition, EMMCVPR ’09 (pp. 28–41). Bae, E., & Tai, X. C. (2009). Efficient global minimization for the multiphase Chan–Vese model of image segmentation. In International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition, EMMCVPR ’09 (pp. 28–41).
Zurück zum Zitat Bae, E., & Tai, X. C. (2009). Graph cut optimization for the piecewise constant level set method applied to multiphase image segmentation. In International Conference of Scale Space and Variational Methods in Computer Vision (pp. 1–13). Bae, E., & Tai, X. C. (2009). Graph cut optimization for the piecewise constant level set method applied to multiphase image segmentation. In International Conference of Scale Space and Variational Methods in Computer Vision (pp. 1–13).
Zurück zum Zitat Bae, E., Yuan, J., & Tai, X. C. (2011). Global minimization for continuous multiphase partitioning problems using a dual approach. International Journal of Computer Vision, 92(1), 112–129. Bae, E., Yuan, J., & Tai, X. C. (2011). Global minimization for continuous multiphase partitioning problems using a dual approach. International Journal of Computer Vision, 92(1), 112–129.
Zurück zum Zitat Boros, E., Hammer, P. L., & Tavares, G. (2006). Preprocessing of unconstrained quadratic binary optimization. Tech. Rep. RRR 10–2006, RUTCOR. Boros, E., Hammer, P. L., & Tavares, G. (2006). Preprocessing of unconstrained quadratic binary optimization. Tech. Rep. RRR 10–2006, RUTCOR.
Zurück zum Zitat Boykov, Y., Veksler, O., & Zabih, R . (1999). Fast approximate energy minimization via graph cuts. In International Conference for Computer Vision, ICCV99 (Vol. 1, pp. 377–384). Boykov, Y., Veksler, O., & Zabih, R . (1999). Fast approximate energy minimization via graph cuts. In International Conference for Computer Vision, ICCV99 (Vol. 1, pp. 377–384).
Zurück zum Zitat Bresson, X., Esedognlu, S., Vandergheynst, P., Thiran, J. P., & Osher, S. (2007). Fast global minimization of the active contour/snake model. Journal of Mathematical Imaging and Vision, 2, 151–167.CrossRef Bresson, X., Esedognlu, S., Vandergheynst, P., Thiran, J. P., & Osher, S. (2007). Fast global minimization of the active contour/snake model. Journal of Mathematical Imaging and Vision, 2, 151–167.CrossRef
Zurück zum Zitat Brown, E., Chan, T., & Bresson, X. (2010). A convex approach for multiphase piecewise constant Mumford–Shah image segmentation. Tech. Rep. CAM 09–66, UCLA. Brown, E., Chan, T., & Bresson, X. (2010). A convex approach for multiphase piecewise constant Mumford–Shah image segmentation. Tech. Rep. CAM 09–66, UCLA.
Zurück zum Zitat Bruckstein, A., Netravali, A., & Richardson, T. (1997). Epi-convergence of discrete elastica. Applicable Analysis, 79(1–2), 137–171.MathSciNet Bruckstein, A., Netravali, A., & Richardson, T. (1997). Epi-convergence of discrete elastica. Applicable Analysis, 79(1–2), 137–171.MathSciNet
Zurück zum Zitat Chan, T. F., & Vese, L. A. (2001). Active contours without edges. IEEE Transation on Image Processing, 10(2), 266–277.MATHCrossRef Chan, T. F., & Vese, L. A. (2001). Active contours without edges. IEEE Transation on Image Processing, 10(2), 266–277.MATHCrossRef
Zurück zum Zitat Chung, G., & Vese, L. A. (2005). Energy minimization based segmentation and denoising using a multilayer level set approach. In International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition (pp. 439–455). Chung, G., & Vese, L. A. (2005). Energy minimization based segmentation and denoising using a multilayer level set approach. In International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition (pp. 439–455).
Zurück zum Zitat Collins, D. L., Zijdenbos, A. P., Kollokian, V., Sled, J. G., Kabani, N. J., Holmes, C. J., et al. (1998). Design and construction of a realistic digital brain phantom. IEEE Transactions on Medical Imaging, 17(3), 463–468. Collins, D. L., Zijdenbos, A. P., Kollokian, V., Sled, J. G., Kabani, N. J., Holmes, C. J., et al. (1998). Design and construction of a realistic digital brain phantom. IEEE Transactions on Medical Imaging, 17(3), 463–468.
Zurück zum Zitat Darbon, J., & Sigelle, M. (2005). A fast and exact algorithm for total variation minimization. IbPRIA, 3522(1), 351–359. Darbon, J., & Sigelle, M. (2005). A fast and exact algorithm for total variation minimization. IbPRIA, 3522(1), 351–359.
Zurück zum Zitat Delong, A., & Boykov, Y. (2009). Global optimal segmentation of multi-region objects. In International Conference on Computer Vision (Vol. 1, pp. 26–33). Delong, A., & Boykov, Y. (2009). Global optimal segmentation of multi-region objects. In International Conference on Computer Vision (Vol. 1, pp. 26–33).
Zurück zum Zitat El-Zehiry, N., & Elmaghraby, A. (2008). A graph cut based active contour without edges with relaxed homogeneity constraint. In International Conference on Pattern Recognition (pp. 1–4). El-Zehiry, N., & Elmaghraby, A. (2008). A graph cut based active contour without edges with relaxed homogeneity constraint. In International Conference on Pattern Recognition (pp. 1–4).
Zurück zum Zitat El-Zehiry, N., Xu, S., Sahoo, P., & Elmaghraby, A. (2007). Graph cut optimization for the mumford-shah model. In International Conference on Visualization, Imaging and Image Processing (pp. 182–187). El-Zehiry, N., Xu, S., Sahoo, P., & Elmaghraby, A. (2007). Graph cut optimization for the mumford-shah model. In International Conference on Visualization, Imaging and Image Processing (pp. 182–187).
Zurück zum Zitat El-Zehiry, N., Sahoo, P., & Elmaghraby, A. (2011). Combinatorial optimization of the piecewise constant Mumford–Shah functional with application to scalar/vector valued and volumetric image segmentation. Image and Vision Computing, 29, 365–381.CrossRef El-Zehiry, N., Sahoo, P., & Elmaghraby, A. (2011). Combinatorial optimization of the piecewise constant Mumford–Shah functional with application to scalar/vector valued and volumetric image segmentation. Image and Vision Computing, 29, 365–381.CrossRef
Zurück zum Zitat El-Zehiry, N. Y. (2009). A graph cut framework for two dimensional/three dimensional implicit front propagation with application to the image segmentation problem. PhD thesis, Louisville, KY. El-Zehiry, N. Y. (2009). A graph cut framework for two dimensional/three dimensional implicit front propagation with application to the image segmentation problem. PhD thesis, Louisville, KY.
Zurück zum Zitat El-Zehiry, N. Y., & Elmaghraby, A. (2007). Brain MRI tissue classification using graph cut optimization of the Mumford–Shah functional. In Inernational Vision Conference of New Zealand, New Zealnd (pp. 321–326). El-Zehiry, N. Y., & Elmaghraby, A. (2007). Brain MRI tissue classification using graph cut optimization of the Mumford–Shah functional. In Inernational Vision Conference of New Zealand, New Zealnd (pp. 321–326).
Zurück zum Zitat Grady, L., & Alvino, C. (2009). The piecewise smooth Mumford–Shah functional on an arbitrary graph. IEEE Transaction on Image Processing, 18(11), 2547–2561.MathSciNetCrossRef Grady, L., & Alvino, C. (2009). The piecewise smooth Mumford–Shah functional on an arbitrary graph. IEEE Transaction on Image Processing, 18(11), 2547–2561.MathSciNetCrossRef
Zurück zum Zitat Grady, L., & Polimeni, J. R. (2010). Discrete calculus: Applied analysis on graphs for computational science. New York: Springer.CrossRef Grady, L., & Polimeni, J. R. (2010). Discrete calculus: Applied analysis on graphs for computational science. New York: Springer.CrossRef
Zurück zum Zitat Hammer, P. L., Hansen, P., & Simeone, B. (1984). Roof duality, complementation and persistency in quadratic 01 optimization. Mathematical Programming, 28(2), 121–155.MathSciNetMATHCrossRef Hammer, P. L., Hansen, P., & Simeone, B. (1984). Roof duality, complementation and persistency in quadratic 01 optimization. Mathematical Programming, 28(2), 121–155.MathSciNetMATHCrossRef
Zurück zum Zitat Ishikawa, H. (2003). Exact optimization for Markov random fields with convex priors. IEEE Transaction on Pattern Analysis and Machine Intelligence, 25, 1333–1336.CrossRef Ishikawa, H. (2003). Exact optimization for Markov random fields with convex priors. IEEE Transaction on Pattern Analysis and Machine Intelligence, 25, 1333–1336.CrossRef
Zurück zum Zitat Jeon, M., Alexander, M., Pedrycz, W., & Pizzi, N. (2005). Unsupervised hierarchical image segmentation with level set and additive operator splitting. Pattern Recognition Letters, 26, 1461–1469.CrossRef Jeon, M., Alexander, M., Pedrycz, W., & Pizzi, N. (2005). Unsupervised hierarchical image segmentation with level set and additive operator splitting. Pattern Recognition Letters, 26, 1461–1469.CrossRef
Zurück zum Zitat Kahl, F., & Strandmark, P. (2011). Generalized roof duality for pseudo-boolean optimization. In International Conference on Computer Vision (pp. 255–262). Kahl, F., & Strandmark, P. (2011). Generalized roof duality for pseudo-boolean optimization. In International Conference on Computer Vision (pp. 255–262).
Zurück zum Zitat Kohli, P., Kumar, M. P., & Torr, P. H. S. (2009). P & beyond: Move making algorithms for solving higher order functions. IEEE Transaction on Pattern Analysis and Machine Intelligence, 31(9), 1645–1656.CrossRef Kohli, P., Kumar, M. P., & Torr, P. H. S. (2009). P & beyond: Move making algorithms for solving higher order functions. IEEE Transaction on Pattern Analysis and Machine Intelligence, 31(9), 1645–1656.CrossRef
Zurück zum Zitat Kolmogorov, V. (2003). Graph based algorithms for scene reconstruction from two or more views. PhD thesis, Cornell University. Kolmogorov, V. (2003). Graph based algorithms for scene reconstruction from two or more views. PhD thesis, Cornell University.
Zurück zum Zitat Kolmogorov, V., & Boykov, Y. (2005). What metrics can be approximated by geo-cuts, or global optimization of length/area and flux. In International Conference on Computer Vision, ICCV05 (Vol. 1, pp. 564–571). Kolmogorov, V., & Boykov, Y. (2005). What metrics can be approximated by geo-cuts, or global optimization of length/area and flux. In International Conference on Computer Vision, ICCV05 (Vol. 1, pp. 564–571).
Zurück zum Zitat Kolmogorov, V., & Rother, C. (2007). Minimizing nonsubmodular functions with graph cuts-a review. IEEE Transaction on Pattern Analysis and Machine Intelligence, 29(7), 1274–1279.CrossRef Kolmogorov, V., & Rother, C. (2007). Minimizing nonsubmodular functions with graph cuts-a review. IEEE Transaction on Pattern Analysis and Machine Intelligence, 29(7), 1274–1279.CrossRef
Zurück zum Zitat Kolmogorov, V., & Zabih, R. (2004). What energy functions can be minimized via graph cuts? IEEE Transaction on Pattern Analysis and Machine Intelligence, 26(2), 147–159.CrossRef Kolmogorov, V., & Zabih, R. (2004). What energy functions can be minimized via graph cuts? IEEE Transaction on Pattern Analysis and Machine Intelligence, 26(2), 147–159.CrossRef
Zurück zum Zitat Komodakis, N., & Tziritas, G. (2007). Approximate labeling via graph cuts based on linear programming. IEEE Transaction on Pattern Analysis and Machine Intelligence, 29(8), 1436–1453.CrossRef Komodakis, N., & Tziritas, G. (2007). Approximate labeling via graph cuts based on linear programming. IEEE Transaction on Pattern Analysis and Machine Intelligence, 29(8), 1436–1453.CrossRef
Zurück zum Zitat Kwan, R. S., Evans, A., & Pike, G. (1999). MRI simulation-based evaluation of image-processing and classification methods. IEEE Transactions on Medical Imaging, 18(11), 1085–1097.CrossRef Kwan, R. S., Evans, A., & Pike, G. (1999). MRI simulation-based evaluation of image-processing and classification methods. IEEE Transactions on Medical Imaging, 18(11), 1085–1097.CrossRef
Zurück zum Zitat Lellmann, J., Becker, F., & Schnörr, C. (2009). Convex optimization for multi-class image labeling with a novel family of total variation based regularizers. In International Conference on Computer Vision (pp. 646–653). Lellmann, J., Becker, F., & Schnörr, C. (2009). Convex optimization for multi-class image labeling with a novel family of total variation based regularizers. In International Conference on Computer Vision (pp. 646–653).
Zurück zum Zitat Martin, D., Fowlkes, C., Tal, D., & Malik, J. (2001). A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In International Conference on Computer Vision (Vol. 2, pp. 416–423). Martin, D., Fowlkes, C., Tal, D., & Malik, J. (2001). A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In International Conference on Computer Vision (Vol. 2, pp. 416–423).
Zurück zum Zitat Mumford, D., & Shah, J. (1988). Optimal approximations by piecewise smooth functions and variational problems. Communications of, Pure and Applied Mathematics, XLII(5), 577–685.MathSciNet Mumford, D., & Shah, J. (1988). Optimal approximations by piecewise smooth functions and variational problems. Communications of, Pure and Applied Mathematics, XLII(5), 577–685.MathSciNet
Zurück zum Zitat Ni, K., Hong, B. W., Soatto, S., & Chan, T. (2009). Unsupervised multiphase segmentation: A recursive approach. Computer Vision and Image Understanding, 113(4), 502–510.CrossRef Ni, K., Hong, B. W., Soatto, S., & Chan, T. (2009). Unsupervised multiphase segmentation: A recursive approach. Computer Vision and Image Understanding, 113(4), 502–510.CrossRef
Zurück zum Zitat Osher, S., & Sethian, J. A. (1988). Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton–Jacobi formulations. Journal of Computational Physics, 79(1), 12–49.MathSciNetMATHCrossRef Osher, S., & Sethian, J. A. (1988). Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton–Jacobi formulations. Journal of Computational Physics, 79(1), 12–49.MathSciNetMATHCrossRef
Zurück zum Zitat Pock, T., Schoenemann, T., Graber, G., Bischof, H., & Cremers, D. (2008). A convex formulation of continuous multi-label problems. In European Conference on Computer Vision (pp. 792–805). Pock, T., Schoenemann, T., Graber, G., Bischof, H., & Cremers, D. (2008). A convex formulation of continuous multi-label problems. In European Conference on Computer Vision (pp. 792–805).
Zurück zum Zitat Pock, T., Cremers, D., Bischof, H., & Chambolle, A. (2009). An algorithm for minimizing the Mumford-Shah functional. In International Conference on Computer Vision (pp. 1133–1140). Pock, T., Cremers, D., Bischof, H., & Chambolle, A. (2009). An algorithm for minimizing the Mumford-Shah functional. In International Conference on Computer Vision (pp. 1133–1140).
Zurück zum Zitat Ramalingam, S., Kohli, P., Alahari, K., & Torr, P. H. S. (2008). Exact inference in multi-label CRFs with higher order cliques. In IEEE Conference on Computer Vision and Pattern Recognition (pp. 1–8). Ramalingam, S., Kohli, P., Alahari, K., & Torr, P. H. S. (2008). Exact inference in multi-label CRFs with higher order cliques. In IEEE Conference on Computer Vision and Pattern Recognition (pp. 1–8).
Zurück zum Zitat Rother, C., Kolmogorov, V., Lempitsky, V., & Szummer, M. (2007). Optimizing binary MRFs via extended roof duality. IEEE Conference on Computer Vision and Pattern Recognition, 5302, 248–261. Rother, C., Kolmogorov, V., Lempitsky, V., & Szummer, M. (2007). Optimizing binary MRFs via extended roof duality. IEEE Conference on Computer Vision and Pattern Recognition, 5302, 248–261.
Zurück zum Zitat Simon, H., & Teng, S. H. (2001). How good is recursive bisection? SIAM Journal on Scientific Computing, 18(5), 1436–1445.MathSciNetCrossRef Simon, H., & Teng, S. H. (2001). How good is recursive bisection? SIAM Journal on Scientific Computing, 18(5), 1436–1445.MathSciNetCrossRef
Zurück zum Zitat Vazquez-Reina, A., Miller, E., & Pfister, H. (2009). Multiphase geometric couplings for the segmentation of neural processes. IEEE Conference Computer Vision and, Pattern Recognition (pp. 2020–2027). Vazquez-Reina, A., Miller, E., & Pfister, H. (2009). Multiphase geometric couplings for the segmentation of neural processes. IEEE Conference Computer Vision and, Pattern Recognition (pp. 2020–2027).
Zurück zum Zitat Vese, L. A., & Chan, T. F. (2002). A multiphase level set framework for image segmentation using the Mumford and Shah model. International Journal of Computer Vision, 50(3), 271–293. Vese, L. A., & Chan, T. F. (2002). A multiphase level set framework for image segmentation using the Mumford and Shah model. International Journal of Computer Vision, 50(3), 271–293.
Zurück zum Zitat Wainwright, M., Jaakkola, T., & Willsky, A. (2002). MAP estimation via agreement on (hyper)trees: Message-passing and linear programming approaches. IEEE Transactions on Information Theory, 51, 3697–3717.MathSciNetCrossRef Wainwright, M., Jaakkola, T., & Willsky, A. (2002). MAP estimation via agreement on (hyper)trees: Message-passing and linear programming approaches. IEEE Transactions on Information Theory, 51, 3697–3717.MathSciNetCrossRef
Zurück zum Zitat Yuan, J., Bae, E., Boykov, Y., & Tai, X. C. (2011). A continuous max-flow approach to minimal partitions with label cost prior. In Scale Space and Variational Methods in Computer Vision (pp. 279–290). Yuan, J., Bae, E., Boykov, Y., & Tai, X. C. (2011). A continuous max-flow approach to minimal partitions with label cost prior. In Scale Space and Variational Methods in Computer Vision (pp. 279–290).
Metadaten
Titel
Combinatorial Optimization of the Discretized Multiphase Mumford–Shah Functional
Publikationsdatum
01.09.2013
Erschienen in
International Journal of Computer Vision / Ausgabe 3/2013
Print ISSN: 0920-5691
Elektronische ISSN: 1573-1405
DOI
https://doi.org/10.1007/s11263-013-0617-0

Weitere Artikel der Ausgabe 3/2013

International Journal of Computer Vision 3/2013 Zur Ausgabe