Image Segmentation

Jayanta Mukhopadhyay
Dept. of CSE,
IIT Kharagpur
 Segmentation
l Partitioning image pixels into meaningful non-
overlapping sets.
l Let R be the entire spatial region occupied by the
image.
l Segmentation is a process to partition R into n sub-
regions R1, R2, …, Rn so that
l Ri is a connected set, i=1,2,..,n A logical predicate over Ri
$

! 𝑅! = 𝑅 𝑅! ∩ 𝑅% = 𝜙, ∀𝑖, 𝑗, 𝑖 ≠ 𝑗 𝑄 𝑅! = 𝑇𝑅𝑈𝐸, ∀𝑖
!"#

𝑄 𝑅! ∪ 𝑅% = 𝐹𝐴𝐿𝑆𝐸, 𝑖𝑓 𝑖 & 𝑗 𝑎𝑑𝑗𝑎𝑐𝑒𝑛𝑡

Segmentation Approaches
l Edge based l Region based
l Checks discontinuities l Checks similarity
in the functional space among connected set of
l Assumption: pixels
Boundaries of regions l Similar according to a
sufficiently different predefines set of
from each other and criteria.
also from the
background.

3
Edge detection: Gradient
Operations

Consider the image as a 2D function: f ( x, y )

¶f ( x, y )
= f ( x + 1, y ) - f ( x, y )
¶x
¶f ( x, y)
= f ( x, y + 1) - f ( x, y)
¶y
¶f ( x, y) Ù ¶f ( x, y) Ù
Ñf ( x, y) = i+ j
¶x ¶y
Computation with mask

1. Scan the image top to bottom

-1 1 and left to right.
( x, y ) ( x + 1, y ) 2. At every point (x,y) place the
mask and compute the
Weights weighted sum.

1 ( x, y + 1) g(x,y)=(1).f(x,y+1)+(-1).f(x,y)

-1 ( x, y ) 3. Write the value g(x,y) at (x,y)

pixel position of the processed
image.
Robust gradient computation

Averaging neighboring gradient values

-1
-1 1 -1 0 1 1 1 1
1
-1
-1 1 1 -1 0 1 0 0 0

-1 -1 1 -1 0 1 -1 -1 -1
1

Prewitt operator
(6 times of the gradient value in any direction)
Robust gradient computation

Weighted average of neighboring gradient values

-1
1x
-1 1
1
-1 0 1 1 2 1
-1
2x -1 1 1 -2 0 2 0 0 0
-1
1x -1
1
1
-1 0 1 -1 -2 -1

Sobel operator
(8 times of the gradient value in any direction)
Results of gradient
operations

Vertical Horizontal Resultant

Example
(Sobel Operator: Horizontal+Vertical)

9
Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008
Example (Gradient Image)

10
Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008
Example (Post Smoothing)

11
Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008
Example (Sobel: Comparison)

l Without Smoothing l With Smoothing

12
Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008
Example (Sobel Diagonal)

13
Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008
Example

09-Sep-11 Image Segmentation 14

Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008
Higher order gradients!
¶f ( x, y )
= f ( x + 1, y ) - f ( x, y )
¶x 1 -2 1
𝜕 &𝑓(𝑥, 𝑦) 𝜕𝑓(𝑥, 𝑦) 𝜕𝑓(𝑥 − 1, 𝑦)
= − (x-1,y) (x,y) (x+1,y)
𝜕𝑥 & 𝜕𝑥 𝜕𝑥
≈ 𝑓 𝑥 + 1, 𝑦 − 𝑓 𝑥, 𝑦 − (𝑓 𝑥, 𝑦 − 𝑓 𝑥 − 1, 𝑦 )
= 𝑓 𝑥 + 1, 𝑦 − 2𝑓 𝑥, 𝑦 + 𝑓 𝑥 − 1, 𝑦

0 1 0 1 0 1
𝜕 &𝑓(𝑥, 𝑦) 𝜕 &𝑓(𝑥, 𝑦) 0 -4 0
& + 1 -4 1 OR
𝜕𝑥 𝜕𝑦 &

