Introduction to the Fourier Rework
BASIS FUNCTIONS:
The Fourier Rework ( on this case, the 2D Fourier Rework )
is the collection growth of a picture perform ( over the 2D house
area ) by way of “cosine” picture (orthonormal) foundation capabilities.
The definitons of the remodel (to growth coefficients) and
the inverse remodel are given beneath:
F(u,v) = SUM{ f(x,y)*exp(-j*2*pi*(u*x+v*y)/N) }
and
f(x,y) = SUM{ F(u,v)*exp(+j*2*pi*(u*x+v*y)/N) }
the place u = 0,1,2,...,N-1 and v = 0,1,2,...,N-1
x = 0,1,2,...,N-1 and y = 0,1,2,...,N-1
j = SQRT( -1 )
and SUM means double summation over correct
x,y or u,v ranges
First we are going to examine the “foundation” capabilities for the Fourier
Rework (FT). The FT tries to characterize all photos as a summation
of cosine-like photos. Due to this fact photos which are pure cosines have
notably easy FTs.
|
This exhibits 2 photos with their Fourier Transforms immediately beneath.
The pictures are a pure horizontal cosine of 8 cycles and a pure
vertical cosine of 32 cycles. Discover that the FT for every simply has
a single part, represented by 2 vibrant spots symmetrically
positioned concerning the heart of the FT picture. The middle of the picture is
the origin of the frequency coordinate system. The u-axis runs left
to proper by means of the middle and represents the horizontal part of
frequency. The v-axis runs backside to high by means of the middle and
represents the vertical part of frequency. In each circumstances there
is a dot on the heart that represents the (0,0) frequency time period or
common worth of the picture. Photos often have a big common
worth (like 128) and plenty of low frequency data so FT
photos often have a vibrant blob of parts close to the middle.
Discover that prime frequencies within the vertical course will trigger
vibrant dots away from the middle within the vertical course.
And that prime frequencies within the horizontal course will trigger
vibrant dots away from the middle within the horizontal course.
 |
Listed here are 2 photos of extra normal Fourier parts. They’re photos
of 2D cosines with each horizontal and vertical parts. The one
on the left has 4 cycles horizontally and 16 cycles vertically. The
one on the precise has 32 cycles horizontally and a couple of cycles vertically.
(Be aware: You see a grey band when the perform goes by means of grey = 128
which occurs twice/cycle.)
It’s possible you’ll start to note there’s a whole lot of symmetry. For all REAL
(versus IMAGINARY or COMPLEX) photos, the FT is symmetrical
concerning the origin so the first and third quadrants are the identical and the
2nd and 4th quadrants are the identical.
If the picture is symmetrical concerning the x-axis (because the cosine photos
are) 4-fold symmetry outcomes.
MAGNITUDE VS. PHASE:
Recall that the definition of the Fourier Rework is:
F(u,v) = SUM{ f(x,y)*exp(-j*2*pi*(u*x+v*y)/N) }
and
f(x,y) = SUM{ F(u,v)*exp(+j*2*pi*(u*x+v*y)/N) }
the place u = 0,1,2,...,N-1 and v = 0,1,2,...,N-1
x = 0,1,2,...,N-1 and y = 0,1,2,...,N-1
and SUM means double summation over correct
x,y or u,v ranges
Be aware that f(x,y) is the picture and is REAL, however F(u,v) (abbreviate as F)
is the FT and is, normally, COMPLEX. Usually, F is represented by
its MAGNITUDE and PHASE relatively that its REAL and IMAGINARY components, the place:
MAGNITUDE(F) = SQRT( REAL(F)^2+IMAGINARY(F)^2 ) PHASE(F) = ATAN( IMAGINARY(F)/REAL(F) )
Briefly, the MAGNITUDE tells “how a lot” of a sure frequency part
is current and the PHASE tells “the place” the frequency part is in
the picture. For example this take into account the next.
 |
Be aware that the FT photos we have a look at are simply the MAGNITUDE photos.
The pictures displayed are horizontal cosines of 8 cycles, differing
solely by the truth that one is shifted laterally from the opposite by
1/2 cycle (or by PI in part). Be aware that each have the identical FT
MAGNITUDE picture. The PHASE photos can be totally different, after all.
We typically don’t show PHASE photos as a result of most individuals who see
them shortly thereafter succomb to hallucinogenics or find yourself in a
Tibetan monastery. Nonetheless, it’s sensible to keep in mind that when
one seems at a typical FT picture and thinks about “excessive” frequency
energy and “low” frequency energy, that is solely the MAGNITUDE a part of
the FT.
By the best way, you will have heard of the FFT and puzzled if was totally different
from the FT. FFT stands for “Quick” Fourier Rework and is just a
quick algorithm for computing the Fourier Rework.
ROTATION AND EDGE EFFECTS:
Basically, rotation of the picture leads to equal rotation of its
FT. To see that that is true, we are going to take the FT of a easy cosine
and in addition the FT of a rotated model of the identical perform. The
outcomes might be seen by:
 |
