Lecture 6: Edge Detection: Dmitrij Csetverikov

Faculty of Informatics
Eotv
os Lorand University
Budapest, Hungary
Lecture 6: Edge Detection

Types of local image features
Edges, lines, corners, blobs
Principles of edge detection
Basic Algorithms for Digital Image Analysis:

a course
Criteria for good edge filters

Gradient edge filters
Canny edge detector
Dmitrij Csetverikov
with help of Attila Lerch, Judit Verestoy, Zoltan Megyesi, Zsolt Janko
and Levente Hajder
http://visual.ipan.sztaki.hu
Edge localisation
Non-maxima suppression
Hysteresis thresholding
Zero-crossing edge detector
2
Local image features
Edge detection
Image edges do not necessarily coincide with physical edges
Edge
Line
Blob
Corner
Basic image features.

Edge: drastic change of intensity across object contour
Image edges are intensity discontinuities

Physical edges are surface discontinuities
Example: Edges of shadows are not surface discontinuities
Importance of intensity edges: Human eye detects them in hardware, at the
initial level of visual processing.
Line: narrow, elongated image region of approximately constant width and

intensity
Corner: sharp turn of a contour
ideal step edge
Blob: compact image region of approximately constant intensity

3
blurred edge
Edge profiles.
4
Principles of edge detection

Edge filtering
Edge localisation
edge magnitude
edge orientation
original image
edge map
edge orientation
Steps of edge detection.

Edge filter responds to edges and yields
Edge magnitude: strength of edge, a measure of local contrast
Edge orientation
original image
edge magnitude
edge orientation
edge map
Example of edge detection by 3 3 Prewitt operator.

Edge orientation is circular data; shown intensity-coded.
Tasks of edge localisation (post-processing):

Remove noisy edges
Remove phantom edges, obtain thin contours
Obtain edge map: a binary edge image.
Note: Noise smoothing may be applied before edge filtering.
Intensity profiles along lower (left) and upper (right) lines drawn in original image
edge
normal
edge
direction
Edge filters
Edge filters are high-pass filters using spatial derivatives of intensity function to
enhance intensity variation across the edge
edge
orientation
Edge normal, edge direction and edge orientation.

Edge normal: Direction of maximum intensity variation at edge point.
Unit vector perpendicular to the edge
Edge direction: Direction tangent to the contour
Unit vector parallel to the edge
Convention needed for unumbiguous definition: e.g., dark on the left
Also used: Edge orientation, which is circular data interpreted modulo .
7
suppress regions of constant intensity

The following operators are applied in edge filtering:
Intensity gradient is vector composed of the first order partial derivatives:
!
. f f
f (x, y) =
,
x y
Laplace operator is scalar composed of the second order partial derivatives:
. 2f 2f
f (x, y) =
+
x2 y 2
8
Criteria for good edge filters

f(x)
df
__
dx
2
d___
f
dx 2
A signal and its first and second derivatives.
1. No response to flat regions Sum of mask values is zero:

2. Isotropy: Response must be independent of edge orientation
r,c w(r, c)
=0
3. Good detection: Minimise the probabilities of

detecting spurious edges caused by noise (false positives)
missing real edges (false negatives)
4. Good localisation: Detected edges must be as close as possible to true edges.
5. Single response: Minimise number of false local maxima around true edge.
Edges are located at

maxima of absolute value of first derivative
zero-crossings of second derivative
step edge
response
noisy edge
response
10
W1
object
original image
isotropic edge filter
anisotropic edge filter
W2
Illustration to the isotropy criterion.

Illustration to the single response criterion.
The isotropic edge filter yields uniform edge magnitude for all directions.
The anisotropic edge filter yields non-uniform magnitude. In this illustration,
the response depends on the edge orientation as follows:
Directions 45 k are slightly amplified
Directions 90 k are slightly suppressed
11
The same piece of contours is detected in window W1 and window W2.