Laplacian Operator 0 1 0 1 0 1
Weighted combination! 0 1 0
Laplacian Operator
1 -4 1
𝜕 &𝑓(𝑥, 𝑦) 𝜕 &𝑓(𝑥, 𝑦) 1x
+
𝜕𝑥 & 𝜕𝑦 & 0 1 0
+ 1 0 1
4 1 4
1 1 -20 1 4x 0 -4 0
x
5
4 1 4 1 0 1
Types of discontinuities in edges
Isolated
Point
Line
or
Roof

Flat Step
Ramp
Segment

Horizontal Intensity profile 17

 First and second derivatives at
discontinuities in edges
Isolated
Point
Line
or
Roof

Flat Step
Ramp
Segment

x
First 0 -a 0 b -b 0 c d-d -c 0 e 0
derivative
Magnitude high during transition
b -2b b c d-c d-cc e -e
Second 0 -a a
derivative
-2d
Change of sign at point of transition
Edge detection from first and
second order derivatives
l First order derivative
l Generally produce thicker edges
l Use magnitude of the derivative.
l Second order derivative
l Stronger response to fine details, such as, thin lines,
isolated points and noise.
l More sensitive to noise
l ‘double edge response’ at the point of discontinuity
l Produces two values for every edge.
l zero crossing, change of sign, better localization
l Sign changes could be used to qualify transition 19

(dark to light, or reverse).

Effect of noise and blur
l Effect of noise
l Introducing spurious discontinuities
l Many local spikes
l Introduces errors in estimating derivatives
l Affects second derivative more
l Weak edges may get suppressed
l Effect of blur
l Step edges tend to become ramp edges
l Slope of ramp edges decreases
l Inversely proportional to amount of blur
l Location of transition shifts. 20
Handling noise
l Smooth image
l Introduces blur due to low pass filtering
l Detect edge points
l Computes candidate edge points
l For example thresholding
l Localize edges
l Select true edge points from the candidates
l Check the zero-crossings
l Blur increases with the increase of size of
smoothing area (scale)
§ Track edge points in scale space 21
The Marr-Hildreth edge detector
(1980)
l For robust edge detection in presence of noise.
l Observations
l Intensity changes are not independent of scale
l Detection requires edge operator of different sizes
l Sudden intensity change gives rise to trough or peak
in first derivative; or equivalently a zero-crossing in
the second derivative
l Two salient features of operators
l A differential operator
l Capable of being tuned to act at any desired scale.
l Large operators for detecting blurry edges 22

l Small operators for sharp edges

The Marr-Hildreth operator (1980)
l Laplacian of Gaussian: Negative
𝛻 &𝐺(𝑥, 𝑦) of the
Mexican Hat Operator LOG is
( ! )*!
' plotted
𝐺 𝑥, 𝑦 = 𝑒 &+!

𝜕 & 𝐺(𝑥, 𝑦) 𝜕 & 𝐺(𝑥, 𝑦)

𝛻 &𝐺 𝑥, 𝑦 = & +
𝜕𝑥 𝜕𝑦 &
𝑥 & + 𝑦 & − 2𝜎 & ( )* ! !
'
𝛻 &𝐺 𝑥, 𝑦 = 𝑒 &+!
𝜎,

Zero crossings occur at x2+y2= 2𝝈2

A circle of radius of √2𝝈 23

Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008

Typical approximation with integer
weight for 𝝈=1

0 0 -1 0 0

0 -1 -2 -1 0

-1 -2 16 -2 -1

0 -1 -2 -1 0

0 0 -1 0 0
Smoothing and differentiation

𝑔 𝑥, 𝑦 = 𝛻 ! 𝑓 𝑥, 𝑦 ∗ 𝐺(𝑥, 𝑦) = 𝑓 𝑥, 𝑦 ∗ 𝛻 ! 𝐺(𝑥, 𝑦)

Smooth with G(x,y) Convolve with

and then apply Laplacian of
Laplacian Gaussian

Detect zero-crossings after applying

the operator to detect edge pixels.
25
Marr-Hildreth edge detection
algorithm
l Filter the image using nxn Gaussian filter.
l To retain 97% of energy, n > 6𝝈
l Compute Laplacian (e.g. using the 3x3 mask for
Laplacian operator)
l Detect zero-crossings

