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
Erschienen in:
Buchtitelbild

2015 | OriginalPaper | Buchkapitel

Object Segmentation and Markov Random Fields

verfasst von : Y Boykov, PhD

Erschienen in: Handbook of Biomedical Imaging

Verlag: Springer US

Einloggen

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

search-config
loading …

Abstract

This chapter discusses relationships between graph cut approach to object delineation and other standard techniques optimizing segmentation boundaries. Graph cut method is presented in the context of globally optimal labeling of binary Markov Random Fields (MRFs). We review algorithms details and show several 2D and 3D examples.

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 "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

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
Nächstes Kapitel Fuzzy methods in medical imaging
Fußnoten
1
Impossibility theorem in [38] shows that no clustering algorithm can simultaneously satisfy three basic axioms on scale-invariance, richness, and consistency. Thus, any clustering method has some bias.
 
2
If necessary, one can build a graph with resolution finer than the pixel grid.
 
3
[20] can be seen as a hierarchical version of standard push-relabel method [26].
 
4
[37] is a notable exception.
 
5
A typed or hand-written letter is an example of a binary image. Restoration of such an image may involve removal of a salt and pepper noise.
 
6
Each pair of connected nodes on a directed graph is linked by two distinct (directed) edges (p, q) and (q, p). Directed edges can be useful in applications (see Sect. 3.3).
 
