Image Segmentation

Image segmentation is an important pre-

processing tool. It produces a binary representation
of the object with features of interest such as
shapes and edges.

Common operations include:

Thresholding: to segment an object from its
background through a simple pixel amplitude
based decision. Complicated thresholding
methods may be used when the background is
not homogeneous.

Edge detection: to identify edges of an object

through a set of high-pass filtering. Directional
filters and adaptive filters are frequently used to
achieve reliable results.
 Image Segmentation

 Image segmentation divides an image into regions

that are connected and have some similarity within
the region and some difference between adjacent
regions.
 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.
• Medical image analysis
can be used as
preliminary screening
techniques to help
doctors
• Partial Differential
Equation (PDE) has
been used for
segmenting medical
images

active contour model (snake)

• For fingerprint, face and
iris images, we also need
to segment out the region
of interest
• Various cues can be used
such as ridge pattern, skin
color and pupil shape
• Robust segmentation
could be difficult for
poor-quality images
 3 types of image features based on sharp local
changes in intensity:
1. Edges: Sets of connected edge pixels.(Edge
pixels:- Region where intensity of an image
function changes abruptly.)

2. Line: Edge segment where the intensity of the

background on either side of the line is much
higher or much lower than the intensity of the
line pixels.

3. Isolated Point : A line whose length and width

are equal to one pixel.
Requirements for digital derivative
First derivative
1) Must be zero in flat segment / constant intensity
2) Must be nonzero along ramps.
3) Must be nonzero at the onset of a gray-level step or
ramp
Second derivative
1) Must be zero in flat segment / constant intensity
2) Must be zero along ramps.
3) Must be nonzero at the onset and end of a gray-level
step or ramp
 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
 Detection of Discontinuities
Point Detection

R T
where T : a nonnegativ e threshold

Note that the mask coefficients sum to zero indicate

that the mask reaponse will be zero in the areas of
constant gyay levels
Find the location of the points as follows:

w=[-1 -1 -1; -1 8 -1; -1 -1 -1];

g=abs(imfilter ( double(f), w);
T=max(g(:));
g=g >=T;
imshow(g);
 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).
 Detection of Discontinuities
Line Detection

All vertical and

Thresholding to
horizontal
max value in
components of
original image.
the image are
Line segment
Eliminated
that was one
Components
pixel thick and
that tend to -
and oriented
45 degree have
towards
strongest
-45 degree is
response
extracted
Detection of Discontinuities
Edge Detection
Detection of Discontinuities
Edge Detection
 Detection of Discontinuities
Edge Detection

 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

 f 
 
x
gx   
f  grad ( f )      
 g y   f 
 
 y 
 Detection of Discontinuities
Edge Detection

 The image Gradient and its properties

◦ Magnitude (length) of vector f, denoted as M(x,y)
◦ The direction of the gradient vector is given by the angle
α(x,y)

M ( x, y )  mag (f )  g x2  g y2
 gy 
 ( x, y )  tan  
1

 gx 
 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

f  G x  G y
 Consider a single row or column of the
image
◦ Plotting intensity as a function of position
gives a signal

Where is the edge?

Where is the edge? Look for peaks in
 This saves us one operation
 Consider

Laplacian of Gaussian
operator

Where is the edge? Zero-crossings of bottom graph

 x2  y2

Smooth by Gaussian S  G * I G 
1
e 2 2

2 

Use Laplacian to find derivatives

 2
 2
2 S  2 S  2 S
x y
2 S  2 G * I   2G * I
x2  y2
1  2
x y 2
 
 G  
2
 2  e 2 2

2  3  2 
 derivative of Gaussian

Laplacian of Gaussian

Gaussian

 is the Laplacian operator:

 x2  y2
1  x y 2 2
 
 G  
2

3 
2 e 2 2

2   2 
Y
0.0008 0.0066 0.0215 0.031 0.0215 0.0066 0.0008
0.0066 0.0438 0.0982 0.108 0.0982 0.0438 0.0066
0.0215 0.0982 0 -0.242 0 0.0982 0.0215 X
0.031 0.108 -0.242 -0.7979 -0.242 0.108 0.031
0.0215 0.0982 0 -0.242 0 0.0982 0.0215
0.0066 0.0438 0.0982 0.108 0.0982 0.0438 0.0066
0.0008 0.0066 0.0215 0.031 0.0215 0.0066 0.0008
Image I 2G * I Edge Image
2 Zero Crossings
* G
Detection

2G * I Zero Crossings

  1

 3

 6
Region Growing

1 0 5 6 7

1 1 5 8 7

0 1 6 7 7

2 0 7 6 6
Connectivity:
Region
Growing
1 0 5 6 7

1 1 5 8 7

0 1 6 7 7

