The Segmentation Problem

Computer Graphics and Image Processing

Lecture 7

Muhammad Usman Ghani Khan

Department of Computer Science & Engineering

UET, Lahore

Autumn Semester

Computer Graphics and Image Processing - Lecture 7

 The Segmentation Problem

Outline

1 The Segmentation Problem

Definitions
Segmentation Examples
Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Computer Graphics and Image Processing - Lecture 7

 The Segmentation Problem

Where we stang?

Today Discussion
So far we have been considering image processing
techniques used to transform images for human
interpretation
Today we will begin looking at automated image analysis
by examining the thorny issue of image segmentation:
The segmentation problem
Finding points, lines and edges

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Outline

1 The Segmentation Problem

Definitions
Segmentation Examples
Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Segmentation Problem

+ The purpose of image segmentation is to partition an image into meaningful

regions with respect to a particular application
+ The segmentation is based on measurements taken from the image and might
be grey level, colour, texture, depth or motion
+ 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

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

The Segmentation Problem

+ 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

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

What is segmentation

Subdivides an image into its constituent regions or objects

Separate an image into regions which are called as objects
and background
Represent the result images with binary images, label the
objects as 1 and the background as 0 commonly.
Heavily rely on one of two properties of intensity values:
Discontinuity — Partition based on abrupt changes in
intensity, e.g., edges in an image
point/ line/ edge/ corner detection
Similarity — Partition based on intensity similarity, e.g.,
thresholding
thresholding, region growing / splitting / merging

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Outline

1 The Segmentation Problem

Definitions
Segmentation Examples
Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Segmentation based on Color

Segmentation based on greyscale

Very simple model of greyscale leads to inaccuracies in
object labelling

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Segmentation based on Texture

Segmentation based on texture
Enables object surfaces with varying patterns of grey to be
segmented

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Segmentation based on Motion

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

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Segmentation based on Depth

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

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Segmentation Examples

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Outline

1 The Segmentation Problem

Definitions
Segmentation Examples
Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Detection Of Discontinuities

There are three basic types of grey level discontinuities that we

tend to look for in digital images:
1 Points
2 Lines
3 Edges
We typically find discontinuities using masks and correlation

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Point Detection

Point detection can be achieved simply using the mask below:

Points are detected at those pixels in the subsequent

filtered image that are above a set threshold

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Point Detection

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Line Detection

The next level of complexity is to try to detect lines

The masks given above extract lines that are one pixel
thick and running in a particular direction

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Line Detection

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Edge Detection

An edge is a set of connected pixels that lie on the boundary

between two regions

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Edges & Derivatives

We have already spoken about how

derivatives are used to find
discontinuities
1st derivative tells us where an
edge is
2nd derivative can be used to
show edge direction

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Derivatives & Noise

Derivative based edge detectors are extremely sensitive to

noise

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Common Edge Detectors

Given a 3 ∗ 3 region of an image the following edge detection

filters can be used

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Edge Detection Example

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Edge Detection Problems

Often, problems arise in edge detection in that there are is

too much detail
For example, the brickwork in the previous example
One way to overcome this is to smooth images prior to
edge detection

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Edge Detection Example With Smoothing

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Laplacian Edge Detection

We encountered the 2nd-order derivative based Laplacian filter
already

The Laplacian is typically not used by itself as it is too

sensitive to noise
Usually when used for edge detection the Laplacian is
combined with a smoothing Gaussian filter
Computer Graphics and Image Processing - Lecture 7
 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Laplacian Of Gaussian

The Laplacian of Gaussian (or Mexican hat) filter uses the

Gaussian for noise removal and the Laplacian for edge
detection

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Laplacian Of Gaussian - Example

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Summary

In this section we have begun looking at segmentation,

and in particular edge detection
Edge detection is massively important as it is in many
cases the first step to object recognition
Next section is about segmentation techniques.

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Outline

1 The Segmentation Problem

Definitions
Segmentation Examples
Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Segmentation technique

We will look at two very simple image segmentation techniques

that are based on the greylevel histogram of an image
Thresholding
Clustering

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Thresholding

Thresholding is usually the first step in any segmentation

approach
We have talked about simple single value thresholding
already
Single value thresholding can be given mathematically as
follows:

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Thresholding Example

Imagine a poker playing robot that needs to visually

interpret the cards in its hand

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Thresholding Example: Be careful

