20 January 2014 Jaggies as aliasing or reconstruction phenomena: a tutorial
Author Affiliations +
J. of Electronic Imaging, 23(1), 010801 (2014). doi:10.1117/1.JEI.23.1.010801
Abstract
Jaggies (staircasing effects) along slanted lines or curved edges are omnipresent in digital imaging. They are so widespread in digital display devices that very often they are associated with the modern “computerized” world (and sometimes even intentionally introduced into artworks such as logos, advertisements, etc. to convey a modern “pixelized” look). Although this subject is not new, it still remains an important issue in the design of modern digital display and printing devices. In the classical literature, jaggies are often considered as aliasing artifacts; and yet some other references consider them instead as reconstruction artifacts. The present tutorial revisits this question and tries to elucidate the real nature of this phenomenon using Fourier-based considerations. It shows that the jaggies can be either aliasing artifacts due to poor sampling in capture, or the result of poor reconstruction; and it explains the implications thereof on the elimination of unwanted jaggies.
Amidror and Hersch: Jaggies as aliasing or reconstruction phenomena: a tutorial

1.

Introduction

It is well known that the approximation of continuous lines or shapes by pixels on a discrete raster grid may cause the appearance of jagged edges (also known as “jaggies” or “staircasing effects”) on the shape’s borders (see Refs. 1 and 2, p. 14). Such jaggies often occur during the sampling process (analog-to-digital conversion) along slanted or curved lines. They are most prominent on sharp edges such as black/white transitions, as in Fig. 1(a), but they are also visible in smoother gray-level transitions, as in Fig. 1(b). These jaggies are particularly objectionable at low resolutions (i.e., low sampling rates), but they may still be present even in modern higher-resolution devices. Thus, although jaggies are not new, they are still an important issue in the design of today’s digital devices, as one can judge, for example, by searching for the term “jaggies” in the U.S. patent database; see, for example, the recent U.S. patents 8,350,967, 8,345,063, 8,294,730, 8,260,089, and 6,307,566 (Refs. 34.5.6.7), to mention just a few. It is therefore important to have a good understanding of this phenomenon and its origins.

Fig. 1

Jaggies in discrete-world images: (a) Along sharp edges (here: slanted black lines forming the letter A). (b) Along smooth gray-level shapes (here: a circular cosinusoidal wave).

JEI_23_1_010801_f001.png

In the classical computer graphics literature, and in particular, in the field of digital typography, jaggies are often considered as aliasing effects (see, for example, Ref. 2, pp. 14–15; Ref. 8; or Ref. 9, pp. 45–48). Moreover, the methods devised for reducing the visibility of these jaggies are often called antialiasing methods. On the other hand, other references consider jaggies as artifacts that are due to the reconstruction process (see, for example, Ref. 10, pp. 107–108). Our aim in this tutorial is to elucidate this question based on simple Fourier considerations: It is clear that if jaggies are indeed aliasing phenomena, they must be represented in some way or another in the Fourier domain (i.e., in the frequency spectrum of the sampled image), too. We will see that in many cases, jaggies are indeed aliasing phenomena, but in other cases they are only generated in the reconstruction stage, i.e., when the display device recreates a continuous-world signal from the sampled one.

Note that throughout this tutorial, we assume that the jaggies in question are sufficiently big to be seen by the unaided eye, and we do not discuss issues related to the human visual system, modulation transfer functions, etc. Also, this tutorial does not intend to provide formal theorems and proofs, but rather favors an informal approach using Fourier-based considerations and pictorial illustrations.

2.

Background

Aliasing is a well-known phenomenon which may occur in the discretization (sampling) of an underlying input function. Discretizing an analog signal requires that the signal’s value be sampled often enough to define the waveform unambiguously. According to the classical sampling theorem (see, for example, Ref. 11, p. 115; Ref. 12, Sec. 8–7; or Ref. 13, p. 1593), a sampling frequency of at least twice the highest frequency present in the signal is sufficient for its waveform to be defined completely, and for allowing its correct reconstruction. (Note that lower sampling frequencies may suffice for some special types of functions, as explained in Appendix A; but the classical sampling theorem addresses the general case.) If the sampling points are not taken as densely as required (a situation often called undersampling), they will fail to follow the high-frequency fine details of the signal, thus leading to aliasing. In the signal domain, this is expressed by the existence of a smoother, lower-frequency signal, known as alias, which can be traced through all the sampled points and “mimic” or “masquerade” the behavior of the original signal on its sampled values (see Fig. 2). Only based on these too far-apart sampling points, the original signal is undistinguishable from its lower-frequency aliased signal, since both of them coincide on all of these sampling points. In other words, aliasing means that high-frequency components in the original signal appear incorrectly as lower frequencies in the sampled result.

Fig. 2

Illustration of the signal-domain interpretation of aliasing: (a) Sampling a continuous signal [here: a cosine function g(x)=cos(2πfx) with frequency f=2] at a rate higher than twice the maximum signal frequency gives a correct discrete representation of the original signal. (b) Sampling the same continuous signal at a rate lower than twice the maximum signal frequency gives a false, aliased lower-frequency signal (here: a cosine function with frequency f=0.25) that mimics the original signal on its sampled values. Both signals are drawn with continuous lines and their sampled values are indicated by black dots.

JEI_23_1_010801_f002.png

