Fourier transforms
and rescaling
Fourier transforms
Fourier Fourier
Image Image
transform transform
Low-pass filtering
* Fourier
=
Fourier
* =
High-pass filtering
- =
- =
Band-pass filtering
- =
- =
- =
Hybrid images (PA1)
Hybrid images (PA1)
Hybrid images (PA1)
Resizing and
resampling
Let’s enhance!
Louis Daguerre, 1838
Let’s enhance!
• When is enhancement possible?
• How can we model what happens when we
upsample or downsample an image?
• Resizing up or down very common operation
• Searching across scales
• applications have different memory/quality tradeoffs
What is a (digital) image?
• True image is a function from R2 to R
• Digital image is a sample from it
• 1D example:
• To enhance, we need to recover the original signal
and sample again
Undersampling
© Kavita Bala, Computer Science, Cornell University
Undersampling
• What if we “missed” things between the samples?
• Simple example: undersampling a sine wave
• unsurprising result: information is lost
• surprising result: indistinguishable from lower frequency
• also was always indistinguishable from higher frequencies
• aliasing: signals “traveling in disguise” as other
frequencies
Aliasing
• When sampling is not adequate, impossible to
distinguish between low and high frequency
signal
© Kavita Bala, Computer Science, Cornell University
Aliasing in time
Aliasing in time
Image Scaling
What happens if we naively
upsample?
Source: S. Seitz
Image sub-sampling
1/16
1/4
Throw away every other row and
column to create a 1/2 size image
- called image sub-sampling
Source: S. Seitz
Image sub-sampling
1/2 1/4 (2x zoom) 1/16 (4x zoom)
Why does this look so crufty? Aliasing!
Source: S. Seitz
Image sub-sampling
Source: F. Durand
Point sampling
in action
Cornell CS4620 Fall 2015 • Lecture
How many samples do we
need?
• 1 sample per time period is too less:
How many samples do we
need?
• 2 samples per time-period is enough
• Nyquist sampling theorem: Need to sample at least
2 times the frequency
• General signals? Need to sample at least 2 times
the maximum frequency
Nyquist sampling: why?
Spatial domain Frequency
domain
Sampling = Keep values at , Sampling = Make frequency
make everything else 0 domain periodic with period
by making copies
Nyquist sampling: why?
Nyquist sampling: why?
Aliasing and downsampling
• Nyquist says must sample at at least twice maximum
frequency
• When downsampling by a factor of two
• Original image has frequencies that are too high
• How can we fix this?
• Eliminate them before sampling!
• Convert to frequency space
• Multiply with low-pass filter
Eliminating
High
Frequencies
© Kavita Bala, Computer Science, Cornell University
Process
• Can we do this in spatial domain?
• Yes!
• Multiplication in frequency domain
= convolution in spatial domain
• Box filter in frequency domain =
sinc in spatial domain
• Multiplication with box filter in
frequency domain = convolution
with sinc filter in spatial domain
Reconstruction from
samples
Spatial domain Frequency
domain
Sampling = Keep values at , Sampling = Make frequency
make everything else 0 domain periodic with period
by making copies
Reconstruction from
samples
Box filter in frequency
space
Reconstruction from
samples
• Multiplication in frequency domain = convolution in
spatial domain
• Box filter in frequency domain = sinc filter in spatial
domain
• Convolve sampled signal with sinc filter to
reconstruct
Reconstruction from
samples
• ”Sampled signal” is non-zero at sample points and 0
everywhere else
• i.e., has holes
*
Recap: subsampling and
reconstruction
Subsampling Reconstruction
1. Convolve with sinc 1. Start with sampled
filter to eliminate signal (0 at non-
high frequencies sample points)
2. Sample by picking 2. Convolve with sinc to
only values at sample reconstruct
points
Sinc is annoying
Sinc and Gaussian
• Sinc is annoying: infinite spatial extent
• Use Gaussian instead!
Sinc/box
Gaussian
Spatial domain Frequency domain
Subsampling images
• Step 1: Convolve with Gaussian to eliminate high
frequencies
• Step 2: Drop unneeded pixels
Subsampling without removing Subsampling after removing
high frequencies high frequencies
Subsampling images
correctly
G 1/8
G 1/4
Gaussian 1/2
• Solution: filter the image, then subsample
Source: S. Seitz
Subsampling with Gaussian pre-
filtering
Gaussian 1/2 G 1/4 G 1/8
• Solution: filter the image, then subsample
Source: S. Seitz
Compare with...
1/2 1/4 (2x zoom) 1/8 (4x zoom)
Source: S. Seitz
Upsampling images
Step 1: blow up to
original size with 0’s
in between
Upsampling images
Step 2: Convolve with
Gaussian
Take-away
• Subsampling causes aliasing
• High frequencies masquerading as low frequencies
• Remove low frequencies by blurring!
• Ideal: sinc
• Common: Gaussian
• When upsampling, reconstruct missing values by
convolution
• Ideal: sinc
• Common: Gaussian
So… can we enhance?
• Nyquist theorem limits frequencies we can
reconstruct from subsampled image
• Can only reconstruct max sampling frequency/2
• Sorry CSI!
Pyramids
Gaussian
pre-filtering
• Solution: filter
the image, then
subsample
F0 F1 F2
blur subsample blur subsample …
F0 * H F1 * H
{
Gaussian
pyramid
blur
F0
subsample blur
F1
subsample
F2
…
F0 * H F1 * H
Gaussian pyramids
[Burt and Adelson, 1983]
• In computer graphics, a mip map [Williams, 1983]
Gaussian Pyramids have all sorts of applications in computer vision
Source: S. Seitz
Gaussian pyramids -
Searching over scales
Gaussian pyramids -
Searching over scales
The Gaussian Pyramid
Low resolution G4 (G3 * gaussian ) 2
blur ) 2 sub-sample
G3 (G2 * gaussian
sub-samp
blur le
G2 (G1 * gaussian ) 2
s ub-
sam
pl e
blur
G11 (G0 * gaussian ) 2
su
b-
sa
mp
le
G0 Image blur
High resolution
Gaussian pyramid and stack
Source: Forsyth
Memory Usage
• What is the size of the pyramid?
5
4
Laplacian pyramid
Expand (up
s ample + bl
ur)
Expand (up
s - ample + bl
ur)
=
Expand (up- =
s am p le + blur)
Re-
duce - =
Expand (up
s ample + bl
ur)
- =
Laplacian pyramid
L 4 = G4 =
L3 = G3 - expand(G4) =
L2 = G2 - expand(G3) =
L1 = G1 - expand(G2) =
L0 = G0 - expand(G1) =
Reconstructing the image
from a Laplacian pyramid
lur)
(u p s a m p le + b
Expand
+ s a m
=p le + blur)
Expand (up
+ (u p
=
s a m p le + blur)
Exp an d
+ =
sample + blur)
Expand (up
+ =
Laplacian pyramid
Source: Forsyth
