12.20 Image Segmentation with Graph Cuts

Problem

Suppose you have an image and want to separate the foreground from the background.

Examples include:

Removing a background from a photograph
Identifying tumors in medical images
Detecting roads in satellite imagery
Isolating objects in computer vision systems
Separating products from backgrounds in e-commerce photos

At first glance, image segmentation appears completely unrelated to network flow.

An image consists of pixels. Maximum flow works on graphs.

The surprising discovery is that image segmentation can be modeled as a minimum-cut problem.

In fact, graph-cut methods became one of the most influential applications of network flow outside traditional optimization.

Solution

Represent the image as a graph.

Each pixel becomes a vertex.

Add:

source
sink

The source represents:

foreground

The sink represents:

background

Then assign edge capacities that encode:

Pixel likelihoods
Similarity between neighboring pixels
User constraints

A minimum cut produces the segmentation.

Pixels on the source side become foreground.

Pixels on the sink side become background.

Basic Graph Construction

For each pixel:

create a vertex.

Add two special vertices:

S
T

where:

S = foreground
T = background

The graph looks like:

S
|
pixels
|
T

with many additional connections between neighboring pixels.

Data Terms

Suppose a pixel strongly resembles foreground.

Example:

foreground probability = 0.9
background probability = 0.1

Add:

S -> pixel
large capacity

and:

pixel -> T
small capacity

The minimum cut prefers keeping the pixel connected to the source.

Similarly, a background-looking pixel receives:

S -> pixel
small capacity

pixel -> T
large capacity

These are called data terms.

They measure how likely a pixel belongs to each class.

Smoothness Terms

Neighboring pixels often belong to the same object.

Consider:

pixel A
pixel B

with nearly identical colors.

Add an undirected similarity connection:

A <-> B

modeled as two directed edges.

Large capacity means:

do not separate these pixels

Small capacity means:

separation is acceptable

These edges are called smoothness terms.

They encourage coherent regions.

Example

Image:

dark dark dark
dark bright bright
dark bright bright

Suppose bright pixels likely belong to the object.

Data terms connect:

bright pixels -> source

with high capacity.

Dark pixels connect:

background sink

with high capacity.

Neighbor edges connect adjacent pixels.

The minimum cut naturally forms the boundary between bright and dark regions.

Why Minimum Cut Works

Every cut divides pixels into:

foreground side
background side

Cutting a source edge means:

assign pixel to background

Cutting a sink edge means:

assign pixel to foreground

Cutting neighbor edges means:

separate adjacent pixels

The total cut capacity measures segmentation quality.

A minimum cut therefore finds the best segmentation according to the model.

Energy Formulation

Graph-cut segmentation minimizes an energy:

Energy
=
Data Cost
+
Smoothness Cost

Data cost:

How well labels match pixel appearance

Smoothness cost:

Penalty for neighboring pixels
receiving different labels

The graph construction converts this optimization into a minimum-cut problem.

Small Example

Three pixels:

P1
P2
P3

Foreground likelihood:

Pixel	Foreground	Background
P1	8	1
P2	7	2
P3	2	9

Source edges:

Edge	Capacity
S -> P1	8
S -> P2	7
S -> P3	2

Sink edges:

Edge	Capacity
P1 -> T	1
P2 -> T	2
P3 -> T	9

Neighbor edges:

P1 <-> P2
P2 <-> P3

capacity:

Minimum cut yields:

P1 foreground
P2 foreground
P3 background

which matches intuition.

User-Guided Segmentation

Many interactive systems allow users to mark:

definitely foreground
definitely background

pixels.

These constraints are encoded with infinite-capacity edges.

Foreground seed:

S -> pixel
capacity = INF

Background seed:

pixel -> T
capacity = INF

The minimum cut must respect these labels.

This idea powered classic interactive segmentation tools.

GrabCut

One of the most famous graph-cut applications is:

entity["software","GrabCut","Interactive image segmentation algorithm"]

The algorithm alternates between:

Estimating color models.
Building a graph.
Computing minimum cuts.
Refining the segmentation.

Graph cuts provide the optimization engine.

The result is often surprisingly accurate even with limited user input.

Neighborhood Structures

Pixels may connect using:

4-Neighborhood

up
down
left
right

Each pixel has four neighbors.

8-Neighborhood

up
down
left
right
diagonals

Each pixel has eight neighbors.

Eight-neighborhood models generally produce smoother boundaries.

Similarity Weights

Neighbor capacities are often:

exp(
    -(color difference)^2
      / (2σ²)
)

Properties:

Similar colors produce large capacities.
Different colors produce small capacities.

This encourages cuts to follow strong image boundaries.

Example Boundary Detection

Suppose:

pixel A = black
pixel B = black

Difference:

Edge capacity:

very large

The cut avoids separating them.

Suppose:

pixel A = black
pixel B = white

Difference:

large

Edge capacity:

small

The cut can pass between them cheaply.

Thus object boundaries emerge naturally.

Min-Cut Interpretation

After computing max flow:

reachable from source

means:

foreground

Not reachable:

background

This is exactly the same reachability rule used throughout the chapter.

The only difference is how capacities are assigned.

Complexity

If:

N = number of pixels

then:

vertices ≈ N
edges ≈ 4N or 8N

depending on the neighborhood model.

Modern max-flow algorithms handle surprisingly large images efficiently.

Push-relabel methods are particularly popular in graph-cut segmentation.

Beyond Binary Segmentation

Basic graph cuts solve:

foreground
vs
background

For:

sky
road
tree
car
building

multiple labels are needed.

Several extensions exist:

Alpha-expansion
Alpha-beta swap
Multiway cuts
Markov random fields

Many still rely on repeated minimum-cut computations.

Applications

Medical Imaging

Segment tumors, organs, and blood vessels.

Satellite Analysis

Identify roads, rivers, forests, and urban areas.

Computer Vision

Object extraction and scene understanding.

Photography

Background removal and compositing.

Manufacturing

Defect detection and quality inspection.

Autonomous Vehicles

Road and obstacle segmentation.

Common Mistakes

Ignoring Smoothness Terms

Using only source and sink edges produces noisy segmentations.

Overweighting Smoothness

Large smoothness penalties may erase object boundaries.

Using Poor Foreground Models

The minimum cut can only optimize the graph provided.

Bad probability estimates produce bad segmentations.

Choosing Small Infinity Values

User constraints should never be violated.

Use capacities larger than any possible finite cut.

Discussion

Image segmentation demonstrates the remarkable reach of network flow theory. A problem that appears entirely visual becomes a graph optimization problem once pixels are interpreted as vertices and segmentation quality is expressed as edge capacities.

The same minimum-cut machinery used for communication networks, transportation systems, and project selection can separate objects from backgrounds in photographs.

This is one of the most elegant examples of algorithmic modeling.

Takeaway

Graph-cut image segmentation models pixels as graph vertices, foreground and background as terminals, and segmentation quality as cut capacity. A minimum cut simultaneously balances data fidelity and boundary smoothness, producing high-quality segmentations.

More importantly, it illustrates a recurring lesson throughout this chapter: many seemingly unrelated optimization problems become solvable once they are transformed into network flow models.

Chapter Summary

In this chapter, you explored the core theory and applications of network flow:

Flow networks and residual graphs
Ford-Fulkerson and augmenting paths
Edmonds-Karp and shortest augmenting paths
Dinic's algorithm and blocking flows
Push-relabel and preflows
Minimum cuts and the max-flow min-cut theorem
Bipartite matching and Hopcroft-Karp
Assignment problems and the Hungarian algorithm
Minimum-cost flow and circulation
Lower bounds and vertex capacities
Edge-disjoint and vertex-disjoint paths
Project selection and graph cuts
Image segmentation with minimum cuts

Together, these techniques form one of the most powerful modeling toolkits in algorithm design. Problems involving allocation, scheduling, routing, matching, planning, reliability, optimization, and segmentation often reduce to a flow network. Once the reduction is found, decades of algorithmic research become available to solve the problem efficiently.