Lecture 3: Image pyramids
1
Announcements
2
Today
3
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?
Review: steerable filters
5
= ?
+
=
Use a multivariable calculus fact:
Directional derivative = linear combination of partial derivatives.
Source: N. Snavely
Given and , steer to direction .
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
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
Decomposing an image
Gaussian filter
(a.k.a. “low pass”)
7
Source: Torralba, Freeman, Isola
Are there filters that does the opposite?
2nd derivatives
1
-1
1
-1
1 | -2 | 1 |
≈
∂f 2
∂x2
∂f
∂x
∂f
∂x
8
Laplacian filter
+
∂I2 ∂I2
∂x2 ∂y2
≈
I ∘
9
0 | 1 | 0 |
1 | -4 | 1 |
0 | 1 | 0 |
Laplacian filter
∘
=
Detects edges and blobs, and not sensitive to orientation. But sensitive to noise.
10
Source: Torralba, Freeman, and Isola
Laplacian of Gaussian
Combine with Gaussian. Picks up “blob-like” structures.
∘
=
11
“Blob” detection with Laplacian
12
σ = 12
Source: S. Lazebnik
Difference of Gaussians
Subtract two blurry images from each other.
Source: S. Laze1b3nik
Can be shown to be a good approximation.
Decomposing an image
+
15
Source: Torralba, Freeman, Isola
-
-
Gaussian filter
(a.k.a. “low pass”)
Approx. Laplacian
(a.k.a. “high pass”)
Approx. Laplacian
-
+
-
+
=
Gaussian filter
16
Source: Torralba, Freeman, Isola
At a distance, we see only low frequencies!
Application: Hybrid Images
Source: S. Lazeb18nik
[A. Oliva, A. Torralba, P.G. Schyns, Hybrid Images, SIGGRAPH 2006]
Hybrid Images
Oliva & Schyns19
Hybrid Images
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
=
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!
Generating both components?
"a lithograph of flowers”
”a lithograph of a panda"
"a photo of a canyon”
”a photo of gandhi”
"a lithograph of waterfalls”
”a lithograph of a pig”
Thanks to Walter Scheirer and Luba Elliot for suggesting this!
The Core Challenge: Preserving Detail During Calibration
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
Today
31
Denoising revisited: salt and pepper noise
Gaussian filter doesn’t work as well!
32
Source: S. Lazebnik
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
Median filtering
Recall: box filtering
38
Filter kernel
Recall: box filtering
39
Filter kernel
Recall: box filtering
Filter kernel
Recall: box filtering
41
Filter kernel
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 | |
| | | | | | |
Median filtering
Median filtering
Median filtering
Median filtering
Median filtering
Median filtering
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 | |
| | | | | | |
…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 | |
| | | | | | |
Median filtering window sizes
Original
w = 5
w = 13
w = 21
51
Idea: weight by visual similarity
Bilateral filtering
p
q
||p - q||
What if we weight by appearance?
53
Bilateral filtering
54
Bilateral filtering
[Paris et al. “A Gentle Introduction to Bilateral Filtering and its Applications”, 2008]
52
Bilateral filter
[Paris et al. “A Gentle Introduction to Bilateral Filtering and its Applications”, 2008]
53
Denoising with Gaussian
Noisy image
Gaussian blur = 3
Gaussian blur = 5
57
Source: [Paris et al. 2008]
Denoising with Bilateral Filter
Original
58
Source: [Paris et al. 2008]
Noisy image
Bilateral filtering
Iteratively applying the filter
59
Source: [Paris et al. 2008]
Image patches as filters
Source: D. Hoiem
57
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
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
Matching with filters
Method 3: Normalized cross-correlation.
Divide by standard deviation of both patches, so they are unit vectors.
60
Source: D. Hoiem
Matching with filters
Input
Normalized61X-Correlation
Thresholded Image
True detections
Method 3: Normalized cross-correlation.
Source: D. Hoiem
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
Recognizing objects: is it really so hard?
66
Find the chair in this image
Not so great!
Source: A. Torralba
Today
64
We want scale invariance!
Source: Torralba, Freeman, I6s5ola
Image pyramids
69
Source: Torralba, Freeman, Isola
Image pyramid
1/2
1/2
1/2
1/2
70
Source: Torralba, Freeman, Isola
Subsampling and aliasing
1/2
1/2
Source: Torralba, Freeman, Isola
Idea #1: Throw away every other pixel.
68
What’s happening?
Consider a sinusoid:
72
Source: S. Marschner
Undersampling
73
Source: S. Marschner
Undersampling
Source: Wikipedia
74
Removing aliasing
Blur
75
Source: Torralba, Freeman, Isola
Gaussian pyramid
For each level:
1. Blur input image with a Gaussian (or binomial) filter
Blur
76
Source: Torralba, Freeman, Isola
Gaussian pyramid
For each level:
77
Source: Torralba, Freeman, Isola
Gaussian pyramid
256×256
128×128
64×64
32×32
2
2
2
78
Source: Torralba, Freeman, Isola
Gaussian pyramid
512×512
79
Source: Torralba, Freeman, Isola. Image from Forsyth & Ponce
(original image)
Gaussian pyramid
For each level
80
Source: Torralba, Freeman, Isola
Recall: Laplacian
+
78
Source: Torralba, Freeman, Isola
-
-
Gaussian filter (a.k.a. “low pass”)
Approx. Laplacian
(a.k.a. “high pass”)
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
Laplacian Pyramid
Gaussian pyramid
Source: Torralba, Freeman, Is8o9la
Laplacian Pyramid
Gaussian pyramid
Source: Torralba, Freeman, Is8o1la
Laplacian pyramid
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) = ????
Upsampling
=
64x64
Insert zeros
128x128
Source: Torralba, Freeman, Is8o3la
128x128
Laplacian Pyramid
Gaussian pyramid
Source: Torralba, Freeman, Is8o4la
Laplacian pyramid
Laplacian Pyramid
Gaussian pyramid
Source: Torralba, Freeman, Is8o5la
High frequencies
things that change fast
Low frequencies
things that change slowly
Laplacian Pyramid
Gaussian residual
Laplacian pyramid
Can we invert the Laplacian Pyramid?
Source: Torralba, Freeman, Is8o6la
Laplacian Pyramid
Gaussian pyramid
Laplacian pyramid
Source: Torralba, Freeman, Is8o7la
Laplacian Pyramid
Gaussian pyramid
Laplacian pyramid
Analysis/Encoder
Synthesis/Decoder
Source: Torralba, Freeman,8I8sola
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]
"a lithograph of waterfalls”
”a lithograph”aofliathsokgurlalp”h of a yin yang”
More Laplacian pyramid applications
Source: Torralba, Freeman, Is9o1la
Image Blending
Source: Torralba, Freeman, Is9o2la
Image Blending
Source: Torralba, Freeman, Is9o3la
Image Blending
I A
Source: Torralba, Freeman, Is9o4la
I B
m
I
I = m * IA + (1 − m) * IB
What if you blurred the mask?
m
IA
IB
I
I = m * IA + (1 − m) * IB
Better, but it loses texture at boundary.
95
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
Image Blending with the Laplacian Pyramid
Source: Torralba, Freeman, Is9o7la
+
=
Simple blend
With Laplacian pyr.
Source: A. Efros
98
Photo credit: Chris Cameron
Source: A. Efros
99
Image Blending (PS2 problem)
Source: Torralba, Freeman, I1s0o0la
Image pyramids
Gaussian Pyramid Laplacian Pyramid
And many more: steerable filters, wavelets, … (and later) convolutional networks!
101
Source: Torralba, Freeman, Isola
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:
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
Laplacian Pyramid
Blurring and downsampling:
Upsampling and blurring:
(blur)
(Downsampling by 2)
(Upsampling by 2)
(blur)
Source: Torralba, Freeman, I1s0o4la
The Laplacian Pyramid
Source: Torralba, Freeman, I1s0o5la
Laplacian Pyramid
Gaussian pyramid
Laplacian pyramid
l0
g2
l1
=
Source: Torralba, Freeman, I1s0o6la
Linear Image Transforms
Gaussian pyramid
Laplacian pyramid
107
Source: Torralba, Freeman, Isola
For more powerful nonlinear models…
convolutional neural networks
[LeCun et al. 1989]
108
Other topics (optional)
109
What makes an image “natural”?
Natural image
“Fake” image
110
Source: Torralba, Freeman, Isola
Is it the distribution of pixel intensities?
Intensity histogram
111
No real structure here…
What about gradients?
g[m,n]
h[m,n]
=
f[m,n]
[-1, 1]
115
Source: Torralba, Freeman, Isola
What about gradients?
g[m,n]
h[m,n]
=
f[m,n]
[-1, 1]T
116
Source: Torralba, Freeman, Isola
Filter response distribution is pretty consistent!
117
Source: Torralba, Freeman, Isola
Image
[1 -1] output histogram
Red – true pdf
Black – best Gaussian fit
[1 -1] filter output
Intensity histogram
115
Source: Torralba, Freeman, Isola
Today
116
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
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
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
1st order statistics differ
123
5% white
Source: A. Efros
20% white
2nd order statistics differ
124
10% white
Source: A. Efros
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
Can you match the texture to the response?
126
3
Mean abs. responses
Filters
Source: A. Efros
A
B
C
1
2
How can we represent texture?
127
Source: A. Efros
Steerable pyramid decomposition
128
Filter bank
Input image
Source: A. Efros
Filter response histograms
129
Fraction of pixels
Filter output
Source: A. Efros
Texture synthesis
130
Start with a noise image as output.
Iterative algorithm [Heeger & Bergen, 95]:
Later in the class we’ll see a simpler optimization method on neural nets [Gatys et al. 2015]
Source: A. Efros
131
Source: A. Efros
132
Source: A. Efros
Failure cases
133
Source: A. Efros
Nonparametric texture synthesis:
who needs pyramids or filters?
134
Modeling local neighborhoods
Model p(p | N(p)),
Probability of pixel given its neighbors
Source: A. Efros
132
Efros & Leung Algorithm
Most similar neighborhoods
non-parametric sampling
p
Input image
133
Source: A. Efros
– Building explicit probability tables is hard
Neighborhood Window
input
Source: A. Efros
134
Varying Window Size
Increasing window size
135
Source: A. Efros
Synthesis Results
139
Source: A. Efros
french canvas rafia weave
More Results
brick wall
white bread
140
Source: A. Efros
Homage to Shannon
141
Source: A. Efros
Hole Filling (a.k.a. Inpainting)
142
Source: A. Efros
Extrapolation
140
Source: A. Efros
Today
141