python - 更快地计算图像 (M, N) 和模板 (3, 3) 之间的平方差之和以进行模板匹配？

Question

我正在实现纹理合成算法，如概述here .为此，我需要计算差平方和，这是一个估计 template 之间误差的指标。以及 image 的不同位置.我有一个缓慢的工作实现如下:

total_weight = valid_mask.sum()  
for i in xrange(input_image.shape[0]):  
    for j in xrange(input_image.shape[1]):  
        sample = image[i:i + window, j:j + window]  
        dist = (template - sample) ** 2  
        ssd[i, j] = (dist * valid_mask).sum() / total_weight  

在这里，total_weight只是为了规范化。有些像素的强度未知，所以我使用 valid_mask掩盖他们。这个嵌套循环位于 2 个循环内部，所以这是 4 个嵌套循环，这显然是性能 killer !

有没有一种方法可以在 NumPy 或 Python 中使它更快，以替代此嵌套循环？矢量化是可能的吗？我需要处理 (3, 3) image 的一部分与 template 的 (3, 3) .

我随后将在 Cython 中实现它，所以我可以越快地使用 NumPy 来实现它，它就越好。

你可以找到完整的代码here .此处引用第 62 - 67 行。

谢谢，
正达语

Answer 1

这基本上是对 Warren Weckesser 答案的改进。要走的路显然是使用原始数组的多维窗口 View ，但您希望防止该 View 触发副本。如果你扩展你的sum((a-b)**2)，你可以把它变成sum(a**2) + sum(b**2) - 2*sum(a *b)，以及您可以使用线性代数运算符执行的先乘后归约加和运算，在性能和内存使用方面都有显着改进:

def sumsqdiff3(input_image, template):
    window_size = template.shape
    y = as_strided(input_image,
                    shape=(input_image.shape[0] - window_size[0] + 1,
                           input_image.shape[1] - window_size[1] + 1,) +
                          window_size,
                    strides=input_image.strides * 2)
    ssd = np.einsum('ijkl,kl->ij', y, template)
    ssd *= - 2
    ssd += np.einsum('ijkl, ijkl->ij', y, y)
    ssd += np.einsum('ij, ij', template, template)

    return ssd

In [288]: img = np.random.rand(500, 500)

In [289]: template = np.random.rand(3, 3)

In [290]: %timeit a = sumsqdiff2(img, template) # Warren's function
10 loops, best of 3: 59.4 ms per loop

In [291]: %timeit b = sumsqdiff3(img, template)
100 loops, best of 3: 18.2 ms per loop

In [292]: np.allclose(a, b)
Out[292]: True

我特意省略了 valid_mask 参数，因为我不完全理解您将如何使用它。原则上，只需将 template 和/或 input_image 中的相应值归零即可达到同样的效果。