Digital Image Processing

Image Segmentation
Element of Image Analysis

Preprocess
Image acquisition, restoration, and enhancement

Intermediate process
Image segmentation and feature extraction

High level process

Image interpretation and recognition
Importance of Image Segmentation

Image segmentation is used to separate an image into constituent

parts based on some image attributes. Image segmentation is an
important step in image analysis

Benefit
1.Image segmentation reduces huge amount of unnecessary data while
retaining only importance data for image analysis
2.Image segmentation converts bitmap data into better structured data
which is easier to be interpreted
Image Attributes for Image Segmentation
1.Similarity properties of pixels inside the object are used to group
pixels into the same set.
2.Discontinuity of pixel properties at the boundary between object
and background is used to distinguish between pixels belonging to
the object and those of background.
Detection of Discontinuities

• 3 basic types of gray-level discontinuities:

Points
Lines
Edges

• Common method of detection: run a mask through

the image.
Spatial Filtering Application to Shape Detection

❖One application of spatial filtering is shape detection: finding

locations of objects with the desired shape.

❖Unlike frequency selective masks that are designed based

on the concept of frequency, shape detection masks are
derived from the shapes to be detected themselves.

❖A mask for shape detection usually contains the shape or a part

of the shape to be detected.

❖The location that is most correlated to the mask is the

location where the highest filter response occurs. The
shape is most likely to exist there.
Point Detection

• T: nonnegative threshold:
9
R = w1 z1 + w2 z 2 + ... + w9 z9 =  wi zi
i=1
Point Detection
❖We can use Laplacian masks
-1 -1 -1 0 -1 0
for point detection.
-1 8 -1 -1 4 -1
❖Laplacian masks have the largest -1 -1 -1 0 -1 0
coefficient at the center of the mask
while neighbor pixels have an
opposite sign.

❖This mask will give the high response to the object that has the
similar shape as the mask such as isolated points.

❖Notice that sum of all coefficients of the mask is equal to zero.

This is due to the need that the response of the filter must be zero
inside a constant intensity area
Point Detection
Point detection can be done by applying the thresholding function:
Line Detection

❖Similar to point detection, line detection can be performed

using the mask the has the shape look similar to a part of a line

❖There are several directions that the line in a digital image

can be.

❖For a simple line detection, 4 directions that are mostly used

are horizontal, +45 degree, vertical and –45 degree.

Line detection masks