Literatur
1.
A. A. Amini, T. E. Weymouth, and R. C. Jain. Using dynamic programming for solving variational problems in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence, 12(9):855–867, September 1990.CrossRef
2.
B. Appleton and H. Talbot. Globally minimal surfaces by continuous maximal flows. IEEE transactions on Pattern Analysis and Pattern Recognition (PAMI), 28(1):106–118, January 2006.
3.
A. Blake. The least-disturbance principle and weak constraints. Pattern Recognition Letters, 1:393–399, 1983.CrossRef
4.
A. Blake, C. Rother, M. Brown, P. Perez, and P. Torr. Interactive image segmentation using an adaptive gmmrf model. In European Conference on Computer Vision (ECCV), Prague, Chech Republic, 2004.
5.
A. Blake and A. Zisserman. Visual Reconstruction. Cambridge, 1987.
6.
E. Boros and P. L. Hammer. Pseudo-boolean optimization. Discrete Applied Mathematics, 123(1-3):155–225, November 2002.
7.
Y. Boykov and G. Funka-Lea. Graph cuts and efficient N-D image segmentation. International Journal of Computer Vision (IJCV), 70(2):109–131, 2006.
8.
Y. Boykov and M.-P. Jolly. Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images. In International Conference on Computer Vision, volume I, pages 105–112, July 2001.
9.
Y. Boykov and V. Kolmogorov. Computing geodesics and minimal surfaces via graph cuts. In International Conference on Computer Vision, volume I, pages 26–33, 2003.
10.
Y. Boykov and V. Kolmogorov. 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, September 2004.CrossRef
11.
Y. Boykov, V. Kolmogorov, D. Cremers, and A. Delong. An integral solution to surface evolution PDEs via geo-cuts. In European Conference on Computer Vision, Graz, Austria, May 2006 (to appear).
12.
Y. Boykov and O. Veksler. Graph cuts in vision and graphics: Theories and applications. In N. Paragios, Y. Chen, and O. Faugeras, editors, Handbook of Mathematical Models in Computer Vision, pages 79–96. Springer-Verlag, 2006.
13.
Y. Boykov, O. Veksler, and R. Zabih. Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(11):1222–1239, November 2001.CrossRef
14.
V. Caselles, R. Kimmel, and G. Sapiro. Geodesic active contours. International Journal of Computer Vision, 22(1):61–79, 1997.CrossRefMATH
15.
A. Chambolle. Total variation minimization and a class of binary MRF models. pages 136–152, 2005.
16.
T. Chan, S. Esedoglu, and M. Nikolova. Algorithms for finding global minimizers of image segmentation and denoising models. SIAM Journal on Applied Mathematics, 66(5):1632–1648, 2006.CrossRefMATHMathSciNet
17.
T. Chan and L. Vese. Active contours without edges. IEEE Trans. Image Processing, 10(2):266–277, 2001.CrossRefMATH
18.
L. D. Cohen. On active contour models and ballons. Computer Vision, Graphics, and Image Processing: Image Understanding, 53(2):211–218, 1991.MATH
19.
W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver. Combinatorial Optimization. John Wiley & Sons, 1998.
20.
A. Delong. A Scalable Max-Flow/Min-Cut Algorithm for Sparse Graphs. MS thesis, University of Western Ontario, 2006.
21.
A. X. Falcão , J. K. Udupa, S. Samarasekera, and S. Sharma. User-steered image segmentation paradigms: Live wire and live lane. Graphical Models and Image Processing, 60:233–260, 1998.
22.
P. Felzenszwalb and D. Huttenlocher. Efficient graph-based image segmentation. International Journal of Computer Vision, 59(2):167–181, 2004.CrossRef
23.
L. Ford and D. Fulkerson. Flows in Networks. Princeton University Press, 1962.
24.
B. Geiger and R. Kikinis. Simulation of endoscopy. In CVRMed, pages 277–281, 1995.
25.
D. Geiger, A. Gupta, L. A. Costa, and J. Vlontzos. Dynamic programming for detecting, tracking, and matching deformable contours. IEEE Transactions on Pattern Analysis and Machine Intelligence, 17(3):294–402, March 1995.CrossRef
26.
A. V. Goldberg and R. E. Tarjan. A new approach to the maximum flow problem. Journal of the Association for Computing Machinery, 35(4):921–940, October 1988.CrossRefMATHMathSciNet
27.
L. Grady. Multilabel random walker segmentation using prior models. In IEEE Conference of Computer Vision and Pattern Recognition, volume 1, pages 763–770, San Diego, CA, June 2005.
28.
D. Greig, B. Porteous, and A. Seheult. Exact maximum a posteriori estimation for binary images. Journal of the Royal Statistical Society, Series B, 51(2):271–279, 1989.
29.
P. L. Hammer. Some network flow problems solved with pseudoboolean programming. Operations Research, 13:388–399, 1965.CrossRefMathSciNet
30.
M. Isard and A. Blake. Active contours. Springer-Verlag, 1998.
31.
H. Ishikawa. Exact optimization for Markov Random Fields with convex priors. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(10):1333–1336, 2003.CrossRef
32.
H. Ishikawa and D. Geiger. Segmentation by grouping junctions. In IEEE Conference on Computer Vision and Pattern Recognition, pages 125–131, 1998.
33.
I. H. Jermyn and H. Ishikawa. Globally optimal regions and boundaries as minimum ratio weight cycles. PAMI, 23(10):1075–1088, October 2001.CrossRef
34.
O. Juan and Y. Boykov. Active graph cuts. In IEEE Conference of Computer Vision and Pattern Recognition, volume I, pages 1023–1029, 2006.
35.
O. Juan and Y. Boykov. Accelerating graph cuts in vision via capacity scaling. In International Conference on Computer Vision, 2007.
36.
M. Kass, A. Witkin, and D. Terzolpoulos. Snakes: Active contour models. International Journal of Computer Vision, 1(4):321–331, 1988.CrossRef
37.
D. Kirsanov and S. J. Gortler. A discrete global minimization algorithm for continuous variational problems. Harvard Computer Science Technical Report, TR-14-04, July 2004, (also submitted to a journal).
38.
J. Kleinberg. An impossibility theorem for clustering. In The 16th conference on Neural Information Processing Systems (NIPS), 2002.
39.
P. Kohli and P. H. Torr. Efficiently solving dynamic markov random fields using graph cuts. In International Conference on Computer Vision, October 2005.
40.
V. Kolmogorov and Y. Boykov. What metrics can be approximated by geo-cuts, or global optimization of length/area and flux. In International Conference on Computer Vision, October 2005.
41.
V. Kolmogorov, Y. Boykov, and C. Rother. Applications of parametric maxflow in computer vision. In International Conference on Computer Vision (ICCV), Nov. 2007.
42.
V. Kolmogorov, A. Criminisi, A. Blake, G. Cross, and C. Rother. Bilayer segmentation of binocular stereo video. In IEEE Conference of Computer Vision and Pattern Recognition, San Diego, CA, 2005.
43.
V. Kolmogorov and C. Rother. Minimizing non-submodular functions with graph cuts - a review. PAMI, 29(7), July 2007.
44.
V. Kolmogorov and R. Zabih. Computing visual correspondence with occlusions via graph cuts. In International Conference on Computer Vision, July 2001.
45.
V. Kolmogorov and R. Zabih. Multi-camera scene reconstruction via graph cuts. In 7th European Conference on Computer Vision, volume III of LNCS 2352, pages 82–96, Copenhagen, Denmark, May 2002. Springer-Verlag.
46.
V. Lempitsky and Y. Boykov. Global optimization for shape fitting. In IEEE Conference of Computer Vision and Pattern Recognition, June 2007.
47.
V. Lempitsky, Y. Boykov, and D. Ivanov. Oriented visibility for multiview reconstruction. In European Conference on Computer Vision, Graz, Austria, May 2006 (to appear).
48.
K. Li, X. Wu, D. Z. Chen, and M. Sonka. Optimal surface segmentation in volumetric images-a graph-theoretic approach. IEEE transactions on Pattern Analysis and Pattern Recognition (PAMI), 28(1):119–134, January 2006.
49.
H. Lombaert, Y. Sun, L. Grady, and C. Xu. A multilevel banded graph cuts method for fast image segmentation. In International Conference on Computer Vision, October 2005.
50.
E. N. Mortensen and W. A. Barrett. Interactive segmentation with intelligent scissors. Graphical Models and Image Processing, 60:349–384, 1998.CrossRefMATH
51.
D. Mumford and J. Shah. Optimal approximations by piecewise smooth functions and associated variational problems. Comm. Pure Appl. Math., 42:577–685, 1989.CrossRefMATHMathSciNet
52.
S. J. Osher and R. P. Fedkiw. Level Set Methods and Dynamic Implicit Surfaces. Springer Verlag, 2002.
53.
54.
C. Rother, V. Kolmogorov, and A. Blake. Grabcut interactive foreground extraction using iterated graph cuts. In ACM Transactions on Graphics (SIGGRAPH), August 2004.
55.
C. Rother, S. Kumar, V. Kolmogorov, and A. Blake. Digital tapestry. In IEEE Conference of Computer Vision and Pattern Recognition, San Diego, CA, June 2005.
56.
S. Roy. Stereo without epipolar lines: A maximum-flow formulation. International Journal of Computer Vision, 34(2/3):147–162, August 1999.CrossRef
57.
S. Roy and I. Cox. A maximum-flow formulation of the n-camera stereo correspondence problem. In IEEE Proc. of Int. Conference on Computer Vision, pages 492–499, 1998.
58.
G. Sapiro. Geometric Partial Differential Equations and Image Analysis. Cambridge University Press, 2001.
59.
J. Sethian. Level Set Methods and Fast Marching Methods. Cambridge University Press, 1999.
60.
J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888–905, August 2000.CrossRef
61.
62.
A. Vasilevskiy and K. Siddiqi. Flux maximizing geometric flows. PAMI, 24(12):1565–1578, December 2002.CrossRef
63.
O. Veksler. Image segmentation by nested cuts. In IEEE Conference on Computer Vision and Pattern Recognition, volume 1, pages 339–344, 2000.
64.
G. Vogiatzis, P. Torr, and R. Cipolla. Multi-view stereo via volumetric graph-cuts. In IEEE Conference of Computer Vision and Pattern Recognition, pages 391–398, 2005.
65.
S. Wang and J. M. Siskind. Image segmentation with ratio cut. 25(6):675–690, June 2003.
66.
R. Whitaker. Reducing aliasing artifacts in iso-surfaces of binary volumes. pages 23–32, 2000.
67.
Z. Wu and R. Leahy. An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15(11):1101–1113, November 1993.CrossRef
68.
A. Yezzi, Jr., S. Kichenassamy, A. Kumar, P. Olver, and A. Tannenbaum. A geometric snake model for segmentation of medical imagery. IEEE Transactions on Medical Imaging, 16(2):199–209, 1997.CrossRef
69.
S. C. Zhu and A. Yuille. Region competition: Unifying snakes, region growing, and Bayes/MDL for multiband image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(9):884–900, September 1996.CrossRef
Metadaten
Titel
Object Segmentation and Markov Random Fields
verfasst von
Y Boykov, PhD
Copyright-Jahr
2015
Verlag
Springer US
Buch
Handbook of Biomedical Imaging

Print ISBN: 978-0-387-09748-0

Electronic ISBN: 978-0-387-09749-7

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-0-387-09749-7_1

Premium Partner

    Bildnachweise