Aliasing

From Wikipedia, the free encyclopedia

This article applies to signal processing, including computer graphics. For uses in computer programming, please refer to aliasing (computing).

In statistics, signal processing, and related disciplines, aliasing is an effect that causes different continuous signals to become indistinguishable (or aliases of one another) when sampled.

Aliasing also refers to the distortion or artifact that is caused by a signal being sampled and reconstructed as an alias of the original signal.

By either meaning, aliasing can take place either in time (temporal aliasing) or in space (spatial aliasing).

Aliasing is a major concern in the analog-to-digital conversion of video and audio signals: improper sampling of the analog signal will cause high-frequency components to be aliased with genuine low-frequency ones, and to be incorrectly reconstructed as such during the subsequent digital-to-analog conversion. To prevent this problem, the sampling frequency must be sufficiently large and the signals must be appropriately filtered before sampling.

Aliasing is also a major concern in digital imaging and computer graphics, where it may give rise to moiré patterns when the original image is finely textured, or to jagged outlines when the original has sharp contrasting edges. Anti-aliasing techniques are used to reduce such artifacts.

[edit] Overview

Two different sinusoids that give the same samples; a high frequency <math>f > f_s/2 \,</math> (red) and an alias at <math>f_s-f \,</math> (blue).

[edit] Aliasing in periodic phenomena

The sun moves east to west in the sky, with 24 hours between sunrises. If one were to take a picture of the sky every 23 hours, the sun would appear to move west to east, with 24 × 23 = 552 hours between sunrises. Note that both motions would result in the same pictures. The same phenomenon causes the wagon-wheel effect, spoked wheels to apparently turn at the wrong speed or in the wrong direction when filmed, or illuminated with a flashing light source — such as fluorescent lamp, a CRT, or a strobe light. These are examples of temporal aliasing.

If someone wearing a tweed jacket with a pronounced herringbone pattern was videoed, and the video played on a TV screen with a smaller number of lines than the image of the pattern or on a computer monitor with pixels larger than the elements of the pattern, then one would see large areas of darkness and lightness over the image of the jacket and not the herringbone pattern. This is an example of spatial aliasing, also known as a moiré pattern; how it is produced is illustrated next.

[edit] Sampling a periodic signal

In the same way, when a sinusoidal signal measured or sampled at regular but not sufficiently close intervals, one will obtain the same sequence of samples that would be obtained from a sinusoid of a lower frequency. Specifically, if a sinusoid of frequency <math>f\,</math> (in cycles per second for a time-varying signal, or in cycles per centimeter for space-varying signal) is sampled <math>f_s\,</math> samples per second or per centimeter, the resulting samples will also be compatible with a sinusoid of frequency <math>Nf_s - f\,</math> and one of frequency <math>Nf_s + f\,</math>, for any integer <math>N\,</math>. If <math>f_s > 2f\,</math>, the lowest of these image frequencies will be the original signal frequency, but otherwise it will not. In the case that <math>f_s < 2f < 2f_s\,</math>, the lowest image frequencies will be at <math>f_s - f\,</math>, the lowest image frequency in a sense masquerades as the sinusoid that was sampled and is called an alias of the sinusoid that was actually sampled, albeit inadequately sampled.

If a sample sequence is used to reconstruct a continuous-time waveform via the Whittaker–Shannon interpolation formula or other lowpass technique, then the lowest-frequency alias will be the one that appears in the reconstruction. In these typical cases, sampling at a rate <math>f_s\,</math> greater than twice the highest frequency expected of any sinusoidal component in the input will generally prevent the distortion known as aliasing. In other reconstruction methods, under suitable restrictive conditions, aliasing in reconstruction can be prevented under more general conditions discussed below, even when <math>f_s\,</math> is not greater than twice the signal frequencies.

[edit] The Nyquist criterion

Image:CriticalSamplingFrequency.png One way to avoid such aliasing is to make sure that the signal does not contain any sinusoidal component with a frequency equal to or greater than <math>f_s/2</math>. More generally, this condition can be generalized to allow energy in some band or set of bands such that no frequencies that are aliases of each other with respect to the sample rate (according to the formulas above, for any and all values of <math>N</math>) are present in the signal.

This condition is sometimes called the Nyquist criterion, and is equivalent to saying that the sampling frequency <math>f_s</math> must be high enough; either greater than twice the highest frequency or some other more complicated criterion.