(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Line Detection Example
Edge Detection

• Edge (a set of connected pixels):

– the boundary between two regions with relatively distinct
gray-level properties.
– Note: edge vs. boundary
• Assumption:
– the regions are sufficiently homogeneous, so that the
transition between two regions can be determined on the
basis of gray-level discontinuities alone.
Edges
Ideal step edge Ideal ramp edge

Blurred edge

Generally, objects and background have different intensities. Therefore,

Edges of the objects are the areas where abrupt intensity changes occur.

(Images from Rafael C. Gonzalez and Richard E.

Wood, Digital Image Processing, 2nd Edition.
Ideal Ramp Edges and its Derivatives
Smoothed Step Edge and Its Derivatives
Derivative Based Edge Detection

❖ From the previous slide, we can conclude that:

Local maxima of the absolute of the 1st derivative and Zero
crossing of the 2nd derivative occur at edges.

❖Therefore, for detecting edges, we can apply zero crossing

detection to the 2nd derivative image or thresholding the absolute
of the 1st derivative image.

❖Nevertheless, derivative operator is very sensitive to noise as

we will see in the next slide.
Noisy Edges and Derivatives

Derivative operator is
f(x) df d2 f
a highpass filter and
dx dx2 thus enhances noise.

AWGN  = 0.1

Edge responses
AWGN  = 1.0
are buried by
noise.

AWGN  = 10
Gradient Operators

The gradient vector points in the direction of

maximum rate of change of f at (x,y).

Gradient magnitude: f = mag(F ) = [G x2 + G y2 ]1/ 2

(maximum rate of increase of f(x,y) per unit distance)

f | Gx | + | G y |

Direction angle of ∇ f at (x,y):

Masks for Estimating Partial Derivatives

Normally, the mask for estimating partial derivative is anti-symmetry with

respect to the orthogonal axis
For example, the Sobel mask for
computing f is anti-symmetry
x
with respect to the y-axis. It has the
positive sign on the right side and
negative sign on the left side.

Notice that sum of all coefficients is

equal to zero to make sure that the
response of a constant intensity area
is zero.
Masks for Detecting Diagonal Edges

The mask for detecting -45-

degree edges is anti-symmetry
with respect to the –45-degree
lines while the mask for detecting
45-degree edges is anti-symmetry
with respect to the 45-degree lines.
Example of Image Gradient
Example of Image Gradient (average masking)

Note: the original image is smoothed by a 5x5 moving average

mask first.
Example of Diagonal Edges

Using -45-degree mask Using 45-degree mask

Note: the original image is smoothed by a 5x5 moving average

mask first.
Laplacian Masks
The Laplacian masks are used to estimate the Laplacian image:

2P 2P
 P= 2 + 2
2
x y

Ideally, the Laplacian mask must be directional invariant: symmetry in

all direction (radially symmetry ). However, for 3x3 masks, there are
Only 8 possible directions. Hence, we can use the following masks:
Laplacian

• The Laplacian is seldom used in practice, because:

– It is unacceptably sensitive to noise (as second-order
derivative)
It produces double edges
– It is unable to detect edge direction
• An important use of the Laplacian
– To find the location of edges using its zero-crossings
property.
• Plus, the Laplacian plays only the role of detector of
whether a pixel is on the dark or light side of an edge.
Laplacian(with smoothing)

• An important use of the Laplacian:

– To find the location of edges using its zero-crossings
property.

• Convolve an image with the Laplacian of a 2D Gaussian

function of the form:

x2 + y2
−
h(x, y) = −e 2 2

where  is the standard deviation.

Laplacian of Gaussian(LoG)

• The Laplacian of the above Gaussian is:

− r2
 r −
2 2

 h = −
2
4
e 2 2

 

where r2 = x2 + y2.

 determines the degree of blurring that occurs.

Laplacian Masks
For a large scale Laplacian mask, we can use a Laplacian of Gaussian
(LOG) as a mask:
 x2 + y2 
x + y −
2 2 2
 −
 2 
2 
 G( x, y) = − 
2
e
  4

Surface plot of
LOG, Looks like
a “Mexican hat” LOG image

Cross section 5x5 LOG

of LOG mask
Linear Operation

• Second derivation is a linear operation

• Thus, 2f is the same as convolving the image with
Gaussian smoothing function first and then computing
the Laplacian of the result
• Thus, we see that the purpose of the Gaussian function in
the LOG formulation is to smooth the image, and the
purpose of the Laplacian operator is to provide an image
with zero crossings.
• Smoothing the image reduces the effect of noise and, in
principle, it counters the increased effect of noise caused
by the second derivatives of the Laplacian.
Example

a). Original image

b). Sobel Gradient
c)Spatial Gaussian smoothing
function
d)Laplacian mask
e). LoG
f). Threshold LoG
g). Zero crossing

30
Zero crossing & LoG

• Approximate the zero crossing from LoG image

• To threshold the LoG image by setting all its
positive values to white and all negative values to
black.
• The zero crossing occur between positive and
negative values of the thresholded LoG.
Zero crossing vs. Gradient

• Attractive
– Zero crossing produces thinner edges
– Noise reduction
• Drawbacks
– Zero crossing creates closed loops. (spaghetti
effect)
– sophisticated computation.
• Gradient is more frequently used.
Gradient Image : revisited
Gradient Operator (  )

P P P P
x y
Gradient Vector Field
Gradient Vector

Gradient
P P
Vector
Field
Gradient Based Image Segmentation

P
P|

Thresholding

Edge map

T=60 T=100
Laplacian Image

Operator
2 P 2 P
 P= 2 + 2
2
x y

2P 2P
P 2 P
x2 y2
Laplacian Image

