8/3/2022

Module 5

Image Segmentation

• Image segmentation divides an image into

regions that are connected
– have some similarity within the region and some
difference between adjacent regions

• The goal is usually to find individual objects in

an image

• Segmentation is concerned with dividing an

image into meaningful regions

1
 8/3/2022

Classification of Image Segmentation Techniques

• Local Segmentation
– Segmenting sub-images which are small windows on a
whole image
– Number of pixels available will be lower than the global
segmentation

• Global Segmentation
– Concerned with segmenting a whole image
– Global segmentation deals with segments consisting of a
relatively large number of pixels
– This makes estimated parameter values for global
segments more robust

Approaches to segmentation
• fundamentally two kinds of approaches to
segmentation on the basis of properties of pixels:
discontinuity and similarity.

• Similarity may be due to pixel intensity, color or

texture.
• Differences are sudden changes (discontinuities)
in any of these but especially sudden changes in
intensity along a boundary line, which is called an
edge.

2
8/3/2022

3
8/3/2022

4
 8/3/2022

Region-Based Segmentation

• Region-based segmentation is based on the

connectivity of similar pixels in a region.
– Each region must be uniform.
– Connectivity of the pixels within the region is very
important.
• There are two main approaches to region-based
segmentation: region growing and region splitting.

Region-Based Segmentation
Basic Formulation

• Let R represent the entire image region.

• Segmentation is a process that partitions R into subregions,
R1,R2,…,Rn, such that
n
(a)  Ri  R
i 1
(b) Ri is a connected region, i  1,2,..., n
(c) Ri  R j   for all i and j , i  j
(d) P ( Ri )  TRUE for i  1,2,..., n
(e) P( Ri  R j )  FALSE for any adjacent regions Ri and R j
where P(Rk): a logical predicate defined over the points in set Rk
For example: P(Rk)=TRUE if all pixels in Rk have the same gray
level.

5
 8/3/2022

Region Growing
• Groups pixels or sub-regions into larger regions based on
predefined criteria.
• The basic idea is to start with a set of seed points and from
these grow regions by appending to each seed those
neighboring pixels that have properties similar to the seed
(specified ranges of gray level or colour)
• Seed points are found out by computing at every pixel value
the same set of properties that ultimately will be used to
assign pixels to regions during growing process.
• If the result of these computations show cluster of values, the
pixels whose properties place them near the centroid can be
used as seeds

6
 8/3/2022

• An initial set of small areas are iteratively merged according

to similarity constraints
• Start by choosing an arbitrary seed pixel and compare it with
neighbouring pixels
• Region is grown from the seed pixel by adding in
neighbouring pixels that are similar, increasing the size of the
region
• When the growth of one region stops we simply choose
another seed pixel which does not yet belong to any region
and start again
• This whole process is continued until all pixels belong to
some region
• Region growing methods often give very good
segmentations that correspond well to the observed edges

Region Growing Process. (a) sample point cloud; (b) one seed point selected; (c) 10 nearest
neighbor points added; (d) 100 nearest neighbor points added; (e) 1000 nearest neighbor
points added; (f) 2000 nearest neighbor points added; (g) all neighbor neighbor points
added, region is complete.

7
 8/3/2022

Region Splitting and Merging

• The main problem with region splitting is
determining where to split a region
• One method to divide a region is to use a
quadtree structure.
• Quadtree: a tree in which nodes have exactly
four descendants.

8
8/3/2022

9
8/3/2022

10
 8/3/2022

Clustering Techniques
• Clustering (cluster analysis) is grouping objects
based on similarities
• Clustering can be used in many areas, including
machine learning, computer graphics, pattern
recognition, image analysis, information retrieval,
bioinformatics, and data compression
• Clustering
– Hierarchical
– Partitional

Clustering

Hierarchical Partitioning

Agglomerative Divisive K-Means

11
 8/3/2022

• Points in the same cluster are closer to each

other.
• Points in the different clusters are far apart.

Hierarchical Clustering
• Hierarchical clustering is a method of cluster analysis
which seeks to build a hierarchy of clusters
• Hierarchical clustering which is used to group the
unlabeled datasets into a cluster and also known
as hierarchical cluster analysis or HCA.
• In this algorithm, the hierarchy of clusters is
developed in the form of a tree, and this tree-shaped
structure is known as the dendrogram.

12
 8/3/2022

Hierarchical clustering can be:

• Agglomerative – it starts with an individual
element and then groups them into single
clusters (Bottom up approach)
• Divisive – it starts with a complete dataset
and divides it into partitions (Top Down
Approach)

13
 8/3/2022

Agglomorative Hierarchical Clustering (AHC)

• Each data point is treated as a single cluster. We have K clusters in
the beginning. At the start, the number of data points will also be K

• Now we need to form a big cluster by joining 2 closest data points

in this step. This will lead to total K-1 clusters

• Two closest clusters need to be joined now to form more clusters.

This will result in K-2 clusters in total

• Repeat the above three steps until K becomes 0 to form one big
cluster. No more data points are left to join

• After forming one big cluster at last, we can use dendrograms to

split the clusters into multiple clusters depending on the use case

14
 8/3/2022

We mention that “closest data points (or clusters)” are combined

together. But how do the algorithms identify closest ones?

15
 8/3/2022

Linkage Criteria:

• It determines the distance between sets of observations as a

function of the pairwise distance between observations.

• In Single Linkage, the distance between two clusters is the

minimum distance between members of the two clusters

• In Complete Linkage, the distance between two clusters is the

maximum distance between members of the two cluster

• In Average Linkage, the distance between two clusters is the

average of all distances between members of the two clusters

• In Centroid Linkage, the distance between two clusters is is

the distance between their centroids

Divisive Clustering
• Divisive hierarchical clustering is exactly the
opposite of Agglomerative Hierarchical clustering.
• In Divisive Hierarchical clustering, all the data
points are considered an individual cluster, and in
every iteration, the data points that are not
similar are separated from the cluster.
• The separated data points are treated as an
individual cluster. Finally, we are left with N
clusters.

16
8/3/2022

17
 8/3/2022

• How to choose which cluster to split?

Check the sum of squared errors of each cluster
and choose the one with the largest value.
The cluster with the largest SSE value is separated
into 2 clusters, hence forming a new cluster

Partition Clustering
• Uses an iterative optimisation procedure that aims at minimising
an objective function f
• f measures the goodness of clustering
• Composed of 2 learning steps
– Partitioning of each pattern to its closest cluster
– Computation of the cluster centroids
• Clustering Procedure start from an initial solution with a
known number of clusters
• Categorised into
• Probabilistic clustering
• K-medoids
• K-means Clustering

18
 8/3/2022

K means clustering
• our aim here is to minimize the distance between the
points within a cluster
• There is an algorithm that tries to minimize the distance
of the points in a cluster with their centroid – the k-means
clustering technique
• K-means is a centroid-based algorithm, or a distance-
based algorithm, where we calculate the distances to
assign a point to a cluster. In K-Means, each cluster is
associated with a centroid
• The main objective of the K-Means algorithm is to
minimize the sum of distances between the points and
their respective cluster centroid.

K-Means Clustering
• It is an iterative procedure
• Clusters data by iteratively computing a mean
intensity for each class and segmenting the image by
classifying each pixel in the class with the closest
means

19
8/3/2022

20
8/3/2022

21
 8/3/2022

Stopping Criteria for K-Means

Clustering
• There are essentially three stopping criteria
that can be adopted to stop the K-means
algorithm:
– Centroids of newly formed clusters do not change
– Points remain in the same cluster
– Maximum number of iterations are reached

22
8/3/2022

23
 8/3/2022

Image segmentation based on thresholding

• Thresholding techniques produce segments having

pixels with similar intensities
• Useful for establishing boundaries in images that
contain solid objects resting on a contrasting
background
• Thresholding requires that an object has
homogeneous intensity and a background with a
different intensity level
• Types
– Global Thresholding
– Adaptive Thresholding

Global Thresholding
• A threshold value T is chosen as the threshold

• Value of T has to be selected in an optimal manner

24
8/3/2022

25
 8/3/2022

Selection of Threshold T in Global Thresholding

1. Select an initial estimate for T

2. Segment the image using T. This will produce two groups of
pixels: G1 consists of all pixels with gray level values > T and
G2 consists of pixels with values <= T
3. Compute the average gray level values µ1 and µ2 for the
pixels in regions G1 and G2.
4. Compute a new threshold value: T = ½ (µ1 + µ2 ).
5. Repeat steps 2 through 4 until the difference in T in
successive iterations is smaller than a predefined parameter
T0
 Error will be more in Global Thresholding.
 So Adaptive Thresholding is used

26
8/3/2022

27
8/3/2022

28
 8/3/2022

Adaptive Thresholding
• In many cases, background gray level is not a constant
• Object contrast varies within an image
• So, threshold in one area might not work well in other
areas of the image.
• So, global thresholding can’t be used there
• Adaptive Thresholding
– Divide the image into sub-images
– Assume that the illumination in each sub-images is constant.
– Use a different threshold for each sub-image.
– Alternatively – use a running window (and use the threshold
of the window only for the central pixel )

29
 8/3/2022

Limitation of Thresholding Technique

• In its simplest form, only 2 classes are
generated and it cannot be applied to all types
of images
• Thresholding technique doesn’t take into
account the spatial characteristics of an
image.
• This causes it to be sensitive to noise and
intensity inhomogeneities.

Detection of Discontinuities

• There are three kinds of discontinuities of intensity: points,

lines and edges.
• The most common way to look for discontinuities is to scan a
small mask over the image. The mask determines which kind
of discontinuity to look for.
9
R  w1 z1  w2 z2  ...  w9 z9   wi zi
i 1

30
 8/3/2022

Detection of Discontinuities
Point Detection

R T
where T : a nonnegative threshold

Detection of Discontinuities
Line Detection

• Only slightly more common than point detection is to find a

one pixel wide line in an image.
• For digital images the only three point straight lines are only
horizontal, vertical, or diagonal (+ or –45).

31
 8/3/2022

Region-Based Segmentation

• Region-based segmentation is based on the

connectivity of similar pixels in a region.
– Each region must be uniform.
– Connectivity of the pixels within the region is very
important.
• There are two main approaches to region-based
segmentation: region growing and region splitting.

32
 8/3/2022

Region-Based Segmentation
Basic Formulation

• Let R represent the entire image region.

• Segmentation is a process that partitions R into subregions,
R1,R2,…,Rn, such that
n
(a)  Ri  R
i 1
(b) Ri is a connected region, i  1,2,..., n
(c) Ri  R j   for all i and j , i  j
(d) P ( Ri )  TRUE for i  1,2,..., n
(e) P( Ri  R j )  FALSE for any adjacent regions Ri and R j
where P(Rk): a logical predicate defined over the points in set Rk
For example: P(Rk)=TRUE if all pixels in Rk have the same gray
level.

33
 8/3/2022

EDGE DETECTION

CONTENTS
• Introduction
• Types of Edges
• Steps in Edge Detection
• Methods of Edge Detection
– First Order Derivative Methods
• First Order Derivative Methods - Summary
– Second Order Derivative Methods
• Second Order Derivative Methods - Summary
– Optimal Edge Detectors
• Canny Edge Detection

1
 8/3/2022

INTRODUCTION

• Edge - Area of significant change

in the image intensity / contrast

• Edge Detection – Locating areas

with strong intensity contrasts

• Use of Edge Detection –

Extracting information about the
image. E.g. location of objects
present in the image, their
shape, size, image sharpening
and enhancement

2
 8/3/2022

TYPES OF EDGES
• Variation of Intensity /
Gray Level
– Step Edge
– Ramp Edge
– Line Edge
– Roof Edge

• Step edge: the image intensity abruptly changes from one