At first, the outcomes appear relatively stunning. The horizontal cosine
has its regular, quite simple FT. However the rotated cosine appears to
have an FT that’s rather more sophisticated, with sturdy diagonal
parts, and in addition sturdy “plus signal” formed horizontal and
vertical parts. The query is, the place did these horizontal
and vertical parts come from? The reply is that the FT at all times
treats a picture as if it have been a part of a periodically replicated
array of an identical photos extending horizontally and vertically to
infinity. And there are sturdy edge results between the neighbors of
such a periodic array as might be seen by:
 |
Thus, what we see because the FT within the “slant” picture (decrease proper of the
picture earlier than final) is
truly the mixture of the particular FT of the cosine perform
and that attributable to the sting results of taking a look at a finite a part of
the picture. These edge results might be considerably diminished by
“windowing” the picture with a perform that slowly tapers off to
a medium grey on the edge. The consequence might be seen by:
 |
The windowed picture is proven within the higher left. Its FT is proven in
the decrease left. The non-windowed FT is proven within the higher proper
and the precise, true FT of a cosine is proven within the decrease proper.
These photos are all scaled in another way and the comparability is barely
qualitative, however it may be seen that the windowed picture FT is far
nearer to the true FT and eliminates lots of the edge results.
SOME IMAGE TRANSFORMS:
Now, with the above introduction, the easiest way to change into accustomed to
Fourier Transforms is to see a lot of photos and plenty of their FTs.
First, an fascinating pair of photos, one sharp and clear, and the opposite
blurred and noisy.
 |
There are 2 photos, goofy and the degraded goofy, with FTs beneath every.
Discover that each undergo from edge results as evidenced by the sturdy
vertical line by means of the middle. The foremost impact to note is that
within the remodel of the degraded goofy the excessive frequencies within the
horizontal course have been considerably attenuated. That is due
to the truth that the degraded picture was shaped by smoothing solely in
the horizontal course. Additionally, in the event you look rigorously
you possibly can see that the degraded goofy has a barely bigger background
noise degree at excessive frequencies. That is tough to see and maybe
not even significant as a result of the photographs are scaled in another way, but when
actually there, it’s as a result of random noise added to the degraded goofy.
Discover additionally that it’s tough to make a lot sense out of the low
frequency data. That is typical of actual life photos.
The following photos present the consequences of edges in photos:
 |
Discover the sturdy periodic part, particularly
within the vertical course for the bricks picture. Horizontal parts
seem nearer collectively within the FT. Within the blocks picture, discover a
vibrant line going to excessive frequencies perpendicular to the sturdy
edges within the picture. Anytime a picture has a strong-contrast, sharp
edge the grey values should change very quickly. It takes a lot of excessive
frequency energy to comply with such an edge so there’s often such a line
in its magnitude spectrum.
Now lets have a look at a bunch of various shapes and their FTs.
 |
Discover that the letters have fairly totally different FTs, particularly on the
decrease frequencies. The FTs additionally are inclined to have vibrant strains which are
perpendicular to strains within the unique letter. If the letter has
round segments, then so does the FT.
Now lets have a look at some collections of comparable objects:
 |
Discover the concentric ring
construction within the FT of the white pellets picture.
It is because of every particular person
pellet. That’s, if we took the FT of only one pellet, we might nonetheless
get this sample. Bear in mind, we’re trying solely on the magnitude
spectrum. The truth that there are numerous pellets and details about
precisely the place every one is is contained largely within the part. The espresso
beans have much less symmetry and are extra
variably coloured so they don’t present the identical ring construction. You
might be able to detect a faint “halo” within the espresso FT. What do you
assume that is from?
 |
Listed here are our first really normal photos. Discover there’s little or no
construction. You’ll be able to see a high left to backside proper slanting line in
the lady picture FT. It’s most likely as a result of edge between her hat
and her hair. There are additionally some small edge results in each
photos. The mandril picture seems to have extra excessive frequency
energy, most likely as a result of hair.
 |
The seafan picture has a whole lot of little holes which are about the identical
dimension and considerably randomly oriented. The dimensions of the holes is about
2 pixels large in order that corresponds to frequency parts about 1/2
method out to the utmost. The sturdy horizontal parts within the lake
picture might be as a result of tree trunk edges.
Now, right here is your first quiz. Think about a picture that’s all black
aside from a single pixel large stripe from the highest left to the underside
proper. What’s its FT? Additionally, take into account a picture that’s completely
random. That’s, each pixel is a few random worth, unbiased of all
different pixels. What’s its FT?
 |
Do you consider it? If not, you possibly can examine it your self. By the best way,
discover the one vibrant dot in the course of the noise FT picture.
Why is it there? Why does the noise FT look darkish grey?
SOME FILTERS:
Now we begin to illustrate the usage of some filters on the lady picture.
The primary is a lowpass filter. The higher left is the unique
picture. The decrease left is produced by:
fft2d 128 girlfft mag2d 128 girlmag
The decrease proper is then produced by:
fftfilt 128 low superb 50 lpgirlfft mag2d 128 lpgirlmag
Lastly, the higher proper is produced by:
ifft2d 128 lpgirl
To see the outcomes:
 |
