Python中的快速互相关方法

Question

最近我一直在尝试用Python语言快速高效地执行两个数组的交叉相关检查。经过一些阅读，我找到了以下两个选项：

1. NumPy.correlate（）方法，在处理大型数组时速度太慢。
2. cv.MatchTemplate()方法似乎更快。

出于明显的原因，我选择了第二个选项。我尝试执行以下代码：

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)

尽管这段代码看起来很简单，但它会抛出以下错误：

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

经过几个小时令人沮丧的尝试，我仍然卡住了！有没有人有什么建议？

顺便说一下，这是我的Python版本输出：

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.

谢谢大家！

- Shlomi

---

这里有一些建议：https://dev59.com/zWw05IYBdhLWcg3w11W0 - Bitwise

我已经阅读了这篇文章，谢谢。正如我所说，我不想使用NumPy\SciPy库，因为它们提供的方法相对较慢。 - Shlomi

虽然numpy/scipy并不总是使用最快的实现方式，但它们本身并不慢。例如，它们的FFT并不像某些库那样快（这就是我编写FFTW包装器的原因）。关键是，不要期望使用OpenCV比使用numpy/scipy的“正确”算法会有神奇的速度提升。Numpy/scipy非常普遍，这是一个很大的优点。 - Henry Gomersall

Answer 1

使用基于FFT的相关方法，你很难达到更快的速度。

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的增加，时间差也会增加。

- Henry Gomersall

---

嗨，亨利，谢谢你的回答！我一定会尝试那个方法。不过，我也想尝试一下CV库的方法。你有任何关于这个错误的原因的想法吗？ - Shlomi

不知道 - 我没有使用过OpenCV。 - Henry Gomersall

Answer 2

我认为你的代码失败是因为OpenCV期望图像是uint8格式，而不是float32格式。您可以尝试使用cv2 Python接口，它可以在ndarray和CV Image格式之间自动进行转换，这可能更加直观易用。

至于相关性速度，您可以尝试使用快速的fft实现（FFTW有一个Python包装器：pyfftw）。

- Nicolas Barbey

---

仅供记录和自我宣传，对于现有的FFTW包装器不满意，我编写了另一套。它们旨在更符合Python风格，不需要关于FFTW的知识，并且由一个相当全面的测试套件支持（截至2012年10月9日正在积极维护和扩展）。 - Henry Gomersall

谢谢！看起来确实很有前途。 - Nicolas Barbey