Phantom edges parallel to true edges, thick contours
The response depends on the overlap between the window and the contour.
The multiple response is typical for all window-based detection tasks.
12
Gradient edge filters
The meaning of the gradient vector
Assume that the intensity function f (x, y) is sufficiently smooth. The intensity
gradient is the following vector:
f f
,
x y
.
f (x, y) =
= fx , f y
original image
The magnitude M (x, y) and the orientation (x, y) of the gradient vector are
obtained as follows:
M (x, y) = kf (x, y)k =
intensity surface
thresholded image
fastest growth
edge
direction
intensity surface
fx2 + fy2
gradient =
edge normal
fx
(x, y) = arctan
fy
level lines
The gradient vector gives the direction and the magnitude of the fastest growth
of intensity.
Intensity surface of an edge and its gradient.
13
14
Simple 3 3 gradient masks
Constraining the gradient masks

The above family of gradient masks obeys the following constraints:
In discrete images, partial derivatives are approximated by finite differences.

The following family of gradient masks are used to compute the components
of the gradient vector:
1
p
1
2p
1
Gx
0
0
0
1
p2
1
1
p
1
0
1
Gy
2p
0
p2
1
0
1
Different values of the parameter p result in different versions of the masks:

p
Prewitt
3
Sobel
4
Isotropic
2+ 2
1. Mirror symetry with respect to (wrt) the edge normal:

Gx(1, c) = Gx(3, c)
2. Antisymmetry wrt the edge orientation
Gx(r, 1) = Gx(r, 3), Gx(r, 2) = 0
and similar for Gy
requried for precise localisation of edges

assumes antisymmetry of intensity profile of edge (sigmoid shape)
mirror symmetry wrt edge normal
When p = 2 + 2, the mask weights reflect the proximity to the mask origin.
The operator becomes less sensitive to edge orientation.
15
and similar for Gy
16
antisymmetry of edge profile
3. No response to flat regions:
r,c Gx (r, c)
follows from the antisymmetry
r,c Gy (r, c)
The Canny edge detector
= 0.
4. Normalised response to ideal step edge of unit height: For such edge, the
output value should be 1.
Using these constraints, the above family of gradient masks can be derived from
a general unconstrained 3 3 mask: 9 free parameters reduce to 1.
The most frequently used are the Prewitt and the Sobel operators whose
X-masks are as follows:
Prewitt
Sobel
1 0 1
1 0 1
1
1
1 0 1
2 0 2
3
4
1 0 1
1 0 1
The Y -masks are obtained by 90 rotation of the X-masks.
The Prewitt operator is the simplest and the fastest.
The Canny edge detector is optimal for noisy step edge under the following
assumptions:
The edge filter is linear.
The image noise is additive, white (uncorrelated) and Gaussian.
The optimality criterion used by Canny combines
good detection and
good localisation
To satisfy the single response criterion, two post-processing (edge localisation)
operations are used:
17
18
A practical approximation of the Canny filter
An efficient implementation of the Canny filter
The original optimal edge filter is quite complicated. A simple practical

approximation is as follows:
1. Apply Gaussian filter obtaining smoothed image g(x, y) = f (x, y) wG(x, y; )
The Gaussian parameter determines the size of the edge filter
2. Apply gradient operator g(x, y) and calculate edge magnitude and
orientation.
The scale parameter is selected based on
the desired level of detail: fine edges vs global edges;
An efficient implementation uses

the commutativity and associativity of linear filters:

f (x, y) wG(x, y) = wG(x, y) f (x, y) = wG(x, y) f (x, y)
and the separability of the Gaussian filter:
wG(x, y) = wG(x) wG(y).
As a result, the filter is implemented as a sequence of convolutions with 1D
masks.
the noise level;

the localisation-detection trade off: see template matching.
19
20
Edge localisation
Input: edge magnitude M (x, y) and edge orientation (x, y) in each pixel of
the image.
Due to the multiple response, edge magnitude M (x, y) may contain wide ridges
around the local maxima.
Output: Binary edge map, with 1s indicating edges, 0s indicating no edges.
Non-maxima suppression removes the non-maxima pixels preserving the

