1 of 115

Lecture 2: Filtering

2 of 115

Recall: blurring and edge detection

Denoising

Edge detection

3 of 115

Recall: neighborhood filtering

0

0

0

0

0

0

0

0

90

90

90

90

0

0

0

90

90

90

90

0

0

0

90

90

90

90

0

0

0

90

0

90

90

0

0

0

90

90

90

90

0

0

0

0

0

0

0

0

0

​

​

​

​

​

​

​

​

?

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

Filter kernel

Input

Output

4 of 115

Recall: neighborhood filtering

0

0

0

0

0

0

0

0

90

90

90

90

0

0

0

90

90

90

90

0

0

0

90

90

90

90

0

0

0

90

0

90

90

0

0

0

90

90

90

90

0

0

0

0

0

0

0

0

0

​

​

​

​

​

​

​

​

?

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

Input

Output

Filter kernel

5 of 115

Recall: neighborhood filtering

0

0

0

0

0

0

0

0

90

90

90

90

0

0

0

90

90

90

90

0

0

0

90

90

90

90

0

0

0

90

0

90

90

0

0

0

90

90

90

90

0

0

0

0

0

0

0

0

0

​

​

​

​

​

​

​

​

?

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

Filter kernel

Input

Output

6 of 115

Recall: neighborhood filtering

0

0

0

0

0

0

0

0

90

90

90

90

0

0

0

90

90

90

90

0

0

0

90

90

90

90

0

0

0

90

0

90

90

0

0

0

90

90

90

90

0

0

0

0

0

0

0

0

0

​

​

​

​

​

​

​

​

40

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

Filter kernel

Input

Output

7 of 115

Recall: neighborhood filtering

0

0

0

0

0

0

0

0

90

90

90

90

0

0

0

90

90

90

90

0

0

0

90

90

90

90

0

0

0

90

0

90

90

0

0

0

90

90

90

90

0

0

0

0

0

0

0

0

0

​

​

​

​

​

​

​

​

40

?

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

Filter kernel

Input

Output

8 of 115

Recall: neighborhood filtering

0

0

0

0

0

0

0

0

90

90

90

90

0

0

0

90

90

90

90

0

0

0

90

90

90

90

0

0

0

90

0

90

90

0

0

0

90

90

90

90

0

0

0

0

0

0

0

0

0

​

​

​

​

​

​

​

​

40

60

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

Filter kernel

Input

Output

9 of 115

Today

  • Linear filtering
  • More neighborhood filters
  • Nonlinear filters

10 of 115

Filtering

10

Adapted from Torralba, Freeman, Isola

Remove unwanted sources of variation, keeping only information that’s relevant for a task.

Image indexed by pixel

f[n, m]

g[n, m]

H

11 of 115

Linear filtering

11

Source: Torralba, Freeman, Isola

g[n, m]

f[n, m]

H

In matrix form:

A very general transformation:

(Assuming 1D signal for simplicity)

12 of 115

Linear filtering

12

Source: Torralba, Freeman, Isola

g[n, m]

f[n, m]

H

In matrix form:

  • Linear transformation:
  • Equivalent to f = Hg where H is constructed from combinations of h
  • A very general transformation. Allows for may types of image changes.

13 of 115

Linear filtering

13

A linear filter in its most general form can be written as (for a 1D signal of length N):

In matrix form:

Source: Torralba, Freeman, Isola

14 of 115

Linear filtering

14

Can generalize to 2D image (for image of size NxM):

Source: Torralba, Freeman, Isola

15 of 115

15

Photo by Fredo Durand, slide adapted from Torralba, Freeman, Isola

Why handle each spatial position differently?�

​

Often want translation invariance for our linear filters.

16 of 115

Translation Invariance

There is an eye in the original image and the shifted image.

​

Translation should have no e ffect on determining this image is an eye.

f (x + h) = f (x)

​

Future: filters for classification of images

17 of 115

Convolution

Let h be the image and g be the kernel. The output of convolving h with g is:

17

Source: F. Durand

Convention: �kernel is “flipped”

g

h

g

f

18 of 115

Cross-correlation

Let be the image and be the kernel. The output of cross-correlating with is:

18

Adapted from: F. Durand

f

g

image

output

kernel

h

19 of 115

Cross-correlation

Let be the image and be the kernel. The output of cross-correlating with is:

19

f

g

image

output

kernel

h

20 of 115

Cross-correlation

Let be the image and be the kernel. The output of cross-correlating with is:

20

Source: F. Durand

f

g

image

output

kernel

h

21 of 115

Cross-correlation

