[SciPy-user] Autocorrelation

Stefan van der Walt stefan at sun.ac.za
Tue Aug 15 12:44:24 CDT 2006

On Tue, Aug 15, 2006 at 05:18:43PM +0100, Pierre Barbier de Reuille wrote:
> David Huard wrote:
> > Hi,
> > I haven't seen in Scipy a function to compute the autocorrelation of a
> > time series. Is there one I missed ?
> >
> Isn't numpy.correlate enough ? For autocorrelation you can do something
> like:
>
> r = numpy.correlate(x, x)

These functions are useful when working with short 1-dimensional
signals, but for larger images they are agonisingly slow.  A way
around the problem is to calculate the correlation using the FFT, i.e.

def fft_correlate(A,B,*args,**kwargs):
return S.signal.fftconvolve(A,B[::-1,::-1,...],*args,**kwargs)

On my computer, I benchmarked these methods with different length
signals.  See the attached graph and script.  You'll notice that the
FFT execution time jumps around bit -- I know that it can be
calculated especially quickly for lengths that are powers of two,
maybe this has something to do with that.  Can someone on the list
enlighten me?

Either way, your mileage may vary.  Some say that this method is
somewhat less accurate, and that it uses more memory.  All I know is
that it finishes calculating before the end of time.

Regards
Stéfan

-------------- next part --------------
A non-text attachment was scrubbed...
Name: corr.py
Type: text/x-python
Size: 643 bytes
Desc: not available
Url : http://projects.scipy.org/pipermail/scipy-user/attachments/20060815/101bb25a/attachment-0001.py
-------------- next part --------------
A non-text attachment was scrubbed...
Name: bench_corr.png
Type: image/png
Size: 45581 bytes
Desc: not available
Url : http://projects.scipy.org/pipermail/scipy-user/attachments/20060815/101bb25a/attachment-0001.png