connectivity of the contours.
Localisation selects those maxima of M (x, y) that correspond to true edge pixels.
Can be applied after any edge filter that computes a measure of edge strength
and provides edge orientation.
Gradient: Canny, Prewitt
Non-gradient: For example, Mero and Vassy
Algorithm 1: Non-maxima suppression

1. From each position (x, y), step in the two directions perpendicular to edge
orientation (x, y).
2. Denote the inital pixel (x, y) by C, the two neighbouring pixels in the
perpendicular directions by A and B.
Includes the following operations:

Non-maxima suppression to remove phantom edges and, if possible, obtain
1-pixel wide contours
Hysteresis thresholding to remove noisy maxima without breaking the
contours
21
3. If the M (A) > M (C) or M (B) > M (C), discard the pixel (x, y) by setting
M (x, y) = 0.
22
normal
direction
M(C)>M(A)
pixel A
pixel B
The output of the non-maxima suppression still contains noisy local maxima.
M(C)>M(B)
pixel C
Contrast (edge strength) may be different in different points of the contour.
Illustration to the non-maxima suppression. Pixels A and B are deleted because

M (C) > M (A) and M (C) > M (B). Pixel C is not deleted.
Careful thresholding of M (x, y) is needed to remove these weak edges while

preserving the connectivity of the contours.
Hysteresis thresholding receives the output of the non-maxima suppression,
MN M S (x, y).
The algorithm uses 2 thresholds, Thigh and Tlow .
edge magnitude
intensity profile (resized)
result of NMS
Thinning wide contours in edge magnitude images by non-maxima suppression.

The intensity profile along the indicated line is shown resized for better visibility.
23
A pixel (x, y) is called strong if MN M S (x, y) > Thigh.

A pixel (x, y) is called weak if MN M S (x, y) Tlow .
All other pixels are called candidate pixels.
24
C4
C3
Algorithm 2: Hysteresis thresholding
C2
1. In each position of (x, y), discard the pixel (x, y) if it is weak; output the pixel
if it is strong.
2. If the pixel is a candidate, follow the chain of connected local maxima in both
directions along the edge, as long as MN M S > Tlow .
weak edge
strong edge
C1
candidate edge
Illustration to the hysteresis thresholding. The candidate edges C1 and C2 are

output, the candidate edges C3 and C4 are not.
3. If the starting candidate pixel (x, y) is connected to a strong pixel, output

this candidate pixel; otherwise, do not output the candidate pixel.
original image
edge magnitude
5, 20
20, 40
Examples of edge localisation with different hysteresis thresholds.

25
26
Implementation of the zero crossing filter: Gaussian smoothing followed by
Laplacian filtering.
Zero-crossing edge detector
Steep edge
Using commutativity and associativity of linear filters and rotation symmetry of

Gaussian filter, we obtain the convolution mask of the zero-crossing operator,
called Laplacian-of-Gaussian (LoG):
Blurred edge
f(x)
+
df
__
dx
wZ (r) = C
+
0
Double edge
___f
_d
dx 2
+
0
Zero crossing
Left: Principles of zero-crossing edge detector.

Right: Simple masks for detection of zero-crossings.
27

2
r2
r
1 exp
2
2 2
C: normalisation constant
r2 = x2 + y 2: square distance from centre of mask
is scale parameter: the smaller the the finer the edges obtained
Discrete zero-crossing mask: Threshold wZ (r) at a small level.
Larger mask obtained for larger : For example, when = 4 the size of the
mask is about 40 pixels.
28
Another, more efficient but approximate, implementation of the zero-crossing

filter is the difference of two separable Gaussian filters, called DoG.
Localising the zero-crossings corresponds to edge localisation in gradient-type
edge detectors.
For more precise localisation, one can locally approximate output of LoG filter
by facets (flat patches), then find zero-crossings analytically.
=5
= 10
LoG absolute
LoG zero
DoG zero
Shape of the Laplacian-of-Gaussian (LoG) filter for different .
Examples of edge detection by 15 15 LoG and DoG operators. LoG absolute is

