Extract blocks or patches from NumPy Array

Question

I have a 2-d numpy array as follows:

a = np.array([[1,5,9,13],
              [2,6,10,14],
              [3,7,11,15],
              [4,8,12,16]]

I want to extract it into patches of 2 by 2 sizes with out repeating the elements.

The answer should exactly be the same. This can be 3-d array or list with the same order of elements as below:

[[[1,5],
 [2,6]],   

 [[3,7],
 [4,8]],

 [[9,13],
 [10,14]],

 [[11,15],
 [12,16]]]

How can do it easily?

In my real problem the size of a is (36, 72). I can not do it one by one. I want programmatic way of doing it.

Answer 1

Using scikit-image:

import numpy as np
from skimage.util import view_as_blocks

a = np.array([[1,5,9,13],
              [2,6,10,14],
              [3,7,11,15],
              [4,8,12,16]])

print(view_as_blocks(a, (2, 2)))

Answer 2

You can achieve it with a combination of np.reshape and np.swapaxes like so -

def extract_blocks(a, blocksize, keep_as_view=False):
    M,N = a.shape
    b0, b1 = blocksize
    if keep_as_view==0:
        return a.reshape(M//b0,b0,N//b1,b1).swapaxes(1,2).reshape(-1,b0,b1)
    else:
        return a.reshape(M//b0,b0,N//b1,b1).swapaxes(1,2)

As can be seen there are two ways to use it - With keep_as_view flag turned off (default one) or on. With keep_as_view = False, we are reshaping the swapped-axes to a final output of 3D, while with keep_as_view = True, we will keep it 4D and that will be a view into the input array and hence, virtually free on runtime. We will verify it with a sample case run later on.

Sample cases

Let's use a sample input array, like so -

In [94]: a
Out[94]: 
array([[2, 2, 6, 1, 3, 6],
       [1, 0, 1, 0, 0, 3],
       [4, 0, 0, 4, 1, 7],
       [3, 2, 4, 7, 2, 4],
       [8, 0, 7, 3, 4, 6],
       [1, 5, 6, 2, 1, 8]])

Now, let's use some block-sizes for testing. Let's use a blocksize of (2,3) with the view-flag turned off and on -

In [95]: extract_blocks(a, (2,3)) # Blocksize : (2,3)
Out[95]: 
array([[[2, 2, 6],
        [1, 0, 1]],

       [[1, 3, 6],
        [0, 0, 3]],

       [[4, 0, 0],
        [3, 2, 4]],

       [[4, 1, 7],
        [7, 2, 4]],

       [[8, 0, 7],
        [1, 5, 6]],

       [[3, 4, 6],
        [2, 1, 8]]])

In [48]: extract_blocks(a, (2,3), keep_as_view=True)
Out[48]: 
array([[[[2, 2, 6],
         [1, 0, 1]],

        [[1, 3, 6],
         [0, 0, 3]]],


       [[[4, 0, 0],
         [3, 2, 4]],

        [[4, 1, 7],
         [7, 2, 4]]],


       [[[8, 0, 7],
         [1, 5, 6]],

        [[3, 4, 6],
         [2, 1, 8]]]])

Verify view with keep_as_view=True

In [20]: np.shares_memory(a, extract_blocks(a, (2,3), keep_as_view=True))
Out[20]: True

Let's check out performance on a large array and verify the virtually free runtime claim as discussed earlier -

In [42]: a = np.random.rand(2000,3000)

In [43]: %timeit extract_blocks(a, (2,3), keep_as_view=True)
1000000 loops, best of 3: 801 ns per loop

In [44]: %timeit extract_blocks(a, (2,3), keep_as_view=False)
10 loops, best of 3: 29.1 ms per loop