5-1 Chapter 5 – Edge Detection
Chapter 5
Edge Detection
Prof. Fei-Fei Li, Stanford University
Department of Mechatronics
5-2 Chapter 5 – Edge Detection
Contents
Edge detection
• Canny edge detector
Department of Mechatronics
5-3 Chapter 5 – Edge Detection
(A) Cave painting at Chauvet, France, about 30,000 B.C.;
(B) Aerial photograph of the picture of a monkey as part of the Nazca Lines geoplyphs, Peru, about 700
– 200 B.C.;
(C) Shen Zhou (1427-1509 A.D.): Poet on a mountain top, ink on paper, China;
(D) Line drawing by 7‐year old I. Lleras (2010 A.D.).
Department of Mechatronics
5-4 Chapter 5 – Edge Detection
We know edges are special from human
(mammalian) vision studies
Department of Mechatronics
5-5 Chapter 5 – Edge Detection
Walther, Chai, Caddigan, Beck & Fei-‐Fei, PNAS, 2011
Department of Mechatronics
5-6 Chapter 5 – Edge Detection
Edge detection
• Goal: Identify sudden changes
(discontinuities) in an image
– Intuitively, most semantic and shape
information from the image can be
encoded in the edges
– More compact than pixels
• Ideal: artist’s line drawing (but
artist is also using object ‐ level
knowledge)
Source: D. Lowe
Department of Mechatronics
5-7 Chapter 5 – Edge Detection
Origin of Edges
surface normal discontinuity
depth discontinuity surface
color discontinuity
illumination discontinuity
• Edges are caused by a variety of factors
Department of Mechatronics
5-8 Chapter 5 – Edge Detection
Characterizing edges
• An edge is a place of rapid change in the image intensity
function
intensity function
image (along horizontal scanline) first derivative
edges correspond to
extrema of derivative
Department of Mechatronics
5-9 Chapter 5 – Edge Detection
Image gradient
• The gradient of an image:
The gradient points in the direction of most rapid increase in intensity. The
gradient direction is given by
• How does this relate to the direction of the edge?
The edge strength is given by the gradient magnitude
Source: Steve
Seitz
Department of Mechatronics
5-10 Chapter 5 – Edge Detection
Differentiation and convolution
• Recall, for 2D function, • We could approximate this
f(x,y): as
∂f f ( x + ε , y ) f ( x, y ) ∂f f ( xn +1 , y ) − f ( xn , y )
lim − ≈
∂x ε →0
ε ε ∂x ∆x
• This is linear and shift • (which is obviously a
invariant, so must be the result convolution)
of a convolution.
1 -1 -1 1
Source: D. Forsyth, D. Lowe
Department of Mechatronics
5-11 Chapter 5 – Edge Detection
Finite difference filters
• Other approximations of derivative filters
−𝟏𝟏 𝟎𝟎 𝟏𝟏 −𝟏𝟏 −𝟏𝟏 −𝟏𝟏
Prewitt: 𝑴𝑴𝒙𝒙 = −𝟏𝟏 𝟎𝟎 𝟏𝟏 𝑴𝑴𝒚𝒚 = 𝟎𝟎 𝟎𝟎 𝟎𝟎
−𝟏𝟏 𝟎𝟎 𝟏𝟏 𝟏𝟏 𝟏𝟏 𝟏𝟏
−𝟏𝟏 𝟎𝟎 𝟏𝟏 −𝟏𝟏 −𝟐𝟐 −𝟏𝟏
Sobel: 𝑴𝑴𝒙𝒙 = −𝟐𝟐 𝟎𝟎 𝟐𝟐 𝑴𝑴𝒚𝒚 = 𝟎𝟎 𝟎𝟎 𝟎𝟎
−𝟏𝟏 𝟎𝟎 𝟏𝟏 𝟏𝟏 𝟐𝟐 𝟏𝟏
𝟏𝟏 𝟎𝟎 𝟎𝟎 𝟏𝟏
Roberts: 𝑴𝑴𝒙𝒙 =
𝟎𝟎 −𝟏𝟏
𝑴𝑴𝒚𝒚 =
−𝟏𝟏 𝟎𝟎
Department of Mechatronics
5-12 Chapter 5 – Edge Detection
Finite differences: example
Which one is the gradient in the x-direction? How about y‐direction?
Department of Mechatronics
14
5-13 Chapter 5 – Edge Detection
Effects of noise
• Consider a single row or column of the image
– Plotting intensity as a function of position gives a signal
Where is the edge?
Department of Mechatronics
5-14 Chapter 5 – Edge Detection
Effects of noise
• Finite difference filters respond strongly to noise
– Image noise results in pixels that look very different
from their neighbors
– Generally, the larger the noise the stronger the response
• What is to be done?
Department of Mechatronics
5-15 Chapter 5 – Edge Detection
Effects of noise
• Finite difference filters respond strongly to noise
– Image noise results in pixels that look very
different from their neighbors
– Generally, the larger the noise the stronger the response
• What is to be done?
– Smoothing the image should help, by forcing pixels
different to their neighbors (=noise pixels?) to look more
like neighbors
Department of Mechatronics
5-16 Chapter 5 – Edge Detection
Solution: smooth first
f*g
d
( f *g)
dx
d
• To find edges, look for peaks in ( f *g)
dx Source: S. Seitz
Department of Mechatronics
5-17 Chapter 5 – Edge Detection
Derivative theorem of convolution
• Differentiation is convolution, and convolution is associative:
d d
( f *g) = f * g
dx dx
• This saves us one operation:
𝒅𝒅
𝒇𝒇 ∗ 𝒈𝒈
𝒅𝒅𝒅𝒅 Source: S. Seitz
Department of Mechatronics
19
5-18 Chapter 5 – Edge Detection
Derivative of Gaussian filter
* [1 -1] =
• 1D Gaussian filter:
𝟏𝟏 𝒙𝒙𝟐𝟐 𝟏𝟏 𝒚𝒚𝟐𝟐
𝒈𝒈𝝈𝝈 𝒙𝒙 = 𝒆𝒆𝒆𝒆𝒆𝒆 − 𝟐𝟐 𝒈𝒈𝝈𝝈 𝒚𝒚 = 𝒆𝒆𝒆𝒆𝒆𝒆 − 𝟐𝟐
𝝈𝝈 𝟐𝟐𝟐𝟐 𝟐𝟐𝝈𝝈 𝝈𝝈 𝟐𝟐𝟐𝟐 𝟐𝟐𝝈𝝈
• Is this filter separable?
Department of Mechatronics
5-19 Chapter 5 – Edge Detection
Derivative of Gaussian filter
x-direction y-direction
• Which one finds horizontal/vertical edges?
Department of Mechatronics
5-20 Chapter 5 – Edge Detection
Tradeoff between smoothing and localization
1 pixel 3 pixels 7 pixels
• Smoothed derivative removes noise, but blurs edge.
Also finds edges at different “scales”.
Department of Mechatronics
5-21 Chapter 5 – Edge Detection
Implementation issues
• The gradient magnitude is large along a thick “trail” or “ridge,”
so how do we identify the actual edge points?
• How do we link the edge points to form curves?
Department of Mechatronics
5-22 Chapter 5 – Edge Detection
Designing an edge detector
• Criteria for an “optimal” edge detector:
– Good detection: the optimal detector must minimize the
probability of false positives (detecting spurious edges
caused by noise), as well as that of false negatives
(missing real edges)
– Good localization: the edges detected must be as close as
possible to the true edges
– Single response: the detector must return one point only for
each true edge point; that is, minimize the number of local
maxima around the true edge
Department of Mechatronics
5-23 Chapter 5 – Edge Detection
Designing an edge detector
• Criteria for an “optimal” edge detector:
– Good detection
– Good localization
– Single response
Department of Mechatronics
5-24 Chapter 5 – Edge Detection
Canny edge detector
• This is probably the most widely used edge detector in
computer vision
• Theoretical model: step-edges corrupted by additive Gaussian
noise
• Canny has shown that the first derivative of the Gaussian
closely approximates the operator that optimizes the product
of signal-to‐noise ratio and localization
J. Canny, A Computational Approach To Edge Detection, IEEE Trans. Papern
Analysis and Machine Intelligence, 8:679-‐714, 1986.
Department of Mechatronics
5-25 Chapter 5 – Edge Detection
Canny edge detector
1. Filter image with derivative of Gaussian
2. Find magnitude and orientation of gradient
3. Non-maximum suppression:
– Thin multi-pixel wide “ridges” down to single pixel width
4. Linking and thresholding (hysteresis):
– Define two thresholds: low and high
– Use the high threshold to start edge curves and the low
threshold to continue them
• MATLAB: edge(image, ‘canny’)
• EmguCV: Image<Gray, Byte> cannyEdges =
Binary_Image.Canny(cannyThreshold,
cannyThresholdLinking);
Department of Mechatronics
5-26 Chapter 5 – Edge Detection
Example
• Original image (Lena)
Department of Mechatronics
5-27 Chapter 5 – Edge Detection
Example
Norm of the gradient
Department of Mechatronics
5-28 Chapter 5 – Edge Detection
Example
Thresholding
Department of Mechatronics
5-29 Chapter 5 – Edge Detection
Example
Thinning (non-‐maximum suppression)
Department of Mechatronics
5-30 Chapter 5 – Edge Detection
Non-Maximum Suppression
At q, we have a maximum
intensity if the value is larger
than those at both p and r.
Interpolate to get these
values.
Source: D. Forsyth
Department of Mechatronics
5-31 Chapter 5 – Edge Detection
Edge linking
Assume the marked point is
an edge point. Then we
construct the tangent to the
edge curve (which is normal
to the gradient at that point)
and use this to predict the
next points (here either r or
s).
Department of Mechatronics
5-32 Chapter 5 – Edge Detection
Hysteresis thresholding
• Check that maximum value of gradient value is
sufficiently large
– Drop-outs? use hysteresis
• Use a high threshold to start edge curves and a low
threshold to continue them.
Department of Mechatronics
5-33 Chapter 5 – Edge Detection
Hysteresis thresholding
original
image
high threshold low threshold hysteresis threshold
(strong edges) (weak edges)
Department of Mechatronics
5-34 Chapter 5 – Edge Detection
Effect of σ (Gaussian kernel spread/size)
original Canny with Canny with
The choice of σ depends on desired behavior
• Large σ detects large scale edges
• Small σ detects fine features
Department of Mechatronics
5-35 Chapter 5 – Edge Detection
Edge detection is just the beginning…
image human segmentation gradient magnitude
• Berkeley segmentation database:
hp p ://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/segbench/
Department of Mechatronics
