CS148: Introduction to Computer Graphics and Imaging

Basic Signal Processing:

Sampling, Aliasing, Antialiasing

No Jaggies

Key Concepts

Frequency space
Filters and convolution
Sampling and the Nyquist frequency
Aliasing and Antialiasing

CS148 Lecture 13 Pat Hanrahan, Fall 2011

 Frequency Space

Sines and Cosines

cos 2πx

CS148 Lecture 13
sin 2πx Pat Hanrahan, Fall 2011
Frequencies cos 2πf x

1
f= f =1
T

cos 2πx

f =2

cos 4πx
CS148 Lecture 13 Pat Hanrahan, Fall 2011

Recall Complex Exponentials

Euler’s Formula

ejx = cos x + j sin x

Odd (-x)

e−jx = cos −x + j sin −x = cos x − j sin x

Therefore
ejx + e−jx ejx − e−jx
cos x = sin x =
2 2j
Hence, use complex exponentials for sines/cosines
CS148 Lecture 13 Pat Hanrahan, Fall 2011
Constant

Spatial Domain Frequency Domain

CS148 Lecture 13 Pat Hanrahan, Fall 2011

sin(2π/32)x

Spatial Domain Frequency Domain

Frequency = 1/32; 32 pixels per cycle
CS148 Lecture 13 Pat Hanrahan, Fall 2011
sin(2π/16)x

Spatial Domain Frequency Domain

CS148 Lecture 13 Pat Hanrahan, Fall 2011

sin(2π/16)y

Spatial Domain Frequency Domain

CS148 Lecture 13 Pat Hanrahan, Fall 2011

sin(2π/32)x × sin(2π/16)y

Spatial Domain Frequency Domain

CS148 Lecture 13 Pat Hanrahan, Fall 2011

−r 2 /162
e

Spatial Domain Frequency Domain

CS148 Lecture 13 Pat Hanrahan, Fall 2011

 −r 2 /322
e

Spatial Domain Frequency Domain

CS148 Lecture 13 Pat Hanrahan, Fall 2011

−x2 /322 −y 2 /162

e ×e

Spatial Domain Frequency Domain

CS148 Lecture 13 Pat Hanrahan, Fall 2011

 −x2 /322 −y 2 /162
Rotate 45 e ×e

Spatial Domain Frequency Domain

CS148 Lecture 13 Pat Hanrahan, Fall 2011

Filtering
My Humble Frequencies

Spatial Domain Frequency Domain

CS148 Lecture 13 Pat Hanrahan, Fall 2011

Remove Low Frequencies (Edges)

Spatial Domain Frequency Domain

CS148 Lecture 13 Pat Hanrahan, Fall 2011

Remove High Frequencies (Blur)

Spatial Domain Frequency Domain

CS148 Lecture 13 Pat Hanrahan, Fall 2011

Remove Low and High Frequencies

Spatial Domain Frequency Domain

CS148 Lecture 13 Pat Hanrahan, Fall 2011

Remove Low and High Frequencies

Spatial Domain Frequency Domain

CS148 Lecture 13 Pat Hanrahan, Fall 2011

Filters = Convolution
Convolution

1 3 0 4 2 1

1 2

CS148 Lecture 13 Pat Hanrahan, Fall 2011

Convolution

1 3 0 4 2 1

1 2

1*1+3*2=7

CS148 Lecture 13 Pat Hanrahan, Fall 2011

Convolution

1 3 0 4 2 1

1 2

3*1+0*2=3

7 3

CS148 Lecture 13 Pat Hanrahan, Fall 2011

Convolution

1 3 0 4 2 1

1 2

0*1+4*2=8

7 3 8

CS148 Lecture 13 Pat Hanrahan, Fall 2011

Convolution Theorem

A filter can be implemented in the spatial domain

using convolution

A filter can also be implemented in the frequency

domain

Convert image to frequency domain

Convert filter to frequency domain

Multiply filter times image in frequency
domain

Convert result to the spatial domain

CS148 Lecture 13 Pat Hanrahan, Fall 2011

Box Filter

1 1

1 1

