Saturday, September 4, 2010

Mind-Blowing Idea #1 - Fourier Transform ++

Ok, time to push up your glasses and pull out your TI-89s. It is Enginerd time. I am guessing that most of you will not take much out of this; however, this is for the more technically minded.

Computer Engineers and Electrical Engineers should remember this, and I am sure James already knows this, but this guy Jean Baptiste Joseph Fourier in 1822 proposed that every function, continuous of discontinuous, could be represented by a series of sine functions, or varying amplitudes and phases. This in its self is ridiculous and mind numbing, but we learned this all in Nelson's Signals and Systems class. That is not what this is about. If you need to refresh, go to the Wikipedia page, and here. Boiling it down, you can "transform" something from the "x," or space, domain to the "w" domain, or frequency domain.

So here is where my jaw dropped. I was in lecture for Computational Photography, and the professor was going over different ways to filter an image. He was talking about Gaussian filters, step filters, media filters... ok, they are fairly unique, bit all fairly intuitive. Then he starts talking about Fourier, I was a little apprehensive about him bringing up something that I briefly learned from Nelson, I was slightly worried that I was going to need to know how to do a transform sitting there in class. Most Picture files in essence are a large array of data points, each one corresponding to a given pixel. This would be analogous to the space domain, each value maps to each pixel. Some crazy genius decided that he was going to apply the same idea of a Fourier series on a image. Now, instead of each data point corresponding to a pixel, each data point corresponds to a sinusoidal image. The center data point would correspond to a 'flat' signal. The the horizontal axis would be a series of sinusoidal images oriented left to right. The vertical images would be a series of sinusoidal images oriented top to bottom. Each step away from the center increasing in frequency. The 'in between' data points correspond to sinusoidal images oriented in off angles and varying frequencies.
From Efros (CMU) and Seitz
 So starting with this image:

Applying a Fourier transform we get this:
Looks like a star!
To note, I shrunk the image a but as to weed out some noise, and I darkened the output to show the highlights. So first thing to notice. Very strong vertical and horizontal lines, this would be because the camera outputs images in a grid system, so there are a ton of "up and down" "Side to side" patterns. Then the center is much more populated than the outskirts, this would "low" frequency things, things that we can easily see, the whole image capturing process weeds out things that we will not notice, and discards them. Now the amazing part, notice the lines that are converging at the center. They end up representing the major "perspective" lines of the image, like the sides of the road, the light rays from the sun, the horizon.

This is a reversible process, as in if I were to perform an inverse transform I could return back to the original image. I am going to change it a bit first. I am going to take and zero out the middle of the image, there by cutting out any "low frequecies" and leaving just the "high ones." These are going to be the ones with the radical changes, or the edges:
Now I am going to do the exact opposite, and take out the "high frequencies," and I am going to get an image without any clear definition:
I only just learned about this process, I don't fully understand how to use it, or how to perfect it. I will let you all know when that comes up, I am sure it will!

I can see how this might be a very poor explanation of this process, and I also recognize that it is really late, and my mine is like that last picture, fuzzy. So let me know if you have any questions, or want more examples!

"The more you know..."

I did steal that first image from my professor's slides,  Alexei Efros 2010


  1. Now YOU are making my head hurt!!!!

  2. Donna -At least he gave the disclaimer at the start: "I am guessing that most of you will not take much out of this; however, this is for the more technically minded." I don't think he meant this entry for you or I... I will be honest... got 3 sentences into the main body of the text, perused the pics, and just read topic sentences to make sure there wasn't a paragraph later in English!!!

  3. Really this is a post for the GU Computer and Electrical Engineers, because they are all familiar with Fourier transforms... and heaven forbid, CONVOLUTION! And James, because... well James knows everything. I should note that James did comment on this, but on facebook. Here is an excerpt (I warn you, it is full of inside jokes):

    Just to let you know, I am aware of Fourier and his series...though I'd much rather prefer the World Series. Fourier's is mind-numbingly ridiculous, but it gets the job done provided you know how to integrate over the piecewise function or you can persuade sophomore engineering students taking Calc II to do it for you.... I just realized that this bit of information, while interesting for some, doesn't help me figure out whether I should go for Cookie and Cream or Chocolate ice cream at the grocery store...which I can recall was a necessary analogy for explaining some theological principle...perhaps Prof Hauck knows the answer...
    ...that is, on which kind of ice cream I should buy...
    *Hand making arc-like motion*

  4. I believe that more recent investigations of the floborebostat as it is applied to the Fourier principle have mined some very important information about how the demafachet influences the informtation that is discarded. You should look into that. I can give you links to that. Just ask.

  5. I am almost afraid to...

    Some thing about the farthfroms and the bozlofs?

  6. Gracious sakes! I'll use this post to demonstrate to my third graders the idea that being able to read and pronounce words does not correlate to comprehension/understanding the content. I look forward to the part where I finish reading, turn to them and say "I have no idea what I just read." Thank you Scott.