This is the interpretation of aliasing in terms of the signal domain, but the aliasing phenomenon can be also interpreted from the viewpoint of the spectral domain. Remember that sampling in the signal domain is equivalent to multiplying the original continuous signal g(x) by (1/Δx)III(x/Δx), a periodic unit-height impulse comb (impulse train) having an impulse interval of Δx (see Fig. 3). The Fourier transform of this sampling impulse comb is itself an impulse comb with impulse interval of fs=1/Δx and impulse height of 1/Δx (see, for example, Ref. 14, pp. 227–228; Ref. 15, p. 577):

(1)

F[(1/Δx)III(x/Δx)]=III(Δxu).

Fig. 3

Schematic illustration of the Fourier-domain interpretation of aliasing: (a) An original continuous-world signal g(x) and its spectrum G(u). (b) The sampling impulse train and its spectrum. (c) The sampled signal is the product of the signals (a) and (b), and therefore its spectrum is the convolution of their spectra. Note the replicas of the original spectrum that are located at all integer multiples of the sampling frequency fs. (d) If the sampling rate is lower than twice the maximum signal frequency fG (say, fs), then each two neighboring replicas of G(u) overlap (additively), giving false aliased frequencies in the overlapped zones. The aliased parts of the spectrum in (d) are shown by thick dashed lines, which are simply the sum of the original overlapped replicas. The horizontal arrows in (c) and (d) indicate the frequency range that is obtained by discrete Fourier transform (DFT), spanning between minus half and plus half of the sampling frequency.

JEI_23_1_010801_f003.png

[Note that due to the impulse property δ(x/a)=|a|δ(x) (Ref. 15, p. 80) the impulse height of the comb III(x/Δx) is Δx (Ref. 15, p. 577), and its unit-height counterpart is (1/Δx)III(x/Δx). Similarly, the impulse height of III(Δxu) is 1/Δx].

Therefore, by virtue of the convolution theorem, the effect on the spectral domain of sampling g(x) is that G(u), the original spectrum of g(x), is now convolved with the impulse comb (1). This means that the spectrum of the sampled version of g(x) consists of infinitely many identical replicas of the spectrum G(u), which are scaled by 1/Δx (in terms of the amplitude) and centered about all the integer multiples of the sampling frequency fs=1/Δx (see, for example, Ref. 14, pp. 227–229 or Ref. 16, pp. 79–81):

(2)

F[(1/Δx)III(x/Δx)g(x)]=F[(1/Δx)III(x/Δx)]*F[g(x)]=III(Δxu)*G(u),
where * is the convolution operator.

Note that if the spectrum G(u) of the original function g(x) is continuous, so is the periodic spectrum (2) of the sampled version of g(x).

Let us now denote by fG the highest frequency in G(u). As long as the sampling frequency fs=1/Δx is at least twice fG, as required by the classical sampling theorem, the replicas of G(u) are sufficiently far from each other to avoid overlapping [Fig. 3(c)]. But if the sampling frequency is lower than twice fG, every two neighboring replicas of G(u) will somewhat overlap [Fig. 3(d)]; note that this overlapping is additive due to the properties of convolution. This means in particular that frequencies from the neighboring replicas will penetrate into the main replica (the replica which is centered about the origin) and appear in the spectrum as parasite, false lower frequencies, known as aliased frequencies. Note that in this case, too, all of the replicas are identical; however, none of them (including the main replica) remains identical to the original spectrum G(u) itself, since they have all been corrupted (additively overlapped) by frequencies (positive or negative) belonging to their neighboring replicas [see Fig. 3(d)].

The above discussion about aliasing can also be extended to the two-dimensional (2-D) or multidimensional cases. In such cases, sampling in the signal domain and the resulting convolution in the spectral domain [Eq. (2)] are simply extended to two or M-dimensions (we assume here that the same sampling interval Δx is used along all the M dimensions, but if required it is also possible to use along each dimension a different sampling interval):

(3)

F[(1/Δx)MIII(x/Δx)g(x)]=F[(1/Δx)MIII(x/Δx)]*F[g(x)]=III(Δxu)*G(u),
where x, uRM, III(x/Δx) is the M-dimensional sampling impulse comb (having an impulse interval of Δx along each dimension), and * is the M-dimensional convolution operator.

3.

Jaggies, Aliasing, and Reconstruction

Having reviewed the image-domain and the spectral-domain manifestations of aliasing, how can this phenomenon be related to jaggies?

Let us consider, as an illustrative example, a slightly rotated periodic line grating, i.e., a periodic sequence of 1-valued lines with period T and width 0<τ<T on a 0-valued background (see Fig. 4, where black is negative, white is positive, and midgray is zero). Its original spectrum, before sampling, is a slightly rotated infinite comb whose impulse interval is equal to the frequency of the line grating, and whose impulse strengths are modulated by a sinc function [which is 1/T of the spectrum of a single line of width τ; see Ref. 17, pp. 21–23 for the one-dimensional (1-D) case]. This spectrum is obviously not band limited. After sampling, as we have seen in Eq. (3), the continuous-world spectrum of the resulting sampled grating consists of the original comb plus infinitely many replicas of this comb that are centered about each impulse of a nailbed (which is itself the Fourier transform of the sampling nailbed). This is shown in Fig. 4 [note that the spectra are obtained by discrete Fourier transform (DFT), and they are only shown between the frequencies (1/2)fs and (1/2)fs along both of the axes, where fs is the sampling frequency]. This means that the spectrum of the sampled grating contains many new impulses belonging to the new replicas. If any of these new impulses falls close enough to the spectrum origin, as in Fig. 4(c) (note the two encircled impulses), a new low-frequency structure (moiré effect) becomes visible in our sampled grating, as shown by the arrows in the image domain (for more details on the sampling moiré effects see, for example, Ref. 17, Sec. 2.13). But even if none of the new impulses falls close to the spectrum origin and causes a moiré effect [see Fig. 4(b)], it is clear that these new impulses still must correspond to some new structures in the sampled grating, which did not exist in the original, continuous grating. Indeed, it turns out that these new impulses represent new frequencies that correspond to the jaggedness of the sampled grating.

