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.
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.
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.
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 by , a periodic unit-height impulse comb (impulse train) having an impulse interval of (see Fig. 3). The Fourier transform of this sampling impulse comb is itself an impulse comb with impulse interval of and impulse height of (see, for example, Ref. 14, pp. 227–228; Ref. 15, p. 577):
Therefore, by virtue of the convolution theorem, the effect on the spectral domain of sampling is that , the original spectrum of , is now convolved with the impulse comb (1). This means that the spectrum of the sampled version of consists of infinitely many identical replicas of the spectrum , which are scaled by (in terms of the amplitude) and centered about all the integer multiples of the sampling frequency (see, for example, Ref. 14, pp. 227–229 or Ref. 16, pp. 79–81):
Note that if the spectrum of the original function is continuous, so is the periodic spectrum (2) of the sampled version of .
Let us now denote by the highest frequency in . As long as the sampling frequency is at least twice , as required by the classical sampling theorem, the replicas of are sufficiently far from each other to avoid overlapping [Fig. 3(c)]. But if the sampling frequency is lower than twice , every two neighboring replicas of 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 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 -dimensions (we assume here that the same sampling interval is used along all the dimensions, but if required it is also possible to use along each dimension a different sampling interval):
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 and width 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 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 and along both of the axes, where 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.
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.
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 . 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.
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].
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?
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 and its spectrum by [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 and below by , where is the sampling frequency [see Fig. 9(b); the constant factor 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 :
Therefore, in the signal domain of Fig. 9(c), the convolution of the sampled signal with yields, indeed, a perfect reconstruction of our original signal :
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 , whose width equals the distance between two consecutive samples (see Fig. 10). [This is, of course, a theoretic idealization, since usually 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)]:4). Indeed, in the signal domain of Fig. 10(c), the convolution of the sampled signal with the “pixel” does not yield a precise copy of our original signal but rather a pixelized or jagged version thereof:
Similarly, in the 2-D case (like in computer displays or in digital printing devices) each impulse of the sampled signal to be displayed is convolved with a single pixel shape (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 , 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 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.
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.
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.
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.
This tutorial is an extended version of material that appeared recently in Sec. 8.5 of the book, Ref. 19 published by Springer.
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).