0
$\begingroup$

In this note, I will argue that the jaggedness observed in rasterized images should not be referred to as aliasing.

First, let us agree on a definition: aliasing is the distortion that arises when overlapping copies of a signal's spectrum combine, causing high-frequency components to be misrepresented as lower-frequency ones.

This misrepresentation leads to artifacts such as beats or moiré patterns in images, as observed when textures are resampled at an insufficient frequency. Visually, this is clearly distinct from jaggedness, and I believe we can all agree on that — raising the question posed in the title.

Let us review what the Shannon-Nyquist sampling theorem prescribes:

  1. Given that the signal has a limited bandwidth, it must be sampled at a sufficiently high frequency (the Nyquist frequency).
  2. The appropriate reconstruction filter must be used — specifically, the sinc function, as given by the Whittaker–Shannon interpolation formula.

I maintain that aliasing occurs when condition (1) is violated, whereas "jaggedness" arises from the violation of (2).

In other words, jaggedness is not introduced during sampling but rather during reconstruction. When visualizing the signal on a raster display, we are forced to reconstruct it using a box filter (or zero-order hold) instead of the ideal sinc filter. This violation of (2) results in the jagged appearance.

I realize that this is not how "aliasing" is commonly interpreted in mainstream computer graphics. However, I can cite several authors who support this perspective.

The consequence of failing to filter the signal properly before sampling is known as "aliasing." Aliasing occurs when a lower frequency signal appears as an "alias" of a high frequency signal after sampling. Therefore highly periodic images of scenes involving, for example, picket fences or venetian blinds may appear, when sampled, to be made up of a few broad strips rather than many fine lines.

Reproducing the signal involves representing each sample in such a way that the reproduced signal has no frequencies higher than the original signal. This can be accomplished by representing each sample as a rectangular pulse and then low-pass filtering the resulting signal. In the two-dimensional case, the result of failing to filter the signal properly during reconstruction is known as "rastering." Rastering is an artifact of the structure of the displayed image.

[The Aliasing Problem in Computer-Generated Shaded Images Franklin C. Crow. Comm of the ACM 11:20, 1977]

Although aliasing may occur in the image-synthesis process, jaggedness is primarily due to pixel-structure artifacts that arise during reconstruction of a sampled signal by the display pixels. In fact, a completely “antialiased” image may still appear jagged, due to inexact reconstruction. Furthermore, few of the algorithms in the literature actually guarantee that the resultant sampled signal has no lower-frequency aliases. Hence, we prefer the term “filtering” rather than “antialiasing.

[Avi C. Naiman. Jagged Edges: When Is Filtering Needed? ACM Transactions on Graphics, Vol. 17, No. 4, October 1998.]

In summary, my point is that jaggedness is not an aliasing effect caused by sampling below the Nyquist frequency. Rather, it is an artifact of using a non-ideal reconstruction kernel.

I would appreciate your thoughts on this.

Edit: I am appending my reply here since I do not have enough reputation to comment.

Thanks a lot for this discussion. As often happens, everyone is right. Of course, one is free to call "aliasing" any artifact that arises in the sampling and reconstruction process, including truncation, quantization, wrong reconstruction function and even the discrete nature of the display.

But if we agree (and you might not, of course) that aliasing specifically refers to the effect where certain frequencies are incorrectly substituted for others (hence the name "alias": a false or assumed identity), occurring due to copies of the original spectrum overlapping because of sampling below the Nyquist rate, then, I find it difficult to relate this to "jaggedness", whereas it fits perfectly to moiré patterns in texture mapping.

$\endgroup$
19
  • $\begingroup$ Aliasing is the name we give to jaggedness. It arises from many sources. $\endgroup$ Commented Mar 10 at 21:54
  • $\begingroup$ Regarding your answer - I suggest reading the paper "Sampling-50 years after Shannon" which you can find freely available from epfl. It should provide a broader context for the whole story. Ultimately you can regard your screen (in an idealized scenario) either as composed by box functions or representable through the Haar wavelet basis. In either case the blockiness is indeed a result of that, but it's not like you have control over it, nor is it visible at higher resolutions. So if you just refer to the screen being pixelated that is of course not aliasing. However when rendering a line or $\endgroup$ Commented Mar 15 at 22:14
  • $\begingroup$ triangle, if you refer to jagginess along the edge - that's integration error, i.e., aliasing if you will. The higher frequency edge shows up as lower frequency blocks due to undersampling. Indeed, if you had a different reconstruction, those would not necessarily have to be blocks, but this being a result of undersampling remains. If you could integrate perfectly (e.g. brightness in a pixel being determined by the ratio of covered area) then this would not occur. However, as I hinted in my answer you can still get aliasing even if you perfectly integrate. Take for example a zoneplate function $\endgroup$ Commented Mar 15 at 22:17
  • $\begingroup$ $g(x,y) = \frac{1+\cos(fx^2)}{2}$. You can integrate the latter perfectly on the pixels of your screen by using Fresnel integrals. Nevertheless, if you decrease the resolution sufficiently you will see aliasing despite of the perfect integration (various low frequency wavelike patterns that do not exist). There are two things at play here: a) the box basis is not the trigonometric basis (or the sinc basis in the non-periodic setting), b) the zoneplate is not bandlimited. The box basis coefficients are equivalent to convolving with a box and sampling. You can use the latter to relate to Shannon $\endgroup$ Commented Mar 15 at 22:29
  • $\begingroup$ I'll also reiterate that the sinc basis is pretty terrible - it decays incredibly slowly, and requires infinitely many samples (a Dirac comb). Not taking infinitely many samples means that you will get oscillations. Moreover, since real functions are rarely bsndlimited you will also get oscillations at discontinuities (also if you use trigonometric bases in the periodic setting). Compare the Fourier vs wavelet approximation here as an example: rafat.github.io/sites/wavebook/math/nla.html The thing is that the well-localised box filter in the Fourier domain is the sinc in the spatial $\endgroup$ Commented Mar 15 at 22:41

