Digital Image Processing

Image Segmentation

1
 Outline
• What is Image segmentation
• Different Approaches for Image Segmentation
– Discontinuity based
– Region based
• Different Edge Detection operators
• Linking of edge points
– Local processing
– Global processing (Hough Transform)

2
 Image analysis
• It is the extraction of meaningful information from images

• Image analysis tasks can be as simple as reading bar coded tags or as

sophisticated as identifying a person from their face.

• Computers are vital for the analysis of large amounts of data, for tasks that
require complex computation, or for the extraction of quantitative
information.

• On the other hand, the human visual cortex is an excellent image analysis
apparatus, especially for extracting higher-level information, and for many
applications — including medicine, security, and remote sensing — human
analysts still cannot be replaced by computers.

• For this reason, many important image analysis tools such as edge
detectors and neural networks are inspired by human visual perception
models.
3
 Image analysis: Techniques
• There are many different techniques used in automatically analyzing
images.

• Each technique may be useful for a small range of tasks. However,

– there still aren't any known methods of image analysis that are
generic enough for wide ranges of tasks, compared to the abilities
of a human's image analyzing capabilities.

• Examples of image analysis techniques in different fields include:

– Image segmentation,
– 2D and 3D object recognition
– motion detection e.g. Single particle tracking,
– video tracking,
– optical flow,
– medical scan analysis,
– 3D Pose Estimation,
– automatic number plate recognition.
4
 Image Segmentation

• Image segmentation is a first and important step in image

analysis
– Segmentation divides an image into its constituent regions or objects.
– Segmentation allows to extract objects in images.
– Unsupervised or supervised Segmentation -Techniques

• Segmentation of images is a difficult task in image processing.

Still under research.
 Image Segmentation
• Image segmentation is the division of an image into regions or categories,
which correspond to different objects or parts of objects
– Every pixel in an image is allocated to one of a number of these
categories.
• 2 x Approaches
– Discontinuity Based segmentation (methods that are based on detecting sharp, local
changes in intensity)
• Isolated points
• Lines
• Edges
– Similarity based
• Thresholding
• Region growing
• Region splitting and Merging

6
Categorization of Image Segmentation
approaches
• Two approaches
• Discontinuity Based segmentation (methods that
are based on detecting sharp, local changes in
intensity)
– Isolated points
– Lines
– Edges
• Similarity based
– Thresholding
– Region growing
– Region splitting and Merging
7
 Discontinuity based Approaches
• Points
Detected through
• Edges Mask processing

• lines
• An isolated point may be viewed as a foreground (background) pixel
surrounded by background (foreground) pixels

• Edge pixels are pixels at which the intensity of an image changes

abruptly, and edges (or edge segments) are sets of connected edge
pixels

• A line may be viewed as a (typically) thin edge segment in which the

intensity of the background on either side of the line is either much
higher or much lower than the intensity of the line pixels, aslo called
“roof edges.” 8
9
 Recall Mask processing

Calculate a weighted sum using the Mask,

Where we denote R to be the response of the Kernel 10
Point Detection

Non-Negative Threshold T,
is compared with filter
11
response
Point detection

12
Point detection

13
Line Detection

14
15
Line Detection

16
 Line Detection
For Mask i and mask j, the line is directed in the
direction of mask i

17
Edges

18
Edges

19
Edge Detection

20
 Edge Detection
Because of Quantization and sampling all the abrupt
changes/transitions are converted to gradual
transitions Intensity profile along a horizontal scan
line.
Second derivative are sensitive to noise, but can be used
to give us secondary information use the sign of the 2nd
derivative to tell either the point are on the darker side
or brighter side. And the zero crossing can give us exact
location of the boundary when there is a gradual
transition between two regions.

21
Edge and line in a single figure

The boundary for two distinct regions is the edge, having

different intensity values

You can think of a line as being two opposite edges very close
together.

23
 Gradient Operator