Let be the image and be the kernel. The output of cross-correlating with is:

21

Source: F. Durand

shift image by (m, n)

f

g

image

output

kernel

h

22 of 115

Cross-correlation

Let be the image and be the kernel. The output of cross-correlating with is:

22

Source: F. Durand

f

g

image

output

kernel

h

dot product between h and shifted f

23 of 115

Cross-correlation

Is this equivalent to what we saw last class? Yes.

  • Given a tiny filter, pad it to make it N x N.
  • Convention: out of bounds indexes wrap around.

f

g

image

output

zero padding

h

24 of 115

Convolution

Let g be the image and h be the kernel. The output of convolving f with h is:

24

h

h

Source: F. Durand

Convention: �kernel is “flipped”

f

g

image

output

kernel

25 of 115

Why flip the kernel?

25

  • Gives it nice mathematical properties.
  • When filter is symmetric, equivalent to cross-correlation.

26 of 115

Convolution versus Cross-Correlation

27 of 115

28 of 115

Properties of the convolution

28

Commutative (no distinction between filter and image):

Associative (doesn’t matter what order you do 2 convolutions):

Distributive with respect to the sum:

29 of 115

1D Example of Convolution

Convolution and cross correlation were described discretely here but can be also thought of continuously with integration.

​

https://mathworld.wolfram.com/Convolution.html

30 of 115

Today

  • Linear filtering
  • More neighborhood filters
  • Nonlinear filters

31 of 115

Rectangular filters

31

=

Source: Torralba, Freeman, Isola

f[m,n]

h[m,n]

g[m,n]

32 of 115

Rectangular filters

32

=

Source: Torralba, Freeman, Isola

f[m,n]

h[m,n]

g[m,n]

33 of 115

“Naturally” occurring filters

33

Motion blur

Input image

Source: Torralba, Freeman, Isola

34 of 115

“Naturally” occurring filters

34

Convolution output

Convolution weights

Input image

Source: Torralba, Freeman, Isola

35 of 115

35

Camera shake

[Fergus et al., 2007]

Source: Torralba, Freeman, Isola

36 of 115

“Naturally” occurring filters

36

Source: Torralba, Freeman, Isola

Blur

37 of 115

Blurring revisited

What’s wrong with this result?

37

Source: D. Forsyth

Box filter

38 of 115

Blurring revisited

38

Source: S. Lazebnik

Idea: weight contribution of neighborhood pixels according to their closeness to the center

“fuzzy blob”

…

39 of 115

Gaussian kernel

  • Constant factor makes kernel sum to 1
    • In practice: create filter without the factor, then normalize it.
  • Make sure to center it: (x, y) is the center of the kernel, not a corner

39

Source: K. Grauman

σ = 2 with 30 x 30 kernel

σ = 5 with 30 x 30 kernel

40 of 115

Gaussian kernel

  • Constant factor in front makes kernel sum to 1
  • Can estimate it by simply summing the values in the kernel

40

Source: K. Grauman

σ = 2 with 30 x 30 kernel

σ = 5 with 30 x 30 kernel

41 of 115

Gaussian vs. box filtering

41

Source: S. Lazebnik

42 of 115

Gaussian standard deviation

42

σ=2

σ=4

σ=8

Source: Torralba, Freeman, Isola

43 of 115

Smoothing with box filter revisited

  • What’s wrong with this picture?
  • What’s the solution?

43

Source: D. Forsyth

44 of 115

Smoothing with box filter revisited

  • What’s the solution?
    • To eliminate edge effects, weight contribution of neighborhood pixels according to their closeness to the center

44

“fuzzy blob”

Source: S. Lazebnik

45 of 115

Gaussian Kernel

  • Standard deviation σ: determines extent of smoothing

45

Source: K. Grauman

σ = 2 with 30 x 30 kernel

σ = 5 with 30 x 30 kernel

46 of 115

Choosing kernel width

  • The Gaussian function has infinite support, but discrete filters use finite kernels

46

Source: K. Grauman

47 of 115

Choosing kernel width

  • Rule of thumb: set filter half-width to about 3σ

47

48 of 115

Gaussian filters

  • Remove high-frequency components from the image (low-pass filter)
  • Convolution with self is another Gaussian
    • So can smooth with small-σ kernel, repeat, and get same result as larger-σ kernel would have
    • Convolving two times with Gaussian kernel with std. dev. σ �is same as convolving once with kernel with std. dev.
  • Separable kernel
    • Factors into product of two 1D Gaussians
    • Discrete example:

48

Source: K. Grauman

49 of 115