2 0 7 6 6
Thresholding

• During the thresholding process, individual pixels in an

image are marked as “object” pixels if their value is
greater than some threshold value (assuming an object to
be brighter than the background) and as “background”
pixels if their value is less than threshold value.

• Typically, an object pixel is given a value of “1” while a

background pixel is given a value of “0”.

• The key parameter in the thresholding process is the

choice of the threshold value.
 Transformation graph
Original Image

255
O
u
t
p
u
t

s
0 30
255 input r
Graph for T=30

• Give a slider ranging from 0 to 255

so that user can select any one
threshold value.
• The graph should also vary along
with the slider depending on
threshold value.
Segmentation is accomplished by scanning the image pixel by pixel
and labeling each pixel as object or background, depending on
whether the grey level is greater or less than the value of T .

 0 f ( x, y )  T

g ( x, y )  
1 f ( x, y )  T


Thresholding works well when a grey level histogram of the image

groups separates the pixels of the object and the background into
two dominant modes. Then a threshold T can be easily chosen
between the modes.
• Human operator decided the threshold
• Use mean gray level of the image
• A fixed proportion of pixels are detected ( set to
1) by the thresholding operation
• Analyzing the histogram of an image
Threshold value 0
Threshold value 10
Threshold value 25
Threshold value 50
Threshold value 100
Threshold value 125
Threshold value 175
Threshold value 200
Threshold value 255
• If two dominant modes characterize the image
histogram, it is called a bimodal histogram. Only one
threshold is enough for partitioning the image.

• If for example an image is composed of two types of

light objects on a dark background, three or more
dominant modes characterize the image histogram.
If a bright object is placed against a dark background
Inspect the histogram and choose threshold
In this technique inspection of histogram is not required

In this case the scene illumination is uniform so the results of

Global threshold are very good
 Global
thresholding fails

Much better results

Divide the image
into subimages
and than do
thresholding for
each sub image

This is called Adaptive thresholding as T is a function of

Subimage location also
Global Thresholding - Guidelines
for Use

The histogram for

image is

This shows a nice bi-modal distribution

--- the lower peak represents the
object and the higher one represents
the background. The picture can be
segmented using a single threshold at
a pixel intensity value of 120. The
result is shown in
Global Thresholding - Guidelines for Use
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).
 No. of pixels with
background are
very very small so
its contribution in
histogram is
Negligible so instead
Subdivide this region further and find
of bimodal histogram
threshold for each sub- subregion it shows single peak
and hence does not
Satisfactory results show good results for
this particular
subimage

So for non uniform illumination global threshold fails

And we need to apply Adaptive thresholding
 LOCAL Thresholding

Bimodal histogram becomes single node histogram

How to solve this problem?
 2 advantage
1. Area of fore ground and background
on histogram becomes nearly equal
symetric histogram
2. Probability of a pixel
belongingness is also equal

Detection of edge points from

gradien and laplacian operator
Gradient gives the strength of
the pixel to belong to the edge
Variation of intensities along X-axis
Laplacien gives the idea
wheather a point lies on the dark
side or bright side of edge
 Such points are not on the edge or near the edge

Points that belong to object

Points that belong to backgroung

For
implementation
0=0
Dark object on a +=128
-=255
bright background
Dark object on a
bright background

Transition along xaxis for an image

having a dark object on a bright background
This is called local thresholding
as we use the gradient and laplacian,
Which is the local property of pixel
location in an image
There are two main approaches to finding the
threshold:
(i) the Chow and Kaneko approach and
(ii) local thresholding.
The assumption behind both methods is that
smaller image regions are more likely to have
approximately uniform illumination, thus being
more suitable for thresholding.
• Chow and Kaneko divide an image into an array
of overlapping sub-images.
• Then find the optimum threshold for each sub-
image by investigating its histogram.
• The drawback of this method is that it is
computational expensive and, therefore, is not
appropriate for real-time applications.
 Adaptive thresholding - Local
thresholding
An alternative approach to finding the local
threshold is to statistically examine the
intensity values of the local neighborhood of
each pixel.
The statistic which is most appropriate
depends largely on the input image. Simple
and fast functions include the mean of the
local intensity distribution,
the median
value,

or the mean of the minimum and maximum

values,
• The size of the neighborhood has to be large
enough to cover sufficient foreground and
background pixels, otherwise a poor
threshold is chosen.
• On the other hand, choosing regions which
are too large can violate the assumption of
approximately uniform illumination.
• This method is less computationally intensive
than the Chow and Kaneko approach and
produces good results for some applications.
• Local adaptive thresholding, on the other hand, selects
an individual threshold for each pixel based on the
range of intensity values in its local neighborhood. This
allows for thresholding of an image whose global
intensity histogram doesn't contain distinctive peaks.
• A task well suited to local adaptive thresholding is in
segmenting text from the image

