Image Processing Reference
In-Depth Information
f
(
n
)=
f
(
m
)
,
and
F
(
n
)=
F
(
m
)
.
(6.52)
Hence, the translation of indices in the time, or frequency domain must be done by
means of a
circular addition
, which means that
n
+
m
and
n
+
m
+
kN
are equivalent.
This results in a
circular topology of DFT
where the first array element labelled as
0 is the nearest neighbor of the one labelled as 1 and
N
1.
Although it is feasible to find neighbors using visual workarounds for discrete
functions defined on 1D-domains (Fig. 6.5), it is definitely a challenge to “visually”
find the neighbor of a point close to grid boundaries in higher dimensions. The arith-
metic modulo function, here abbreviated as Mod(
m, N
), is handy in practical appli-
cations of DFT to avoid the practical difficulties associated with its circular topology.
The function computes the unique remainder of
m
after division by
N
; that is, the
result is always one of the integers 0
−
···
N
−
1, e.g.,
Mod(3
,
17) = Mod(
−
14
,
17) = Mod(20
,
17) = 3
(6.53)
Ordinary addition using the Mod function, i.e., Mod(
m
+
n, N
), defines a so-
called finite group so that integers that differ with integer multiples of
N
are equiva-
lent to each other. This allows a seamless interpretation of
all
translations on rectan-
gular discrete grids, in all dimensions, which is precisely what is needed to interpret
the indices of DFT correctly.
For example, when
N
=17, the integers 3
,
−
14
,
20 represent the same coeffi-
cient
f
(3) =
f
(
−
14) =
f
(20)
and
F
(3) =
F
(
−
14) =
F
(20)
(6.54)
although
14 and 20 are obviously not possible to use as the indices of an array
having 17 elements, which has index labels 0
−
16. After an application of the mod-
ulo function, e.g., Eq. (6.53), the resulting integers can be used as indices of arrays
holding the discrete values of
f
and
F
, Eq. (6.54).
A systematic use of the Mod function in all index references, additions, and sub-
traction, known also as
modulo arithmetic
, enables
circular translation
, i.e., transla-
tions that hit no grid boundaries. This can be used to “walk” around in the DFT arrays
conveniently, which is particularly important for a correct implementation and inter-
pretation of the convolution operation by DFT, as we will study in Chap. 7. The
circular interpretation of the DFT indices on 1D domains is illustrated by Fig. 6.5
using
N
points (
taps
). Note that the first index is 0 and the last index is
N
···
−
1, and
the indices are periodic with the period
N
in the modulo
N
arithmetic.
