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:
NumPy.correlate()
method, which is too slow when it comes to large arrays.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!
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.