Graph Cuts and Efficient N-D Image Segmentation

Yuri BoykovGareth Funka-Lea

article2006IJCV2,239 citations

Presents an N-dimensional image segmentation framework using binary s/t graph cuts that finds globally optimal object boundaries by efficiently combining region cues, boundary regularization, and user constraints.

Listen

Isolating objects within two-dimensional images and three-dimensional volumetric data is a fundamental requirement across domains such as medical diagnostics, video processing, and digital media editing. Traditional segmentation techniques frequently suffer from severe practical shortcomings: simple heuristic methods often leak across subtle or weak boundaries, while advanced continuous techniques are susceptible to getting trapped in local sub-optimal solutions and can be computationally unpredictable. The article evaluates and demonstrates a combinatorial optimization framework based on network flow graph cuts designed to deliver globally optimal, computationally efficient object extraction across N-dimensional datasets.

To evaluate this framework, the authors tested the approach across diverse practical datasets, including historical photographs, multi-frame video sequences, and complex volumetric medical scans such as cardiac magnetic resonance imaging and computed tomography data of bones, livers, and lungs. The method models data elements as nodes in a graph and balances regional visual cues with boundary continuity costs, using user-placed or automatically initialized seeds to enforce strict region constraints.

Key findings show that the algorithm reliably computes exact global solutions across arbitrary dimensions without numerical convergence issues. The approach supports unrestricted segment topologies, allowing it to seamlessly handle complex shapes, multiple disconnected components, and internal cavities. In performance testing on standard hardware, initial segmentation across standard images and volumes took between less than one second and thirty seconds, while incremental corrections via dynamic graph updates were processed virtually instantaneously in under a second.

These capabilities significantly improve operational workflows by reducing manual editing overhead, improving boundary accuracy, and ensuring repeatable results across complex image analyses. For applications requiring interactive refinement, the framework provides an intuitive mechanism for users to correct segmentation boundaries with minimal additional input, while structured medical tasks can leverage template-based seeding to automate the extraction pipeline.

For future implementation, stakeholders should consider integrating multi-label cut algorithms when simultaneous multi-object extraction is required, while also adopting adaptive color models or flow-based vector constraints to counteract edge-shrinking biases in low-contrast environments. The primary limitations involve memory overhead in very large volumes—which can be mitigated through multi-level banding strategies—and the inability to optimize certain higher-order boundary properties like curvature. Overall, the methodology demonstrates high reliability and robustness for deployment in high-throughput image and volumetric processing systems.

Siemens Corporate Research University of Western Ontario graph cuts graph cut segmentation N-D image segmentation min-cut algorithms

Boykov et al (2006).pdf

Paper: An experimental comparison of min-cut/max- flow algorithms for energy minimization in vision, Yuri Boykov et al. (2001). Reading this benchmarking analysis of min-cut and max-flow algorithms provides essential foundation on the computational engines that power efficient graph-cut image segmentation.
Paper: What energy functions can be minimized via graph cuts?, Vladimir Kolmogorov et al. (2004). Understanding which energy functions are mathematically representable and minimizable via graph cuts is a direct theoretical prerequisite for the broader segmentation framework discussed in the source.

Paper: Efficient Inference in Fully Connected CRFs with Gaussian Edge Potentials, Philipp Krähenbühl et al. (2011). This paper extends the graph-based energy minimization principles of the source by introducing efficient inference for fully connected conditional random fields with Gaussian edge potentials.
Paper: Semantic Image Segmentation with Deep Convolutional Nets and Fully Connected CRFs, Liang-Chieh Chen et al. (2014). Building directly upon the foundational segmentation and CRF concepts established in the source, this work demonstrates how deep convolutional networks and fully connected CRFs combine for semantic image segmentation.

Cover for Graph Cuts and Efficient N-D Image Segmentation

Abstract

Combinatorial graph cut algorithms have been successfully applied to a wide range of problems in vision and graphics. This paper focusses on possibly the simplest application of graph-cuts: segmentation of objects in image data. Despite its simplicity, this application epitomizes the best features of combinatorial graph cuts methods in vision: global optima, practical efficiency, numerical robustness, ability to fuse a wide range of visual cues and constraints, unrestricted topological properties of segments, and applicability to N-D problems. Graph cuts based approaches to object extraction have also been shown to have interesting connections with earlier segmentation methods such as snakes, geodesic active contours, and level-sets. The segmentation energies optimized by graph cuts combine boundary regularization with region-based properties in the same fashion as Mumford-Shah style functionals. We present motivation and detailed technical description of the basic combinatorial optimization framework for image segmentation via s/t graph cuts. After the general concept of using binary graph cut algorithms for object segmentation was first proposed and tested in Boykov and Jolly (2001), this idea was widely studied in computer vision and graphics communities. We provide links to a large number of known extensions based on iterative parameter re-estimation and learning, multi-scale or hierarchical approaches, narrow bands, and other techniques for demanding photo, video, and medical applications.

