Region-based Segmentation

Image Segmentation
• Group similar components (such as, pixels in an image, image
frames in a video) to obtain a compact representation.
• Applications: Finding tumors, veins, etc. in medical images, finding
targets in satellite/aerial images, finding people in surveillance
images, summarizing video, etc.
• Methods: Thresholding, K-means clustering, etc.

2
 Segmentation strategy
Edge-based Region-based
• Assumption: different objects are • Assumption: different objects are
separated by edges (grey level separated by other kind of
discontinuities) perceptual boundaries
– neighborhood features
• The segmentation is performed by
identifying the grey level gradients • Most often texture-based
• The same approach can be – Textures are considered as
instantiations of underlying
extended to color channels
stochastic processes and
analyzed under the assumptions
that stationarity and ergodicity
hold
• Method
– Region-based features are
extracted and used to define
“classes”
3
 Examples zoomed

original

4
 Examples
Canny
block mean block std

5
 Image Segmentation
Contour-based Region-based
• Discontinuity • Similarity, homogeneity
– The approach is to partition an
• The principal approaches in this
image based on abrupt changes
in gray-scale levels.
category are based on
– The principal areas of interest – thresholding,
within this category are detection – region growing
of isolated points, lines, and – region splitting/merging
edges in an image. – clustering in feature space

6
 Thresholding
• Image model
– The objects in the image differ in the graylevel distribution
• Simplest: object(s)+background
– The spatial (image domain) stochastic parameters (i.e. mean, variance)
are sufficient to characterize each object category
• rests on the ergodicity assumption
– Easily generalized to multi-spectral images (i.e. color images)

7
 Thresholding
• Individual pixels in an image are marked as “object” pixels if their
value is greater than some threshold value and as “background”
pixels otherwise → threshold above
– assuming an object to be brighter than the background
– Variants
• threshold below, which is opposite of threshold above;
• threshold inside, where a pixel is labeled "object" if its value is between two
thresholds
• threshold outside, which is the opposite of threshold inside
– Typically, an object pixel is given a value of “1” while a background pixel
is given a value of “0.” Finally, a binary image is created by coloring
each pixel white or black, depending on a pixel's label.

8
 Thresholding types
• Histogram shape-based methods
– Peaks, valleys and curvatures of the smoothed histogram are analyzed
• Clustering-based methods
– gray-level samples are clustered in two parts as background and
foreground (object), or alternately are modeled as a mixture of two
Gaussians
• Entropy-based methods
– Entropy of the foreground and background regions, cross-entropy
between the original and segmented image, etc.
• Object attribute-based methods
– Based on a measure of similarity between the gray-level and the
binarized images, such as fuzzy shape similarity, edge coincidence, etc.

9
 Thresholding types
• Stchastic methods using higher-order probability distributions and/or
correlation between pixels
• Local methods adapt the threshold value on each pixel to the local
image characteristics

10
 Histogram thresholding
• Suppose that an image, f(x,y), is composed of light objects on a dark
background, and the following figure is the histogram of the image.

• Then, the objects can be extracted by comparing pixel values with a

threshold T.

11
Thresholding

12
Thresholding

13
 Histogram thresholding
• Analytical models can be fit to the valleys of the histogram and then
used to find local minima
object

background

ax2+bx+c

T=xmin=-b/2a

14
 Multiple histogram thresholding
• It is also possible to extract objects that have a specific intensity range
using multiple thresholds.

Extension to color images is straightforward: There are three color

channels, in each one specifies the intensity range of the object… Even if
objects are not separated in a single channel, they might be with all the
channels… Application example: Detecting/Tracking faces based on skin
color…
15
 Clustering based thresholding
• Exercise: Cost of classifying a background pixel as an object pixel is Cb.
• Cost of classifying an object pixel as a background pixel is Co.
• Find the threshold, T, that minimizes the total cost.

Background

h1 Object
h2

a 2a
T
16
 Clustering based thresholding
• Idea 1: pick a threshold such that each pixel on each side of the
threshold is closer in intensity to the mean of all pixels on that side
of the threshold than the mean of all pixels on the other side of the
threshold. Let
μB(T) = the mean of all pixels less than the threshold (background)
μO(T) = the mean of all pixels greater than the threshold (object)
• We want to find a threshold such that the greylevels for the object
are closest to the average of the object and the greylevels for the
background are closest to the average of the background:

∀g ≥ T → g − μo (T ) < g − μ B (T )
∀g < T → g − μo (T ) ≥ g − μ B (T )

17
 Clustering based thresholding
• Idea 2: select T to minimize the within-class variance—the weighted
sum of the variances of each cluster:

σ 2 within (T ) = nB (T ) σ 2 B (T ) + no (T ) σ 2 o (T )
T −1
nB (T ) = ∑ p ( g )
g =0
N −1
no (T ) = ∑ p ( g )
g =T

σ 2 B (T ) : variance of the pixels in the background (g<T)

σ 2 0 (T ) : variance of the pixels in the object (g ≥ T)
0,..., N − 1: range of intensity levels

18
 Clustering based thresholding
• Idea 3: Modeling the pdf as the superposition of two Gaussians and
take the overlapping point as the threshold
2 2
1 ⎛ x − μ1 ⎞ 1 ⎛ x − μ2 ⎞
− ⎜ ⎟ − ⎜ ⎟
P1 2 ⎝ σ1 ⎠ P2 2⎝ σ2 ⎠
h(x) = P1 p1 (x) + P2 p 2 (x)= e + e
2πσ 1
2
2πσ 2
2

19
 Thresholding
• Non-uniform illumination may change the histogram in a way that it
becomes impossible to segment the image using a single global
threshold.
• Choosing local threshold values may help.

20
Thresholding

21
 Thresholding
• Adaptive thresholding

22
 Region-Oriented Segmentation
• Region Growing
– Region growing is a procedure that groups pixels or subregions into larger
regions.
– The simplest of these approaches is pixel aggregation, which starts with a set
of “seed” points and from these grows regions by appending to each seed
points those neighboring pixels that have similar properties (such as gray
level, texture, color, shape).
– Region growing based techniques are better than the edge-based techniques
in noisy images where edges are difficult to detect.

23
Region-Oriented Segmentation

24
Region-Oriented Segmentation

25
 Region-Oriented Segmentation
• Region Splitting
– Region growing starts from a set of seed points.
– An alternative is to start with the whole image as a single region and
subdivide the regions that do not satisfy a condition of homogeneity.
• Region Merging
– Region merging is the opposite of region splitting.
– Start with small regions (e.g. 2x2 or 4x4 regions) and merge the regions that
have similar characteristics (such as gray level, variance).
– Typically, splitting and merging approaches are used iteratively.

26
Region-Oriented Segmentation

27
 Use of Motion In Segmentation
Take the difference between a reference image and a subsequent image to
determine the still elements image components.

28
Application to 3D data

29
Clustering and Classification
 What is texture?
• No agreed reference definition
– Texture is property of areas
– Involves spatial distributions of grey levels
– A region is perceived as a texture if the number of primitives in the field
of view is sufficiently high
– Invariance to translations
– Macroscopic visual attributes
• uniformity, roughness, coarseness, regularity, directionality, frequency [Rao-
96]
– Sliding window paradigm

31
 Texture analysis
• Texture segmentation
– Spatial localization of the different textures that are present in an image
– Does not imply texture recognition (classification)
– The textures do not need to be structurally different
– Apparent edges
• Do not correspond to a discontinuity in the luminance function
• Texture segmentation ↔ Texture segregation
– Complex or higher-order texture channels

32
 Texture analysis
• Texture classification (recognition)
– Hypothesis: textures pertaining to the same class have the same visual
appearance → the same perceptual features
– Identification of the class the considered texture belongs to within a
given set of classes
– Implies texture recognition
– The classification of different textures within a composite image results
in a segmentation map

33
 Co-occurrence matrix
• A co-occurrence matrix, also referred to as a co-occurrence
distribution, is defined over an image to be the distribution of co-
occurring values at a given offset.
• Mathematically, a co-occurrence matrix Ck,l[i,j] is defined over an
NxM image I, parameterized by an offset (k,l), as:

N M
⎧1, if I ( p, q ) = i and I ( p + k , q + l ) = j
Ck ,l [i, j ] = ∑∑ ⎨
p =1 q =1 ⎩ 0, otherwise

• The co-occurrence matrix depends on (k,l), so we can define as

many as we want

34
 Texture Classification
• Problem statement
– Given a set of classes {ωi, i=1,...N} and a set of observations
{xi,k,k=1,...M} determine the most probable class, given the
observations. This is the class that maximizes the conditional
probability:

ωwinner = max P(ωi xk )

k

35
 Texture classification
• Method
– Describe the texture by some features which are related to its
appearance
• Texture → class → ωk
• Subband statistics → Feature Vectors (FV) → xi,k
– Define a distance measure for FV
• Should reflect the perceived similarity/dissimilarity among textures
(unsolved)
– Choose a classification rule
• Recipe for comparing FV and choose ‘the winner class’
– Assign the considered texture sample to the class which is the closest in
the feature space

36
 Exemple: texture classes
ω1 ω2 ω3 ω4

37
 FV extraction
• Step 1: create independent texture instances

Training set

Test set

