带有滑动 window 的 Numpy 求和真的很慢

Question

代码：

shape = np.array([6, 6])
grid = np.array([x.ravel() for x in np.meshgrid(*[np.arange(x) for i, x in enumerate(shape)], indexing='ij')]).T
slices = [tuple(slice(box[i], box[i] + 2) for i in range(len(box))) for box in grid]
score = np.zeros((7,7,3))
column = np.random.randn(36, 12) #just for example

column
>> array([[  0,   1,   2,   3, ... 425, 426, 427, 428, 429, 430, 431]])

column = column.reshape((16, 3, 3, 3))
for i, window in enumerate(slices):
        score[window] += column[i]
score
>> array([[[0.000e+00, 1.000e+00, 2.000e+00],
    [3.000e+01, 3.200e+01, 3.400e+01],
    [9.000e+01, 9.300e+01, 9.600e+01], ... 
    [8.280e+02, 8.300e+02, 8.320e+02],
    [4.290e+02, 4.300e+02, 4.310e+02]]])

它可以工作，但最后两行需要很多时间，因为它们将处于循环状态。问题是 'grid' 变量包含一个 windows 的数组。我现在不知道如何加快这个过程。

Answer 1

让我们稍微简化一下问题 - 减少维度，并删除最终大小 3 维度：

In [265]: shape = np.array([4,4])
In [266]: grid = np.array([x.ravel() for x in np.meshgrid(*[np.arange(x) for i
     ...: , x in enumerate(shape)], indexing='ij')]).T
     ...: grid = [tuple(slice(box[i], box[i] + 3) for i in range(len(box))) fo
     ...: r box in grid]
     ...: 
     ...: 
In [267]: len(grid)
Out[267]: 16
In [268]: score = np.arange(36).reshape(6,6)
In [269]: X = np.array([score[x] for x in grid]).reshape(4,4,3,3)
In [270]: X
Out[270]: 
array([[[[ 0,  1,  2],
         [ 6,  7,  8],
         [12, 13, 14]],

        [[ 1,  2,  3],
         [ 7,  8,  9],
         [13, 14, 15]],

        [[ 2,  3,  4],
         [ 8,  9, 10],
         [14, 15, 16]],

        ....
        [[21, 22, 23],
         [27, 28, 29],
         [33, 34, 35]]]])

这是一个移动 window - 一个 (3,3) 数组，上移 1，...，下移 1，等等

使用 as_strided 可以构造一个包含所有这些 windows 的数组视图，但无需实际复制值。在我能够构建等效步幅之前与 as_strided 合作过：

In [271]: score.shape
Out[271]: (6, 6)
In [272]: score.strides
Out[272]: (48, 8)
In [273]: ast = np.lib.stride_tricks.as_strided
In [274]: x=ast(score, shape=(4,4,3,3), strides=(48,8,48,8))
In [275]: np.allclose(X,x)
Out[275]: True

这可以扩展到你的(28,28,3)维度，变成求和。

生成这样的移动 windows 已在之前的 SO 问题中介绍过。它也在其中一个图像处理包中实现。

适应 3 通道图像，

In [45]: arr.shape
Out[45]: (6, 6, 3)
In [46]: arr.strides
Out[46]: (144, 24, 8)
In [47]: arr[:3,:3,0]
Out[47]: 
array([[ 0.,  1.,  2.],
       [ 6.,  7.,  8.],
       [12., 13., 14.]])

In [48]: x = ast(arr, shape=(4,4,3,3,3), strides=(144,24,144,24,8))
In [49]: x[0,0,:,:,0]
Out[49]: 
array([[ 0.,  1.,  2.],
       [ 6.,  7.,  8.],
       [12., 13., 14.]])

由于我们一次将 window 移动一个元素，因此 x 的步幅很容易从源步幅中导出。

对于 4x4 windows，只需更改形状

x = ast(arr, shape=(3,3,4,4,3), strides=(144,24,144,24,8))

在

@Divikar 建议使用 skimage

默认step=1，结果兼容：

In [55]: from skimage.util.shape import view_as_windows
In [63]: y = view_as_windows(arr,(4,4,3))
In [64]: y.shape
Out[64]: (3, 3, 1, 4, 4, 3)
In [69]: np.allclose(x,y[:,:,0])
Out[69]: True

带有滑动 window 的 Numpy 求和真的很慢

Numpy summation with sliding window is really slow

numpy

sliding-window

numpy-slicing