Image Segmentation

Normalized Cuts + Graph Cuts

Highly demonstrative slides for naive learners

Big idea
An image can be treated as a graph: Cut the graph so that meaningful
pixels are nodes, similarity is edge objects or regions separate clearly.
weight.

Two tools
Normalized Cuts: balanced graph partition.
Graph Cuts: energy minimization with source/sink labels.

01
Roadmap
First understand the graph idea, then learn two ways of cutting it.

1. Image → Graph 2. Weights 3. Cut 4. Normalized Cuts 5. Graph Cuts

Each pixel/superpixel Strong similarity = strong Remove weak links between Avoid tiny isolated partitions. Minimize label energy using
becomes a node. connection. groups. source/sink graph.

logic
Final ability
Given a small graph, we should be able to identify strong
first see this as coloured squares. groups, weak bridges, and the likely segmentation
boundary.

which squares are strongly connected?

02
Why Use Graph-Based Segmentation?
Some boundaries are not obvious from intensity alone.

Thresholding asks
“Is this pixel brighter than T?”
Works only when objects have clearly
different brightness.

Region methods ask

“Is this local area homogeneous?”
May create blocky or local decisions.

Graph methods ask

“Which pixels are strongly connected as a
whole?”
Can use global relationships.

Graph view: dense connections inside objects, weak connections between

objects.

03
Image as a Graph: The Basic Conversion
Pixels or superpixels become nodes; similarities become edges.

Node
A pixel, group of pixels, or superpixel. For large images, superpixels
reduce computation.

Edge
A connection between two nodes. Nearby similar pixels get
stronger edges.

Weight
A number that says how similar two nodes are. High weight = hard
to separate.

Simple rule: cut weak bridges, preserve strong communities.

04
Edge Weights: How Similar Are Two Pixels?
A graph only becomes useful after we define similarity.

Fᵢ − Fⱼ Xᵢ − Xⱼ exp(−distance)
Difference in colour, intensity, texture or Difference in spatial position: how far the Small difference gives weight near 1; large
other image features. pixels are in the image. difference gives weight near 0.

Case Meaning Weight

Same colour + nearby Very strong connection High

Same colour + far apart Maybe related, but weaker spatial link Medium

Different colour + nearby Likely boundary between regions Low

05
What Does a “Cut” Mean?
A cut removes edges to split the graph into groups.

8
2

7
1

4 10
3 9

5
11
6 12

Inside-group edges Between-group edges Cut cost

Strong edges should remain uncut. They Weak bridges are good candidates for the cut. Sum of weights of edges crossing the partition.
represent similar pixels.

cut(A,B) = Σ w(i,j) for edges crossing A | B

06
Minimum Cut Alone Can Be Misleading
A plain min-cut may isolate a tiny weakly connected node.

a
c x

Low cost, but poor segmentation: one tiny node is separated.

Better idea: prefer groups that are internally meaningful and

reasonably balanced.

Problem: min cut only asks “what is cheapest to remove?”

07
Normalized Cut: The Key Correction
Normalize the cut by how strongly each group is connected to the whole graph.

Ncut(A,B) = cut(A,B) / assoc(A,V) + cut(A,B) / assoc(B,V)

cut(A,B) assoc(A,V) Normalization

Total weight of edges crossing between A and B. Total connection from group A to all nodes in the Small isolated groups get penalized because
graph. their association is small.

Ncut: “remove weak edges but keep

Plain cut: “remove the cheapest edges.”
groups meaningful.”

08
Toy Calculation: Why Normalization Helps
Students can calculate this example by hand.

Case A: isolate one weak node Case B: split two real communities
cut = 1 cut = 3
assoc(small group,V) = 2 assoc(group A,V) = 35
assoc(rest,V) = 42 assoc(group B,V) = 33

Ncut = 1/2 + 1/42 = 0.524 Ncut = 3/35 + 3/33 = 0.177

Even though the cut is cheap, the normalized score is not good. A larger cut can be better when both groups are well supported.

Important lesson: lower Ncut means a more meaningful partition.

09
Spectral Intuition: Eigenvectors as a Soft Map
The graph partition is solved approximately using linear algebra.

−
(D − W)y = λDy +
−
−

W: similarity matrix +

Stores all edge weights. Strong connections have large

values. −
−
+
+

D: degree matrix
Diagonal matrix where Dᵢᵢ is total connection of node i.

Second-smallest eigenvector often separates the graph into

y: soft partition two groups.
Nodes with similar y-values tend to belong together.

10
Normalized Cuts Algorithm: Clear Flow
A practical step-by-step view for beginners.

1. Build graph
Choose pixels/superpixels as nodes.

2. Compute weights
Use feature and spatial similarity.

3. Solve eigenproblem
Get a soft partition vector y.

4. Choose threshold
Split y into A and B.

5. Repeat if needed
Recursively divide large regions.
Teaching demo: draw a 10-node graph on the board and let students decide
where the dashed cut should go before showing Ncut.

11
Classroom Demo: Weighted Friendship Graph
Make the class calculate the best cut without images.

B
Question: Which links should be F

8
cut? 8
9 Hint: preserve weights 7–9; remove weak bridges 1 9
A and 2. E
7 1 7
C G
7 7
8 8

D 2 H

Expected reasoning Student activity

Inside weights are 7–9, but bridges are 1 and 2. Cut the weak bridges. Ask teams to propose the cut and explain using weights, not visual
guesswork.

12
Graph Cuts: A Different Goal
Instead of balanced partitioning, we minimize a labeling energy.

Labels
Each pixel must receive a label, often foreground or background.