2 P 2 P

P 2 P

2 P
Laplacian Based Image Segmentation

2 P

Zero crossing
Detection
thresholding
T=0

2 P
Edge Linking and Boundary Detection

• Edge detection algorithms are followed by

linking procedures to assemble edge pixels
into meaningful edges.
• Basic approaches
– Local Processing
– Global Processing via the Hough Transform
– Global Processing via Graph-Theoretic
Techniques
Local Processing

• Analyze the characteristics of pixels in a small

neighborhood (say, 3x3, 5x5) about every edge
pixels (x,y) in an image.
• All points that are similar according to a set of
predefined criteria are linked, forming an edge of
pixels that share those criteria.
Criteria

1. The strength of the response of the gradient

operator used to produce the edge pixel
– an edge pixel with coordinates (x0,y0) in a
predefined neighborhood of (x,y) is similar in
magnitude to the pixel at (x,y) if
|f(x,y) - f (x0,y0) |  E

2. The direction of the gradient vector

– an edge pixel with coordinates (x0,y0) in a
predefined neighborhood of (x,y) is similar in
angle to the pixel at (x,y) if
| (x,y) - (x0,y0) | < A
Criteria

• A point in the predefined neighborhood of (x,y) is

linked to the pixel at (x,y) if both magnitude and
direction criteria are satified.
• The process is repeated at every location in the
image
• A record must be kept simply by assigning a
different gray level to each set of linked edge
pixels.
Example
• Find rectangles whose sizes make them suitable candidates for license plates
• Use horizontal and vertical Sobel operators
• Eliminate isolated short segments
• Link conditions: gradient value > 25, gradient direction differs < 15
Hough Transformation (Line)

xy-plane ab-plane or parameter space

yi =axi + b b = - axi + yi

• Given n points in an image, find subsets of points that lie on straight lines.
•Find all lines determined by every pair of points(O(n2)) and then find all subsets of points
in an image that are close to a particular line(O(n3)).
• Hough transform :
• a point in xy-plane corresponds to a line in the parameter space
•all points (xi ,yi) contained on the same line must have lines in parameter space that
intersect at (a’,b’)
Accumulator cells

• (amax, amin) and (bmax, bmin) are the

expected ranges of slope and intercept
values.
• all are initialized to zero
• if a choice of ap results in solution bq
then we let A(p,q) = A(p,q)+1
• at the end of the procedure, value Q in
A(i,j) corresponds to Q points in the xy-
plane lying on the line y = aix+bj

b = - axi + yi
-plane

 = 90 measured with respect to x-axis

• Problem of using equation y = ax + b is that value of a is infinite for a

vertical line.
• To avoid the problem, use equation x cos + y sin  =  to represent a line
instead.
• Vertical line has  = 90 with  equals to the positive y-intercept or  = -90
with  equals to the negative y-intercept 46
 range of =  2D

where D is the distance

between corners in the
image

47
Generalized Hough Transformation (ex: Circle)
• Can be used for any function of the form
g(v,c) = 0
• v is a vector of coordinates
• c is a vector of coefficients
• Equation:
(x-c1)2 + (y-c2)2 = c32
• Three parameters (c1, c2, c3)
• Cube like cells
• Accumulators of the form A(i, j, k)
• Increment c1 and c2 , solve of c3 that satisfies the equation
• Update the accumulator corresponding to the cell
associated with triplet (c1, c2, c3)
Edge-linking based on Hough Transformation
1. Compute the gradient of an image and threshold it to
obtain a binary image.
2. Specify subdivisions in the -plane.
3. Examine the counts of the accumulator cells for high
pixel concentrations.
4. Examine the relationship (principally for continuity)
between pixels in a chosen cell.

• Continuity
• Based on computing the distance between disconnected
pixels identified during traversal of the set of pixels
corresponding to a given accumulator cell.
• A gap at any point is significant if the distance between
that point and its closet neighbor exceeds a certain
threshold.
Continuity

