|
Welcome to the downloadable DFT demonstration kit which accompanies the book Mastering the Discrete Fourier Transform in One, Two or Several Dimensions: Pitfalls and Artifacts by I. Amidror, published by Springer.
The reason for this site is that Fourier transform pairs are always best appreciated when they are plotted graphically. Clearly, tables full of Fourier transform equations cannot give the same insights as graphic presentations do. Although the mathematical formulas remain, of course, indispensable, it is always helpful for didactic reasons to illustrate them graphically, too; the impact of a visual presentation cannot be overestimated.
Pictorial illustrations of some frequently encountered CFT pairs can be found in the literature (see, for example, [Bracewell00 pp. 573-591]). However, users who try to plot such CFT pairs using their favorite DFT software package are often surprised to get quite different results. This mismatch may originate from several reasons: First of all, the DFT software in question may be using a DFT definition that is based on different conventions than your given CFT pairs (for example, different scaling factors, different signs in the exponents, etc.); this is explained in detail in Chapter 2 of the DFT book. Another possible source of error is due to an incorrect reorganization of the input or output data when using the DFT; this is explained in Chapter 3 of the DFT book. But even when the reorganization is done correctly and the DFT and CFT definitions being used are based on the same conventions, like in the present DFT demonstration kit, discrepancies still may exist between the CFT and DFT results, due to some inherent DFT artifacts such as aliasing, leakage, etc. One of the main aims of the present DFT demonstration kit is to point out these artifacts, whenever they occur, and to show how to correctly interpret the discrepancies they may cause.
Nowadays one can find on the internet various online interactive DFT applets or calculators, some of which can also plot the DFT results graphically (see examples in the links page). Such interactive tools may be quite attractive, but they cannot give the same insights as worked-out examples that are carefully designed for didactic purposes. The main advantage of interactive applets is that they may easily lend themselves to manual DFT experimentations, but on the other hand they do not offer similar capabilities for the CFT. (Note that analytic or symbolic computations of the CFT are much more complex than numeric DFT calculations; altough such CFT computations may be available in some advanced mathematical packages, they are still quite limited in their capabilities.) Therefore, general DFT applets do not offer a comparison with the corresponding CFT, and they cannot explain the discrepancies between the two.
In the present demonstration kit we provide a gallery of DFT pairs, each being accompanied by the corresponding CFT pair. The CFT and DFT definitions being used are the same as in the DFT book (see pp. 17 and 19 therein, respectively). Whenever possible the discrete and continuous results are shown superposed within the same plot, to better illustrate the relationships and the discrepancies between them. (Note, however, that in 2D cases such superpositions are no longer possible, and therefore only the discrete results are shown graphically.) Each of the examples in this kit is also accompanied by a short explanation, along with references to the relevant sections in the DFT book or to other useful remarks in the literature. Special attention is given to DFT artifacts such as aliasing and leakage, their graphical presentation, and their correct identification and interpretation.
Note that in order to be able to plot the DFT and the CFT together, using the same axes and the same units, we first have to normalize the DFT results: We must reorganize them, and then rescale them to compensate for the different scaling factors that appear in the CFT and DFT definitions being used. These issues are fully explained and illustrated in Chapters 3 and 4 of the DFT book, respectively. These normalizations are automatically performed in all our figures, as indicated in the figure legends (whenever possible) by an adequate label such as "DFT after input and output reorganization and vertical scaling." This normalization of the DFT results is necessary for several reasons: First, it allows us to correctly approximate and plot an unknown CFT by means of the much easier to compute DFT; and second, it allows us, whenever the CFT is known, to plot the CFT and the DFT to scale within the same graph, and hence to clearly show the possible discrepancies between them (for example due to aliasing, leakage, etc.)
In cases having an impulsive spectrum (such as periodic functions) or an impulsive signal domain, a further amplitude scaling is needed in order for the DFT results to match the underlying CFT. This is explained in detail in Appendix A and in Sec. D.9 of the DFT book. This additional correction should not be performed, however, if the DFT is being used for computing the Fourier series coefficients of a given periodic function, rather than for computing its CFT (see Remark D.3 and Example D.1 in the DFT book). It is therefore up to the user to decide whether or not to apply this further scaling correction, depending on his needs. In the present DFT demonstration kit we do apply this scaling - unless otherwise mentioned - in order to obtain a correct match between the DFT spectrum and the underlying CFT, and to be able to clearly illustrate the discrepancies between them whenever they occur.
Each item in this DFT demonstration kit is provided in two different file formats: as a PostScript file, and as a PDF file. The PostScript or PDF files provided here may be downloaded and printed on any standard printer of at least 600 dpi. Both formats should give the same printed results. Click on the highlighted "PS" or "PDF" indicator next to each of the items below to download the corresponding PostScript or PDF file. You can also prepare your own DFT demonstration kit by printing these PostScript or PDF files. Further information on printing PostScript files is given here; further information on printing PDF files is given here.
This DFT demonstration kit accompanies the book Mastering the Discrete Fourier Transform in One, Two or Several Dimensions: Pitfalls and Artifacts by I. Amidror, published by Springer. All the references are made to this book, unless otherwise mentioned. The other references being used are:
g(x) = sinc(x) ---> G(u) = rect(u)
(see, for example, [Bracewell00 p. 578]).
Fig. sinc shows a 32-point DFT of the function sinc(x) within the range -4...4, while Fig. sinca shows a 32-point DFT of sinc(x) within the range -8...8.
Similarly, Fig. sinc2 shows a 32-point DFT of sinc(2x) within the range -4...4, while Fig. sinc2a shows a 32-point DFT of sinc(2x) within the range -2...2.
Note that the discrete sequence of numbers that is provided as input to the DFT is identical
in Figs. sinc and sinc2a, and in Figs. sinca and sinc2 (compare the input values at the points
k = 0 ... k = 31 using the discrete axis at the top of the figures). How can it
be that for identical input sequences the DFT gives in each case a different output sequence?
The answer is given in Chapter 4 of the DFT book: In order to obtain a correct match
between the DFT values and the underlying CFT, some scalings must be applied to the DFT results, to
compensate for the different constant factors that appear in the DFT and CFT definitions being used.
By applying the required corrections, as explained in Chapter 4 of the book, the
DFT results are adapted to the scaling factors of the CFT so that they can be plotted together
in the same graph. Without applying these corrections, the DFT output sequences we obtain
for identical input sequences are, of course, identical, but then they do not necessarily
match the corresponding CFTs.
For more details on this subject see Example 4.1 and Example 4.2 in the DFT book (pp. 79-81).
DFT artifacts:
Because the sinc function is not finite-length (it extends over the entire x axis)
it is clear that the DFT spectrum in this case is flawed by leakage. This is, indeed, the origin of
the ripple artifact in the DFT spectrum (as compared to the clear-cut rect function in the
CFT spectrum). This is explained in detail in Example 6.2 and Fig. 6.5 in the DFT book.
The effect of aliasing on such cases is shown in Example 5.1 and Fig. 5.6 of the DFT book.
The effect of signal-domain aliasing on such cases is explained in Sec. 5.7 and
Fig. 5.19 of the DFT book.
g(x) = rect(x) ---> G(u) = sinc(u)
This case is simply the inverse of the case shown above in Fig. sinc. Note that the function rect(x) is nonzero within the range -0.5...0.5.
Fig. rect shows a 32-point DFT of the function rect(x) within the range -4...4 (see also Fig. 3.5 in the DFT book). Fig. rectd shows a 32-point DFT of the function rect(0.5x) within the same range -4...4, illustrating the effect of the dilation theorem. And Fig. rectsh shows a 32-point DFT of the function rect(x - 1) within the same range -4...4, illustrating the effect of the shift theorem.
Note that the value the sampled rect function takes at the two discontinuity points of rect(x) is neither 0 nor 1, but rather the midvalue 0.5; this is explained in Sec. 8.2 of the DFT book.
DFT artifacts:
Because the rect function is not band limited (its CFT extends over the entire u axis)
it is clear that the DFT spectrum in this case is flawed by aliasing. This explains, indeed, the
slight discrepancy we observe between the plots of the DFT and the CFT in this figure. Note that
without having plotted both the normalized DFT and the underlying CFT together, this error in the DFT
results would not be easy to detect visually.
g(x) = sinc(x) + 0.5sinc(0.5x) ---> G(u) = rect(u) + rect(2u)
(see a similar case in [Bracewell00 p. 589]).
In Fig. sincdiff the given function g(x) and its CFT G(u) are:
g(x) = 2sinc(x) - 0.5sinc(0.5x) ---> G(u) = 2rect(u) - rect(2u)
In Fig. sincdiffa the given function g(x) and its CFT G(u) are:
g(x) = 2sinc(x) - sinc(0.5x) ---> G(u) = 2rect(u) - 2rect(2u)
Another similar case appears in Fig. 5.5(b) of the DFT book.
DFT artifacts:
Because the functions g(x) are not finite-length (they extend over the
entire x axis) it is clear that the DFT spectrum in these cases is flawed by leakage.
This is, indeed, the origin of the ripple artifact in the DFT spectrum (as compared to the
clear-cut functions in the CFT spectrum).
g(x) = sinc2(x) ---> G(u) = tri(u)
(see, for example, [Bracewell00 p. 578]).
Fig. sincp2 shows a 32-point DFT of sinc2(x) within the range -4...4.
DFT artifacts:
Because the sinc2 function is not finite-length (it extends over the
entire x axis) it is clear that the DFT spectrum in this case is flawed by leakage.
However, since the input sequence taken by the DFT in the present case is much less
truncated than in the case of the sinc function, the resulting leakage artifact in the DFT spectrum
is much less significant, too.
The effect of aliasing on such cases is shown in Example 5.2 and Fig. 5.7 of the DFT book.
g(x) = tri(x) ---> G(u) = sinc2(u)
This case is simply the inverse of the case shown above in Fig. sincp2. Note that the function tri(x) is nonzero within the range -1...1, while the function rect(x) is nonzero within the range -0.5...0.5.
Fig. tri shows a 32-point DFT of the function tri(x) within the range -4...4. See also Figs. D.8 and D.9 in the DFT book (pp. 328-329).
DFT artifacts:
Because the tri function is not band limited (its CFT extends over the entire u axis)
it is clear that the DFT spectrum in this case is flawed by aliasing. This explains, indeed, the
slight discrepancy we observe between the plots of the DFT and the CFT in this figure. Note that
without having plotted both the normalized DFT and the underlying CFT together, this small error
in the DFT results would not be easy to detect visually.
g(x) = e-xstep(x) ---> G(u) = 1/[1+(2πu)2] - 2πui/[1+(2πu)2]
(see, for example, the DFT book p. 104 or [Bracewell00 p. 581]).
Fig. exp shows a 32-point DFT of g(x) within the range 0...8, while Fig. exp1 shows a 32-point DFT of g(x) within the symmetric range -4...4. See also Figs. 3.1 and 3.3, respectively, in the DFT book.
It is clear that the CFT in both exp and exp1 is indeed identical (note that the continuous function
g(x) is the same in both cases, and that the CFT is always calculated over the entire domain of
the function). But what about the DFT? Is it possible that the DFT, too, is identical in both cases,
in spite of the 16-point shift difference between the input sequences of Figs. exp and exp1?
The answer is, of course, that a shift in the input sequence does modify the resulting output
of the DFT, as predicted by the DFT shift theorem (see point 6 in Sec. 2.4.4 of the DFT book or
[Brigham88 pp. 107, 114]). But this shift is compensated by the input reorganization that must be
performed in exp1 due to its symmetric sampling around the origin, as explained in the DFT book in Sec. 3.3.
For further details, see Example 3.1 in the DFT book (pp. 54-55).
DFT artifacts:
Because the function g(x) is neither finite-length nor band-limited, its DFT suffers
from both leakage and aliasing. Note, however, that in the case of exp1 the input sequence taken by the
DFT is truncated at its
positive end earlier than in the case of exp. This gives in exp1 a slightly higher discrepancy
between the DFT results and the CFT, due to leakage. This discrepancy, which can be hardly noticed in the
present figures, is explained in the DFT book in Sec. 6.4 and clearly illustrated there in Fig. 6.7.
The effect of aliasing on such cases is shown in Example 5.3 and Fig. 5.8 of the DFT book.
g(x) = 0.5e-|x| ---> G(u) = 1/[1+(2πu)2]
(see, for example, [Bracewell00 p. 581]).
Fig. dexp shows a 32-point DFT of g(x) within the symmetric range -4...4. See also Fig. 3.4 in the DFT book.
DFT artifacts:
Because the function g(x) is neither finite-length nor band-limited, its DFT suffers
from both leakage and aliasing. Note, however, that in the present case both artifacts are
marginal and they can be hardly noticed.
g(x) = cos(2πfx) ---> G(u) = 0.5[δ(u + f) + δ(u - f)]
(see, for example, [Bracewell00 pp. 108-110]).
Remark: Note that varying f in the function g(x) = cos(2πfx) does not affect the impulse heights in the spectrum G(u), but only their locations. This seems to violate the dilation theorem (point 2 in Sec. 2.4.1 of the DFT book), but in fact this unusual behaviour is caused by the particular scaling property of the impulse (see [Bracewell00 p. 80]), which cancels here the scaling effect of the dilation theorem. This happens in all cases having impulsive spectra, including all periodic functions.
Fig. cos shows a 32-point DFT of the function cos(2πfx) with f = 0.5 within the range -4...4; Fig. cos2 shows a 32-point DFT of the function cos(2πfx) with f = 1 within the range -2...2; and Fig. cosleak shows a 32-point DFT of the function cos(2πfx) with f = 18/32 within the range -4...4. Fig. cosleak1 is identical to Fig. cosleak, except that the cosine frequency here is f = 17/32. Finally, Figs. cosfreq1 and cosfreq2 show a series of functions cos(2πfx) within the range -4...4 having gradually varying frequencies f, and their respective 64-point DFTs: (a) f = 0.25; (b) f = 0.5; (c) f = 2; (d) f = 3; (e) f = 3.5; (f) f = 3.75; (g) f = 4, namely, half of the sampling frequency; (h) f = 4.25; (i) f = 7.5; and (j) f = 7.75.
Note that the vertical scaling applied to the DFT output includes here the correction explained in Appendix A of the DFT book, in order to obtain the best match between the DFT spectrum and the underlying CFT.
Note also that the discrete sequence of numbers that is provided as input to the DFT is identical
in Figs. cos and cos2 (compare the input values at the points k = 0 ... k = 31 using
the discrete axis at the top of the figures). How can it be that for identical input sequences the
DFT gives in each case a different output sequence?
The answer is given in Chapter 4 of the DFT book: In order to obtain a correct match
between the DFT values and the underlying CFT, some scalings must be applied to the DFT results, to
compensate for the different constant factors that appear in the DFT and CFT definitions being used.
By applying the required corrections, as explained in Chapter 4 of the book, the
DFT results are adapted to the scaling factors of the CFT so that they can be plotted together
in the same graph. Without applying these corrections, the DFT output sequences we obtain
for identical input sequences are, of course, identical, but then they do not necessarily
match the corresponding CFTs.
For more details on this subject see Example 4.3 and Figs. 4.2 and 4.6 in the DFT book.
DFT artifacts:
In Figs. cosleak and cosleak1, unlike in Figs. cos or cos2,
the cosine frequency f is not an integer multiple of the frequency step of the DFT spectrum,
so that the two impulses of the underlying CFT fall between output array elements of the DFT.
As explained in Sec. 6.5 of the DFT book, this causes in the DFT spectrum a leakage artifact, where
each of the original sharp impulses leaks into the neighbouring output array elements of the DFT,
giving a visual effect of smearing accompanied by gradually decaying oscillations
(ripple) to both sides. For more details on this leakage effect see Example 6.1 and Fig. 6.3 in the
DFT book. As explained there, the leaked spectrum corresponds, in fact, to the CFT of the truncated
(windowed) version of the function g(x), g(x)w(x), i.e.
to the convolution of the original impulse pair G(u) with a certain narrow sinc function.
The effect of aliasing in the case of the cosine function is explained in detail in Example 5.4
and Fig. 5.10 of the DFT book. We illustrate it here with Figures cosfreq1 and cosfreq2. These figures
show a series of continuous-world cosine functions g(x) = cos(2πfx) having
gradually varying frequencies f, as well as their respective spectra (CFTs),
G(u) = 0.5[δ(u + f) + δ(u - f)]. On each of these Fourier
pairs we also overprinted its corresponding discrete counterpart as obtained by 64-point sampling of
g(x) within the range -4...4 and by DFT. For the sake of clarity (see
Sec. 1.5.1 and Fig. 1.1 in the DFT book),
we have connected consecutive dots of the sampled cosine signal by straight line segments; the original,
continuous-world cosines are drawn by thinner curves (that are only visible when the discrete signal does
not exactly override its continuous counterpart). Note that the sampling frequency is always the same
(fs = 8), and only the cosine frequency f is being varied
in the different rows. In row (g) the cosine frequency f equals half of the sampling frequency
fs, meaning that in this case f is the maximum frequency
that can be represented in the DFT spectrum (see p. 73 in the DFT book). Note that in the DFT spectrum
of row (g) the positive frequency impulse at
f = 4 is already aliased, and falls on top of the negative frequency impulse at f = -4.
This happens because when the number of sampling points N is even (here: N = 64) the
DFT spectrum contains in its positive end one element less than in the negative end, so that the minimum
frequency -0.5fs is indeed included in the DFT spectrum, but
the maximum frequency 0.5fs is already folded over (for more details on this point see Fig. 5.10(d) in the DFT book). In rows
(h)-(j) the cosine frequency f exceeds 0.5fs, meaning
that aliasing indeed occurs (note that in the spectral domain the corresponding impulses exceed beyond
the boundaries of the DFT spectrum
and re-enter from the opposite end). In particular, when the folded-over impulses are sufficiently close
to the spectrum origin (see rows (i) and (j)) a strong low-frequency sampling moiré becomes more
prominent and visible than the original cosine function itself. Note, however, that the low-frequency
beating effects which appear in rows (e),(f),(h) are not true sampling moirés but rather
pseudo-moiré effects: As we can see, there are no corresponding low-frequency impulses in the
respective spectra, and even in the signal domain, the beating effect does not really represent a low
frequency signal (as in rows (i) and (j)) but rather a highly oscillating signal that is
only modulated by a low-frequency cosinusoidal envelope
env(x) = ±cos(2πεx) with
ε = 0.5fs - f.
This artifact, which is sometimes called a sub-Nyquist artifact, is explained in Sec. 8.6 of the
DFT book and in the figures therein.
g(x) = sin(2πfx) ---> G(u) = 0.5i[δ(u + f) - δ(u - f)]
(see, for example, [Bracewell00 p. 576]).
Fig. sin shows a 32-point DFT of the function sin(2πfx) with f = 0.5 within the range -4...4; Fig. sin2 shows a 32-point DFT of the function sin(2πfx) with f = 1 within the range -2...2; and Fig. sinleak shows a 32-point DFT of the function sin(2πfx) with f = 18/32 within the range -4...4. Fig. sinleaka is identical to Fig. sinleak, except that its first element has been zeroed (see the remark below).
Note that the vertical scaling applied to the DFT output includes here the correction explained in Appendix A of the DFT book, in order to obtain the best match between the DFT spectrum and the underlying CFT.
Note, again, just as in the case of the cosine, that the discrete sequence of numbers that is provided as input to the DFT is identical in Figs. sin and sin2 (compare the input values at the points k = 0 ... k = 31 using the discrete axis at the top of the figures); and yet, the DFT results we obtain in these two figures are different. The reason is, again, the same: In order to obtain a correct match between the DFT values and the underlying CFT, some scalings must be applied to the DFT results, to compensate for the different constant factors that appear in the DFT and CFT definitions being used. By applying the required corrections, as explained in Chapter 4 of the book, the DFT results are adapted to the scaling factors of the CFT so that they can be plotted together in the same graph. Without applying these corrections, the DFT output sequences we obtain for identical input sequences are, of course, identical, but then they do not necessarily match the corresponding CFTs.
DFT artifacts:
In Fig. sinleak, unlike in Figs. sin or sin2,
the sine frequency f is not an integer multiple of the frequency step of the DFT spectrum,
so that the two impulses of the underlying CFT fall between output array elements of the DFT.
Just as in the case of the cosine (see the previous example), this causes in the DFT spectrum a leakage
artifact, where each of the original sharp impulses leaks into the neighbouring output array elements
of the DFT, giving a visual effect of smearing accompanied by gradually decaying oscillations (ripple)
to both sides. This leaked spectrum corresponds, in fact, to the CFT of the truncated (windowed)
version of the function g(x), g(x)w(x), i.e.
to the convolution of the original impulse pair G(u) with a certain narrow sinc function.
The effect of aliasing in the case of the sine function is similar to that shown for the cosine
function in Example 5.4 and Fig. 5.10 of the DFT book.
Remark: Note that in Fig. sinleak the first element of the sampled function breaks the perfect anti-symmetry of the discrete input signal, and hence the resulting DFT output is no longer purely imaginary-valued (although the underlying continuous sine signal remains perfectly symmetric, and its CFT is purely imaginary-valued). As shown in Fig. sinleaka, this DFT artifact can be eliminated by zeroing the value of the first sampled element. This unusual DFT artifact has no equivalent in the case of the cosine function (see above); it is due to symmetry particularities of the DFT, as explained (for the 2D case) in Sec. 8.4 of the DFT book.
g(x) = (1/T)III(x/T) * rect(x) ---> G(u) = III(Tu) sinc(u)
where "*" indicates convolution, or in other words:
g(x) = Σmrect(x - mT) ---> G(u) = (1/T)sinc(u) Σmδ(u - m/T)
where the summations run over all integer values m (see, for example, Sec. 2.5 in [Amidror09 pp. 21-23]). Note that the impulse train (1/T)III(x/T) has impulse intervals of T and impulse heights of 1, while the impulse train III(Tu) has impulse intervals of 1/T and impulse heights of 1/T (see, for example, Footnote 2 on p. 92 of the DFT book, or [Bracewell00 pp. 83, 577]).
Fig. rectwave shows a 64-point DFT of the rectangular wave obtained by repeating rect(x) with period T = 2, within the range -4...4. Fig. rectwave1 shows a 64-point DFT of the rectangular wave obtained by repeating rect(2x) with period T = 1, within the same range -4...4. Figs. rectwave1.5, rectwave2 and rectwave3 are similar to Fig. rectwave1, but with a period T of 1.5, 2 and 3, respectively. Finally, Figs. rectwave2sh, rectwave2sha and rectwave2shb show three shifted versions of Fig. rectwave2, with shifts of 0.25, 0.5 and 1, respectively, illustrating the effect of the shift theorem. Since Fig. rectwave2shb is again symmetric, the impulses in the imaginary-valued part of its spectrum have zero heights (they fall exactly on zero-crossing points of the dashed envelope in the figure).
Note that the vertical scaling applied to the DFT output includes here the correction explained in Appendix A of the DFT book, in order to obtain the best match between the DFT spectrum and the underlying CFT. This correction should not be applied, however, if one only wishes to find the Fourier series coefficients of the periodic function g(x) (see Remark D.3 and Example D.1 in the DFT book).
Remark: The relationship between the DFT of the periodic rectangular wave and the DFT of the rect function (see above) is explained in Sec. D.9.1 and Figs. D.7-D.11 in the DFT book (although the illustrations provided there concern the triangular case). The effect of the number of periods we include in the input signal on the resulting DFT is explained in Remark 7.1 and Fig. 7.1 of the DFT book.
DFT artifacts:
In the case of Fig. rectwave the wave frequency f = 1/T = 0.5 is an integer
multiple of the frequency step of the DFT spectrum. A similar situation occurs in Figs. rectwave1 and
rectwave2, too. But when this is not the case, like in Figs. rectwave1.5 and rectwave3, the
impulses of the underlying CFT fall between output array elements of the DFT. Just as in the
case of the cosine (see Fig. cosleak above), this causes in the DFT spectrum
a leakage artifact, where each of the original sharp impulses leaks into the neighbouring output
array elements of the DFT, giving a visual effect of smearing accompanied by decaying oscillations
(ripple) to both sides.
For more details on this leakage effect see Example 6.1 and Fig. 6.3 in the DFT book (which illustrate
the case of the cosine function). This leaked spectrum corresponds, in fact, to the CFT of the truncated
(windowed) version of the function g(x), g(x)w(x), i.e.
to the convolution of the original impulse train G(u) with a certain narrow sinc function.
Note that the height of the narrow, modulated sincs that correspond to the leaked impulses may be
slightly higher or lower than that of the modulating envelope, (1/2T)sinc(u/2);
see also Fig. D.5 in the DFT book.
The effect of aliasing in the case of the rectangular wave is similar to that shown for the
triangular wave in Example 5.5 and Fig. 5.11 of the DFT book. Note that the effect of aliasing is
particularly strong in the case of Fig. rectwave1, where significant parts of the original CFT
fall beyond the boundaries of the DFT and hence undergo foldover.
g(x) = (1/T)III(x/T) * tri(2x) ---> G(u) = III(Tu) 0.5sinc2(0.5u)
where "*" indicates convolution, or in other words:
g(x) = Σmtri(2(x - mT)) ---> G(u) = (0.5/T)sinc2(0.5u) Σmδ(u - m/T)
where the summations run over all integer values m (see, for example, [Bracewell00 p. 244]; for cases with period T other than 1, see Fig. D.7 in the DFT book). Note that the impulse train (1/T)III(x/T) has impulse intervals of T and impulse heights of 1, while the impulse train III(Tu) has impulse intervals of 1/T and impulse heights of 1/T (see, for example, Footnote 2 on p. 92 of the DFT book, or [Bracewell00 pp. 83, 577]).
Fig. triwave shows a 64-point DFT of the triangular wave obtained by repeating tri(2x) with period T = 2, within the range -4...4 (see also Figs. D.10 and D.11 in the DFT book).
Note that the vertical scaling applied to the DFT output includes here the correction explained in Appendix A of the DFT book, in order to obtain the best match between the DFT spectrum and the underlying CFT. This correction should not be applied, however, if one only wishes to find the Fourier series coefficients of the periodic function g(x) (see Remark D.3, Example D.1 and Sec. D.9.1 in the DFT book).
Remark: The relationship between the DFT of the periodic triangular wave and the DFT of the tri function (see above) is explained in Sec. D.9.1 and Figs. D.7-D.11 in the DFT book. The effect of the number of periods we include in the input signal on the resulting DFT is explained in Remark 7.1 and Fig. 7.1 of the DFT book.
DFT artifacts:
In the case of Fig. triwave the wave frequency f = 1/T = 0.5 is an integer
multiple of the frequency step of the DFT spectrum. But when this is not the case, the impulses of
the underlying CFT fall
between output array elements of the DFT. Just as in the case of the cosine (see Fig.
cosleak above), this causes in the DFT spectrum a leakage artifact, where each of the original
sharp impulses leaks into the neighbouring output array elements of the DFT, giving a visual effect
of smearing accompanied by decaying oscillations (ripple) to both sides. This leaked spectrum
corresponds, in fact, to the CFT of the truncated
(windowed) version of the function g(x), g(x)w(x), i.e.
to the convolution of the original impulse pair G(u) with a certain narrow sinc function.
The effect of aliasing in the case of the triangular wave is explained in Example 5.5 and Fig.
5.11 of the DFT book.
See also Problem 4-10 on p. 88 of the DFT book.
g(x,y) = sinc(x) sinc(y) ---> G(u,v) = rect(u) rect(v)
(see, for example, [Bracewell00 p. 334]).
Fig. sinc2D shows a 32x32-point DFT of the function sinc(x) sinc(y) within the range -4...4
to both directions, while Fig. sinc22Da shows a 32x32-point DFT of sinc(2x) sinc(2y) within
the range -2...2 to both directions.
Note that Fig. sinc2D is the 2D extension of Fig. sinc, and Fig sinc22Da is the 2D extension
of Fig. sinc2a.
DFT artifacts:
Because the 2D sinc function is not finite-length (it extends throughout the entire x,y
plane) it is clear that the DFT spectrum in this case is flawed by leakage. This is, indeed, the origin of
the ripple artifact (the gray-level fluctuations) in the DFT spectrum, as compared to the clear-cut 2D
rect function in the CFT spectrum. This is the 2D counterpart of the leakage artifact in the case of the
1D sinc function. See also Remark 6.7 on p. 173 of the DFT book.
The effect of aliasing on such cases can be seen as a 2D extension of Example 5.1 and Fig. 5.6 in
the DFT book.
g(x,y) = rect(x) rect(y) ---> G(u,v) = sinc(u) sinc(v)
(see, for example, [Bracewell95 p. 150]). This is simply the inverse of the case shown above (2D sinc).
Fig. rect2D shows a 32x32-point DFT of the function rect(x) rect(y) within the range -4...4
to both directions, while Fig. rect22Da shows a 32x32-point DFT of rect(2x) rect(2y)
within the range -2...2 to both directions. Note that Fig. rect2D is the 2D extension of Fig. rect.
See also Example 3.2 and Fig. 3.6 as well as Example 4.4 and Fig. 4.7 in the DFT book.
Note that the value the sampled 2D rect function takes at the discontinuity points along the rectangle's edges is neither 0 nor 1, but rather the midvalue 0.5, except for the 4 corners where the value is 0.25; this is explained in Sec. 8.2 of the DFT book. Nevertheless, when using higher resolution DFTs, such as the 128x128-point DFT used in the examples which follow, the penalty incurred when ignoring this midvalue rule is rather marginal, and we will no longer bother about this subtlety when preparing the input data for the DFT.
Remark: The location of the axes with respect to the discrete pixels in each of the 2D figures is explained in Problem 3-8 of the DFT book (p. 68). For the sake of simplicity the axes will be omitted in the following 2D figures, which are provided at a higher resolution (128x128 points). Note, however, that this remark remains valid in all cases.
DFT artifacts:
Because the 2D rect function is not band limited (its CFT extends throughout the entire
u,v plane) it is clear that the DFT spectrum in this case is flawed by aliasing.
But just as in the 1D case (see Fig. rect above), since G(u,v) is rather smooth
and non-impulsive, the foldover due to aliasing only slightly modifies the shape of the DFT spectrum,
and it may be quite difficult to detect visually in the DFT spectrum. Aliasing is easier to detect in
a slightly rotated version of the 2D rect function, as shown in the following example.
g(x,y) = rect(xcosθ - ysinθ) rect(xsinθ + ycosθ) --->
G(u,v) = sinc(ucosθ - vsinθ) sinc(usinθ + vcosθ)
Fig. rotrect2D shows, for 3 different angles θ, the 128x128-point DFT of the rotated 2D rect function within the range -8...8 to both directions: (a) θ = 0o; (b) θ = 14o; (c) θ = 45o.
DFT artifacts:
Because the rotated 2D rect function is not band limited (its CFT extends throughout the entire
u,v plane) it is clear that the DFT spectrum in this case is flawed by aliasing.
And yet, the existence of aliasing is not always easy to detect here: Indeed, aliasing is easier
to detect in case (b), where
the 2D rect function is slightly rotated, than in cases (a) or (c). To see this, note that without
aliasing the rotated sinc function in the DFT spectrum of (b) would have been perfectly symmetric
with respect to its rotated axes. In cases (a) and (c), however, this cue no longer helps,
since in these cases the DFT spectra remain symmetric even under the effect of aliasing. Nevertheless,
in case (c) the existence of aliasing can be identified in the 4 corners of the DFT spectrum, each of
which is darker (i.e. more negative) than the preceding negative lobe along the diagonal. In a true
sinc function the undulations decay as they go farther away from the center, so that each lobe has a
weaker amplitude (positive or negative) than the preceding ones.
See also Example 5.9 and Fig. 5.16 in the DFT book.
Remark: Note that the rotation theorem is only valid in the continuous world, but as clearly illustrated here it no longer holds in the discrete world.
g(x,y) = rect(x) ---> G(u,v) = sinc(u) δ(v)
Note that this infinite straight bar is, in fact, a 2D extension along the vertical direction of the 1D rect function (see above).
Fig. bar shows a 128x128-point DFT of the straight bar rect(ax) within the range -8...8 to both directions: Rows (a), (b) and (c) show what happens when the bar width is gradually increased (illustrating the dilation theorem), and row (d) shows what happens when the straight bar (c) is shifted to the right by 1/8, i.e. by one discrere-world pixel (illustrating the shift theorem).
Comparing rows (c), (b) and (a) in Fig. bar we see that as the bar width in the signal domain decreases,
the modulating sinc in the
spectral domain becomes wider (as predicted by the dilation theorem). Note that in row (a) the bar
width is one discrete-world pixel, i.e. the smallest possible non-zero width in the discrete world.
This one-pixel wide bar is, in fact, the discrete counterpart of the continuous-world line impulse
along the y axis, g(x,y) = δ(x), whose CFT is the line impulse
G(u,v) = δ(v) along the u axis of the spectrum (see [Bracewell00
p. 335]). In the continuous world, if the bar width in the signal domain becomes infinitely small (so that
the bar actually becomes a line impulse with a constant height of 1), then the modulating sinc function
in the spectrum becomes infinitely wide, and hence the spectrum, too, becomes a line impulse with a constant
height of 1, but in the perpendicular direction. As shown in row (a), the discrete-world counterpart of
a line impulse having an infinitely-small width is a one-pixel wide line.
On the relationship between the continuous-world impulse and its discrete counterpart (in the 1D case)
see Appendix A of the DFT book.
DFT artifacts:
Because the straight bar is not band limited (its CFT consists of a line impulse extending along
the entire u axis to both sides of the origin), it is clear that the DFT spectrum in
this case is flawed by aliasing, just like in the 1D rect function (see above). Aliasing is easier to detect
in a slightly rotated version of the straight bar, as shown in the following example.
g(x,y) = rect(xcosθ - ysinθ) ---> G(u,v) = sinc(ucosθ - vsinθ) δ(usinθ + vcosθ)
Thus, the CFT of the rotated infinite straight bar consists of a rotated version of the infinite line impulse of the previous example. Note that the rotated line impulse always passes through the origin of the spectrum, and remains perpendicular to the rotated bar in the signal domain.
Fig. rotbar shows, for different angles θ, the 128x128-point DFT of the rotated 2D bar g(x,y) within the range -8...8 to both directions: (a) θ = 14o; (b) θ = 10o; (c) θ = 45o; (d) same angle as in case (a), but with a wider bar. Fig. rotbara is identical to Fig. rotbar, except that its leftmost column and most bottom row have not been zeroed (see the first remark below).
DFT artifacts:
Because the rotated straight bar is not band limited (its CFT consists of a line impulse extending
ad infinitum to both sides of the origin), it is clear that the DFT spectrum in
this case is flawed by aliasing. And indeed, whenever this spectral line-impulse exceeds the boundaries
of the DFT spectrum, it folds over and re-enters from the opposite side. But because in the CFT the
line-impulse extends to both directions ad infinitum, it follows that in the discrete world the
folded-over line impulse exceeds the boundaries of the DFT spectrum over and over again, each time
re-entering from the opposite side. This is explained in more detail in Example 5.6 and
Fig. 5.13 of the DFT book; see also Problem 5-9 and Fig. 5.21 there. Note that the CFT of the rotated
straight bar consists of a single infinite line-impulse that passes through the spectrum origin.
All the other parallel line-impulses in the DFT spectrum are, therefore, easily recognized as aliasing
artifacts. However, when the original line impulse runs along a diagonal of the DFT spectrum, as in
case (c), its parts which exceed from one side of the DFT spectrum re-enter from the opposite side
and fall there exactly on top of the same line impulse, their amplitudes simply being summed up.
A similar effect occurs also when θ = 0o, as shown in the previous
example (bar). In these cases, where only one line-impulse appears in the DFT spectrum, the effect
of aliasing is less obvious to the eye (it only consists of some amplitude deviations with respect to
the underlying true CFT).
Because the rotated straight bar is not finite-length, either (it extends to both directions
ad infinitum), its DFT suffers also from leakage. This explains, indeed, the small oscillations
around the center of the DFT spectrum. See also Sec. 6.6 and Remark 6.7 in the DFT book.
Remark: Note that in Fig. rotbar we have zeroed the leftmost column and the most bottom row in the signal domain. This is done here in order to avoid a quite unusual DFT artifact, which is explained in detail in Sec. 8.4 and Fig. 8.4 of the DFT book. As shown in Fig. rotbara, without this correction the discrete input signal is no longer centrosymmetric, and hence the resulting DFT output has a non-zero imaginary-valued part, in flagrant contradiction with the original continuous-world case. (Note that in Fig. rotbara the amplitude of the imaginary-valued part of the DFT spectrum has been somewhat exaggerated in order to make it clearly visible in the gray-level plot.)
Remark: The relationship between aliasing and the jaggies which appear in the signal domain along the edges of the rotated bar is explained in detail in Sec. 8.5 of the DFT book.
Remark: Note that the rotation theorem is only valid in the continuous world, but as clearly illustrated here it no longer holds in the discrete world.
g(x,y) = cos(2πfx) ---> G(u,v) = 0.5[δ(u+f, v) + δ(u-f, v)]
(see, for example, [Bracewell00 p. 334]), where δ(u,v) = δ(u) δ(v) denotes the 2D unit impulse [Bracewell00 pp. 89-90].
Note that the cosinusoidal line grating g(x,y) is, in fact, a 2D extension along the y axis of the cosine function in the 1D case (see above).
Fig. cosgrat shows the 128x128-point DFT of the cosinusoidal line grating g(x,y) within the range -8...8 to both directions, for 4 different frequencies f: (a) f = 1; (b) f = 2; (c) f = 4; (d) f = 6. Fig. cosgratleak is identical to Fig. cosgrat except that the frequencies f in this case are slightly modified: (a) f = 1 - ε; (b) f = 2 - ε; (c) f = 4 - ε; (d) f = 6 - ε; where ε = 0.5(8/128) = 1/32 (i.e. the frequency difference corresponding to half a pixel in our DFT spectrum). Finally, rows (a) and (b) of Fig. subnyq2D show the 128x128-point 2D counterparts of rows (a) and (f) of Figs. cosfreq1 and cosfreq2, respectively.
Remark: Note that varying f in the function g(x,y) = cos(2πfx) does not affect the impulse heights in the spectrum G(u,v), but only their locations. This seems to violate the dilation theorem (point 2 in Sec. 2.4.2 of the DFT book), but in fact this unusual behaviour is caused by the particular scaling property of the impulse (see the 1D equivalent in [Bracewell00 p. 80]), which cancels here the scaling effect of the dilation theorem. This phenomenon occurs in all cases having impulsive spectra, including all periodic functions.
On the relationship between the continuous-world impulse and its discrete counterpart (in the 1D case) see Appendix A of the DFT book.
DFT artifacts:
As long as the cosinusoidal line grating has a frequency f that is lower than half of the
sampling frequency, its spectral impulses fall inside the range of the DFT spectrum, and no aliasing
occurs (see rows (a) and (b) in Fig. cosgrat). Row (c) in the figure shows the limit case where the
cosine frequency f exactly equals half of the sampling frequency (see the explanation for the
1D cosine in row (g) of Fig. cosfreq2 above). Row (d) of the figure shows what happens when the cosine
frequency f
is higher than half of the sampling frequency, and hence the spectral impulses exceed beyond the borders
of the DFT spectrum: As we can see, each of the impulses folds over and re-enters into the DFT spectrum
from the opposite side, giving a false, lower-frequency impulse (an alias). This aliasing artifact
corresponds to a false lower-frequency cosinusoidal grating, as we can see, indeed, in the signal domain.
Note that due to this aliasing artifact, row (d) in the discrete world becomes exactly identical to
row (b), although originally in the continuous world row (d) was obviously different from row (b),
having a much higher frequency. See also Example 5.4 and Fig. 5.10 of the DFT book for the explanation
of the 1D counterpart.
In the case of Fig. cosgratleak, unlike in Fig. cosgrat,
the cosine frequency f is not an integer multiple of the frequency step of the DFT spectrum,
so that the two impulses of the underlying CFT fall between output array elements of the DFT.
This causes in the DFT spectrum a horizontal leakage artifact, where each of the original sharp impulses
leaks leftwards and rightwards into the neighbouring output array elements of the DFT, giving a visual
effect of horizontal smearing accompanied
by gradually decaying oscillations (ripple) to both sides. More details on this leakage can be found
in Sec. 6.5 of the DFT book for the 1D case and in Sec. 6.6 for the 2D case. As explained there, the
leaked spectrum corresponds, in fact, to the CFT of the truncated (windowed) version of the function
g(x,y), g(x,y)w(x,y), i.e.
to the convolution of the original impulse pair G(u,v) with a certain narrow 2D
sinc function.
It is interesting to note that leakage affects also the folded-over impulses in the case of
aliasing (see row (d) in Fig. cosgratleak). Furthermore, the oscillating tails extending to both
sides of each leaked impulse may themselves exceed beyond the borders of the DFT spectrum; each such
exceeding tail will fold over and re-enter from the opposite side of the DFT spectrum, thus causing
an aliasing artifact - even if the original cosine-frequency f itself is still below half of the
sampling frequency, and does not cause aliasing.
Finally, the darkening effect to both sides of the signal domain in row (c) of Fig. cosgratleak
is due to the sub-Nyquist artifact. As we can see in the 1D counterpart in rows (f), (g) of Fig. cosfreq2,
when the cosine frequency f is just slightly below half of the sampling frequency, i.e. almost
at the border of the DFT spectrum, the sampled signal shows a low-frequency beating effect due to
modulation by a low-frequency cosinusoidal envelope. And indeed, in our case here the modulating
envelope has its zeroes along the left and right edges of the figure. Another example of 2D sub-Nyquist
artifact is shown in row (b) of Fig. subnyq2D; this is precisely the 2D counterpart of row (f) in
Fig. cosfreq2.
g(x,y) = cos[2πf(xcosθ - ysinθ)] --->
G(u,v) = 0.5δ[(ucosθ - vsinθ) + f, (usinθ + vcosθ)] +
0.5δ[(ucosθ - vsinθ) - f, (usinθ + vcosθ)]
Thus, the CFT of the rotated cosinusoidal line grating consists of a rotated version of the impulse pair of the previous example. Note that the rotated impulse pair always remains perpendicular to the rotated cosinusoidal grating in the signal domain.
Fig. rotcosgrat shows, for different angles θ, the 128x128-point DFT of the rotated line grating g(x,y) having period T = 1 within the range -8...8 to both directions: (a) θ = 14o; (b) θ = 10o; (c) θ = 8o; (d) θ = 3o. Fig. rotcosgrata is identical to Fig. rotgrat, except that its leftmost column and most bottom row have not been zeroed (see the first remark below). Fig. rotcosgrat1 shows, for different periods T, the 128x128-point DFT of the rotated cosinusoidal line grating g(x,y) with θ = 3o within the range -8...8 to both directions: (a) T = 1.05, so that f = 1/T = 0.95; (b) T = 1.05/2, so that f = 1.90; (c) T = 1.05/4, so that f = 3.81; (d) T = 1.05/8, so that f = 7.62. Finally, rows (c) and (d) of Fig. subnyq2D show two 128x128-point rotated cosines whose frequencies are just slightly below half of the sampling frequency (so that their impulses are located almost at the boundaries of the respective DFT spectra).
DFT artifacts:
As we see in Fig. rotcosgrat1, as long as the spectral impulses of the cosinusoidal line grating
fall inside the range of the DFT spectrum (rows (a), (b)), no aliasing occurs. But when the spectral
impulses exceed beyond the borders of the DFT spectrum (like in row (d)), each of them folds over and
re-enters into the DFT spectrum from the opposite side, giving a false, lower-frequency impulse (an alias).
This aliased impulse pair corresponds to a false lower-frequency cosinusoidal grating, as we can see,
indeed, in the signal domain of row (d).
Note that the orientation of this aliased lower-frequency cosinusoidal grating may be different from
the orientation of the original continuous-world cosinusoidal grating g(x,y):
The false aliased grating is perpendicular to the orientation of its impulse pair (i.e. the two
false aliased impulses) in the DFT spectrum, and it does not inherit the angle
θ = 3o of the original continuous-world grating g(x,y).
Note that if any of the folded-over impulses due to aliasing happens to fall close enough
to the spectrum origin, its new frequency there is so small that it may correspond back in the signal
domain to a new, visible low-frequency parasite structure (like in row (d) of Fig. rotcosgrat1). This
parasite structure does not exist in our original function (the continuous-world cosinusoidal line
grating), and it only
appears in its sampled version due to aliasing (i.e. due to the undersampling of the original grating).
Such low-frequency structures are known as sampling moirés; this subject is explained
in greater detail in [Amidror09, Sec. 2.13]. See also Example 5.8 and Fig. 5.15 in the DFT book
(showing a similar case with a raised cosinusoidal line grating).
The low-frequency structure that is visible in the signal domain in row (c) of Fig. rotcosgrat1 is
not a true sampling moiré effect (note that in row (c) there are no corresponding
low-frequency impulses in the DFT spectrum). This artifact is a pseudo-moiré effect that is
sometimes called a sub-Nyquist artifact (see Sec. 8.6 in the DFT book). Other examples of 2D
sub-Nyquist artifacts are shown in rows (c) and (d) of Fig. subnyq2D. Note that in all of these cases no
corresponding low-frequency impulses exist in the DFT spectrum, and even in the signal domain,
the beating effect in question does not really represent a low frequency
signal (as in row (a) of Fig. subnyq2D) but rather a highly oscillating signal that is
only modulated by a low-frequency 2D cosinusoidal envelope. Other examples of 2D sub-Nyquist
artifacts are given in Appendix C below.
The rotated cosinusoidal line grating may also suffer from leakage. Because the continuous-world
function g(x,y) is periodic, its DFT suffers from leakage whenever the impulses
of the CFT fall between pixels of the DFT spectrum, or equivalently, whenever the discrete input
of the DFT is not perfectly cyclical (seamlessly wraparound); see Remark 6.7 on p. 173 of the DFT book.
In such cases, each impulse in the DFT spectrum leaks into the neighbouring output array elements of
the DFT, giving a visual effect of smearing accompanied by gradually decaying oscillations (ripple) to
both directions, horizontally as well as vertically. The effect of leakage is clearly visible in the
spectral domain of Figs. rotcosgrat and rotcosgrat1, but in Fig. subnyq2D no leakage occurs (this figure
was intentionally designed to have all the impulse locations precisely on pixels of the DFT spectrum).
The leakage effect in the 2D case is discussed in
Sec. 6.6 of the DFT book. As explained there, the leaked spectrum corresponds, in fact, to the CFT of
the truncated (windowed) version of the function g(x,y),
g(x,y)w(x,y), i.e. to the convolution of the original
impulse comb G(u,v) with a certain narrow 2D sinc function.
Note that leakage affects also the folded-over impulses in the case of
aliasing (see row (d) in Fig. rotcosgrat1). Furthermore, the oscillating tails extending to both
sides of each leaked impulse may themselves exceed beyond the borders of the DFT spectrum; each such
exceeding tail will fold over and re-enter from the opposite side of the DFT spectrum, thus causing
an aliasing artifact - even if the original cosine-frequency f itself is still below half of the
sampling frequency, and does not cause aliasing.
Remark: Note that in Figs. rotcosgrat and rotcosgrat1 we have zeroed the leftmost column and the most bottom row in the signal domain. This is done here in order to avoid a quite unusual DFT artifact, which is explained in detail in Sec. 8.4 and Fig. 8.4 of the DFT book. As shown in Fig. rotcosgrata, without this correction the discrete input signal is no longer centrosymmetric, and hence the resulting DFT output has a non-zero imaginary-valued part, in flagrant contradiction with the original continuous-world case. (Note that in Fig. rotcosgrata the amplitude of the imaginary-valued part of the DFT spectrum has been somewhat exaggerated in order to make it clearly visible in the gray-level plot.)
Remark: Note that the rotation theorem is only valid in the continuous world, but as clearly illustrated here it no longer holds in the discrete world.
g(x,y) = [(1/T)III(x/T) δ(y)] * rect(x) ---> G(u,v) = III(Tu) sinc(u) δ(v)
where "*" indicates convolution, or in other words:
g(x,y) = Σmrect(x - mT) ---> G(u,v) = (1/T)sinc(u) [Σmδ(u - m/T)] δ(v)
where the summations run over all integer values m. Note that the line-impulse train (1/T)III(x/T) has line-impulse intervals of T and line-impulse heights of 1, while the line-impulse train III(Tu) has line-impulse intervals of 1/T and line-impulse heights of 1/T (see for the 1D equivalent Footnote 2 on p. 92 of the DFT book, or [Bracewell00 pp. 83, 577]).
Note that the periodic line grating g(x,y) is, in fact, a 2D extension along the y axis of the periodic rectangular wave in the 1D case (see above).
Fig. grat shows a 128x128-point DFT of the periodic line grating g(x,y) with period T = 1 within the range -8...8 to both directions: Rows (a), (b) and (c) show what happens when the line widths are gradually increased (illustrating the dilation theorem), and row (d) shows what happens when the line grating (c) is shifted to the right by 1/8, i.e. by one discrere-world pixel (illustrating the shift theorem).
Comparing rows (c), (b) and (a) in Fig. grat we see that as the line width in the signal domain
decreases, the modulating sinc in the
spectral domain becomes wider (as predicted by the dilation theorem). Note that in row (a) the line
widths equal one discrete-world pixel, i.e. the smallest possible non-zero width in the discrete world.
This one-pixel wide line grating is, in fact, the discrete counterpart of the continuous-world line-impulse
grating parallel to the y axis, g(x,y) = III(x), whose CFT is the impulse
comb G(u,v) = III(u) δ(v) along the u axis of the spectrum
(see [Bracewell00 p. 335]). In the continuous world, if the line widths in the signal domain become
infinitely small (so that the lines actually become line-impulses with a constant height of 1), then the
modulating sinc function in the spectrum becomes infinitely wide, and hence the spectrum becomes an impulse
comb with a constant height of 1 along the u axis. Note that the discrete-world counterpart of a
comb with infinitely-small impulse widths is a comb consisting of one-pixel wide elements.
On the relationship between the continuous-world impulse and its discrete counterpart (in the 1D case)
see Appendix A of the DFT book.
Remark: The relationship between the DFT of the periodic straight line grating and the DFT of the infinite straight bar (see above) is explained in Sec. D.9.1 and Figs. D.7-D.11 in the DFT book (although the illustrations provided there concern the 1D triangular case). The effect of the number of periods we include in the input signal on the resulting DFT is explained in Remark 7.1 and Fig. 7.1 of the DFT book.
DFT artifacts:
Because the periodic straight line grating is not band limited (its CFT consists of an impulse comb
extending along the entire u axis to both sides of the origin), it is clear that the DFT spectrum in
this case is flawed by aliasing, just like the periodic rectangular wave in the 1D case (see above).
The periodic straight line grating may also suffer from leakage, just like the periodic rectangular wave
in the 1D case. This was already explained in detail in the case of the cosinusoidal straight line grating
(see Fig. cosgratleak above).
g(x,y) = [(1/T)III[(xcosθ - ysinθ)/T] δ(xsinθ + ycosθ)] * rect(xcosθ - ysinθ) --->
G(u,v) = III[T(ucosθ - vsinθ) sinc(ucosθ - vsinθ)] δ(usinθ + vcosθ)
where "*" indicates convolution, or in other words:
g(x,y) = Σmrect[(xcosθ - ysinθ) - mT] --->
G(u,v) = (1/T)sinc[(ucosθ - vsinθ)] [Σmδ[(ucosθ - vsinθ) - m/T]] δ(usinθ + vcosθ)
where the summations run over all integer values m.
Thus, the CFT of the rotated periodic line grating consists of a rotated version of the infinite impulse comb of the previous example. Note that the rotated impulse comb always passes through the origin of the spectrum, and remains perpendicular to the rotated grating in the signal domain.
Fig. rotgrat shows, for different angles θ, the 128x128-point DFT of the rotated line grating g(x,y) having period T = 1 within the range -8...8 to both directions: (a) θ = 14o; (b) θ = 10o; (c) θ = 8o; (d) θ = 3o. Fig. rotgrata is identical to Fig. rotgrat, except that its leftmost column and most bottom row have not been zeroed (see the first remark below). Finally, Fig. rotgrat1 shows, for different periods T, the 128x128-point DFT of the rotated line grating g(x,y) with θ = 3o within the range -8...8 to both directions: (a) T = 1.05, so that f = 1/T = 0.95; (b) T = 1.05/2, so that f = 1.90; (c) T = 1.05/4, so that f = 3.81; (d) T = 1.05/8, so that f = 7.62.
It is interesting to compare the three figures of the present example with their respective counterparts in the case of the rotated cosinusoidal line grating, in which each of the spectra includes only the first-harmonic impulse pair, and no higher-order impulses are present. This difference between the two cases has a significant impact on their DFT artifacts. Note, in particular, the absence of higher-order sampling moirés and the absence of jaggies in the case of the cosinusoidal grating (see the DFT artifacts of the rotated line grating below, and those of the rotated cosinusoidal grating above).
DFT artifacts:
Because the rotated line grating is not band limited (its CFT consists of an impulse comb extending
ad infinitum to both sides of the origin), it is clear that the DFT spectrum in
this case is flawed by aliasing. And indeed, whenever this spectral impulse comb exceeds the boundaries
of the DFT spectrum, it folds over and re-enters from the opposite side. But because in the CFT the
impulse comb extends to both directions ad infinitum, it follows that in the discrete world the
folded-over impulse comb exceeds the boundaries of the DFT spectrum over and over again, each time
re-entering from the opposite side. This is explained in more detail in Example 5.7 and
Fig. 5.14 of the DFT book. Note that the CFT of the rotated
straight line grating consists of a single infinite impulse comb that passes through the spectrum origin.
All the other parallel impulse combs in the DFT spectrum are, therefore, easily recognized as aliasing
artifacts.
If any of the folded-over impulses due to aliasing happens to fall close enough to the spectrum origin,
its new frequency there is so small that it may correspond back in the signal domain to a new, visible
low-frequency parasite structure (see row (d) in Fig. rotgrat and all rows in Fig. rotgrat1). This parasite
structure does not exist in our original function (the continuous-world line grating), and it only
appears in its sampled version due to aliasing (i.e. due to the undersampling of the original grating).
Such low-frequency structures are known as sampling moirés; this subject is explained
in greater detail in [Amidror09, Sec. 2.13]. Note that in row (d) of Fig. rotgrat the folded-over impulses
which fall close to the spectrum origin are high-order impulses of the original CFT, so that the
corresponding sampling moiré effect in the discrete signal domain is also of the same high order
and hence not very prominent. But in row (d) of Fig. rotgrat1 the folded-over impulses which fall
closest to the origin are the first-order impulses of the original CFT, so that the corresponding
sampling moiré effect in the discrete signal domain is also a first-order moiré, which
is indeed very prominent (note that the original line grating is no longer visible in this case, and we
only see its low-frequency alias). Obviously, in the case of the rotated cosinusoidal grating (see above)
the higher-order sampling moiré has no equivalent, since in that case there exist no
higher-order impulses. The only sampling moiré effect which may exist in the case of the
cosinusoidal line grating is the first-order moiré (compare Figs. rotgrat and rotgrat1 with
their respective cosinusoidal counterparts, Figs. rotcosgrat and rotcosgrat1).
Finally, note that unlike in row (c) of Fig. rotcosgrat1, the effect that we see in
row (c) of Fig. rotgrat1 is indeed a true sampling moiré effect, and not merely a
sub-Nyquist artifact: Unlike in the cosinusoidal grating, the DFT spectrum in the present case does
include low-frequency
impulses which correspond to the low-frequency structure that we see in the signal domain; simply,
these folded-over impulses are higher-order impulses of the black/white straight line grating, which
do not exist in the cosinusoidal case.
The rotated line grating may also suffer from leakage. This was already explained in detail in the
case of the rotated cosinusoidal line grating above.
Remark: Note that in Fig. rotgrat we have zeroed the leftmost column and the most bottom row in the signal domain. This is done here in order to avoid a quite unusual DFT artifact, which is explained in detail in Sec. 8.4 and Fig. 8.4 of the DFT book. As shown in Fig. rotgrata, without this correction the discrete input signal is no longer centrosymmetric, and hence the resulting DFT output has a non-zero imaginary-valued part, in flagrant contradiction with the original continuous-world case. (Note that in Fig. rotgrata the amplitude of the imaginary-valued part of the DFT spectrum has been somewhat exaggerated in order to make it clearly visible in the gray-level plot.)
Remark: The relationship between aliasing and the jaggies which appear in the signal domain along the edges of the rotated bar is explained in detail in Sec. 8.5 of the DFT book.
Remark: Note that the rotation theorem is only valid in the continuous world, but as clearly illustrated here it no longer holds in the discrete world.
DFT artifacts:
The only difference between the twelve rows of Figs. circcos1-circcos3
is in the radial period T of the circular grating. As long as the radial period is
sufficiently large, the sampling rate is sufficient for capturing the main features of the
circular grating and there is no aliasing (see rows (a)-(d) in the figures). In such cases the
impulsive ring in the spectrum is fully contained within the frequency range of the DFT
spectrum, and no foldover occurs. The signal-domain counterpart is that the circular
cosinusoidal grating can be easily recognized in the sampled figure, and only some minor
distortions can be observed. (Note that these distortions are not caused by aliasing, since
in rows (a)-(d) there is no aliasing. The minor distortions in the signal domain, particularly
visible in row (d), are discussed in the DFT book in Problem 5-18; the minor ripple artifact
in the DFT spectra is due to leakage).
But when the radial period T gets smaller the sampling rate
becomes insufficient. In such cases (see rows (e)-(l) in the figures) the spectral impulsive
ring exceeds the borders of the DFT spectrum and folds-over, so it is not surprising that
in the signal domain the structure of the circular grating is lost and a lower-frequency
structure takes its place. And if the folded-over impulse ring falls sufficiently close to the
spectrum origin (see rows (h)-(j) and (l)), the new aliased low-frequencies near the origin
manifest themselves in the form of a strong sampling moiré effect that completely
overshadows the original structure of the circular grating.
When the folded-over frequencies fall exactly on the spectrum origin, they correspond
to a singular moiré, i.e. a moiré having frequency zero. For example, in row (i)
the moiré effect is singular along the two main axes, i.e. along the directions from which
the folded-over impulse-ring touches the spectrum origin. But when the folded-over
frequencies fall just slightly away from the spectrum origin the moiré effect has low,
visible frequencies and it becomes very prominent. A more detailed explanation on this
subject and on the geometric shapes (hyperbolic, parabolic or elliptic) of the moiré fringes
that are obtained in this case can be found in [Amidror09 Sec. 10.7.5].
Note that the aliasing effect in our figures may look as a mirroring-back or a reflection of
the exceeding parts of the spectral rings from the same edge of the DFT spectrum. But
the correct interpretation of the foldover is that whatever exceeds from one side
of the DFT spectrum re-enters in a cyclical way from the opposite side.
Let us return to our discussion above on the artifacts that may occur in the case of the cosine function. As we have seen there, when the frequency f of a sampled cosine is very close to (1/2)fs, half of the sampling frequency fs (i.e. to the boundaries of the DFT spectrum; see p. 73 in the DFT book), a low-frequency beating effect becomes visible in the signal domain, due to a low-frequency cosinusoidal modulation. This beating effect, illustrated by rows (e),(f),(h) in Figs. cosfreq1-cosfreq2, is not a true sampling moiré but rather a pseudo-moiré effect: As we can see in these 3 rows, no corresponding low-frequency impulses exist in the respective spectra, and even in the signal domain, the beating effect in question does not really represent a low frequency signal (as in rows (i) and (j) of Fig. cosfreq2) but rather a highly oscillating signal that is only modulated by two interlaced low-frequency cosinusoidal envelopes. These beating effects are called sub-Nyquist artifacts, reflecting the fact that they may occur well below the Nyquist frequency 0.5fs.
As shown in Figs. cosfreq3-cosfreq5, such artifacts may also appear when sampling a cosine signal g(x) = cos(2πfx) whose frequency f is close to any other rational fraction of the sampling frequency fs, such as (1/4)fs, (1/6)fs or (1/3)fs, respectively. The sub-Nyquist artifact which occurs when f is close to the fraction (m/n)fs is called the (m/n)-order sub-Nyquist artifact. A more detailed analysis of these artifacts can be found in this Tutorial.
As we can see in Fig. subnyq2D12, higher-order sub-Nyquist artifacts are much more difficult to observe in the 2D case than in the 1D case. The reason is that 2D cases are usually represented by gray-level density plots (see Sec. 1.5.2 in the DFT book), which are observed from the top and not from the side like 1D plots. Because in higher-order sub-Nyquist artifacts the modulating envelopes are interlaced, the node of one envelope always coincides with the body of another envelope. In the 1D case, where the waves are viewed in profile, the nodes of the interlaced envelopes are rather easy to recognize; but in the 2D density plots, the nodes of one envelope are hidden below the body of another envelope, and they are therefore more difficult to identify (compare row (b) of Fig. subnyq2D12 with its 1D section through the horizontal axis, shown in row (d) of Fig. cosfreq3). In row (c) of Fig. subnyq2D12 the diagonal structure of the interlaced envelopes can hardly be perceived, and we only see the sampled 2D cosine itself. And in row (d), which is drawn at a 2-fold higher resolution than row (c), the diagonal interleaved envelopes are already blurred by the halftoning elements being used to generate the gray levels of the density plot, and the individual 128x128 pixels are no longer visible (see under a magnifying glass). Note that in the 2D (1/2)-order sub-Nyquist artifacts shown in rows (b)-(d) of Fig. subnyq2D the modulating envelopes can be identified much more easily, since the envelopes in this case are not interlaced and their nodes are clearly visible even when observed from the top.
Interestingly, however, 2D higher-order sub-Nyquist artifacts can be observed more easily when the sampled 2D function is drawn as a pseudo-3D wireframe plot (see Sec. 1.5.2 in the DFT book). This is clearly illustrated in Fig. subnyq2D12a, which shows exactly the same 2D cases as Fig. subnyq2D12 but using wireframe plots rather than density plots. Although the nodes themselves are not as obvious here as in the corresponding 1D plots, one can still observe here the ripple artifact (the round "humps" around the maxima of the interlaced envelopes).
|