Image Processing Reference
In-Depth Information
6.3 Discrete Fourier Transform (DFT)
When
f
is a finite extension function with the extension
T
, Eq. (5.14) states that
f
can be periodized and synthesized by means of FCs,
F
(
n
2
T
), which are samples of
an infinite extension function
F
. Albeit theoretically infinite in number, the discrete
function values,
F
(
n
2
T
), decrease since they are FCs. As such, they must decrease,
or else the synthesis formula will not converge to the periodized version of
f
. Ac-
cordingly,
F
(
n
2
π
T
lim
n→∞
)
→
0
(6.35)
is a fact for real signals and from Fourier series we obtain a periodic function which
approximates the periodized
f
(
t
) well. Consequently, when synthesizing
f
from its
FCs as in Eq. (5.14), there exists
N
such that we can ignore the
F
(
m
2
T
) for which
m
N
, and still obtain a reasonably good approximation of the periodized
f
(
t
).
In accordance with the above, we will attempt to bring the concept of the FT
closer to applications, by assuming in this section that not only
f
has a finite exten-
sion
T
, but that the corresponding FCs are also finite in number, i.e., only FCs
≥
ω
n
=
n
2
π
T
N−
1
n
=0
{
F
(
nω
n
)
}
with
(6.36)
are nonzero. According to Eq. (5.14), we can synthesize
f
(
t
)
N−
1
2
π
T
f
(
t
)=
F
(
ω
m
) exp(
iω
m
t
)
(6.37)
m
=0
by means of the following
N
coefficients:
T
2
1
2
π
F
(
ω
m
)=
f
(
t
) exp(
−
iω
m
t
)
dt
(6.38)
−
T
2
where
m
1. Because
f
has a finite extension, any sampling of it will
yield a finite number of function values. If we choose to sample
f
at a set of
t
n
in such a way that the sampling interval corresponds to what the Nyquist theorem
affords us, it should be possible not to lose information. The largest sampling step
suggested by the Nyquist theorem is 2
π
(
N
2
T
)
−
1
=
∈
0
,
···
N
−
T
N
, where
N
2
T
represents the
N−
1
n
=0
extension of
{
F
(
nω
n
)
}
. We proceed accordingly, and substitute
t
n
in Eq. (6.37)
N−
1
2
π
T
t
n
=
n
T
N
f
(
t
n
)=
F
(
ω
m
) exp(
iω
m
t
n
)
with
(6.39)
m
=0
Notice that there are exactly
N
samples of
f
(
t
n
). Thus, it should be possible to com-
pute
F
(
ω
m
) appearing in Eq. (6.39) directly from
f
(
t
n
), without passing through
a continuous reconstruction of
F
(
ω
) (and then sampling it) in Eq. (6.38). We ob-
serve that the sequence of complex numbers exp(
it
n
ω
m
) appearing in Eq. (6.39)
