FFT For Pattern Recognition
How I did Data Science without knowing.
How do you find regularities in a Picture ? Catch a wave and fast Fourier transform your way to awesome diagnostics.
What is a FFT ? Well basically its just a genius way of fast performing a Fourier transformation — saving a lot of computational time and energy. Thats was FFT actually stands for. Fast Fourier Transformation.
So FFT helps us save the planet, using it instead of an old fashioned regular Fourier Transformation. But why do we need it?
For the sake of understanding this blog we will leave the actual algorithm of a FFT to the geniuses that developed it (e.g. Cooley und Tukey) and call it a shortcut to a discrete Fourier Transformation. Now we just need to wrap our head around a Fourier Transformation.
FT’s are used literally anywhere, in the music you’re listening to, the Movies you’re watching, space exploration, Instagram filters and so on. Basically everywhere, where you have signals over time.
And what about still standing images? Well with a little conceptual workaround, even there.
What’s does a Fourier Transformation do?
Long story short: It converts a wavelike signal into its underlying frequencies. Or in simpler terms — if there is a regular pattern, a FT will find it!
Imagine an Audio record of a song. Let’s say you’re listening to Deep Purples Iconic first chords of “Smoke on the water”, the song every 16 Year old Rock enthusiast with a guitar in his hand will immediately start to play. (Well that or Smells like Teen spirit).
If you would record that chord on your mobile, it would show something like this the yellow line in the picture. What a mess, this does not look like the neat sinus like waveform you would observe in the swinging of that teenagers guitar string. That is because, a chord is playing three different Tunes simultaneously. Each tune at its specific Frequency. In the picture these are the red, blue and green lines. And if you watch closely, the guitarist actually hits at least three strings not just one. When you sum up all the amplitudes of the three lines at any point in time. You will get the Yellow line.
A FT does the exact opposite. It transforms the summated signal of the yellow line into the underlying frequencies of the red blue and yellow lines.
With that transformation the audio identification App Shazam for example could tell that the first chord of Smoke on the Water has the underlaying frequencies of 165 Hz (E) , 208 Hz (G#) and 246 Hz (B).
What the FT does, is it takes a signals wraps it around a central point and scales this wrapping over a certain time. Creating a flowerlike 2-Dimensional structure. Then calculation the center of mass of that flower-structure using complex numbers (having a real and an imaginary part). From that a vector is created, that when plotted over time, will have a peak exactly at every underlying frequencies maximum.
Of course there is a calculus approach to this as well:
I highly recommend watching this youtube Video to get a deeper understanding about the math behind a FT
How did I end up using this with pictures ?
Well back in the days of me writing my thesis in physical chemistry about a process called spinodal wrinkling. I would stand in a clean Room all day to create beautiful structures like this:
What are these? It’s a sandwich of two very thin layers, one being a kind of plastic glass and the other one a very thin metal layer. If you gently heat these up for a couple of minutes or hours the layer will start to wrinkle and form patterns.
Yes I did the opposite of anti aging — you could call it pro aging, I wanted as many wrinkles as possible. Some of them even manifested themselfs on my forehead when i tried to first understand FT.
Note that these structures are in the nanometer scale, that is 0.00000001 m. To directly measure the wavelength of these wrinkles you need a microscope with a resolution so high that it can not use light anymore but will “tap” single atoms like a blind man walking with a stick (a thing called an AFM). These measurements take up to 3 hours per picture.. if you’re lucky. Instead you can use a normal high quality light based microscope and then
- make a snapshot (big pictures)
- perform FFT on the picture (as seen in the top right corners)
- Take a slice from that FFT (bottom wave-diagramm)
- digitally measure the distance between two peaks, the height of a peak etc.
And the Data Science?
FFT are widely used in image processing and machine learning algorithms. As data scientists we are always eager to recognise patterns and derive information from that. FFT is a very powerful tool for doing so.