OR
l Filter the image using nxn LoG filter.
l To retain the effect of zero-crossing, n> 2√2𝝈
l Detect zero-crossings 26
Approximation of LoG by DoG
A kind of BPF.
( ! )*! ( ! )*!
1 ' 1 '
l DoG: 𝐷𝑜𝐺 𝑥, 𝑦 = 𝑒 +"
!
− 𝑒 &+!
!

2𝜋𝜎#& 2𝜋𝜎&&

l Approximates to LoG with the ratio: 𝝈1 : 𝝈2 = 1.6:1

l 𝝈 of LoG having same zero-crossings:
& & &
𝜎 # 𝜎& 𝜎#
𝜎& = & & ln &
𝜎# − 𝜎& 𝜎&
Certain channels of human vision system are
selective w.r.t. freq. and orientation
and be modeled by DOG with a ratio of 1.75:1.
LoG: Example

28
Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008
Example

1. Original image
2. Sobel Gradient
3. LoG
4. Threshold LoG
5. Zero crossing

29
Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008
LoG: Example

l SW: Original
l SE: LoG
l NW: Thresholded
l NE: Zero-Crossings

30
Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008
LoG: Effect of Sigma

31
Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008
The Canny edge detector (1986)
l Three basic objectives
l Low error rate
l All edge pixels to be detected
l No spurious edges
l Good localization
l To be as close as possible to true edge points
l Single edge point response
l Only one point for each edge point
l Optimization criteria set involving above
objectives.
l Difficult to get closed form optimal solution 32
 Optimal detector for noisy step
edges
l Extension to 2D
l In 1-D
l Analysis required to be
l Derive responses for an repeated along a direction
ideal step edge in 1- D
l but not known a priori.
contaminated by white
Gaussian noise. l Compute gradient vector
l Smooth the image
l Optimal numerical solution
close to first derivative of a using Gaussian filter
Gaussian. l Apply Sobel operator

l Get magnitude M(x,y)

(!
𝑑
' !
𝑒 &+ 𝑥 '(!
! and direction 𝝰(x,y) at
= − & 𝑒 &+ each pixel.
𝑑𝑥 𝜎
l Edges are thick. 33
Localization and thin edges
l Non-maximal suppression
l Get the discrete direction d (e.g. 0, 45, 90 and 135 in degrees)
closest to 𝝰(x,y).
l Set M(x,y)=0, if it is less than its neighbor along the orthogonal
direction of d.
l Use of two thresholds
l Higher threshold (TH): low false +ve but high false –ve.
l Detected edge pixel less erroneous, but misses weaker edges
l Lower threshold (TL): High false +ve but low false –ve.
l Detected edge pixel more erroneous, but retains weaker edges
l Hysteresis Thresholding
l Retain all edge pixels whose M(x,y) > TH
l Category 1
l Retain an edge pixel with TH > M(x,y) > TL, if it is connected to 34

an edge pixel of category 1.

Canny edge detection pipeline
e(x,y)
f(x,y)
Double
Thresholding
"! #$!
! &
𝐺 𝑥, 𝑦 = 𝑒 %&!
Connectivity
Analysis

𝛻 Non Maximal
Suppression

35
 Example: Canny

e)
White: Strong Edges
Grey: Weak Edges
Black: No Edges

f)
White: Valid Edges
Blue: Chosen Weak
Edges
Red: Rejected Weak
Edges
14-Sep-11 Image Segmentation 36
Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008
Example: Canny

37
Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008
Example: Canny

38
Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008
 Edge linking
l Local linking l Global linking
l Link an edge pixel with l Hough Transform
another pixel in its l Accumulate votes of
neighborhood having similar possible sets of
magnitude and direction. parameters for lines
l Computationally expensive or curves passing
l Another technique through the edge
l Set an edge pixel of specific pixel.
direction with a tolerance and
l Local peaks provide
having sufficient magnitude to
1, else to 0. the geometric lines
l Fill small gaps along that or curves linking the
direction and compute edge points. 39

connected components.
 Hough transform