In the case of a single band of width B with lower and upper frequency limits <math>f_1</math> and <math>f_2</math>, the criterion was incompletely spelled out by Harold Stephen Black in his 1953 book Modulation Theory. The criterion he states is that the minimum sampling rate is <math>2f_2/m</math>, where <math>m</math> is the largest integer not exceeding <math>f_2/B</math>. See the plot to the right, where the segments correspond to integer values of <math>m</math> starting with 1. He does point out, however, that this lower bound is not a sufficient condition, since higher sampling frequencies will lead to aliasing in some cases, saying simply, "Obviously, not all higher rates are necessarily usable." The more complete criterion is spelled out in Nyquist–Shannon sampling theorem#Undersampling.

[edit] Origin of the term

The term "aliasing" derives from the usage in radio engineering, where a radio signal could be picked up at two different positions on the radio dial in a superheterodyne radio: one where the local oscillator was above the radio frequency, and one where it was below. This is analogous to the frequency-space "wrapround" that is one way of understanding aliasing.

[edit] An audio example

The qualitative effects of aliasing can be heard in the following audio demonstration. Six sawtooth waves are played in succession, with the first two sawtooths having a fundamental frequency of 440 Hz (A4), the second two having fundamental frequency of 880 Hz (A5), and the final two at 1760 Hz (A6). The sawtooths alternate between bandlimited (non-aliased) sawtooths and aliased sawtooths and the sampling rate is 22.05 kHz. The bandlimited sawtooths are synthesized from the sawtooth waveform's Fourier series such that no harmonics above the Nyquist frequency are present.

The aliasing distortion in the lower frequencies is increasingly obvious with higher fundamental frequencies, and while the bandlimited sawtooth is still clear at 1760 Hz, the aliased sawtooth is degraded and harsh with a buzzing audible at frequencies lower than the fundamental. Note that the audio file has been coded using Ogg's Vorbis codec, and as such the audio is somewhat degraded.

• Sawtooth aliasing demo {440 Hz bandlimited, 440 Hz aliased, 880 Hz bandlimited, 880 Hz aliased, 1760 Hz bandlimited, 1760 Hz aliased}

[edit] Mathematical explanation of aliasing

The preceding explanation and the Nyquist criterion are somewhat idealised, because they assume instantaneous sampling and other slightly unrealistic hypotheses, although useful approximations to these things do exist. The following is a more detailed explanation of the phenomenon in terms of function approximation theory.

[edit] Continuous signals

For the purposes of this analysis, we define a continuous-time signal as a real or complex valued function whose domain is the interval [0,1]. To quantify the "magnitude" of a signal (and, in particular, to measure the difference between two signals), we will use the root mean square norm (see L_p spaces for some details), namely

<math>||f||^2 := \int_0^1|f(t)|^2\,dt.</math>

Accordingly, we will consider only signals that have finite norm, i.e. the square-integrable functions

<math>L^2=L^2([0,1]):=\left\{ f:[0,1] \rightarrow \Bbb C : ||f||<\infin\right\}.\,</math>

Note that these signals need not be continuous as functions; the adjective "continuous" refers only to the domain.

To be precise, we do not distinguish between functions that differ only on sets of zero measure. This technicality turns || || into a norm, and explains some of the difficulties (see the S₀ sampling method, below.) For details, see Lp spaces.

[edit] Point sampling

The conversion of a continuous signal f to an n-dimensional vector of equally spaced samples (a sampled signal) can be modeled as a point sampling operator <math>S_0</math>, defined by <math>S_0 f := (f(t_1), f(t_2), \dots, f(t_n))</math>, where <math>t_i = i/n</math>. That is, the function is sampled at the points <math>1/n, 2/n, \dots, 1.\,</math>

Note that <math>S_0</math> is a linear map: for any two signals f and g, and any scalar a, then <math>S_0(af+g)=aS_0(f)+S_0(g).\,</math>

Unfortunately, while <math>S_0(f)</math> is well-defined if f is continuous (say), it is not well defined on the space <math>L^2</math> defined above. A symptom of this is, even if we restrict our attention to functions f that are continuous, function <math>S_0</math> of f is not continuous in the <math>L^2</math> norm.

In many physically significant settings, the <math>L^2</math> norm, or a similar norm, is an appropriate measure of similarity between signals. What will then happen is that two signals f and g that are deemed very similar to begin with will sample to two signals <math>S_0f</math> and <math>S_0g</math> which are very dissimilar.

[edit] A better sampling method (filtering)

In order to preserve closeness of signals after sampling (in other words, to get a sampling method which varies smoothly as a function of the signal f) we need to modify our sampling strategy <math>S_0</math>. An improved method is as follows:

<math>S_1f(k)=n \int_{(k-1)/n}^{k/n} f(t)dt, k=1,...,n</math>

This is a better filtering method, as <math>S_1\,</math> is now a continuous linear map from <math>L^2\,</math> to <math>\Bbb C^n</math>.