Source and sink

Source represents one label; sink represents the other label.

Minimum cut
The cut separates source-connected pixels from sink-connected
pixels.

Graph Cut = choose labels with minimum total cost

13
Energy-Based Segmentation: The Main Formula
Every possible labeling receives a cost; the best labeling has minimum cost.

E(L) = Σ Dp(Lp) + λ Σ Vpq(Lp,Lq)

Unary / data term Pairwise / smoothness term λ balance parameter

Dp(Lp) asks: “How suitable is label L for this pixel?” Vpq asks: “Should neighbouring pixels have similar Controls how much smoothness matters compared
Example: bright pixel may fit foreground better. labels?” Similar neighbours prefer same label. with raw pixel evidence.

Plain-language reading:
Good segmentation = pixels match their labels + neighbouring similar pixels stay
together.

14
Unary Term Demo: Which Label Fits Each Pixel?
Foreground and background costs can come from intensity, colour, or user seeds.

Pixel value Cost if BG Cost if FG Better label

20 25 28 180 185 190 20 1 9 BG

28 2 8 BG
Toy 1D image: left pixels look dark; right pixels look bright.
180 8 1 FG

190 9 1 FG

How to teach it But unary alone is not enough

A low unary cost means the label is believable for that pixel. The graph Noise can make isolated wrong labels. That is why pairwise smoothness is
will prefer low-cost assignments. added.

15
Pairwise Term Demo: Neighbours Prefer Smooth Labels
Neighbouring pixels with similar intensities should usually stay in the same region.

B B B B B B

B F B B B B

B B B B B B

Unary-only result: one noisy foreground pixel inside

With pairwise smoothness: isolated mistake is discouraged.
background.

Vpq = high penalty when similar neighbours get different labels

16
Building the Source–Sink Graph
Graph Cut converts energy minimization into a min-cut problem.

1 2 3 4

S T

5 6 7 8
source sink
foreground background

t-links n-links min cut

Edges from source/sink encode unary costs: how Edges between neighbouring pixels encode The minimum cut chooses which pixels remain
likely each pixel is FG or BG. pairwise smoothness. with source or sink.

17
Minimum Cut / Maximum Flow: Simple Intuition
The algorithm finds the cheapest way to separate source from sink.

Flow view
Imagine water flowing from source to sink through edge
capacities.

Bottleneck
The maximum possible flow reveals the weakest separating
bottleneck.

Cut view
The same solution gives the minimum-cost source–sink
separation.

Max-flow value = Min-cut cost

18
Interactive Segmentation with Seeds
Graph cuts are often used when the user marks examples of foreground and background.

1. User marks seeds

A few pixels are marked as object and background examples.

2. Estimate appearance
The algorithm learns what foreground/background intensities or
colours look like.

3. Run graph cut

Labels spread through the image while respecting boundaries and
smoothness.

4. Refine if needed
User adds more seeds in wrong regions and repeats.

19
λ Parameter: Data Accuracy vs Smooth Boundary
Changing λ changes the personality of the segmentation.

Low λ Medium λ High λ

Trust pixel evidence more Balanced result Trust smoothness more
Can be noisy or speckled Good starting point May oversmooth boundaries

λ controls the penalty for neighbouring similar pixels having different labels.

20
Normalized Cuts vs Graph Cuts
Both cut graphs, but their goals and inputs are different.

Aspect Normalized Cuts Graph Cuts / Energy

Main idea Balanced graph partition Minimum-cost labeling

Typical input Similarity graph only Unary + pairwise costs, often seeds

Math tool Eigenvectors / spectral partition Min-cut / max-flow

Best for Unsupervised region discovery Interactive or model-driven FG/BG segmentation

Main risk High computation, parameter sensitivity Bad unary model or too much smoothness

When to teach Ncut When to teach Graph Cut

Use it to explain global image partitioning and why tiny cuts are Use it to explain energy terms, user seeds, and foreground/background
discouraged. masks.

21
Medical Image Segmentation Pipeline
Graph methods are useful when structure, smoothness and user input matter.

1. Acquire
MRI / CT / microscopy image

2. Preprocess
denoise, normalize, enhance

3. Model graph
nodes, weights, unary/pairwise

4. Segment
Ncut or Graph Cut

5. Validate
Dice, IoU, expert review

Important caution: segmentation supports measurement and visualization; it does not replace medical expertise.

22
Live Classroom Activities
Use these to make graph methods concrete.

Activity 1: Human graph Activity 2: Pixel grid cut Activity 3: λ experiment

Students are nodes. Friendship/similarity strengths Give a 4×4 grid with values. Students draw a likely Show three results: noisy, balanced,
become edge weights. Let them find weak bridges. graph-cut boundary. oversmoothed. Students identify λ behaviour.

30 32 35 180 Teacher prompt

“Which neighbouring pairs have a high penalty if we separate them? Which pairs are cheap to cut?”
31 34 170 182

28 33 172 178

25 29 35 181 Exit check

Define node, edge, weight, cut, unary term, pairwise term.

Demo grid: where should the cut pass?

23
Final Recap: Five Sentences Students Should Remember
A compact memory map for revision.

1 Graph segmentation treats pixels as nodes and similarities as edge weights.

2 A cut separates the graph by removing edges between groups.

3 Normalized Cuts avoids trivial tiny partitions by normalizing the cut cost.

4 Graph Cuts minimize an energy made of unary and pairwise terms.

5 Good segmentation balances image evidence with spatial smoothness.

Next topic bridge: graph methods naturally lead to medical image segmentation pipelines and evaluation metrics.
24