Edge Detection Edges and Gradients Prewitt Kernels Prewitt Kernels [PDF]

Edge Detection

Edge Detection Gradient-based Operators

Edges and Gradients

Edge Detection

I

Edge: local indication of an object transition

I

Edge detection: local operators that “find” edges (usually involves convolution)

I

Local intensity transitions are indicated by the gradient:   ∂ ∂x I  ∇I =  ∂ ∂y I

CS 650: Computer Vision

I

Interpretation: I I

Edge Detection

Gradient magnitude k∇Ik: edge “strength” Gradient orientation φ(∇I): cross-edge direction

Edge Detection

Gradient-based Operators

Gradient-based Operators

Prewitt Kernels

Prewitt Kernels

Idea: central finite differences Central difference: dI ≈ [I(x + 1) − I(x − 1)]/2 dx

Or for more robustness to noise, smooth in the other direction: -1 -1 -1

or for two-dimensional images: ∂I ≈ [I(x + 1, y ) − I(x − 1, y )]/2 ∂x

0 1 0 1 0 1 ∂/∂x

-1 0 1

-1 -1 0 0 1 1 ∂/∂y

This corresponds to the following convolution kernel: -1

0

-1 0 1

1

Edge Detection

Edge Detection

Gradient-based Operators

Gradient-based Operators

Sobel Kernels

From Gradient Magnitude to Edges

Or, giving more weight to the central pixels when averaging: -1 -2 -1

0 1 0 2 0 1 ∂/∂x

-1 0 1

-2 -1 0 0 2 1 ∂/∂y

I

These kernels can also be thought of as 3 × 3 approximations of the first derivative of a small Gaussian

I

Can be though of as blurring by a small Gaussian to remove noise, then taking the derivative: ∂ ∂ (I ∗ G) = I ∗ G ≈ I ∗ Sobel(x) ∂x ∂x

The gradient magnitude gives a measure at every pixel of the “edginess” of each pixel: k∇I(x, y )k Somehow, you have to still find the best edges: I

Threshold (global or local), etc.

I

Local maxima of gradient magnitude .. .

Edge Detection

Edge Detection

Second-derivative Operators

Second-derivative Operators

Using Second Derivatives

I

Using Second Derivatives

Classic maximum test from calculus: x is a extremum of f (x) if

I

df (x) = 0 dx

Extend this idea to find maximal first derivatives: x is a extremum of

df df 2 (x) = 0 (x) if dx dx 2

Edge Detection

Edge Detection

Second-derivative Operators

Second-derivative Operators

Laplacian I

Marr-Hildreth Edge Detection

The Laplacian is defined mathematically as     ∂ ∂ 2 2 ∂x ∂x · = ∂ + ∂ ∇2 = ∇ · ∇ =  ∂ ∂ ∂x 2 ∂y 2 ∂y

I

∂y

When we apply it to an image, we get     ∇2 f = 

∂ ∂x

∂ ∂y

·

∂ ∂x

∂ ∂y

2 2  I = ∂ I + ∂ I 2 ∂x ∂y 2

Can’t always find discrete pixels where the Laplacian is exactly zero—look for zero crossings instead.

Edge Detection

Second-derivative Operators

Derivatives of Gaussians

Laplacian Operators

Derivatives of Gaussians

Second difference: d 2I dx 2

I

∇2 I(x, y) = 0 I

Edge Detection

I

Idea: approximate finding maxima of gradient magnitude (edges) by finding places where

I

≈ [I(x + 1) − I(x)] − [I(x) − I(x − 1)] = I(x + 1) − 2I(x) + I(x − 1)

G(x, y) = (2πσ)−d/2 e−r

The Laplacian is one of these in the x direction added to one of these in the y direction: 0 1 0

0 -2 0

0 1 0

+

0 0 0

1 -2 1

0 0 0

=

0 1 0

1 -4 1

Gaussian kernel for noise removal:

0 1 0

2 /2σ 2

where r 2 = x 2 + y 2 and d is the dimensionality (images=2) I

Can solve in closed form for the first- and second-order derivatives of the Gaussian (including the Laplacian)

I

Can convolve with these directly— exactly the same as blurring first then applying derivatives

Edge Detection

Edge Detection

Derivatives of Gaussians

Other Approaches

Difference of Gaussians I

Combining Both First- and Second-Derivatives

Another property of the Laplacian of Gaussian: ∇2 G =

I

I

∂ G ∂σ

We can thus approximate the Laplacian by the difference of one Gaussian and a just-smaller one: ∇2 G ≈ G(x, y ; σ1 ) − G(x, y ; σ2 )

∇2 I = 0 I

Problem: Tells you the gradient magnitude is at a maximum, not how strong it is—lots of spurious edges.

I

Idea: Combine the two measures

This is the Difference of Gaussians (DoG) kernel. I

Laplacian zero crossings:

∇2 I = 0 and ∇I > T

Ratio (σ1 /σ2 ) for best √ approximation is about 1.6. (Some people like 2.)

Edge Detection

Edge Detection

Other Approaches

Edge Linking and Representation

Canny Edge Detector

Now What?

I Problem with Laplacian zero-crossings: adds the principal curvatures

together—it doesn’t really determine a maximum of gradient magnitude in any one direction.

I The Canny Edge Detector defines edges as zero-crossings of second

derivatives in the direction of greatest first derivative.

The Direction of Greatest First Derivative This is simply the gradient direction. The Second Derivative in The Direction of . . . We can compute this using the matrix of second derivatives (Hessian). Zero Crossings of. . . As with the Marr-Hildreth edge detector, we’ll use positive-negative transitions to “trap” zeroes.

Now you have potential edge points, how do you get contours? I I

Thresholding gradient magnitude Threshold, then “relax” the labeling I I

Thresholding with hysteresis (Canny) Edge relaxation algorithms using other criteria

I

Edge linking (including postprocessing)

I

Connected loci of local maxima (ridges)

I

Maximum-magnitude contours/paths (Turns into optimization problem—we’ll come back later.)

I Gives connected edges much like the Laplacian operator but more

accurately localize the edge.

Edge Detection

Edge Detection

Edge Linking and Representation

Edge Linking and Representation

Representation

Representation

Once you have contours, how do you represent them? I

Chain codes (4- or 8-connected directions)

I

Differential chain codes (4- or 8-connected relative directions)

I I

Polylines (fit with short line segments) Arc-length parameterization I I I I I

Position Tangent orientation Curvature Distance to some central point ...

I

Fourier descriptors

I

Many other ways to represent curves

What do you want to do with the representation? I I

Reproduction Matching I I I I I

Translated Rotated Scaled Noise and variation (smooth the curves) ...

Want to be invariant to as much as possible