Because this image contains a

strong illumination gradient, global
thresholding produces a very poor
result, as can be seen in these
figures
Adaptive thresholding -Guidelines
for Use
Using the mean of a 7×7 neighborhood, adaptive thresholding
yields
• The method succeeds in the area surrounding
the text because there are enough foreground
and background pixels in the local
neighborhood of each pixel.
• i.e. the mean value lies between the intensity
values of foreground and background and,
therefore, separates easily.
• On the margin, however, the mean of the local
area is not suitable as a threshold.
• Because the range of intensity values within a
local neighborhood is very small and their mean
is close to the value of the center pixel.
The situation can be improved if the threshold
employed is not the mean, but (mean-C),
where C is a constant. Using this statistic, all
pixels which exist in a uniform neighborhood
(e.g. along the margins) are set to background.
The result for a 7×7 neighborhood and C=7 is
shown in

and for a 75×75 neighborhood and C=10 in

The larger window yields the poorer result,

because it is more adversely affected by the
illumination gradient. Also note that the latter
is more computationally intensive than
thresholding using the smaller window.
The result of using the median instead of the mean
can be seen in the figure below

The neighborhood
size for this
example is 7×7 and
C = 4). The result
shows that, in this
application, the
median is a less
suitable statistic
than the mean.
Consider another example image containing a strong
illumination gradient

This image can not be

segmented with a global
threshold, as shown in

where a threshold of 80 was used.

However, since the image contains a large

object, it is hard to apply adaptive
thresholding, as well. Using the (mean - C)
as a local threshold, we obtain.
with a 7×7 window and C
=4
You can simulate the effect with the following steps:
1. Convolve the image with a suitable statistical
operator, i.e. the mean or median.
2. Subtract the original from the convolved image.
3. Threshold the difference image with C.
4. Invert the thresholded image.
Why Region-Based
Segmentation?
 Segmentation
 Edge detection and
Thresholding not
always effective.
 Homogenous
regions
 Region-based
segmentation.
 Effective in noisy
images.
a) Every pixel must be in
a region
b) Points in a region
must be connected.
c) Regions must be
disjoint.
d) All pixels in a region
satisfy specific
properties.
e) Different regions have
different properties.
Region Segmented Image
 Thresholded image to
Xray image of a weilded region find the seed points.
Region with faults or dicontinuties have higher pixel cordinates having
Intensities in the xray image the intensity value 255
are chosen as the seedpoint

Region growing on the seed

points applied on the
original image

Segmentation achieved : defects extracted from the

xray image
Quad tree representation
 Do the following for each pixel I(u,v)
 Look at your four neighbors, left, right, up
and down
 If they all have the same sign as you, then
you are not a zero crossing
 Else, if you have the smallest absolute value
compared to your neighbors with opposite
sign, then you are a zero crossing
• 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.
1. Smooth image with Gaussian filter
2. Compute derivative of filtered image
3. Find magnitude and orientation of
gradient
4. Apply “Non-maximum Suppression”
5. Apply “Hysteresis Threshold”
• Smooth by Gaussian
x2  y2
S  G * I G 
1
e

2 2

2 
• Compute x and y derivatives
T
  
S   S 
S   Sx Sy 
T

 x y 
• Compute gradient magnitude and orientation

S  S x2  S y2

Sy
  tan 1

Sx
I Sx

Sy
Canny Edge
Detector
S  S x2  S y2

S  Threshold  25
• We wish to mark points along the curve
where the magnitude is highest.
• We can do this by looking for a maximum
along a slice normal to the curve (non-
maximum suppression).
• There are then two algorithmic issues: at
which point is the maximum, and where is
the next one?
Suppress the pixels in ‘Gradient Magnitude Image’ which are not
local maximum

 if S x, y   S x , y 
 S x, y 
M x, y    & S x, y   S x , y 
x, y 
 0 otherwise

x, y 
x,y  and x,y  are the neighbors of x,y  in S
x, y along the direction normal to an edge
Non-Maximum
Suppression

S  S x2  S y2

M  Threshold  25
Hysteresis Thresholding

• If the gradient at a pixel is above ‘High’,

declare it an ‘edge pixel’.

• If the gradient at a pixel is below ‘Low’,

declare it a ‘non-edge-pixel’.

• If the gradient at a pixel is between ‘Low’ and

‘High’ then declare it an ‘edge pixel’ if and
only if it is connected to an ‘edge pixel’
directly or via pixels between ‘Low’ and
‘ High’
Canny Edge Detector Hysteresis
Thresholding
Connectivity:
M M  Threshold  25

High  35
Low  15