1 Answer 1

1
$\begingroup$

The word aliasing has a precise mathematical meaning. Let a function $f:[-1,1]\to\mathbb{R}$ be given. Now suppose you want to approximate $f$ as best as possible wrt the standard complex inner product on $[-1,1]$: $\langle g, f \rangle = \int_{-1}^{1} \overline{g(x)} f(x)\,dx$. If you have an orthogonal Schauder basis $(b_k)_{k\in\mathbb{Z}}$ for $L_2([-1,1])$, where $b_k:[-1,1]\to \mathbb{C}$, you can approximate any "function" in $L_2$ as a linear combination of the basis functions: $\exists (c_k)_{k\in\mathbb{Z}} \,:\,\|f - \sum_{k\in\mathbb{Z}} c_k b_k\|_2 = 0$. Since the basis is orthogonal it holds that $$c_k(f) = \frac{\langle b_k, f\rangle}{\langle b_k, b_k\rangle} = \frac{\int_{-1}^{1} \overline{b_k(x)}f(x)\,dx}{\int_{-1}^{1} |b_k(x)|^2\,dx}.$$

One such representative is the trigonometric basis $b_k(x)=\exp(i \pi k x)$. One can easily verify that it is orthogonal wrt the above inner product and that $\|b_k\|^2 = 2$. Then the series $$S(f)(x) = \sum_{k\in\mathbb{Z}} c_k(f) b_k(x)$$ is known as the Fourier series of $f$. The first issue with the above is that we may be unable to compute the integrals for the coefficients even if we truncate the sum. You could then choose to approximate the integrand by a piecewise constant function of $2N$ pieces - then the integral of the latter is just the sum of the areas of the rectangles: $$c_k = \frac{1}{2} \int_{-1}^1\exp(-i\pi k x)f(x)\,dx \approx \frac{1}{2}\sum_{j=-N}^{N-1} \exp(-i\pi k j/N) f(j/N) \frac{2}{2N} = \tilde{c}_k.$$ We can try to express the approximated coefficients $\tilde{c}_k$ by the true coefficients $c_{\ell}$. To that end suppose $S(f) = f$ and use the series representation of $f(j/N)$: \begin{align} \tilde{c}_k &= \frac{1}{2N}\sum_{j=-N}^{N-1} \exp(-i\pi k j/N) f(j/N) \\ &= \frac{1}{2N} \sum_{j=-N}^{N-1} \exp(-i\pi kj/N) \sum_{\ell=-m}^m c_{\ell} \exp(i\pi \ell j/N) \\ &= \frac{1}{2N}\sum_{\ell=-m}^m c_{\ell} \sum_{j=-N}^{N-1} \exp(i\pi (\ell-k) j/N) \\ &= \frac{2N}{2N} \left(\sum_{r\in\mathbb{Z}} c_{2rN+k}\right). \end{align} The last equality holds because if $\ell-k=2rN$ (is a multiple of $2N$) then $$\exp(i \pi (k+\ell) j / N)=\exp(i \pi 2rN j/N)=\exp(i2\pi rj) = 1.$$ And we have 2N summands, so the sum is $2N$. On the other hand when $p=k+\ell\ne 2rN$ the sums are zero, this is the same discrete orthogonality principle used in the DFT \begin{align} \sum_{j=-N}^{N-1} \exp(i \pi p j/N) &= \sum_{j=0}^{2N-1} \exp(i \pi p (j-N)/N) \\ &= \exp(-i\pi)^p\sum_{j=0}^{2N-1} \exp(i \pi p/N)^j \\ \\ &= (-1)^p \frac{\exp(i\pi p/N)^{2N} - 1}{\exp(i\pi p/N)-1} = 0. \end{align} The last holds from the formula for the sum of geometric series.

