Computer Vision
Chapter 5: Image segmentation
Course Content
• Chapter 1. Introduction
• Chapter 2. Image formation, acquisition and digitization
• Chapter 3. Image Processing
• Chapter 4. Feature detection and matching
• Chapter 5. Segmentation
• Chapter 6. Motion object detection and tracking
• Chapter 7. Object recognition and deep learning
Chapter 5. Segmentation
• Introduction to image segmentation
• Segmentation based on pixel classification
‒ Thresholding
‒ Clustering techniques
• Region-based segmentation
‒ Region growing algorithm,
‒ Split and merge algorithm
• Edge-based segmentation
Segmentation based on active contours
3
Introduction
• Purpose:
‒ to partition an image into meaningful regions with
respect to a particular application
• Goal:
‒ to cluster pixels into salient image regions, i.e., regions
corresponding to individual surfaces, objects, or natural
parts of objects.
• The segmentation is based on the feature
measurements taken from the image:
‒ grey level, color, texture, depth or motion…
4
Introduction
Source : Jean-Christophe Baillie, ENSTA, uei.ensta.fr/baillie/assets/ES322%20-%20Segmentation.ppt
5
Introduction
• Entity can be extracted from images using mask
Source : Pascal Bertolino, Cours de Traitement d'images. LIS, INPG (France)
6
Applications
• Image segmentation
‒ is usually an initial and vital step in a series of processes
aimed at overall image understanding of computer vision
• Segmentation applications:
‒ Object recognition;
‒ Image retrieval;
‒ Medical image analysis;
‒ Boundary estimation within motion or stereo systems;
‒ Tracking of objects in a video;
‒ Classification of terrains visible in satellite images
‒…
8
Applications
9
Approaches for image segmentation
• Segmentation is usually based on:
‒ discontinuities: edges
• sudden changes, borders (frontiers) between regions…
‒ homogeneous zones: regions
• same color, texture, intensity, ...
10
Approaches for image segmentation
‒ Pixel-based approach
‒ Region-based approach:
• look for homogeneous areas in the image
‒ Edge-based approach :
• look for discontinuities in the image
• A closed edge is equivalent to a region
‒ Hybrid (Dual) approach (region + edge)
11
Examples
Original images Segmented images
12
Pixel-based approach
• Pixel-based approach
‒ Thresholding
‒ Clustering
• It is not a region segmentation technique
‒ But we often in segmentation look for regions
‒ Need some post-processing
13
Thresholding
• Thesholding is a simple and popular method for
object segmentation in digital images
• Thresholding can be
‒ Global: one threshold for the whole image
‒ Local: one threshold for a part of the image
‒ Adaptive: one threshold ajusted according to each
image or each image part
15
Basic global thresholding
• Basic thresholding (2 classes) – main idea :
‒ IF value(pixel) >= threshold THEN value(pixel) = 1 (or 255)
‒ IF value(pixel) < threshold THEN value(pixel) = 0
• The result is a binary image
• It is also possible to use n thresholds to split the image
in n+1 classes
• Problem: choosing the threshold(s)!
16
Example
17
Basic global thresholding
• Find the threshold on histogram of gray level
intensity (histogram thresholding)
0, 𝑓(𝑥, 𝑦) < 𝑇
𝑔 𝑥, 𝑦 = ቊ
1, 𝑓(𝑥, 𝑦) ≥ 𝑇
18
Basic global thresholding
• Threshold value: not difficile if
‒ Controled environment
‒ Industrial applications
19
Multi-thresholds
• n thresholds to split the image in n+1 classes:
‒ IF value(pixel) < threshold_1
• THEN value(pixel) = 0
‒ IF value(pixel) >= threshold_1 && value(pixel) <
threshold_2
• THEN value(pixel) = 1
‒…
‒ IF value(pixel) >= threshold_n
• THEN value(pixel) = n
• Problems: How many thresholds?
20
Multi-thresholds
0, 𝑓 𝑥, 𝑦 < 𝑇1
𝑔 𝑥, 𝑦 = ቐ1, 𝑇2 > 𝑓 𝑥, 𝑦 ≥ 𝑇1
2, 𝑓 𝑥, 𝑦 ≥ 𝑇2
21
Threshold value
• Global thresholding: How to find the value of the
threshold T ?
‒ Value obtained by tests
‒ The mean value of gray values
‒ The median value between the min gray level and the
max one
‒ One value balancing both sections of the histogram
• automatic thresholding
22
Choice of thresholds (optimal)
• 2 classes (background and object) in an image
‒ We suppose mathematical models for distributions
(gaussians, etc.)
‒ We determine the probability of error in the classes 1
and 2
‒ We search for a threshold T resulting in a minimum error
• Several methods for achieving this
Source : www.iro.umontreal.ca/~dift2730/
23
Example: Global automatic thresholding
• One possible algorithm:
‒ Choose an initial value for the threshold T (mean, median, …)
‒ We obtain 2 groups of pixels
• G1 where f(x,y) >= T and G2 where f(x,y) < T
‒ Compute the gray level means for G1 and G2 -> μ1 and μ2
‒ Compute a new value for T
• T = 1/2 (μ1 + μ2)
‒ Repeat until T is ~ constant
• There exist many other global automatic methods
‒ Otsu, Kittler, K-means, …
‒ No solution on which one to use
‒ Must be tested for each new application
24
Example: Otsu algorithm
• Sweep all possible threshold value for T
• For each value of T:
‒ Compute the mean and variance for each
class
‒ We look for the intraclass variance
• Means: 𝜇1 , 𝜇2
• Variances: 𝜎12 , 𝜎22
• Inter-class variance:
𝜎𝑤2 = 𝑃1 ∗ 𝜎12 + 𝑃2 ∗ 𝜎22
• The optimal threshold is the one with the
minimum value for 𝜎𝑤2
• It is based on the idea that classes are
well defined and well grouped
Source : www.iro.umontreal.ca/~dift2730/
25
Example: Otsu algorithm
• Threshold found by the algorithm:
‒ T = 125
26
Global threshold: problem
• Problem:
‒ Global thresholding cannot be used in that case
• Solution: adaptive local thresholding
27
Example of adaptive thresholding
• Split the image in sub-images and process each sub-image with its own
threshold
• The main decision is to choose the size of the sub-images
• Before processing each sub-image, check the variance to make sure that
the sub-image contains two regions, and not only one.
‒ Example: no thresholding for a sub-image if variance<100
28
Example of adaptive thresholding
Bimodal
Bimodal ?
29
Example of adaptive thresholding
30
Clustering-based segmentation
• Image is considered as a set of N image pixels.
• Attributes (property) of the pixels
‒ gray level of single-band gray tone images,
‒ color values of three-band color images: (r, g, b)
‒ values of multi-band images, …
• Based on the similar attribute, pixels classification operators
partition an image into homogeneous regions.
‒ Clustering provides a grouping of the pixels that is dependent on
their values in the image but not necessarily on their locations in the
image unless location is a specified property
‒ Classifier provide the pixel classes which should be homogeneous
regions.
31
Clustering algorithms
• Image segmentation approaches including:
‒ Feature space clustering approaches
‒ Graph-based approaches
• Clustering algorithms:
‒ K-Means clustering
‒ Mean-Shift Clustering
‒ Expectation-Maximization Clustering
‒ Watershed Segmentation
‒ Graph Cuts (Spectral clustering)
‒ Normalized cuts
‒…
32
K-means clustering
33
Slide based on one by Eamonn Keogh
Partition Algorithm 1: k-means
1. Decide on a value for k.
2. Initialize the k cluster centers (randomly, if necessary).
3. Decide the class memberships of the N objects by
assigning them to the nearest cluster center.
4. Re-estimate the k cluster centers, by assuming the
memberships found above are correct.
5. If none of the N objects changed membership in the last
iteration, exit. Otherwise goto 3.
K-means Clustering: Step 1
Algorithm: k-means, Distance Metric: Euclidean Distance
5
4
k1
3
2
k2
k3
0
0 1 2 3 4 5
Slide based on one by Eamonn Keogh
K-means Clustering: Step 2
Algorithm: k-means, Distance Metric: Euclidean Distance
5
4
k1
3
2
k2
k3
0
0 1 2 3 4 5
Slide based on one by Eamonn Keogh
K-means Clustering: Step 3
Algorithm: k-means, Distance Metric: Euclidean Distance
5
4
k1
k3
1 k2
0
0 1 2 3 4 5
Slide based on one by Eamonn Keogh
K-means Clustering: Step 4
Algorithm: k-means, Distance Metric: Euclidean Distance
5
4
k1
k3
1 k2
0
0 1 2 3 4 5
Slide based on one by Eamonn Keogh
K-means Clustering: Step 5
Algorithm: k-means, Distance Metric: Euclidean Distance
5
expression in condition 2
4
k1
3
k2
1 k3
0
0 1 2 3 4 5
expression in condition 1
Slide based on one by Eamonn Keogh
K-means Clustering: examples
Input image K-means on color
Source : D.A. Forsyth and J. Ponce. Computer Vision : A Modern Approach. Prentice-Hall, 2002.
40
K-means clustering: examples
41
Example
42
Pixel-based approach: Pros & cons
• Pros
‒ Simple, fast
• Cons: thresholding is mainly an operation on pixels
‒ It does not give connected regions ➔ can add more
features
‒ we need to « clean » the results
• erase lonely pixels, keep regions
• Other segmentation methods exist
• that can keep the integrity of regions (connected pixels)
43
Features for segmentation
• Intensity, Color?
• Position
• Texture
•…
44
Segmentation as clustering
Depending on what we choose as the feature space, we
can group pixels in different ways.
Grouping pixels based
on intensity similarity
Feature space: intensity value (1-d)
Slide credit: Kristen Grauman
Segmentation as clustering
Depending on what we choose as the feature space, we
can group pixels in different ways.
Grouping pixels based on
intensity+position similarity
Intensity
X Both regions are black, but if we also
include position (x,y), then we could group
the two into distinct segments; way to
Slide credit: Kristen Grauman
encode both similarity & proximity.
Segmentation as clustering
Depending on what we choose as the feature space, we
can group pixels in different ways.
Grouping pixels based
on texture similarity
F1
F2
Filter bank
of 24 filters
…
F24
Feature space: filter bank responses (e.g., 24-d)
Slide credit: Kristen Grauman
Segmentation with texture features
• Find “textons” by clustering vectors of filter bank outputs
• Describe texture in a window based on texton histogram
Count
Image Texton map
Texton index
Count
Count
Texton index Texton index
Malik, Belongie, Leung and Shi. IJCV 2001. Adapted from Lana Lazebnik
Image segmentation example
Slide credit: Kristen Grauman
Region-based segmentation
• Finding region based on the criterion of
homogeneity and connectivity of pixels (region)
‒ Each region is homogeneous (i.e., uniform in terms of
the pixel attributes such as intensity, color, range, or
texture, etc.)
‒ and connected
• Algorithms:
‒ Region growing
‒ Split and merge algorithm
‒ Hierarchical clustering
‒…
50
Region-based segmentation
• Region-based approaches provide :
‒ All pixels must be assigned to regions
‒ Each pixel must belong to a single region only
‒ Each region must be uniform
‒ Any merged pair of adjacent regions must be non-
uniform
‒ Each region must be a connected set of pixels
• Region-based approaches:
‒ Different methods
‒ Common point: homogeneity criteria
51
Region growing
• Start from a point (seed) and add neighbor pixels
following a given criteria
• The seeds can be manually or automatically chosen
‒ automatic seeds in very homogeneous zones for example
image Seed Region growing Final result
52
Region growing algorithm
• Algorithm:
‒ Choose K random pixels in K regions
‒ Use 8-connected and threshold to determine
‒ Repeat a and b until almost points are K classified.
• Example illustrated:
53
Region growing with multi-seeds
54
Example
Simulation
of region
growing
(90% pixels )
55
Split-and-merge
• Split (step 1)
‒ Recursively split all non-homogeneous
regions following a given criteria
• variance, max-min, …
‒ Dividing one region gives 4 subregions
‒ Subregion attributes are re-computed
• Merge (step 2)
‒ Group all homogeneous adjacent
regions following a given criteria
56
Split-and-merge: split
Image initiale
Split1
Split 2
split 3
Homogeneity = criteria on the variance
(or max-min <= 1)
Source : Jean-Christophe Baillie. Cours de segmentation. ENSTA ParisTech (France).
57
Split-and-merge: merge
Phase 1: Create homogeneous zones (split)
Phase 2: Group homogeneous zone (merge)
Quadtree
Connect homogeneous adjacent regions
Source : Jean-Christophe Baillie. Cours de segmentation. ENSTA ParisTech (France)
58
Split-and-merge
59
Edge-based segmentation
• Finding region based on edges
• Algorithms:
‒ Basic Edge Detection
‒ The Marr-Hildreth edge detector (LoG)
‒ Short response Hilbert transform (SRHLT)
‒ Watersheds
60
Watershed segmentation
• We consider the image as a 3D shape using the
gray level as the third dimension
2D image Visualization in 3D
Source : http://www.gpa.etsmtl.ca/cours/gpa669/
61
Watershed segmentation
• After we reverse (upside down) the values to
create « holes » in the shape
62
Watershed segmentation
• Next we fill in the holes with water
63
Watershed segmentation
64
Watershed segmentation
https://docs.opencv.org/master/d3/db4/tutorial_py_watershed.html
65
Watershed segmentation
66
Segmentation – advices
• Image segmentation
‒ No method works for all images
‒ No miracle, no warranty!
• One of the main problem is to define the goal of
segmentation:
‒ What exactly are we looking for in the image?
• Global regions or small details?
• Presence or not of persons details in the face?
• It is good to think in advance what we will do with this
segmentation results
‒ This helps to define the level of precision needed
67
Segmentation – advices
• Image Pre-processing:
‒ good selection of sensors and energy source, and
controled image acquisition conditions help to make
segmentation easier and more efficient
• For some applications, we realize today that we
can avoid to segment the image. It is often better
like this.
68
Limits of segmentation
Image segmentation alone
cannot find all image
objects as we can interpret
them
69
Segmentation vs. grouping
• Term 'segmentation' :
‒ less used
‒ segmentation, which let think
about an exact image splitting
into regions
• 'Pixel grouping'
‒ which refers only to a notion
of similarity between pixels
without relation on the
content of regions.
Source : [Malik 2001].
70
Motion segmentation
Input sequence Image Segmentation Motion Segmentation
Input sequence Image Segmentation Motion Segmentation
A.Barbu, S.C. Zhu. Generalizing Swendsen-Wang to sampling arbitrary posterior probabilities,
IEEE Trans. PAMI, August 2005.
Credit: Kristen Grauman, UT Austin
Thank you for
your attention!
76