Topics

graph cuts

Keywords

graph cut segmentation N-D image segmentation min-cut algorithms binary segmentation multi-way cut segmentation energy segmentation boundary active contour models

1. Introduction
1.1. Previous Object Segmentation Methods
1.2. Why Graph Cuts?
Relation to Previous Segmentation Methods.
2. Optimal Object Segmentation via Graph Cuts
2.1. Basic Ideas and Background Information
2.2. Segmentation Energy
2.3. 'Region' vs. 'Boundary'
2.4. Hard Constraints
2.5. Optimal Solution Via Graph Cuts
2.6. Fast Editing of Segments
2.7. Using Directed Edges
3. Experimental Results
3.1. Photo and Video Editing
3.2. Medical Images and Volumes
4. Discussion
Acknowledgements
Notes
References

Knowls

Knowl 1 — Graph Construction for Exact Binary Energy Minimization with Hard Constraints

model/method

To globally minimize the energy functional combining regional and boundary cues subject to user-defined hard constraints (seeds), an $s-t$ graph $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ is constructed over the set of image elements (pixels or voxels) $\mathcal{P}$ and neighborhood system $\mathcal{N}$ .

The node set is defined as: $\mathcal{V} = \mathcal{P} \cup \{S, T\}$ where $S$ is the source node representing the "object" terminal and $T$ is the sink node representing the "background" terminal.

The edge set $\mathcal{E}$ comprises undirected neighborhood edges ( $n$ -links) between adjacent data elements and terminal edges ( $t$ -links) connecting each element $p \in \mathcal{P}$ to both terminals $S$ and $T$ : $\mathcal{E} = \mathcal{N} \cup \bigcup_{p \in \mathcal{P}} \{\{p, S\}, \{p, T\}\}$

Let $\mathcal{O} \subset \mathcal{P}$ and $\mathcal{B} \subset \mathcal{P}$ denote the disjoint sets of pixels marked as object seeds and background seeds, respectively. The edge weights (capacities) are assigned as follows:

Edge	Weight (Cost)	Condition
$\{p, q\}$	$B_{p,q}$	$\{p, q\} \in \mathcal{N}$
$\{p, S\}$	$\lambda \cdot R_p(\text{"bkg"})$	$p \in \mathcal{P}, p \notin \mathcal{O} \cup \mathcal{B}$
$\{p, S\}$	$K$	$p \in \mathcal{O}$
$\{p, S\}$	$0$	$p \in \mathcal{B}$
$\{p, T\}$	$\lambda \cdot R_p(\text{"obj"})$	$p \in \mathcal{P}, p \notin \mathcal{O} \cup \mathcal{B}$
$\{p, T\}$	$0$	$p \in \mathcal{O}$
$\{p, T\}$	$K$	$p \in \mathcal{B}$

where the constant $K$ is set sufficiently large to ensure that hard constraints cannot be severed by a minimal cut: $K = 1 + \max_{p \in \mathcal{P}} \sum_{q: \{p,q\} \in \mathcal{N}} B_{p,q}$

A minimum cost cut on this graph partitions $\mathcal{V}$ into two sets separating $S$ and $T$ , directly yielding the optimal binary segmentation.

Knowl 2 — Global Optimality of Minimum s-t Cut Binary Segmentation
theoretical result
Let $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ be the segmentation graph constructed with terminals $S$ and $T$ , hard constraint seed sets $\mathcal{O}, \mathcal{B} \subset \mathcal{P}$ (where $\mathcal{O} \cap \mathcal{B} = \emptyset$ ), and terminal capacity constant $K = 1 + \max_{p \in \mathcal{P}} \sum_{q: \{p,q\} \in \mathcal{N}} B_{p,q}$ .

