[CS5670] Lecture 3: Image Resampling & Interpolation

| Today's topic is Sampling & interpolation.

 

| Key points

• Subsampling an image can cause aliasing. Better is to blur (“pre-filter”) to remote high frequencies then downsample
• If you repeatedly blur and downsample by 2x, you get a Gaussian pyramid
• Upsampling an image requires interpolation. This can be posed as convolution with a “reconstruction kernel”

 

Image scaling

 

 

This image is too big to fit on the screen. How can we generate a half-sized version?

 

Image scaling

 

 

Throw away every other row and column to create a 1/2 size image

• called image sub-sampling

 

 

Why does this look so crufty?

 

Image sub-sampling - another example

 

 

Even worse for synthetic images

 

 

 

 

 

Aliasing

 

 

• Occurs when your sampling rate is not high enough to capture the amount of detail in your image
• Can give you the wrong signal/image - an alias
• To do sampling right, need to understand the structure of your signal/image
• Enter Monsieur Fourier…
  • “But what is the Fourier Transform? A visual introduction.”
  • https://www.youtube.com/watch?v=spUNpyF58BY
• To avoid aliasing:
  • sampling rate ≥ 2 * max frequency in the image
    • said another way: ≥ two samples per cycle
  • This minimum sampling rate is called the Nyquist rate

 

Wagon-wheel effect

 

• Imagine a spoked wheel moving to the right (rotating clockwise).
• Mark wheel with dot so we can see what's happening.
• If camera shutter is only open for a fraction of a frame time (frame time = 1/30 sec. for video, 1/24 sec. for film):

 

 

Without dot, wheel appears to be rotating slowly backwards! (counterclockwise)

 

Nyquist limit - 2D example

 

 

 

 

 

 

Aliasing

 

• When downsampling by a factor of two
  • Original image has frequencies that are too high
• How can we fix this?

 

 

Gaussian pre-filtering

 

 

• Solution: filter the image, then subsample

 

 

Subsampling with Gaussian pre-filtering

 

 

• Solution: filter the image, then subsample

 

Compare with...

 

 

Gaussian pre-filtering

 

 

• Solution: filter the image, then subsample

 

 

 

Gaussian pyramids [Burt and Adelson, 1983]

 

 

• In computer graphics, a mip map [Williams, 1983]
• A precursor to wavelet transform Gaussian Pyramids have all sorts of applications in computer vision

 

Gaussian Pyramids have all sorts of applications in computer vision.

 

• How much space does a Gaussian pyramid take compared to the original image?

 

Gaussian pyramid

 

 

Question❓

 

How much space (number of pixels) does a Gaussian pyramid of an image take compared to the original image?

 

Back to the checkerboard

 

• What should happen when you make the checkerboard smaller and smaller?

 

 

Upsampling

 

• This image is too small for this screen: 
• How can we make it 10 times as big?
• Simplest approach: repeat each row and column 10 times
• ("Nearest neighbor interpolation")

 

 

Image interpolation

 

 

Recall that a digital images is formed as follows:

 

$$F[x, y] = quantize \left\{ f(xd, yd) \right\} $$

 

• It is a discrete point-sampling of a continuous function
• If we could somehow reconstruct the original function, any new image could be generated, at any resolution and scale

 

 

 

What if we don't know $f$?

• Guess an approximation: $\tilde{f}$
• Can be done in a principled way: filtering
• Convert $F$ to a continuous function:
  • $f_F (x) = F (\frac{x}{d})$ when $\frac{x}{d}$ is an integer, 0 otherwise
• Reconstruct by convolution with a reconstruction filter, $h$

 

 

 

Reconstruction filters

What does the 2D version of this hat function look like?

 

 

• Often implemented without cross-correlation
  • E.g., http://en.wikipedia.org/wiki/Bilinear_interpolation
• Better filters give better resampled images
  • Bicubic is common choice

 

 

Image interpolation

 

 

 

Raster-to-vector graphics

 

 

 

Depixelating Pixel Art

 

 

Modern methods

 

 

Super-resolution with multiple images

 

• Can do better upsampling if you have multiple images of the scene taken with small (subpixel) shifts
• Some cellphone cameras (like the Google Pixel line) capture a burst of photos
• Can we use that burst for upsampling?

 

Google Pixel 3 Super Res Zoom

 

 

Effect of hand tremor as seen in a cropped burst of photos, after global aligbnment

 

 

Example photo with and without super res zoom (smart burst align and merge)

 

 

Reference: Lecture 1: Images and image filtering