Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
International Journal of Computer Vision
Erschienen in: International Journal of Computer Vision 3/2013

01.09.2013

Discrete and Continuous Models for Partitioning Problems

verfasst von: Jan Lellmann, Björn Lellmann, Florian Widmann, Christoph Schnörr

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

Recently, variational relaxation techniques for approximating solutions of partitioning problems on continuous image domains have received considerable attention, since they introduce significantly less artifacts than established graph cut-based techniques. This work is concerned with the sources of such artifacts. We discuss the importance of differentiating between artifacts caused by discretization and those caused by relaxation and provide supporting numerical examples. Moreover, we consider in depth the consequences of a recent theoretical result concerning the optimality of solutions obtained using a particular relaxation method. Since the employed regularizer is quite tight, the considered relaxation generally involves a large computational cost. We propose a method to significantly reduce these costs in a fully automatic way for a large class of metrics including tree metrics, thus generalizing a method recently proposed by Strekalovskiy and Cremers (IEEE conference on computer vision and pattern recognition, pp. 1905–1911, 2011).
Vorheriger Artikel A Survey and Comparison of Discrete and Continuous Multi-label Optimization Approaches for the Potts Model
Nächster Artikel Combinatorial Optimization of the Discretized Multiphase Mumford–Shah Functional

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Literatur
Ambrosio, L., Fusco, N., & Pallara, D. (2000). Functions of bounded variation and free discontinuity problems. Oxford: Clarendon Press.MATH
Appleton, B., & Talbot, H. (2006). Globally minimal surfaces by continuous maximal flows. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28, 106–118.CrossRef
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, 112–129.MathSciNetMATHCrossRef
Bartal, Y. (1998). On approximating arbitrary metrices by tree metrics. In ACM symposium on theory of computing.
Bertsekas, D. P. (1998). Network optimization: Continuous and discrete models. Belmont, MA: Athena Scientific.MATH
Blake, A., & Zisserman, A. (1987). Visual reconstruction. Cambridge: MIT Press.
Boykov, Y. (2003). Computing geodesics and minimal surfaces via graph cuts. In The international conference on computer vision (pp. 26–33).
Boykov, Y., Veksler, O., & Zabih, R. (2001). Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(11), 1222–1239.CrossRef
Braides, A. (2002). Gamma-convergence for beginners. Oxford: Oxford University Press.MATHCrossRef
Călinescu, G., Karloff, H., & Rabani, Y. (2000). An improved approximation algorithm for multiway cut. Journal of Computer and System Sciences, 60, 564–574.MathSciNetMATHCrossRef
Caselles, V., Kimmel, R., & Sapiro, G. (1997). Geodesic active contours. International Journal of Computer Vision, 22, 61–79.MATHCrossRef
Chambolle, A. (1999). Finite-differences discretizations of the Mumford–Shah functional. Modélisation Mathématique et Analyse Numérique, 33, 261–288.MathSciNetMATHCrossRef
Chambolle, A., & Darbon, J. (2009). On total variation minimization and surface evolution using parametric maximum flows. International Journal of Computer Vision, 84, 288–307.CrossRef
Chambolle, A., Levine, S. E., & Lucier, B. J. (2011). An upwind finite-difference method for total variation-based image smoothing. Journal of Imaging Science, 4(1), 277–299.MathSciNetMATHCrossRef
Chan, T. F., Esedoglu, S., & Nikolova, M. (2006). Algorithms for finding global minimizers of image segmentation and denoising models. Journal of Applied Mathematics, 66(5), 1632–1648.MathSciNetMATH
Chan, T. F., & Vese, L. A. (2001). Active contours without edges. IEEE Transactions on Image Processing, 10(2), 266–277.MATHCrossRef
Charikar, M., Chekuri, C., Goel, A., Guha, S., & Plotkin, S. (1998). Approximating a finite metric by a small number of tree metrics. In ACM Foundations on Computer Science (pp. 379–388).
Combettes, P. L., & Pesquet, J. C. (2010). Proximal splitting methods in signal processing. In Fixed-point algorithms for inverse problems in science and engineering. New York: Springer.
Couprie, C., Grady, L., Najman, L., & Talbot, H. (2011). Power watersheds: A unifying graph-based optimization framework. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(7), 1384–1399.CrossRef
Couprie, C., Grady, L., Talbot, H., & Najman, L. (2011). Combinatorial continuous maximum flow. Journal of Imaging Science, 4(3), 905–930.MathSciNetMATHCrossRef
Dahlhaus, E., Johnson, D. S., Papadimitriou, C. H., & Seymour, P. D. (1994). The complexity of multiterminal cuts. Journal of Computing, 23(4), 864–894.MathSciNetMATH
Dal Maso G. (1993). An introduction to \(\Gamma \)-convergence. Basel: Birkhäuser.
De Giorgi, E., & Franzoni, T. (1975). Su un tipo di convergenza variazionale. Atti Accad. Naz. Lincei Rend Cl. Sci. Fis. Mat. Natur., 68, 842–850.
Dixit, N., Keriven, R., & Paragios, N. (2005). GPU-cuts: Combinatorial optimisation, graphic processing units and adaptive object extraction. Tech. Rep. 05–07, CERTIS, ENPC.
Esser, E., Zhang, X., & Chan, T. F. (2010). A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. Journal of Imaging Science, 3, 1015–1046.
Fakcharoenphol, J., Rao, S., & Talwar, K. (2004). A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences, 69(3), 485–497.MathSciNetMATHCrossRef
Faugeras, O., & Luong, Q. T. (2001). The geometry of multiple images. Cambridge: MIT Press.MATH
Geman, S., & Geman, D. (1984). Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6, 721–741.MATHCrossRef
Gobbino, M., & Mora, M. G. (2001). Finite-difference approximation of free-discontinuity problems. Proceedings of the Royal Society of Edinburgh, 131, 567–595.
Goldluecke, S., & Cremers, D. (2010). Convex relaxation for multilabel problems with product label spaces. In European conference of computer vision (pp. 225–238).
Goldschlager, L. M., Shaw, R. A., & Staples, J. (1982). The maximum flow problem is log space complete for P. Theoretical Computer Science, 21, 105–111.MathSciNetMATHCrossRef
Grady, L. J., & Polimeni, J. R. (2010). Discrete calculus: Applied analysis on graphs for computational science. New York: Springer.CrossRef
Hartley, R., & Zisserman, A. (2000). Multiple view geometry in computer vision. Cambridge: Cambridge University Press.MATH
Ising, E. (1925). Beitrag zur Theorie des Ferromagnetismus. Zeitschrift fur Physik, 31(1), 253–258.CrossRef
Kass, M., Witkin, A., & Terzopoulos, D. (1987). Snakes: Active contours models. International Journal of Computer Vision, 1(4), 321–331.CrossRef
Kleinberg, J. M., & Tardos, E. (1999). Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields. In Foundations of computer science (pp. 14–23).
Klodt, M., Schoenemann, T., Kolev, K., Schikora, M., & Cremers, D. (2008). An experimental comparison of discrete and continuous shape optimization methods. In European conference of computer vision (pp. 332–345). France: Marseille.
Koller, D., & Friedman, N. (2009). Probabilistic graphical models: Principles and techniques. Cambridge, MA: MIT Press.
Kolmogorov, V., & Boykov, Y. (2005). What metrics can be approximated by geo-cuts, or global optimization of length/area and flux. International conference on computer vision (Vol. 1, pp. 564–571).
Komodakis, N., & Tziritas, G. (2007). Approximate labeling via graph cuts based on linear programming. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(8), 1436–1453.CrossRef
Lauritzen, S. (1996). Graphical models. Oxford: Oxford University Press.
Lellmann, J. (2011). Nonsmooth convex variational approaches to image analysis. Ph.D. thesis, University of Heidelberg.
Lellmann, J., Breitenreicher, D., & Schnörr, C. (2010). Fast and exact primal-dual iterations for variational problems in computer vision. In European conference on computer vision. LNCS (vol. 6312, pp. 494–505). Berlin: Springer.
Lellmann, J., Kappes, J., Yuan, J., Becker, F., & Schnörr, C. (2009). Convex multi-class image labeling by simplex-constrained total variation. In Scale space and variable methods. LNCS (Vol. 5567, pp. 150–162). Berlin: Springer.
Lellmann, J., Lenzen, F., & Schnörr, C. (2011). Optimality bounds for a variational relaxation of the image partitioning problem. In Energy minimization methods and applications in computer vision and pattern recognition.
Lellmann, J., Lenzen, F., & Schnörr, C. (2012). Optimality bounds for a variational relaxation of the image partitioning problem. Journal of Mathematical Imaging and Vision. doi:10.​1007/​s10851-012-0390-7.
Lellmann, J., & Schnörr, C. (2011). Continuous multiclass labeling approaches and algorithms. Journal of Imaging Science, 4(4), 1049–1096.
Lempitsky, V., Rother, C., & Blake, A. (2007). Logcut—Efficient graph cut optimization for Markov random fields. In European conference on computer vision (pp. 1–8).
Lempitsky, V., Rother, C., Roth, S., & Blake, A. (2010). Fusion moves for Markov random field optimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(8), 1392–1405.
Lie, J., Lysaker, M., & Tai, X. C. (2006). A variant of the level set method and applications to image segmentation. Mathematics of Computation, 75, 1155–1174.
Morel, J. M., & Solimini, S. (1995). Variational methods in image segmentation. Basel: Birkhäuser.CrossRef
Mumford, D., & Shah, J. (1989). Optimal approximations by piecewise smooth functions and associated variational problems. Communications on Pure and Applied Mathematics, 42, 577–685.MathSciNetMATHCrossRef
Olsson, C. (2009). Global optimization in computer vision: Convexity, cuts and approximation algorithms. Ph.D. thesis, Lund University.
Olsson, C., Byröd, M., Overgaard, N. C., & Kahl, F. (2009). Extending continuous cuts: Anisotropic metrics and expansion moves. In International conference on computer vision.
Paragios, N., Chen, Y., & Faugeras, O. (Eds.). (2006). The handbook of mathematical models in computer vision. New York: Springer.
Pock, T., Chambolle, A., Cremers, D., & Bischof, H. (2009). A convex relaxation approach for computing minimal partitions. In Computer vision on pattern recognition (pp. 810–817).
Pock, T., Schönemann, T., Graber, G., Bischof, H., & Cremers, D. (2008). A convex formulation of continuous multi-label problems. In European conference on computer vision (Vol. 3, pp. 792–805).
Rickett, J., & Fomel, S. (1999). A second-order fast marching Eikonal solver. Tech. Rep. 100, Standford Exploration Project Report.
Scherzer, O., Grasmair, M., Grossauer, H., Haltmeier, M., & Lenzen, F. (2009). Variational Methods in Imaging. Applied Mathematical Sciences (Vol. 167). Berlin: Springer.
Sinop, A. K., & Grady, L. (2007). A seeded image segmentation framework unifying graph cuts and random walker which yields a new algorithm. In International conference on computer vision (pp. 1–8).
Strekalovskiy, E., & Cremers, D. (2011). Total variation for cyclic structures: Convex relaxation and efficient minimization. In Conference on computer vision and pattern recognition (pp. 1905–1911).
Strekalovskiy, E., Goldluecke, B., & Cremers, D. (2011). Tight convex relaxations for vector-valued labeling problems. In International conference on computer vision (pp. 2328–2335).
Trobin, W., Pock, T., Cremers, D., & Bischof, H. (2008). Continuous energy minimization by repeated binary fusion. In European conference on computer vision (Vol. 4, pp. 667–690).
Zach, C., Gallup, D., Frahm, J. M., & Niethammer, M. (2008). Fast global labeling for real-time stereo using multiple plane sweeps. In Vision, modeling, and visualization.
Metadaten
Titel
Discrete and Continuous Models for Partitioning Problems
verfasst von
Jan Lellmann
Björn Lellmann
Florian Widmann
Christoph Schnörr
Publikationsdatum
01.09.2013
Verlag
Springer US
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-0621-4

Weitere Artikel der Ausgabe 3/2013

International Journal of Computer Vision 3/2013 Zur Ausgabe

OriginalPaper

A Variational Approach to Video Registration with Subspace Constraints

OriginalPaper

Optimization of Robust Loss Functions for Weakly-Labeled Image Taxonomies

OriginalPaper

A Survey and Comparison of Discrete and Continuous Multi-label Optimization Approaches for the Potts Model

OriginalPaper

Combinatorial Optimization of the Discretized Multiphase Mumford–Shah Functional

EditorialNotes

Guest Editorial: Energy Optimization Methods

OriginalPaper

A Distributed Mincut/Maxflow Algorithm Combining Path Augmentation and Push-Relabel