Edge detection

◼ Gradient-based edge operators

⚫ Prewitt
⚫ Sobel
⚫ Roberts
◼ Laplacian zero-crossings
◼ Canny edge detector
◼ Hough transform for detection of straight lines
◼ Circle Hough Transform

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 1
 Gradient-based edge detection
◼ Idea (continous-space): local gradient magnitude indicates edge strength
  f (x, y )   f (x, y )
2 2

(
grad f (x, y ) = ) 
 x
 +
   y



◼ Digital image: difference ( -1 1 )

use finite differences
to approximate
central difference ( -1 0  1 )
derivatives  −1 0 1 
Prewitt  −1 0 1 
 −1 0 1 
◼ Edge templates
 −1 0 1 
Sobel  −2 0 2 
 −1 0 1 

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 2
 Practical edge detectors
◼ Edges can have any orientation
◼ Typical edge detection scheme uses K=2 edge templates
◼ Some use K>2

e  x, y 
1 
Combination,
e.g., edge
s x, y  e  x, y   x, y  2
2  e k  
magnitude
k
M  x, y 
or

 Max k ek  x, y 

e  x, y    x, y 
K   (edge orientation)

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 3
 Gradient filters (K=2)

 0 0 0   0 −1 0 
Central   0 1   1 0 
 −1 0 1   0 0 0  Roberts    
Difference      −1 0   0 −1 
 0 0 0   0 1 0 

 −1 0 1   −1 −1 −1 
  
Prewitt  −1 0 1   0 0 0 
   
 −1 0 1   1 1 1 

 −1 0 1   −1 −2 −1 
   
Sobel  −2 0  2   0 0 0 
   
 −1 0 1   1 2 1 

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 4
 Kirsch operator (K=8)
 +5 +5 +5  +5  +5  −3 
  −3 +5  −3 −3  −3 −3
Kirsch  −3 0 −3  −3 0 +5  −3 0 +5  −3 0 +5 
    
 −3 −3 −3  −3 −3 −3  −3 −3 +5  −3 +5 +5 
 −3 −3 −3  −3  −3  −3 
  −3 −3  +5 −3  +5 +5
 −3 0 −3  +5 0 −3  +5 0 −3  +5 0 −3 
    
 +5 +5 +5  +5 +5 −3  +5 −3 −3  −3 −3 −3 

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 5
 Prewitt operator example

Magnitude of
image filtered with
 −1 0 1 

 −1 0 1 
 
 −1 0 1 
(log display)

Magnitude of
Original image filtered with
1024x710  −1 −1 −1 
 
 0 0 0 
 
 1 1 1 
(log display)

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 6
 Prewitt operator example (cont.)

Sum of squared threshold = 900 threshold = 4500 threshold = 7200

horizontal and
vertical gradients
(log display)

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 7
 Sobel operator example

Sum of squared threshold = 1600 threshold = 8000 threshold = 12800

horizontal and
vertical gradients
(log display)

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 8
 Roberts operator example

Magnitude of
image filtered with
 1 0 
 
 0 −1 
 
(log display)

Magnitude of
Original image filtered with
1024x710  0 1 
 
 −1 0 
 
(log display)

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 9
 Roberts operator example (cont.)

Sum of squared threshold = 100 threshold = 500 threshold = 800

diagonal gradients
(log display)

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 10
 Edge orientation
Central
Gradient scatter plot
Difference
 0 0 0 
 
 −1 0  1 

y-component
 
 0 0 0 
 0 −1 0 

 0 0  0 
 
 0 1 0 

x-component

Roberts
 
 0 1 

y-component
 −1 0 
 
 
 1 0 
 0 −1 
 

x-component

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 11
 Edge orientation
Prewitt Gradient scatter plot
 −1 0 1 

 −1 0 1 

1 

y-component
 −1 0 
 −1 −1 −1 

 0 0 0 
 
 1 1 1 

x-component

Sobel
 
 −1
0 1 
 −2 0 2 

y-component
 
 −1 0 1 

 −1 −2 −1 
 0 0 0 
 
 1 2 1 

x-component

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 12
 Edge orientation
Gradient scatter plot

y-component
5x5 “consistent”
gradient operator
[Ando, 2000]

x-component

 -0.0604 -0.1632 0 0.1632 0.0604 

 -0.4286 -1.1335 0 1.1335 0.4286 
 
 -0.7448 -1.9612 0 1.9612 0.7448 
 -0.4286 -1.1335 0 1.1335 0.4286 

 -0.0604 -0.1632 0 0.1632 0.0604 
 -0.0604 -0.4286 -0.7448 -0.4286 -0.0604 
 -0.1632 -1.1335 -1.9612 -1.1335 -0.1632 
 
 0 0 0 0 0 
 0.1632 1.1335 1.9612 1.1335 0.1632 

 0.0604 0.4286 0.7448 0.4286 0.0604 

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 13
 Gradient consistency problem

Calculate this va lue

using gradient f ield

Same resu lt,

regardless of path?

Known
gray
value

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 14
 Laplacian operator
◼ Detect edges by considering second derivative

 f (x, y)=
2
2
f (x, y )+
2
f (x, y)
x 2
 y2
