在2D numpy数组的每个滚动窗口中获取最大值

Question

我有一个2D numpy数组，我想要获取每个2d滚动窗口中包含的最大值，该窗口从左到右，从上到下，滚动一行或列每次。最天真的方法是遍历所有的滚动窗口，并获得在这个滚动窗口中包含的所有值的最大值。我写下下面这个方法：

import numpy as np 
shape=(1050,300) 
window_size=(120,60) 
a = np.arange(shape[1]*shape[0]).reshape(shape[1],shape[0]) 
max_Map=np.full((shape[1]-window_size[1]+1,shape[0]-window_size[0]+1),0,dtype='uint32') 

for i in range(shape[1]-window_size[1]+1): 
    for j in range(shape[0]-window_size[0]+1): 
     window_max=np.max(a[i:i+window_size[1],j:j+window_size[0]]) 
     max_Map[i][j]=window_max 

但是，这是非常低效的，因为只有2行（或列2）之间改变各个滑，但我的代码不会考虑到连续2滚动之间的任何关联视窗。我可以想到的一个改进是针对每个滑动窗口（假定水平滚动），我将计算最左列的最大值和剩余列的最大值，并将2个值的最大值作为当前窗口的最大值。对于下一个滚动窗口，最大值将是新添加的列和以前的剩余列的最大值......但我仍然认为这不是最优化的...

我真的很感激，如果有人可以指出我正确的方向，我觉得这应该是一个很好的研究问题，但我无法找到解决方案的任何地方... 在此先感谢！

Answer 1

方法＃1使用Scipy's 2D max filter -

from scipy.ndimage.filters import maximum_filter as maxf2D 

# Store shapes of inputs 
N,M = window_size 
P,Q = a.shape 

# Use 2D max filter and slice out elements not affected by boundary conditions 
maxs = maxf2D(a, size=(M,N)) 
max_Map_Out = maxs[M//2:(M//2)+P-M+1, N//2:(N//2)+Q-N+1] 

方法2使用Scikit's 2D sliding window views - 在窗口的大小和它的使用

from skimage.util.shape import view_as_windows 

N,M = window_size 
max_Map_Out = view_as_windows(a, (M,N)).max(axis=(-2,-1)) 

注：原来的做法有窗口大小以翻转方式对齐，即的第一个形状参数沿着第二轴滑动，而第二形状参数决定窗沿着第一轴滑动的方式。对于滑动最大值过滤的其他问题可能不是这种情况，我们通常对2D数组的第一个轴使用第一个形状参数，对于第二个形状参数也使用类似的方法。因此，要解决这些情况，只需使用：M,N = window_size并按原样使用其余代码。

运行测试

途径 -

def org_app(a, window_size): 
    shape = a.shape[1], a.shape[0] 
    max_Map=np.full((shape[1]-window_size[1]+1, 
        shape[0]-window_size[0]+1),0,dtype=a.dtype) 
    for i in range(shape[1]-window_size[1]+1): 
     for j in range(shape[0]-window_size[0]+1): 
      window_max=np.max(a[i:i+window_size[1],j:j+window_size[0]]) 
      max_Map[i][j]=window_max 
    return max_Map 

def maxf2D_app(a, window_size): 
    N,M = window_size 
    P,Q = a.shape 
    maxs = maxf2D(a, size=(M,N)) 
    return maxs[M//2:(M//2)+P-M+1, N//2:(N//2)+Q-N+1] 

def view_window_app(a, window_size): 
    N,M = window_size 
    return view_as_windows(a, (M,N)).max(axis=(-2,-1)) 

时序和验证 -

In [573]: # Setup inputs 
    ...: shape=(1050,300) 
    ...: window_size=(120,60) 
    ...: a = np.arange(shape[1]*shape[0]).reshape(shape[1],shape[0]) 
    ...: 

In [574]: np.allclose(org_app(a, window_size), maxf2D_app(a, window_size)) 
Out[574]: True 

In [575]: np.allclose(org_app(a, window_size), view_window_app(a, window_size)) 
Out[575]: True 

In [576]: %timeit org_app(a, window_size) 
1 loops, best of 3: 2.11 s per loop 

In [577]: %timeit view_window_app(a, window_size) 
1 loops, best of 3: 1.14 s per loop 

In [578]: %timeit maxf2D_app(a, window_size) 
100 loops, best of 3: 3.09 ms per loop 

In [579]: 2110/3.09 # Speedup using Scipy's 2D max filter over original approach 
Out[579]: 682.8478964401295