Fig. 4

Aliasing in the two-dimensional (2-D) case: A simple example where the spectrum consists of a one-dimensional (1-D) impulse comb. The original continuous-world function in the signal domain is a vertical line grating that has been slightly rotated by angle θ. Its spectrum is a horizontal infinite impulse comb through the spectrum origin that is slightly rotated by the same angle θ, and whose impulse interval is equal to the frequency of the grating (see, for example, Ref. 17, pp. 23–25). After sampling, the spectrum of the resulting sampled grating consists of the original comb plus infinitely many replicas of this comb, that are centered about the points (kfs, lfs), where fs is the sampling frequency in both directions and k, lZ. In each of the rows of this figure the left-hand column shows the sampled, discrete-world signal and the right-hand column shows its spectrum (as obtained by DFT) between the frequencies (1/2)fs and (1/2)fs in both directions. The only difference between the three rows is in the rotation angle θ: (a) θ=0deg; (b) θ=14deg; and (c) θ=3deg. In case (c), due to the small rotation angle, the replicas of the original comb form a sharper angle θ with the horizontal axis of the spectrum, and thus they fall much closer to the original comb itself [compare the spectra in rows (b) and (c)]. In such cases, impulses of the replicas may fall very close to the spectrum origin (see the two impulses marked by circles). Indeed, these impulses correspond to a new low-frequency parasite structure (sampling moiré) which is clearly visible in the sampled line grating (see the arrows in the signal domain). But even when none of the new impulses falls close to the spectrum origin [as in row (b)], it is clear that these new impulses still must correspond to some new structures in the sampled gratings; and as we will see below, they correspond indeed to the jaggedness of the sampled grating. The cross-like oscillations, which surround impulses in the spectra of (b) and (c), are due to the leakage artifact of the DFT (see, for example, Ref. 16, Sec. 6.4). Note that in this and the following figures gray levels represent the displayed values: black is negative, white is positive, and midgray is zero.

JEI_23_1_010801_f004.png

To see this, consider Fig. 5, which is intentionally drawn at a lower resolution so that the individual jaggies as well as the individual impulses in the spectrum can be clearly visible. Figure 5(a) shows the sampled grating and its spectrum as obtained by DFT. As we can see, the spectrum contains the main, original impulse comb (the slightly rotated comb passing through the origin, which is indicated by the arrows) plus impulses belonging to its new replicas due to the sampling. In order to see the influence of these new impulses, let us zero all of them, leaving in the spectrum only the impulses belonging to the original comb. The corresponding structure back in the signal domain is obtained by taking the inverse DFT of this spectrum. The results of this manipulation are shown in Fig. 5(b). As we can see in this figure, the effect on the signal domain of eliminating the impulses of the new replicas (the aliased impulses) consists of smoothing out the jagged edges of the sampled grating (see the gray level pixels along the line edges). Note, however, that this does not yet completely eliminate the jaggies; as we will see later, the residual jaggies that we still see in Fig. 5(b) are reconstruction artifacts that occur due to the square pixels being used to draw the sampled signal. Finally, Fig. 5(c) shows what happens if we zero in the spectrum of Fig. 5(a) the impulses of the original comb and keep only the new impulses that are due to the sampling. Once again, the corresponding structure back in the signal domain is obtained by taking the inverse DFT of this spectrum. Note that the signal-domain structure in Fig. 5(c) is simply the difference between the jagged grating of Fig. 5(a) and its smoothed-out version of Fig. 5(b); this difference corresponds, indeed, to the net effect of the jaggies themselves on the line edges.

Fig. 5

Jaggies along the edges of a sampled, slightly rotated line grating, and their spectral representation. (a) The sampled grating and its spectrum (as obtained by DFT) between the frequencies (1/2)fs and (1/2)fs in both directions; the arrows in the spectrum show the main comb. (b) The impulses of the main comb alone, after zeroing all the remaining aliased impulses, and the corresponding signal-domain structure obtained by inverse DFT. (c) The aliased impulses outside the main comb, after zeroing the impulses of the main comb, and the corresponding signal-domain structure obtained by inverse DFT. As shown in (b), the effect on the signal domain of eliminating the impulses of the other replicas (the aliased impulses) consists of smoothing out the jagged edges of the sampled grating (see the gray level pixels along the line edges). The signal-domain structure in (c) is simply the difference between the jagged grating of (a) and its smoothed-out version of (b); this difference corresponds, indeed, to the net effect of the jaggies themselves on the line edges. Note that for the sake of simplicity, the grating shown in (a) is perfectly symmetric about its origin, so that the resulting spectrum is purely real-valued. If the original continuous-world grating is slightly shifted before sampling, the jaggies in (a) may vary and lose their perfect symmetry; in this case, each spectral component will also have an imaginary-valued part as predicted by the 2-D shift theorem (Ref. 18, p. 156), but except for having in that case complex-valued impulses, nothing in our discussion will be changed. Note also that in the present figure, there are no leakage artifacts because the figure is perfectly wraparound (see Sec. 6.4 in Ref. 16 for the 1-D case or Sec. 6.6 and Remark 6.7 in Ref. 19 for the 2-D case).