CS148 Lecture 13 Pat Hanrahan, Fall 2011

Box Filter = Low-Pass Filter

Spatial Domain Frequency Domain

CS148 Lecture 13 Pat Hanrahan, Fall 2011

Wider Filters, Lower Frequencies

Spatial Domain Frequency Domain

CS148 Lecture 13 Pat Hanrahan, Fall 2011

Size of Filter

As a filter is localized in space,

it spreads out in frequency
Conversely, as a filter is localized in frequency,
it spreads out in space

A box filter is very localized in space;

it has infinite extent in frequency space

CS148 Lecture 13 Pat Hanrahan, Fall 2011

Efficiency?

When would it be faster to apply the filter in the

spatial domain?

When would it be faster to apply the filter in the

frequency domain?

CS148 Lecture 13 Pat Hanrahan, Fall 2011

 Sampling

Image Generation = Sampling

Evaluating a function at a point is sampling

for( int x = 0; x < xmax; x++ )

for( int y = 0; y < ymax; y++ )
Image[x][y] = f(x,y);

Rasterization is equivalent to evaluating the

function inside(triangle,x,y)

CS148 Lecture 13 Pat Hanrahan, Fall 2011

Sampling Causes Jaggies

Retort, by Don Mitchell

Staircase pattern or jaggies

CS148 Lecture 13 Pat Hanrahan, Fall 2011

Sampling in Computer Graphics

Artifacts due to sampling - Aliasing

Jaggies – sampling in space

Wagon wheel effect – sampling in time

Temporal strobing – sampling in space-time

Moire – sampling texture coordinates

Sparkling highlights – sampling normals
Preventing these artifacts - Antialiasing

CS148 Lecture 13 Pat Hanrahan, Fall 2011

 Aliasing

Wagon Wheel Effect

[Link]
“Aliases”

These two sine waves are indistinguishable

Indistinguishable frequencies are called “aliases”
CS148 Lecture 13 Pat Hanrahan, Fall 2011

Nyquist Frequency

Definition: The Nyquist frequency is ½ the

sampling frequency (1/Ts)

Frequencies above the Nyquist frequency appear

as aliases

No aliases appear if the function being sampled

has no frequencies above the Nyquist
frequency

CS148 Lecture 13 Pat Hanrahan, Fall 2011

 Antialiasing

Antialiasing

Simple idea:

Remove frequencies above the Nyquist

frequency before sampling

How? Filtering before sampling

CS148 Lecture 13 Pat Hanrahan, Fall 2011

Prefiltering by Computing Coverage

A 1 pixel box filter removes frequencies whose

period is less than or equal to 1 pixel

Original

Filtered
CS148 Lecture 13 Pat Hanrahan, Fall 2011

Point- vs. Area-Sampled

Point Area

Checkerboard sequence by Tom Duff

CS148 Lecture 13 Pat Hanrahan, Fall 2011
Antialiasing

Jaggies Prefilter
CS148 Lecture 13 Pat Hanrahan, Fall 2011

Antialiasing vs. Blurred Aliases

Blurred Jaggies Prefilter

CS148 Lecture 13 Pat Hanrahan, Fall 2011
Things to Remember

Signal processing

Frequency domain vs. spatial domain

Filters in the frequency domain

Filters in the spatial domain = convolution
Sampling and aliasing

Image generation involves sampling

May also sample geometry, motion, …

Nyquist frequency is ½ the sampling rate

Frequencies above the Nyquist frequency
appear as other frequencies – aliases

Antialiasing – Filter before sampling
CS148 Lecture 13 Pat Hanrahan, Fall 2011

Extra Slides

Supersampling
Supersampling

Approximate a box filter by taking more samples

and averaging them together

4 x 4 supersampling

CS148 Lecture 13 Pat Hanrahan, Fall 2011

Point-sampling vs. Super-sampling

Point 4x4 Super-sampled

Checkerboard sequence by Tom Duff

CS148 Lecture 13 Pat Hanrahan, Fall 2011
Area-Sampling vs. Super-sampling

Exact Area 4x4 Super-sampled

CS148 Lecture 13 Pat Hanrahan, Fall 2011