38
 Feature extraction
• Step 2: extract features to form feature vectors
subimages
Intensity image

DWT/DWF

The FVs contain some

For each sub-image statistical parameters
evaluated on the subband
For each subband images
• estimates of local variances

Calculate the • histograms

local energy
(variance)

Fill the corresponding

⇒ Collect the local energy of each sub-image
position in the FV
in the different subbands in a vector

One FV for each sub-image Classification algorithm

39
 Building the FV

approximation d1 d2 d3

scale 1

scale 2

40
 Building the FV
elements of FV1 of texture 1
elements of FV2 of texture 1
approximation d1 d2 d3 FV1 FV2
scale 1

scale 2

41
 Implementation
• Step 1: Training
– The classification algorithm is provided with many examples of each
texture class in order to build clusters in the feature space which are
representative of each class
• Examples are sets of FV for each texture class
• Clusters are formed by aggregating vectors according to their “distance”

• Step 2: Test
– The algorithm is fed with an example of texture ωi (vector xi,k) and
determines which class it belongs as the one which is “closest”
Training set Build the
Sample
reference
Feature cluster
extraction

Test set Classification

core

42
 Clustering in the Feature Space
Bi-dimensional feature
space (FV of size 2) Multi-dimensional feature
space

FV(1)
FV(1)

FV(2) FV(3)

FV(2)
FV classification: identification of the
cluster which best represents the vector
according to the chosen distance
measure
43
 Classification algorithms
• Measuring the distance among a class and a vector
– Each class (set of vectors) is represented by the mean (m) vector and
the vector of the variances (s) of its components ⇒ the training set is
used to build m and s
– The distance is taken between the test vector and the m vector of each
class
– The test vector is assigned to the class to which it is closest
• Euclidean classifier
• Weighted Euclidean classifier

• Measuring the distance among every couple of vectors

– kNN classifier

44
 kNN classifier
• Given a vector v of the test set
– Take the distance between the vector v and ALL the vectors of the
training set
– (while calculating) keep the k smallest distances and keep track of the
class they correspond to
– Assign v to the class which is most represented in the set of the k
smallest distances
0.1 0.57 0.9 1.2
2.5 2.77 3.14 k=3
0.1 6.10 7.9 8.4
2.3

v v is assigned to class 1
FV for FV for FV for
class 1 class 2 class 3

45
 Confusion matrix

textures 1 2 3 4 5 6 7 8 9 10 % correct
1 841 0 0 0 0 0 0 0 0 0 100.00%
2 0 840 1 0 0 0 0 0 0 0 99.88%
3 2 0 839 0 0 0 0 0 0 0 99.76%
4 0 0 0 841 0 0 0 0 0 0 100.00%
5 0 0 88 0 753 0 0 0 0 0 89.54%
6 0 0 134 0 0 707 0 0 0 0 84.07%
7 0 66 284 0 0 0 491 0 0 0 58.38%
8 0 0 58 0 0 0 0 783 0 0 93.10%
9 0 0 71 0 0 0 0 0 770 0 91.56%
10 0 4 4 0 0 0 0 0 0 833 99.05%
Average recognition rate 91.53%

46
 K-Means Clustering
1. Partition the data points into K clusters randomly. Find the centroids of
each cluster.
2. For each data point:
– Calculate the distance from the data point to each cluster.
– Assign the data point to the closest cluster.
3. Recompute the centroid of each cluster.
4. Repeat steps 2 and 3 until there is no further change in the
assignment of data points (or in the centroids).

47
K-Means Clustering

48
K-Means Clustering

49
K-Means Clustering

50
K-Means Clustering

51
K-Means Clustering

52
K-Means Clustering

53
K-Means Clustering

54
K-Means Clustering

55
 K-Means Clustering
• Example

Duda et al.

56
 K-Means Clustering
• RGB vector

⎧ 2⎫
K-means clustering minimizes ∑ ⎨ ∑ x j − μi ⎬
i∈clusters ⎩ j∈elements of i'th cluster ⎭
57
 Clustering
• Example

D. Comaniciu and P.
Meer, Robust Analysis
of Feature Spaces:
Color Image
Segmentation, 1997.

58
 K-Means Clustering
• Example

Original K=5 K=11

59
K-means, only color is used
in segmentation, four clusters
(out of 20) are shown here.

60
 K-means, color and position
is used in segmentation, four
clusters (out of 20) are shown
here.

Each vector is (R,G,B,x,y).

61
 K-Means Clustering: Axis Scaling
• Features of different types may have different scales.
– For example, pixel coordinates on a 100x100 image vs. RGB color values in
the range [0,1].
• Problem: Features with larger scales dominate clustering.
• Solution: Scale the features.

62