JEI_23_1_010801_f005.png

Although these Fourier-based considerations are most easily illustrated in periodic structures as in Fig. 5 (since their spectra are purely impulsive), it is clear that jaggies do not only occur in periodic structures. To illustrate a simple aperiodic case consider Fig. 6, which shows a single slightly rotated line of width τ>0. The spectrum of this aperiodic structure consists of a continuous infinitely long line impulse (a “blade”) passing through the origin, whose amplitude is modulated by a sinc function, and which is slightly rotated by the same angle (Ref. 19, pp. 332–334). In this case, too, the spectrum is obviously not band limited, so that the sampled signal will suffer from aliasing. After sampling, the spectrum of the resulting sampled line consists of the original line impulse plus infinitely many replicas thereof. Figure 6(a) shows the sampled line and its DFT spectrum. Figure 6(b) shows the main line impulse, after zeroing all its replicas (the aliased elements) in the DFT spectrum, and the corresponding signal-domain counterpart obtained by inverse DFT. Finally, Fig. 6(c) shows only the replicas of the line impulse, after zeroing the main line impulse itself, and the corresponding signal-domain counterpart obtained by inverse DFT. As in Fig. 5, the effect on the signal domain of eliminating the aliased elements from the spectrum consists of smoothing out the jagged edges of the sampled line.

Fig. 6

Same as in Fig. 5, except that this time the original continuous-world signal is not a slightly rotated line grating, but only a single line taken from this grating (the central one). The spectrum of this line consists of a continuous line impulse passing through the origin whose amplitude is modulated by a sinc function, and which is slightly rotated by the same angle. After sampling, the spectrum of the resulting sampled line consists of the original line impulse (indicated by arrows) plus infinitely many replicas of this line impulse, that are centered about the points (kfs, lfs), where fs is the sampling frequency in both directions and k, lZ. (a) The sampled line and its spectrum (as obtained by DFT) between the frequencies (1/2)fs and (1/2)fs in both directions. (b) The main line impulse, after zeroing all its replicas in the DFT spectrum, and the corresponding signal-domain structure obtained by inverse DFT. (c) The replicas of the line impulse, after zeroing the main line impulse, and the corresponding signal-domain structure obtained by inverse DFT. As in Fig. 5, the effect on the signal domain of eliminating the aliased elements from the spectrum consists of smoothing out the jagged edges of the sampled line. The ripple effect in the DFT spectrum is due to the leakage; leakage artifacts are present here because in this case the signal-domain figure is not wraparound (see, for example, Sec. 6.6 in Ref. 19).

JEI_23_1_010801_f006.png

Note that in both Figs. 5 and 6, the jaggies occur on slanted edges. In both cases, if the lines in the signal domain are purely vertical (or horizontal) no jaggies appear on their edges. Indeed, in such cases, the new replicas in the DFT spectrum due to the sampling fall on top of the original replica, and no new frequencies are generated that correspond to jaggies [see Figs. 4(a) and 7].

Fig. 7

A sampled vertical line grating may have a sampling moiré effect (note the periodically repeating thicker vertical lines) due to the new aliased low frequencies that appear due to an interaction with the sampling frequency. Compare with Fig. 4(a), where no sampling moiré occurs. In both cases, no jaggies are present.

JEI_23_1_010801_f007.png

As we can see, there is indeed strong evidence in favor of considering jaggies as aliasing phenomena. Furthermore, just like the previously discussed facets of aliasing (masquerading lower frequencies in the signal domain or overlapping of replicas in the spectral domain), jaggies, too, tend to become less prominent when we increase the sampling resolution or when we apply low-pass filtering prior to the sampling, so that sharp transitions become smoother.1,20

On the other hand, there are also good reasons against considering jaggies as aliasing phenomena. For example, there exist many structures that present strong aliasing, but have no jaggies at all (for instance, as shown in Fig. 7, a sampled horizontal or vertical line grating may have a sampling moiré effect due to new aliased low frequencies without having jaggies). This means, indeed, that aliasing does not necessarily cause jaggies. But furthermore, jaggies may also exist when there is no aliasing at all—for example, in a 2-D plot of a slightly rotated cosinusoidal grating, whose frequency is far below half of the sampling frequency (see Fig. 8). How can this be explained?

Fig. 8

Low-resolution figure showing a slightly rotated cosine wave of frequency f=0.88 and its spectrum. Note that jaggies are visible although the sampling frequency fs=4 is higher than 2f, and no aliasing occurs in the sampling process.

JEI_23_1_010801_f008.png

