Image Processing Reference
In-Depth Information
f
(
k
)
and
g
(
k
)
are samples of band-limited signals
f
(
t
)
and
g
(
t
)
. Likewise, theorem
7.4 also holds if
δ
is interpreted as the Kronecker delta.
Convolution and DFT
It is logical to use the same definition of convolution on an array holding
N
scalars
as the one given for an infinitely large grid containing samples of a function.
N−
1
h
(
k
)=(
f
∗
g
)(
k
)
f
(
k
−
n
)
g
(
n
)
(7.26)
n
=0
However, the translated function
f
(
k
−
n
) needs to be more elaborately defined. The
index
k
n
must refer to well-defined array elements. This is because even if
k
and
n
are within 0
−
n
is not necesserily in that range,
which is a problem that an infinite grid does not have. Remembering that the DFT
was derived from lemma 6.2 and that both
f
(
t
) and
F
(
ω
) have been extended to be
periodic, it is clear that the translation
k
···
N
−
1, their difference
k
−
n
on the grid is equivalent to the
circular
translation
discussed in Sect. 6.4. In other words,
−
f
(
m
)
←
f
(Mod(
m, N
))
(7.27)
as well as
n, N
) (7.28)
should be used in practice. Using the above definition for convolution together with
circular translation is also called
circular convolution
.
Upon this interpretation of convolution, we now investigate how a circular con-
volution transforms under DFT. Let the symbol
f
(
k
−
n
)
←
f
(Mod(
k
−
represent the DFT, and let
F
,
G
and
H
be DFTs of the discrete function values
f
,
g
, and
h
on a grid. The functions
f
,
g
, and
h
are assumed to have been defined on a finite grid of
t
m
, while the functions
F
,
G
, and
H
are defined on a grid of
ω
m
. Both grids have the same number of grid
points,
N
, as generated by integers
m
F
∈
0
,
1
,
2
···
N
−
1.
⎛
⎝
j
⎞
⎠
exp
N
l
g
)(
k
)=
1
ik
2
πl
N
F
(
f
∗
f
(
j
)
g
(
l
−
j
)
−
⎧
⎨
F
(
m
)exp
ij
2
πm
N
N
l
1
=
⎩
j
m
⎫
G
(
n
)exp
i
(
l
exp
(7.29)
⎬
j
)
2
πn
N
ik
2
πl
N
×
−
−
⎭
n
We change the order of summations so that we can obtain a “delta” function that
helps us to annihilate summations. However, we first shift the order of the sums with
indices
l, j
with those with the indices
n, m
:
