Edge and Corner Detection

Basics

• Edge pixels are those at which image intensity changes abruptly.

​

• Edge segments or edges are sets of connected edge pixels.

2

Digital derivatives: first versus second

• Along a ramp (i.e. intensity change with constant slope), first derivative is a non-zero constant.

​

• Second derivative is zero along the ramp, except at the start and end!

​

• Second derivative is preferable for image sharpening! Many edges in images are ramp-like, in which case first derivative will give thick edges (undesirable), whereas second derivative gives thin edges two pixels wide (desirable).

​

• Second derivative changes sign midway at a step edge (zero crossing property).

​

3

• At roof edges, second derivative gives stronger response than first derivative (i.e. has larger magnitude) – except if both parts of the roof were at 45 degrees, where both will have equal response.

​

• At isolated points, second derivative gives stronger response than first derivative

​

• A rotationally invariant second-derivative operator is used for edge detection: the Laplacian, in fact zero-crossings of a Laplacian.

4

Digital derivatives: first versus second

Laplacian of an image

5

Laplacian operators: second operator is obtained by adding second derivatives along both the diagonals, to the first operator

Rotationally symmetric operator (in the continuous domain)

6

From book by Gonzalez and Woods

Intensity discontinuity, also called step edge

Edge detection under noise

7

First and second derivatives are very sensitive to noise!

Left to right in each row: original image, first derivative, second derivative

In any column: increase in noise level

Steps in robust edge detection

• Image smoothing to reduce noise: because first and second derivatives are noisy

​

• Actual detection of edge points (may produce thick or disconnected edges)

​

• Pruning or linking of the edge points

8

Edge detection: image gradient

• An image gradient is defined as follows:

9

Robust edge operators

10

These operators: Prewitt and Sobel perform some smoothing prior to difference computation, and hence are more robust than the simple finite differences from the previous slide.

Prewitt and Sobel

11

• Apply the differencing mask [-1 0 1]^T and then apply the smoothing mask [1 1 1] on the result. This is equivalent to applying the first Prewitt mask (i.e. for f_y).
• For the Prewitt operator for f_x, apply [-1 0 1] and then [1 1 1]^T.

• Apply the differencing mask [-1 0 1]^T and then apply the smoothing mask [1 2 1] on the result. This is equivalent to applying the first Sobel mask (i.e. for f_y).
• For the Sobel operator for f_x, apply [-1 0 1] and then [1 2 1]^T.

12

Original image

Derivatives in y direction: f_y

Derivatives in x direction: f_x

| f_x | + |f_y|

Edges with Sobel Mask

13

Original image

Derivatives in y direction: f_y

Derivatives in x direction: f_x

|f_x | + |f_y|

Edges with 5 x 5 averaging followed by Sobel Mask

Notice: finer details removed

14

Edge map after Thresholding the earlier map.

Marr-Hildreth edge detector

• Principled approach to combined edge detection and image smoothing

​

• An edge operator should satisfy two criteria:
• Notion of scale in edge detection (operators of different sizes)
• Differential operator to compute first or second derivatives of the intensity

​

• Uses the Laplacian of Gaussian operator on an image satisfies both criteria

15

Laplacian of Gaussian (LoG or Mexican hat)

16

17

Why LoG for edge detection?

• Remember: we are interesting in zero-crossings of the second derivative!
• We want the second derivative operator to be rotationally invariant. The Laplacian is the simplest (though not the only) such operator.
• The Gaussian is a low-pass filter, which blurs structures with intensity difference smaller than σ.
• Gaussian is smooth in spatial and frequency domains.

18

Using LoG for edge detection

• (1) Convolve the image with the LoG operator, i.e.:

​

​

• (2) Find the zero-crossings in the resultant image.

19

Implementing the convolution

20

Use an n x n mask, created by sampling the formula for LoG on a discrete Cartesian crid of size n x n.

​

How to choose n? Depends on σ: n should be >= 6σ, because more than 99% of the volume underneath a 2D Gaussian lies between μ-3σ and μ+3σ.

Finding zero-crossings

• Look at a 3 x 3 window around a pixel.

​

• There exists a zero-crossing at that pixel if the signs of at least one pair of opposing neighbors (top & bottom, left & right, top-left & right-bottom, top-right & left-bottom) differ and the difference in their values must exceed a threshold p.

21

(x,y)

22

σ = 4, n = 25

Convolut-ion with LoG

Zero-crossings

Zero-crossings + thresholding

Some properties of the Marr-Hildreth Edge Detector

• Detected edges are 1-pixel in thickness

​

• Can be used for different sigma values, keeping only those edge points that are common to multiple scales

23

Canny Edge Detector: using 1^st derivatives

• Three aims/objectives:
• Low error (no spurious responses due to noise)
• Well-localized edge points
• Single pixel wide edges

​

Canny’s detector was formulated by analyzing step edges in 1D under zero-mean i.i.d. Gaussian noise, and expressing the preceding three criteria mathematically and deriving an (approximate) operator that obeys all criteria.

24

Canny’s Edge Detector

• In 1D, the approximate operator was the first derivative of the Gaussian:

​

​

• In 2D, the approximate operator was the first derivative of the Gaussian in the direction of the local image gradient (i.e. perpendicular to the edge).

