# Fast cross correlation method in Python

I have been recently trying to find a fast and efficient way to perform cross correlation check between two arrays using Python language. After some reading, I found these two options:

- The NumPy.correlate() method, which is too slow when it comes to large arrays.
- The cv.MatchTemplate() method, which seems to be much faster.

For obvious reasons, I chose the second option. I tried to execute the following code:

import scipy import cv image = cv.fromarray(scipy.float32(scipy.asarray([1,2,2,1])),allowND=True) template = cv.fromarray(scipy.float32(scipy.asarray([2,2])),allowND=True) result = cv.fromarray(scipy.float32(scipy.asarray([0,0,0])),allowND=True) cv.MatchTemplate(image,template,result,cv.CV_TM_CCORR)

Even though this code suppose to be very simple, it throws the next error:

OpenCV Error: Bad flag (parameter or structure field) (Unrecognized or unsupported array type) in cvGetMat, file /builddir/build/BUILD/OpenCV-2.1.0/src/cxcore/cxarray.cpp, line 2476 Traceback (most recent call last): File "<stdin>", line 1, in <module> cv.error: Unrecognized or unsupported array type

After a few hours of frustrating tries, I am still stuck! Does anybody have any suggestion?

BTW, this is my Python version output:

Python 2.7 (r27:82500, Sep 16 2010, 18:03:06) [GCC 4.5.1 20100907 (Red Hat 4.5.1-3)] on linux2 Type "help", "copyright", "credits" or "license" for more information.

Thank you all!

## Answers

You're unlikely to get much faster than using an fft based correlation method.

import numpy from scipy import signal data_length = 8192 a = numpy.random.randn(data_length) b = numpy.zeros(data_length * 2) b[data_length/2:data_length/2+data_length] = a # This works for data_length being even # Do an array flipped convolution, which is a correlation. c = signal.fftconvolve(b, a[::-1], mode='valid') # Use numpy.correlate for comparison d = numpy.correlate(a, a, mode='same') # c will be exactly the same as d, except for the last sample (which # completes the symmetry) numpy.allclose(c[:-1], d) # Should be True

Now for a time comparison:

In [12]: timeit b[data_length/2:data_length/2+data_length] = a; c = signal.fftconvolve(b, a[::-1], mode='valid') 100 loops, best of 3: 4.67 ms per loop In [13]: timeit d = numpy.correlate(a, a, mode='same') 10 loops, best of 3: 69.9 ms per loop

If you can cope with a circular correlation, you can remove the copy. The time difference will increase as data_length increases.