1 of 144

Lecture 3: Image pyramids

1

2 of 144

Announcements

2

  • Reminder: PS1 due next Weds.
  • Discussion section this week:
    • Fourier transform
  • Suggested reading: Szeliski chapter or Torralba, Isola, Freeman chapter

3 of 144

Today

3

  • Filtering (finishing up from last class)
    • More linear filters
    • Nonlinear filters
  • Image pyramids

4 of 144

Review: derivatives in other directions

= ?

Adapted from N. Snavely

4

1

0

0

-1

desired direction

Image

​

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

Define a filter?

5 of 144

Review: steerable filters

5

= ?

+

=

Use a multivariable calculus fact:

Directional derivative = linear combination of partial derivatives.

Source: N. Snavely

Given and , steer to direction .

6 of 144

Review: steerable filters

= ?

+

=

∂f ∂f

Given and , steer to direction u⃗ = [ux uy].

∂x ∂y

​

Use a multivariable calculus fact:

r~uf (~x) = rf (~x) · ~u

Directional derivative = linear combination of partial derivatives.

Source: N. Snavely

5

7 of 144

Filter approximations

6

1

2

1

Binomial filter

Gaussian

1

4

1

3

3

1

1

4

6

4

1

1

8

1

16

1

2

1

0

0

0

-1

-2

-1

1

8

Sobel filter

Derivative of Gaussian

8 of 144

Decomposing an image

Gaussian filter

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

7

Source: Torralba, Freeman, Isola

Are there filters that does the opposite?

9 of 144

2nd derivatives

1

-1

1

-1

1

-2

1

≈

∂f 2

∂x2

∂f

∂x

∂f

∂x

8

10 of 144

Laplacian filter

+

∂I2 ∂I2

∂x2 ∂y2

≈

I ∘

9

0

1

0

1

-4

1

0

1

0

11 of 144

Laplacian filter

∘

=

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

10

Source: Torralba, Freeman, and Isola

12 of 144

Laplacian of Gaussian

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

∘

=

11

13 of 144

“Blob” detection with Laplacian

12

σ = 12

Source: S. Lazebnik

14 of 144

Difference of Gaussians

Subtract two blurry images from each other.

Source: S. Laze1b3nik

Can be shown to be a good approximation.

15 of 144

Decomposing an image

+

15

Source: Torralba, Freeman, Isola

-

-

Gaussian filter

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

Approx. Laplacian

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

16 of 144

Approx. Laplacian

-

+

-

+

=

Gaussian filter

16

Source: Torralba, Freeman, Isola

17 of 144

18 of 144

At a distance, we see only low frequencies!

19 of 144

Application: Hybrid Images

Source: S. Lazeb18nik

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

20 of 144

Hybrid Images

Oliva & Schyns19

21 of 144

Hybrid Images

22 of 144

23 of 144

24 of 144

What if we generated the high pass using a neural network?

+

low pass

Daniel Geng

Aaron Park

Andrew Owens

[Factorized Diffusion: Perceptual Illusions by Noise Decomposition, ECCV 2024]

high pass

=

25 of 144

What if we generated the high pass using a neural network?

+

low pass

“a photo of a lightbulb”

image generator

=

Daniel Geng

Aaron Park

Andrew Owens

[Factorized Diffusion: Perceptual Illusions by Noise Decomposition, ECCV 2024]

You’ll learn more about this in PS7!

26 of 144

27 of 144

Generating both components?

28 of 144

"a lithograph of flowers”

”a lithograph of a panda"

29 of 144

"a photo of a canyon”

”a photo of gandhi”

30 of 144

"a lithograph of waterfalls”

”a lithograph of a pig”

31 of 144

Thanks to Walter Scheirer and Luba Elliot for suggesting this!

32 of 144

The Core Challenge: Preserving Detail During Calibration

  • How can we transfer HST's photometric properties to JunoCam without losing JunoCam's unique high-frequency details (like meso-scale storms)?

​

