Fourier and For me

(Warning: this post contains a lot of animated GIFs)
(Warning Addendum: This will consume a lot of Data/Bandwidth)
$Why? \, because \, I \, can$

As promised from last post, here are some test patterns and their Fourier Transforms.
As the patterns are tweaked, their FT's also change.
I'm not really good at explaining so, I'll let the images speak for themselves.

Is it moving yet? 

This is a 11.1 MB upload so let it load for a bit

$Unless \, your \, internet \, has \, transcended \, Philippine \, standards$

Now, what happens if we combine some of these patterns, say two sinusoids?
As a Physics major I should know the property of Fourier Transform that

$\mathcal{F} \{ f(x)g(x) \} = F(k)*G(k)$

where

$F(k) = \mathcal{F}\{ f(x) \} $
  

$G(k) = \mathcal{F}\{ g(x) \} $

Simply put, the FT of the product of two functions is the convolution of their separate FT's.

Like so

 

Woah! Hold on there. What is this convolution? Well... umm...

I'm not sure how mathematicians define convolution (a quick Google search is not helping and I don't want to search for longer than quick.) But in my own words I'd say convolution is like an element-wise operation where each element of A is multiplied to the whole of B.

 That's not helping. English please. Uh...... 

Okay so I have two images A and B. Now imagine all white dots on A suddenly looks like B.

$BOOM \, CONVOLUTION$ 

Well I hope this makes things clearer

The thing here is that when the points are spaced too closed to each other, the resulting convolution pattern will have overlapping images of the sample pattern.

---

In the previous entry, we found out that using Fourier Transform we can find certain features in an image. That's quite useful for image recognition or just plain cheating in Finding Waldo or those I Spy-like games.

What else can we use FT for then?
Filtering out noise, that's what.

Have you ever put your thumb mark on something and it looked too light. Or maybe it was too dark and smudgy? Eitherway it just looked kinda wrong.
Then FT is fourier. $Josh \, STAHP$

So here's a thumbmark

Looks a bit too light, right? And look at all those white spots

Let's look at the FT of this fingerprint

$Looks \, like \, a \, galaxy. \, COOL!$

What does a fingerprint look like? That's right, radially propagating sin waves (where did that come from? Ansatz baybeh.) From the samples in the first part, we can deduce that the FT of the clean fingerprint ridges look like a convolution of many sinusoidal FT's. That would be the nebula-like ring of our 'galaxy'.

Now lets remove everything else

