Spatial anti-aliasing

Last updated

In digital signal processing, spatial anti-aliasing is a technique for minimizing the distortion artifacts known as aliasing 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.

Contents

Anti-aliasing means removing signal components that have a higher frequency than is able to be properly resolved by the recording (or sampling) device. This removal is done before (re)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 (the larger the pixel pitch, the lower the achievable resolution at the sensor level).

Examples

Aliased.png
Visual distortion when anti-aliasing is not used
Antialiased.png
Anti-aliased
Antialiased lanczos.png
Anti-aliased via sinc filter algorithm
Antialiased-zoom.png
Magnified portion of image lacking anti-aliasing (left) and anti-aliased (right)

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 (and how much video memory it consumes).

Near the top of an image with a receding checker-board pattern, the image is both difficult to recognise and not aesthetically appealing. 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. [1] 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.

Left: an aliased version of a simple shape. Right: an anti-aliased version of the same shape. Anti-aliased-diamonds.png
Left: an aliased version of a simple shape. Right: an anti-aliased version of the same shape.

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:

defplot_antialiased_point(x:float,y:float):forroundedxinfloor(x)toceil(x):forroundedyinfloor(y)toceil(y):percent_x=1-abs(x-roundedx)percent_y=1-abs(y-roundedy)percent=percent_x*percent_ydraw_pixel(coordinates=(roundedx,roundedy),color=percent(range0-1))

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 3-D 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 DrawPixel 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 (usually a multiple that is a power of 2 to reduce distortion), 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 (x,y) 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

Sinc function, with separate X and Y Sinc(x) x sinc(y) plot.jpg
Sinc function, with separate X and Y

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 (it is not even square-integrable). 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.

Gaussian plus differential function Gaussian plus its own curvature.jpg
Gaussian plus differential function

One might consider a Gaussian plus enough of its second derivative to flatten the top (in the frequency domain) or sharpen it up (in the spatial domain), 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 (x and y) and in the spectral (j and k) 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 (either software or hardware accelerated). 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 (such as triangles that share an edge).

To approximate the uniform averaging algorithm, one may use an extra buffer for sub-pixel data. The initial (and least memory-hungry) 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 (such as the Z-buffer.)

Mipmapping

There is also an approach specialised for texture mapping called mipmapping, which works by creating lower resolution, pre-filtered versions of the texture map. When rendering the image, the appropriate-resolution mipmap is chosen and hence the texture pixels (texels) are already filtered when they arrive on the screen. Mipmapping is generally combined with various forms of texture filtering in order to improve the final result.

An example of an image with extreme pseudo-random aliasing

Because fractals have unlimited detail and no noise other than arithmetic round-off error, they illustrate aliasing more clearly than do photographs or other measured data. The escape times, which are converted to colours at the exact centres of the pixels, go to infinity at the border of the set, so colours from centres near borders are unpredictable, due to aliasing. This example has edges in about half of its pixels, so it shows much aliasing. The first image is uploaded at its original sampling rate. (Since most modern software anti-aliases, one may have to download the full-size version to see all of the aliasing.) The second image is calculated at five times the sampling rate and down-sampled with anti-aliasing. Assuming that one would really like something like the average colour over each pixel, this one is getting closer. It is clearly more orderly than the first.

In order to properly compare these images, viewing them at full-scale is necessary.

It happens that, in this case, there is additional information that can be used. By re-calculating with a "distance estimator" algorithm, points were identified that are very close to the edge of the set, so that unusually fine detail is aliased in from the rapidly changing escape times near the edge of the set. The colours derived from these calculated points have been identified as unusually unrepresentative of their pixels. The set changes more rapidly there, so a single point sample is less representative of the whole pixel. Those points were replaced, in the third image, by interpolating the points around them. This reduces the noisiness of the image but has the side effect of brightening the colours. So this image is not exactly the same that would be obtained with an even larger set of calculated points. To show what was discarded, the rejected points, blended into a grey background, are shown in the fourth image.

Finally, "Budding Turbines" is so regular that systematic (Moiré) aliasing can clearly be seen near the main "turbine axis" when it is downsized by taking the nearest pixel. The aliasing in the first image appears random because it comes from all levels of detail, below the pixel size. When the lower level aliasing is suppressed, to make the third image and then that is down-sampled once more, without anti-aliasing, to make the fifth image, the order on the scale of the third image appears as systematic aliasing in the fifth image.

Pure down-sampling of an image has the following effect (viewing at full-scale is recommended):

Super sampling / full-scene anti-aliasing

Super sampling anti-aliasing (SSAA), [2] also called full-scene anti-aliasing (FSAA), [3] is used to avoid aliasing (or "jaggies") on full-screen images. [4] SSAA was the first type of anti-aliasing available with early video cards. But due to its tremendous computational cost and the advent of multisample anti-aliasing (MSAA) support on GPUs, it is no longer widely used in real time applications. MSAA provides somewhat lower graphic quality, but also tremendous savings in computational power.

The resulting image of SSAA may seem softer, and should also appear more realistic. However, while useful for photo-like images, a simple anti-aliasing approach (such as super-sampling and then averaging) may actually worsen the appearance of some types of line art or diagrams (making the image appear fuzzy), especially where most lines are horizontal or vertical. In these cases, a prior grid-fitting step may be useful (see hinting).

In general, super-sampling is a technique of collecting data points at a greater resolution (usually by a power of two) than the final data resolution. These data points are then combined (down-sampled) to the desired resolution, often just by a simple average. The combined data points have less visible aliasing artifacts (or moiré patterns).

Full-scene anti-aliasing by super-sampling usually means that each full frame is rendered at double (2x) or quadruple (4x) the display resolution, and then down-sampled to match the display resolution. Thus, a 2x FSAA would render 4 super-sampled pixels for each single pixel of each frame. Rendering at larger resolutions will produce better results; however, more processor power is needed, which can degrade performance and frame rate. Sometimes FSAA is implemented in hardware in such a way that a graphical application is unaware the images are being super-sampled and then down-sampled before being displayed.

Object-based anti-aliasing

A graphics rendering system creates an image based on objects constructed of polygonal primitives; the aliasing effects in the image can be reduced by applying an anti-aliasing scheme only to the areas of the image representing silhouette edges of the objects. The silhouette edges are anti-aliased by creating anti-aliasing primitives which vary in opacity. These anti-aliasing primitives are joined to the silhouetted edges, and create a region in the image where the objects appear to blend into the background. The method has some important advantages over classical methods based on the accumulation buffer [ clarification needed ] since it generates full-scene anti-aliasing in only two passes and does not require the use of additional memory required by the accumulation buffer. Object-based anti-aliasing was first developed at Silicon Graphics for their Indy workstation.

Anti-aliasing and gamma compression

