Image Segmentation

Segmentation

accurate boundary delineation is often required

Goal:

find coherent “blobs” or specific “objects”

lower level tasks large grey area higher level tasks
(e.g. “superpixels”) in-between (e.g. cars, humans, or organs)
Why is this useful?

AIBO
RoboSoccer
(VelosoLab)
Ideal Segmentation

can
recognize
objects
with
known ?
simple ?
color ?
models
 Image Segmentation Techniques

❑Edge Detection Techniques

❑Histogram-based thresholding

❑Region growing

❑ Region splitting and merging

 TYPES OF EDGES and definition
• Variation of Intensity / Gray
Level
• Step Edge
• Ramp Edge
• Line Edge
• Roof Edge
• Definition of edge is the abrupt
change in intensity value

6
 METHODS OF EDGE DETECTION

❑First Order Derivative / Gradient Methods

Roberts Operator
Sobel Operator
Prewitt Operator
❑Second Order Derivative
Laplacian
Laplacian of Gaussian
Difference of Gaussian
❑Optimal Edge Detection
Canny Edge Detection
7
Edge Detection
 Gradient Operators
❑The gradient of the image I(x,y) at location (x,y), is the
vector:
 I ( x, y ) 
G x    x 
I =   =  I ( x, y ) 
G
 y  
 y
 

❑The magnitude of the gradient:
I = I = G 2
x + G y2 
❑The direction of the gradient vector:
 Gx 
 ( x, y ) = tan  
−1

 Gy 
The direction of the edge at location (x,y) is
perpendicular to the gradient vector at that point
 Gradient
❑ Approximation of Gradient for a discrete
two dimensional function Gx  f [i, j + 1] − f [i, j ]
❑ Convolution Mask
❑ Gx= Gy  f [i, j ] − f [i + 1, j ]
-1 1 -1 1
❑ Gy =
1 -1 1
-1 1 1
❑ Differences are computed at the -1 -1
interpolated points [i, j+1/2] and [i+1/2, j]

10
Robert Operator
Sobel Operator
 Sobel Operator - Example

• Compare the output of the Sobel

Operator with that of the Roberts
Operator:
• The spurious edges are still present
but they are relatively less intense
compared to genuine lines
• Roberts operator has missed a few
edges
• Sobel operator detects thicker
edges
• Will become more clear with the
final demo 13
Outputs of Sobel (top) and Roberts operator
Gradient Methods – Prewitt Operator

14
 Prewitt Operator

The gradient magnitude is usually computed as

Prewitt operator is defined by a set of eight masks, four of which are

shown in Figure . Others can be generated by rotation of 90' successively.
 Kirsch Operator

Kirsch masks can be defined in eight directions,

which yields the estimated gradients in these directions
 First Order Derivative Methods - Summary

❑ Noise – simple edge detectors are affected by noise –

filters can be used to reduce noise

❑ Edge Thickness – Edge is several pixels wide for Sobel

operator– edge is not localized properly

❑ Robert's operator is very sensitive to noise

❑ Sobel operator goes for averaging and emphasizes on the

pixel closer to the center of the mask. It is less affected by
noise and is one of the most popular Edge Detectors.

17
 Second Order Derivative Methods

• Zero crossing of the second derivative of a

function indicates the presence of a maxima

18
 Second Order Derivative Methods - Laplacian

❑Defined as

❑Mask
0 1 0
1 -4 1
0 1 0

❑Very susceptible to noise, filtering required, use

Laplacian of Gaussian
19
Second Order Derivative Methods - Laplacian of Gaussian

❑ Smooth the image using Gaussian filter

❑ Enhance the edges using Laplacian operator

❑ Zero crossings denote the edge location

❑ Use linear interpolation to determine the sub-pixel

location of the edge

20
 Laplacian of Gaussian – contd.

❑Defined as

❑Greater the value of s, broader is the Gaussian filter, more is

the smoothing
❑Too much smoothing may make the detection of edges
difficult

21
Laplacian of Gaussian - contd.
• Also called the Mexican Hat operator

22
 Laplacian of Gaussian – contd.

• Mask

Discrete approximation to LoG function with Gaussian = 1.4

23
 Second Order Derivative Methods -
Difference of Gaussian - DoG

• LoG requires large computation time for a large edge

detector mask
• To reduce computational requirements, approximate the
LoG by the difference of two LoG – the DoG

x 2+ y 2 x 2+ y 2
−( ) −( )
212
e 2 2
2
e
DoG ( x, y ) = −
2 1 2 2
2 2

24
 Difference of Gaussian – contd.

Advantage of DoG
❑Close approximation of LoG
❑Less computation effort
❑Width of edge can be adjusted by changing s1 and s2

25
 Canny Edge Detection
❑Low error rate
❑All true edges should be found
❑Edge points should be well localized Edges
should be located as close as possible to the true
edges
❑Single edge point response One point for each
true edge point No of local maxima around true
should be minimum
 Canny Edge Detection Algorithm
❑Smooth image I with 2D Gaussian:
GI
❑Find local edge normal directions for each pixel
(G  I )
n=
(G  I )
❑Compute edge magnitudes
(G  I )
❑Locate edges by finding zero-crossings along the edge
normal directions (non-maximum suppression)

 2 (G  I )
=0
n 2
 Thresholding

• Broken edges due to fluctuation of operator output

above and below the threshold – results in Streaking
• Use double thresholding to eliminate streaking

28
 Thresholding
Bi-level thresholding is employed on images which have
bimodal histograms.
In bi-level thresholding, the object and background form two
different groups with distinct gray levels.
A simple iterative algorithm for threshold selection in a bimodal image
Multilevel Thresholding
 Region growing

The fundamental drawback of histogram-based region

detection is that histograms provide no spatial information (only
the distribution of gray levels)

Region-growing approaches exploit the important fact that

pixels which are close together have similar gray values

Region growing techniques start with one pixel of a

potential region and try to grow it by adding adjacent
pixels till the pixels being compared are too dissimilar
 Region growing

Region growing in a brief…

1. Choose the seed pixels (one for every segment).The first

pixel selected can be just the first unlabeled pixel in the
image or a set of seed pixels can be chosen from the
image
2. Check the neighboring pixels and add them to the region
if they are similar to the seed

3. Repeat step 2 for each of the newly added pixels; stop if

no more pixels can be added
 Split & merge

Split & merge in a brief…

1. Split (& merge) starts from the assumption that the entire
image is homogeneous
2. If this is not true (by the homogeneity criterion), the image is
split into four sub images
3. This split is repeated until no further splitting is possible

4. Merging phase: If 2 adjacent regions are homogenous, they

are merged
5. Repeat step 4 until no further merging is possible
 Split & Split and merge

Since the procedure is recursive, it produces an image representation

that can be described by a tree whose nodes have four sons each
*Such a tree is called a
‘Quadtree’. Therefore split is also
known as ‘quadtree segmentation’

Split &
merge
 Split & Split and merge

Split advantage:
Created regions are adjacent and homogenous

Split dis-advantage:
Over splitting since no merge is performed

Improvement::

Split &
merge
 Split & Split and merge

Split vs. Split & merge

original Split only Split & merge