link criteria:
1) the pixels belonged to one of the set of pixels linked
according to the highest count
2) no gaps were longer than 5 pixels
Global Processing via Graph-Theoretic Techniques

• A global approach based on representing edge

segments in the form of a graph and searching the
graph for low-cost paths that correspond to
significant edges.

• Advantage:
– performs well in the presence of noise

• Disadvantage:
– complicated and requires more processing time.
Global Processing via Graph-Theoretic Techniques

• Graph G = (N,U):
– A finite, nonempty set of nodes N together with
a set U of unordered pairs of distinct elements of
N.
• (ni,nj) of U: arc

• Directed graph:
– a graph in which arcs are directed
– If ni to nj is directed, nj is a successor of its
parent node ni.
Global Processing via Graph-Theoretic Techniques

• Expansion of node:
– Identifying the successors of a node
– Level 0 consists of a single node (start or root node)
– Last level contains the goal nodes.
• A sequence of nodes n1,n2,…,nk (with each ni
being a successor of ni-1) is called a path from n1
to nk and its cost is:
k
c =  c(ni−1 , ni )
i=2
Global Processing via Graph-Theoretic Techniques

• Edge element:
– The boundary between two pixels p & q such
that p and q are 4-neighbors.
• Edge:
– A sequence of connected edge elements.
Minimum cost path

c( p, q) = H −[ f ( p) − f (q)]

H: the highest intensity value in the image

Global Processing via Graph-Theoretic Techniques
Global Processing via Graph-Theoretic Techniques
Thresholding

image with dark image with dark

background and background and
a light object two light objects

58
Multilevel thresholding

• A point (x,y) belongs to

– to an object class if T1 < f(x,y)  T2
– to another object class if f(x,y) > T2
– to background if f(x,y)  T1
• T depends on
– only f(x,y) : only on gray-level values →Global threshold
– both f(x,y) and p(x,y) : on gray-level values and its
neighbors →Local threshold

59
The Role of Illumination

f(x,y) = i(x,y) r(x,y)

Illumination : the amount of source

illumination incident on the scene

Reflectance : the amount of illumination

reflected by the objects in the scene

(c) easily use global thresholding :

object and background are separated
(e) difficult to segment

60
Histogram distortion
• f(x,y) = r(x,y) i(x,y)
• z(x,y) = ln f(x,y) = ln r(x,y) + ln i(x,y) = r’(x,y) + i’(x,y)
• H(z(x,y)) = H(r’(x,y)) * H(i’(x,y)) , where * denotes the
convolution and H() refers to the histogram
• If i(x,y) were constant, i’(x,y) would be constant also, and its
histogram will be a simple spike or an impulse
• Convolution with an impulse will leave the shape unchanged
• If i(x,y) had a broader histogram, i’(x,y) will smear H(r’(x,y))

61
Illumination compensation

• Compensate nonuniformity by projecting the illumination pattern onto a

constant, white reflective surface.

• Thus, g(x,y) = k i(x,y) , where k is a constant that depends on the surface

and i(x,y) is the illumination pattern

• For any image f(x,y) = i(x,y) r(x,y) obtained with the same illumination
function

• Simply dividing f(x,y) by g(x,y) yields a normalized function h(x,y)

h(x,y) = f(x,y)/g(x,y) = r(x,y)/k

• Thus, if r(x,y) can be segmented with T, we can use a single threshold T/k to
segment h(x,y)

62
Pixel Oriented Image Segmentation: Thresholding
Intensity Thresholding Example
Automatic Threshold Level Selection
The major problem of intensity thresholding is to find a good
threshold level
Algorithm: effective for bimodal histogram
1. Set initial value of T

2. T1 = Average( p(x, y) p(x, y)  T )

3. T2 = Average( p(x, y) p(x, y)  T )

T1 + T2
4. T =
2

5. Repeat step 2
Automatic Threshold Level Selection Example
Multilevel Intensity Thresholding

Threshold Level
Histogram
1500
T1 = 158
1000
T2 = 196
500
T3 = 228
0

0 50 100 150 200 250

