Introduction

Segmentation Techniques
Performance Evaluation
Color Image Segmentation
Conclusion

Image Segmentation

Subrajeet Mohapatra
Image Processing and Computer Vision Laboratory
Department of Electrical Engineering
National Institute of Technology Rourkela

June 9th, 2011

1/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Performance Evaluation
Color Image Segmentation
Conclusion

Table of Contents

1 Introduction
Digital Image Processing
What is Image Segmentation?
Problem Definition
Methodology
2 Segmentation Techniques
Discontinuity Based Segmentation
Point and Line Detection
Edge Detection
Similarity Based Segmentation
Thresholding Based Segmentation
Region Based Segmentation
Clustering Based Segmentation
3 Performance Evaluation
4 Color Image Segmentation
5 Conclusion

2/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Digital Image Processing
Segmentation Techniques
What is Image Segmentation?
Performance Evaluation
Problem Definition
Color Image Segmentation
Methodology
Conclusion

Digital Image & Digital Image Processing

An image is a 2D function, I = f (x , y )
where x and y are spatial coordinates
Amplitude of f at any pair of coordinates (x , y ) is called the
intensity (I) or gray level of the image.

When spatial coordinates and amplitude values are all

finite, discrete quantities, the image is called as
digital image.

Processing of such images by digital computers is called

Digital Image Processing.

3/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Digital Image Processing
Segmentation Techniques
What is Image Segmentation?
Performance Evaluation
Problem Definition
Color Image Segmentation
Methodology
Conclusion

What is Image Segmentation?

Definition
Image Segmentation is the partitioning of an image into
meaningful regions that have strong correlation with objects
or areas of the real world contained in the image.

Definition
Image Segmentation is a procedure that describes the process
of dividing an image into non overlapping, connected image
areas, called regions, on the basis of criteria governing
similarity and homogeneity.

4/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Digital Image Processing
Segmentation Techniques
What is Image Segmentation?
Performance Evaluation
Problem Definition
Color Image Segmentation
Methodology
Conclusion

Necessity of Image Segmentation

Image segmentation is a prerequisite for most of the

machine vision application or for image analysis.
Success of the machine vision applications is highly
dependent on the success of the autonomous
segmentation of images.
Every machine vision application should have a support of
robust segmentation algorithm.

5/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Digital Image Processing
Segmentation Techniques
What is Image Segmentation?
Performance Evaluation
Problem Definition
Color Image Segmentation
Methodology
Conclusion

Segmentation Examples

Figure: Original Image

Figure: Segmented Image

6/118 Subrajeet Mohapatra Image Segmentation
 Introduction
Digital Image Processing
Segmentation Techniques
What is Image Segmentation?
Performance Evaluation
Problem Definition
Color Image Segmentation
Methodology
Conclusion

Segmentation Examples

Figure: MRI Image Segmentation

7/118 Subrajeet Mohapatra Image Segmentation
 Introduction
Digital Image Processing
Segmentation Techniques
What is Image Segmentation?
Performance Evaluation
Problem Definition
Color Image Segmentation
Methodology
Conclusion

Problem Definition

Segmentation can be considered as a pixel labeling

problem.
Every pixel in an image is assigned a label such that pixels
with the same label share certain visual characteristics.
Each of the pixels in a region are similar with respect to
some characteristic, such as color, intensity, or texture.
Neighboring regions are significantly different with respect
to the same characteristics.

There is no standard segmentation algorithm which can work

reasonably well for all images.

8/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Digital Image Processing
Segmentation Techniques
What is Image Segmentation?
Performance Evaluation
Problem Definition
Color Image Segmentation
Methodology
Conclusion

Problem Definition

(a) Blood Image (b) Label Image

(c) Region 1 (d) Region 2 (e) Region 3 (f) Region 4

9/118 Subrajeet Mohapatra : Image Segmentation

 Introduction
Digital Image Processing
Segmentation Techniques
What is Image Segmentation?
Performance Evaluation
Problem Definition
Color Image Segmentation
Methodology
Conclusion

Methodology
Image segmentation algorithms are developed based on
two basic properties of intensity values:
Discontinuity
Similarity
In discontinuity based approach the partition is carried out
based on some abrupt changes in gray level intensity of
the image.
Similarity based approach is based on grouping of pixels
based on some features.

Irrespective of the segmentation algorithm employed each

technique aims at achieving low inter class similarity and high
intra class similarity.

10/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Methods of Segmentation

