NumPy 模板匹配 SQDIFF 与“滑动 window_view”

Question

SQDIFF 定义为 openCV definition。（我相信他们省略了频道）

初级numpyPython应该是

A = np.arange(27, dtype=np.float32)
A = A.reshape(3,3,3) # The "image"
B = np.ones([2, 2, 3], dtype=np.float32) # window
rw, rh = A.shape[0] - B.shape[0] + 1, A.shape[1] - B.shape[1] + 1 # End result size
result = np.zeros([rw, rh])
for i in range(rw):
    for j in range(rh):
        w = A[i:i + B.shape[0], j:j + B.shape[1]]
        res =  B - w
        result[i, j] = np.sum(
            res ** 2
        )
cv_result = cv.matchTemplate(A, B, cv.TM_SQDIFF) # this result is the same as the simple for loops
assert np.allclose(cv_result, result)

这是一个相对较慢的解决方案。我读过 sliding_window_view 但无法正确理解。

# This will fail with these large arrays but is ok for smaller ones
A = np.random.rand(1028, 1232, 3).astype(np.float32)
B = np.random.rand(248, 249, 3).astype(np.float32)
locations = np.lib.stride_tricks.sliding_window_view(A, B.shape)
sqdiff = np.sum((B - locations) ** 2, axis=(-1,-2, -3, -4)) # This will fail with normal sized images

将失败并返回 MemoryError，即使结果很容易记住。我怎样才能用这种更快的方式产生与 cv2.matchTemplate 函数相似的结果？

Answer 1

相当于

其中 'star' 操作是互相关，1_[m, n] 是 window 模板的大小，而 1_[k, l] 是 window 与图片大小。

您可以使用 'scipy.signal.correlate' 计算互相关项，并通过在方差图中查找局部最小值来找到匹配项。
您可能也想进行一些非最小值抑制。此解决方案需要的存储内存要少几个数量级。

如需更多帮助，请 post 具有对算法有效的图像和模板的可重现示例。使用噪声将导致无意义的输出。

Answer 2

作为最后的手段，您可以分块执行计算，而不是“一次全部”计算。

np.lib.stride_tricks.sliding_window_view returns 数据的视图，因此不会消耗大量 RAM。

表达式B - locations不能使用视图，需要RAM来存储一个float元素的形状为(781, 984, 1, 248, 249, 3)的数组。

用于存储 B - locations 的总 RAM 为 781*984*1*248*249*3*4 = 569,479,908,096 字节。

为了避免一次性在 RAM 中存储 B - locations，当“tile”计算需要较少的 RAM 时，我们可以在 tiles 中计算 sqdiff。

一个简单的图块划分是使用每一行作为一个图块 - 遍历 sqdiff 的行，并逐行计算输出。

示例：

sqdiff = np.zeros((locations.shape[0], locations.shape[1]), np.float32)  # Allocate an array for storing the result.

# Compute sqdiff row by row instead of computing all at once.
for i in range(sqdiff.shape[0]):
    sqdiff[i, :] = np.sum((B - locations[i, :, :, :, :, :]) ** 2, axis=(-1, -2, -3, -4))

可执行代码示例：

import numpy as np
import cv2

A = np.random.rand(1028, 1232, 3).astype(np.float32)
B = np.random.rand(248, 249, 3).astype(np.float32)
locations = np.lib.stride_tricks.sliding_window_view(A, B.shape)

cv_result = cv2.matchTemplate(A, B, cv2.TM_SQDIFF)  # this result is the same as the simple for loops

#sqdiff = np.sum((B - locations) ** 2, axis=(-1, -2, -3, -4))  # This will fail with normal sized images

sqdiff = np.zeros((locations.shape[0], locations.shape[1]), np.float32)  # Allocate an array for storing the result.

# Compute sqdiff row by row instead of computing all at once.
for i in range(sqdiff.shape[0]):
    sqdiff[i, :] = np.sum((B - locations[i, :, :, :, :, :]) ** 2, axis=(-1, -2, -3, -4))

assert np.allclose(cv_result, sqdiff)

我知道解决方案有点令人失望...但这是我能找到的唯一通用解决方案。

NumPy 模板匹配 SQDIFF 与“滑动 window_view”

NumPy template matching SQDIFF with `sliding window_view`

python

numpy

opencv

stride