aliasing.md

   1 # Aliasing
   2
   3 *See also [antialiasing](antialiasing.md).*
   4
   5 Aliasing is a certain typically undesirable phenomenon that distorts [signals](signal.md) (such as sounds or images) when they are [sampled](sampling.md) [discretely](discrete.md) (captured at single points, usually at periodic intervals) -- this can happen e.g. when capturing sound with digital recorders or when [rendering](rendering.md) computer graphics. There exist [antialiasing](antialiasing.md) 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 [FPS](fps.md)).
   6
   7 A simple example showing how sampling at discrete points can quite dramatically alter the recorded result:
   8
   9 ```
  10 |      .|-'-'.' '           .--.           |   |''''
  11 |  . '  |      ' .        .'    '.         |   |
  12 '|- - -O+ - -O- - .|     |  O  O  |        '---+---.
  13  |     \|_ _ /    ||     |  \__/  |            |   |
  14 _ _'_._ |      . '|       '.    .'         ____|   |
  15        ' ' ' '              ''''
  16   original image    taking even columns  taking odd columns
  17 ```
  18
  19 The following diagram shows the principle of aliasing with a mathematical function:
  20
  21 ```
  22 ^       original                     sampling period
  23 |   |               |               |<------------->|
  24 |   |             _ |           _   |         _     |
  25 | .'|'.         .' '|         .' '. |       .' '.   |
  26 |/__|__\_______/____|\_______/_____\|______/_____\__|___
  27 |   |   \     /     | \     /       \     /       \ |
  28 |   |    '._.'      |  '._.'        |'._.'         '|_.'
  29 |   |               |               |               |
  30 |   :               :               :               :
  31 V   :               :               :               :
  32     :               :               :               :
  33 ^   :               :               :               :
  34 |   :               :               :               :
  35 |---o---...____     :               :               :
  36 |   |          '''''o...____        :               :
  37 |___|_______________|______ ''''----o_______________:___
  38 |                                     '''----___    |
  39 |                                               ''''o---
  40 |     reconstructed
  41 |
  42 V
  43 ```
  44
  45 The top signal is a [sine](sin.md) function of a certain [frequency](frequency.md). 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.
  46
  47 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.
  48
  49 The explanation above shows why a helicopter's rotating blades look to stand still in a video whose [FPS](fps.md) 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.
  50
  51 Of course this doesn't only happen with perfect sine waves. [Fourier transform](fourier_transform.md) shows that any signal can be represented as a sum of different sine waves, so aliasing can appear anywhere.
  52
  53 **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 [low pass filter](low_pass.md) 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.
  54
  55 Aliasing is also a common problem in [computer graphics](computer_graphics.md). 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).
  56
  57 The same thing may happen in [ray tracing](ray_tracing.md) if we shoot a single sampling ray for each screen pixel. Note that [interpolation/filtering](interpolation.md) of textures won't fix texture aliasing. What can be used to reduce texture aliasing are e.g. by [mipmaps](mipmap.md) 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 [anisotropic filtering](anisotropic_filtering.md)). However even if we sufficiently suppress aliasing in textures, aliasing can still appear in geometry. This can be reduced by [multisampling](multisampling.md), 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.
  58
  59 **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 [integrate](integration.md). 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 [motion blur](motion_blur.md)).
  60
  61 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).