Aliasing (original) (raw)

Aliasing is a phenomenon in signal sampling and in design of experiments, when several continuous signals that are different become indistinguishable (or aliases of one another) when sampled. Consequently the signal cannot be uniquely reconstructed from the sampled signal. The term is used often in Digital Imaging, where anti-aliasing is used to limit clipping artifacts around contrasted edges (like in screen-fonts) and in poorly-sampled raster images.

Overview

The sun moves east to west in the sky, with 24 hours between sunrises. If one were to take a picture of the sun in the sky every 23 hours and write down the precise date and time on each picture, the sun would appear to move west to east, and the period between each apparent "sunrise" on the horizon in the west would be 24 pictures, which is 552 hours (24x23), that is, 23 real days. If the observations are made every 25 hours, the sun now moves apparently east to west, and it will still take 24 images for the sun to complete a revolution, but now each image will have lapsed 25 hours. The apparent period of the sun is then 600 hours (24x25), which is 25 real days. A similar temporal aliasing effect may occur filming a spoked wheel. This effect can be used to cause a repetitive action to appear to slow down by using a strobe light.

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.

The qualitative effects of aliasing can be heard in the following audio demonstration. Four sawtooth waves are played in succession, with the first two sawtooths having a fundamental frequency of 220 Hz (A2) and the second two having fundamental frequency of 440 Hz (A3). The sawooths alternate between bandlimited (non-aliased) sawtooths and aliased sawtooths. Note that the audio file has been coded using Ogg's Vorbis codec, and as such the audio is somewhat degraded.

{220 Hz bandlimited, 220 Hz aliased, 440 Hz bandlimited, 440 Hz aliased}

A more rigorous explanation of aliasing, based on function approximation, is outlined below as an introduction for a deeper mathematic understanding of the phenomenon.

Technical discussion

First we will introduce a formal notion of "continuous signal". Since there are more than one possible choices (depending on the subject at hand), we will give some general outline, but fix our attention on a specific example for the purpose of this article. Second, we will give a notion of similarity of signals. Again, this precise notion depends on the underlying physical problem, but we will provide a common example for the sake of discussion. Third, we will give the most common sampling method as an example, and fourth we will show its failings. Fifth, we will give an improved sampling method that is more in-tune with the similarity notion introduced in the second section.

In engineering, the method introduced in the third section is called sampling, while a method such as that introduced in the fifth section is called filtering. This discussion may be viewed as a theoretical introduction to the ideas of anti-aliasing.

Continuous signals

A signal is usually a real or complex valued function whose domain could be the real line (which we might understand as a time variable), the plane (for computer graphics) or some other set. More specific details depend on the nature of the signals we're studying, but an example of a mathematically precise space of interest might be

the set of functions whose square is integrable.

These signals are in fact not necessarily continuous functions; the adjective "continuous" refers to the domain as opposed to a discrete or even finite set.

The signal could arise from a variety of physical processes. For instance, one could measure the seismic movement of the ground with a seismograph. The output of a seismograph is a strip of paper known as a seismogram. This strip of paper can be interpreted as the graph of a function. This function will be in _L_2 as defined above, and thus we obtain a mathematical signal from a physical process.

Similar signals

We need to find a way of judging whether two such signals are similar. We will quantify this, usually with a norm. Such a simple system may not be appropriate; for an example of a more sophisticated approach, see the psychoacoustic model. For the sake of discussion, we will use the root mean square norm (see Lp spacess for some details).

A simple sampling method

An obvious way to go from a continuous function of to an _n_-dimensional vector (a sampled signal) is the following "point sampling" method:

That is, the function is sampled at the points . The obvious advantage of this scheme is its simplicity. However, the map has some unfortunate properties.

The features of S0

Note that is a linear map: if f and g are any two functions for which and are defined, and if a is any scalar, then . The domain of includes at least all continuous functions of . On the other hand, for technical reasons, it is not clear how to extend to all of . In particular (and perhaps more telling) is that is not continuous as a function on .

Indeed, define by

Then, the norm in is and so converges to zero. However, for any , the vector is and so does not converge to zero. Hence is not continuous.

Therefore, the sampling function very poorly represents our notion of closeness in our signal space .

An improved sampling method (filtering)

First, note that is contained in (see Lp spaces.) Hence, we can define a new "interval averaging" sampling method by

This sampling method, unlike , is defined over all of . Also, by the Cauchy-Schwarz inequality (for instance,) is also continuous in the root mean square norm. Hence, signals which alias to the same sampled vector will be related as far as the root mean square norm is concerned.

Frequency analysis

We continue with but now we will use its Hilbert space structure. Let F be any sampling method (a linear map from to .)

In our example, the vector space of sampled signals is _n_-dimensional complex space. Any proposed inverse R of F (reconstruction formula, in the lingo) would have to map to some subset of . We could choose this subset arbitrarily, but if we're going to want a reconstruction formula R that is also a linear map, then we have to choose an _n_-dimensional linear subspace of .

This fact that the dimensions have to agree is related to the Nyquist-Shannon sampling theorem.

The elementary linear algebra approach works here. Let (all entries zero, except for the _k_th entry, which is a one) or some other basis of . To define an inverse for F, simply choose, for each k, an so that . This uniquely defines the (pseudo-)inverse of F.

Of course, one can choose some reconstruction formula first, then either compute some sampling algorithm from the reconstruction formula, or analyze the behavior of a given sampling algorithm with respect to the given formula.

Popular reconstruction formulae

Perhaps the most widely used reconstruction formula is as follows. Let is a basis of in the Hilbert space sense; for instance, one could use the canonical

although other choices are certainly possible. Note that here the index k can be any integer, even negative.

Then we can define a linear map R by

for each , where is the basis of given by(This is the usual discrete Fourier basis.)

The choice of range is somewhat arbitrary, although it satisfies the dimensionality requirement and reflects the usual notion that the most important information is contained in the low frequencies. In some cases, this is incorrect, so a different reconstruction formula needs to be chosen.

A similar approach can be obtained by using wavelets instead of Hilbert bases. For many applications, the best approach is still not clear today.

We note here that there is an efficient algorithm, known as the Fast Fourier transform to convert vectors between the canonical basis of and the Fourier basis . This algorithm is significantly faster than the matrix multiplication required in the general case of change of basis. On the other hand, wavelets are often defined so that the change of basis matrix is sparse, and so again the change of basis algorithm is efficient.

Analysis of sampling methods and filters

For many applications, the reconstruction algorithm R suggested above is useful. We can return to and and analyze them in relation to R.

In the case of , for any , at least, , and so the reconstruction formula is a reasonable match of the sampling method. However, it is fairly easy to see that, for any , is nonzero, in fact, these quantities behave periodically in . Hence, any high frequencies which can not be represented by R will get "folded into" the low frequencies.

In the case of , one can analyze, via convolutions, to which extend the high frequencies are "folded into" the low frequencies. They still are, but to a somewhat lesser extent.

This "folding" of frequencies is often considered to be undesirable when R is chosen properly. For instance, it is possible to choose a reconstruction formula based on the Haar basis (see wavelets) in which case does not fold any high frequencies into the lower frequencies. However, this reconstruction formula (or the Haar basis) are inappropriate to most problems.

If one is giving a reconstruction formula in terms of Hilbert bases, as is our case, then one can give a "perfect" filter, which does not fold any frequencies at all, in terms of convolutions.