hpdz.net

Introduction

Two questions were posed on the page discussing anti-aliasing regarding how to perform supersampling:

• How much oversampling?
• What kind of filter?

These were the most immediately obvious things to consider. A less obvious, but very important, question is considered on this page.

What should the supersampling grid look like?

It may not be clear what this even means, let alone why it would matter, but it can have a huge impact on how the final output image looks.

In the discussion on anti-aliasing filtering, the assumption was that the supersampling points were taken on a uniform square grid within each image pixel. This is the most intuitive construction, but by no means the only way to supersample. We could use arrange the supersampling points in a hexagon, triangle, or anything else. We can even randomly spread the supersampling points around in the pixel. Why would we want to do anything other than a square grid, especially spreading the points around randomly?

Spread the noise around a little

The reason we might want the sampling grid to be randomly spaced is that the shape of the grid determines how the out-of-band energy above the Nyquist frequency is aliased into the signal band. A regularly-spaced grid will reliably map a particular frequency above the Nyquist frequency to a unique single frequency in the sampling band. That is why moire patterns can develop.

It turns out that if the supersampling grid is not regularly spaced, but rather is random, then the aliased energy from any frequency is spread out randomly into the passband. A single high frequency no longer gets aliased to a single low frequency, but instead turns into a small amount of broadband noise in the sample band. The effect is that moire disappears and is replaced with white noise.

This is called stochastic supersampling. It is, in a way, more "honest" in the sense that it is replacing moire (a visual artifact of aliasing) in undersampled areas of the image with white noise, which is the DSP way of saying "I don't have enough information to accurately render what's here".

Whether the effect is esthetically desirable is, I suppose, a matter of taste. Do you like moire or do you like noise? It is a fundamental result of DSP theory that you cannot simultaneously eliminate both.

Random points and the Poisson disc

Once we decide we want to use stochastic supersampling, we have to decide how the supersampling points are to be randomized into the pixel grid.

Uniform distribution

The most obvious approach would be to pick the X and Y coordinates of each point at random using a uniformly distributed random number generator. This does work, but turns out to be suboptimal in the way it spreads the aliased energy around in the passband. Since it has a uniform Fourier transform, it spreads high and low frequencies equally, so some energy is still present at the more visually noticeable lower frequencies.

Poisson disc

The optimal way to do this (depending on how you define "optimal") is to use something called a Poisson disc to distribute the random points. This kind of distribution has points randomly scattered, but limited to being no closer together than a certain minimum distance. That distance determines the cutoff frequency where aliased energy is sent. Since the sampling points are never closer than a certain minimum distance, the Fourier transform of this sampling grid has a minimum at low frequencies and rises at higher frequencies. This kind of thing is called "blue noise" and is the key to stochastic supersampling removing moire effects.

Nature is pretty smart

Photoreceptors in most animal retinas, including those of humans, are distributed according to a Poisson disc distribution. That is part of why we do not have aliasing in our vision. At the center of our vision, they are arranged on a regular hexagonal grid, which can give aliasing, but the lens acts as an anti-aliasing filter.

Uniform Jitter

It is computationally difficult to generate Poisson disc distributions, so something almost as good is usually used in practical image processing systems. This is a simple jitter of the supersampled points. The pixel to be rendered is divided up into subpixels as with regular supersampling, then each subpixel is shifted around slightly. This gives a blue noise spectrum similar to the Poisson disc but with slightly different properties. Depending on what you're trying to do, this can actually be better in some applications.

Practical significance

Supersampling in general is expensive, and stochastic supersampling is no exception. The same costs apply to stochastic supersampling that were described for anti-aliasing. Nasty factors of 4X, 9X, 16X, etc come up. But the cost of using a random sampling grid is only minutely greater than the cost of using a regularly spaced grid, since the time needed to generate the necessary random numbers is miniscule compared to the time it takes to iterate the fractal function. This is especially true at very high magnifications, where the function has to be iterated many tens of thousands of times, and where moire is most likely to arise.

Examples

Below are some examples of stochastic supersampling. There are five variations demonstrated with 320x240 uncompressed BMP images, and some short animations showing how three of these techniques look in motion. These are taken from the final part of Centanimus, with a size vertically of 6.6E-102 in the complex number plane.

Another great example of stochastic supersampling is the deep zoom image of a mini-brot in the type 1 Magnet Fractal, created as part of the validation of the new floating point arithmetic code.

The descriptions of each method are below.

Image A	Image B
Image C	Image D
Image E

These are uncompressed 320x240 AVI files (to preserve as much detail as possible) and are about 83 MB each.

• MethodA
• MethodB
• MethodC

If 83 MB thrice is too much, then consider this compressed version which is almost as good.

• 500 Kbps MP4 (4.5 MB 320x240) FastStart

Finally, there is this high-resolution rendering with a median filter and 16X stochastic supersampling. It's a 921KB 640x480 BMP file that deserves a look.

It sure is pr'ty, but at 5.74 hours of computational time to render on my 3.2 GHz Pentium-IV, it is out of my league for animations (even if I used the quad-Core2 system, it would still be impractical)

Descriptions of Techniques

Method A

Original image with no modifications.

Method B

1X stochastic sampling. The same size sampling grid was used, but each point was jittered by a random amount. This has the effect of spreading out the aliased energy over the entire spatial frequency spectrum, rather than concentrating it at a few low frequencies. Moire is essentially gone, but it is replaced by dramatically increased noise in the areas where the image is sampled below the spatial frequency of the radial lines.

Method C

Stochastic supersampling on a 2x2 grid with median filtering. Each image pixel is the median of four supersampled points taken on a jittered 2x2 supersampling grid. This clearly has more detail where the radial spokes converge, and moire is reduced.

Method D

Stochastic supersampling on a 3x3 grid with median filtering. Each image pixel is the median of nine supersampled points taken on a jittered 3x3 supersampling grid.

Method E

Non-jittered supersampling on a 5-point cross with median filtering. This greatly reduces sparkle noise due to the effective low-pass filtering, but it has much less of an effect on moire. That is because the mapping of the above-Nyquist spatial frequencies into the sampled band is preserved with this regular grid, so coherent artifacts like moire are able to persist.