q Discretize parameter space into bins
q For each feature point in the image, put a vote in
every bin in the parameter space that could have
generated this point.
q Find bins that have the most votes.

y=mx+b

m
Image space b
Hough parameter space
P.V.C. Hough, Machine Analysis of Bubble Chamber Pictures, Proc. Int. Conf. High Energy Accelerators and Instrumentation, 1959
 Parameter space representation
• A straight line in the image corresponds to a point in
Hough space.

Image space
Hough parameter space
y b

y=m1x+b1 (m1,b1)

x m
Adapted from slides by S. Seitz
 Parameter space representation
• A point in the image corresponds to a line in the
Hough space.

Image space Hough parameter space

b
y
b=-x1m+y1
(x1,y1)

x m
Adapted from slides by S. Seitz
 Parameter space representation
• Two points in the image correspond to two lines in
the Hough space.

Image space Parameters of Hough parameter space

straight line
(x2,y2) joining these b
y two points. b=-x1m+y1
(x1,y1) b=-x2m+y2

x m
Adapted from slides by S. Seitz
Parameter space
representation
• Problems with the (m,b) space:
l Unbounded parameter domain

l Vertical lines require infinite m

• Alternative: polar representation

x cos q + y sinq = r
• q varies from 0 to 180o
• r varies from 0 to the length
of diagonal of the image grid.
Each point will add a sinusoid in the (q,r) parameter space
Adapted from slides by S. Seitz
 Algorithm
A: Accumulator array
• Initialize accumulator A to all zeros
• For each edge point (x,y) in the image
• {
For θ = 0 to 180
ρ
• {
ρ = x cos θ + y sin θ
A(θ, ρ) = A(θ, ρ) + 1 θ
}
}
• Find the value(s) of (θ, ρ) where A(θ, ρ) is a local
maximum
l The detected line in the image is given by
ρ = x cos θ + y sin θ
Adapted from slides by S. Seitz
Basic illustration

features votes

http://ostatic.com/files/images/ss_hough.jpg
A more complicated image

http://ostatic.com/files/images/ss_hough.jpg
Binarization (Thresholding)

l Separation of foreground from background.

l Foreground: Dark pixels (text)
l Background: Bright pixels (white region)
l Pixels in a binarized image set to one of the two
values (e.g. 255 or 0).
l 255 for background.
l 0 for foreground.
l f: R (or Z) à {0,1} (Or {0, 255}, etc.)
l A pixel mapping function
Binarization (Thresholding)

l A simple algorithm
l Choose a threshold value T.

l A pixel greater than T is set to 255

(background), otherwise to 0 (foreground).
Image histogram

Frequency

Brightness (x)
Normalized Histogram à p(x)
Thresholding

Can you
automate
this
operation?

Th=156 Th=192
A simple iterative algorithm
l Select an initial estimate of global threshold T.
l Partition into two sets of background (x > T) and
foreground (x < T).
l Compute means of background and foreground
m1 and m2, respectively.
l Obtain new estimate of T, T=(m1+m2)/2.
l Iterate above steps till convergence

52
Bayesian Classification of
foreground and background pixels
Pixels belonging to two classes:
w1: Foreground
w2: Background
Compute p(w1|x) and p(w2|x).
p(x)

Bayes’ theorem:
p(w ) p( x | w )
p(x|w1)
x p(x|w2) p(w | x) =
p ( x)
Bayes’ classification rule:
Assign x to w1 if p(w1|x) > p(w2|x), else to w2.
To check whether p(w1)p(x|w1) > p(w2) p(x|w2)
Expectation-Maximization
Algorithm
1. Compute p(w1) and
p(w2) from proportional
areas of each region.
2. Compute parameters of
p(x|w1) by assuming it
Gaussian.

Th
3. Compute parameters of p(x|w2)
by assuming it Gaussian.
Expectation-Maximization
Algorithm Th
p ( w1) = å p ( x)
x =0

p ( w2) = 1 - p ( w1)
p(x)

Th
µ1 = å x. p ( x)
x =0
Th
Th x s 12 = å x 2 . p ( x) - µ 21
x =0
4. Compute new threshold 255
value so that for x<Th,
p(w1|x)>p(w2|x), and vice
µ2 = å x. p( x)
x =Th +1
versa. 255
5. Iterate till the value of Th s =
2
2 å x 2
. p ( x ) - µ 2
2
converges. x =Th +1
Otsu Thresholding