The left facet of the picture now we have seen earlier than. Within the decrease proper,
discover how sharply the excessive frequencies are lower off by the “superb”
lowpass filter. Discover additionally that not very a lot energy is being thrown
away past the circle that’s lower off. Within the higher proper, the
reconstructed picture is clearly blurrier as a result of lack of excessive
frequencies. General distinction continues to be fairly good because of that reality
that not an excessive amount of energy was thrown away. Discover additionally that there are
apparent “ringing” artifacts within the reconstructed picture. That is
as a result of very sharp cutoff of the “superb” filter. A Butterworth
or Exponential filter with fairly low order wouldn’t trigger these.
Now we are going to do a highpass filter. The next picture is produced in
the identical method because the earlier one besides:
fftfilt 128 excessive butter 50 hpgirlfft
In different phrases, a butterworth filter of 1st order is used.
 |
Discover within the decrease proper that this filter doesn’t lower off sharply
on the 50% level because the lowpass did. Nonetheless, the middle vibrant
spot, which accounts for many of the energy within the picture, is clearly
gone. The picture within the higher proper, which seems completely black, in
reality is just not completely black. If you happen to use the colormap functionality of
“dym” to stretch the grey values from 0-20 out over your entire
vary, you possibly can see that this highpass filter has preserved the
picture data the place there are very speedy adjustments in grey degree.
Such a course of is steadily what’s desired in an edge detector.
Nonetheless, it’s not an enchancment within the picture. There are 2 issues.
First, it’s too darkish. This may be fastened by rescaling or re-contrast-
stretching the picture after filtering. That is generally executed and is
straightforward. Second, and more durable, is the truth that an excessive amount of of the low
frequency tonal data is gone.
Picture sharpening requires a “sharpening” filter or excessive frequency
emphasis filter. This type of filter preserves a few of the low
frequency data however comparatively boosts the upper frequencies.
To do such a factor, we are going to assemble our personal filter which might be
piecewise-linear. The filter might be circularly symmetrical and can
have coefficients as follows:
0 0.5 96 4.0 127 4.0
In different phrases, Fourier coefficients of frequency-distance 0 from the
origin might be multiplied by 0.5. As you go away from the origin or
zero frequency, out to frequency-distance 96, the multiplier might be
interploated between 0.5 and 4.0. From then outward, the multiplier
might be 4.0. So increased frequency coefficients are multiplied by
values better than 1.0 and decrease frequency coefficients are
multiplied by values much less thatn 1.0. The general web impact on the
picture energy is that it’s unchanged. The above values are in a file
known as “filter_coeffs”. To use the filter, the next steps are
carried out:
filttabler filter_file fftfilt 128 file filterfile mfgirlfft
The remainder of the picture is constructed as earlier than. To see the consequence:
 |
Discover the relative brightness at excessive frequencies within the decrease
proper picture. Which higher picture is sharper? Which higher picture seems
higher? Portraits are one of many few contradictions to the overall
principal that sharper is healthier.
Filtering can be used to scale back noise. It’s notably
efficient when the noise is confined to just some frequencies:
 |
The picture on the higher left is goofy with a superimposed cosine
added to it, representing noise. Within the decrease left, discover the
sturdy cosine “dots” simply to the left and proper of the origin.
Within the decrease proper, these “dots” have been eliminated ( I truly did
it with the “hint” functionality in dym ). The ensuing magnitude
file is then used with the “filter” command to filter the Fourier
coefficients. The file of coefficients is then inverse FT’d to get
the higher proper picture. The cosine “noise” is gone.
Life is just not at all times this straightforward as is proven within the subsequent instance:
 |
On this case, a grid has been positioned over goofy. The decrease left
exhibits the ensuing FT. Discover that the grid is kind of sharp so it
has a lot of excessive frequencies so its affect on the frequency area
may be very unfold out. Dym was once more used to “paint” out the grid
frequencies as a lot as attainable. The best half of the decrease proper
picture is just not painted as a result of it’s the symmetric reflection of the
left half and isn’t utilized by the filter.
YOUR ASSIGNMENT: (SHOULD YOU CHOOSE TO ACCEPT IT)
(1) Decide a picture.
(2) FFT it and discover the magnitude spectrum.
see man for fft2d and mag2d
(3) Do one thing to the spectrum or the fft.
ex: filter
fftfilt
one thing like:
cm
double
multiply by alternating +1,-1
take part solely
take magnitude solely
(4) Reconstruct a picture by inverse fft.
see man for ifft2d
(5) Put the outcomes collectively just like the above photos utilizing "group"
see man for group
(6) Clarify your outcomes (1-2 pages).
Extra credit score might be given to the creativeness of what you do than
to the correctness of your rationalization.