Fourier Analysis

A form of analysis to turn time domain inputs into frequency domain outputs. Used for frequency analysis of sound.

However, Fourier Analysis is also used on pictures that have x and y components, but no time components. What's up with this? I ask a man who uses Fourier analysis for testing about it and he is clueless.

The confusion arises from the above definition. It's not specifically about interconverting between time and frequency domains, it's about going from any well-behaved space into its corresponding Fourier dual space. Keith's explanation below tries to help make intuitive sense of what "spatial frequency" means, but even more fundamentally, the topic is just about converting from one set of units to another, like going from X, Y rectangular coordinate space into R, THETA coordinate space. It's just that in this case, rather than being able to convert from one point in the first coordinate system into a corresponding point in the other, instead the new point depends on the values of the entire function in the first domain. That's what "transform" means.

Imagine you had a one-dimensional image, say a very long dashed line, alternate inches dark and light, let's say. Can you see that such a thing is very similar to a square-wave sound signal? The amount of light emitted from a point on the line is like the amplitude of the sound wave at some point in time. Now, extend that analogy to a one-dimensional image who's brightness varies sinusoidally along its length. That's like sound wave with a unique frequency, like a fundamental or harmonic, right? Now, just as, in the case of sound, you can transform a wave into a bunch of sinusoids of various frequencies and amplitudes combined together via Fourier analysis, you can also transform a one-dimensional image into a bunch of sinusoidal images of various spatial frequencies (say, 250 cycles per inch, rather than cycles per second) and amplitudes combined together. A similar argument applies in two dimensions.

Now, to produce a clean square wave, let's say, by summing sinusoids requires an infinite sum. Suppose we had the square wave signal produced directly (using an astable circuit, let's say) and we sent it through a low-pass filter, attenuating the higher frequencies. By Fourier analysis, we can show that this would have the effect of softening the shoulders of the square wave. Analogue synthesizers often work this way, building complex waveforms by filtering out part of the frequency spectrum of a square or saw-tooth wave. A perfect square wave would contain the fundamental and all its odd harmonics to infinity, a saw-tooth all the even ones, so suitable filtering can produce very complex waveforms. Hammond organs go the other way, building up complex wave forms from sinusoids generated at different frequencies by the tone-wheels. Since few harmonics are available for a given fundamental in the Hammond system, the range of waveforms that can be created is smaller.

Similarly, if we took a very high contrast image (like our spatial square wave dashed line) and filtered out the high spatial frequencies, it would become less sharp as the spatial square wave became rounded. This effect can also be used to clean an image up: if an image contains, say, scratches that lie predominantly in one direction, these will show up as spikes in its Fourier transform. If those spikes are attenuated and the inverse transform applied the image will be a little less sharp over all, but will also not have the scratches.

The 2-d Fourier transform of an image can be calculated, or generated with a fairly simple optical system. If the image is illuminated with coherent light (for convenience), the focal plane of a simple convex lens will hold the Fourier transform of the image. Certain parts of the spatial spectrum can be attenuated just by placing a transparent screen with suitable patterns marked on it in the focal plane. Another lens will perform the inverse transformation. -- KeithBraithwaite

Right, since FT is easily done with lenses, FT has been used to do fingerprint matching long before fast computers were available.

Actually, old Fourier himself used this stuff to solve heat-transfer problems. Fourier Analysis is very, very cool. Infinitely cooler than structured analysis or object oriented analysis. -- AndrewQueisser

Yes. time domain <-> frequency domain is just one special case of what Fourier methods do. Quantum mechanics is packed with them, for instance.

http://www-stat.wharton.upenn.edu/~bob/stat540/class24.html
- includes some very compact implementations of FFT.
http://www.fftw.org
- Great product; fast FFTs and DFTs of arbitrary length; GPLed.
- Recently released version 3, which is a big improvement.
- Targeted at linux, with great configuration options, but probably easily usable by any C++ compiler.
http://www.gnu.org/software/gsl/manual/gsl-ref_15.html#SEC237
- GnuScientificLibrary? has FFT functions
http://math.nist.gov/~BMiller/java/#FFT
- jnt.FFT is a FFT library in Java