​

• But the true gradient is not known, so we first smooth the image with a 2D Gaussian and then use its gradient magnitude and direction.

​

25

Canny’s Edge Detector

• Gradient magnitude and direction:

​

​

​

• M(x,y) contains wide ridges along the true edges of the image.
• Though the maximum values are along the edge, those values don’t immediately fall off to 0 on either side of the edge.
• Recall ramp edges.

26

Canny edge detector

• This requires us to perform a thinning operation – called as non-maximal suppression (i.e. we set to zero those values of M(x,y) which are likely to NOT be local maxima).

27

Canny edge detector

• Consider the four quantized directions shown on the previous slide. Pick the direction d_k, which is closest to ϴ(x,y).
• If M(x,y) is less than either of its two neighbors along the direction d_k, then set it to 0 (i.e. suppress the non-maximum), otherwise we leave it as is.
• After this processing, M(x,y) is the non-maximal suppressed image.

28

Canny Edge Detector

• The (thinned) edge map so far may still contain some false positives. This is taken care of (to some extent) by hysteresis thresholding.
• This uses a low-threshold TL and a high threshold TH.
• We keep only those pixels for which

-M(x,y) > TH, OR

-M(x,y) > TL AND (x,y) is a neighbor of at least one pixel with M(x,y) > TH.

29

(x,y)

The 8 neighbors of pixel (x,y)

Summary: Canny Edge detector

1. Convolve the image with a Gaussian Filter. Compute the gradient magnitudes and orientations.

​

(2) Perform non-maximal suppression.

​

(3) Perform hysteresis thresholding.

30

31

32

33

Gaussian filtered (sigma = 1.4, 5 x 5 mask)

Intensity gradients superimposed

Non-maximum suppression

Double thresholding (TL = 0.1, TH = 0.3)

After edge-linking (hysteresis)

https://en.wikipedia.org/wiki/Canny_edge_detector

Corner Detection

Importance of corners

• Corners are considered salient feature points.

​

• Useful in many tasks in computer vision and image processing

​

• Example: corresponding control points for image alignment

35

36

Importance of corners

• In some applications, we need to find matching patches.
• But some patch matches are easier to find than others.
• See next slide for examples.

​

37

38

Good patch for matching

Bad patch for matching

http://www.cse.psu.edu/~rtc12/CSE486/lecture06.pdf

Importance of corners

• Good patches should contain corners – large intensity variations in all directions.
• Shifting the window in any direction yields large appearance change.

39

http://www.cse.psu.edu/~rtc12/CSE486/lecture06.pdf

40

Ambiguity in point matching in flat intensity regions or along edges

Principle behind Harris corner detector

• Consider two patches – one each centered at (x,y) and (x+u,y+v) in two images (patch domain: Ω, typically rectangular, like say 7 x7 or 5 x 5) with u,v being small.

​

• The image have same intensity at physically corresponding locations.

​

• The sum of squared difference (SSD) between their intensities is given as:

41

42

Structure tensor matrix (size 2 x 2)

Principle behind Harris corner detector

• The local A matrix on the previous slide is called the structure tensor.

​

• A carries information about local image geometry.

​

​

​

• It is always positive semi-definite, i.e. its two eigenvalues are always non-negative.

​

• In locally flat regions, A will be close to a zero matrix and hence both its eigenvalues will be close to 0.

43

Proof that the structure tensor matrix is positive semi-definite: Method 1

44

Any matrix that can be written in the form A = ZZ^T is always positive semi-definite (quoting a result from linear algebra)

Proof that the structure tensor matrix is positive semi-definite: Method 2

45

Principle behind Harris corner detector

• At a point lying on an edge, only one of the eigenvalues is large (corresponding to the eigenvector that points across the edge) and the other is close to 0 (corresponding to the eigenvector that points along the edge)

​

• At a corner point, both eigenvectors will be large.

​

• We would like the SSD to be large for all non-zero shifts (u,v) so that we can allow for maximum discriminability and easier point matching.

46

47

http://www.cse.psu.edu/~rtc12/CSE486/lecture06.pdf

48

http://www.cse.psu.edu/~rtc12/CSE486/lecture06.pdf

49

http://www.cse.psu.edu/~rtc12/CSE486/lecture06.pdf

“Corner”-ness measure

• We would like both eigenvalues of this matrix to be large.

​

• Corner response or “corner”ness measure:

R_H = det(A) – k (trace(A))², k between 0.04 to 0.06

• Does not require explicit eigenvalue/eigenvector computation:

50

51

http://www.ipol.im/pub/art/2018/229/article_lr.pdf

52

Computing corners

• Smooth image I to compute various derivatives

​

• Choose a window size (say 7 x 7) and compute the structure tensor at each pixel, given this window size

​

• Compute the corner-ness measure for each pixel

​

• Perform thresholding or non-maximal suppression to create a corners map.

53

54

55

56

57

58

Invariance

• The detected corners are invariant under affine intensity change, i.e. image J replaced by aJ + b for scalars a,b.

​

• The corners are also invariant to rotation and translation.

59

Other measures of corner-ness

• Based on just the minimum eigenvalue – declared a corner if the minimum eigenvalue exceeds a threshold

​

• Harmonic mean of eigenvalues

60