Edge detection

Image Processing

1. Edge detection
(Trucco, Chapt 4 AND Jain et al., Chapt 5)
ƒDeŒnition of edges
-Edges are signiŒcant local changes of intensity in an image.
-Edges typically occur on the boundary between twodifferent regions in an image.
ƒGoal of edge detection
-Produce a line drawing of a scene from an image of that scene.
-Important features can be extracted from the edges of an image (e.g., corners,
lines, curves).
-These features are used by higher-levelcomputer vision algorithms (e.g., recogni-
tion).

2. -2-
ƒWhat causes intensity changes?
-Various physical events cause intensity changes.
-Geometric events
*object boundary (discontinuity in depth and/or surface color and texture)
*surface boundary (discontinuity in surface orientation and/or surface color
and texture)
-Non-geometric events
*specularity (direct reection of light, such as a mirror)
*shadows (from other objects or from the same object)
*inter-reections
ƒEdge descriptors
Edge normal:unit vector in the direction of maximum intensity change.
Edge direction:unit vector to perpendicular to the edge normal.
Edge position or center:the image position at which the edge is located.
Edge strength:related to the local image contrast along the normal.

3. -3-
ƒModeling intensity changes
-Edges can be modeled according to their intensity proŒles.
Step edge:the image intensity abruptly changes from one value to one side of the
discontinuity to a different value on the opposite side.
Ramp edge:astep edge where the intensity change is not instantaneous but occur
overaŒnite distance.
Ridge edge:the image intensity abruptly changes value but then returns to the
starting value within some short distance (generated usually by lines).

4. -4-
Roof edge:aridge edge where the intensity change is not instantaneous but occur
overaŒnite distance (generated usually by the intersection of surfaces).
ƒThe four steps of edge detection
(1) Smoothing:suppress as much noise as possible, without destroying the true
edges.
(2) Enhancement:apply a Œlter to enhance the quality of the edges in the image
(sharpening).
(3) Detection:determine which edge pixels should be discarded as noise and
which should be retained (usually,thresholding provides the criterion used for
detection).
(4) Localization:determine the exact location of an edge (sub-pixelresolution
might be required for some applications, that is, estimate the location of an edge to
better than the spacing between pixels). Edge thinning and linking are usually
required in this step.

5. -5-
ƒEdge detection using derivatives
-Calculus describes changes of continuous functions usingderivatives.
-Animage is a 2D function, so operators describing edges are expressed using
partial derivatives.
-Points which lie on an edge can be detected by:
(1) detecting local maxima or minima of the Œrst derivative
(2) detecting the zero-crossing of the second derivative

6. -6-
ƒDifferencing 1D signals(see also Trucco, Appendix A.2)
-Tocompute the derivative ofasignal, we approximate the derivative byŒnite dif-
ferences:
Computing the 1st derivative:
f¢(x)=
h->0
lim
f(x+h)-f(x)
h
»f(x+1)-f(x)(h=1)
mask: [-11]
-Examples using the edge models and the mask[-101 ](centeredaboutx):

