All geek questions in one place

Vectorized two-dimensional moving window in numpy, including edges

I understand that my question is quite similar to Numpy's Vectorized Moving Window on a 2D Array , but the answers there do not quite satisfy my needs.

Is it possible to make a vector 2D window (rotation window), which includes the so-called edge effects? What would be the most effective way to do this?

That is, I would like to move the center of the moving window along my grid so that the center can move around each grid cell. When moving along the grid fields, this operation returns only the part of the window that overlaps the grid. If the window is completely inside the grid, the full window is returned. For example, if I have a grid:

array([[1,2,3,4],
       [2,3,4,5],
       [3,4,5,6],
       [4,5,6,7]])

... and I want to try every point in this grid using a window 3x3centered at that point, the operation should return a series of arrays or, ideally, a series of views in the original array as follows:

array([[1,2],    array([[1,2,3],    array([[2,3,4],    array([[3,4],
       [2,3]])          [2,3,4]])          [3,4,5]])          [4,5]])

array([[1,2],    array([[1,2,3],    array([[2,3,4],    array([[3,4],
       [2,3],           [2,3,4],           [3,4,5],           [4,5],
       [3,4]])          [3,4,5]])          [4,5,6]])          [5,6]])

array([[2,3],    array([[2,3,4],    array([[3,4,5],    array([[4,5],
       [3,4],           [3,4,5],           [4,5,6],           [5,6],
       [4,5]])          [4,5,6]])          [5,6,7]])          [6,7]])

array([[3,4],    array([[3,4,5],    array([[4,5,6],    array([[5,6],
       [4,5]])          [4,5,6]])          [5,6,7]])          [6,7]])

Since I need to perform this operation many times, speed is important, and a vector operation would be the ideal solution.

+4
source share
2 answers

You can define the function that the generator gives and use it. The window will be half the shape you want to divide by 2, and the trick is to simply index the array along this window when moving along rows and columns.

def window(arr, shape=(3, 3)):
    # Find row and column window sizes
    r_win = np.floor(shape[0] / 2).astype(int)
    c_win = np.floor(shape[1] / 2).astype(int)
    x, y = arr.shape
     for i in range(x):
         xmin = max(0, i - r_win)
         xmax = min(x, i + r_win + 1)
         for j in range(y):
             ymin = max(0, j - c_win)
             ymax = min(y, j + c_win + 1)
             yield arr[xmin:xmax, ymin:ymax]

You can use this function as follows:

arr = np.array([[1,2,3,4],
               [2,3,4,5],
               [3,4,5,6],
               [4,5,6,7]])
gen = window(arr)
next(gen)
array([[1, 2],
       [2, 3]])

Passing through the generator produces all the windows in your example.

, , , . @PaulPanzer, np.lib.stride_tricks.as_strided, . - :

def rolling_window(a, shape):
    s = (a.shape[0] - shape[0] + 1,) + (a.shape[1] - shape[1] + 1,) + shape
    strides = a.strides + a.strides
    return np.lib.stride_tricks.as_strided(a, shape=s, strides=strides)

def window2(arr, shape=(3, 3)):
    r_extra = np.floor(shape[0] / 2).astype(int)
    c_extra = np.floor(shape[1] / 2).astype(int)
    out = np.empty((arr.shape[0] + 2 * r_extra, arr.shape[1] + 2 * c_extra))
    out[:] = np.nan
    out[r_extra:-r_extra, c_extra:-c_extra] = arr
    view = rolling_window(out, shape)
    return view

