Digital Signal Processing Reference
In-Depth Information
2-d Fast Fourier Transform
The 2-d Fast Fourier Transform (2-d FFT) is an extension of the 1-d FFT
discussed in Section 3.1.3. As in the 1-d case, it is a much faster computation
method of the 2-d DFT discussed in the previous section, by using some
periodic properties of the exponential functions in Equation 6.10 and Equa-
tion 6.11.
An
N
1
N
2
2
complex multiplications, whereas a 2-d FFT requires only (
N
1
log
2
N
1
)
×
N
2
point 2-d DFT or
N
1
×
N
2
point 2-d IDFT requires
N
1
2
×
×
(
N
2
log
2
N
2
) complex multiplications, when both
N
1
and
N
2
are powers of 2,
also termed as
radix-2 2-d FFT
. This is especially significant for large values
of
N
1
and
N
2
. For example, when
N
1
=
N
2
= 128, the number of complex
multiplications are 268,435,460 for direct 2-d DFT computation, and only
229,376 for a radix-2 2-d FFT.
6.1.2
Simulation of 2-Dimensional Imaging Process
The fundamental aspect of 2-dimensional image processing is the transmis-
sion of discrete video signals through the medium, between the
transmitter
and
receiver
. Assuming the medium to be LSI, the complete imaging process,
as shown in Figure 6.3, is described in the
spatial domain
by the following
equations, in the spatial range 0
≤
n
1
≤
N
1
-
1
,
0
≤
n
2
≤
N
2
-
1:
(
)
=
(
)
(
)
+
(
)
Restored image
yn n
,
xn n
,
* *
hn n
,
η
n n
,
(6.12)
1
2
1
2
1
2
1
2
and
(
)
=
(
)
(
)
Restored image
xn n
,
yn n
,
* *
gn n
,
(6.13)
r
1
2
1
2
1
2
Transmission
system
Restoring
filter
Degraded
image
y
r
(n
1
,n
2
)
g(n
1
,n
2
)
Original
picture
x(n
1
,n
2
)
h(n
1
,n
2
)
Restored
image
x
r
(n
1
,n
2
)
+
Noise
η
(n
1
,n
2
)
FIGURE 6.3
Basic imaging system.