7. -7-
Computing the 2nd derivative:
f¢¢(x)=
h->0
lim
f¢(x+h)-f¢(x)
h
»f¢(x+1)-f¢(x)=
f(x+2)-2f(x+1)+f(x)(h=1)
-This approximation iscenteredaboutx+1; by replacingx+1byxwe obtain:
f¢¢(x)»f(x+1)-2f(x)+f(x-1)
mask: [1-21]
00 0010000
1010101010
20202020 f(x)
-1000 010 0
f'(x)
f''(x)
0
= f(x+1) - f(x)
= f(x-1)-2f(x)+f(x+1)
zero-crossing
(approximates f'() at x+1/2)
(approximates f''() at x)
-Examples using the edge models:

8. -8-
Edge detection using the gradient
ƒDeŒnition of the gradient
-The gradient is a vector which has certain magnitude and direction:
Ñf=
æ
ç
ç
è
¶f
¶x
¶f
¶y
ö
÷
÷
ø
magn(Ñf)=
Ö` ````
(
¶f
¶x
)
2
+(
¶f
¶y
)
2
=Ö` ``````
M
x
2
+M
y
2
dir(Ñf)=tan
-1
(M
y/M
x)
-Tosav ecomputations, the magnitude of gradient is usually approxi-
mated by:
magn(Ñf)»|M
x|+|M
y|
ƒProperties of the gradient
-The magnitude of gradient provides information about the strength of the edge.
-The direction of gradient is always perpendicular to the direction of the edge (the
edge direction is rotated with respect to the gradient direction by -90 degrees).

9. -9-
ƒEstimating the gradient with Œnite differences
¶f
¶x
=
h->0
lim
f(x+h,y)-f(x,y)
h
¶f
¶y
=
h->0
lim
f(x,y+h)-f(x,y)
h
-The gradient can be approximated byŒnite differences:
¶f
¶x
=
f(x+h
x,y)-f(x,y)
h
y
=f(x+1,y)-f(x,y), (h
x=1)
¶f
¶y
=
f(x,y+h
y)-f(x,y)
h
y
=f(x,y+1)-f(x,y), (h
y=1)
-Using pixel-coordinate notation (remember:jcorresponds to thexdirection and
ito the negativeydirection):
x
y
y-h
y+h
x+hx-h
¶f
¶x
=f(i,j+1)-f(i,j)
¶f
¶y
=f(i-1,j)-f(i,j)or
¶f
¶y
=f(i,j)-f(i+1,j)

10. -10-
Example
Suppose we want to approximate the gradient magnitude atz
5
Z1 Z2 Z3
Z4 Z5 Z6
Z7 Z8 Z9
¶I
¶x
=z
6-z
5,
¶I
¶y
=z
5-z
8
magn(ÑI)=Ö` `````````````(z
6-z
5)
2
+(z
5-z
8)
2
-Wecan implement
¶I
¶x
and
¶I
¶y
using the following masks:
-1 1
1
-1
(note:M
xis the approximation at (i,j+1/2) andM
yis the approximation at
(i+1/2,j))

11. -11-
ƒThe Roberts edge detector
¶f
¶x
=f(i,j)-f(i+1,j+1)
¶f
¶y
=f(i+1,j)-f(i,j+1)
-This approximation can be implemented by the following masks:
M
x=
é
ê
ë
1
0
0
-1
ù
ú
û
M
y=
é
ê
ë
0
1
-1
0
ù
ú
û
(note:M
xandM
yare is approximations at (i+1/2,j+1/2))
ƒThe Prewitt edge detector
-Consider the arrangement of pixels about the pixel (i,j):
a
0
a
7
a
6
a
1
[i,j]
a
5
a
2
a
3
a
4
-The partial derivativescan be computed by:
M
x=(a
2+ca
3+a
4)-(a
0+ca
7+a
6)
M
y=(a
6+ca
5+a
4)-(a
0+ca
1+a
2)
-The constantcimplies the emphasis giventopixels closer to the center of the
mask.
-Settingc=1, we get the Prewitt operator:
M
x=
é
ê
ê
ë
-1
-1
-1
0
0
0
1
1
1
ù
ú
ú
û
M
y=
é
ê
ê
ë
-1
0
1
-1
0
1
-1
0
1
ù
ú
ú
û
(note:M
xandM
yare approximations at (i,j))

12. -12-
ƒThe Sobel edge detector
-Settingc=2, we get the Sobel operator:
M
x=
é
ê
ê
ë
-1
-2
-1
0
0
0
1
2
1
ù
ú
ú
û
M
y=
é
ê
ê
ë
-1
0
1
-2
0
2
-1
0
1
ù
ú
ú
û
(note:M
xandM
yare approximations at (i,j))
ƒMain steps in edge detection using masks
(1) Smooth the input image (^f(x,y)=f(x,y)*G(x,y))
(2)^f
x=^f(x,y)*M
x(x,y)
(3)^f
y=^f(x,y)*M
y(x,y)
(4)magn(x,y)=|^f
x|+|^f
y|
(5)dir(x,y)=tan
-1
(^f
y/^f
x)
(6) Ifmagn(x,y)>T,then possible edge point
(an example using the Prewitt edge detector - don'tdivide by 2)

13. -13-
(with noise Œltering)

14. -14-
(without noise Œltering)

15. -15-
ƒIsotropic property of gradient magnitude
-The magnitude of gradient is anisotropicaloperator (it detects edges in any
direction !!)

16. -16-
ƒSome practical issues
-The differential masks act as high-pass Œlters which tend to amplify noise.
-Toreduce the effects of noise, the image needs to be smoothed Œrst with a low-
pass Œlter.
(1) The noise suppression-localization tradeoff: a larger Œlter reduces noise, but
worsens localization (i.e., it adds uncertainty to the location of the edge) and vice
versa.
-(2) Howshould we choose the threshold?

17. -17-
-(3) Edge thinning and linking are required to obtain good contours.
ƒCriteria for optimal edge detection
(1) Good detection:the optimal detector must minimize the probability of false
positives(detecting spurious edges caused by noise), as well as that of false neg-
atives(missing real edges).
(2) Good localization:the edges detected must be as close as possible to the true
edges.
Single response constraint:the detector must return one point only for each true
edge point; that is, minimize the number of local maxima around the true edge
(created by noise).

18. -18-
The Canny edge detector
-This is probably the most widely used edge detector in computer vision.
-Cannyhas shown that the Œrst derivative ofthe Gaussian closely approximates
the operator that optimizes the product ofsignal-to-noiseratio and localization.
-His analysis is based on "step-edges" corrupted by "additive Gaussian noise".
Algorithm
1. Computef
xandf
y
f
x=
¶
¶x
(f*G)=f*
¶
¶x
G=f*G
x
f
y=
¶
¶y
(f*G)=f*
¶
¶y
G=f*G
y
G(x,y)isthe Gaussian function
G
x(x,y)isthe derivate ofG(x,y)with respect tox:G
x(x,y)=
-x

2
G(x,y)
G
y(x,y)isthe derivate ofG(x,y)with respect toy:G
y(x,y)=
-y

2
G(x,y)
2. Compute the gradient magnitude
magn(i,j)=Ö` ````
f
x
2
+f
y
2
3. Apply non-maxima suppression.
4. Apply hysteresis thresholding/edge linking.

19. -19-
ƒNon-maxima suppression
-ToŒnd the edge points, we need to Œnd the local maxima of the gradient magni-
tude.
-Broad ridges must be thinned so that only the magnitudes at the points of greatest
local change remain.
-All values along the direction of the gradient that are not peak values of a ridge
are suppressed.
665 7545
44335 52
10 12 16 14 10 11 13
direction of
gradient
magn(i1,j1)
magn(i,j)
magn(i2,j2)
Algorithm
Foreach pixel (x,y) do:
ifmagn(i,j)<magn(i
1,j
1)ormagn(i,j)<magn(i
2,j
2)
thenI
N(i,j)=0
elseI
N(i,j)=magn(i,j)

20. -20-
ƒHysteresis thresholding/Edge Linking
-The output of non-maxima suppression still contains the local maxima created by
noise.
-Can we get rid of them just by using a single threshold?
*ifweset a lowthreshold, some noisy maxima will be accepted too.
*ifweset a high threshold, true maxima might be missed (the value of true
maxima will uctuate above and belowthe threshold, fragmenting the edge).
-Amore effective scheme is to use twothresholds:
*alow thresholdt
l
*ahigh thresholdt
h
*usually,t
h»2t
l
Algorithm
1. Produce twothresholded imagesI
1(i,j)andI
2(i,j).
(note: sinceI
2(i,j)was formed with a high threshold, it will contain fewer false
edges but there might be gaps in the contours)
2. Link the edges inI
2(i,j)into contours
2.1 Look inI
1(i,j)when a gap is found.
2.2 By examining the 8 neighbors inI
1(i,j), gather edge points fromI
1(i,j)
until the gap has been bridged to an edge inI
2(i,j).
-The algorithm performs edge linking as a by-product of double-thresholding !!

21. -21-
(left:Sobel, middle: thresh=35, right: thersh=50)
(Canny-left:
=1, middle:
=2, right:
=3)
(Canny-7x7 Gaussian, more details)

22. -22-
(Canny-31x31 Gaussian, less details)

23. -23-
Edge detection using the second derivative
-Edge points can be detected by Œnding the zero-crossings of the second
derivative.
-There are twooperators in 2D that correspond to the second derivative:
*Laplacian
*Second directional derivative
ƒThe Laplacian
Ñ
2
f=
¶
2
f
¶x
2
+
¶
2
f
¶y
2
-ApproximatingÑ
2
f:
¶
2
f
¶x
2
=f(i,j+1)-2f(i,j)+f(i,j-1)
¶
2
f
¶y
2
=f(i+1,j)-2f(i,j)+f(i-1,j)
Ñ
2
f=-4f(i,j)+f(i,j+1)+f(i,j-1)+f(i+1,j)+f(i-1,j)

24. -24-
Example:
Z1 Z2 Z3
Z4 Z5 Z6
Z7 Z8 Z9 Ñ
2
f=-4z
5+(z
2+z
4+z
6+z
8)
-The Laplacian can be implemented using the mask shown below:
0 0
1 1
0 1 0
-4
1
Example:

25. -25-
ƒProperties of the Laplacian
-Itisanisotropic operator.
-Itischeaper to implement (one mask only).
-Itdoes not provide information about edge direction.
-Itismore sensitive tonoise (differentiates twice).
ƒThe Laplacian-of-Gaussian (LOG)
-Toreduce the noise effect, the image is Œrst smoothed with a low-pass Œlter.
-Inthe case of the LOG, the low-pass Œlter is chosen to be a Gaussian.
G(x,y)=e
-
x
2
+y
2
2

2
(
determines the degree of smoothing, mask size increases with )
-Itcan be shown that:
Ñ
2
[f(x,y)*G(x,y)] =Ñ
2
G(x,y)*f(x,y)
Ñ
2
G(x,y)=(
r
2
-

2

4
)e
-r
2
/2

2
,(r
2
=x
2
+y
2
)

26. -26-

27. -27-
ƒGradient vs LOG: a comparison
-Gradient works well when the image contains sharp intensity transitions and low
noise
-Zero-crossings of LOG offer better localization, especially when the edges are
not very sharp

28. -28-
ƒThe second directional derivative
-This is the second derivative computed in the direction of the gradient.
¶
2
¶n
2
=
f
2
xf
xx+2f
xf
yf
xy+f
2
yf
yy
f
2
xf
2
y
ƒMultiscale processing (scale space)
-Aserious practical problem with anyedge detector is the matter of choosing the
scaleof smoothing (e.g.,the value of
using a Gaussian).
-For manyapplications, it is desirable to be able to process an image at multiple
scales.
-Wedetermine which edges are most signiŒcant in terms of the range of scales
overwhich theyare observed to occur.

29. -29-
(Cannyedges at multiple scales of smoothing, =0.5, 1, 2, 4, 8, 16)