value to one side of the discontinuity to a different value on
the opposite side
• Line edge: If the segment is very narrow, it necessarily has two
edges in close proximity. This arrangement is called line edge
• Ramp edge: A ramp allows smoother transition between
segments. A ramp edge is used for modelling the blurred
edges created from sampling a scene containing objects not
aligned to pixel grid
• Roof edge: Two nearby ramp edges result in a line structure
called roof.

3
 8/3/2022

Steps in Edge Detection

• Filtering – Filter image to improve performance of the
Edge Detector wrt noise
• Enhancement – Emphasize pixels having significant
change in local intensity
• Detection – Identify edges - thresholding
• Localization – Locate the edge accurately, estimate edge
orientation

Noisy Image
• Example of Noisy Image

4
 8/3/2022

METHODS OF EDGE DETECTION

• First Order Derivative / Gradient Methods

– Roberts Operator
– Sobel Operator
– Prewitt Operator
• Second Order Derivative
– Laplacian
– Laplacian of Gaussian
– Difference of Gaussian
• Optimal Edge Detection
– Canny Edge Detection

5
 8/3/2022

First Derivative
• At the point of greatest
slope, the first derivative
has maximum value
– E.g. For a Continuous 1-
dimensional function f(t)

Detection of Discontinuities
Gradient Operators

• First-order derivatives:
– The gradient of an image f(x,y) at location (x,y) is defined
as the vector:
Gx   fx 
f      f 
G y   y 
– The magnitude of this vector: f  mag(f )  G x2  G y2 
1
2

 Gx 
– The direction of this vector:  ( x, y )  tan 1  

G
 y

6
8/3/2022

7
8/3/2022

8
 8/3/2022

Robert Operator
• Main objective is to determine the differences
b/w adjacent pixels.
• Use {+1, -1} that calculates the difference
between adjacent pixels (Forward differences)
• Roberts kernels are too small to reliably find
edges in the presence of noise (Disadvantage)

9
 8/3/2022

Prewitt Kernel
• Masks of 2X2 are not easy to implement because they do not have clear
centre.
• An approach is to find the gradient using 3X3 mask

• In this formulation, the difference between the first and third rows of 3x3
image region approximates the derivative in x direction, and the difference
between third and first columns approximates the derivate in y direction

10
 8/3/2022

Advantages:
• Good performance on detecting vertical and horizontal edges
• Best operator to detect the orientation of an image
• Prewitt mask differentiates in one direction and averages in other
direction . So, edge detector is less vulnerable to noise

Limitations:
• The magnitude of coefficient is fixed and cannot be changed
• Diagonal direction points are not preserved always

Sobels Kernel
• Relies on central differences but gives greater
weight to the central pixels when averaging

• A weight value of 2 is used to achieve some

smoothing by giving more importance to
centre point

11
 8/3/2022

Sobels Kernel

• Noise suppression characteristic is better than

Prewitt mask

First Order Derivative Methods - Summary

 Noise – simple edge detectors are affected by noise –
filters can be used to reduce noise

 Roberts operator is very sensitive to noise

 Edge Thickness – Edge is several pixels wide for Sobel

operator– edge is not localized properly

 Sobel operator goes for averaging and emphasizes on the

pixel closer to the center of the mask.

 It is less affected by noise and is one of the most popular

Edge Detectors.

12
 8/3/2022

• Compare the output of the

Sobel Operator with that of
the Roberts Operator:

– Roberts operator has missed

a few edges
– Sobel operator detects
thicker edges

Outputs of Sobel (top) and Roberts operator

Detection of Discontinuities
Gradient Operators: Example

f  G x  G y

13
 8/3/2022

Detection of Discontinuities
Gradient Operators: Example

14
 8/3/2022

Second Order Derivative Methods

• Zero crossing of the second derivative of a

function indicates the presence of a maxima

15
 8/3/2022

Laplacian Filter
The Laplacian is defined as follows:

2 f 2 f
 f  2  2
2

 x  y
2 f
 f ( x  1, y )  f ( x  1, y )  2 f ( x, y )
2 x

2 f
 f ( x, y  1)  f ( x, y  1)  2 f ( x, y )