T1< P <T2 T2< P <T3 P > T3

Noise Problem

peak
Image degraded by Histogram
Gaussian noise ( =12) 250

200
T1 = 158
150
T2 = 196
100

50
T3 = 228
0

0 50 100 150 200 250

T1< P <T2 T2< P <T3 P > T3

Example of Nonuniform Illumination Problem

900

800

700

600

500

400

300

200

100

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

T=0.4

Error
Nonuniform Illumination and Global Thresholding

Global threshold level

Global thresholding of nonuniform

illumination image can cause huge
errors!
Histogram

Nonuniform illumination Global thresholding

image result
Nonuniform Illumination and Local Thresholding

Local thresholding:
1. Divide an image into subimages.
2. Threshold each subimage independently
1. Compute histogram of each subimage and select a
suitable threshold value for each subimage
2. threshold each subimage using a threshold value in 2.1
3. Combine all local thresholding results

Error

16 subimages Result of local thresholding

Histogram of Subimages and Local Thresholding
If areas of object and
background are not
balanced, a histogram
will be unimodal.

If areas of object and

background are nearly
equal, a histogram will
be bimodal
Optimum Thresholding

• The histogram of an image containing two principal

brightness regions can be considered an estimate of the
brightness probability density function p(z):
the sum (or mixture) of two unimodal densities (one for
light, one for dark regions).

• The mixture parameters are proportional to the areas of the

picture of each brightness.
• If the form of the densities is known or assumed,
determining an optimal threshold (in terms of minimum
error) for segmenting the image is possible.
Optimum Thresholding
Background

p1(z) = PDF of object pixels

Object
p2(z) = PDF of background pixels

Error due to background pixels

classified as object pixels is :
E1 (T ) =  p (z)dz
−
2


Error due to object pixels
classified as background pixels is: E2 (T ) =  p1 (z)dz
T

Total error = E(T ) = P2 E1 (T ) + P1E2 (T )

P1 = Probability of occurrence of object pixels
P2 = Probability of occurrence of background pixels
Solution to Optimum Thresholding

Differentiating E(T) with respect to T and equate with 0 :

P1 p1 (T ) = P2 p2 (T )

Estimating densities : model whose parameters are reasonably

simple to obtain
• Gaussian densities
• If variances are same, a single threshold can be found as :
Min. Mean Square Error Approach

The mean square error between the (continuous) mixture

density p(z) and the (discrete) image histogram h(z) is :

In general, determining analytically the parameters that

minimizes this mean square error is not a simple matter
Optimum Thresholding

• Preprocessing
1. Each pixel was mapped with a log function
2. Image before injection of contrast medium is subtracted from the one
obtained after.
3. Several angiograms were summed
Optimum Thresholding

• 7x7 grid of the preprocessed image with 50% overlap(64x64 window in 256x256 image)
1. A test of bimodality for each window
2. The remaining histograms were then fitted by bimodal Gaussian density curves.
3. Only regions with bimodal histograms were assigned thresholds
4. Thresholds for remaining regions were obtained by interpolations
5. The second interpolation was carried out by point by point by using neighboring
theshold values
6. Finally, a binary decision was carried out for each pixel
Threshold Selection Based on Boundary Characteristics

• The chances of selecting a good threshold are increased if

the histogram peaks are:
– Tall
– Narrow
– Symmetric
– Separated by deep valleys

• One way to improve the shape of histograms is to consider

only those pixels that lie on or near the boundary between
objects and the background.
– Thus, histograms would be less dependent on the
relative sizes of objects and the background.
Threshold Selection Based on Boundary Characteristics

• Problem:
– The assumption that the boundary between objects and
background is known.
– Not available during segmentation.
• Solution:
– An indication of whether a pixel is on an edge may be
computed by its gradient.
– The Laplacian yields information on whether a pixel
lies on the dark or light side of an edge.
– The average value of the Laplacian is 0 at the transition
of an edge, so deep valleys are produced in the
histogram.
Smoothed Step Edge and Its Derivatives
Threshold Selection Based on Boundary Characteristics