Discontinuity based
Detection of Isolated Points
Detection of Lines
Edge Detection
Similarity based
Thresholding
Region growing
Region Splitting and Merging
Clustering
K–Means Clustering
Fuzzy C Means Clustering

11/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Measuring Discontinuity

There are three basic types of discontinuities

Points
Lines
Edge
Image discontinuities is mostly measured using a squared
mask.
The mask is moved over the entire image.

12/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Measuring Discontinuity
The sum of products of the mask coefficients with the
corresponding image gray values is computed for each
pixel.

13/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Measuring Discontinuity

Considering a mask of size 3 × 3, the response of the mask

at each pixel is


9
R = w1 f1 + w2 f2 + w3 f3 + · · · + w9 f9 = wi fi
i =1

Where fi is the gray value of the pixel under the mask

coefficient wi .
High response of the mask indicates gray level
discontinuity.

14/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Point, Line and Edge Detection

Edge pixels are pixels at which the intensity of an image

function changes abruptly.
Edges are set of connected edge pixels. An edge
essentially demarcates between two distinctly different
regions.
Line may be embedded inside a single uniformly
homogeneous region.
An isolated point may be viewed as a line whose length
and width are equal to one pixel.

15/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Point Detection using Mask

Isolated points in an image are those points which have

abruptly different gray values than those of its surrounding
pixels.
A mask is utilized for point detection and involves
highlighting the gray value difference.
Response of such a mask is zero for a region with same
gray values for all pixels.
For central pixel with different gray value the response of
the mask is m times of the difference in gray values, where
m is the central weight of the mask.

16/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Point Detection using Mask

High response of the mask indicates a different central
value and the presence of an isolated point.
Selection of an isolated point can be formulated in terms of
an threshold T .

|R | > T
Points are detected at those pixels in the subsequent
filtered image above this threshold.
A 3 × 3 point detection mask can be represented as:

17/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Point Detection using Mask

(a) X-ray Image (b) Result point detection (c) Result Thresholding

:
18/118 Subrajeet Mohapatra Image Segmentation
 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Line Detection using Mask

Straight line segments can be detected in an image using

specific masks.
Lines can be detected in a specified direction.
The masks below will extract lines that are one pixel thick
and running in a particular direction.

(a) Horizontal (b) +45 degree (c) Vertical (d) –45 degree

19/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Line Detection using Mask

A high response of the mask indicates a presence of a line
segment.
The mask whose response is higher will determine the
orientation of the line.

(a) Wire Bond Image (b) Line detection (c) Result Thresholding

20/118 Subrajeet Mohapatra

: Image Segmentation
 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Edge Detection

It is the most common approach for detection of gray level

discontinuity in an image.
Edge is a boundary between two regions having distinct
intensity levels.

Large intensity difference between the 4th and 5th pixel

indicates an edge.

21/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Why Edge Detection is Interesting?

Edges preserve structural information of objects and

background.
A higher level of abstraction (less memory consumption).
Act as features independent from illumination variation.

22/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Edge Detection Techniques using Derivatives

Edge detection operation is essentially an operation to

detect significant local changes in the intensity level in an
image.
The change in intensity level is measured by computing
derivative of the image.
First order and second order derivative or difference
(discrete) operators are commonly used for edge detection.

23/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Derivatives

Derivatives of a digital function are defined in terms of

differences.
The first order derivative at a point x of a one dimensional
function f (x ) can be approximated as

∂f
= f (x + 1) − f (x )
∂x
Second derivative about a point x can be expressed as

∂2 f
= f (x + 1) + f (x − 1) − 2f (x )
∂x 2

24/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Edge Detection using Derivatives

95

90

85

80

75

70

65

60

55

50
0 2 4 6 8 10 12 14 16

(a) Intensity
40
40

30
30

20
20

10
10

0
0

−10
−10

−20
−20

−30 −30

−40 −40
0 5 10 15 0 2 4 6 8 10 12 14

(b) First Derivative (c) Second Derivative

:
25/118 Subrajeet Mohapatra Image Segmentation
 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Edge Detection using Derivatives

26/118 Subrajeet Mohapatra : Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Edge Detection using Derivatives

The magnitude of both first and second derivative can be

used to detect the presence of edges.
For dark to light gray level transition the sign of the
second derivative goes from positive to negative.
While for light to dark transition the sign of the second
derivative goes from negative to positive.
Unlike first derivative the second derivative produces two
pulses per edge.
The second derivative is more sensitive to edges as well
as to noise.

27/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Applying Derivative Operators

The derivative operators can be applied under the following

