Image Segmentation

Introduction
 Segmentation is to subdivide an image into its
component regions or objects.
 Segmentation should stop when the objects of
interest in an application have been isolated.
 Segmentation algorithms generally are based on one
of 2 basis properties of intensity values:
 discontinuity : to partition an image based on
sharp changes in intensity
 similarity : to partition an image into regions
that are similar according to a set of predefined
criteria.
Segmentation
 Discontinuities based
segmentation
 There are three basic types of gray-level discontinuities
in a digital image: points, lines, and edges
 The most common way to look for discontinuities is to
run a mask through the image.
 We say that a point, line, and edge has been detected at
the location on which the mask is centered
if R  T ,where
R  w1 z1  w2 z2  ......  w9 z9
 Discontinuities based
segmentation
 Point detection

a point detection mask

 Line detection

a line detection mask

Line Detection
Line Detection
1st and 2nd order Gradients
1st order Gradients
1st order Gradients
1st order Gradients
1st order Gradients
Laplacian of Gaussian(LOG)
LoG
 Fundamental ideas –
 The Gaussian blurs the image
 The Laplacian is isotropic and no other directional
mask is needed.
 The zero crossings of the operator indicate edge
pixels. They may be computed by using a 3x3
window around a pixel and detect if two of its
opposite neighbors have different signs (and their
difference is significant compared to a threshold).
LoG
 Segmentation Approaches
 Edge-based approaches
 Use the boundaries of regions to segment the image.
 Detect abrupt changes in intensity (discontinuities).
 Region-based approaches
 Use similarity among pixels to find different regions.
Image Gradient
Gradient Properties
Gradient operators
Prewitt Operator
Sobel Operator
Canny Edge Detection
Step 1:Smooth image
Step 2: Compute Gradient
Step 3: Nonmaxima Suppression
Step 3: Nonmaxima Suppression
Step 3: Nonmaxima Suppression
Step 4: Double Thresholding
Step 4: Double Thresholding
Double Thresholding
Canny Vs LoG
Main Approaches
 Thresholding (i.e., pixel classification)
 Region growing (i.e., splitting and merging)
 Thresholding
 The simplest approach to
segment an image.

If f (x, y) > T then

f (x, y) = 0
else f (x, y) = 255
Thresholding Using Image Histogram
 Regions with uniform intensity give rise to strong
peaks in the histogram.
 In general, a good threshold can be selected if the
histogram peaks are tall, narrow, symmetric, and
separated by deep valleys.

T
 Thresholding Using Image Histogram
(cont’d)

 Multiple thresholds are possible

If f (x, y) < T1 then f (x, y) = 255
else if T1 < f (x, y) < T2 then f (x, y) = 128
else f (x, y) = 0

T1 T2
Effect of Illumination on Segmentation

 How does illumination affect the histogram of an

image?
Effect of Illumination on Segmentation
(cont’d)
Handling non-uniform illumination:
local thresholding
 A single threshold will not work well when we have
uneven illumination due to shadows or due to the
direction of illumination.
 Idea:
 Partition the image into m x m subimages (i.e., illumination is
likely to be uniform in each subimage).
 Choose a threshold Tij for each subimage.
Handing non-uniform illumination:
local thresholding (cont’d)

This approach might lead

to subimages having simpler
histogram (e.g., bimodal)
Handling non-uniform illumination:
local thresholding (cont’d)

single threshold local thresholding using Otsu’s method

Drawbacks of Thresholding
 Threshold selection is not always straightforward.
 Pixels assigned to a single class need not form
coherent regions as the spatial locations of pixels are
completely ignored.
 Only hysteresis thresholding considers some form of spatial
proximity.
Other Methods
 Region Growing
 Region Merging
 Region Splitting
 Region Splitting and Merging
Properties of region-based
segmentation
 Partition an image R
into sub-regions R1, R2,..., Rn

 Suppose P(Ri) is a logical

predicate, that is, a property
that the pixel values of region Ri satisfy
(e.g., the gray level values are between 100 and 120).
Region Growing
 Region-growing approaches exploit the fact that
pixels which are close together have similar gray
values.
 Start with a single pixel (seed) and add new pixels
slowly
Region Growing (cont’d)

Multiple regions
can be grown in
parallel using
multiple seeds
Region Growing (cont’d)
 How do we choose the seed(s) in practice ?
 It depends on the nature of the problem.
 Without a-priori knowledge, compute the histogram and
choose the gray-level values corresponding to the strongest
peaks
 Region Growing (cont’d)

 How do we choose the similarity criteria (predicate)?

 The homogeneity predicate can be based on any characteristic of the
regions in the image such as:
 average intensity
 variance
 color
 texture
Region growing
Region growing
Region growing
0 1 2 0
2 5 6 1
1 4 7 3
0 2 5 1
 Region Merging
 Merging schemes begin with a partition satisfying
condition (4) (e.g., regions produced using
thresholding).

 Then, they proceed gradually merging adjacent

image regions.
Region Merging (cont’d)
 Region Splitting
 Region splitting operations add missing boundaries
by splitting regions that contain parts of different
objects.
 Splitting schemes begin with a partition satisfying
condition (5), for example, the whole image.

 Then, they proceed to satisfy condition (4) by

gradually splitting image regions.
 Region Splitting (cont’d)
 Two main difficulties in implementing this
approach:
 Deciding when to split a region (e.g., use variance, surface
fitting).
 Deciding how to split a region.
Region Splitting and Merging
 Splitting or merging might not produce good results
when applied separately.
 Better results can be obtained by interleaving merge
and split operations.
Region Splitting and Merging (cont’d)
Image Discriptors
 Segmentation:
 Dived the image in objects and back ground
 Morphology:
 Regularises the objects and background
 Image understanding :
 Given regularised image segments, make computer
understand the objects in image
 We need proper description of objects which can be
matched with prior knowledge.
Image understanding techniques
 Boundary based segmentation: represent boundary
such that we can describe the object
Interested in shape of objects
 Region based: Not only boundary but also surface
property
 Finally matching mechanism to identify objects
 Chain code: Boundary based representation.
 Chain code:
 Works on digital representation of image
2  To define shape , the direction of pixels can
3 1
have one of the eight values assuming 8-
connectivity.
4 0  When we move from (i)th point to (i+1) th
point there are only 8 options and length is
one and each has specific direction
5 7
6  Represent this direction with a number
 Boundary will be sequence of numbers
 So we get code which is called Chain code.
Scale, rotation and translation
 Often we want descriptors that are invariant of
scale, rotation and translation:
Chain Code
 The chain code depends on the starting point.
 To normalize it, we treat the code as a circular
sequence of direction numbers and redefine the
starting point so that the resulting sequence forms
an integer of minimum magnitude.
 To account for rotation, we use the first differences
of the chain code instead of the code itself.
 The first difference is obtained by counting the
number of direction changes that separate two
adjacent elements of the code.
Find Chain Code
Find Chain Code

8-connected:
0007776542344542212
Find Chain Code and differential chain
code

8-connected:
0007776542344542212

2
First Difference(Clockwise): 3 1
0001001112770712017
4 0

5 7
6
Shape number
 First Difference(Clockwise):
0001001112770712017
 Consider this as cycle instead of sequence
 Choose the starting point anywhere
 Take the starting point such that the code is smallest
(minimum) numerical value
 This value will be unique and this is called Shape
number