If you get the threshold wrong the results can be disastrous

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Basic Global Thresholding

Based on the histogram of an image

Partition the image histogram using a single global
threshold
The success of this technique very strongly depends on
how well the histogram can be partitioned

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Basic Global Thresholding Algortithm

The basic global threshold T is calculated as follows:
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
µ1 + µ2
T = (1)
2
4 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
Computer Graphics and Image Processing - Lecture 7
 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Thresholding Example 1

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Thresholding Example 2

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Types of thresholding Techniques

MEAN TECHNIQUE This technique used the mean value of the pixels as the
threshold value and works well in strict cases of the images that have
approximately half to the pixels belonging to the objects and other half to the
background.
P-TILE TECHNIQUE Uses knowledge about the area size of the desired object
to the threshold an image.
HISTOGRAM DEPENDENT TECHNIQUE (HDT) separates the two
homogonous region of the object and background of an image.
EDGE MAXIMIZATION TECHNIQUE (EMT) Used when there are more than one
homogenous region in image or where there is a change of illumination between
the object and its background.
VISUAL TECHNIQUE Improve peoples ability to accurately search for target
items

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Thresholding techniques examples

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Thresholding techniques examples

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Thresholding techniques examples

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Clustering

Defined as the process of identifying groups of similar

image primitive.
It is a process of organizing the objects into groups based
on its attributes
An image can be grouped based on keyword (metadata) or
its content (description)
KEYWORD Form of font which describes about the image
keyword of an image refers to its different features
CONTENT Refers to shapes, textures or any other
information that can be inherited from the image itself.

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Problems With Single Value Thresholding

Single value thresholding only works for bimodal
histograms
Images with other kinds of histograms need more than a
single threshold

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Problems With Single Value Thresholding

Let’s say we want to isolate the contents of the bottles

Think about what the histogram for this image would look
like
What would happen if we used a single threshold value?

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Single Value Thresholding and Illumination

Uneven illumination can really upset a single valued

thresholding scheme

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Basic Adaptive Thresholding

An approach to handling situations in which single value

thresholding will not work is to divide an image into sub
images and threshold these individually
Since the threshold for each pixel depends on its location
within an image this technique is said to adaptive

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Basic Adaptive Thresholding Example

The image below shows an example of using adaptive
thresholding with the image shown previously

As can be seen success is mixed

But, we can further subdivide the troublesome sub images
for more success
Computer Graphics and Image Processing - Lecture 7
 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Basic Adaptive Thresholding Example

These images show the

troublesome parts of the previous
problem further subdivided
After this sub division successful
thresholding can be achieved

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Summary

In this section we have begun looking at segmentation,

and in particular thresholding
We saw the basic global thresholding algorithm and its
shortcomings
We also saw a simple way to overcome some of these
limitations using adaptive thresholding

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Outline

1 The Segmentation Problem

Definitions
Segmentation Examples
Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Segmentation Approaches

Water based segmentation

Region grow segmentation
Edge based segmentation
Connectivity preserving relaxation based method

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Water based segmentation

Derive surface image: A variance image is derived from

each image layer. Centred at every pixel, a 3x3 moving
window is used to derive its variance for that pixel. The
surface image for watershed delineation is a weighted
average of all variance images from all image layers.
Delineate watersheds From the surface image, pixels
within a homogeneous region form a watershed
Merge Segments Adjacent watershed may be merged to
form a new segment with larger size according to their
spectral similarity and a given generalization level

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Water based segmentation - example 1

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Water based segmentation - example 2

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Region grow approach

This approach relies on the homogeneity of spatially

localized features
It is a well-developed technique for image segmentation. It
postulates that neighbouring pixels within the same region
have similar intensity values.
The general idea of this method is to group pixels with the
same or similar intensities to one region according to a
given homogeneity criterion.

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Region Grow Example

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Edge based methods

Edge-based methods center around contour detection: their

weakness in connecting together broken contour lines make
them, too, prone to failure in the presence of blurring.

Computer Graphics and Image Processing - Lecture 7

 Definitions
Segmentation Examples
The Segmentation Problem Some common foreground objects detection
Segmentation techniques
Segmentation Approaches

Connectivity preserving relaxation based method

Referred as active contour model
The main idea is to start with some initial boundary shape represented in the
form of spline curves, and iteratively modify it by applying various
shrink/expansion operations according to some energy function

Computer Graphics and Image Processing - Lecture 7