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

​

​

Unfortunately, taking image derivatives accentuates high frequencies and hence amplifies noise, as the proportion of noise to signal is larger at high frequencies. It is therefore prudent to smooth the image with a low-pass filter prior to computing the gradient.

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

removes weaker detections that have too much overlap with stronger detections, using a greedy most-confident-first algorithm

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