2 y

32

16
 8/3/2022

Laplacian Filter

So, the Laplacian can be given as follows:

 2 f  [ f ( x  1, y )  f ( x  1, y )
 f ( x , y  1)  f ( x , y  1)]
 4 f ( x, y )
Can we implement it 0 1 0
using a filter/ mask?
1 -4 1

0 1 0
33

Laplacian Filter

34

17
 8/3/2022

• The Laplacian generally is not used in its

original form for edge detection for several
reasons
• As a second order derivative, the laplacian is
unacceptably sensitive to noise
• The magnitude of Laplacian process double
edges an undesirable effect because it
complicates segmentation
• Laplacian is unable to detect edge direction

Effect of noise

18
 8/3/2022

Derivative theorem of convolution

19
 8/3/2022

Second Order Derivative Methods - Laplacian

of Gaussian
• Also called Marr-Hildreth Edge Detector
• Steps
– Smooth the image using Gaussian filter
– Enhance the edges using Laplacian operator
– Zero crossings denote the edge location
– Use linear interpolation to determine the sub-
pixel location of the edge

Detection of Discontinuities
Gradient Operators

• Consider the function: A Gaussian function

r2
 2
h( r )  e 2
where r 2  x 2  y 2
and  : the standard deviation
• The Laplacian of h is
r2 The Laplacian of a
 r 2   2   2 2 Gaussian (LoG)
 h( r )  
2
e
 
4

• The Laplacian of a Gaussian sometimes is called the Mexican
hat function. It also can be computed by smoothing the image
with the Gaussian smoothing mask, followed by application of
the Laplacian mask.

20
 8/3/2022

Laplacian of Gaussian – contd.

• Greater the value of , broader is the

Gaussian filter, more is the smoothing
• Too much smoothing may make the detection
of edges difficult

21
 8/3/2022

Laplacian of Gaussian - contd.

• Also called the Mexican Hat operator

Laplacian of Gaussian – contd.

• Mask

Discrete approximation to LoG function with Gaussian = 1.4

22
 8/3/2022

Second Order Derivative Methods -

Difference of Gaussian - DoG
• LoG requires large computation time for a
large edge detector mask
• To reduce computational requirements,
approximate the LoG by the difference of two
LoG – the DoG

x2  y2 x2  y2
( ) ( )
2 12 2 2 2
DoG ( x, y )  e e

23
 8/3/2022

Difference of Gaussian – contd.

• Advantage of DoG
– Close approximation of LoG
– Less computation effort
– Width of edge can be adjusted by changing 1
and 2

Second Order Derivative Methods - Summary

• Second Order Derivative methods especially

Laplacian, are very sensitive to noise
• Probability of false and missing edges remain
• Localization is better than Gradient Operators

24
 8/3/2022

Canny edge detection

Canny edge detection technique with regards to following
criteria (Optimal Edge detection criteria):

• Detection: The probability of detecting real edge points

should be maximized while the probability of falsely
detecting non-edge points should be minimized. This
corresponds to maximizing the signal-to-noise ratio.
• Localization: The detected edges should be very close
to real edges. There will be minimum gap between real
edge and detected Edge.
• Number of responses: One real edge should not result
in more than one detected edge.

The Canny edge detection algorithm is

composed of 4 steps:
• Noise reduction;
• Gradient calculation;
• Non-maximum suppression;
• Hysteresis Thresholding.

25
 8/3/2022

Steps in Canny edge detection

• Step 1: Noise Reduction
Since edge detection is susceptible to noise in the
image, first step is to remove the noise in the image
with a 5x5 Gaussian filter.

26
 8/3/2022

• Step 2: Gradient Calculation

 Smoothened image is then filtered with a Sobel kernel
in both horizontal and vertical direction to get first
derivative in horizontal direction (Gx) and vertical
direction (Gy).
 From these two images, we can find edge gradient and
direction for each pixel as follows:

G  Gx 2  Gy 2  Gx  Gy

 Gy 
  tan 1  
 Gx 