A cut $C \subset \mathcal{E}$ is defined as a subset of edges whose removal disconnects $S$ and $T$ . A cut is feasible ( $C \in \mathcal{F}$ ) if it severs exactly one $t$ -link at each pixel $p$ , severs $\{p, q\} \in \mathcal{N}$ if and only if $p$ and $q$ are connected to different terminals, severs $\{p, T\}$ for all $p \in \mathcal{O}$ , and severs $\{p, S\}$ for all $p \in \mathcal{B}$ .

For any feasible cut $C \in \mathcal{F}$ , the associated binary segmentation $A(C)$ is given by: $A_p(C) = \begin{cases} \text{"obj"}, & \text{if } \{p, T\} \in C \\ \text{"bkg"}, & \text{if } \{p, S\} \in C \end{cases}$

The cost of any feasible cut satisfies: $|C| = E(A(C)) - \sum_{p \in \mathcal{O}} \lambda \cdot R_p(\text{"obj"}) - \sum_{p \in \mathcal{B}} \lambda \cdot R_p(\text{"bkg"}) = E(A(C)) - \text{const}$

Every minimum $s-t$ cut $\hat{C}$ on $\mathcal{G}$ is feasible ( $\hat{C} \in \mathcal{F}$ ). Consequently, the segmentation $\hat{A} = A(\hat{C})$ globally minimizes the energy functional: $E(A) = \lambda \cdot R(A) + B(A)$ among all possible binary segmentations $A \in \mathcal{H}$ that satisfy the hard constraints $\forall p \in \mathcal{O}, A_p = \text{"obj"}$ and $\forall p \in \mathcal{B}, A_p = \text{"bkg"}$ .
Knowl 3 — Energy Minimization Formulation for N-D Binary Segmentation
equation
For an arbitrary set of data elements (pixels or voxels) $\mathcal{P}$ in $N$ dimensions and a neighborhood system $\mathcal{N}$ of unordered pairs $\{p, q\}$ , a binary segmentation is defined by an assignment vector $A = (A_1, \dots, A_{|\mathcal{P}|})$ where each $A_p \in \{\text{"obj"}, \text{"bkg"}\}$ .

The segmentation energy function is formulated as: $E(A) = \lambda \cdot R(A) + B(A)$

where $\lambda \ge 0$ is a scalar parameter weighting the relative importance between regional and boundary constraints. The regional term $R(A)$ sums individual pixel labeling penalties: $R(A) = \sum_{p \in \mathcal{P}} R_p(A_p)$ Typically, $R_p(\cdot)$ is derived from the negative log-likelihoods of intensity probability distributions: $R_p(\text{"obj"}) = -\ln \Pr(I_p \mid \text{"obj"})$ $R_p(\text{"bkg"}) = -\ln \Pr(I_p \mid \text{"bkg"})$ where $I_p$ is the observed intensity (or feature vector) at pixel $p$ .

The boundary regularization term $B(A)$ penalizes label discontinuities between neighboring pixels: $B(A) = \sum_{\{p,q\} \in \mathcal{N}} B_{p,q} \cdot \delta_{A_p \neq A_q}$ where $\delta_{A_p \neq A_q} = 1$ if $A_p \neq A_q$ and $0$ otherwise, and $B_{p,q} \ge 0$ specifies the penalty for assigning different labels to adjacent elements $p$ and $q$ .
Knowl 4 — Intensity-Gradient Discontinuity Penalty for Spatial Boundary Regularization
equation
The boundary discontinuity penalty $B_{p,q} \ge 0$ between neighboring data elements $p$ and $q$ under a neighborhood system $\mathcal{N}$ is formulated as a decreasing function of image intensity contrast and spatial distance:

$B_{p,q} \propto \exp\left(-\frac{(I_p - I_q)^2}{2\sigma^2}\right) \cdot \frac{1}{\text{dist}(p, q)}$

where:
- $I_p$ and $I_q$ denote the image intensities at elements $p$ and $q$ .
- $\text{dist}(p, q)$ is the spatial Euclidean distance between $p$ and $q$ .
- $\sigma$ is a scaling parameter representing the camera/sensor noise level among neighboring pixels.
When $|I_p - I_q| < \sigma$ , the exponential penalty is large, strongly penalizing segmentation boundaries through homogeneous regions. When $|I_p - I_q| > \sigma$ , the penalty drops toward zero, encouraging the segmentation cut to align with high-gradient intensity edges.
Knowl 5 — Incremental Flow Re-computation for Interactive Hard Constraint Editing
algorithm
When a user adds or alters hard constraint seeds after an initial segmentation has been computed, the optimal solution can be updated efficiently by reusing the pre-existing residual flow without recomputing the maximum flow from scratch.

Decreasing an edge capacity directly can violate flow conservation if flow already traverses that edge. To avoid capacity reductions when converting an unconstrained pixel $p$ into an object seed ( $p \in \mathcal{O}$ ), a positive constant $c_p$ is added to both $t$ -links of $p$ , which leaves the cut minimization invariant while ensuring capacities only increase.
Input: Residual flow graph $G$ from previous solution, newly marked object seed $p \in \mathcal{O}$
Output: Updated globally optimal segmentation $A$
Set $c_p = \lambda \cdot R_p(\text{"bkg"})$
Increase capacity of t-link $\{p, S\}$ by $K + \lambda \cdot R_p(\text{"obj"})$
Increase capacity of t-link $\{p, T\}$ by $c_p$
Continue augmenting paths in max-flow algorithm from current residual state until graph is saturated
Determine minimum cut $\hat{C}$ from saturated edges
return Segmentation $\hat{A} = A(\hat{C})$
Knowl 6 — Directed Graph Cut Formulation for Asymmetric Boundary Penalties and Flux Alignment
model/method
The graph cuts segmentation framework extends to directed graphs, enabling asymmetric edge weights between adjacent pixels depending on transition direction.

For a neighborhood system $\mathcal{N}$ composed of ordered pairs $(p, q)$ , the directed boundary energy is formulated as: $B(A) = \sum_{(p,q) \in \mathcal{N}} B_{(p,q)} \cdot \delta_{A_p=\text{"obj"}, A_q=\text{"bkg"}}$

where $B_{(p,q)}$ is the penalty incurred specifically when pixel $p$ is labeled as object and pixel $q$ as background. This allows boundary costs to depend on the sign of the intensity difference $(I_p - I_q)$ rather than solely its absolute value. For instance, to favor transitions from bright object tissue to dark background tissue while penalizing transitions from dark to bright, weights can be assigned as: $w_{(p,q)} = \begin{cases} 1, & \text{if } I_p \le I_q \\ \exp\left(-\frac{(I_p - I_q)^2}{2\sigma^2}\right), & \text{if } I_p > I_q \end{cases}$

Exact minimization via $s-t$ graph cuts is guaranteed as long as directed edge penalties satisfy submodularity: $B_{(p,q)} + B_{(q,p)} \ge 0$ Geometrically, this directed formulation corresponds to optimizing the flux of a vector field across the segmentation boundary.
Knowl 7 — Multi-Object Segmentation Formulation via Multi-Way Graph Cuts
model/method
The binary graph cut segmentation model generalizes to simultaneous multi-object extraction by extending the two-terminal graph to a multi-terminal graph with a set of terminals representing labels $\{\text{obj}_1, \text{obj}_2, \dots, \text{obj}_M\}$ .

The multi-label segmentation energy over assignment vector $A \in \{\text{obj}_1, \dots, \text{obj}_M\}^{|\mathcal{P}|}$ is defined as: $E(A) = \lambda \sum_{p \in \mathcal{P}} R_p(A_p) + \sum_{\{p,q\} \in \mathcal{N}} B_{p,q}(A_p, A_q) \cdot \delta_{A_p \neq A_q}$

where $R_p(A_p)$ denotes the likelihood penalty of assigning label $A_p$ to pixel $p$ , and $B_{p,q}(A_p, A_q)$ defines label-dependent discontinuity costs between neighboring pixels. User seeds of different label categories are implemented by setting infinite-capacity $t$ -links to the corresponding target terminal.

Although finding the exact minimum multi-way cut for $M > 2$ terminals is NP-hard, provably good approximations are computed efficiently using the $\alpha$ -expansion algorithm.
Knowl 8 — Empirical Segmentation Speed and Topological Freedom Across 2D and 3D Modalities
empirical result
The combinatorial $s-t$ graph cut framework, using a 4-neighborhood system in 2D and a 26-neighborhood system in 3D evaluated on a 1.4 GHz Pentium III, achieved the following benchmark performance characteristics across domains:
- 2D Photographs: Initial segmentation on images up to $1000 \times 1000$ pixels completed in under 1 second using boundary terms alone ( $\lambda = 0$ ). Correcting seed additions updated the cut almost instantaneously.
- Video Object Extraction: A 21-frame video sequence ( $255 \times 189$ resolution) treated as a single 3D spatio-temporal volume was segmented in 3 to 5 seconds from seeds placed in only 1 to 5 frames, with corrections updating within 1 second.
- 3D Medical CT/MRI Volumes: Segmentation of volumetric structures (such as a $256 \times 256 \times 119$ bone CT volume, a $170 \times 170 \times 144$ liver CT volume, and a $55 \times 80 \times 32$ multi-phase kidney MRI) completed in 10 to 30 seconds for initial solves and under 1 second for subsequent interactive seed corrections.
- Topological Invariance: The implicit representation naturally captured complex and unconstrained topologies, successfully segmenting structures consisting of multiple disconnected components as well as components containing internal holes without requiring explicit topology preservation mechanisms.
Knowl 9 — Shrinking Bias and Second-Order Boundary Modeling Limitations of Graph Cuts
limitation
The standard graph cut segmentation framework has two primary modeling limitations:
1. Boundary Shrinking Bias: Minimizing boundary regularization terms based on pairwise $n$ -links geometrically corresponds to minimizing the metric length (in 2D) or surface area (in 3D) of the boundary. This creates a systematic preference for shorter boundaries over longer, geometrically accurate ones (a "shrinking" bias). This bias must be counteracted by incorporating strong regional bias terms or directed vector-field flux.
2. Restriction to First-Order Cliques: Standard graph cuts are restricted to submodular pairwise pixel interactions ( $n$ -links) and cannot directly optimize second-order geometric boundary properties, such as curvature. Modeling curvature or higher-order shape properties requires higher-order (e.g., triple-clique) interactions, which are generally not optimizable via exact two-terminal minimum $s-t$ cuts.

Coverage note — None was omitted; all core theoretical formulations, graph constructions, optimality proofs, dynamic algorithms, directed/multi-way extensions, empirical performance metrics, and stated limitations are fully covered.

References

