在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