• In essence:

• In the image s(x,y):

– pixels that are not on an edge are labeled 0
– pixels on the dark side of an edge are labeled +
– pixels on the light side of an edge are labeled –

• Light background/dark object:

(…) (-,+) (0 or +) (+,-) (…)

0 1 0
Threshold Selection Based on Boundary Characteristics
Threshold Selection Based on Boundary Characteristics
 Thresholds Based on Several Variables

• Multispectral thresholding : when a sensor makes

available more than one variable to characterize
each pixel in an image (e.g. color imaging, RGB)

• Each pixel is characterized by 3 values, and the

histogram becomes 3D. So thresholding now is
concerned with finding clusters of points in 3D
space.
– Instead of the RGB model, the HSI model might
be used too.
Pixel Oriented Image Segmentation for Color Images

RGB, CMY color models:

Thresholding based on distance in the color space.

HSI color model:

Thresholding based on H and S component mainly.
Color Image Segmentation Example
Pixel Oriented Image Segmentation for Multispectral Images
pixel oriented image segmentation
Multispectrum partition
Feature space
Image Domain

From www.jpl.nasa.gov/radar/
sircxsar/munch.html
Self Organizing Map for Color Image Segmentation

SOM
Region Oriented Image Segmentation

• The objective of segmentation is to partition an image into regions.

• Region oriented image segmentation
1. Region Growing
2. Region Splitting and Merging

Connected P
pixels

Pixel P and
its neighbors
Region Growing Algorithm

seed pixel
Region Growing Image Segmentation Example
Region Growing Image Segmentation Example

Histogram

X-ray image of defective weld

Region Growing Image Segmentation Example
Region Splitting and Merging Algorithm
Quadtree for Region Splitting Representation

•Subdivide an image initially into a set of disjoint regions and then

merge the regions in an attempt to satisfy certain conditions
•Segment R into smaller regions Ri with P(Ri)=TRUE for some
predicate P → quadtree
1. Split a region Ri into quadrants if P(Ri)=FALSE
2. Merge any adjacent regions Ri and Rj if P(Ri U Rj ) =TRUE
3. Stop when no further merging or splitting is possible
Region Splitting Algorithm

Region Splitting
Region Splitting Example

Region Spliting
standard deviation 5
Region Merging Algorithm
2. Merging
Region Merging Example

Region Merging
Region Splitting and Merging Example

• P(Ri)=TRUE if at least 80% of the pixels in are in have

the property of | zi − mi | 2 i
Morphological Watersheds

• Until now, segmentation is based on

• Detection of discontinuities
• Thresholding
• Region processing
• Segmentation based on morphological watersheds
• More stable segmentation
• Continuous segmentation boundaries
•Incorporates knowledge-based constraints in the
segmentation process
• Topographic interpretation in which we consider points
• belonging to a regional minimum
• at which a drop of water fall into a single minimum
– catchment basin or watershed of that minimum
•at which water would fall into more than one
minimum –divide lines or watershed lines
Watershed

• Segmentation = to find the watershed lines

1. Finding downstream path from each pixel
– Local gradient
2. Fill from the bottom (Immersion or flooding)
Morphological Watersheds - Immersion

•Punch a hole in each regional minimum and the entire

topography is flooded from below by letting water rise
through the holes at a uniform rate.
•When rising water is about to merge, a dam is built to
prevent the merging.
•The flooding will eventually reach a stage when only the
tops of the dams are visible.
•These dam boundaries correspond to the divide lines of the
watersheds.
• Therefore, continuous boundaries are extracted.
Morphological Watersheds
Morphological Watersheds
Applications of watershed

• Extraction of nearly uniform (bloblike)

objects from the background
• Regions with small variations of gray level
→ small gradient
• Watershed segmentation applied to gradient
image instead of the image itself
Practical Algorithm

• Make the gradient of the image

• Blur the image slightly
• Find all local minima (pixels that are less than all of neighbors) –
number these; they are the catchment basins
• For each pixel in the image:
– Find the minimum value in its neighborhood – continue following
minimum values until a catchment basin or previously labeled pixel is
encountered
– Label the pixel with the catchment basin number
• The boundaries between the catchment basins define the
watershed boundaries
Practical Algorithm

