2D DFT2.32003/01/022003/03/11Rob"The Kid"Nowaknowak@rice.eduMichaelHaagmjhaag@rice.eduRob"The Kid"Nowaknowak@rice.edu2D-DFTconvolutionDFTFFTimageimage processingtwo-dimensional dftThis module extends the ideas of the Discrete Fourier Transform (DFT) into two-dimensions, which is necessary for any image processing.2D DFT
To perform image restoration (and many other useful image
processing algorithms) in a computer, we need a Fourier
Transform (FT) that is discrete and two-dimensional.
Fklu2kNv2lNFuv
for
k0…N1 and
l0…N1.
FuvmnfmnumvmFklmN10nN10fmn2kmN2lnN
where the above equation ()
has finite support for an
NxN
image.
Inverse 2D DFT
As with our regular fourier transforms, the 2D DFT also has
an inverse transform that allows us to reconstruct an image
as a weighted combination of complex sinusoidal basis
functions.
fmn1N2kN10lN10Fkl2kmN2lnNPeriodic Extensions2D DFT and Convolution
The regular 2D convolution equation is
gmnkN10lN10fklhmknl
Below we go through the steps of convolving two
two-dimensional arrays. You can think of
f as representing an image and
h represents a PSF, where
hmn0 for
mn1 and
mn0.
hh00h01h10h11ff00…f0N1⋮⋱⋮fN10…fN1N1
Step 1 (Flip h):
hmnh11h100h01h000000
Step 2 (Convolve):
g00h00f00
We use the standard 2D convolution equation () to find the first element of
our convolved image. In order to better understand what is
happening, we can think of this visually. The basic idea is
to take
hmn and place it "on top" of
fkl, so that just the bottom-right element,
h00 of
hmn overlaps with the top-left element,
f00, of
fkl. Then, to get the next element of our convolved
image, we slide the flipped matrix,
hmn, over one element to the right and get the
following result:
g01h00f01h01f00
We continue in this fashion to find all of the elements of
our convolved image,
gmn. Using the above method we define the general
formula to find a particular element of
gmn as:
gmnh00fmnh01fmn1h10fm1nh11fm1n1Circular Convolution
What does
HklFkl
produce?
2D Circular Convolution
g~mnIDFTHklFklcircular convolution in 2D
Due to periodic extension by DFT ():
Based on the above solution, we will let
g~mnIDFTHklFkl
Using this equation, we can calculate the value for each
position on our final image,
g~mn. For example, due to the periodic extension of
the images, when circular convolution is applied we will
observe a wrap-around effect.
g~00h00f00h10fN10h01f0N1h11fN1N1
Where the last three terms in are a result of the wrap-around effect caused
by the presence of the images copies located all around it.
Zero Padding
If the support of h is
MxM
and f is
NxN,
then we zero pad f and
h to
MN1 x
MN1 (see ).
Circular Convolution = Regular Convolution
Computing the 2D DFTFklmN10nN10fmn2kmN2lnN
where in the above equation,
nN10fmn2lnN
is simply a 1D DFT over n.
This means that we will take the 1D FFT of each row; if we
have N rows, then it will
require
NN operations per row. We can rewrite this as
FklmN10f′ml2kmN
where now we take the 1D FFT of each column, which means
that if we have N columns,
then it requires
NN operations per column.
Therefore the overall complexity of a 2D FFT is
ON2N
where
N2 equals the number of pixels in the image.