Module 4

IMAGE SEGMENTATION
4.1 Point, Line, and Edge Detection: Detection of Isolated Points, Line
detection, edge models, Canny's edge detection algorithm , Edge linking :
Local processing and boundary detection using regional processing (polygonal
fitting)
4.2 Thresholding : Foundation, Role of illumination and reflectance, Basic
global thresholding
4.3 Region Based segmentation: Region Growing, Region Splitting and merging
Introduction to image segmentation

• purpose --is to partition an image into meaningful regions

with respect to a particular application.

• Image segmentation divides an image into regions that

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

• The segmentation is based on measurements taken from

the image and might be grey level, colour, texture, depth
or motion
2
 Introduction to image segmentation
⚫ The goal is usually to find individual objects in an image.
⚫ For the most part there are fundamentally two kinds of
approaches to segmentation:

⚫ 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.
 Applications of image segmentation
• Usually image segmentation is an initial and vital step in a
series of processes aimed at overall image understanding

• Applications of image segmentation include

• Identifying objects in a scene for object-based measurements such
as size and shape
• Identifying objects in a moving scene for object-based video
compression (MPEG4)
• Identifying objects which are at different distances from a sensor
using depth measurements from a laser range finder enabling path
planning for a mobile robots
Why segmentation is difficult ?

It can be difficult for many reasons:

•Non- uniform illumination
•No control of the environment
•Inadequate model of the object of interest
•Noise
 Classification of the Segmentation
techniques
Image segmentation

Discontinuity Similarity

e.g. e.g.
- Point Detection - Thresholding

- Line Detection - Region Growing

- Edge Detection - Region splitting &
merging
Segmentation Examples
• Segmentation based on greyscale
• Very simple ‘model’ of greyscale leads to inaccuracies in
object labelling

9
• Example 2
• Segmentation based on texture
• Enables object surfaces with varying patterns of
grey to be segmented

10
• Example 3
• Segmentation based on motion
• The main difficulty of motion segmentation is that
an intermediate step is required to (either implicitly
or explicitly) estimate an optical flow field
• The segmentation must be based on this estimate
and not, in general, the true flow

11
Motion based image segmentation

12
• Example 3
• Segmentation based on depth
• This example shows a range image, obtained with
a laser range finder
• A segmentation based on the range (the object
distance from the sensor) is useful in guiding
mobile robots

13
 Range image
Original
image

Segmented
image

14
Background First-order derivatives
generally produces thicker
edges in an image.
Second order derivatives
have a stronger response to
fine details such as thin
lines, isolated points and
noise
second order- produce a
double edge response at
ramp and step transitions in
intensity.
The sign of .the 2nd order
derivative can be used to
determine whether
transition is from light to
dark or vice versa
 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.
Detection of Discontinuities
Isolated Point Detection
Point Detection (cont…)
T equal to 90% of the highest absolute pixel of
the image in middle figure

X-ray image of Result of point Result of

a turbine blade detection thresholding
 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°).
Line Detection
Line Detection
Detection of Discontinuities
Edge Detection
Detection of Discontinuities
Edge Detection
Detection of Discontinuities
Edge Detection
Detection of Discontinuities
Edge Detection
 Detection of Discontinuities
Gradient Operators
⚫ The image Gradient and its properties
⚫ The total of choice for finding edge strenth and direction at location (x,y) of an
image, f, is the gradient, denoted by ∇f, and defined as the vector
First-order derivatives:
⚫ The gradient of an image f(x,y) at location (x,y) is defined as the vector:

⚫ The magnitude of this vector:

⚫ The direction of this vector:

 Detection of Discontinuities
Gradient Operators

Roberts cross-gradient operators

Prewitt operators

Sobel operators
 Detection of Discontinuities
Gradient Operators

Prewitt masks for

detecting diagonal edges

Sobel masks for

detecting diagonal edges
 Detection of Discontinuities
Gradient Operators: Example
 Detection of Discontinuities
Gradient Operators: Example
 Detection of Discontinuities
Gradient Operators: Example
 Detection of Discontinuities
Gradient Operators

• Second-order derivatives: (The Laplacian)

• The Laplacian of an 2D function f(x,y) is defined as

• Two forms in practice:

More Advanced Techniques for Edge Detection
Marr-Hildreth edge detector
Marr and Hildreth argued that
(1) intensity changes are not independent of image scale
and so their detection requires the use of operators
different sizes
(2) that a sudden intensity change will give rise to a peak
or trough in the first derivative or, equivalently, to zero
crossing in the second derivative.
 Edge detection should have following silent
