[PD] Cross correlation using FFT

[Mathieu Bouchard]

On Mon, 3 Apr 2006, Jamie Bullock wrote:

I'll summarize what we said on the #dataflow chatline:

> 1. Zero pad the signal vectors to twice the vector size

This is to prevent the result from wrapping around.

> 2. Take their ffts: fft(x) fft(y)
> 3. Take the complex conjugate of fft(x) and multiply this by fft(y)

> Whatever I try doesn't seem to give the correct output. In particular -
> I am unsure of step 3 above. Can anyone give some clarification or an
> example patch.

there are several ways to do steps 2 and 3, because there are several
identities about fft. especially, fft(fft(signal)) = reverse(signal) *
blocksize. Note that reverse() here keeps sample t=0 at the same place and
only reverses the rest of the block.

Then fft(fft(fft(fft(signal)))) = signal * blocksize^2

Then ifft is like fft of the reversal, and also like the conj of the fft.

Pd now can do FFT on pictures, using GridFlow's [#fft]. I mention it in 
case it helps you visualizing what's going on. You will need to install 
FFTW.

 _ _ __ ___ _____ ________ _____________ _____________________ ...
| Mathieu Bouchard - tél:+1.514.383.3801 - http://artengine.ca/matju
| Freelance Digital Arts Engineer, Montréal QC Canada