Aliasing
See also [1]antialiasing.
Aliasing is a certain typically undesirable phenomenon that distorts
[2]signals (such as sounds or images) when they are [3]sampled
[4]discretely (captured at single points, usually at periodic intervals)
-- this can happen e.g. when capturing sound with digital recorders or
when [5]rendering computer graphics. There exist [6]antialiasing methods
for suppressing or even eliminating aliasing. Aliasing can be often seen
on small checkerboard patterns as a moiré pattern (spatial aliasing), or
maybe more famously on rotating wheels or helicopter rotor blades that in
a video look like standing still or rotating the other way (temporal
aliasing, caused by capturing images at intervals given by the camera's
[7]FPS).
A simple example showing how sampling at discrete points can quite
dramatically alter the recorded result:
| .|-'-'.' ' .--. | |''''
| . ' | ' . .' '. | |
'|- - -O+ - -O- - .| | O O | '---+---.
| \|_ _ / || | \__/ | | |
_ _'_._ | . '| '. .' ____| |
' ' ' ' ''''
original image taking even columns taking odd columns
The following diagram shows the principle of aliasing with a mathematical
function:
^ original sampling period
| | | |<------------->|
| | _ | _ | _ |
| .'|'. .' '| .' '. | .' '. |
|/__|__\_______/____|\_______/_____\|______/_____\__|___
| | \ / | \ / \ / \ |
| | '._.' | '._.' |'._.' '|_.'
| | | | |
| : : : :
V : : : :
: : : :
^ : : : :
| : : : :
|---o---...____ : : :
| | '''''o...____ : :
|___|_______________|______ ''''----o_______________:___
| '''----___ |
| ''''o---
| reconstructed
|
V
The top signal is a [8]sine function of a certain [9]frequency. We are
sampling this signal at periodic intervals indicated by the vertical lines
(this is how e.g. digital sound recorders record sounds from the real
world). Below we see that the samples we've taken make it seem as if the
original signal was a sine wave of a much lower frequency. It is in fact
impossible to tell from the recorded samples what the original signal
looked like.
Let's note that signals can also be two and more dimensional, e.g. images
can be viewed as 2D signals. These are of course affected by aliasing as
well.
The explanation above shows why a helicopter's rotating blades look to
stand still in a video whose [10]FPS is synchronized with the rotation --
at any moment the camera captures a frame (i.e. takes a sample), the
blades are in the same position as before, hence they appear to not be
moving in the video.
Of course this doesn't only happen with perfect sine waves. [11]Fourier
transform shows that any signal can be represented as a sum of different
sine waves, so aliasing can appear anywhere.
Nyquist-Shannon sampling theorem says that aliasing can NOT appear if we
sample with at least twice as high frequency as that of the highest
frequency in the sampled signal. This means that we can eliminate aliasing
by using a [12]low pass filter before sampling which will eliminate any
frequencies higher than the half of our sampling frequency. This is why
audio is normally sampled with the rate of 44100 Hz -- from such samples
it is possible to correctly reconstruct frequencies up to about 22000 Hz
which is about the upper limit of human hearing.
Aliasing is also a common problem in [13]computer graphics. For example
when rendering textured 3D models, aliasing can appear in the texture if
that texture is rendered at a smaller size than its resolution (when the
texture is enlarged by rendering, aliasing can't appear because
enlargement decreases the frequency of the sampled signal and the sampling
theorem won't allow it to happen). (Actually if we don't address aliasing
somehow, having lower resolution textures can unironically have beneficial
effects on the quality of graphics.) This happens because texture samples
are normally taken at single points that are computed by the texturing
algorithm. Imagine that the texture consists of high-frequency details
such as small checkerboard patterns of black and white pixels; it may
happen that when the texture is rendered at lower resolution, the
texturing algorithm chooses to render only the black pixels. Then when the
model moves a little bit it may happen the algorithm will only choose the
white pixels to render. This will result in the model blinking and
alternating between being completely black and completely white (while it
should rather be rendered as gray).
The same thing may happen in [14]ray tracing if we shoot a single sampling
ray for each screen pixel. Note that [15]interpolation/filtering of
textures won't fix texture aliasing. What can be used to reduce texture
aliasing are e.g. by [16]mipmaps which store the texture along with its
lower resolution versions -- during rendering a lower resolution of the
texture is chosen if the texture is rendered as a smaller size, so that
the sampling theorem is satisfied. However this is still not a silver
bullet because the texture may e.g. be shrink in one direction but
enlarged in other dimension (this is addressed by [17]anisotropic
filtering). However even if we sufficiently suppress aliasing in textures,
aliasing can still appear in geometry. This can be reduced by
[18]multisampling, e.g. sending multiple rays for each pixel and then
averaging their results -- by this we increase our sampling frequency and
lower the probability of aliasing.
Why doesn't aliasing happen in our eyes and ears? Because our senses don't
sample the world discretely, i.e. in single points -- our senses
[19]integrate. E.g. a rod or a cone in our eyes doesn't just see exactly
one point in the world but rather an averaged light over a small area
(which is ideally right next to another small area seen by another cell,
so there is no information to "hide" in between them), and it also doesn't
sample the world at specific moments like cameras do, its excitation by
light falls off gradually which averages the light over time, preventing
temporal aliasing (instead of aliasing we get [20]motion blur).
So all in all, how to prevent aliasing? As said above, we always try to
satisfy the sampling theorem, i.e. make our sampling frequency at least
twice as high as the highest frequency in the signal we're sampling, or at
least get close to this situation and lower the probability of aliasing.
This can be done by either increasing sampling frequency (which can be
done smart, some methods try to detect where sampling should be denser),
or by preprocessing the input signal with a low pass filter or otherwise
ensure there won't be too high frequencies (e.g. using lower resolution
textures).
Links:
1. antialiasing.md
2. signal.md
3. sampling.md
4. discrete.md
5. rendering.md
6. antialiasing.md
7. fps.md
8. sin.md
9. frequency.md
10. fps.md
11. fourier_transform.md
12. low_pass.md
13. computer_graphics.md
14. ray_tracing.md
15. interpolation.md
16. mipmap.md
17. anisotropic_filtering.md
18. multisampling.md
19. integration.md
20. motion_blur.md