Graph-Theoretic Clustering
STEP 1 · BASIC IDEA

What Is Graph-Theoretic Segmentation?

It is a way of dividing an image into regions by thinking of the image as a graph.

Remember only this: Similar neighboring pixels are grouped together. Very different neighboring pixels are separated.
Image
↓
Pixels become graph nodes
↓
Neighboring pixels are connected
↓
Compare their colors
↓
Group similar pixels
↓
Segments
Exam definition:

Graph-theoretic image segmentation represents an image as a graph and groups similar connected pixels into regions.

STEP 2 · IMAGE → GRAPH

Pixels Become Nodes

Imagine every pixel is a point in a graph.

Pixel A ─── Pixel B
  │       │
Pixel C ─── Pixel D
Node

A pixel in the image.

Edge

A connection between neighboring pixels.

Simple idea:

If neighboring pixels look similar, they probably belong to the same region.

What does a graph node represent?

STEP 3 · COMPARE NEIGHBORS

Similar Pixels Stay Together

The edge between two neighboring pixels can represent how different their colors are.

Blue pixel ─ small difference ─ Blue pixel

Blue pixel ─ large difference ─ Red pixel
Small difference

Pixels are similar → keep together.

Large difference

Pixels are different → separate them.

EASIEST MEMORY

Similar → join. Different → separate.

STEP 4 · SETUP

Install the Correct OpenCV Package

Graph segmentation is inside OpenCV's extra ximgproc module.

pip install opencv-contrib-python numpy
Important:

Use opencv-contrib-python because ximgproc is an extra OpenCV module.

Read an image

import cv2

image = cv2.imread("image.jpg")
Use an easy image:

Choose an image with clear regions such as sky, grass, road, buildings, or colorful objects.

STEP 5 · CREATE THE ALGORITHM

Create a Graph Segmentor

OpenCV already implements the graph-based segmentation algorithm for us.

segmentor = cv2.ximgproc.segmentation.createGraphSegmentation(
    sigma=0.5,
    k=300,
    min_size=100
)
sigma

How much the image is smoothed first.

k

Controls how easily regions are joined.

min_size

Very tiny regions are merged.

For your first practical:

Just start with 0.5, 300, 100.

STEP 6 · RUN SEGMENTATION

Call processImage()

Give the image to the graph segmentation algorithm.

labels = segmentor.processImage(image)
What are labels?

labels contains a segment number for every pixel.

0 0 0 1 1
0 0 0 1 1
2 2 2 1 1
  • All pixels with label 0 belong to one segment.
  • All pixels with label 1 belong to another segment.
  • All pixels with label 2 belong to another segment.
IMPORTANT

processImage() returns segment IDs, not a colorful final image.

STEP 7 · VISUALIZE

Give Each Segment One Color

To make the result easy to see, fill each segment with its average color.

import numpy as np

result = np.zeros_like(image)

for label in np.unique(labels):

    mask = labels == label

    average_color = image[mask].mean(axis=0)

    result[mask] = average_color
Take one segment
↓
Find all its pixels
↓
Find their average color
↓
Paint the whole segment
↓
Repeat
Why?

This makes the segmented regions easy to see.

STEP 8 · COMPLETE PROGRAM

Complete Graph Segmentation Practical

This is the main program students need to understand.

import cv2
import numpy as np

# Read image
image = cv2.imread("image.jpg")

# Create graph segmentation algorithm
segmentor = cv2.ximgproc.segmentation.createGraphSegmentation(
    sigma=0.5,
    k=300,
    min_size=100
)

# Segment the image
labels = segmentor.processImage(image)

# Empty output image
result = np.zeros_like(image)

# Give each segment its average color
for label in np.unique(labels):

    mask = labels == label

    average_color = image[mask].mean(axis=0)

    result[mask] = average_color

# Show result
cv2.imshow("Original", image)
cv2.imshow("Segmented", result)

cv2.waitKey(0)
cv2.destroyAllWindows()
Read image
↓
Create GraphSegmentation
↓
processImage()
↓
Get labels
↓
Color each segment
↓
Display

Try only these experiments

  1. Run with k=300.
  2. Change k to 500.
  3. See if regions become larger or merge more.
  4. Change min_size from 100 to 200.
STEP 9 · PARAMETERS

Understand sigma, k and min_size

You only need a basic understanding of these three values.

Parameter Simple meaning
sigma Smooths the image before segmentation.
k Controls how easily regions are merged. Larger values generally give larger regions.
min_size Minimum segment size. Tiny segments are merged.
Do not memorize exact values.

The best values depend on the image. Just understand what each one controls.

STEP 10 · EXAM REVISION

What You Need to Remember

These short answers are enough for a basic college exam or viva.

1. What is graph-theoretic segmentation?
It represents an image as a graph and groups similar connected pixels into regions.
2. What is a node?
A node represents a pixel.
3. What is an edge?
An edge connects neighboring pixels.
4. What does an edge weight represent?
How similar or different two connected pixels are.
5. What is the main clustering idea?
Similar neighboring pixels are grouped together, while very different pixels are separated.
6. Which OpenCV function creates the algorithm?
cv2.ximgproc.segmentation.createGraphSegmentation().
7. What does processImage() return?
A segment label for every pixel.
8. What does sigma do?
It controls smoothing before segmentation.
9. What does k do?
It controls how easily regions merge. Larger values generally make larger segments.
10. What does min_size do?
It controls the minimum segment size.
Image → Graph → Compare neighbors → Group similar pixels → Segments

Completion checklist

  • I know what graph-theoretic segmentation means.
  • I know that pixels are nodes.
  • I know that edges connect neighboring pixels.
  • I understand similar → join, different → separate.
  • I can create GraphSegmentation in OpenCV.
  • I know what processImage() returns.
  • I understand sigma, k and min_size.
  • I can run the complete practical.

Codelab complete! 🎉

You can now explain and demonstrate segmentation by graph-theoretic clustering using OpenCV.