[PD] Cross correlation using FFT

[Jamie Bullock]

Hi,

On Thu, 6 Apr 2006 13:35:04 -0400 (EDT)
Mathieu Bouchard <matju at artengine.ca> wrote:

> 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.
> 

Please find attached, my attempt at making this into a PD patch. The array 'proper' contains a snapshot of the output of from my PD extern, which performs time domain cross-correlation, and what I believe the output should look like.

The output to the 'output' array is clearly wrong, but I'm not sure why.

The complex product subpatch is based on one of Miller's examples, I can't remember which. Not sure if the -1 multiply for complex conj (added by me) is implemented properly...


> 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.
> 

Thanks. I'll check that out.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: cross-fft.pd
Type: application/octet-stream
Size: 3221 bytes
Desc: not available
URL: <http://lists.puredata.info/pipermail/pd-list/attachments/20060406/5f52898f/attachment.obj>