FFT image comparison (theoretical)

Can anybody explain me (simplified) wha开发者_运维问答t happen if I do an image comparison with FFT? I somehow don't understand how it's possible to convert a picture into frequencies and how this is used to differentiate between two images. Via Google I can not find a simple description, which I (as non mathematic/informatic) could understand.

Any help would be very appreaciated! Thanks!

---

Alas, a good description of an FFT might involve subjects such as the calculus of complex variables and the computational theory of recursive algorithms. So a simple description may not be very accurate.

Think about sound. Looking at the waveform of the sound produced by two singers might not tell you much. The two waveforms would just be a complicated long and messy looking squiggles. But a frequency meter could quickly tell you that one person was singing way off pitch and whether they were a soprano or bass. So you might be able to determine that certain waveforms did not indicate a good match for who was singing from the frequency meter readings.

An FFT is like a big bunch of frequency meters. And each scan line of a photo is a waveform.

Around 2 centuries ago, some guy named Fourier proved that any reasonable looking waveform squiggle could be matched by an appropriate bunch of just sine waves, each at a single frequency. Other people several decades ago figured out a very clever way of very quickly calculating just which bunch of sine waves that that was. The FFT.

---

Discrete FFT transforms a (2D) matrix of let's say, pixel values, into a 2D matrix in frequency domain. You can use a library like FFTW to convert an image from the ordinary form to the spectral one. The result of your comparison depends on what you really compare.

Fourier transform works in other dimensions than 2d, as well. But you'll be interested in a 2D FFT.