heads:
First order detectors use gradient operator to compute
the first derivative.
Second order detectors employ laplacian operator for
computing second derivative.

28/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Gradient Operator

The first derivative can be computed using the derivative

operator. Considering a digital image f (x , y )
The gradient of the image can be defined as
   ∂f

f = Gx ∂x
∇ = ∂f
Gy ∂y

Magnitude of the gradient is given as

f)
∇f = mag (∇
1
= [Gx2 + Gy2 ] 2
≈ |Gx | + |Gy |
29/118 Subrajeet Mohapatra Image Segmentation
 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Gradient Operator

 f is
Direction of ∇
 
−1 Gy
α(x , y ) = tan (1)
Gx

f.
α(x , y ) provides the direction of ∇
 f.
Edge direction is perpendicular to the direction of ∇

30/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Gradient Edge Detectors

Gradient based edge detectors are classified based on the

way they compute edge strength or gradient.
Prewitt Operator
Sobel Operator

31/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Prewitt Operator
Prewitt operator is a discrete differentiation operator, which
computes the gradient of the image intensity at each point
along with its orientation.
Two 3 × 3 kernels are convolved with the image to obtain
the derivatives for horizontal and vertical changes.

(a) Horizontal (b) Vertical

:
32/118 Subrajeet Mohapatra Image Segmentation
 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Sobel Operator
Sobel operator calculates the gradient of the image
intensity at each point.
Sobel operator uses two 3 × 3 kernels are convolved with
the image to obtain the derivatives for horizontal and
vertical changes.

(a) Horizontal (b) Vertical

33/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Laplacian Operator
Laplacian is the second derivative
Laplacian operator of f (x , y ) is

∂2 f ∂2 f
∇2 f =
+
∂x 2 ∂y 2
Mask implementing second derivative operator is given as

(a) Horizontal-Vertical (b) All Directions

34/118 Subrajeet Mohapatra Image Segmentation
 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Laplacian Of Gaussian Operator

Laplacian operator is highly sensitive to noise.

Initial smoothing is required before applying laplacian
operator for edge detection.
Gaussian smoothing and laplacian detection is achieved
jointly using Laplacian Of Gaussian operator (LoG).

35/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Laplacian Of Gaussian Operator

(a) Gaussian Mask Two Dimension (b) Laplacian of Gauusian (LoG)

Figure: Three Dimensional Plot of Gaussian and LoG

36/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Laplacian Of Gaussian Mask

(a) Laplacian of Gauusian (b) LoG Mask

37/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Edge Detection Results

(a) Original (b) Sobel

(c) Prewitt (d) Canny (e) LoG

38/118 Subrajeet Mohapatra Image Segmentation
 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Comparison (Gradient and Laplacian)

First order detectors are always preferable for edge

detection.
Second order detectors are highly sensitive to noise,
hence seldom used for edge detection.
Double edge detection is also a demerit of second order
detectors.
Second order detectors are useful for extracting secondary
information.
Using the zero crossing information in second derivative
the exact location of the edge can be determined.

39/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Edge Linking

Due to non uniform illumination and noise the edges

obtained by edge detectors are not always connected.
Edge linking is performed to get connected edges.
Connected edges are achieved using two approaches.
Local Processing
Global Processing

40/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Limitations of Edge–Based Segmentation

Classical edge detectors produce spurious edges and

gaps in low quality images.
Edge detection techniques use local neighborhood
information of the image. They do not consider model
based information embedded in the image.
Edge linking process sometimes leads to discontinuities
and gaps in the image.
Edge linking methods often resort to arbitrary interpolation
in order to complete boundary gaps.

41/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Similarity Based Segmentation

It is based on grouping the pixels in the image based on

certain similar feature or attribute.
The features can be intensity, color, texture etc.
Similarity based methods can be classified as:
Thresholding
Region Growing
Region Splitting and Merging
Clustering

42/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Thresholding

Thresholding is a technique for converting a gray scale or

color image to a binary image based upon a threshold
value.
Image thresholding is very useful for object extraction and
background rejection.
Belongingness of each pixel to object or background is
decided on the basis of a particular threshold.
Accurate estimation of the threshold is essential for proper
segmentation and object extraction successively.

43/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Thresholding Example

(a) Original (b) Thresholded

(c) Low Threshold (d) High Threshold

44/118 Subrajeet Mohapatra : Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Image Histogram
Image histogram describes the frequency of the intensity
values that occur in an image.
Histogram can be very efficiently used for determining the
threshold for image segmentation.

1000

900

800

700

600
Pixel Count

500

400

300

200

100

0 50 100 150 200 255

Gray Levels

(a) Original Image (b) Histogram

45/118 Subrajeet Mohapatra : Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Bimodal Histogram

46/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Bimodal Histogram

Ideal bimodal histogram consists of peaks corresponding

to the object and background regions and a valley in
between.
The object and background of images with bimodal
histogram form two different groups with distinct gray
levels.
Bi–level thresholding is employed for such images.
So a threshold T has to be selected from the valley region
for segmenting the image.

47/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Bi–level Thresholding

A single threshold is enough for segmenting an image with

bimodal histogram and is called bi–level thresholding.
For an image f (x , y ) with an bright object and dark
background, the binary segmented image can be
mathematically represented as

1 if f (x , y ) ≥ T ⇒ Object
g (x , y ) =
0 if f (x , y ) < T ⇒ Background

Every pixel intensity value has to be compared with the

threshold T to classify each pixel as a background or an
object pixel.

48/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Bi–level Thresholding Results

(a) Original Image (b) Segmented Image

49/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Multimodal Histogram

50/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Multimodal Histogram

Images with multimodal histogram have disjoint objects

and there gray levels are clearly distinct from the
background.
Each peak of the multimodal histogram is distinctly
separate from the other.
For segmenting such images the valleys between the
peaks are chosen as the threshold values.
The total number of thresholds required for segmentation
are N − 1, where N is the number of peaks in the
histogram.
Each pixel has to be categorized into a particular region
depending upon the threshold region it belongs to.
51/118 Subrajeet Mohapatra Image Segmentation
 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Multimodal Thresholding
Images with multimodal histogram requires multiple
thresholds for partitioning an image into different
segments.
Thresholding for a Multimodal Histogram can be
mathematically represented as

f(x, y) > T2 ⇒ (x, y) ∈ R2

f(x, y) ≤ T2 ⇒ (x, y) ∈ R1

f(x, y) < T1 ⇒ (x, y) ∈ Background

There may be image histograms with more than three
peaks.
52/118 Subrajeet Mohapatra Image Segmentation
 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Thresholding Selection

Selection of proper threshold is essential for every

threshold based segmentation technique.
This threshold value of the thresholding operation can be
considered as an operation that invokes testing against a
function T where this function T is of the form

T = T[(x, y), p(x, y), f(x, y)]

where,
(x,y) ⇒ Pixel Location
p(x,y) ⇒ Local property in a neighborhood centered at
(x , y ).
f(x,y) ⇒ Pixel intensity at (x , y ).
53/118 Subrajeet Mohapatra Image Segmentation
 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Thresholding Selection

So in general this threshold T can be a function of pixel

Location, local property within the neighborhood and pixel
intensity value.
Threshold T can be a function of any combination of the
above three terms.
Depending on this combination the threshold T can be
classified as
Global Threshold
Local Threshold
Adaptive Threshold

54/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Thresholding Selection

If the threshold T is only a function of pixel intensity value

f (x , y ). Then T is termed as global threshold.

T [f(x, y)] ⇒ GlobalThreshold

Threshold T is termed as local threshold if T is a function

of pixel intensity value and local property.

T[f(x, y), p(x, y)] ⇒ LocalThreshold

If the threshold is a function of all the three properties then

T is termed as adaptive threshold.

T[(x, y), f(x, y), p(x, y)] ⇒ AdaptiveThreshold

55/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Thresholded Image

Using this threshold T we want to get a thresholded binary

image g (x , y ) defined as

1 if f (x , y ) ≥ T ⇒ Object
g (x , y ) =
0 if f (x , y ) < T ⇒ Background

This threshold T can be global, local or adaptive.

56/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Threshold Estimation

The threshold T can be estimated by

Histogram based thresholding (Visual Inspection)
Automatic thresholding
For completely unsupervised machine vision applications
visual inspection of histogram for threshold estimation is
impossible.
Thus threshold has to be estimated automatically from the
given image for unsupervised image segmentation.

57/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Histogram Based Threshold Estimation

Considering a image with bimodal histogram.

By visually inspecting the histogram we can select a

threshold from the deep valley region.
Using this threshold we can obtain a segmented image.
58/118 Subrajeet Mohapatra Image Segmentation
 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Histogram Based Thresholding Results

3500

3000

2500

2000

1500

1000

500

0 50 100 150 200 250

(a) Original Image (b) Histogram (c) Segmented

59/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Automatic Thresholding

Threshold estimation by visual inspection is unlikely in

machine vision applications.
So a automatic process has to be followed for threshold
estimation.
This is achieved using an iterative process.

60/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Automatic Thresholding
Algorithm
1 Select an initial value of threshold T .

61/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Automatic Thresholding
Algorithm
1 Select an initial value of threshold T .

2 Use T to segment the image into two groups G 1 &G2

61/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Automatic Thresholding
Algorithm
1 Select an initial value of threshold T .

2 Use T to segment the image into two groups G 1 &G2

3 Compute the mean μ 1 and μ2 for each group of pixels.

61/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Automatic Thresholding
Algorithm
1 Select an initial value of threshold T .

2 Use T to segment the image into two groups G 1 &G2

3 Compute the mean μ 1 and μ2 for each group of pixels.

4 Compute the new updated threshold T using the relation

61/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Automatic Thresholding
Algorithm
1 Select an initial value of threshold T .

2 Use T to segment the image into two groups G 1 &G2

3 Compute the mean μ 1 and μ2 for each group of pixels.

4 Compute the new updated threshold T using the relation

μ1 + μ2
T=
2
5 Repeat step 2-4 until

Ti − Ti +1 ≤ Th
61/118 Subrajeet Mohapatra Image Segmentation
 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Global Threshold
3000

2500

2000

1500

1000

500

0 50 100 150 200 250

62/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Global Threshold

The threshold which have been selected does not consider

pixel location and local neighborhood property.
Threshold considered here is global as we use one
particular threshold for segmenting the entire image.
So we call it as global thresholding operation.
Global thresholding is only applicable for images with
uniform illumination.

63/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Dealing with Illumination

64/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Illumination Effects on Thresholding

65/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Thresholding for Poor Illumination Images

Global thresholding fails for images with poor illumination.

Valley is not well defined for such images in the image
histogram.
One approach for dealing with poor illumination is
Subdivide the image into number of smaller sub images.
Assuming that illumination will be roughly uniform for each
of the sub images.
So for each sub image we can have a threshold and
segment each sub image.
Combination of all the sub images will give the final
segmented image.
Since the threshold selection here is position dependent
so the threshold here is adaptive threshold.
66/118 Subrajeet Mohapatra Image Segmentation
 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Thresholding for Poor Illumination Images

67/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Optimal Thresholding

Thresholding methods which consider accuracy of the

thresholding or try to minimize threshold error.
Statistical property of the image is used to minimize the
mean error during thresholding.
The histogram of an image is approximated using a
weighted sum of two or more probability densities with
normal distribution.
The threshold is set as the closest gray level
corresponding to the minimum probability between the
maxima of two or more normal distributions.
Such thresholding results with minimum error
segmentation or optimal thresholding.
68/118 Subrajeet Mohapatra Image Segmentation
 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Optimal Thresholding

Assuming there are two intensity regions in the image i.e.

object and background.
If we assume that intensity variables can be modeled as
random variables.
Say this random variable be represented as z
The normalized histogram of this image can be viewed as
a probability density function p (z ) of this random variable
z.
As per our assumption the image contains two regions we
will have a bimodal histogram.

69/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Optimal Thresholding

70/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Optimal Thresholding

The histogram is assumed to be a probability density

function of the intensity variable z .
So the bimodal histogram is a combination of two
probability density functions (PDF) i.e. p1 (z ) and p2 (z ).
p1 (z ) is the probability density function of the intensities of
the pixels belonging to background.
p2 (z ) is the probability density function of the intensities of
the pixels belonging to object.

71/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Optimal Thresholding
Overall histogram p (z ) can be represented by the
combination of p1 (z ) and p2 (z ).
p (z ) can be mathematically denoted as,
p (z ) = P1 p1 (z ) + P2 p2 (z )
where,
P1 indicates the probability that a pixel will belong to the
background.
P2 indicates the probability that a pixel will belong to the
object.
Sum of both the probabilities will be unity.
P1 + P2 = 1
72/118 Subrajeet Mohapatra Image Segmentation
 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Optimal Thresholding

The objective is to determine the threshold T which will

minimize average segmentation error.
Since the over all probability is modeled as combination of
two different probabilities.

73/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Optimal Thresholding

Considering a threshold T for image segmentation

f (x , y ) > T ⇒ Object
Pixels beyond T with intensity f (x , y ) also have a finite
probability that it may belong to the background.

74/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Optimal Thresholding

Thus while selecting this threshold we incorporate some

error.
This error can be like
The error probability that a object pixel will be classified as
an background pixel and can be defined as
 T
E1 (T ) = p2 (z )dz
−∞

The error probability that a background pixel may be

classified as an object and can be formulated as
 ∞
E2 (T ) = p1 (z )dz
T

75/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Optimal Thresholding

The overall error probability is given as

E (T ) = P2 E1 (T ) + P1 E2 (T )
For minimizing this error we will take derivative of E (t ) and
equate to zero.

∂E (T )
=0
∂T
Under this condition what ever T we get will give us
minimum error.
P1 p1 (T ) = P2 p2 (T )

76/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Optimal Thresholding

Solution of this equation gives the value of T , provided we

know the PDF of p 1 (T ) and p2 (T ).
Assuming Gaussian PDF and using the above equation we
get the solution of T as

(μ1 + μ2 ) σ2 P2
T= + ln( )
2 μ1 − μ2 P1

Using this threshold we can have minimum number of

background pixels classified as object pixels and minimum
number of object pixels classified as background pixels.
The threshold here is optimal because this gives minimal
average segmentation error.
77/118 Subrajeet Mohapatra Image Segmentation
 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Local Thresholding
Threshold selection is easier if the image histogram is:
Bimodal and modes are tall, narrow and separated by a
deep valley.
If the modes are symmetric.

In such type of histogram threshold can be obtained from

the valley region and the image can be segmented.
78/118 Subrajeet Mohapatra Image Segmentation
 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Local Thresholding
Considering an image where a very small number of pixels
represent a object and large number of pixels represent
the back ground.

79/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Local Thresholding

For such image the contribution to the histogram by the

object pixels is almost negligible as the number of pixels
representing object region is very less in comparison to
background region.
Bimodal nature of the histogram is not very well defined
and it is rather a unimodal histogram with major
contribution from background pixels.
Determination of threshold is an issue as the valley is not
well defined.

80/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Local Thresholding

Instead of considering all the pixels for generating the

histogram, pixels on the boundary and near the boundary
can only be considered.
The objective is to identify the pixels in a narrow strip
around the boundary. and this pixels around the boundary
will be considered for histogram generation.
Considered these pixels for histogram generation the
number of pixels contributing to the object region and the
background region will be approximately same.

81/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Local Thresholding

Advantages
Thus the histogram will be symmetric.
Histogram will be independent of relative size of object and
background region.
The probability of a pixel belonging to object and the
probability of a pixel belonging to background within the
narrow strip is almost same.
Thresholding such an histogram will be easier.

82/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Local Thresholding

Determining the pixels on the boundary or around the

boundary is essential for the above segmentation
approach.
But the boundary between object and background is
unknown so the above approach is not applicable.
As a solution to the above is use of image gradient and
laplacian for obtaining the boundary pixels and pixels near
the boundary.

83/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Local Thresholding

84/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Local Thresholding

The gradient operator output is used to determine the

position of the edge points.
The pixels which are lying on the boundary or near the
boundary the gradient magnitude will be high.
The output of the laplacian operator is used to determine
whether a pixel is lying on the darker side of the edge point
or lighter side of the edge point.
The laplacian output is negative if a pixel lies on the bright
side of the edge and the laplacian will be positive if a pixel
lies on the dark side of the edge.

85/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Local Thresholding
Using f (x , y ), |∇f |, |∇2 f | an intermediate segmented image
can be obtained

⎧
⎪
⎪ 0 if ∇f < T
⎪
⎨
s (x , y ) = ⎪
⎪ + if ∇f ≥ T and∇2f ≥ 0
⎪
⎩ − if ∇f ≥ T and∇2f < 0

Each value of s (x , y ) provides certain amount of

information
⎧
⎪
⎪ 0 → Pixel does not belong to the boundary
⎪
⎨
s (x , y ) = ⎪
⎪ + → Pixel belong to the object region
⎪
⎩ − → Pixel belong to the boundary region

86/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Local Thresholding

The final segmented image is obtained from the

intermediate image consisting of 0, +, −.
Transition from one region to other can be detected using
this symbols.
−, + → Transition from background to object.
+, − → Transition from object to background.
Final segmented binary image is obtained after scanning
the entire image and assigning the pixels of the
background region as 1 and to the object as 0.
The thresholding here is local because we use gradient
and laplacian of the image to obtain the threshold which is
a local property.

87/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Local Thresholding

88/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Region Based Segmentation

Homogeneity property of the image regions are used as

the segmentation criterion.
The concept is to maximize homogeneity in each
segmented regions.
Homogeneity criteria can be based on gray level, color,
texture.
Selection of proper homogeneity criteria is most important
and influence segmentation performance.
Region based image segmentation can be classified as
Region Growing
Region Splitting and Merging

89/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Region Definition

Considering all the pixels in the image as a set of pixels

and denoting it as R .
The segmentation operation partitions the set of pixels R
to number of subregions say R 1 , R2 , . . . Rn .

90/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Region Definition

During partitioning certain properties are followed i.e.

n

i =1Ri = R ,
Ri Rj = ∅ for i  j,
P (Ri ) = TRUE for i=1,2,. . . , n
P (Ri Rj ) = FALSE for i  j,
Where P (Ri ) is a predicate defined in terms of feature
values over region Ri .
All the pixels belonging to a particular region must be
similar and pixels belonging to two different region are
dissimilar.
Regions must be connected, disjoint and homogeneous in
nature.

91/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Region Growing
It is a procedure which groups the pixels or subregions into
larger region based on a defined predicate.
After selecting a set of points (seed) in the image, the
operation tries to grow the region staring from the seed
point incorporating all the points similar to the seed point.
Two points can be said similar if there intensity values are
very close.

92/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Region Growing Process

A seed pixel is selected from the image and is assigned a

label.
Each of the neighbor pixels are labeled recursively using a
similarity measure or a homogeneity property.
When no more pixels can be labeled with the same label,
the first region is found.
Then another seed pixel is selected out of the yet to label
pixels and then same labeling process is followed.
The entire process is repeated until no more pixels remain
unlabeled.
The concepts of 4–connected or 8–connected pixel
windows is usually considered.
93/118 Subrajeet Mohapatra Image Segmentation
 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Homogeneity Measure

Homogeneity property is to be satisfied by the gray levels

of pixels lying within a region.
The gray level variance of the pixels can be a metric for
homogeneity measurement and can be defined as

1  2
MH (R ) = f (x , y ) − f̄ (x , y ) ≤ T
|R |
(x ,y )∈R

where, |R | represents the size of region R in number of

pixels and T is the threshold. f̄ is the average gray value
within R .

94/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Homogeneity Measure

Another homogeneity property for a small range of gray

levels of pixels in a region can be defined as

max − min ≤ T
g(r ,c )∈R g(r ,c )∈R

where, |R | represents the size of region R in number of

pixels and T is the threshold.

95/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Region Growing Results

96/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Demerits of Region Growing

Requires large execution time.

Selection of suitable property to be satisfied.
Selection of seed points.

97/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Region Splitting

Homogeneity property is tested over a rectangular region.

If the features do not satisfy the property the image region
is divided into four equal quadrants.
If the property is satisfied the region is left as it is.
The steps are repeated until all the regions satisfy the
property.
Use the quad tree data structure.

98/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Region Splitting Example

99/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Quad Tree

100/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Region Merging

It is exactly opposite to the splitting process.

Each pixel is considered as a distinct region.
At each level of merging homogeneity property is checked
for four adjacent regions.
If the condition is satisfied then the regions are merged
into a single homogeneous region else it is left as it is.
Above steps are repeated until no more regions are left for
merging.
A quad tree can be formed with the image as the root node
and each leaf node represents a rectangular
homogeneous region.

101/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Region Merging Example

102/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Region Splitting and Merging

Region splitting and merging operation can be performed

simultaneously within a same algorithm.
This algorithm is a hybrid of the split and merge process
and starts somewhere in the middle of the quad tree.
Starting with a rectangular region of size m × m. pixels.
Each region homogeneity is tested.
If the test fails the region is split into four quadrants of size
2 × 2.
m m

If the region satisfies the homogeneity then merging

process is followed to form a region of size (2m) × (2m).
The process stops when no more split or merge is
possible.
103/118 Subrajeet Mohapatra Image Segmentation
 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Clustering Based Segmentation

Clustering based image segmentation is the process of

assigning a label to every pixel in an image such that pixels
with the same label share certain visual characteristics.
Cluster oriented segmentation uses the multidimensional
data to partition the image pixels into clusters.
Cluster-oriented techniques may be more appropriate than
histogram-oriented ones in segmenting images, where
each pixel has several attributes and is represented by a
vector.

104/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Clustering Based Segmentation

In cost minimization clustering techniques, each clustering

configuration is assigned a value or cost to measure its
goodness.
An appropriate cost function measures the goodness of a
cluster.
The cost for a cluster configuration is its squared error, i.e.,
the sum of squared Euclidean distances of each point to its
cluster center.
Clustering methods which can be applied to image
segmentation problem are:
K-means clustering
Fuzzy C-means clustering (FCM)

105/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

K- means clustering
K-Means algorithm is an unsupervised clustering algorithm
that classifies the input data points into multiple classes
based on their inherent distance from each other.
Algorithm:
1 Assign initial means vi (centroid)
2 Assign each data pattern (point) Xk to the cluster Ui for the
closest mean.
3 New updated centroid


X k ∈ Ui Xk
vi = ,
| Ci |
4 Repeat step 2 and 3 until the updated centroid become
stable.
106/118 Subrajeet Mohapatra Image Segmentation
 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Fuzzy c-means clustering

FCM is a soft version of K-means, where each data point
has a fuzzy degree of belonging to each cluster.
Algorithm:
1 Assign initial means vi , Choose values for fuzzifier m and
threshold . Set the iteration counter t = 1.
2 Repeat Steps 3 and 4, by incrementing t , until
|μik (t ) − μik (t − 1)| > tmax .
3 Compute μik for c clusters and N data patterns.
1
μik =   m2−1
c dik
j =1 djk

4 Update means using

N
k =1 (μik )m Xk
vi =  N
,
k =1 (μik )
m
107/118 Subrajeet Mohapatra Image Segmentation
 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Scatter Plot (K–means Clustering)

108/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

K–Means Clustering Segmentation Results

(a) Blood Image

(b) Region 1 (c) Region 2 (d) Region 3 (e) Region 4

109/118 Figure:Image Segmentation

Subrajeet Mohapatra
 Introduction
Segmentation Techniques
Discontinuity Based Segmentation
Performance Evaluation
Similarity Based Segmentation
Color Image Segmentation
Conclusion

Fuzzy–C Means Clustering Segmentation Results

(a) Blood Image

(b) Region 1 (c) Region 2 (d) Region 3 (e) Region 4

110/118 Figure:Image Segmentation

Subrajeet Mohapatra
 Introduction
Segmentation Techniques
Performance Evaluation
Color Image Segmentation
Conclusion

Evaluation of Image Segmentation Algorithms

Image segmentation and its performance evaluation are

very difficult problems in computer vision.
The criteria of a good segmentation are often application
dependent and hard to explicitly define.
Some researchers feel it is impossible .

111/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Performance Evaluation
Color Image Segmentation
Conclusion

Evaluation of Image Segmentation Algorithms

112/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Performance Evaluation
Color Image Segmentation
Conclusion

Subjective Evaluation

Evaluation methods that require user assistance are

known as subjective evaluation or supervised evaluation.
Evaluation is performed by comparing the resulting
segmented image against a manually-segmented
reference image referred as gold standard.

113/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Performance Evaluation
Color Image Segmentation
Conclusion

Subjective Evaluation

(a) Cell 1 (b) Ground Truth (c) Cell 2 (d) Ground Truth

Figure:

Total number of misclassified pixels

ε=
Total number of pixels in a region

114/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Performance Evaluation
Color Image Segmentation
Conclusion

Objective Evaluation

Unsupervised evaluation does not require comparison with

a manually-segmented reference image, it is quantitative
and objective.
Creating a reference image is tedious and
time-consuming, and for many real time applications, it is
hard or maybe even impossible.
Objective evaluation is suitable for on line image
segmentation in real-time systems.

115/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Performance Evaluation
Color Image Segmentation
Conclusion

Color Image Segmentation

Color based segmentation techniques are broadly

classified as:
Feature space based techniques
Color based clustering
Histogram
Image domain based techniques
Split and merge
Region growing
Physics based techniques
Dichromatic reflection model
Unichromatic reflection model

116/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Performance Evaluation
Color Image Segmentation
Conclusion

Conclusion

Image segmentation is an essential preliminary step in

most automatic pictorial pattern recognition and scene
analysis applications.
There is no universal algorithm or segmentation technique
for all kind of images.
Specific methods have to be developed for segmenting
particular kind of images.
None of the segmentation evaluation measure are perfect.

117/118 Subrajeet Mohapatra Image Segmentation

 Introduction
Segmentation Techniques
Performance Evaluation
Color Image Segmentation
Conclusion

Important References I

1 Anil K. Jain.
Fundamentals of Digital Image Processing.
Prentice-Hall of India, 1989.

2 Rafael Gonzalez and Richard Woods.

Digital Image Processing.
Addison Wesley, 1992.

118/118 Subrajeet Mohapatra Image Segmentation