absolute value of filter output: dark lines are contours. LoG zero was obtained
with removal of weak edges, DoG zero without removal.
29
30
= 15
= 20
Properties of zero crossing edge detector
The continuous zero-crossing edge detector always gives closed contours.

Reason: Cross-sections of continuous surface at zero level
In principle, this may help in contour following
In practice, many spurious loops appear
Prewitt 3 3
Mero-Vassy 7 7
LoG 21 21
Canny 3 3
Canny 7 7
Canny 25 25
Controlled operator size Natural edge hierarchy within a scale-space.

Edges may only merge or disappear at rougher scales (larger )
This tree-like data structure facilitates structural analysis of image
Does not provide edge orientation.
Non-maxima suppression and hysteresis threshoding are not applicable
Other ways of post-processing to remove unrealiable edges can be used
31
Examples of edge detection by different operators. The LoG result was obtained
with removal of weak edges. Mero-Vassy is a non-gradient edge detector.
32
Summary of edge detection

3 3 gradient operators (Prewitt, Sobel) are simple and fast. Used when
Fine edges are only needed
Noise level is low
By varying the parameter, the Canny operator can be used
to detect fine as well as rough edges
at different noise levels
All gradient operators
provide edge orientation;
need localisation: non-maxima suppression, hysteresis threshoding.
The zero-crossing edge detector
is supported by neurophysiological experiments;
was popular in the 1980s ;
today, less frequently used in practice.
33

Lecture 6: Edge Detection: Dmitrij Csetverikov

Uploaded by

Copyright:

Available Formats

Lecture 6: Edge Detection: Dmitrij Csetverikov

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lecture 6: Edge Detection: Dmitrij Csetverikov

Uploaded by

Copyright:

Available Formats

Faculty of Informatics

Lecture 6: Edge Detection

Basic Algorithms for Digital Image Analysis:

Criteria for good edge filters

Local image features

Image edges do not necessarily coincide with physical edges

Basic image features.

Image edges are intensity discontinuities

Line: narrow, elongated image region of approximately constant width and

ideal step edge

Blob: compact image region of approximately constant intensity

Principles of edge detection

Steps of edge detection.

Example of edge detection by 3 3 Prewitt operator.

Tasks of edge localisation (post-processing):

Edge normal, edge direction and edge orientation.

suppress regions of constant intensity

Criteria for good edge filters

A signal and its first and second derivatives.

1. No response to flat regions Sum of mask values is zero:

3. Good detection: Minimise the probabilities of

Edges are located at

isotropic edge filter

anisotropic edge filter

Illustration to the isotropy criterion.

The same piece of contours is detected in window W1 and window W2.

Gradient edge filters

The meaning of the gradient vector

Intensity surface of an edge and its gradient.

Simple 3 3 gradient masks

Constraining the gradient masks

In discrete images, partial derivatives are approximated by finite differences.

Different values of the parameter p result in different versions of the masks:

1. Mirror symetry with respect to (wrt) the edge normal:

and similar for Gy

requried for precise localisation of edges

and similar for Gy

antisymmetry of edge profile

3. No response to flat regions:

follows from the antisymmetry

The Canny edge detector

A practical approximation of the Canny filter

An efficient implementation of the Canny filter

The original optimal edge filter is quite complicated. A simple practical

An efficient implementation uses

the noise level;

Output: Binary edge map, with 1s indicating edges, 0s indicating no edges.

Non-maxima suppression removes the non-maxima pixels preserving the

Algorithm 1: Non-maxima suppression

Includes the following operations:

Contrast (edge strength) may be different in different points of the contour.

Illustration to the non-maxima suppression. Pixels A and B are deleted because

Careful thresholding of M (x, y) is needed to remove these weak edges while

intensity profile (resized)

Thinning wide contours in edge magnitude images by non-maxima suppression.

A pixel (x, y) is called strong if MN M S (x, y) > Thigh.

Algorithm 2: Hysteresis thresholding

Illustration to the hysteresis thresholding. The candidate edges C1 and C2 are