​

32

?

JunoCam: High Detail, Uncalibrated

HST: Lower Detail, Calibrated

New Images: High Detail, Calibrated

Meso Scale storm

Introduction

Background & Motivation

Contributions

Conclusion

Evaluation & Results

33 of 144

33

34 of 144

Today

  • More filtering (finishing up from last class)
    • More linear filters
    • Nonlinear filters
  • Image pyramids
  • Image statistics
  • Texture synthesis

31

35 of 144

Denoising revisited: salt and pepper noise

Gaussian filter doesn’t work as well!

32

Source: S. Lazebnik

36 of 144

Blurring

Gaussian filter

33

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

Image filters aren’t “aware” of edges

37 of 144

Median filtering

38 of 144

Recall: box filtering

38

Filter kernel

39 of 144

Recall: box filtering

39

Filter kernel

40 of 144

Recall: box filtering

Filter kernel

41 of 144

Recall: box filtering

41

Filter kernel

42 of 144

Recall: box filtering

42

Input

Output

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

60

40

20

​

​

60

90

60

40

20

​

​

50

80

80

60

30

​

​

50

80

80

60

30

​

​

30

50

50

40

20

​

​

​

​

​

​

​

​

43 of 144

Median filtering

44 of 144

Median filtering

45 of 144

Median filtering

46 of 144

Median filtering

47 of 144

Median filtering

48 of 144

Median filtering

49 of 144

Median filtering

49

Input

Output

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

​

​

​

​

​

​

​

​

0

90

90

0

0

​

​

90

90

90

90

0

​

​

90

90

90

90

0

​

​

90

90

90

90

0

​

​

0

90

90

0

0

​

​

​

​

​

​

​

​

50 of 144

…vs. box filtering

50

Input

Output

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

60

40

20

​

​

60

90

60

40

20

​

​

50

80

80

60

30

​

​

50

80

80

60

30

​

​

30

50

50

40

20

​

​

​

​

​

​

​

​

51 of 144

Median filtering window sizes

Original

w = 5

w = 13

w = 21

51

52 of 144

Idea: weight by visual similarity

53 of 144

Bilateral filtering

p

q

||p - q||

What if we weight by appearance?

53

54 of 144

Bilateral filtering

54

55 of 144

Bilateral filtering

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

52

56 of 144

Bilateral filter

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

53

57 of 144

Denoising with Gaussian

Noisy image

Gaussian blur = 3

Gaussian blur = 5

57

Source: [Paris et al. 2008]

58 of 144

Denoising with Bilateral Filter

Original

58

Source: [Paris et al. 2008]

Noisy image

Bilateral filtering

59 of 144

Iteratively applying the filter

59

Source: [Paris et al. 2008]

60 of 144

Image patches as filters

  • Goal: find in an image

​

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

Source: D. Hoiem

57

61 of 144

Matching with filters

Method 1: Filter the image with

h[m, n] = ∑ g[k,l ] f [m + k, n + l ]

k ,l

What went wrong?

f = image

g = filter

Filtered58 Image

Input

Source: D. Hoiem

62 of 144

Matching with filters

True detections

False detections

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

Thresholded Image

Filtered Image (scaled)

