Faster way to extract patches from images?

Question

I am trying to extract patches of fixed size centered at some given position (x,y). The code is given below-

for i,j in zip(indices[0],indices[1]):
    patches.append(
        x[None,
          i-int(np.floor(patch_size/2.0)):i+int(np.floor(patch_size/2.0))+1,
          j-int(np.floor(patch_size/2.0)):j+int(np.floor(patch_size/2.0))+1])

Variable indices is the locations (indices.shape=(2,770)). x is the original image.

But this code is taking 25s seconds time. Can anyone tell me how to make this work faster? or any other alternatives if you can suggest it would be of great help.

Could there be overlap between patches? How would you handle the boundary or near-boundary indices? — Divakar, Jun 18 '16 at 21:05
Yes overlap is there! and boundary condition is handled separately. Btw, the solution worked for me :) Thanks! — Avijit Dasgupta, Jun 19 '16 at 06:20

Divakar · Accepted Answer · 2016-06-18T21:31:33.810

Assuming you are dealing with near-boundary indices separately, as otherwise you would have different shaped patches, let us suggest ourselves a vectorized approach making use broadcasting together with some knowledge about linear-indexing. Posted below is an implementation to go with that philosophy to give us a 3D array of such patches -

m,n = x.shape
K = int(np.floor(patch_size/2.0))
R = np.arange(-K,K+1)                  
out = np.take(x,R[:,None]*n + R + (indices[0]*n+indices[1])[:,None,None])

Let's do a sample run on a minimal input case with input image x of (8,10) and indices are such that the desired patches don't extend beyond the boundaries of the input image. Then, run the original and proposed approaches for verification. Here we go -

1] Inputs :

In [105]: # Inputs
     ...: x = np.random.randint(0,99,(8,10))
     ...: indices = np.array([[4,2,3],[6,3,7]])
     ...:

3] Original approach with output :

In [106]: # Posted code in the question ...

In [107]: patches[0]
Out[107]: 
array([[[92, 21, 84],
        [10, 52, 36],
        [ 5, 62, 61]]])

In [108]: patches[1]
Out[108]: 
array([[[71, 76, 75],
        [80, 32, 55],
        [77, 62, 42]]])

In [109]: patches[2]
Out[109]: 
array([[[16, 88, 31],
        [21, 84, 51],
        [52, 36,  3]]])

3] Proposed approach with output :

In [110]:  # Posted code in the solution earlier ...

In [111]: out
Out[111]: 
array([[[92, 21, 84],
        [10, 52, 36],
        [ 5, 62, 61]],

       [[71, 76, 75],
        [80, 32, 55],
        [77, 62, 42]],

       [[16, 88, 31],
        [21, 84, 51],
        [52, 36,  3]]])

what if I am looking for batches at (7,9) or (1,10)? something like: `indices = np.array([[1,1,7],[1,10,9]])` ? your method give an error: `IndexError: index 80 is out of bounds for size 80` — Farid Alijani, Oct 23 '19 at 11:35

score 2 · Answer 2 · answered Jun 19 '16 at 11:19

Using scikit-learn:

from sklearn.feature_extraction.image import extract_patches

all_patches = extract_patches(x, patch_size)

upper_left = indices - patch_size // 2
patches = all_patches[upper_left[0], upper_left[1]]

A similar function can be found in scikit-image: view_as_windows.

Faster way to extract patches from images?

2 Answers2

Linked