Digital images are usually stored in a gamma-compressed format, but most optical anti-aliasing filters are linear. So to down-sample an image in a way that would match optical blurring, one should first convert it to a linear format, then apply the anti-aliasing filter, and finally convert it back to a gamma compressed format. [5] Using linear arithmetic on a gamma-compressed image results in values which are slightly different from the ideal filter. This error is larger when dealing with high contrast areas, causing high contrast areas to become dimmer: bright details (such as a cat's whiskers) become visually thinner, and dark details (such as tree branches) become thicker, relative to the optically anti-aliased image. [6] Each pixel is individually distorted, meaning outlines become unsmooth after anti-aliasing. Because the conversion to and from a linear format greatly slows down the process, and because the differences are usually subtle, almost all image editing software, including Final Cut Pro, Adobe Photoshop and GIMP, process images in the gamma-compressed domain.

Most modern GPUs support storing textures in memory in sRGB format, and can perform transformation to linear space and back transparently, with essentially no loss in performance.

History

Important early works in the history of anti-aliasing include:

See also

Related Research Articles

Rendering (computer graphics) Process of generating an image from a model

Rendering or image synthesis is the process of generating a photorealistic or non-photorealistic image from a 2D or 3D model by means of a computer program. The resulting image is referred to as the render. Multiple models can be defined in a scene file containing objects in a strictly defined language or data structure. The scene file contains geometry, viewpoint, texture, lighting, and shading information describing the virtual scene. The data contained in the scene file is then passed to a rendering program to be processed and output to a digital image or raster graphics image file. The term "rendering" is analogous to the concept of an artist's impression of a scene. The term "rendering" is also used to describe the process of calculating effects in a video editing program to produce the final video output.

Nyquist–Shannon sampling theorem Sufficiency theorem for reconstructing signals from samples

The Nyquist–Shannon sampling theorem is a theorem in the field of digital signal processing which serves as a fundamental bridge between continuous-time signals and discrete-time signals. It establishes a sufficient condition for a sample rate that permits a discrete sequence of samples to capture all the information from a continuous-time signal of finite bandwidth.

Texture mapping Method of defining surface detail on a computer-generated graphic or 3D model

Texture mapping is a method for defining high frequency detail, surface texture, or color information on a computer-generated graphic or 3D model. The original technique was pioneered by Edwin Catmull in 1974.

Aliasing Effect that causes signals to become indistinguishable when sampled; often producing detectable aberrations

In signal processing and related disciplines, aliasing is an effect that causes different signals to become indistinguishable when sampled. It also often refers to the distortion or artifact that results when a signal reconstructed from samples is different from the original continuous signal.

Sampling (signal processing) measurement of a signal at discrete time intervals

In signal processing, sampling is the reduction of a continuous-time signal to a discrete-time signal. A common example is the conversion of a sound wave to a sequence of samples.

In computer graphics, mipmaps or pyramids are pre-calculated, optimized sequences of images, each of which is a progressively lower resolution representation of the previous. The height and width of each image, or level, in the mipmap is a power of two smaller than the previous level. Mipmaps do not have to be square. They are intended to increase rendering speed and reduce aliasing artifacts. A high-resolution mipmap image is used for high-density samples, such as for objects close to the camera; lower-resolution images are used as the object appears farther away. This is a more efficient way of downfiltering (minifying) a texture than sampling all texels in the original texture that would contribute to a screen pixel; it is faster to take a constant number of samples from the appropriately downfiltered textures. Mipmaps are widely used in 3D computer games, flight simulators, other 3D imaging systems for texture filtering and 2D as well as 3D GIS software. Their use is known as mipmapping. The letters MIP in the name are an acronym of the Latin phrase multum in parvo, meaning "much in little".

Fractal flame

Fractal flames is a member of the iterated function system class of fractals created by Scott Draves in 1992. Draves' open-source code was later ported into Adobe After Effects graphics software and translated into the Apophysis fractal flame editor.

Anisotropic filtering Method of enhancing the image quality of textures on surfaces of computer graphics

In 3D computer graphics, anisotropic filtering is a method of enhancing the image quality of textures on surfaces of computer graphics that are at oblique viewing angles with respect to the camera where the projection of the texture appears to be non-orthogonal.

In computer graphics, texture filtering or texture smoothing is the method used to determine the texture color for a texture mapped pixel, using the colors of nearby texels. There are two main categories of texture filtering, magnification filtering and minification filtering. Depending on the situation texture filtering is either a type of reconstruction filter where sparse data is interpolated to fill gaps (magnification), or a type of anti-aliasing (AA), where texture samples exist at a higher frequency than required for the sample frequency needed for texture fill (minification). Put simply, filtering describes how a texture is applied at many different shapes, size, angles and scales. Depending on the chosen filter algorithm the result will show varying degrees of blurriness, detail, spatial aliasing, temporal aliasing and blocking. Depending on the circumstances filtering can be performed in software or in hardware for real time or GPU accelerated rendering or in a mixture of both. For most common interactive graphical applications modern texture filtering is performed by dedicated hardware which optimizes memory access through memory cacheing and pre-fetch and implements a selection of algorithms available to the user and developer.

Cone tracing and beam tracing are a derivative of the ray tracing algorithm that replaces rays, which have no thickness, with thick rays.

Pixel-art scaling algorithms any image scaling algorithm optimized for pixel art, often used as a graphical filter in video game emulators

Pixel-art scaling algorithms are graphical filters that are often used in video game console emulators to enhance hand-drawn 2D pixel art graphics. The re-scaling of pixel art is a specialist sub-field of image rescaling.

Gaussian blur Visual effect

In image processing, a Gaussian blur is the result of blurring an image by a Gaussian function. It is a widely used effect in graphics software, typically to reduce image noise and reduce detail. The visual effect of this blurring technique is a smooth blur resembling that of viewing the image through a translucent screen, distinctly different from the bokeh effect produced by an out-of-focus lens or the shadow of an object under usual illumination. Gaussian smoothing is also used as a pre-processing stage in computer vision algorithms in order to enhance image structures at different scales—see scale space representation and scale space implementation.

In a mixed-signal system, a reconstruction filter, sometimes called an anti-imaging filter, is used to construct a smooth analog signal from a digital input, as in the case of a digital to analog converter (DAC) or other sampled data output device.

Lanczos resampling

Lanczos filtering and Lanczos resampling are two applications of a mathematical formula. It can be used as a low-pass filter or used to smoothly interpolate the value of a digital signal between its samples. In the latter case it maps each sample of the given signal to a translated and scaled copy of the Lanczos kernel, which is a sinc function windowed by the central lobe of a second, longer, sinc function. The sum of these translated and scaled kernels is then evaluated at the desired points.

Image scaling Changing the resolution of a digital image

In computer graphics and digital imaging, imagescaling refers to the resizing of a digital image. In video technology, the magnification of digital material is known as upscaling or resolution enhancement.

In imaging science, difference of Gaussians (DoG) is a feature enhancement algorithm that involves the subtraction of one Gaussian blurred version of an original image from another, less blurred version of the original. In the simple case of grayscale images, the blurred images are obtained by convolving the original grayscale images with Gaussian kernels having differing width. Blurring an image using a Gaussian kernel suppresses only high-frequency spatial information. Subtracting one image from the other preserves spatial information that lies between the range of frequencies that are preserved in the two blurred images. Thus, the DoG is a spatial band-pass filter that attenuates frequencies in the original grayscale image that are far from the band center.

Supersampling supersampler

Supersampling or SSAA is a spatial anti-aliasing method, i.e. a method used to remove aliasing from images rendered in computer games or other computer programs that generate imagery. Aliasing occurs because unlike real-world objects, which have continuous smooth curves and lines, a computer screen shows the viewer a large number of small squares. These pixels all have the same size, and each one has a single color. A line can only be shown as a collection of pixels, and therefore appears jagged unless it is perfectly horizontal or vertical. The aim of supersampling is to reduce this effect. Color samples are taken at several instances inside the pixel, and an average color value is calculated. This is achieved by rendering the image at a much higher resolution than the one being displayed, then shrinking it to the desired size, using the extra pixels for calculation. The result is a downsampled image with smoother transitions from one line of pixels to another along the edges of objects.

Temporal anti-aliasing (TAA) seeks to reduce or remove the effects of temporal aliasing. Temporal aliasing is caused by the sampling rate of a scene being too low compared to the transformation speed of objects inside of the scene; this causes objects to appear to jump or appear at a location instead of giving the impression of smoothly moving towards them. To avoid aliasing artifacts altogether, the sampling rate of a scene must be at least twice as high as the fastest moving object. The shutter behavior of the sampling system strongly influences aliasing, as the overall shape of the exposure over time determines the band-limiting of the system before sampling, an important factor in aliasing. A temporal anti-aliasing filter can be applied to a camera to achieve better band-limiting. A common example of temporal aliasing in film is the appearance of vehicle wheels travelling backwards, the so-called wagon-wheel effect. Temporal anti-aliasing can also help to reduce jaggies, making images appear softer.

The term post-processing is used in the video/film business for quality-improvement image processing methods used in video playback devices,, and video players software and transcoding software. It is also commonly used in real-time 3D rendering to add additional effects.

This is a glossary of terms relating to computer graphics.

References

  1. Leler, William J. (July 1980). "Human Vision, Anti-aliasing, and the Cheap 4000 Line Display". ACM SIGGRAPH Computer Graphics. 14 (3): 308–313. doi:10.1145/965105.807509.
  2. "AMD's Radeon HD 5870: Bringing About the Next Generation Of GPUs". AnandTech.com.
  3. Jason Gregory, Jeff Lander (2009). Game Engine Architecture. A K Peters, Ltd. p. 39. ISBN   978-1-56881-413-1.
  4. M. Carmen Juan Lizandra (June 2000). "Graphic libraries for Windows programming". Crossroads. ACM. 6 (4): 14–18. doi:10.1145/333424.333433.
  5. Maruszczyk, Kuba; Denes, Gyorgy; Mantiuk, Rafal K. (2018). "Improving Quality of Anti-Aliasing in Virtual Reality" (PDF). EG UK Computer Graphics & Visual Computing.
  6. Brasseur, Eric. "Gamma error in picture scaling". www.4p8.com. Archived from the original on 2012-12-23. Retrieved 2012-12-14.