• Gradient direction is always perpendicular to

edges. It is rounded to one of four angles
representing vertical, horizontal and two
diagonal directions

27
 8/3/2022

• Step 3: Non-maximum Suppression

After getting gradient magnitude and direction, a
full scan of image is done to remove any
unwanted pixels which may not constitute the
edge.
For this, at every pixel, pixel is checked if it is a
local maximum in its neighborhood in the
direction of gradient.

28
8/3/2022

29
 8/3/2022

• Hysteresis Thresholding:
This stage decides which are all edges are really
edges and which are not.
For this, we need two threshold values, minVal
and maxVal.
Any edges with intensity gradient more than
maxVal are sure to be edges and those below
minVal are sure to be non-edges, so discarded.
Those who lie between these two thresholds are
classified edges or non-edges based on their
connectivity. If they are connected to "sure-edge"
pixels, they are considered to be part of edges.
Gradient Value

30
 8/3/2022

• The edge A is above the maxVal, so considered as "sure-edge“

• Although edge C is below maxVal, it is connected to edge A,
so that also considered as valid edge and we get that full
curve
• But edge B, although it is above minVal and is in same region
as that of edge C, it is not connected to any "sure-edge", so
that is discarded. So it is very important that we have to select
minVal and maxVal accordingly to get the correct result
• This stage also removes small pixels noises on the assumption
that edges are long lines
• So what we finally get is strong edges in the image.

31
 8/3/2022

An edge is not a line...

How can we detect lines ?

Finding lines in an image

y b

b0

x m0 m
image space Hough space

• Connection between image (x,y) and Hough

(m,b) spaces
– A line in the image corresponds to a point in Hough
space
– To go from image space to Hough space:
• given a set of points (x,y), find all (m,b) such that y = mx + b

32
 8/3/2022

Finding lines in an image

y b

y0

x0 x m
image space Hough space

• Connection between image (x,y) and Hough (m,b) spaces

– A line in the image corresponds to a point in Hough space
– To go from image space to Hough space:
• given a set of points (x,y), find all (m,b) such that y = mx + b
– What does a point (x0, y0) in the image space map to?

– A: the solutions of b = -x0m + y0

– this is a line in Hough space

33
 8/3/2022

• So, the 2 curves corresponding to (𝑥1 , 𝑦1) 𝑎𝑛𝑑

(𝑥2 , 𝑦2) intersect at a particular 𝜌, 𝜃 .
• That (𝜌, 𝜃) will give the straight line with those
2 points.
• So, our aim is to find out (𝜌, 𝜃) with maximum
intersection of sinusoidal curves so as to
determine a line with more number of points

34
 8/3/2022

Hough Transform – contd.

Mapping of
Edge Points in
Edge Detected Image Hough
Parameter
Space

35
 8/3/2022

Active Contour
• Active contour model, also called snakes, is a
framework in computer vision for delineating
an object outline from a possibly noisy 2D
image
• The curve formed by the connected edge
points defines the active contour
• It is a set of connected points which
interactively move so as to minimise a
specified energy function

36
 8/3/2022

• Local properties of the image such as gray

level, gradient, etc., contribute to the energy
of the snake.
• The snake reacts to the image, but moves in a
smooth continuous manner towards the
desired object boundary

37
 8/3/2022

Steps involved
• Prepare the image –
– Define an energy function which could naturally
take on low values for points located on the actual
boundary
– Generate an initial boundary by a segmentation
technique such as thresholding

• Wiggle the snake

– Compare the energies of each point on the
boundary with the energies calculated for points
in its neighbourhood.
– For each current boundary point, move the
boundary to the neighbouring point that has the
lowest energy.
– Perform this operation once on all points on the
boundary to complete one iteration of the snake
algorithm.
– Repeat this iteration until it causes no further
movement of the boundary points. – When this
happens, the snake is said to have ‘converged’ and
the segmentation is complete

38
8/3/2022

39
 8/3/2022

Brain tumor segmentation from MRI image

using greedy snake algorithm

40
8/3/2022

41