Image Processing Reference
In-Depth Information
N
n
g
)(
k
)=
1
F
(
f
∗
F
(
m
)
G
(
n
)
×
m
exp
ij
2
πm
N
exp
i
(
l − j
)
2
πn
N
exp
−ik
2
πl
N
l
j
exp
il
2
π
(
n
exp
ij
2
π
(
m
N
n
F
(
m
)
G
(
n
)
l
1
−
k
)
−
n
)
=
N
N
m
j
N
2
N
=
F
(
m
)
G
(
n
)
δ
(
n
−
k
)
δ
(
m
−
n
)
m
n
N
2
N
=
F
(
n
)
G
(
n
)
δ
(
n
−
k
)
n
=
N
F
(
k
)
G
(
k
)
(7.30)
We note here that the two Kronecker delta functions are obtained by recognizing
sums (the ones with
l
and
j
) as scalar products between complex exponentials, see
Eq. (6.42), and that these deltas annihilated
1
two summations (the ones with
m
and
n
) before they disappeared. Accordingly, we give the definition for circular convolu-
tions.
Definition 7.4.
Given two
finite
discrete signals
f
(
m
)
and
g
(
m
)
, with
m
being inte-
ger in
0
,
···
N
−
1
, the circular convolution operation for such signals is denoted by
∗
, and is defined as
N−
1
h
(
k
)=(
f
∗
g
)(
k
)=
f
(
k
−
n
)
g
(
n
)
(7.31)
n
=0
All references to indices, including additions, are in
Mod
N
arithmetic.
Accordingly,
h
(
m
), the outcome of the discrete convolution, is periodic with the
period
N
, just as the component sequences
f
(
m
) and
h
(
m
). We summarize the result
on
DFT of convolution
as a lemma.
Lemma 7.2.
Given the discrete circular convolution defined by Eq. (7.31), it trans-
forms as multiplication under the DFT
h
(
m
)=(
f
∗
g
)(
m
)
⇔
H
(
k
)=
N
F
(
k
)
·
G
(
k
)
(7.32)
Likewise, theorem 7.4 holds if
δ
is interpreted as the Kronecker delta.
1
The
δ
s are very efficient “summation annihilators”. They erase summations twice: The first
time when they are created, and the second time when they disappear. The Dirac distribu-
tions are the analogous “integration annihilators”.