Gaussian filters

  • Convolution with self is another Gaussian
    • Can smooth with small-σ kernel, repeat, get same result as larger-σ
    • Convolving two times with Gaussian kernel with std. dev. σ �is same as convolving once with kernel with std. dev.

49

Source: K. Grauman

  • It’s a separable kernel
    • Blur with 1D Gaussian in one direction, then the other.
    • Much faster to compute. O(n) time for an n*n kernel instead of O(n2)
    • Learn more about this in Problem Set 1!

50 of 115

Useful properties of Gaussian filters

50

Convolve a Gaussian filter with itself? Get another Gaussian.

=

51 of 115

Useful properties of Gaussian filters

51

I

blur(blur(I))

blur(blur(blur(I)))

Smooth with small σ repeatedly. Equivalent to smoothing with large σ!

Exploits associativity:

52 of 115

Useful properties of Gaussian filters

52

Gaussian kernels are separable.

  • Blur with 1D Gaussian in one direction, then the other. Produces same result!
  • These are (n x 1) and (1 x n) rectangular filters.
  • Fast! For an n x n kernel, O(n) instead of O(n^2) .

I

blurx(I)

blury(blurx(I))

53 of 115

Recall: derivatives

53

Adapted from: Torralba, Freeman, Isola

Another option:

54 of 115

Problems with simple derivative filters

54

[1 -1]

  • Sensitive to edges at small spatial scales
  • Also sensitive to noise
  • You'll see this in Problem Set 1!

Sensitive to “tiny” edges

55 of 115

Where’s the edge?

55

Noisy input image

​

Source: S. Seitz

56 of 115

Solution: smooth first

56

f

h

f * h

Source: S. Seitz

To find edges, look for peaks in

57 of 115

Derivative of Gaussian filter

57

Gaussian

Derivative of Gaussian (x)

Source: N. Snavely

58 of 115

Derivative of Gaussian filter

58

x-direction

y-direction

Source: N. Snavely

59 of 115

Gaussian Scale

59

σ=2

σ=4

σ=8

Source: Torralba, Freeman, Isola

60 of 115

Derivative of Gaussian scales

60

σ=2

σ=4

σ=8

Source: Torralba, Freeman, Isola

61 of 115

Derivatives in other directions

61

Adapted from N. Snavely

1

0

0

-1

desired direction

What if we need lots of angles? This could get expensive.

Image

62 of 115

Steerable filters

62

= ?

+

=

Use a multivariable calculus fact:

Directional derivative = linear combination of partial derivatives.

Source: N. Snavely

Given and , steer to direction .

63 of 115

Computing a directional derivative

63

+

=

From multivariable calculus:

Directional derivative is a linear combination of partial derivatives

Source: N. Snavely

64 of 115

Also works for derivative of Gaussian filter

64

x direction

y direction

+

=

Source: N. Snavely

See [Freeman and Adelson, “Design and Use of Steerable Filters”, 1991] for a deeper look.

65 of 115

Filter approximations

65

1

2

1

1

3

3

1

1

4

6

4

1

Binomial filter Gaussian

1

2

1

0

0

0

-1

-2

-1

Sobel filter

Derivative of Gaussian

66 of 115

2nd derivatives

66

1

-1

1

-1

1

-2

1

67 of 115

Laplacian filter

67

0

1

0

1

-4

1

0

1

0

68 of 115

Laplacian filter

68

Detects edges and blobs, and not sensitive to orientation. But sensitive to noise.

Source: Torralba, Freeman, and Isola

69 of 115

Laplacian of Gaussian

69

Combine with Gaussian. Picks up “blob-like” structures.

70 of 115

“Blob” detection with Laplacian

70

Source: S. Lazebnik

71 of 115

Decomposing an image

71

-

+

-

Gaussian filter

(a.k.a. “low pass”)

Approx. Laplacian

(a.k.a. “high pass”)

Source: Torralba, Freeman, Isola

72 of 115

72

-

+

-

+

=

Source: Torralba, Freeman, Isola

Approx. Laplacian

73 of 115

Application: Hybrid Images

[A. Oliva, A. Torralba, P.G. Schyns, Hybrid Images, SIGGRAPH 2006]

73

Source: S. Lazebnik

74 of 115

Hybrid Images

74

Oliva & Schyns

75 of 115

Hybrid Images

75

76 of 115

76

77 of 115

77

78 of 115

78

79 of 115

79

80 of 115

80

81 of 115

Today

  • Linear filtering
  • More neighborhood filters
  • Nonlinear filters

82 of 115

Denoising revisited: salt and pepper noise

Gaussian filter doesn’t work as well!

82

Source: S. Lazebnik

83 of 115

Blurring

83

Gaussian filter

Images from [Paris et al. “A Gentle Introduction to Bilateral Filtering and its Applications”, 2008]

Image filters aren’t “aware” of edges

84 of 115

Median filtering

84

Gaussian filter

Bilateral filter

Median filtered

result

85 of 115

Median filtering window sizes

85

Gaussian filter

Bilateral filter

Original

w = 5

w = 13

w = 21

86 of 115

Another approach

86

Let’s start by rewriting the Gaussian filter:

Bilateral filter

Blurred intensity

Gaussian density:

​

87 of 115

Bilateral filtering

87

Gaussian filter

Bilateral filter

What if we weight by appearance?

88 of 115

Bilateral filtering

88

Gaussian filter

Bilateral filter

Gaussian filter:

Bilateral filter:

Spatial Gaussian

Range Gaussian

Normalization constant

(to make weights sum to 1)

89 of 115

Bilateral filter

89

[Paris et al. “A Gentle Introduction to Bilateral Filtering and its Applications”, 2008]

90 of 115

Bilateral filter

90

[Paris et al. “A Gentle Introduction to Bilateral Filtering and its Applications”, 2008]

91 of 115

Denoising with Gaussian

91

Source: [Paris et al. 2008]

Noisy image

Gaussian blur σ = 3

Gaussian blur σ = 5

92 of 115

Denoising with Bilateral Filter

92

Source: [Paris et al. 2008]

Original

Noisy image

Bilateral filtering

93 of 115

Iteratively applying the filter

93

Source: [Paris et al. 2008]

94 of 115

Iteratively applying the filter

94

[Winnemoller et al., 2006]

“Cartoonifying” a video

95 of 115

Image patches as filters

  • Goal: find in an image

​

  • What’s a good similarity/distance measure between two patches?

Source: D. Hoiem

96 of 115

Matching with filters

Method 1: Filter the image with

Input

Filtered Image

What went wrong?

f = image

g = filter

Source: D. Hoiem

97 of 115

Matching with filters

Input

Filtered Image (scaled)

Thresholded Image

True detections

False detections

mean of f

Method 2: Filter the image with zero-mean eye.

`

Source: D. Hoiem

98 of 115

Matching with filters

mean image patch

mean template

Method 3: Normalized cross-correlation. �Divide by standard deviation of both patches, so they are unit vectors.

Source: D. Hoiem

99 of 115

Matching with filters

Input

Normalized X-Correlation

Thresholded Image

True detections

Method 3: Normalized cross-correlation.

Source: D. Hoiem

100 of 115

Recognizing objects: is it really so hard?

This is a chair

Find the chair in this image

Output of normalized correlation

Source: A. Torralba

101 of 115

Recognizing objects: is it really so hard?

Find the chair in this image

Not so great!

Source: A. Torralba

102 of 115

What makes an image “natural”?

Natural image

“Fake” image

Source: Torralba, Freeman, Isola

103 of 115

Is it the distribution of pixel intensities?

Intensity histogram

No real structure here…

104 of 115

What about gradients?

g[m,n]

h[m,n]

=

f[m,n]

[-1, 1]

Source: Torralba, Freeman, Isola

105 of 115

What about gradients?

g[m,n]

h[m,n]

=

f[m,n]

[-1, 1]T

Source: Torralba, Freeman, Isola

106 of 115

Filter response distribution is pretty consistent!

Source: Torralba, Freeman, Isola

107 of 115

Red – true pdf

Black – best Gaussian fit

Image

[1 -1] filter output

[1 -1] output histogram

Intensity histogram

Source: Torralba, Freeman, Isola

108 of 115

Applications of image statistics

Compression

Image restoration

Learning

(later in course)

109 of 115

Taking a picture…

109

What the camera give us…

How do we correct this?

Source: R. Fergus

110 of 115

Image formation process

=

⊗

Blurry image

Sharp image

Blur �kernel

Input to algorithm

Desired output

Convolution�operator

Source: R. Fergus

111 of 115

Multiple possible solutions

=

⊗

Blurry image

Sharp image

Blur kernel

=

⊗

=

⊗

Source: R. Fergus

112 of 115

Natural image statistics

Histogram of image gradients

Characteristic distribution with heavy tails

Source: R. Fergus

113 of 115

Blurry images have different statistics

Histogram of image gradients

Source: R. Fergus

114 of 115

Removing motion blur

Original photograph

After matching filter distribution

Source: R. Fergus

Solve for an image with a distribution of edge gradients that “matches” a normal image.

115 of 115

Next class: image pyramids