Fast Way to slice image into overlapping patches and merge patches to image

An efficient way to “patchify” an array, that is, to get an array of windows to the original array is to create a view with custom strides, the number of bytes to jump to the following element. It can be helpful to think of a numpy array as a (glorified) chunk of memory, and then strides are a way to map indices to memory address.

For example, in

a = np.arange(10).reshape(2, 5)

a.itemsize equals 4 (ie, 4 bytes or 32 bits for each element) and a.strides is (20, 4) (5 elements, 1 element) so that a[1,2] refers to the element which is 1*20 + 2*4 bytes (or 1*5 + 2 elements) after the first one:

0 1 2 3 4
5 6 7 x x

In fact, the elements are placed in memory one after another, 0 1 2 3 4 5 6 7 x x but the strides let us index it as a 2D array.

Building on that concept, we can rewrite patchify as follows

def patchify(img, patch_shape):
    img = np.ascontiguousarray(img)  # won't make a copy if not needed
    X, Y = img.shape
    x, y = patch_shape
    shape = ((X-x+1), (Y-y+1), x, y) # number of patches, patch_shape
    # The right strides can be thought by:
    # 1) Thinking of `img` as a chunk of memory in C order
    # 2) Asking how many items through that chunk of memory are needed when indices
    #    i,j,k,l are incremented by one
    strides = img.itemsize*np.array([Y, 1, Y, 1])
    return np.lib.stride_tricks.as_strided(img, shape=shape, strides=strides)

This function returns a view of img, so no memory is allocated and it runs in just a few tens of microseconds. The output shape is not exactly what you want, and in fact it must be copied to be able to get that shape.

One has to be careful when dealing with views of an array that are much larger than the base array, because operations can trigger a copy which would need to allocate a lot of memory. In your case, since the arrays isn’t too big and there aren’t that many patches, it should be ok.

Finally, we can ravel the array of patches a bit:

patches = patchify(img, (39,39))
contiguous_patches = np.ascontiguousarray(patches)
contiguous_patches.shape = (-1, 39**2)

This doesn’t reproduce the output of your patchify function because you kind of develop the patches in Fortran order. I recommend you to use this instead because

1. It leads to more natural indexing later on (ie, the first patch is patches[0] instead of patches[:, 0] for your solution).

2. It’s also easier in numpy to use C ordering everywhere because you need less typing (you avoid stuff like order=”F”, arrays are created in C order by default…).

“Hints” in case you insist: strides = img.itemsize * np.array([1, Y, Y, 1]), use .reshape(..., order="F") on contiguous_patches and finally transpose it .T