Hi and welcome to module 8.3,
in which we will apply frequency
analysis to digital imaging.
We will first define DFT for
two dimensional signals, and
then we will look at the amount of
information that we can extract
from the magnitude and
the phase of the DFT of an image.
4D analysis of two dimensional signals
can be developed exactly as we did for
the one dimensional case.
Says here we're concerned
mostly with digital images.
Namely finite support,
two dimensional images,
we will only review the definition
of the two dimensional DFT.
So let's consider a two dimensional
finite support signal of support,
big N one times big N two.
The DFT is defined as the double sum for
the first index that goes from zero to
big N one minus one, and the second
index that goes from zero to big N two
minus one of the values of
the dimensional signal over the support.
Times the product of two
complex exponentials
whose frequencies are 2
pi over big N1 n1 k1,
and 2 pi over big N2 n2 2 k2.
The product of this two complex
exponential represents a basis
function for
the space of images of size n1 times n2.
The DFT can be easily inverted just
like we did in the one dimensional case.
We take basically complex exponentials
with the sign reverse and
we repeat the sum taken now
the DFT coefficients into the sum.
Normalisation is by convention
applied to the inverse formula and
in this case we have to divide the sum
by the product of big N1 times big N2.
It is certainly instructive to look in
more detail at the basis functions for
the space N1 times N2 images.
These have the form that we have shown
before in the DF sum, and we can
easily prove, like in the one dimensional
case, that they are orthogonal.
There are n1 times n2 basis function for
an image of that size, and so,
it would be very hard to look at each one
of them, even for images of moderate size.
But we can try and plot some key
representative basis functions to give you
an idea of what the building
blocks are for an image in space.
We will show this basis functions by
plotting the real part only as a grey
scale image where the value of
zero is indicated by a black and
the value of one is indicated by white.
So here we have the space
of 256 by 256 pixel images.
And this is one of the simplest
basis functions that we can plot.
We keep the vertical frequency as 0 and
the horizontal frequency spans
1 period between 0 and 255.
So if we were to look at this in a three
dimensional space we could plot,
this is the image plane and these
are the values of the basis function.
And this a wave,
a solid wave that goes like this, right?
So it goes down and and
then it goes up again and
here we have the white part and
here we have the black part.
We can invert the roles of the vertical
and horizontal frequency and
we get an image which is simply a noted
degree of rotation of the previous one.
We can increase the horizontal frequency
at this point for K 1 equal to two we
will have the basis function spans two
periods over the support of the image.
This will be 3 periods, and if we
swap the roles of the frequency, we obtain
again an image rotated by 90 degrees.
We can increase the frequency the more and
the density of these bands
will increase correspondingly.
Whenever the vertical frequency and
horizontal frequency are the same,
the bands will be angled at 45 degrees.
And by varying the frequencies,
we can obtain a wide range of
different angles for the bands.
The good news is that a 2D-DFT
basis functions are separable,
and so the DFT can be
computed in a separable way.
In particular, we first compute
a one D-DFT along the columns.
So if this is our image of size big n
one time big n two, we first compute
big n one D-DFT is of size and
two along the columns.
And once we're done with that,
we compute 1 DDFTs along the rows.
So, computationally, speaking, we first
need to compute big n1, DFTs of size n2.
We know that we can use
the DFFD algorithm.
So the cost will be N two
log in base two of N two and
then we need to compute N
two FFTs of size N one.
So there would be N one log in base two of
N one which is much less than N one and
N two squared.
The cost of implementing a two dimensional
DFT directly from the equation.
We can also express
the two D-DMT matrix form.
For that we need to express
first of all the signal,
the two dimensional signal as a matrix.
This is very straight forward
because an n one times n two image
is simply an n one times n two matrix.
There is only the technicality
that the Orientation
of the rows is inverted with
respect to the Cartesian notation.
So for instance in the Cartesian plane,
N2 would go from, say, 0 upwards.
But if we express, and this is our image,
but if we express this in matrix notation,
this element of the matrix normally is 00.
So, there's a flipping
of the vertical axis.
But this is just a technicality.
You will also recall the N times N DFT
matrix that we saw in module 4.2.
This is a standard DFT matrix of size N,
where W recall this simply e to
the -j to phi over capitan N.
With this notation implies,
let's look at the DFT formula once again.
The inter summation is
simply the product of
the DFT matrix of size big
N2 times the signal matrix.
We call this intermedia
matrix capital V and
Capital V belongs to the space
of N2 times N1 matrices.
Then the outer sum can be expressed,
the right product of
the matrix V which is defined,
times a DFD matrix, of size capital N1.
And so
the resultant signal is a matrix that
collects the DFT values for the image.
In compact form we can express
the two dimensional DFT
as a product of a DFT matrix exercise and
two times the image times the DFT
matrix times the size and one.
So now we know how to compute
a two dimensional DFT.
Well, can we look at one?
We can try and
plot the magnitude of the DFT.
Since the DFT is a two
dimensional signal and
therefore can be interpreted as an image.
But this wouldn't work because the dynamic
range of the DFT is way too big for
either a monitor screen or
a piece of paper to represent.
We wouldn't have grayscale
level to show the details.
So we could try to normalize the values
by dividing the DFT magnitude
by its maximum value.
And yet, that wouldn't work either,
because for images on average,
the distribution of the the magnitude
of the three coefficients
follows a curve like this one.
So what we have here is a few outliers
here that really go above the average
values of the coefficients, and some tail
outliers here that drive the value down.
What we're interested in is
this band between the extreme.
So we take a two step approach.
First we remove the flagrant outliers,
for instance the value of DFT in [0,
0] is simply the sum of all pixel values.
Now, for a grey scale images where all
pixels are positive values between zero
and one, say,
this will be definitely a large value
with respect to any other coefficient.
And then, to remove the tail
we use nonlinear mapping.
For instance, we use a curve like x to the
power of one-third after normalizing all
values between 0 and 1.
So for instance,
if this is the range between 0 and 1,
the nonlinearity will map this range
like so, which means that the tail
outliers that we've seen before
will be squished in a band.
That is very close to zero, and so
they will appear as black pixels.
And the rest of the values,
those that we're interested in,
will occupy the bulk of
the dynamic range of the medium.
If we do that,
we obtain something like this.
So our little dog has been transform
in this, cryptic image here.
Where if you look very closely we can
identify for instance some lines here and
here that correspond to
clear lines in the image
captured by some of the basic functions
that have this orientations, but
by and large it's very, very difficult
to understand what's going on.
We get a confirmation of
our suspicion if we try to
invert the free so we take an image,
we take the Fourier transform,
we discard the phase information, and
then we do an inverse Fourier
transform from the magnitude.
What we get if we start with a dog
picture is this picture here,
where we are absolutely unable
to guess the original picture.
What is more interesting is that if we do
the same thing but keep in just the phase.
In other words,
we throw away the magnitude,
we set the magnitude uniformly at one.
But we keep the phase information and
then we do an inverse transform.
We obtain the following image.
So with images, the phase information
carries most of the relevant information.
So why is that?
The idea is that most of
the semantic information in an image
is contained into its edges.
Edges are points of discontinuity
in the gray level's signal.
In 1-D, you would represent
an edge as a transition from,
say, a wide level to a dark level.
This resolution is what
the eye perceives as image.
Now edges, therefore,
are very localized in space.
And they're not captured by the DFT's
magnitude, which represents a distribution
in frequency of the energy
of the whole image.
In order to obtain an edge from
the combination of functions on
the other hand, their phase has to
be aligned in a very precise manner.
And that's why the phase information
captures the intelligibility
part of an image.
A consequence of this is that the global
DFT of an image is only of limited use in
image processing.