1.Amini, A.A., Weymouth, T.E., and Jain, R.C. 1990. Using dynamic programming for solving variational problems in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence, 12(9):855–867.
2.Appleton, B. and Talbot, H. 2006. Globally minimal surfaces by continuous maximal flows. IEEE transactions on Pattern Analysis and Pattern Recognition (PAMI), 28(1):106–118.
3.Blake, A., Rother, C., Brown, M., Perez, P., and Torr, P. 2004. Interactive image segmentation using an adaptive gmmrf model. In European Conference on Computer Vision (ECCV), Prague, Chech Republic.
4.Boykov, Y. and Kolmogorov, V. 2003. Computing geodesics and minimal surfaces via graph cuts. In International Conference on Computer Vision, vol. I, pp. 26–33.
5.Boykov, Y., Veksler, O., and Zabih, R. 1998. Markov random fields with efficient approximations. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 648–655.
6.Boykov, Y. and Jolly, M.-P. 2001. Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images. In International Conference on Computer Vision, vol. I, pp. 105–112, July 2001.
7.Boykov, Y. and 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.
8.Boykov, Y., Kolmogorov, V., Cremers, D., and Delong, A. 2006. An integral solution to surface evolution PDEs via geo-cuts. In European Conference on Computer Vision, LNCS 3953, Graz, Austria, vol. III, pp. 409–422.
9.Boykov, Y. and Veksler, O. 2006. Graph cuts in vision and graphics: Theories and applications. In: N. Paragios, Y. Chen, and O. Faugeras, (Eds.), Handbook of Mathematical Models in Computer Vision, Springer-Verlag, pp. 79–96.
10.Boykov, Y., Veksler, O., and Zabih, R. 2001. Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(11):1222–1239.
11.Bray, M., Kohli, P., and Torr, P.H.S. 2006. Posecut: Simultaneous segmentation and 3D pose estimation of humans using dynamic graph-cuts. In European Conference on Computer Vision, Graz, Austria, May 2006, (to appear).
12.Caselles, V., Kimmel, R., and Sapiro, G. 1997. Geodesic active contours. International Journal of Computer Vision, 22(1):61–79.
13.Cohen, L.D. 1991. On active contour models and ballons. Computer Vision, Graphics, and Image Processing: Image Understanding, 53(2):211–218.
14.Cohen, L.D. and Kimmel, R. 1997. Global minimum for active contour models: A minimal path approach. International Journal of Computer Vision, 24(1):57–78.
15.Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., and Schrijver, A. 1998. Combinatorial Optimization. John Wiley & Sons.
16.Cox, I.J., Rao, S.B., and Zhong, Y. 1996. “Ratio regions”: a technique for image segmentation. In International Conference on Pattern Recognition, vol. II, pp. 557–564.
17.Cremers, D. 2006. Dynamical statistical shape priors for level set based tracking. IEEE Trans. on Pattern Analysis and Machine Intelligence, (to appear).
18.Cremers, D., Osher, S.J., and Soatto, S. 2006. Kernel density estimation and intrinsic alignment for shape priors in level set segmentation. International Journal of Computer Vision, (to appear).
19.Falcão, A.X., Udupa, J.K., Samarasekera, S., and Sharma, S. 1998. User-steered image segmentation paradigms: Live wire and live lane. Graphical Models and Image Processing, 60:233–260.
20.Felzenszwalb, P. and Huttenlocher, D. 2004. Efficient graph-based image segmentation. International Journal of Computer Vision, 59(2):167–181.
21.Ford, L. and Fulkerson, D. 1962. Flows in Networks. Princeton University Press.
22.Funka-Lea, G., Boykov, Y., Florin, C., Jolly, M.-P., Moreau-Gobard, R., Ramaraj, R., and Rinck, D. 2006. Automatic heart isolation for CT coronary visualization using graph-cuts. In IEEE International Symposium on Biomedical Imaging, Arlington, VA, April 2006.
23.Geiger, D., Gupta, A., Costa, L.A., and Vlontzos, J. 1995. Dynamic programming for detecting, tracking, and matching deformable contours. IEEE Transactions on Pattern Analysis and Machine Intelligence, 17(3):294–402.
24.Goldberg, A.V. and Tarjan, R.E. 1988. A new approach to the maximum-flow problem. Journal of the Association for Computing Machinery, 35(4):921–940.
25.Grady, L. 2005. Multilabel random walker segmentation using prior models. In IEEE Conference of Computer Vision and Pattern Recognition, San Diego, CA, June 2005, vol. 1, pp. 763–770.
26.Greig, D., Porteous, B., and Seheult, A. 1989. Exact maximum a posteriori estimation for binary images. Journal of the Royal Statistical Society, Series B, 51(2):271–279.
27.Griffin, L.D., Colchester, A.C.F., Röll, S.A., and Studholme, C.S. 1994. Hierarchical segmentation satisfying constraints. In British Machine Vision Conference, pp. 135–144.
28.Haralick, R.M. and Shapiro, L.G. 1992. Computer and Robot Vision. Addison-Wesley Publishing Company.
29.Hochbaum, D.S. 1998. The pseudoflow algorithm for the maximum flow problem. Manuscript, UC Berkeley, revised 2003, Extended abstract in: The pseudoflow algorithm and the pseudoflow-based simplex for the maximum flow problem. Proceedings of IPCO98, June 1998. Lecture Notes in Computer Science, Bixby, Boyd and Rios-Mercado (Eds.) 1412, Springer, pp. 325–337.
30.Isard, M. and Blake, A. 1998. Active contours. Springer-Verlag.
31.Ishikawa, H. and Geiger, D. 1998. Occlusions, discontinuities, and epipolar lines in stereo. In 5th European Conference on Computer Vision, pp. 232–248.
32.Ishikawa, H. and Geiger, D. 1998. Segmentation by grouping junctions. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 125–131.
33.Ishikawa, H. 2003. Exact optimization for Markov Random Fields with convex priors. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(10):1333–1336.
34.Jermyn, I.H. and Ishikawa, H. 1999. Globally optimal regions and boundaries. In International Conference on Computer Vision, vol. II, pp. 904–910.
35.Juan, O. and Boykov, Y. 2006. Active Graph Cuts. In IEEE Conference of Computer Vision and Pattern Recognition, 2006 (to appear).
36.Kass, M., Witkin, A., and Terzolpoulos, D. 1988. Snakes: Active contour models. International Journal of Computer Vision, 1(4):321–331.
37.Kimmel, R. and Bruckstein, A.M. 2003. Regularized Laplacian zero crossings as optimal edge integrators. International Journal of Computer Vision, 53(3):225–243.
38.Kirsanov, D. and Gortler, S.J. 2004. A discrete global minimization algorithm for continuous variational problems. Harvard Computer Science Technical Report, TR-14-04, July 2004, (also submitted to a journal).
39.Kleinberg, J. 2002. An impossibility theorem for clustering. In The 16th conference on Neural Information Processing Systems (NIPS).
40.Kohli, P. and Torr, P.H.S. 2005. Efficiently solving dynamic markov random fields using graph cuts. In International Conference on Computer Vision.
41.Kohli, P. and Torr, P.H.S. 2006. Measuring uncertainty in graph cut solutions—efficiently computing min-marginal energies using dynamic graph cuts. In European Conference on Computer Vision, Graz, Austria, May 2006 (to appear).
42.Kolmogorov, V. and 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, Beijing, China, vol. I, pp. 564–571.
43.Kolmogorov, V., Criminisi, A., Blake, A., Cross, G., and Rother, C. 2005. Bi-layer segmentation of binocular stereo video. In IEEE Conference of Computer Vision and Pattern Recognition, San Diego, CA.
44.Kolmogorov, V. and Zabih, R. 2002. Multi-camera scene reconstruction via graph cuts. In 7th European Conference on Computer Vision, volume III of LNCS 2352, pp. 82–96, Copenhagen, Denmark, May 2002. Springer-Verlag.
45.Kolmogorov, V. and Zabih, R. 2004. What energy functions can be minimized via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(2):147–159.
46.Kumar, M.P., Torr, P.H.S., and Objcut, A.Z. 2005. In IEEE Conference of Computer Vision and Pattern Recognition, pp. 18–25.
47.Kwatra, V., Schodl, A., Essa, I., and Bobick, A. 2003. GraphCut textures: image and video synthesis using graph cuts. In ACM Transactions on Graphics (SIGGRAPH), vol. 22, July 2003.
48.Lempitsky, V., Boykov, Y., and Ivanov, D. 2006. Oriented visibility for multiview reconstruction. In European Conference on Computer Vision, Graz, Austria, May 2006 (to appear).
49.Li, K., Wu, X., Chen, D.Z., and Sonka, M. 2006. Optimal surface segmentation in volumetric images-a graph-theoretic approach. IEEE transactions on Pattern Analysis and Pattern Recognition (PAMI), 28(1):119–134.
50.Li, Y., Sun, J., and Shum, H.-Y. 2005. Video object cut and paste. In SIGGRAPH (ACM Transaction on Graphics),
51.Li, Y., Sun, J., Tang, C.-K., and Shum, H.-Y. 2004. Lazy snapping. In SIGGRAPH (ACM Transaction on Graphics).
52.Lombaert, H., Sun, Y., Grady, L., and Xu, C. 2005. A multilevel banded graph cuts method for fast image segmentation. In International Conference on Computer Vision, October 2005.
53.Mortensen, E.N. and Barrett, W.A. 1998. Interactive segmentation with intelligent scissors. Graphical Models and Image Processing, 60:349–384.
54.Mumford, D. and Shah, J. 1989. Optimal approximations by piecewise smooth functions and associated variational problems. Comm. Pure Appl. Math., 42:577–685.
55.Murota, K. 2003. Discrete Convex Analysis. SIAM Monographs on Discrete Mathematics and Applications.
56.Osher, S. and Paragios, N. 2003. Geometric Level Set Methods in Imaging, Vision, and Graphics. Springer Verlag.
57.Osher, S.J. and Fedkiw, R.P. 2002. Level Set Methods and Dynamic Implicit Surfaces. Springer Verlag.
58.Reese, L.J. 1999. Intelligent paint: Region-based interactive image segmentation. Master’s thesis, Brigham Young University.
59.Rother, C., Kolmogorov, V., and Blake, A. 2004. Grabcut—interactive foreground extraction using iterated graph cuts. In ACM Transactions on Graphics (SIGGRAPH).
60.Rother, C., Kumar, S., Kolmogorov, V., and Blake, A. 2005. Digital tapestry. In IEEE Conference of Computer Vision and Pattern Recognition, San Diego, CA.
61.Roy, S. and Cox, I. 1998. A maximum-flow formulation of the n-camera stereo correspondence problem. In IEEE Proc. of Int. Conference on Computer Vision, pp. 492–499.
62.Sapiro, G. 2001. Geometric Partial Differential Equations and Image Analysis. Cambridge University Press.
63.Scharstein, D. and Szeliski, R. 2002. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. International Journal of Computer Vision, 47(1/3):7–42.
64.Sethian, J.A. 1999. Level Set Methods and Fast Marching Methods. Cambridge University Press.
65.Shi, J. and Malik, J. 2000. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888–905.
66.Szeliski, R. and Zabih, R. 1999. An experimental comparison of stereo algorithms. In Vision Algorithms: Theory and Practice, number 1883 in LNCS, pp. 1–19, Springer-Verlag, Corfu, Greece, September 1999.
67.Vasilevskiy, A. and Siddiqi, K. 2002. Flux maximizing geometric flows. PAMI, 24(12):1565–1578.
68.Veksler, O. 2000. Image segmentation by nested cuts. In IEEE Conference on Computer Vision and Pattern Recognition, vol. 1, pp. 339–344.
69.Vogiatzis, G., Torr, P.H.S., and Cipolla, R. 2005. Multi-view stereo via volumetric graph-cuts. In IEEE Conference of Computer Vision and Pattern Recognition, pp. 391–398.
70.Wang, J., Bhat, P., Colburn, R.A., Agrawala, M., and Cohen, M.F. 2005. Interactive video cutout. In SIGGRAPH (ACM Transaction on Graphics).
71.Wu, Z. and Leahy, R. 1993. 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.
72.Xu, N., Bansal, R., and Ahuja, N. 2003. Object segmentation using graph cuts based active contours. In IEEE Conference on Computer Vision and Pattern Recognition, vol. II, pp. 46–53.
73.Yezzi, A., Jr., Kichenassamy, S., Kumar, A., Olver, P., and Tannenbaum, A. 1997. A geometric snake model for segmentation of medical imagery. IEEE Transactions on Medical Imaging, 16(2):199–209.
74.Zhu, S.C. and Yuille, A. 1996. 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.

Citation

MLA

Boykov, Y., and G. Funka-Lea. “Graph Cuts and Efficient N-D Image Segmentation”. International Journal of Computer Vision, vol. 70, no. 2, 2006, pp. 109–31, https://doi.org/10.1007/s11263-006-7934-5.

APA

Boykov, Y., & Funka-Lea, G. (2006). Graph Cuts and Efficient N-D Image Segmentation. International Journal of Computer Vision, 70(2), 109–131. https://doi.org/10.1007/s11263-006-7934-5

Chicago

Boykov, Y., and G. Funka-Lea. 2006. “Graph Cuts and Efficient N-D Image Segmentation”. International Journal of Computer Vision 70 (2): 109–31. https://doi.org/10.1007/s11263-006-7934-5.

Harvard

Boykov, Y. and Funka-Lea, G. (2006) “Graph Cuts and Efficient N-D Image Segmentation”, International Journal of Computer Vision, 70(2), pp. 109–131. Available at: https://doi.org/10.1007/s11263-006-7934-5.

Vancouver

1. Boykov Y, Funka-Lea G (2006) Graph Cuts and Efficient N-D Image Segmentation. International Journal of Computer Vision 70:109–131

BibTeX

@article{Boykov_2006, title={Graph Cuts and Efficient N-D Image Segmentation}, volume={70}, ISSN={1573-1405}, url={http://dx.doi.org/10.1007/s11263-006-7934-5}, DOI={10.1007/s11263-006-7934-5}, number={2}, journal={International Journal of Computer Vision}, publisher={Springer Science and Business Media LLC}, author={Boykov, Yuri and Funka-Lea, Gareth}, year={2006}, month=Nov, pages={109–131} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Graph Cuts and Efficient N-D Image Segmentation

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Graph Construction for Exact Binary Energy Minimization with Hard Constraints

Knowl 2 — Global Optimality of Minimum s-t Cut Binary Segmentation

Knowl 3 — Energy Minimization Formulation for N-D Binary Segmentation

Knowl 4 — Intensity-Gradient Discontinuity Penalty for Spatial Boundary Regularization

Knowl 5 — Incremental Flow Re-computation for Interactive Hard Constraint Editing

Knowl 6 — Directed Graph Cut Formulation for Asymmetric Boundary Penalties and Flux Alignment

Knowl 7 — Multi-Object Segmentation Formulation via Multi-Way Graph Cuts

Knowl 8 — Empirical Segmentation Speed and Topological Freedom Across 2D and 3D Modalities

Knowl 9 — Shrinking Bias and Second-Order Boundary Modeling Limitations of Graph Cuts

References

Citation

BibTeX

Access the Paper