How to apply the derivative operations, for edge detection we are

interested in the magnitude of gradient.

27
Gradient Direction

28
Edge Operators

29
Prewitt Edge Operator

30
 Sobel Edge Operator

Has an effect of image averaging that’s why has a good

response to spurious noise
31
Sobel Edge detection example

32
Sobel Edge detection example

33
Edge detection with Thresholding

34
Diagonal Edge detection

35
2nd Derivative operator

36
LoG

37
 LoG

The Laplacian of a Gaussian sometimes is called the Mexican hat function. It

also can be computed by smoothing the image with the Gaussian smoothing
mask, followed by application of the Laplacian mask. 38
39
 Edge Linking

Edges are not usually connected…. Due to non uniform illumination

or presence of noise

40
Edge linking: Local Processing
They are similar, if:

41
 Edge Linking and Boundary Detection
Local Processing: Example

In this example,
we can find the
license plate
candidate after
edge linking
process.
 Hough Transform

Global processing technique to include points that are further apart.

It is a mapping from the spatial domain to a parameter space
e.g. in x, y plane Specified by two parameters, one is slop and the other is intercept
m and c, in the parameter space it will be a single point. 43
Hough Transform, equation of a line
passing through a point x1, y1

44
Hough Transform, many lines passing
through a single point (x1,y1) in xy
plane

45
 Hough Transform

Many line passing through a single point in xy plane becomes a single line
in mc plane, with x1 and y1 as the slope and C-intercept 46
 Hough Transform

The red line passing through the two boundary points is

represented by the intersecting point of the two lines c-
47
dash and m-dash
Hough Transform
Diagram just simplified, only
showing the that- red passing
line

Two lines two equations

48
Hough Transform
If many boundary points,
there would still be one
particular red line

Number of lines in mc plane

is equal to the boundary
points

49
 Hough Transform

A(i,j) corresponds
to mi and cj
Initialized A(i,j) =0

Entire m c space is divide into a number of smaller accumulator cells

Smaller accumulator cells
50
 Hough Transform
• A boundary point or edge point that needs linking (xk,yk) is given by
c=-mxk +yk --Eq.1 in the m-c plane
• What we will do is to iterate through all possible slopes, m-values as part of our m-
c grid and find the corresponding c –value for each m value. Now add a 1 to that
(m,c) cell in the accumulator, to put it in other words,
For each mp in Eq1 ==> cq
Write A(p,q)=A(p,q) +1

• This has to be done for all the boundary points (xk,yk)

• Suppose A(i,j) =Q , where Q is the number of points in the xy-plane that are part of
a line with ci and mj as the specific intercept and slope. And if we want to keep this
line in our output Hough transd image then the equation of this line is given by
y=mix +cj

• Accuracy depend on the number of bins 51

 Hough Transform

How to find the number of straight lines in an

image. Problem with this version of Hough
transform
53
 Hough Transform (Normal
Representation of a straight line)

54
 Hough Transform (Normal
Representation of a straight line)
Maximum values of theta and row

55
 Hough Transform (Normal
Representation of a straight line)

56
The rest of the story is similar with
that to mc plane described earlier

57
The rest of the story is similar with
that to mc plane described earlier

58
A particular line equation selected
from the row-theta grid

59
As before see the boundary points in
xy plane and the row-theta plane its
zero crossings highlighting significant
lines to be retained,

60
Segmentation followed by edge linking
through hough transform

61
Extra slides for reference

62
 Detection of Discontinuities
Gradient Operators: Example

f  G x + G y
 Detection of Discontinuities
Gradient Operators: Example
 Detection of Discontinuities
Gradient Operators: Example
 Detection of Discontinuities
Gradient Operators

Gaussian mask
 References
• Gonzalez R. C. & Woods R.E. (2008). Digital Image Processing. Prentice
Hall.
• Forsyth, D. A. & Ponce, J. (2011).Computer Vision: A Modern Approach.
Pearson Education.

67