(except the middle, let's keep some of that)

(credits to Kit Guial for pointing out that a small fraction instead of 0's in the middle is better)

Now let's transform it back into an image

(after hours of tweaking the mask parameters)

 Well?

That looks worse! 

Hold your horses, judging cowboy. It's just a contrast issue. Let me fix that for you.

 

Better?

Cleaning in Fourier space does not make it instantly better. It just removes the noisy elements.

Now we can get a much cleaner binarized image.

---

Now lets try it on a picture $FROM \, THE \, MOON$.

(read that again in an ominous echoing voice)

(better? alright we can move on)

 

See those horizontal lines? Annoying.

Horizontal lines? $EZ$ Those are just dots along the y-axis.

I'm not even gonna post the FT and mask images. 

I basically just made two black vertical line along the middle of the Fourier transform before turning it back into an image. (Making sure there is a gap in the center.) I tried to vary the length of the line as well as the size of the gap in the middle but there is not much difference observed.

Ahh much better.

---

Now let's see if we can separate a painting from its canvas

Behold an amazing 100% authentic Daria painting

I know some of my classmates drew masks manually but I felt lazy doing that.

So I created masks using varying thresholds.

In fact I'm getting a bit lazy in writing as of now.

So again I'll let the pictures talk for themselves.

As I reduce the threshold, more of the "canvas" features are removed. At the same time more of the painting features are removed. So in the end we have to compromise between canvas noise and missing painting.

Personally my favorite is using a threshold value of 0.57, which looks like this

Taking the FT of the color-inverted mask we get

Surprise! It's the canvas pattern.

Finally, since this is a painting, it does not do justice if we do not return the color.

I split the original image into its R,G,B channels using GIMP.
I applied the same technique on the three channels to remove the canvas pattern.

The final colored image was then obtained by storing the three cleaned channels into an RGB image.

And voila

Here is the restored image using threshold value = 0.57

along with the original for comparison

---

Hooboy. That's finally over.

I found this topic to be really cool.

So much so that I ended up playing with it too much.

So yeah... 

Spongebob won't be returning because this one took me a lot more than 5 hours of "blogging" (that includes generating more pretty images).

I would like to thank Kit again for the fingerprint advice,

and Roland for tips on general array handling in Scilab. (I still hate you scilab)

Overall I am again, giving myself a solid 11/10! $wagoom$

Fourier Information

---

($Again \, Good \, Job \, Roland \, For \, The \, Title$)

Now now, what have we here?
Fourier Transform! And lots of it...

Do I know what Fourier Transform is?
Yes, it's been discussed in many a physics class for at least three years now.
Yes, I know the equation (For 1D at least)

$\mathcal{F}(k) = \int_{-\infty}^{+\infty} f(x) e^{2\pi ikx} dx$
$Yeahp \, looks \, legit$
Yes, I kinda know what it means. Converts a signal into frequency space, right? $Right?$
How does it actually work? I have no idea. Don't even ask me about DFT or FFT.

---

Well to hell with the theory (for now). $Import \, FFT \, = \, Problem \, Solved$

The first thing we did was to take the Fourier Transform of a circular aperture.
As an aspiring physicist I know that this should look like an Airy Pattern. Why? $NO \, IDEA$

And lo and behold

That doesn't look right...

Turns out directly converting a matrix to uint8 without normalizing to 255 in Scilab causes much information to be lost.

There we go

---

That looks cool. Physicists sure get to see cool stuff.
But wait, we also see this in high school Biology!
Where you ask?
Well lenses actually perform Fourier Transform on images.
If you tried adjusting a microscope for yourself this might look familiar.

What is that?

Oh look it's a cute little bacterium

$Or  \, a \, microscopic \, mouse$

Mathematically (computationally?), this is the result of convolving an image with an aperture of different sizes.

Physcially, this can be a result of varying the object distance from the lens.

---

What else can we use FFT for? Finding stuff!
Technically, multiplying the FT of an image and the conjugate of the FT of another would show a correlation between the two images.
If we see a high correlation then we can say that the two images share the same features.

Now if we limit the second image to a small feature say the letter 'A', then we can find where the letter 'A's are in an image.

Like this

 

$Magic$

The high correlation areas don't really look obvious but by applying a threshold we can be more certain where a feature is present and where it isn't.

Now suppose we have a movie poster, say The Avengers

http://www.pngall.com/avengers-png

Now I want to know if Captain America is in the movie. What would Cap always have? That's right his shield. 

Lets try to find Cap using the same method as 'A' 

Is that bright spot Cap?

$Yeahp  \, there \,  he \, is.$

---

So we can now find features in our images. What else can we do with FT?
It can also be used for edge detection.
Before, if you ask me how to find edges in a picture, I would say that you have to check each pixel then compare the pixel value to its neighbors'.
Thats the brute force method. Apparently, using convolution in Fourier space does the same.
By convolving an image with a 3x3 'edge' pattern, we are basically finding any 3x3 pixels in the image that resembles the edge pattern.
For this part I convolved a test image with four types of patterns.

I used the same image of Sunken garden extracted from Google Maps that I used in the previous activity.
Using different patterns result in extracted edges that look similar to the pattern
i.e. horizontal pattern detects horizontal edges better and vertical pattern detects vertical edges better. ...
The built-in edge function from SIVP module of Scilab produced similar results to that of the diagonal pattern.
Meanwhile, using a center dot pattern produced the best results.

Here I applied the same method to "microsoft"
The built-in edge from the Windows 10 package yields a very different result.

Taking the edge of microsoft using FT

HAHAHAHAHA. Get it? Get it?
$I'm \, gonna \, die \, alone$

---

Well this activity was fun. I'm getting quite used to Scilab now.
Still don't know how to define functions properly though.
My working directory looks so disorganized. And I had to write separate codes for each part.

I did not include some test patterns and their FT's in this post. They will be making an appearance in the next activity.

For this activity, I'm gonna give myself a solid 11/10! $Well \, done \, you$

Spongebob makes a return