window2(arr, (3,3))
array([[[[ nan,  nan,  nan],
         [ nan,   1.,   2.],
         [ nan,   2.,   3.]],

        [[ nan,  nan,  nan],
         [  1.,   2.,   3.],
         [  2.,   3.,   4.]],

        [[ nan,  nan,  nan],
         [  2.,   3.,   4.],
         [  3.,   4.,   5.]],

        [[ nan,  nan,  nan],
         [  3.,   4.,  nan],
         [  4.,   5.,  nan]]],


       [[[ nan,   1.,   2.],
         [ nan,   2.,   3.],
         [ nan,   3.,   4.]],

        [[  1.,   2.,   3.],
         [  2.,   3.,   4.],
         [  3.,   4.,   5.]],

        [[  2.,   3.,   4.],
         [  3.,   4.,   5.],
         [  4.,   5.,   6.]],

        [[  3.,   4.,  nan],
         [  4.,   5.,  nan],
         [  5.,   6.,  nan]]],


       [[[ nan,   2.,   3.],
         [ nan,   3.,   4.],
         [ nan,   4.,   5.]],

        [[  2.,   3.,   4.],
         [  3.,   4.,   5.],
         [  4.,   5.,   6.]],

        [[  3.,   4.,   5.],
         [  4.,   5.,   6.],
         [  5.,   6.,   7.]],

        [[  4.,   5.,  nan],
         [  5.,   6.,  nan],
         [  6.,   7.,  nan]]],


       [[[ nan,   3.,   4.],
         [ nan,   4.,   5.],
         [ nan,  nan,  nan]],

        [[  3.,   4.,   5.],
         [  4.,   5.,   6.],
         [ nan,  nan,  nan]],

        [[  4.,   5.,   6.],
         [  5.,   6.,   7.],
         [ nan,  nan,  nan]],

        [[  5.,   6.,  nan],
         [  6.,   7.,  nan],
         [ nan,  nan,  nan]]]])

np.nan, . 3 , , window, , , .

+3

, , , , (- ?)

, , . +/- . Python Numpy, numba.

def mw_mean(in_arr,out_arr,x_win,y_win):
    xn,yn = in_arr.shape
    for x in range(xn):
        xmin = max([0,x - x_win])
        xmax = min([xn, x + x_win + 1])
        for y in range(yn):
            ymin = max([0,y - y_win])
            ymax = min([yn, y + y_win + 1])

            out_arr[x,y] = in_arr[xmin:xmax, ymin:ymax].mean()
    return out_arr



@jit("i4[:,:](i4[:,:],i4[:,:],i4,i4)", nopython = True)
def mw_mean_numba(in_arr,out_arr,x_win,y_win):
    xn,yn = in_arr.shape
    for x in range(xn):
        xmin = max(0,x - x_win)
        xmax = min(xn, x + x_win + 1)
        for y in range(yn):
            ymin = max(0,y - y_win)
            ymax = min(yn, y + y_win + 1)

            out_arr[x,y] = in_arr[xmin:xmax, ymin:ymax].mean()
    return out_arr

- (100x100 1000x1000):

a = np.array([[1,2,3,4], [2,3,4,5], [3,4,5,6], [4,5,6,7]])
b = np.random.randint(1,7, size = (100,100))
c = np.random.randint(1,7, size = (1000,1000))

aout,bout,cout = np.zeros_like(a),np.zeros_like(b),np.zeros_like(c)

x_win = 1
y_win = 1

Runtimes :

%timeit mw_mean(a,aout,x_win,y_win)
1000 loops, best of 3: 225 µs per loop

%timeit mw_mean(b,bout,x_win,y_win)
10 loops, best of 3: 137 ms per loop

%timeit mw_mean(c,cout,x_win,y_win)
1 loop, best of 3: 14.1 s per loop

Runtimes :

%timeit mw_mean_numba(a,aout,x_win,y_win)
1000000 loops, best of 3: 1.22 µs per loop

%timeit mw_mean_numba(b,bout,x_win,y_win)
1000 loops, best of 3: 550 µs per loop

%timeit mw_mean_numba(c,cout,x_win,y_win)
10 loops, best of 3: 55.1 ms per loop

: , , , - . .

+5

Source: https://habr.com/ru/post/1692061/

More articles:


All Articles