features

• 1) it should be a differential operator capable of computing digital

approximation of the first or second derivative at every point in
image.

• 2) it should be capable of being “tuned” to act at any desired scale

so that large operators can be used to detect blurry edges and small
operators to detect sharply focused fine details
⚫ Marr-Hildreth edge detector
⚫ Marr and Hildreth argued that the most satisfactory operator
fulfilling these conditions is the filter ∇2G where, ∇2 is the
Laplacian operator, and G is the 2-D Gaussian function
Marr-Hildreth edge detector
 Detection of Discontinuities
Gradient Operators: Example

Sobel gradient

Gaussian smooth function Laplacian mask

 Detection of Discontinuities
Gradient Operators: Example
Marr and Hildreth Edge Operator
other approximation:
Marr and Hildreth Edge Operator

X
Marr and Hildreth Edge Operator

Zero Crossings Edge Image

Detection

Zero Crossings
 Quality of an Edge Detector
• Robustness to Noise
• Localization
• Too Many/Too less Responses True Edge

Poor robustness to noise Poor localization Too many responses

 Canny Edge Detector
• Criterion 1: Good Detection: The optimal detector must
minimize the probability of false positives as well as false
negatives.

• Criterion 2: Good Localization: The edges detected must

be as close as possible to the true edges.

• Single Response Constraint: The detector must return one

point only for each edge point.
Canny Edge Detector
• Convolution with derivative of Gaussian
• Non-maximum Suppression
• Hysteresis Thresholding
 Edge Linking and Boundary Detection
Local Processing
• Two properties of edge points are useful for edge linking:
• the strength (or magnitude) of the detected edge points
• their directions (determined from gradient directions)
• This is usually done in local neighborhoods.
• Adjacent edge points with similar magnitude and direction are
linked.
• For example, an edge pixel with coordinates (x0,y0) in a predefined
neighborhood of (x,y) is similar to the pixel at (x,y) if
 Edge Linking and Boundary Detection
Local Processing: Example

In this example,
we can find the
license plate
candidate after
edge linking
process.
 Edge Linking the Hough Transform
• Hough transform: a way of finding edge points in an image that lie
along a straight line.
• Example: xy-plane v.s. ab-plane (parameter space)
 Edge Linking and Boundary Detection
Global Processing via the Hough Transform

• The Hough transform consists of

finding all pairs of values of θ and
ρ which satisfy the equations that
pass through (x,y).
• These are accumulated in what is
basically a 2-dimensional
histogram.
• When plotted these pairs of θ and
ρ will look like a sine wave. The
process is repeated for all
appropriate (x,y) locations.
Edge Linking and Boundary Detection
Hough Transform Example

The intersection of the

curves corresponding to
points 1,3,5

2,3,4

1,4
Edge Linking and Boundary Detection
Hough Transform Example
 How can we divide an image into uniform regions
?

Segmentation techniques can be classified as either

contextual or non-contextual .
Non-contextual techniques ignore the relationships
that exist between features in an image; pixels are
simply grouped together on the basis of some global
attribute, such as grey level.

Contextual techniques, additionally exploit the

relationships between image features. Thus, a
contextual technique might group together pixels that
have similar grey levels and are close to one another .
segmentation methods

• some categorization is necessary to present the methods

• Edge based segmentation.

• Threshold based segmentation.
• Region based segmentation
• Clustering techniques.
• Matching
Segmentation based on
Similarity
 Thresholding

The input to a thresholding operation is typically a grayscale or

color image. In the simplest implementation, the output is a
binary image representing the segmentation. Black pixels
correspond to background and white pixels correspond to
foreground (or vice versa).
 Thresholding
Thresholding can be viewed as an operation that
involves tests against a function T of the form:

where p(x,y) denotes

some local property of this
point.
⚫ When T depends only on f(x,y) 🡪
global threshold

⚫ When T depends on both f(x,y) and p(x,y) 🡪

local threshold

⚫ When T depends on x and y (in addition) 🡪

dynamic threshold
Why Thresholding?
It has a center position in applications of image segmentation.
1) Its intuitive properties.
2) Simplicity of implementation.
3) Computational speed

Foundation:
 Thresholding
• In A: light objects in dark background
• To extract the objects
• Select a T that separates the objects from the
background
• i.e. any (x,y) for which f(x,y)>T is an object point.

