# Introduction to the Fourier Rework

*by*Phil Tadros

##
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.