nach oben

International Journal of Computer Vision

Erschienen in:

01.09.2013

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

verfasst von: Claudia Nieuwenhuis, Eno Töppe, Daniel Cremers

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

KI-gestützte Suche

Aus

Abstract

We present a survey and a comparison of a variety of algorithms that have been proposed over the years to minimize multi-label optimization problems based on the Potts model. Discrete approaches based on Markov Random Fields as well as continuous optimization approaches based on partial differential equations can be applied to the task. In contrast to the case of binary labeling, the multi-label problem is known to be NP hard and thus one can only expect near-optimal solutions. In this paper, we carry out a theoretical comparison and an experimental analysis of existing approaches with respect to accuracy, optimality and runtime, aimed at bringing out the advantages and short-comings of the respective algorithms. Systematic quantitative comparison is done on the Graz interactive image segmentation benchmark. This paper thereby generalizes a previous experimental comparison (Klodt et al. 2008) from the binary to the multi-label case.

Vorheriger Artikel Guest Editorial: Energy Optimization Methods

Nächster Artikel Discrete and Continuous Models for Partitioning Problems

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

In Komodakis and Tziritas (2005) several algorithms are proposed for different choices of parameters \(h_i\). In this paper we use the \(\alpha \)-expansion equivalence of FastPD (called \(\text{ PD2 }_{\mu = 1}\) by Komodakis and Tziritas) since it corresponds to the Potts model.

http://vision.csd.uwo.ca/code/

http://www.csd.uoc.gr/~komod/FastPD/

Alahari, K., Kohli, P., & Torr, P. H. S. (2010). Dynamic hybrid algorithms for MAP inference in discrete MRFs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(10), 1846–1857.CrossRef

Batra, D. (2011). Making the right moves: Guiding alpha-expansion using local primal-dual gaps. In P. Kohli (Ed.), International Conference on Computer Vision and Pattern Recognition, Colorado Springs.

Besag, J. (1986). On the statistical analysis of dirty pictures. Journal of Royal Statistical Society Series B, 48(3), 259–302.MathSciNetMATH

Boykov, Y., & Kolmogorov, V. (2004). An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(9), 1124–1137.CrossRef

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

Chambolle, A., Cremers, D., Pock, T. (2008). A convex approach for computing minimal partitions. Technical Report TR-2008-05. Bonn: University of Bonn.

Chan, T., & Esedoglu, S., & Nikolova, M., (2006). Algorithms for finding global minimizers of image segmentation and denoising models. SIAM Journal on Applied Mathematics, 66(5), 1632–1648.

Chan, T., & Vese, L. (2001). Active contours without edges. IEEE Transactions on Image Processing, 10(2), 266–277.MATHCrossRef

Cremers, D., Rousson, M., & Deriche, R. (2007). A review of statistical approaches to level set segmentation: Integrating color, texture, motion and shape. International Journal of Computer Vision, 72(2), 195–215.CrossRef

Cremers, D., Sochen, N., & Schnörr, C. (2004). Multiphase dynamic labeling for variational recognition-driven image segmentation. In T. Pajdla & V. Hlavac (Eds.), European Conference on Computer Vision volume of 3024 LNCS (pp. 74–86). New York: Springer.

Cremers, D., Sochen, N., & Schnörr, C. (2006). A multiphase dynamic labeling model for variational recognition-driven image segmentation. International Journal of Computer Vision, 66(1), 67–81.

Felzenszwalb, P., & Veksler, O. (2010). Tiered scene labeling with dynamic programming. In International Conference on Computer Vision and Pattern Recognition, San Francisco.

Geman, S., & Geman, D. (1984). Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6(6), 721–741.MATHCrossRef

Goldschlager, L., Shaw, R., & Staples, J. (1982). The maximum flow problem is log space complete for P. Theoretical Computer Science, 21, 105–111.MathSciNetMATHCrossRef

Greig, D. M., Porteous, B. T., & Seheult, A. H. (1989). Exact maximum a posteriori estimation for binary images. Journal of Royal Statistical Society Series B, 51(2), 271–279.

Ishikawa, H. (2003). Exact optimization for Markov random fields with convex priors. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(10), 1333–1336.CrossRef

Kleinberg, J., & Tardos, E. (2002). Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields. Journal of the ACM, 49(5), 672–713 .

Klodt, M., Schoenemann, T., Kolev, K., Schikora, M., & Cremers, D. (2008). An experimental comparison of discrete and continuous shape optimization methods. In European Conference on Computer Vision, Marseille, France.

Kolev, K., Pock, T., & Cremers, D. (2010). Anisotropic minimal surfaces integrating photoconsistency and normal information for multiview stereo. In European Conference on Computer Vision, Crete.

Kolmogorov, V. (2006). Convergent tree-reweighted message passing for energy minimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28, 1568–1583.CrossRef

Komodakis, N., & Tziritas, G. (2005). A new framework for approximate labeling via graph cuts. In IEEE International Conference on Computer Vision, New Orleans.

Komodakis, N., Tziritas, G., & Paragios, N. (2007). Fast, approximately optimal solutions for single and dynamic MRFs. In International Conference on Computer Vision and Pattern Recognition, Ezhou.

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 IEEE International Conference on Computer Vision (pp. 646–653).

