UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Course Name : Digital Image Processing
Click to edit Master subtitle style
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Chapter 10: Image Segmentation
Image Segmentation
Segmentation attempts to partition the pixels of an
image into groups that strongly correlate with the
objects in an image
Typically the first step in any automated computer
vision application
2
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Image Segmentation
• Segmentation algorithms generally are based on one
of two basis properties of intensity values
• Discontinuity: to partition an image based on
abrupt changes in intensity (such as edges)
• Similarity: to partition an image into regions that
are similar according to a set of predefined
criteria.
3
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Image Segmentation
Image Segmentation
4
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Image Segmentation
Image Segmentation
5
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Image Segmentation
Detection of discontinuities:
There are three basic types of gray-level
discontinuities:
points , lines , edges
the common way is to run a mask through
the image
6
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Point Detection:
• Note that the mark is the same as the mask of
Laplacian Operation (in chapter 3)
• The only differences that are considered of
interest are those large enough (as determined
by T) to be considered isolated points.
|R| >T
7
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Point Detection:
8
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Line Detection
R1 R2 R3 R4
• Horizontal mask will result with max response when a line passed
through the middle row of the mask with a constant background.
• the similar idea is used with other masks.
• note: the preferred direction of each mask is weighted with
a larger coefficient (i.e.,2) than other possible directions.
9
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Line Detection
• Apply every masks on the image
• let R1, R2, R3, R4 denotes the response of the
horizontal, +45 degree, vertical and -45 degree
masks, respectively.
• if, at a certain point in the image
|Ri| > |Rj|, for all j≠i,
• that point is said to be more likely associated
with a line in the direction of mask i.
10
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Line Detection
• Alternatively, if we are interested in detecting all lines in
an image in the direction defined by a given mask, we
simply run the mask through the image and threshold
the absolute value of the result.
• The points that are left are the strongest responses,
which, for lines one pixel thick, correspond closest to
the direction defined by the mask.
11
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Line Detection
12
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Edge Detection Approach
Segmentation by finding pixels on a region
boundary.
Edges found by looking at neighboring pixels.
Region boundary formed by measuring gray
value differences between neighboring pixels
13
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Edge Detection
• an edge is a set of connected pixels that
lie on the boundary between two regions.
• an edge is a “local” concept whereas a
region boundary, owing to the way it is
defined, is a more global idea.
14
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Edge Detection
15
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Edge Detection
16
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Edge Detection
17
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Edge Detection
Detection of discontinuities: Image Derivatives
18
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Edge Detection
• First column: images and gray- level profiles
of a ramp edge corrupted by random
Gaussian noise of mean 0 and = 0.0, 0.1,
1.0 and 10.0, respectively.
• Second column: first-derivative
images and gray-level profiles.
• Third column : second- derivative images and
gray- level profiles.
19
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Edge Detection
Gradient Operator
f
Gx x
f f
G y
y
f G G 2
x y
2 1/ 2
for 3 3 mask
Gx (z7 z8 z9 ) (z1 z2 z3 )
Gy (z3 z6 z9 ) (z1 z4 z7 )
20
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Edge Detection
Prewitt and Sobel Operators
21
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Edge Detection
22
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Edge Detection
23
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Edge Detection
24
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Edge Detection
25
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Edge Detection
The Laplacian
26
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Edge Detection
27
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Edge Detection
The Laplacian of Gaussian (LoG)
28
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Edge Detection
The Laplacian of Gaussian (LoG)
29
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
The Hough Transform
30
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
The Hough Transform
Global processing: The Hough Transform
31
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
The Hough Transform
Global processing: The Hough Transform
32
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
The Hough Transform
Global processing: The Hough Transform
33
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
What is a Region?
Basic definition :- A group of connected
pixels with similar properties.
Important in interpreting an image because
they may correspond to objects in a scene.
For that an image must be partitioned into
regions that correspond to objects or parts of
an object.
34
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Region-Based vs. Edge-Based
Region-Based Edge-Based
Closed boundaries Boundaries formed
not necessarily
closed
Multi-spectral No significant
images improve improvement for
segmentation multi-spectral images
Computation based Computation based
on similarity on difference 35
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Image Thresholding
•What is thresholding?
•Simple thresholding
•Adaptive thresholding
36
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Thresholding – A Key Aspect
Most algorithms involve establishing a
threshold level of certain parameter.
Correct thresholding leads to better
segmentation.
Using samples of image intensity available,
appropriate threshold should be set
automatically in a robust algorithm i.e. no
hard-wiring of gray values
37
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Automatic Thresholding
Use of one or more of the following:-
1. Intensity characteristics of objects
2. Sizes of objects
3. Fractions of image occupied by objects
4. Number of different types of objects
Size and probability of occurrence – most popular
Intensity distributions estimate by histogram
computation.
38
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Automatic Thresholding Methods
Some automatic thresholding schemes:
1. P-tile method
2. Iterative threshold selection
3. Adaptive thresholding
39
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Thresholding Methods
P-tile Method:- If object
occupies P% of image pixels
then set a threshold T such
that P% of pixels have
intensity below T.
Iterative Thresholding:-
Successively refines an
T 12
approx. threshold to get a 1
new value which partitions 2
the image better. 40
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
P-Tile Thresholding
• Thresholding is usually the first
step in any segmentation approach
• Single value thresholding can be
given mathematically as follows:
1 if f (x, y) T
g(x, y)
0 if f (x, y) T 41
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
P-Tile Thresholding
• Basic global thresholding:
• Based on the histogram of an image Partition
the image histogram using a single global
threshold
42
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
P-Tile Thresholding
• Basic global thresholding:
• The success of this technique very strongly
depends on how well the histogram can be
partitioned
43
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Iterative P-Tile Thresholding
• The Basic global thresholding:
1. Select an initial estimate for T (typically the
average grey level in the image)
2. Segment the image using T to produce two groups
of pixels: G1 consisting of pixels with grey levels >T
and G2 consisting pixels with grey levels ≤ T
3. Compute the average grey levels of pixels in G1 to
give μ1 and G2 to give μ2
44
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Iterative P-Tile Thresholding
• The Basic global thresholding:
4. Compute a new threshold value:
1 2
T
2
5. Repeat steps 2 – 4 until the difference in T in
successive iterations is less than a predefined limit
T∞
This algorithm works very well for finding thresholds when
the histogram is suitable. 45
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
P-Tile Thresholding
46
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
P-Tile Thresholding
47
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
P-Tile Thresholding
• Limitation of P-Tile thresholding:
48
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
P-Tile Thresholding
• Limitation of P-Tile thresholding:
49
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
P-Tile Thresholding
• Limitation of P-Tile thresholding:
50
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Adaptive Thresholding
Adaptive Thresholding is used in scenes with
uneven illumination where same threshold
value not usable throughout complete image.
In such case, look at small regions in the
image and obtain thresholds for individual
sub-images. Final segmentation is the union
of the regions of sub-images.
51
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Adaptive Thresholding
Thresholding – Basic Adaptive Thresholding
52
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Adaptive Thresholding
Thresholding – Basic Adaptive Thresholding
53
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Adaptive Thresholding
Thresholding – Basic Adaptive Thresholding
54
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Adaptive Thresholding
Thresholding – Basic Adaptive Thresholding
55
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Adaptive Thresholding
Thresholding – Basic Adaptive Thresholding
56
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Summary
Segmentation is the most essential step
in most scene analysis and automatic
pictorial pattern recognition problems.
Choice of the technique depends on the
peculiar characteristics of individual
problem in hand.
57
UNIVERSITY OF ENGINEERING & MANAGEMENT, KOLKATA
Thank You
58
