How to locate 1-D array in a multi-dimensional array in all possible directions

user_970729 0
Viewed 46

I'm trying to solve an image search issue using NumPy and Pandas for weeks now. Would like to seek for some advice regarding same as I'm stuck and feeling back to square one with any attempt.

  • There're 2 image sets. The first set of images are full images and another set is smaller / cut version (chunks). The smaller chunks can be in any order (flipped, transposed, rotated, etc).
  • Converted both to corresponding NumPy matrices.
  • For simplicity, consider the below 2 matrices. I'm using a smaller size for illustration, but the actuals are 10000x12000 or more.
array([[ 2, 15,  9, 16,  4,  3, 12,  8],
       [ 9,  9,  0, 16,  0,  1, 11, 12],
       [ 9, 10,  6,  3,  2, 12, 19,  2],
       [16,  2,  0,  6,  7,  5,  8,  8],
       [18, 17,  3, 19,  5, 10,  1, 18],
       [10,  7,  0,  0,  8, 17,  6,  4],
       [ 2, 12,  8,  9,  6,  1, 11,  1],
       [ 6,  7, 15, 15, 18, 15, 17, 15]])

and I'm trying to locate the following 1-D array in the earlier matrix.

array([6, 7, 5, 8])

It's in location (3,3) -> (3,4) -> (4,4) -> (5,4), which isn't in a straight line, rather in L-shape as in below:

array([[ False, False, False, False, False, False, False, False],
       [ False, False, False, False, False, False, False, False],
       [ False, False, False, False, False, False, False, False],
       [ False, False, False, True,  True,  False, False, False],
       [ False, False, False, False, True,  False, False, False],
       [ False, False, False, False, True,  False, False, False],
       [ False, False, False, False, False, False, False, False],
       [ False, False, False, False, False, False, False, False]])

The elements from 1-D array aren't in a straight line always, rather can follow any order, like straight-line, L-shape, slanting line, etc. since the image chunks are transformed. This leads to a larger permutations & combinations, so need an efficient way.

So far, I tried to formalize few patterns and locating the position of the each element in the dataframe / matrix by indexing methods and checking for True per element:

np.any(a == 6, axis=0)
np.any(a == 7, axis=1)

It's taking forever to identify 1 pattern and forcing to consider some other solution, which I'm not aware of.

What would be the best way to locate the 1-D array in this multi-dimensional array in any order as mentioned earlier using NumPy and/or Pandas library? Any advice is appreciated. Thank you.

pandas numpy-ndarray python-3.x numpy
1 Answers

IIUC, one way is to convolve a 4 by 4 filter on the main 2-D array. The 4 by 4 squares which contains all of the 4 wanted values are the candidates for further inspection.

for i in range(len(main)-len(to_match)+1):
    for j in range(len(main)-len(to_match)+1):
        filter4 = main[i:i+4, j:j+4]
        if np.sum(np.isin(to_match, filter4))==4:
            print(np.isin(filter4, to_match))
            print('------')
user_72816750
Related