This sampling method is also a better model of how an actual machine might sample a signal. For instance, telescopes sample light signals by accumulating photons on a film or CCD receptor. The resulting image is therefore approximately the integral of all the electrons received over a period of time and over a rectangular region of the image plane.

This rectangle function filter is just one of many possible filters for sampling. In the frequency domain, it is a lowpass sinc-shaped filter, with the first zero at a frequency of one cycle per sample, which is twice the Nyquist frequency. This zero removes all the signal energy that would alias to DC (zero frequency), and greatly attenuates all frequencies that would alias to very low frequencies. The filter does not have a sharp cutoff at the Nyquist frequency, however, so does little to prevent energy just above the Nyquist frequency aliasing to just below it. The rectangle function filter is popular in computer-generated image anti-aliasing, where it is "good enough".

[edit] Reconstruction

Given a sampled signal <math>f(k)\in \Bbb C^n</math> one would like to reconstruct the original signal <math>f(x)\in L^2</math>. This is obviously impossible in general, as <math>L^2</math> is an infinite dimensional vector space, while <math>\Bbb C^n</math> is a finite dimensional vector space (of dimension n.)

In practice, one picks a subspace <math>H \subset L^2</math> of dimension n and a reconstruction linear map R from <math>\Bbb C^n</math> to H. The purpose of R is to turn a sampled signal into a continuous one in a way that makes sense to us.

An example reconstruction map would be

<math>R_1s=\sum_{k=1}^n s(k) 1_{[(k-1)/n,k/n)}</math>

where <math>1_E(x)</math> is 1 if <math>x\in E</math> and 0 otherwise.

Ideally, we would have <math>S(R(s))=s</math> for all <math>s\in \Bbb C^n</math>. If this occurs, then R and S both have the same picture of how signals in <math>L^2</math> and in <math>\Bbb C^n</math> behave, we might say that S and R are coherent. Here, <math>R_1</math> and <math>S_1</math> are in fact coherent, but <math>R_1</math> and <math>S_0</math> aren't.

Another way of saying that R and S are coherent is that R is a right-inverse for S (or S is a left-inverse for R.)

[edit] Aliasing

For any sampled signal <math>v\in \Bbb C^n</math> the set of continuous signals <math>f\in L^2</math> which sample to the same <math>v</math> are called aliases of one another. The fact that there are many aliases for any one given sampled signal is called aliasing. As previously mentioned, the large quantity of aliasing is caused by <math>L^2</math> being infinite dimensional while <math>\Bbb C^n</math> is finite dimensional.

[edit] Optimal filtering

In certain physical situations, the choice of R, H or S are somehow constrained. For instance, it is usual to choose H to be the linear span of low-degree trigonometric polynomials:

<math>H=\left\{\sum_{k=-n}^n \alpha_k \exp 2\pi ikx\,;\, \alpha_k \in \Bbb C \right\}.\,</math>

Further restrictions are that, for instance, S should coincide with <math>S_0 \ </math> on H. If sufficiently many of these demands are put forward, we eventually conclude that the sampling algorithm must take a very special shape:

<math>S_\mathrm{opt}f=S_0(\mathrm{sinc}*f) \ </math>

where <math>\mathrm{sinc}*f \ </math> is some sort of sinc filter or sinc function.

The reconstruction formula R is chosen so that R and S are coherent.

[edit] Caveats

It is important to keep in mind what is much repeated in the above discussion: the Nyquist theorem, the optimality of the sinc filter, the choice of the error norm (we chose <math>L^2</math>) and so on are all assumptions we are making about the underlying physical problem.

In many problems, these assumptions are unsuitable, and in these cases, the Nyquist theorem might need to be modified to be more relevant to the situation at hand.

[edit] See also

• Anti-aliasing
• Wagon-wheel effect
• Sinc filter
• Sinc function
• Temporal aliasing
• Nyquist–Shannon sampling theorem
• Whittaker–Shannon interpolation formula
• Nyquist rate
• Nyquist frequency

[edit] External links

• Sampling Theory white paper by Dan Lavry; opens with an incorrect statement about Nyquist; mostly a diatribe about audio.
• Aliasing animated gif a graph of signals sampled at different rates, showing how the character of some signals changes dramatically when the rate is too low.
• Frequency Aliasing Demonstration by Burton MacKenZie using stop frame animation and a clock.

de:Alias-Effekt es:Aliasing fr:Crènelage hr:Aliasing it:Aliasing nl:Aliasing pl:Aliasing (przetwarzanie sygnałów) ru:Алиасинг (обработка сигналов) zh:混疊