The key for understanding this question resides in the ambiguity of the term aliasing. This term is used in the literature for two different effects: (1) the distortion that is produced by poor sampling, and which causes the sampled signal to become indistinguishable from a lower-frequency signal (an alias); and (2) the distortion that is produced by poor reconstruction, which causes the signal that is reconstructed from the samples to be different from the original continuous signal (again, an alias). Note that both of these problems originate from failures in the correct application of the sampling theorem: the failure to fulfil the required condition on the frequencies leads to sampling aliasing; while the failure to approximate ideal reconstruction leads to reconstruction error. To resolve this terminological ambiguity, we will henceforth call the first, classical effect aliasing due to the sampling or sampling aliasing, while the second effect will be called reconstruction error [other terms being sometimes used in the literature are prealiasing and postaliasing, respectively (see Ref. 21, p. 222)]. Let us explain this in more detail.

Sampling is the process that converts a continuous signal to a discrete one, while reconstruction is the process that recreates a continuous signal from its samples (Ref. 2, Sec. 14.10.5; Ref. 21). Note that theoretically, a sampled signal consists of zero-width impulses (of varying heights), and not of real-world “pixels” having square or circular shapes. It is precisely the reconstruction process that brings back the “flesh” around each of the sampled “bones.” Now, according to the classical sampling theorem, all the information in the original continuous signal is preserved in its sampled version, if the sampling frequency is at least twice the highest frequency contained in the signal. Under this condition, the theorem guarantees that the original continuous signal can be perfectly reconstructed by multiplying the spectrum of the sampled signal with a rect function that cuts off all the frequencies beyond half of the sampling frequency, or equivalently, by convolving the sampled signal with the Fourier transform of this rect function, i.e., with the corresponding narrow sinc function (Ref. 16, p. 83). This is easier to understand in the spectral domain, as is clearly shown in the right-hand column of Figs. 3 and 9. To formulate the perfect reconstruction process shown in Fig. 9 mathematically, let us denote our sampled signal by s(x)=(1/Δx)III(x/Δx)g(x) and its spectrum by S(u)=III(Δxu)*G(u) [see row (c) in Fig. 3, which has been copied into row (a) of Fig. 9]. We also denote the ideal rect function that cuts off all the frequencies above (1/2)fs and below (1/2)fs by Δx rect(u/fs), where fs=1/Δx is the sampling frequency [see Fig. 9(b); the constant factor Δx=1/fs is required to normalize the heights]. Then, the product of the spectra in rows (a) and (b) of Fig. 9 gives back, as we can see in Fig. 9(c), the original spectrum G(u):

(4)

S(u)Δxrect(u/fs)=G(u).

Fig. 9

Continuation of Fig. 3 showing schematically the signal and spectral domain representations of an ideal reconstruction process, which gives back exactly the original continuous signal we had before sampling. (a) The sampled signal, as in Fig. 3(c). (b) The ideal reconstruction function according to the classical sampling theorem (a narrow sinc function of height 1) and its spectrum, which is a rect function of height 1/fs=Δx that extends from (1/2)fs to (1/2)fs. (c) The perfectly reconstructed signal [convolution of the signals (a) and (b)] and its spectrum [product of the spectra (a) and (b)]. Note that the reconstructed signal in row (c) is indeed identical to the original continuous signal shown in row (a) of Fig. 3.

JEI_23_1_010801_f009.png

Therefore, in the signal domain of Fig. 9(c), the convolution of the sampled signal s(x) with F1[Δxrect(u/fs)]=sinc(fsx) yields, indeed, a perfect reconstruction of our original signal g(x):

(5)

s(x)*sinc(fsx)=g(x).

However, in practice, the reconstruction of a sampled signal is never done by convolving its impulses with an infinite-range sinc function, as stipulated by the classical sampling theorem and shown in Fig. 9. Instead, each impulse of the sampled signal is typically represented (i.e., convolved) by a pulse function p(x), whose width equals the distance between two consecutive samples (see Fig. 10). [This is, of course, a theoretic idealization, since usually p(x) is not a perfect rectangle.] Stating this mathematically, in the case of real-world reconstruction we get in the spectral domain the product [see Fig. 10(c)]:

(6)

S(u)P(u)G(u),
[where P(u) is the spectrum of p(x)] rather than the perfectly reconstructed spectrum of Eq. (4). Indeed, in the signal domain of Fig. 10(c), the convolution of the sampled signal s(x) with the “pixel” p(x) does not yield a precise copy of our original signal g(x) but rather a pixelized or jagged version thereof:

(7)

s(x)*p(x)g(x).

Fig. 10

Continuation of Fig. 3 showing schematically the signal and spectral domain representations of a nonideal reconstruction process, that causes reconstruction artifacts. (a) The sampled signal, as in Fig. 3(c). (b) A nonideal reconstruction function (a rect function representing a square pixel) and its spectrum, which is a sinc function that extends ad infinitum. (c) The reconstructed signal [convolution of the signals (a) and (b)] and its spectrum [product of the spectra (a) and (b)]. Row (c) is not identical to row (a) in Fig. 3, and it contains reconstruction artifacts (note the debris from the neighboring replicas that give new high-frequency noise in the resulting reconstructed signal).

JEI_23_1_010801_f010.png

