Python中的快速互相关方法 [英] Fast cross correlation method in Python

问题描述

我最近一直在尝试找到一种快速有效的方法，以使用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:

1. NumPy.correlate()方法，对于大型数组，它太慢了.
2. cv.MatchTemplate()方法，它似乎要快得多.

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?

顺便说一句，这是我的Python版本输出:

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.

谢谢大家！

推荐答案

您不可能比使用基于fft的相关方法快得多.

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

现在进行时间比较:

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

如果您可以处理循环相关性，则可以删除副本.时间差将随着data_length的增加而增加.

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

这篇关于Python中的快速互相关方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！