`

Source: D. Hoiem

Input

63 of 144

Matching with filters

Method 3: Normalized cross-correlation.

Divide by standard deviation of both patches, so they are unit vectors.

60

Source: D. Hoiem

64 of 144

Matching with filters

Input

Normalized61X-Correlation

Thresholded Image

True detections

Method 3: Normalized cross-correlation.

Source: D. Hoiem

65 of 144

Recognizing objects: is it really so hard?

65

This is a chair

Find the chair in this image

Output of normalized correlation

Source: A. Torralba

66 of 144

Recognizing objects: is it really so hard?

66

Find the chair in this image

Not so great!

Source: A. Torralba

67 of 144

Today

  • More filtering (finishing up from last class)
    • More linear filters
    • Nonlinear filters
  • Image pyramids

64

68 of 144

We want scale invariance!

Source: Torralba, Freeman, I6s5ola

69 of 144

Image pyramids

69

Source: Torralba, Freeman, Isola

70 of 144

Image pyramid

1/2

1/2

​

​

1/2

1/2

70

Source: Torralba, Freeman, Isola

71 of 144

Subsampling and aliasing

1/2

1/2

Source: Torralba, Freeman, Isola

Idea #1: Throw away every other pixel.

68

72 of 144

What’s happening?

Consider a sinusoid:

72

Source: S. Marschner

73 of 144

Undersampling

  • What if we “missed” things between the samples?
  • As expected, information is lost
  • Unexpectedly: indistinguishable from low-frequency sinusoid!
  • Also indistinguishable from higher frequencies
  • Aliasing: signals “traveling in disguise” as other frequencies

73

Source: S. Marschner

74 of 144

Undersampling

Source: Wikipedia

74

75 of 144

Removing aliasing

  • Remove the high frequencies first!
  • Blur the image before downsampling
    • Next class we’ll see why blurring does this

​

​

Blur

75

Source: Torralba, Freeman, Isola

76 of 144

Gaussian pyramid

For each level:

1. Blur input image with a Gaussian (or binomial) filter

Blur

76

Source: Torralba, Freeman, Isola

77 of 144

Gaussian pyramid

For each level:

  1. Blur input image with a Gaussian (or binomial) filter
  2. Downsample (throw away every other pixel)

77

Source: Torralba, Freeman, Isola

78 of 144

Gaussian pyramid

256×256

128×128

64×64

32×32

2

2

2

78

Source: Torralba, Freeman, Isola

79 of 144

Gaussian pyramid

512×512

79

Source: Torralba, Freeman, Isola. Image from Forsyth & Ponce

(original image)

80 of 144

Gaussian pyramid

For each level

  1. Blur input image with a Gaussian filter
  2. Downsample image

80

Source: Torralba, Freeman, Isola

81 of 144

Recall: Laplacian

+

78

Source: Torralba, Freeman, Isola

-

-

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

Approx. Laplacian

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

82 of 144

Laplacian Pyramid

Compute the difference between upsampled Gaussian pyramid level k+1 and Gaussian pyramid level k. Recall that this approximates the blurred Laplacian.

+

-

Source: Torralba, Freeman, Is7o9la

83 of 144

Laplacian Pyramid

Gaussian pyramid

Source: Torralba, Freeman, Is8o9la

84 of 144

Laplacian Pyramid

Gaussian pyramid

Source: Torralba, Freeman, Is8o1la

Laplacian pyramid

85 of 144

Laplacian Pyramid

Source: Torralba, Freeman, Is8o2la

Blurring and downsampling:

gk+1 = Gk(gk) = downsample(blur(gk))

Upsampling, blurring, and subtraction:

lk = Fk(gk, gk+1) = ????

86 of 144

Upsampling

=

64x64

Insert zeros

128x128

Source: Torralba, Freeman, Is8o3la

128x128

87 of 144

Laplacian Pyramid

Gaussian pyramid

Source: Torralba, Freeman, Is8o4la

Laplacian pyramid

88 of 144

Laplacian Pyramid

Gaussian pyramid

Source: Torralba, Freeman, Is8o5la

High frequencies

things that change fast

Low frequencies

things that change slowly

89 of 144

Laplacian Pyramid

Gaussian residual

Laplacian pyramid

Can we invert the Laplacian Pyramid?

Source: Torralba, Freeman, Is8o6la

90 of 144

Laplacian Pyramid

Gaussian pyramid

Laplacian pyramid

Source: Torralba, Freeman, Is8o7la

91 of 144

Laplacian Pyramid

​

Gaussian pyramid

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

Laplacian pyramid

​

​

Analysis/Encoder

​

​

​

​

​

​

​

​

​

​

​

Synthesis/Decoder

Source: Torralba, Freeman,8I8sola

92 of 144

Application: generating “triple” hybrid images!

(You’ll learn more about this on PS7)

Daniel Geng Aaron Park Andrew Owens

[Factorized Diffusion: Perceptual Illusions by Noise Decomposition, ECCV 2024]

93 of 144

"a lithograph of waterfalls”

”a lithograph”aofliathsokgurlalp”h of a yin yang”

94 of 144

More Laplacian pyramid applications

Source: Torralba, Freeman, Is9o1la

  • Texture synthesis
  • Image compression
  • Noise removal
  • Computing image “keypoints”

95 of 144

Image Blending

Source: Torralba, Freeman, Is9o2la

96 of 144

Image Blending

Source: Torralba, Freeman, Is9o3la

97 of 144

Image Blending

I A

Source: Torralba, Freeman, Is9o4la

I B

m

I

I = m * IA + (1 − m) * IB

98 of 144

What if you blurred the mask?

m

IA

IB

I

I = m * IA + (1 − m) * IB

Better, but it loses texture at boundary.

95

99 of 144

Image Blending with the Laplacian Pyramid

lA

0

lA

1

lA

2

lA

3

lA

4

lA

5

lA

6

gA

7

lB

1

lB

2

lB

3

lB

4

lB

5

lB

6

gB

7

lB

Source: Torralba, Freeman, Is9o6la

0

100 of 144

Image Blending with the Laplacian Pyramid

Source: Torralba, Freeman, Is9o7la

101 of 144

+

=

Simple blend

With Laplacian pyr.

Source: A. Efros

98

102 of 144

Photo credit: Chris Cameron

Source: A. Efros

99

103 of 144

Image Blending (PS2 problem)

  • Build Laplacian pyramid for both images: LA, LB

​

  • Build Gaussian pyramid for mask: G

​

  • Build a combined Laplacian pyramid

​

  • Collapse L to obtain the blended image

Source: Torralba, Freeman, I1s0o0la

104 of 144

Image pyramids

Gaussian Pyramid Laplacian Pyramid

And many more: steerable filters, wavelets, … (and later) convolutional networks!

101

Source: Torralba, Freeman, Isola

105 of 144

H

Are Gaussian/Laplacian pyramids linear filters?

​

f = Hg

102

g[n, m]

f[n, m]

Recall: linear filter

Equivalent to matrix multiplication with some matrix H:

106 of 144

1D Gaussian pyramid as a linear transformation

g

1

g2

g0

g1 = G0g0

[1, 4, 6, 4, 1]

[1, 4, 6, 4, 1]

103

Source: Torralba, Freeman, Isola

107 of 144

Laplacian Pyramid

Blurring and downsampling:

Upsampling and blurring:

(blur)

(Downsampling by 2)

(Upsampling by 2)

(blur)

Source: Torralba, Freeman, I1s0o4la

108 of 144

The Laplacian Pyramid

Source: Torralba, Freeman, I1s0o5la

109 of 144

Laplacian Pyramid

Gaussian pyramid

Laplacian pyramid

​

l0

g2

l1

=

Source: Torralba, Freeman, I1s0o6la

110 of 144

Linear Image Transforms

Gaussian pyramid

Laplacian pyramid

107

Source: Torralba, Freeman, Isola

111 of 144

For more powerful nonlinear models…

  • Later, we’ll study a powerful nonlinear model,

convolutional neural networks

  • Their main building blocks are linear filters.

[LeCun et al. 1989]

108

112 of 144

Other topics (optional)

  • Image pyramids
  • Image statistics
  • Texture synthesis

109

113 of 144

What makes an image “natural”?

Natural image

“Fake” image

110

Source: Torralba, Freeman, Isola

114 of 144

Is it the distribution of pixel intensities?

Intensity histogram

111

No real structure here…

115 of 144

What about gradients?

g[m,n]

h[m,n]

=

f[m,n]

[-1, 1]

115

Source: Torralba, Freeman, Isola

116 of 144

What about gradients?

g[m,n]

h[m,n]

=

f[m,n]

[-1, 1]T

116

Source: Torralba, Freeman, Isola

117 of 144

Filter response distribution is pretty consistent!

117

Source: Torralba, Freeman, Isola

118 of 144

Image

[1 -1] output histogram

Red – true pdf

Black – best Gaussian fit

[1 -1] filter output

Intensity histogram

115

Source: Torralba, Freeman, Isola

119 of 144

Today

  • Image pyramids
  • Image statistics
  • Texture synthesis

116

120 of 144

Texture analysis

What we’d like: are they made of the same “stuff”. Are these textures similar?

117

True (infinite) texture

Analysis

“Same” or “different”

Source: A. Efros

121 of 144

How do humans analyze texture?

121

Human vision is sensitive to the difference of some types of elements and appears to be “numb” on other types of differences.

Béla Julesz

Source: A. Efros

122 of 144

Julesz Conjecture

122

Textures cannot be spontaneously discriminated if they have the same first-order and second-order statistics and differ only in their third-order or higher-order statistics.

Somewhat imprecise (and later proved wrong)

Béla Julesz

Source: A. Efros

123 of 144

1st order statistics differ

123

5% white

Source: A. Efros

20% white

124 of 144

2nd order statistics differ

124

10% white

Source: A. Efros

125 of 144

How can we represent texture in natural images?

125

Idea #1: Record simple statistics (e.g., mean, standard deviation) of absolute filter responses

Source: A. Efros

126 of 144

Can you match the texture to the response?

126

3

Mean abs. responses

Filters

Source: A. Efros

A

B

C

1

2

127 of 144

How can we represent texture?

127

Source: A. Efros

  • Generalize this to “orientation histogram”
  • Idea #2: Histograms of filter responses
    • One histogram per filter

128 of 144

Steerable pyramid decomposition

128

Filter bank

Input image

Source: A. Efros

129 of 144

Filter response histograms

129

Fraction of pixels

Filter output

Source: A. Efros

130 of 144

Texture synthesis

130

Start with a noise image as output.

Iterative algorithm [Heeger & Bergen, 95]:

  • Match pixel histogram of output image to input
  • Decompose input/output images using a Steerable Pyramid
  • Match histograms of input and output pyramids
  • Reconstruct image and repeat

​

Later in the class we’ll see a simpler optimization method on neural nets [Gatys et al. 2015]

Source: A. Efros

131 of 144

131

Source: A. Efros

132 of 144

132

Source: A. Efros

133 of 144

Failure cases

133

Source: A. Efros

134 of 144

Nonparametric texture synthesis:

who needs pyramids or filters?

134

135 of 144

Modeling local neighborhoods

Model p(p | N(p)),

Probability of pixel given its neighbors

Source: A. Efros

132

136 of 144

Efros & Leung Algorithm

Most similar neighborhoods

non-parametric sampling

​

p

​

Input image

​

133

Source: A. Efros

  • Synthesize one pixel at a time. Want to sample: P(p|N(p)), where N(p) are the already filled-in neighbors

– Building explicit probability tables is hard

  • Instead, we search the input image for all similar neighborhoods — that’s our distribution for p
  • To sample from this distribution, just pick one match at random
  • ​

137 of 144

Neighborhood Window

input

Source: A. Efros

​

​

​

​

​

​

​

​

134

138 of 144

Varying Window Size

Increasing window size

135

Source: A. Efros

139 of 144

Synthesis Results

139

Source: A. Efros

french canvas rafia weave

140 of 144

More Results

brick wall

white bread

140

Source: A. Efros

141 of 144

Homage to Shannon

141

Source: A. Efros

142 of 144

Hole Filling (a.k.a. Inpainting)

142

Source: A. Efros

143 of 144

Extrapolation

140

Source: A. Efros

144 of 144

Today

  • Image pyramids
  • Image statistics
  • Texture synthesis

141