Similarly, in the 2-D case (like in computer displays or in digital printing devices) each impulse of the sampled signal s(x,y) to be displayed is convolved with a single pixel shape p(x,y) (which may be, depending on the device, a square dot, a circular dot, etc.). The resulting reconstructed signal may therefore have highly visible jaggies along its borders (see Fig. 8), and possibly also sharp transitions between the values of neighboring pixels. These elements correspond to new high frequencies in the reconstructed signal that are not present in the samples, and which do not exist in the original, continuous signal g(x,y), either (see the 1-D spectral domain explanation of Fig. 10). This process results in reconstruction errors, since when the resolution of the display device is not sufficient the reconstructed image differs significantly from the original continuous image (it is pixelized and jagged), and what we actually see is an alias. This kind of “aliasing” has nothing to do with undersampling and it is solely due to poor reconstruction; indeed, as already mentioned above, this phenomenon may occur even in cases which are completely alias-free (in the classical sense), as in Fig. 8.

Note that in some cases the individual display-device pixel p(x,y) is smoother and has the shape of a narrow 2-D Gaussian; this is often the case in CRT displays. In such cases reconstruction errors still exist (although they look smoother), since the spectrum of a Gaussian is itself a Gaussian (Ref. 18, p. 149), which is obviously not a band-limited spectrum.

Let us now return to our original question. As we can see in Figs. 5 and 6, in many cases jaggies indeed result from the sampling aliasing, and they are represented in the spectrum by aliased elements (this is particularly evident when sampling a 2-D signal involving slanted sharp transitions, which is not band limited and hence suffers from aliasing). Clearly, jaggies are further amplified by the reconstruction errors (poor reconstruction of the signal). However, they can even be generated by the reconstruction errors if they have not already been generated due to the sampling aliasing. This is the case, for example, in a slightly rotated low-frequency cosinusoidal grating, which is clearly band limited and has no sampling aliasing (the impulse samples along the corrugations of the sampled cosinusoidal grating are gradually attenuated in such a way that no jaggies are apparent). In cases like this, if the reconstruction is correctly done, as stipulated by the classical sampling theorem, no jaggies should appear in the reconstructed signal; and if jaggies do appear—as in Fig. 8—this is only due to the reconstruction error. Indeed, this observation led some references to say that jaggies are not aliasing artifacts as often claimed in the literature, but rather reconstruction artifacts (see, for example, Ref. 10, pp. 107–108).

In conclusion, we see that jaggies have mixed origins: in some cases as in Figs. 5 and 6, they are due to the sampling aliasing (although even then they may be further amplified by poor reconstruction); but in other cases, like in a low-resolution cosinusoidal grating (Fig. 8), they are a pure product of poor reconstruction. In the first case, jaggies clearly manifest themselves as aliased elements in the spectrum of the sampled signal, but in the latter case they do not, since they only occur in a later stage, during the reconstruction of the continuous signal (hence the name postaliasing). Of course, they would have appeared in the continuous-world spectrum of the reconstructed signal, as shown in Fig. 10(c), had we cared to produce such a spectrum.

Finally, let us return to the question with which we opened this section: What is the connection between the sampling-induced jaggies and the classical manifestations of aliasing (masquerading lower-frequencies in the signal domain or spectral replications in the spectral domain)? Indeed, the most notorious signal-domain manifestation of aliasing consists of cases where new very low-frequency structures appear due to the sampling process, as shown in Fig. 2(b) for the 1-D case and in Fig. 4(c) for the 2-D case. These new very low-frequency structures are simply sampling moirés. But the spectral-domain replicas due to the sampling process may also introduce new aliased frequencies that are higher than this. These new higher frequencies contribute to the microstructure details of the sampled signal and give it its typical jagged look, as shown for example in Fig. 5.

4.

Discussion

The fact that jaggies can result either from poor sampling or from poor reconstruction (or both) has a direct implication on the methods to be used for their elimination. Clearly, jaggies that are generated by aliasing (poor sampling) will not be eliminated by improvements in the reconstruction stage (see a spectral-domain illustration in Fig. 11 and a signal-domain illustration in Fig. 12). Similarly, jaggies that are only due to poor reconstruction (as in Fig. 8) will not be eliminated by improvements in the sampling stage, such as prefiltering of the original signal before its sampling or other antialiasing methods. Thus, whenever it is needed to eliminate jaggies, for example, during the developing process of a new display device, it is important to first precisely understand the origin of the jaggies in question before trying to set up an adequate solution. The optimal way for eliminating (or at least reducing) jaggies on a display device depends, of course, on the specific properties of the device in question, as we can see from the multitude of patents that continue to be issued on this subject year by year. Of course, as a general rule, increasing the device resolution whenever this is feasible, will also decrease the size of the jaggies, and hence reduce their visibility. On very high resolution devices display artifacts such as jaggies will no longer be visible to the unaided eye.

Fig. 11

Same as Fig. 9, but this time we take as our starting point row (d) of Fig. 3 (i.e., a poorly sampled and slightly aliased signal) rather than row (c) of Fig. 3 (a correctly sampled signal). In such cases, even a convolution with a narrow sinc reconstruction function, as we did in Fig. 9, will not be able to recover from the sampled signal the original jagless, continuous-world signal, since a multiplication in the spectral domain with the corresponding rect function will not be able to eliminate the aliased frequencies. (a) The poorly sampled and aliased signal of Fig. 3(d). (b) The narrow sinc reconstruction function whose spectrum is a rect function extending from minus half to plus half of the sampling frequency fs. (c) The reconstructed signal [convolution of the signals (a) and (b)] and its spectrum [product of the spectra (a) and (b)]. Note that the reconstructed signal in row (c) is contaminated by new high frequencies, and is not identical to the original continuous signal shown in row (a) of Fig. 3, even though we have used here a good reconstruction function. Because in this case the conditions required by the sampling theorem are not met in the sampling stage, the results stipulated by the theorem for the reconstruction stage are no longer guaranteed (see Appendix A). This figure illustrates the fact that jaggies or other parasite phenomena that are due to poor sampling cannot be eliminated by a general recipe improving the reconstruction process (for example, by using a narrow sinc-shaped element, as done in this figure, rather than the narrow rect pixel usually used in the display devices).

JEI_23_1_010801_f011.png

Fig. 12

Looking at Fig. 8, it may be tempting to say that pixelization and jaggies originate from improper reconstruction (for example, due to the use of square pixels rather than narrow 2-D sinc-shaped elements). However, this is not always true, and sometimes jaggies originate from improper sampling, and no general recipes for improvements in the reconstruction stage can eliminate them. The present figure illustrates this more intuitively, directly in the signal domain, showing the sampled versions of a slightly rotated binary (0/1-valued) line in (a), and of a low frequency cosinusoidal function (whose values vary between 0 and 1) in (b). Both of the sampled signals (a) and (b) are shown before reconstruction, i.e., as pure impulses before their convolution with the pixel function p(x,y). Note that in (b) the sampled cosinusoidal structure consists of impulses with gradually varying values, whereas in (a) the sampled slanted line consists of only 0- and 1-valued impulses, so that sharp 0/1 transitions are omnipresent. In the cosinusoidal case, where the signal varies slowly, a convolution with a narrow 2-D sinc-shaped pixel can yield a smooth, continuous reconstructed structure, as stipulated by the classical sampling theorem. But this is hopeless in the case of the binary line, which is not band limited and therefore does not meet the conditions of the sampling theorem.

JEI_23_1_010801_f012.png

5.

Conclusion

Digital devices such as smartphone displays, computer displays, printers, etc., are being constantly developed and improved. Rendering of digital text and graphics on such devices involves conversions from analog to digital and back, yielding jaggies as unavoidable artifacts. Although this phenomenon is not new, it still remains an important issue in the design of modern digital display and printing devices. The present tutorial sheds some light on this phenomenon. Based on simple Fourier considerations it shows that jaggies can be, depending on the case, either the outcome of aliasing, i.e., a sampling artifact, or a reconstruction artifact. This also has a direct impact on the methods to be used for the elimination of undesirable jaggies, since antialiasing methods, such as prefiltering, will not eliminate jaggies that are reconstruction artifacts and vice versa. Understanding the real nature of the jaggies in each case may therefore help in their elimination (when they are indeed undesired). Note that our discussion here is completely general, and applies also to the three-dimensional (3-D) case, where jaggies are generated by 3-D printing devices.

Appendices

Appendix A

As mentioned earlier, the classical sampling theorem says that all the information in the original continuous signal is preserved in its sampled version if the sampling frequency is at least twice the highest frequency contained in the signal. Under this condition, the theorem guarantees (see Fig. 9) that the original continuous signal can be perfectly reconstructed by multiplying the spectrum of the sampled signal with a rect function that cuts off all the frequencies beyond half of the sampling frequency, or equivalently, by convolving the sampled signal with the Fourier transform of this rect function, i.e., with the corresponding narrow sinc function (Ref. 16, p. 83).

Figures 11 and 12 show that when the conditions required by the classical sampling theorem are not met in the sampling stage (i.e., when the sampling frequency is not at least twice the highest frequency contained in the original unsampled signal), the results stipulated by the theorem for the reconstruction stage are not guaranteed. In such cases, the narrow sinc reconstruction function is not necessarily optimal (see Fig. 11). Moreover, in such cases, there may exist no general recipe for reconstruction functions that can recover the original continuous-world signal (and hence eliminate all jaggies). Yet, the mere fact that the conditions of the classical sampling theorem (known as Nyquist conditions) are not met does not yet imply that no optimal reconstruction function may exist. Indeed, for certain families of signals that do not meet the Nyquist conditions there still may exist particular variants of the sampling theorem that allow to recover the original signal from its samples using some particular reconstruction functions (see, for example, Refs. 22 and 23). But such reconstruction functions are obviously not general, and they only work for the respective families of input signals.

In conclusion, we see that nothing general can be said about cases in which the conditions of the classical sampling theorem are not met, and the situation then should be studied on a case-by-case basis.

Readers who wish to deepen their understanding of the generalized sampling theory and to break out of the unrealistic case of band-limited signals may refer to Ref. 23, which goes much beyond the theory required for the present tutorial.

Acknowledgments

This tutorial is an extended version of material that appeared recently in Sec. 8.5 of the book, Ref. 19 published by Springer.

References

1. 

F. C. Crow, “The aliasing problem in computer-generated shaded images,” Commun. ACM 20(11), 799–805 (1977).CACMA20001-0782http://dx.doi.org/10.1145/359863.359869Google Scholar

2. 

J. D. Foleyet al., Computer Graphics: Principles and Practice, 2nd ed., Addison-Wesley, Reading, Massachusetts (1990).Google Scholar

3. 

R. H. WymanB. Schoner, “Method and system for reducing the appearance of jaggies when deinterlacing moving edges,” U.S. Patent 8,350,967 (January 8 2013).Google Scholar

4. 