l Choose a threshold value, which maximizes

between class variance (σ2B).
p(x)

Th

s = p( w1) p( w2)(µ2 - µ1 )
2
B
2
 10
4
10 4
16

8
14

7
12

6
10
5
8
4

An example
6
3

4
2

2 1

0 0

0 50 100 150 200 250 0 50 100 150 200 250

Bayesia
Otsu:157
n:157
 Probabilistic modeling with
mixture of densities
Number of Component density
components

Component proportion
l Gi defines the ith segment or cluster.
l K is a hyper-parameter and should be known.
l For multivariate Gaussian distribution:
1
1 - ( x -μ ) S ( x -μ )
T -1
l P(x|Gi) ~ N(μi, Σi) P( x ) = e2
d 1
(2p )2 S 2
l To estimate μi, Σi, and P(Gi) for all i. from the set of iid.
input samples: X={xt}, t=1,2,…,N
 Mixture of Gaussians:
Probabilistic inference
l Technique could be refined by computing
probabilities of belongingness to a segments.
Mixing coefficients
Parametric PDF:

Mean vector
Covariance matrix
 Expectation
Maximization (EM) Zi = å p k N (xi | µk , S k )
Algorithm Normalizing
k

factor

probability

Optional step. probability

Decision to be
taken at the end.
EM thresholding: An
example

Intervals: [0,60], [61, 119], [120,255]

Blue Green Yellow
 K-means clustering: Segmentation
through estimating means
l Given N d-dimensional data points,
l compute K partitions (clusters) in them
l so that it minimizes the sum of square of distances between a data point
and the center of its respective partition (cluster).

Optimization problem

Minimization of Sum of Squared Errors (SSE)

where
 The Lloyd algorithm (1957)
(Batch K-Means)

l Given K initial centers, assign a point to the

cluster represented by its center, if it is the
closest among them.
l Update the centers.
l Iterate above two steps, till the centers do not
change their positions.
K-means: example (k=2)

Choose initial centers.

Compute partitions.
K-means: example (k=2)

Compute partitions.

Update centers.
K-means: example (k=2)

Compute new partitions with

updated centers.
K-means: example (k=2)

Update centers.
K-means: example (k=2)
K-means: example (k=2)

Compute new partitions with

updated centers.
K-means: example (k=2)

Update centers.
K-means: example (k=2)

