Spatial anti-aliasing


In digital signal processing, spatial anti-aliasing is a technique for minimizing the distortion artifacts when representing a high-resolution image at a lower resolution. Anti-aliasing is used in digital photography, computer graphics, digital audio, and many other applications.
Anti-aliasing means removing signal components that have a higher frequency than is able to be properly resolved by the recording device. This removal is done before sampling at a lower resolution. When sampling is performed without removing this part of the signal, it causes undesirable artifacts such as black-and-white noise.
In signal acquisition and audio, anti-aliasing is often done using an analog anti-aliasing filter to remove the out-of-band component of the input signal prior to sampling with an analog-to-digital converter. In digital photography, optical anti-aliasing filters made of birefringent materials smooth the signal in the spatial optical domain. The anti-aliasing filter essentially blurs the image slightly in order to reduce the resolution to or below that achievable by the digital sensor.

Examples

In computer graphics, anti-aliasing improves the appearance of "jagged" polygon edges, or "jaggies", so they are smoothed out on the screen. However, it incurs a performance cost for the graphics card and uses more video memory. The level of anti-aliasing determines how smooth polygon edges are.
Near the top of an image with a receding checker-board pattern, the image is difficult to recognise and often not considered aesthetically pleasing. In contrast, when anti-aliased the checker-board near the top blends into grey, which is usually the desired effect when the resolution is insufficient to show the detail. Even near the bottom of the image, the edges appear much smoother in the anti-aliased image. Multiple methods exist, including the sinc filter, which is considered a better anti-aliasing algorithm. When magnified, it can be seen how anti-aliasing interpolates the brightness of the pixels at the boundaries to produce grey pixels since the space is occupied by both black and white tiles. These help make the sinc filter antialiased image appear much smoother than the original.
In a simple diamond image, anti-aliasing blends the boundary pixels; this reduces the aesthetically jarring effect of the sharp, step-like boundaries that appear in the aliased graphic.
Anti-aliasing is often applied in rendering text on a computer screen, to suggest smooth contours that better emulate the appearance of text produced by conventional ink-and-paper printing. Particularly with fonts displayed on typical LCD screens, it is common to use subpixel rendering techniques like ClearType. Sub-pixel rendering requires special colour-balanced anti-aliasing filters to turn what would be severe colour distortion into barely-noticeable colour fringes. Equivalent results can be had by making individual sub-pixels addressable as if they were full pixels, and supplying a hardware-based anti-aliasing filter as is done in the OLPC XO-1 laptop's display controller. Pixel geometry affects all of this, whether the anti-aliasing and sub-pixel addressing are done in software or hardware.

Simplest approach to anti-aliasing

The most basic approach to anti-aliasing a pixel is determining what percentage of the pixel is occupied by a given region in the vector graphic - in this case a pixel-sized square, possibly transposed over several pixels - and using that percentage as the colour.
A very basic plot of a single, white-on-black anti-aliased point using that method can be done as follows:

def plot_antialiased_point:
"""Plot a single, white-on-black anti-aliased point."""
for rounded_x in floor to ceil:
for rounded_y in floor to ceil:
percent_x = 1 - abs
percent_y = 1 - abs
percent = percent_x * percent_y
draw_pixel, color=percent )

This method is generally best suited for simple graphics, such as basic lines or curves, and applications that would otherwise have to convert absolute coordinates to pixel-constrained coordinates, such as 3D graphics. It is a fairly fast function, but it is relatively low-quality, and gets slower as the complexity of the shape increases. For purposes requiring very high-quality graphics or very complex vector shapes, this will probably not be the best approach.
Note: The draw_pixel routine above cannot blindly set the colour value to the percent calculated. It must add the new value to the existing value at that location up to a maximum of 1. Otherwise, the brightness of each pixel will be equal to the darkest value calculated in time for that location which produces a very bad result. For example, if one point sets a brightness level of 0.90 for a given pixel and another point calculated later barely touches that pixel and has a brightness of 0.05, the final value set for that pixel should be 0.95, not 0.05.
For more sophisticated shapes, the algorithm may be generalized as rendering the shape to a pixel grid with higher resolution than the target display surface, then using bicubic interpolation to determine the average intensity of each real pixel on the display surface.

Signal processing approach to anti-aliasing

In this approach, the ideal image is regarded as a signal. The image displayed on the screen is taken as samples, at each pixel position, of a filtered version of the signal. Ideally, one would understand how the human brain would process the original signal, and provide an on-screen image that will yield the most similar response by the brain.
The most widely accepted analytic tool for such problems is the Fourier transform; this decomposes a signal into basis functions of different frequencies, known as frequency components, and gives us the amplitude of each frequency component in the signal. The waves are of the form:
where j and k are arbitrary non-negative integers. There are also frequency components involving the sine functions in one or both dimensions, but for the purpose of this discussion, the cosine will suffice.
The numbers j and k together are the frequency of the component: j is the frequency in the x direction, and k is the frequency in the y direction.
The goal of an anti-aliasing filter is to greatly reduce frequencies above a certain limit, known as the Nyquist frequency, so that the signal will be accurately represented by its samples, or nearly so, in accordance with the sampling theorem; there are many different choices of detailed algorithm, with different filter transfer functions. Current knowledge of human visual perception is not sufficient, in general, to say what approach will look best.

Two dimensional considerations

The previous discussion assumes that the rectangular mesh sampling is the dominant part of the problem. The filter usually considered optimal is not rotationally symmetrical, as shown in this first figure; this is because the data is sampled on a square lattice, not using a continuous image. This sampling pattern is the justification for doing signal processing along each axis, as it is traditionally done on one dimensional data. Lanczos resampling is based on convolution of the data with a discrete representation of the sinc function.
If the resolution is not limited by the rectangular sampling rate of either the source or target image, then one should ideally use rotationally symmetrical filter or interpolation functions, as though the data were a two dimensional function of continuous x and y. The sinc function of the radius has too long a tail to make a good filter. A more appropriate analog to the one-dimensional sinc is the two-dimensional Airy disc amplitude, the 2D Fourier transform of a circular region in 2D frequency space, as opposed to a square region.
Image:Gaussian plus its own curvature.jpg|thumb|Gaussian plus differential function
One might consider a Gaussian plus enough of its second derivative to flatten the top or sharpen it up, as shown. Functions based on the Gaussian function are natural choices, because convolution with a Gaussian gives another Gaussian whether applied to x and y or to the radius. Similarly to wavelets, another of its properties is that it is halfway between being localized in the configuration and in the spectral representation. As an interpolation function, a Gaussian alone seems too spread out to preserve the maximum possible detail, and thus the second derivative is added.
As an example, when printing a photographic negative with plentiful processing capability and on a printer with a hexagonal pattern, there is no reason to use sinc function interpolation. Such interpolation would treat diagonal lines differently from horizontal and vertical lines, which is like a weak form of aliasing.

Practical real-time anti-aliasing approximations

There are only a handful of primitives used at the lowest level in a real-time rendering engine. These include "points", "lines" and "triangles". If one is to draw such a primitive in white against a black background, it is possible to design such a primitive to have fuzzy edges, achieving some sort of anti-aliasing. However, this approach has difficulty dealing with adjacent primitives.
To approximate the uniform averaging algorithm, one may use an extra buffer for sub-pixel data. The initial approach used 16 extra bits per pixel, in a 4 × 4 grid. If one renders the primitives in a careful order, such as front-to-back, it is possible to create a reasonable image.
Since this requires that the primitives be in some order, and hence interacts poorly with an application programming interface such as OpenGL, the latest methods simply have two or more full sub-pixels per pixel, including full color information for each sub-pixel. Some information may be shared between the sub-pixels