K. Iourchaet al., “Filtering method and apparatus for anti-aliasing,” U.S. Patent 8,345,063 (January 1 2013).Google Scholar

5. 

Ch. Tremblay, “Anti-aliasing of a graphical object,” U.S. Patent 8,294,730 (October 23 2012).Google Scholar

6. 

A. V. Tonissonet al., “Orientation adapted aliasing cancellation,” U.S. Patent 8,260,089 (September 4 2012).Google Scholar

7. 

W. Hillet al., “Methods and apparatus for performing image rendering and rasterization operations,” U.S. Patent 6,307,566 (October 23 2001).Google Scholar

8. 

T. Duff, “Polygon scan conversion by exact convolution,” in Raster Imaging and Digital Typography, J. AndréR. D. Hersch, Eds., pp. 154–168, Cambridge University Press, Cambridge (1989).Google Scholar

9. 

R. Rubinstein, Digital Typography: An Introduction to Type and Composition for Computer System Design, Addison-Wesley, Reading, Mass. (1988).Google Scholar

10. 

G. Wolberg, Digital Image Warping, IEEE Computer Society Press, California (1990).Google Scholar

11. 

R. W. Ramirez, The FFT: Fundamentals and Concepts, Prentice Hall, Englewood Cliffs, New Jersey (1985).Google Scholar

12. 

J. D. Gaskill, Linear Systems, Fourier Transforms, and Optics, Wiley, New York (1978).Google Scholar

13. 

E. W. Weisstein, CRC Concise Encyclopedia of Mathematics, CRC Press, Boca Raton (1999).Google Scholar

14. 

K. R. Castleman, Digital Image Processing, Prentice Hall, Englewood Cliffs, New Jersey (1979).Google Scholar

15. 

R. N. Bracewell, The Fourier Transform and its Applications, 3rd ed., McGraw-Hill, Boston (2000).Google Scholar

16. 

E. O. Brigham, The Fast Fourier Transform and its Applications, Prentice-Hall, Englewood Cliffs, New Jersey (1988).Google Scholar

17. 

I. Amidror, The Theory of the Moiré Phenomenon, Volume I: Periodic Layers, 2nd ed., Springer, New York (2009).Google Scholar

18. 

R. N. Bracewell, Two Dimensional Imaging, Prentice Hall, Englewood Cliffs, N.J. (1995).Google Scholar

19. 

I. Amidror, Mastering the Discrete Fourier Transform in One, Two or Several Dimensions: Pitfalls and Artifacts, Springer, Berlin (2013).Google Scholar

20. 

S. GuptaR. F. Sproull, “Filtering edges for gray-scale displays,” Comput. Graph. 15(3), 1–5 (1981).0097-8493http://dx.doi.org/10.1145/965161Google Scholar

21. 

D. P. MitchellA. N. Netravali, “Reconstruction filters in computer graphics,” Comput. Graph. 22(4), 221–228 (1988).0097-8493http://dx.doi.org/10.1145/378456Google Scholar

22. 

M. MishaliY. C. Eldar, “Sub-Nyquist sampling,” IEEE Signal Process. Mag. 28(6), 98–124 (2011).ISPRE61053-5888http://dx.doi.org/10.1109/MSP.2011.942308Google Scholar

23. 

M. UnserA. Aldroubi, “A general sampling theory for nonideal acquisition devices,” IEEE Trans. Signal Process. 42(11), 2915–2925 (1994).ITPRED1053-587Xhttp://dx.doi.org/10.1109/78.330352Google Scholar

Biography

Isaac Amidror received a BSc degree in mathematics from the Hebrew University of Jerusalem, Israel, and an MSc degree in computer science from the Weizmann Institute of Science in Rehovot, Israel. He received a Japanese government scholarship for a 2-year research period in the Computer Science Department of the Toyohashi University of Technology in Japan. After having worked for a few years in industry (notably in the fields of laser printing and digital typography), he received the PhD degree from the Swiss Federal Institute of Technology (EPFL), Lausanne, Switzerland. He is the author of three books (two volumes on the moiré phenomenon and one on the discrete Fourier transform). He also published numerous scientific papers and is inventor or coinventor of several patent applications. His research interests include the mathematical foundations of moiré phenomena, security printing, and image processing in general.

Roger D. Hersch received the engineering and PhD degrees from ETH Zurich in 1975 and from EPFL in 1985, respectively. He is a professor of computer science and head of the Peripheral Systems Laboratory at the Ecole Polytechnique Fédérale de Lausanne (EPFL), Switzerland. He has published more than 150 scientific papers and is inventor or coinventor in many patent applications. His inventions are present in security documents such as passports, ID cards, and train tickets. He is interested in novel imaging techniques related to color prediction, color reproduction, artistic imaging, and security printing. He is a member of the IEEE Computer Society and a fellow of IS&T (Society for Imaging Science and Technology).

Isaac Amidror, Roger D. Hersch, "Jaggies as aliasing or reconstruction phenomena: a tutorial," Journal of Electronic Imaging 23(1), 010801 (20 January 2014). http://dx.doi.org/10.1117/1.JEI.23.1.010801
Submission: Received ; Accepted
JOURNAL ARTICLE
12 PAGES


SHARE
KEYWORDS
Convolution

Signal processing

Fourier transforms

Printing

3D printing

Smoothing

Visible radiation

Back to Top