[Numpy-discussion] reformulating a series of correlations as one fft, ifft pair

Paul Northug pnorthug@gmail....
Tue Apr 20 20:33:38 CDT 2010

Stéfan van der Walt <stefan <at> sun.ac.za> writes:
> I haven't checked your code in detail, but I'll mention two common
> problems with this approach in case it fits:
> 1) When convolving a KxL with an MxN array, they both need to be zero
> padded to (K+M-1)x(L+N-1).
> 2) One of the signals needs to be reversed and conjugated.
> Also have a look at scipy.signal.fftconvolve.  For real 2D images, I use:
> def fft_corr(A, B, *args, **kwargs):
>     return ss.fftconvolve(A, B[::-1, ::-1, ...], *args, **kwargs)

Thanks Stefan. 

Do you mean either reverse or conjugate, not and? I am still a little confused.
Suppose you had a 3d problem and you wanted to convolve on two axes and
correlate on the third. I can see now how you could do so by using fftconvolve
and reversing the axis you wanted to correlate as you've shown. 

But how would you implement it the other way by fft'ing and then conjugating one
of the fft pair, multiplying and ifft'ing? You can't conjugate along an axis.
Also I am not sure which one is faster, conjugating a list or reversing it.

I would like to correct another mistake I made when I said that the fft method
is much slower in this case. This is only true when the padding doesn't give you
dimensions that are split radix method-friendly or just powers of 2.

More information about the NumPy-Discussion mailing list