Lellmann, J., Kappes, J. H., Yuan, J., Becker, F., & Schnörr, C. (2009). Convex multi-class image labeling by simplex-constrained total variation. Scale Space and Variational Methods in Computer Vision (SSVM), 5567, 150–162.CrossRef

Lellmann, J., Lenzen, F., & Schnörr, C. (2011). Optimality bounds for a variational relaxation of the image partitioning problem. In International Conference on Energy Minimization Methods for Computer Vision and Pattern Recognition. New York: Springer.

Lempitsky, V., Rother, C., & Blake, A. (2007). Logcut: Efficient graph cut optimization for Markov random fields. In IEEE International Conference on Computer Vision.

Liu, X., Veksler, O., & Samarabandu, J. (2010). Order preserving moves for graph cut based optimization. IEEE Transaction on Pattern Analysis and Machine Intellignece, 32(7), 1317–1324.

Michelot, C. (1986). A finite algorithm for finding the projection of a point onto the canonical simplex of \(R^n\). Journal of Optimization Theory and Applications, 50(1), 189–193.

Mumford, D., & Shah, J. (1989). Optimal approximation by piecewise smooth functions and associated variational problems. Communications on Pure and Applied Mathematics, 42, 577–685.MathSciNetMATHCrossRef

Nieuwenhuis, C., & Cremers, D. (2012). Spatially varying color distributions for interactive multi-label segmentation. In IEEE Transactions on Pattern Analysis and Machine Intelligence, Philadelphia.

Nieuwenhuis, C., & Töppe, E., & Cremers, D. (2011). Space-varying color distributions for interactive multiregion segmentation: Discrete versus continuous approaches. In International Conference on Energy Minimization Methods for Computer Vision and Pattern Recognition, New York.

Osokin, A., Vetrov, D., & Kolmogorov, V. (2011). Submodular decomposition framework for inference in associative markov networks with global constraints. In International Conference on Computer Vision and Pattern Recognition, St. Petersburg.

Pearl, J. (1988). Probabilistic reasoning in intelligent systems. San Mateo: Morgan Kauffmann.

Pock, T., & Chambolle, A. (2011). Diagonal preconditioning for first order primal-dual algorithms in convex optimization. In IEEE International Conference on Computer Vision, Barcelona.

Pock, T., Cremers, D., Bischof, H., & Chambolle, A. (2009). An algorithm for minimizing the piecewise smooth Mumford-Shah functional. In IEEE International Conference on Computer Vision, Kyoto.

Pock, T., Cremers, D., Bischof, H., & Chambolle, A. (2010). Global solutions of variational models with convex regularization. SIAM Journal of Imaging Sciences, 3(4), 1122–1145.MathSciNetMATHCrossRef

Santner, J. (2010). Interactive multi-label segmentation. Ph.D. thesis, University of Graz, Graz.

Schlesinger, M. I. (1976). Sintaksicheskiy analiz dvumernykh zritelnikh signalov v usloviyakh pomekh (syntactic analysis of two-dimensional visual signals in noisy conditions). Kibernetika, 4, 113–130. (in Russian).

Strekalovskiy, E., & Cremers, D. (2011). Generalized ordering constraints for multilabel optimization. In IEEE International Conference on Computer Vision, Barcelona.

Szeliski, R., Zabih, R., Scharstein, D., Veksler, O., Kolmogorov, V., Agarwala, A., Tappen, M., & Rother, C. (2006). A comparative study of energy minimization methods for Markov random fields. In European Conference on Computer Vision, volume 3952 of, Lecture Notes in Computer Science, Graz (pp. 16–29).

Tsai, A., Yezzi, A., Wells, W., Tempany, C., Tucker, D., & Fan, A., et al. (2001). Model-based curve evolution technique for image segmentation. In Computer Vision Pattern Recognition, Kauai, Hawaii (pp. 463–468).

Veksler, O. (2007). Graph cut based optimization for MRFs with truncated convex priors. In International Conference on Computer Vision and Pattern Recognition, Beijing.

Veksler, O. (2009). Multi-label moves for MRFs with truncated convex priors. In International Conference on Energy Minimization Methods for Computer Vision and Pattern Recognition, Bonn.

Wainwright, M., Jaakkola, T., & Willsky, A. (2005). Map estimation via agreement on (hyper)trees: Message-passing and linear-programming approaches. IEEE Transactions on Information Theory, 51, 3697–3717.

Werner, T. (2007). A linear programming approach to maxsum problem: A review. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(7), 1165–1179.

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 workshop (VMV), Konstanz.

Zach, C., Häne, C., & Pollefeys, M. (2012). What is optimized in tight convex relaxations for multi-label problems? In International Conference on Computer Vision and Pattern Recognition, Lund Sweden.

Zach, C., Niethammer, M., & Frahm, J. M. (2009). Continuous maximal flows and Wulff shapes: Application to MRFs. In International Conference on Computer Vision and Pattern Recognition, Bonn.

Titel: A Survey and Comparison of Discrete and Continuous Multi-label Optimization Approaches for the Potts Model
verfasst von: Claudia Nieuwenhuis
Eno Töppe
Daniel Cremers
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-0619-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2013

A Variational Approach to Video Registration with Subspace Constraints

Guest Editorial: Energy Optimization Methods

Combinatorial Optimization of the Discretized Multiphase Mumford–Shah Functional

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

Optimization of Robust Loss Functions for Weakly-Labeled Image Taxonomies

Discrete and Continuous Models for Partitioning Problems