1 of 34

Edge detection

2 of 34

Project 1: Hybrid Images

3 of 34

Project 1 Demo

4 of 34

Reading

  • Szeliski 7.2

5 of 34

Edge detection

TexPoint fonts used in EMF.

Read the TexPoint manual before you delete this box.: AAA

  • Convert a 2D image into a set of curves
    • Extracts salient features of the scene
    • More compact than pixels

6 of 34

Origin of edges

  • Edges are caused by a variety of factors

depth discontinuity

surface color discontinuity

illumination discontinuity

surface normal discontinuity

7 of 34

Images as functions…

  • Edges look like steep cliffs

8 of 34

Characterizing edges

  • An edge is a place of rapid change in the image intensity function

image

intensity function�(along horizontal scanline)

first derivative

edges correspond to�extrema of derivative

Source: L. Lazebnik

9 of 34

Image derivatives

  • How can we differentiate a digital image F[x,y]?
    • Option 1: reconstruct a continuous image, f, then compute the derivative
    • Option 2: take discrete derivative (finite difference)

​

​

​

1

-1

​

​

​

​

How would you implement this as a linear filter?

​

​

​

​

-1

​

​

1

​

:

:

Source: S. Seitz

10 of 34

Image gradient

  • The gradient of an image:

The gradient points in the direction of most rapid increase in intensity���

The edge strength is given by the gradient magnitude:

​

​

​

The gradient direction is given by:

​

​

    • how does this relate to the direction of the edge?�

Source: Steve Seitz

11 of 34

Image gradient

Source: L. Lazebnik

12 of 34

Effects of noise

Where is the edge?

Source: S. Seitz

Noisy input image

​

​

13 of 34

Solution: smooth first

f

h

f * h

Source: S. Seitz

To find edges, look for peaks in

14 of 34

Associative property of convolution

  • Differentiation is convolution, and convolution is associative:

​

  • This saves us one operation:

f

Source: S. Seitz

15 of 34

The 1D Gaussian and its derivatives

16 of 34

2D edge detection filters

Gaussian

derivative of Gaussian (x)

17 of 34

Derivative of Gaussian filter

x-direction

y-direction

18 of 34

The Sobel operator

  • Common approximation of derivative of Gaussian

-1

0

1

-2

0

2

-1

0

1

1

2

1

0

0

0

-1

-2

-1

  • The standard definition of the Sobel operator omits the 1/8 term
      • doesn’t make a difference for edge detection
      • the 1/8 term is needed to get the right gradient magnitude

19 of 34

Sobel operator: example

Source: Wikipedia

20 of 34

21 of 34

Which method is the best way to compute the gradient of an image?

ⓘ Start presenting to display the poll results on this slide.

22 of 34

Example

original image

Demo: http://bigwww.epfl.ch/demo/ip/demos/edgeDetector/

Image credit: Joseph Redmon

23 of 34

smoothed gradient magnitude

Finding edges

24 of 34

thresholding

Finding edges

where is the edge?

25 of 34

Get Orientation at Each Pixel

  • Get orientation (below, threshold at minimum gradient magnitude)

​

θ = atan2(gy, gx)

0

360

Gradient orientation angle

26 of 34

Non-maximum supression

  • Check if pixel is local maximum along gradient direction
    • requires interpolating pixels p and r

27 of 34

Before Non-max Suppression

28 of 34

After Non-max Suppression

29 of 34

Thresholding edges

  • Still some noise
  • Only want strong edges
  • 2 thresholds, 3 cases
    • R > T: strong edge
    • R < T but R > t: weak edge
    • R < t: no edge
  • Why two thresholds?

​

30 of 34

Connecting edges

  • Strong edges are edges!
  • Weak edges are edges �iff they connect to strong
  • Look in some neighborhood�(usually 8 closest)

​

31 of 34

Canny edge detector

  1. Filter image with derivative of Gaussian

​

  • Find magnitude and orientation of gradient

​

  • Non-maximum suppression

​

  • 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

Source: D. Lowe, L. Fei-Fei, J. Redmon

MATLAB: edge(image,‘canny’)

32 of 34

Canny edge detector

  • Our first computer vision pipeline!
  • Still a widely used edge detector in computer vision

​

​

  • Depends on several parameters:

​

J. Canny, A Computational Approach To Edge Detection, IEEE Trans. Pattern Analysis and Machine Intelligence, 8:679-714, 1986.

: width of the Gaussian blur

high threshold

low threshold

33 of 34

Canny edge detector

Canny with

Canny with

original

  • The choice of depends on desired behavior
    • large detects “large-scale” edges
    • small detects fine edges

Source: S. Seitz

34 of 34

Scale space [Witkin 83]

  • Properties of scale space (w/ Gaussian smoothing)
    • edge position may shift with increasing scale (σ)
    • two edges may merge with increasing scale
    • an edge may not split into two with increasing scale

larger

Gaussian filtered signal

first derivative peaks