• Make the gradient magnitude image by evaluating the

magnitude at each image point
• Start at threshold T=1
• Find pixels above threshold and pixels below or equal to T
• Let T=T+1
• If a region of pixels above T combines with a region of pixels
below or equal to T, then mark as a watershed boundary
• Repeat until highest gradient magnitude is reached (T=K-1)
Dam Construction

When threshold =T, there are 2 partially flooded

catchment basins (2 connected components)

When threshold =T+1, 2 catchment basins merge

(1 connected component)– need to build a dam

Dilate the two components subject to the constrain

of the merged component area. Dam is selected as
a set of connected pixels, which are equidistant
from 2 components.
The Minimum Following Algorithm

• Using “runoff water” analogy, we could also compute the watershed

regions by evaluating which pixels “drain” into which catchment
basins
• In other words, we can trace the flow (in the direction of the steepest
descent) to match each pixel to a local minimum ( a catchment
basin)
Watershed algorithm

• M1,M2,…,MR : points of in the regional minina of an

image(gradient) g(x,y)
• C(Mi) : catchment basin points
• T[n] : points of g(x,y) < n
• Flood from min+1 to max+1
• Cn(Mi) : catchment basin points at stage n
• Cn(Mi) = C(Mi) AND T[n]
• C[n] = U1,R Cn(Mi)
• C[max+1] = U1,R C(Mi) C[n − 1]  C[n]  T[n]
Watershed algorithm

• Each connected component of C[n-1] is contained in

exactly one connected component of T[n]
• Initially C[min+1] = T[min+1]
• Assuming that C[n-1] has been constructed,
– Q : the set of connected components in T[n]
– Then either
1. q  C[n − 1] =  or
2. q  C[n −1] = 1 connected component
3. q  C[n −1] >= 1 connected component
4. ,where
q  Q[n]
Watershed algorithm

1. q  C[n − 1] = 
– A new minimum is encountered
– q is added to C[n-1] to form C[n]
2. q  C[n −1] = 1 connected component
– q lies within a catchment basin of some regional
minima
3. q  C[n −1] >= 1 connected component
– All, or part of, a ridge separating two or more
catchment basins is encountered
– A dam must be built
Gradient Image

Original P Surface of P
image

P at edges look
like mountain ridges.
Morphological Watersheds

(Images from Rafael C. Gonzalez and Richard E.

Wood, Digital Image Processing, 2nd Edition.
Morphological Watersheds

• Oversegmentation due to noise and local irregularity

• Limit the number of allowable regions
• A marker is a connected component belonging to an image
1. Internal marker : associated with objects of interest
2. External marker : associated with background
• Marker selection :
• Preprocessing(smoothing typically)
• Define a set of criteria that markers must satisfy
Morphological Watersheds

• After smoothing,
• Internal markers are set :
• A region that is surrounded by points of higher altitude
• The points in the region form a connected component
• All points in the connected component have the same gray-level value
• Watershed algorithm is applied with markers as local minima → watershed
lines in (a) which is are external markers
• Partition each of these regions into 2 : a single object and the background
The use of motion in segmentation

• Motion is a powerful cue used by humans and many anirnals to extract

objects of interest from a background of irrelevant detail.
• Motion arises from a relative displacement between the sensing system and
the scene.
• Motion in spatial and frequency domain
• Pixel difference > T : form a difference image
• Noise removal
• An accumulated difference image (ADI) is formed by comparing this
reference image with every subsequent image in the sequence.
• A counter for each pixel location in the accumulative image is
incremented every time a difference occurs at that pixel location between
the reference and an image in the sequence.
• absolute, positive and negative ADIs
The use of motion in segmentation
Establishing a reference image

•When a non-stationary component has moved completely out of its position in

the reference frame,
•the corresponding background in the present frame can be duplicated in
the location originally occupied by the object in the reference frame.