Index of smallest neighbouring cell greater than a value in 2D array

Question

I have a numpy array a:

a = np.array([[0,4,3,9,9,9,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10],
          [4,4,3,5,9,9,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10],
          [4,8,3,9,2,6,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10],
          [4,2,2,9,2,6,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10],
          [4,4,2,9,2,6,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10],
          [4,2,2,2,2,8,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10],
          [4,2,2,2,6,8,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10],
          [4,2,2,2,6,8,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10],
          [4,2,2,2,6,8,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10],
          [4,2,2,2,6,8,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10],
          [4,2,2,2,6,8,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10],
          [4,2,2,9,2,6,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10],
          [4,2,2,2,6,8,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10],
          [4,4,2,2,6,8,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10],
          [4,4,4,3,4,4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10],
          [4,4,4,3,4,4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]])

I'm looking for the index of the smallest neighbours of cell(s) where value= 2 (numpy.where(a==value)) but bigger than value. I also need the index of the corresponding cell(s) = value for which we found the smallest neighbour.

Result in this case (value = 2) should be:

• index of neighbouring cells: [0,2] and [4,3] The corresponding and

• index of corresponding cell(s): [1,2] and [3,3]

Please apologies if the question is not very clear.

This is what I have so far:

import numpy as np
value = 2
neighbors = np.zeros(4, dtype = np.float)
fdx = np.flatnonzero(a== value)
locations = fdx // a.shape[1], fdx % a.shape[1]
maximums = []
for item in zip(*locations):
    i, j = item[0], item[1]
    neighbors[0], neighbors[1], neighbors[2],neighbors[3] = [a[i-1,j], a[i+1,j], a[i,j-1], a[i,j+1]]
    maximums.append(min(neighbors[neighbors> value]))
print np.where(a==min(maximums))

prints: (array([0, 4]), array([2, 3]))

Which is very slow and also still don't know how to find the index of corresponding cells. Any solution which is totally different to my solution would be also accepted.

Answer 1

Using window_nd from a previous answer

def min_search(a, val = 2):
        a_view = window_nd(np.pad(a, ((1, 1),(1, 1)), 'constant',
                           constant_values = np.inf), 3)
        min_val = np.where(a_view[a == val] <= val, np.inf, a_view[a == val]).min()
        neig_mask = np.array([[0, 1, 0], [1, 0, 1], [0, 1, 0]], dtype = bool)
        rev_mask = np.logical_and(np.any(np.logical_and(a_view == min_val,
                                         neig_mask), axis = (-1, -2)), a == val)
        min_mask = np.logical_and(np.any(np.logical_and(a_view == val,
                                         neig_mask), axis = (-1, -2)), a == min_val)

        return np.nonzero(min_mask), np.nonzero(rev_mask)

What this does:

• Creates a sliding window over a padded with val (so the windowed shape is (*a.shape, 3, 3))
• finds the minimum value greater than val among all windows with val at the center (padding allows inlcusion of edges) an assigns it to min_val
• neig_mask restricts neigbors to cardinal directions
• finds windows with min_val in neig_mask positions and val in the center, assigns to rev_mask
• finds windows with val in neig_mask positions and min_val in the center, assigns to min_mask

• returns np.nonzero of min_mask and rev_mask, which are tuples that can be used as an index on a

  min_search(a)
  Out:
  ((array([0, 4], dtype=int32), array([2, 3], dtype=int32)),
  (array([1, 3], dtype=int32), array([2, 3], dtype=int32)))
  

Answer 2

Not sure how much faster (if at all) this is, but it finds the corresponding cells.

import numpy as np

a = np.array([[0,4,3,9,9,9],
          [4,4,2,2,2,9],
          [4,2,2,9,2,6],
          [4,2,2,2,6,8],
          [4,4,4,3,4,4]])

value = 2
idx = np.where(a == value)
idx = zip(idx[0],idx[1])

running_min = np.inf
corresponding_idx = []#corresponding cells
nb_min_list = []#location of neighbors
nb_min_idx = []
for i in idx:
    nb_idx = [(i[0]+1,i[1]),(i[0]-1,i[1]),(i[0],i[1]+1),(i[0],i[1]-1)]#note no check for out of bounds.
    nb_idx = [nb for nb in nb_idx if nb[0] >= 0 and nb[0] < a.shape[0] and nb[1] >= 0 and nb[1] < a.shape[1]]#test for edges

    try:
        nb_min = min([a[nb] for nb in nb_idx if a[nb] > value])
        corresponding_idx.append(i)
        nb_min_list.append(nb_min)
        nb_min_idx.append([nb for nb in nb_idx if a[nb] == nb_min])
    except:
        pass

nb_min_loc = np.where(nb_min_list == min(nb_min_list))[0]
corresponding_cells = []
min_nbs = []
for nb in nb_min_loc:
    corresponding_cells.append(corresponding_idx[nb])
    min_nbs.append(nb_min_idx[nb])

print(corresponding_cells)#[(1, 2), (3, 3)]
print(min_nbs)#[[(0, 2)], [(4, 3)]]

Answer 3

You can find neighbors using scipy.ndimage.morphology.binary_dilation

import numpy as np
from scipy.ndimage import morphology
a = np.array([[0,4,3,9,9,9],
              [4,4,2,2,2,9],
              [4,2,2,9,2,6],
              [4,2,2,2,6,8],
              [4,4,4,3,4,4]])
k = 2

# make mask
eq = a==k
# find greater neighbors (as mask)
nbs = morphology.binary_dilation(eq) & (a>k)
# translate to index
minidx = np.argwhere(nbs & (a == np.min(a[nbs])))

# now find neighbors' neighbors
# pad original mask
m,n = a.shape
eqp = np.zeros((m+2, n+2), bool)
eqp[1:-1,1:-1] = eq
# generate offset vectors for the four major directions (up, down, left, right)
# corrected for padding
offsp = np.array([(0,1),(2,1),(1,0),(1,2)])
# without padding correction
offs = offsp - 1#
# for each minimum, find all (1-4) reference neighbors
refidx = [i + offs[eqp[tuple((i+offsp).T)]] for i in minidx]

print(minidx)
print(refidx)

# [[0 2]
#  [4 3]]
# [array([[1, 2]]), array([[3, 3]])]