Ultimately the key observation is that $\tilde{c}_{k} = \sum_{r\in\mathbb{Z}} c_{2rN+k}$. That is, with this sampling we cannot distinguish between waves of frequency $k$ and $2rN+k$. This is precisely what aliasing refers to. The first frequency at which this occurs is $k=N$ since we cannot distinguish it from $k-2N = N-2N = -N$. This is precisely the Nyquist limit as we had $2N$ samples and issues occur at $N$ which is half of the sampling rate $2N$. This also means that if our signal is bandlimited: $c_k=0$ for $|k|\geq N$ we have no issues ($k\geq N$ and $k<-N$ is also fine in the discrete setting with the above formulation).

TLDR

The takeaway of this lengthy example is that aliasing is the result of numerical integration error in your best approximation formulation. For example if you have to draw a triangle, ideally you would color a pixel based on the area of the triangle covering it, but that is expensive, so modern GPUs instead just sample a few locations to approximate coverage. This causes jaggies. Similarly if we have a high resolution texture you can see aliasing clearly. That's why you have mipmaps. Analytic filtering/integration of procedural textures is sometimes also possible.

Finally, if you have a very low resolution screen then even if you were to integrate perfectly within each pixel you would still have a blocky image. The mathematical counterpart of this is truncating the series even if you were to exactly compute the coefficients. In practice, however, a lower screen resolution typically also implies a higher integration error as your rendering resolution is usually tied to the output resolution (unless you decide to render to a target with a resolution several times higher and then downsample, but then again edges have infinite frequencies). I also don't think screen resolution is an issue nowadays since at 4K or 8K I woulad argue your eyes' PSF already filters out any frequencies that would cause aliasing, so the only thing causing aliasing there is integration error from rendering with an insufficient sample rate or/and insufficient prefiltering.

So in theory the answer to your question is it depends. But in practice jaggedness is almost always actual aliasing due to integration error. Regarding different reconstruction functions - yes they will produce different artifacts, the Fourier basis has actually quite unpleasant and global oscillatory artifacts (see Gibbs' phenomenon), on the other hand highly localized and regular stuff like box functions tends to result in more jaggies as you noted. Ideally one would pick something inbetween like Lanczos or w/e, but higher order operators typically suffer from oscillations and halos just like the Fourier basis. Ultimately it's a tradeoff between what kinds of artifacts you want your integration error (or interpolation assumptions) to show up as - blur vs sharpness against halos/oscillations. The sinc function is actually a terrible choice in practice - windowed/weighted sinc functions are more acceptable. Also note that the standard shannon theorem applies only to regular sampling. One can do much better with adaptive sampling and appropriate functions such as wavelets.

$\endgroup$
8
  • $\begingroup$ This is more of a discussion of how to resolve aliasing then it is a description of what aliasing is. If we have two signals of different frequencies, and are trying to generate a mapping between them, we say that the two signals are aliased and we use filtering to approximate an accurate reconstruction of one onto the other. The frequency difference arises in many situations. From digital photography, to drawing simple lines, to shadow mapping, and many more. Not that this isn't a good answer, it just seems to be missing a clear definition of the term. $\endgroup$ Commented Mar 12 at 15:01
  • $\begingroup$ @pmw1234 I don't know about that. The OP started with "In this note, I will argue that the jaggedness observed in rasterized images should not be referred to as aliasing.", with clear emphasis on the above statement. However, in practice "jaggedness" is both a product of the pixels and aliasing. The above definition of aliasing I provided gives a precise meaning of the term, in terms of the coefficients $c_{2rN+k}$ spoiling $\tilde{c}_k$. There is the additional truncation of the series which I would also call aliasing, but that's trickier and would have required a much longer answer. $\endgroup$ Commented Mar 12 at 20:52
  • $\begingroup$ @pmw1234 To adress this part: "The frequency difference arises in many situations. From digital photography, to drawing simple lines, to shadow mapping, and many more.", note that all of those can be modeled in a mathematical framework of best approximation or interpolation. So a generalization of what I derived above would still apply there to some extent. I did elide a discussion of the truncation of the series as well as the difference in bases (i.e. piecewise constant vs trigonometric polynomials), since as mentioned that would require me to write an actual article with examples & proofs. $\endgroup$ Commented Mar 12 at 20:56
  • $\begingroup$ The question argues that aliasing artifacts (jaggedness) is largely the result of sampling below the Nyquist frequency, however aliasing artifacts are typically viewed as a result of improper reconstruction not the sampling process itself. Which your response rightly pointed out. And from a rigorous signal processing stand point this answer is well structured. But in the broader context of computer graphics the term aliasing is used more generally. My comment was putting aliasing into that context instead of the original questions very narrow view on it. $\endgroup$ Commented Mar 12 at 22:22
  • 1
    $\begingroup$ @pmw1234 My point is that there's no impasse. People trying to fit "theory" incorrectly to explain "practice" doesn't mean that the theory and practice are inconsistent or incompatible. The very question of the OP and the sources he cites is a good illustration of this. That's not the first and I am sure won't be the last time where CG folks attempt to retrofit theory incorrectly to explain practice - it happens a lot in CG papers from my experience, e.g. compared to image processing, optimization, or physics research. Granted, this is my anecdotal observation. $\endgroup$ Commented Mar 12 at 23:44

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.