Stop at no change
(or a very little
change in cluster
centers).
Histogram analysis using K-
Means clustering
l Compute the histogram h(x), x=0,1,2,..N
l Choose initial k brightness levels for the set of
means, say m1,m2,..,mk, such that
0<m1<m2<..<mk<N
l Update the ith means, for all i
(+! ,+!$# )/!
∑(+ ,+ )/! 𝑥ℎ(𝑥)
!"# !
𝑚) = (+! ,+!$# )/!
∑(+ ,+ )/! ℎ(𝑥)
!"# !

l Iterate till convergence

 K-Means Segmentation: An
example

k-means for Blue: 0-65

k=3 green: 66-119
m1=39,
m2=90, yellow:120-255
m3=147
Mean Shift Algorithm:
Segmentation through estimating
modes (peaks)

l A probability density estimation method

l Non-parametric
l Does not require the number of components (K) as in K-
Means.
l Identify peaks of distribution.
l Each peak defines a cluster / segment.
l Pixels / elements having shortest path to a peak defines
a segment
Probability density estimation

l Probability distribution using Parzen Windows

l A function of some finite number of data points x1…xn

1 n
P ( x) = å K ( x - x i )
n i =1 K(x-x0)
l Kernel Properties:
l Normalized
ò K (x)dx = 1
l Symmetric
Rd

ò xK (x)dx = 0
Rd

l Exponential weight Decay d

lim x K (x) = 0
x ®¥
Examples of kernels
!
l Epanechnikov 𝐾0 𝐱 = 2 𝑐(1 − 𝐱 ) 𝐱 ≤1
0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

𝑐 𝐱 ≤1
l Uniform 𝐾/ 𝐱 = 2
0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

3
2 𝐱 %
l Gaussian 𝐾1 𝐱 = 𝑐𝑒 !
Mode selection
l Compute the gradient of distribution
1 n æ x - xi 2
ö
∇ P ( x) = å ∇ K ( x - x i ) K (x - xi ) = ck ç
ç h ÷÷
n i =1 è ø
é n ù
c n cé n ù êå i i x g ú Size of
Ñ P ( x ) = å Ñ ki = ê å g i ú  ê n
i =1
- x ú window
n i =1 n ë i =1 û ê ú
å
êë i =1
gi
úû
g(x) = -k ¢(x)
é n æ x - xi 2 ö ù
ê å xi g ç ÷ ú
ê i =1 ç h ÷ ú
è ø - x =0 x(i+1) = x(i)+m(x(i))
∇P(x)=0 m (x) = ê
æ 2
ö
ú
ê n
x - xi ú
ê å g ç
ç h ÷
÷ ú
ë i =1
è ø û
 Mean shift algorithm
• Searches a mode or local
maximum of density of a given
distribution from a point
l Choose a search window (width and location)
l Compute the mean of the data in the search window
l Center the search window at the new mean location
l Repeat until convergence
l Converged point is a mode.
l From every point do the same.
l Set of points arriving at the same mode forms a segment
Mean shift analysis of histogram
l Compute the histogram h(x), x=0,1,2,..N
l For each x determine the mode m(x) in the
histogram.
l Ensure monotonicity in m(x)=0,1,2,…,N
l m(x1) < m(x2), for x1 < x2
l Prune spurious modes
l sufficient support (brightness interval),
l sufficient gap between adjacent distinct pair, and
l sufficient strength (number of pixels).
l Get brightness interval for each mode
Mean shift analysis of
histogram and segmentation

modes: yellow:[1,51]
32,67,117,130 red:[52,82]
blue:[83,128]
white:[129,256]
Segmentation results from
various approaches

GMM K-Means Mean Shift

Component Labeling
(Region growing)
l Partitioning connected image pixels into meaningful
non-overlapping sets.
l Neighborhood definition.
l 4-neighbor, 8-neighbor

o o o o

o o o o o o

o o o o

4-neighbors 8-neighbors
 o o o
o o o
o o o
Component Labeling
l Form a graph with edges between neighboring pixels
having same labels.
l Compute connected components.
l Graph traversal algorithms

20 20 50 20

20 20 50 100

50 50 50 100

100 100 20 20
 o o o
o o o
o o o
Component Labeling
l Form graph with edges between neighboring pixels
having same labels.
l Compute connected components.
l Graph traversal algorithms

Do you require
an explicit
20 20 50 20
graph
20 20 50 100
representation?
Can you
50 50 50 100 compute using
only the image
100 100 20 20
array?
Examples of
components
?

Why a part of river channel is missing?

 Morphological watersheds
l Topographic interpretation of a point in the functional space
l Three types of points
l Points belonging to a regional minimum

l Points from which a water-drop will fall to a minimum

l The set of such points corresponding to the regional minimum
forms the catchment basin (a segment)
§ Connected
l Points from which a water-drop is equally likely to fall toward
multiple minimum
l Points are near the boundaries of the catchment basins and
adjacent basins need to be kept separated by building dams at
their meeting points.
87
§ Core catchment area incrementally dilated from both side to detect
the meeting points.
 Simulating flooding process
l T(n): Set of points having brightness value < n
l Xmin, Xmax: Minimum and maximum brightness values
l {M1, M2, .., Mk }: The set of regional minima identified
for formation of catchment basin.
l Each as a pit for forming catchment basin with flooded water.
l Ci(Mj): Catchment basin of Mj at level i
l set of points connected to Mj having brightness value < i
l Cmax(Mi): Full catchment basin of Mi
l C(n): Union of catchment basins at level n;
l Union of Cn(Mi)’s
l The same as T(n) – {set of points building dam} 88
Watershed segmentation
l The process to keep the catchment basins
separated by building dams
l at the meeting points of catchment basins while
water level rises from the bottom to top
l from Xmin to Xmax

89
Flooding process and dam building
Two connected One connected
components component

Level i-1 Level i

Build dam
l T(i-1): Number of l T(i): Number of connected
connected components: 2 component: 1
90
Decrease of number of connected component in
consecutive levels indicates the event of dam building.
 Watershed segmentation
l C(i-1): Union of catchment basins at level i-1 having
l T(i): Set of pixels having having brightness value < I
l C(Xmin)=T(Xmin) and C(Xmax)=⋃ Cmax(Mi)
l Approach: Incrementally compute C(i) from C(i-1)
l Start from C(Xmin) and Stop at C(Xmax).
l Perform connected component analysis from T(i)
l Check each component q of T(i)

l Perform q ⋂ C(i-1)

§ If it is NULL à New catchment basin, include in C(i)

§ If it is one component àNo spill over, include q in C(i)
§ If it is multiple components à Spill over takes place.
§ Expand each through dilation and build dam at meeting
points of expansion, and include those modified
91
components..
Building dam at meeting
points of expansion
l Dilate each component of q ⋂ C(i-1) in steps with a
constraint that only additional points from q are included
in those expanded components.
l SE: Disk of 8-Neighbor distance of radius 1, Size: 3x3
l The common points of multiple components are not
included in the expanded components and are marked
for the separating dam.
l One pixel width
l Stop when q is completely covered
l A point belongs to either one of the components of C(i-1) or
to the dam.
92
Courtesy: Prof. P.P.Das, CSE, IITKGP

Dam Construction

l M1, M2:
l Sets of coordinates of points
in the two regional minima
l Cn-1(M1), Cn-1(M2)
l Sets of coordinates of points
in the catchment basins
associated with M1 M2 at
stage n-1 of flooding
(catchment basins up to the
flooding level)
l C[n-1] = Cn-1(M1) È Cn-1(M2)
93
Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008
Courtesy: Prof. P.P.Das, CSE, IITKGP

Dam Construction
l At flooding step n-1, there are
two connected components. At
flooding step n, there is only one
connected component
l The water between the two
catchment basins has
merged at flooding step n
l Use “q” to denote the single
connected component
l Steps
l Dilate Cn-1(M1), Cn-1(M2) by
the 3×3 SE, subject to:
l Constrain SE to q
l Dilation cannot merge the sets
94
Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008
 Courtesy: Prof. P.P.Das, CSE, IITKGP

Dam Construction

l The dam is constructed by the

points on which the dilation
would cause the sets being
dilated to merge.
l Resulting one-pixel thick
connected path
l Setting the gray level at each
point in the resultant path to
max+1
95
Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008
Courtesy: Prof. P.P.Das, CSE, IITKGP

Watershed segmentation: A
few tips and issues
l Instead of working on an image itself, this
technique is often applied on its gradient image.
l Each object is distinguished from the background by its
up-lifted edges

0
100
80 100
60 80
40 60
40
20 20
0 0

96
Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008
Watershed segmentation:
Typical results

97

Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008

 Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008
Watershed Segmentation: Use
of markers
Over segmentation

l Use of marker
l A connected region defining the pit or the dam.

l Internal marker within object: Pit

98

l External marker in background: Dam

Example results using markers

99

Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008

Another Example

a) Original Image
b) Gradient Image:
3X3 Sobel Edge
Detector
c) Raw Watershed
d) Controlled
Watershed with
Region Marking

100
Courtesy: Prof. P.P. Das, CSE, IIT Kharagpur
Summary
l Meaningful partitioning of image pixels
l Edges, Regions
l Edge operators: First order and Second order derivatives
(Laplacian)
l Marr-Hildreth, Canny
l Analysis of histogram
l Binarization through classification
l Bayes’ classification rule applied
l Binarization through maximizing interclass variances.
l Otsu thresholding
l By finding peaks / valleys and declare intervals of
brightness value for a segment.
l Gaussian mixture model
l Mean shift algorithm
Summary
l K-means clustering in the feature space, if the cluster
number known.
l Component labeling for connected components.
l Watershed segmentation algorithm
Thank You

103