⚫ A thresholded image:
(objects)

(background)
• T- constant----- global thresholding
• T- variable ----- variable thresholding
 Thresholding

(multilevel thresholding)
⚫ So: (x,y) belongs:
⚫ To one object class if T1<f(x,y)≤T2
⚫ To the other if f(x,y)>T2
⚫ To the background if f(x,y)≤T1
A) classic bi-modal intensity distribution. -- successfully segmented
using a single threshold T1.
B) slightly more complicated- the central peak represents the
objects we are interested in and so threshold segmentation requires
two thresholds: T1 and T2.
C) the two peaks of a bi-modal distribution have run together and so
it is almost certainly not possible to successfully segment this image
using a single global threshold
 Thresholding
⚫ Success of intensity thresholding is directly related to width
and depth of valley separating the histogram modes

⚫ Key factor affecting the properties of valley(s)

⚫ 1) separation between peaks

⚫ 2)noise content in the image
⚫ 3)Relative size of object and background
⚫ 4) the uniformity of illumination source
⚫ 5) the uniformity of reflectance properties of the image
Role of noise in thresholding
 Role of Illumination and reflectance

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

⚫ A non-uniform illumination destroys the reflectance

patterns that can be exploited by thresholding (e.g. for
object extraction).
⚫ Solution:

⚫ Project the illumination pattern onto a constant, white

reflective surface.

⚫ This yields an image g(x,y) = ki(x,y), where

⚫ k is a constant depending on the surface and
⚫ i(x,y) is the illumination pattern.
 Role of Illumination and reflectance
• Solution (cont.):

• Then, for any image f(x,y) = i(x,y) r(x,y), divide by g(x,y). This
yields:

So:
if r(x,y) can be segmented by using a single threshold
T, then h(x,y) can also be segmented by using a single
threshold of value T/k.
 Illumination and reflection role in thresholding

easily use global

thresholding
difficult to segment
object and
Background
are separated
The histogram for image is

Due to the severe illumination gradient across the scene, the peaks
corresponding to foreground and background have run together and
so simple thresholding does not give good results. Following images
show the resulting bad segmentations for single threshold values of
80 and 120 respectively (reasonable results can be achieved by using
adaptive thresholding on this image).
 Basic
An algorithm usedGlobal
to obtainThresholding
T
automatically for global thresholding

1. Select an initial estimate for T.

2. Segment the image using T. This well produce two groups of
pixels: G1 consisting of all pixels with gray level values>T and
G2 consisting 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 = ½[μ1 + μ2 ]
5. Repeat step 2 through 4 until the difference in T in successive
iterations is smaller than a predefined parameter To.
Basic Global Thresholding
 Region-Based Segmentation

• Edges and thresholds sometimes do not give good results

for 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

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.
 Region-based segmentation
Region Growing
⚫ Algorithm:
a. Choose a random pixels
b. Use 8-connected and threshold to determine
c. Repeat a and b until almost points are classified.

92
• Consider a seed pixel of 2 in the given image and a threshold value of 3, if a pixel has a
value greater than 3 then it will be considered inside the seed pixel region. Otherwise, it
will be considered in another region. Hence 2 regions are formed in the following image
based on a threshold value of 3.
 Region-Based Segmentation
Region Splitting and Merging
• Region splitting is the opposite of region growing.
• First there is a large region (possible the entire image).
• Then a predicate (measurement) is used to determine if
the region is uniform.
• If not, then the method requires that the region be split
into two regions.
• Then each of these two regions is independently tested
by the predicate (measurement).
• This procedure continues until all resulting regions are
uniform.
Region Splitting
 Region-Based Segmentation
Region Splitting
• 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.
Numerical
Question: Apply Region Splitting And Merging Algorithm To The
Following Image And Show The Resulting Quad Tree. Predicate to be
used is “ all pixels in a region should have the same grey value.
• Apply region splitting on following image . Assume the threshold
value <=3.

5 6 4 7 4 5 5 3

6 7 7 6 3 3 2 1

6 6 4 4 3 2 5 6

4 5 4 5 4 6 2 3

3 2 3 0 7 5 3 2

1 0 1 0 2 2 6 5

1 0 1 1 3 0 4 4

0 2 1 0 2 3 5 4
• segment the following image using region split and merge
technique. Draw quad tree representation for the corresponding
segmentation.
Results – Region grow
Results – Region Split
Results – Region Split and Merge