◼ Isotropic (rotationally invariant) operator
◼ Zero-crossings mark edge location
Detect
zero crossing

Edge profile f(x) f ’(x f”(x)

)
Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 15
 Approximations of Laplacian operator by 3x3 filter
 0  1 1 
1 0   1 
 
 
 1 −4 1  1 −8 1 
   
0   1 1 1 
 1 0 

8 15

6
10
4
|H|

|H|
5
2

0 0
2 2
0 2 0 2
0 0
-2 -2 -2 -2
y x y x

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 16
 Zero crossings of Laplacian

◼ Sensitive to very fine detail and noise ➔ blur image first

◼ Responds equally to strong and weak edges
➔ suppress zero-crossings with low gradient magnitude

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 17
 Laplacian of Gaussian
◼ Filtering of image with Gaussian and Laplacian operators can be combined into
convolution with Laplacian of Gaussian (LoG) operator

= 2
1  x +y  −
0 .0 2
x2+ y2

( )
2 2
LoG x, y = − 1− e 2 2 0

 
4
2 
2 -0 .0 2

-0 .0 4

-0 .0 6

-0 .0 8

-0.1
4
2 4
0 2
0
-2
-2
Y -4 -4 X

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 18
 Discrete approximation of Laplacian of Gaussian
= 2
0 0 1 2 2 2 1 0 0

0 2 3 5 5 5 3 2 0 200
1 3 5 3 0 3 5 3 1
150
2 5 3 -12 -23 -12 3 5 2

2 5 0 -23 -40 -23 0 5 2 100

|H|
2 5 3 -12 -23 -12 3 5 2
50
1 3 5 3 0 3 5 3 1

0 2 3 5 5 5 3 2 0 0
0 0 1 2 2 2 1 0 0 2
0 2
0
-2 -2
y x

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 19
 Zero crossings of LoG

= 2  =2 2  =4 2  =8 2

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 20
 Zero crossings of LoG – gradient-based threshold

= 2  =2 2  =4 2  =8 2

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 21
 Canny edge detector
1. Smooth image with a Gaussian filter
2. Approximate gradient magnitude and angle (use Sobel, Prewitt . . .)
f 2  2 
M x, y  f   −1 f f 
  x  y +  x, y  tan  
     y x 

3. Apply nonmaxima suppression to gradient magnitude

4. Double thresholding to detect strong and weak edge pixels
5. Reject weak edge pixels not connected with strong edge pixels

[Canny, IEEE Trans. PAMI, 1986]

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 22
 Canny nonmaxima suppression
◼ Quantize edge normal to one of four directions:
horizontal, -45o, vertical, +45o
◼ If M[x,y] is smaller than either of its neighbors in edge normal direction
➔ suppress; else keep.

[Canny, IEEE Trans. PAMI, 1986]

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 23
 Canny thresholding and suppression of weak edges
◼ Double-thresholding of gradient magnitude
Strong edge: M  x, y    high
Weak edge:  high  M  x, y    low

◼ Typical setting: high low = 2...3

◼ Region labeling of edge pixels
◼ Reject regions without strong edge pixels

[Canny, IEEE Trans. PAMI, 1986]

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 24
 Canny edge detector

= 2  =2 2  =4 2

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 25
 Hough transform
◼ Problem: fit a straight line (or curve) to a set of edge pixels
◼ Hough transform (1962): generalized template matching technique
◼ Consider detection of straight lines y = mx + c

x m

edge pixel

y
c
Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 26
 Hough transform (cont.)
◼ Subdivide (m,c) plane into discrete “bins,” initialize all bin counts by 0
◼ Draw a line in the parameter space [m,c] for each edge pixel [x,y] and increment
bin counts along line.
◼ Detect peak(s) in [m,c] plane
x m

detect peak

y
c
Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 27
 Hough transform (cont.)
◼ Alternative parameterization avoids infinite-slope problem
x 

edge pixel



−−
x cos + y sin =  2 2 
y

◼ Similar to Radon transform

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 28
 Hough transform example

100

200

300

400

500

600

700

800
200 400 600 800

Original image

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 29
 Hough transform example

100

200

300

400

500

600

700

800
200 400 600 800

Original image

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 30
 Hough transform example

100

200

300

400

500

600

700

800
200 400 600 800

Original image

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 31
 Hough transform example
-4000 1500

-2000
 1000
0

500
2000
De-skewed
Paper Paper
(3264x2448)

4000 0
-50 0 50

-81.8 deg

-81.8 deg

Global thresholding

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 32
 Circle Hough Transform
◼ Find circles of fixed radius r
x x0
Circle center

edge pixel

y
y0
◼ Equivalent to convolution (template matching) with a circle

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 33
 Circle Hough Transform for unknown radius
◼ 3-d Hough transform for parameters (x0 , y0 ,r )
◼ 2-d Hough transform aided by edge orientation ➔ “spokes” in parameter space

x x0

Circle center

edge pixel

y
y0

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 34
 Example: circle detection by Hough transform
Prewitt edge detection Detected circles
Original
coins image

Image Processing: Huynh Trung Tru, © 2023 PTIT HCM -- Edge Detection 35