2
import numpy as np

data = np.array([[0, 0, 1, 1, 2, 2],
                 [1, 0, 0, 1, 2, 2],
                 [1, 0, 1, 0, 0, 0],
                 [1, 1, 0, 0, 2, 0]])

How can I do the followings?

Within 2 by 2 patch:

if any element is 2: put 2
if any element is 1: put 1
if all elements are 0: put 0

The expected result is:

np.array([[1, 1, 2],
          [1, 1, 2]])
Fred Foo
  • 355,277
  • 75
  • 744
  • 836
  • What have you tried so far? As it stands this looks like you are asking someone to write code for you. –  May 14 '14 at 04:25
  • 1
    What if both `1` and `2` are present in a block? – user2357112 May 14 '14 at 04:28
  • @Lego Stormtroopr 'As it stands this looks' what does it mean? Sorry, I am not native English speaker. –  May 14 '14 at 04:29
  • It looks like you are asking us to do your work for you as there is no code. –  May 14 '14 at 04:30
  • @user2357112 since priority is given to 2 in the first step, 2 is put. –  May 14 '14 at 04:30
  • @LegoStormtroopr I understand overall meaning of your sentence, but I did not understand how you combine 'As it stands this looks'? I mean structure; just asking because you seems native speaker. –  May 14 '14 at 04:33

4 Answers4

4

Using extract_patches from scikit-learn you can write this as follows (copy and paste-able code):

import numpy as np
from sklearn.feature_extraction.image import extract_patches

data = np.array([[0, 0, 1, 1, 2, 2],
                 [1, 0, 0, 1, 2, 2],
                 [1, 0, 1, 0, 0, 0],
                 [1, 1, 0, 0, 2, 0]])

patches = extract_patches(data, patch_shape=(2, 2), extraction_step=(2, 2))
output = patches.max(axis=-1).max(axis=-1)

Explanation: extract_patches gives you a view on patches of your array, of size patch_shape and lying on a grid of extraction_step. The result is a 4D array where the first two axes index the patch and the last two axes index the pixels within the patch. We then evaluate the maximum over the last two axes to obtain the maximum per patch.

EDIT This is actually very much related to this question

Community
  • 1
  • 1
eickenberg
  • 14,152
  • 1
  • 48
  • 52
  • 1
    Cool - ```extract_patches``` uses ```numpy.lib.stride_tricks.as_strided``` - https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/feature_extraction/image.py – wwii May 15 '14 at 16:32
  • Indeed - (and thanks for noticing, I was proud of that contribution at the time ;)) the cool thing is that numpy makes a copy as soon as you act upon this view with a `.reshape((-1,) + patch_shape)`. That way you push patch extraction down to C level instead of using e.g. a for loop. – eickenberg May 15 '14 at 18:47
2

I'm not sure where you get your input from or where you are supposed to leave the output, but you can adapt this.

import numpy as np

data = np.array([[0, 0, 1, 1, 2, 2],
                 [1, 0, 0, 1, 2, 2],
                 [1, 0, 1, 0, 0, 0],
                 [1, 1, 0, 0, 2, 0]])

def patchValue(i,j):
    return max([data[i][j],
                data[i][j+1],
                data[i+1][j],
                data[i+1][j+1]])

result = np.array([[0, 0, 0],
                   [0, 0, 0]])

for (v,i) in enumerate(range(0,4,2)):
    for (w,j) in enumerate(range(0,6,2)):
        result[v][w] = patchValue(i,j)

print(result)
jspurim
  • 925
  • 8
  • 25
  • 4
    Using `max` is a brilliant idea, but your implementation is not taking full advantage of numpy. This will do the same in a much more numpythonic way: `rows, cols = data.shape; result = np.max(data.reshape(rows//2, 2, cols//2, 2), axis=(1, 3))` – Jaime May 14 '14 at 06:18
  • Which version of numpy do you need to be able to write `axis=(1, 3)`? It doesn't work in my `1.6.1`, but it is a functionality I have always needed. It would make my proposition more concise, too. – eickenberg May 14 '14 at 07:09
  • @Jaime What's difference between rows//2 and rows/2 ? –  May 14 '14 at 10:00
  • @Jaime you are super master, why do not you propose your best solution to this similar question? http://stackoverflow.com/questions/23546931/is-not-it-possible-to-patch-the-2d-array-into-array-of-subarry-using-functions-a –  May 14 '14 at 10:26
  • 1
    @eickenberg I think it is a 1.7 thing. – Jaime May 14 '14 at 14:01
  • 1
    @alps `rows // 2` will always return integer division, while `rows / 2` will do floating point division in Python 3.x, or if you are using `from __future__ import division` in Python 2.x. – Jaime May 14 '14 at 14:03
1

Here's a rather lengthy one-liner that relies solely on reshaping, transposes, and taking maximums along different axes. It is fairly fast too.

data.reshape((-1,2)).max(axis=1).reshape((data.shape[0],-1)).T.reshape((-1,2)).max(axis=1).reshape((data.shape[1]/2,data.shape[0]/2)).T

Essentially what this does is reshape to take the maximum in pairs of two horizontally, then shuffle things around again and take the maximum in pairs of two vertically, ultimately giving the maximum of each block of 4, matching your desired output.

IanH
  • 10,250
  • 1
  • 28
  • 32
  • This is, if I am not mistaken, exactly what @Jaime proposes in his comment further up, with the steps taken separately. – eickenberg May 14 '14 at 07:11
  • Yes it is. I missed his comment. His version is quite a bit more elegant. – IanH May 14 '14 at 15:04
1

If the original array is large, and performance is an issue, the loops can be pushed down to numpy C code by manipulating the shape and strides of the original array to create the windows that you are acting on:

import numpy as np
from numpy.lib.stride_tricks import as_strided

data = np.array([[0, 0, 1, 1, 2, 2],
                 [1, 0, 0, 1, 2, 2],
                 [1, 0, 1, 0, 0, 0],
                 [1, 1, 0, 0, 2, 0]])

patch_shape = (2,2)
data_shape = np.array(data.shape)

# transform data to a 2x3 array of 2x2 patches/windows

# final shape of the computation on the windows can be calculated with:
# tuple(((data_shape-patch_shape) // patch_shape) + 1)
final_shape = (2,3)

# the shape of the windowed array can be calculated with:
# final_shape + patch_shape
newshape = (2, 3, 2, 2)

# the strides of the windowed array can be calculated with:
# tuple(np.array(data.strides) * patch_shape) + data.strides
newstrides = (48, 8, 24, 4)

# use as_strided to 'transform' the array
patch_array = as_strided(data, shape = newshape, strides = newstrides)

# flatten the windowed array for iteration - dim of 6x2x2
# the number of windows is the product of the 'first' dimensions of the array
# which can be calculated with:
# (np.product(newshape[:-len(patch_shape)])) + (newshape[-len(patch_array):])
dim = (6,2,2)

patch_array = patch_array.reshape(dim)

# perfom computations on the windows and reshape to final dimensions
result = [2 if np.any(patch == 2) else
          1 if np.any(patch == 1) else
          0 for patch in patch_array]
result = np.array(result).reshape(final_shape)

A generalized 1-d function for creating the windowed array can be found at Efficient rolling statistics with NumPy

A generalised multi-dimension function and a nice explanation can be found at Efficient Overlapping Windows with Numpy

wwii
  • 23,232
  • 7
  • 37
  • 77
  • The ```extract_patches``` function used by @eickenburg also uses ```as_strided()``` and is another example of a generalized n-dimension solution for *creating* windows to operate on. https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/feature_extraction/image.py – wwii May 15 '14 at 16:36