10

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:

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

Shlomi
  • 115
  • 1
  • 2
  • 8
  • 1
    There are a number of suggestions here: http://stackoverflow.com/questions/6991471/computing-cross-correlation-function – Bitwise Sep 07 '12 at 19:22
  • I already read this post, thanks. As I said, I don't want to use the NumPy\SciPy libraries, since they offer a rather slow methods. – Shlomi Sep 07 '12 at 21:23
  • 1
    Although numpy/scipy don't always use the fastest implementation, they're not inherently slow. For example, their FFT is not as fast as some (which is why I wrote my [FFTW wrappers](https://github.com/hgomersall/pyFFTW)). The point is, don't expect a magical speed increase using OpenCV versus using the 'correct' algorithm with numpy/scipy. Numpy/scipy are pretty ubiquitous, which is a big plus. – Henry Gomersall Sep 08 '12 at 07:05

2 Answers2

22

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.

Henry Gomersall
  • 8,434
  • 3
  • 31
  • 54
3

I believe your code fails because OpenCV is expecting images as uint8 and not float32 format. You may find the cv2 python interface more intuitive to use (automatic conversion between ndarray and CV Image formats).

As for the speed of correlation, you can try using a fast fft implementation (FFTW has a python wrapper : pyfftw).

Nicolas Barbey
  • 6,639
  • 4
  • 28
  • 34
  • 1
    Just for the record and self publicity, unsatisfied with the existing wrappers for FFTW, i've written [another set](https://github.com/hgomersall/pyFFTW). They're intended to be more pythonic and less requiring of knowledge about FFTW, and are supported by a pretty comprehensive test suite (and are being actively maintained and extended, as of 10/9/12). – Henry Gomersall Sep 10 '12 at 12:04
  • Thanks ! Looks promising indeed. – Nicolas Barbey Sep 10 '12 at 12:16