Searching a sub-array inside a 2D array (image recognition) [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

Questions asking for code must demonstrate a minimal understanding of the problem being solved. Include attempted solutions, why they didn't work, and the expected results. See also: Stack Overflow question checklist

Closed 8 years ago.

Improve this question

Essentially, I have a numpy image array and I'm trying to find if it contains a 2x2 block of particular RGB pixel values. So, for example, if my (simplified) image array was something like:

A B C D E F

G H I J K L

M N O P Q R

S T U V W X

I am trying to check if it contains, say:

J K

P Q

I'm pretty new to numpy so I'd appreciate any help on this, thanks.

Answer 1

How about this solution:

1) Identify all the locations of the upper-right left-hand element of the small array in the big array.

2) Check if the slice of the big array that corresponds to a every given element is exactly the same as the small array.

Say if the upper left-hand corner element of the slice is 5, we would find locations of 5 in the big array, and then go check if a slice of the big array to the bottom-left of 5 is the same as small array.

import numpy as np

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

b = np.array([[5,6],
              [5,7]])

b2 = np.array([[6,7],
               [6,8],
               [7,9]])

def check(a, b, upper_left):
    ul_row = upper_left[0]
    ul_col = upper_left[1]
    b_rows, b_cols = b.shape
    a_slice = a[ul_row : ul_row + b_rows, :][:, ul_col : ul_col + b_cols]
    if a_slice.shape != b.shape:
        return False
    return (a_slice == b).all()

def find_slice(big_array, small_array):
    upper_left = np.argwhere(big_array == small_array[0,0])
    for ul in upper_left:
        if check(big_array, small_array, ul):
            return True
    else:
        return False

Result:

>>> find_slice(a, b)
True
>>> find_slice(a, b2)
True
>>> find_slice(a, np.array([[5,6], [5,8]]))
False

Answer 2

You can efficiently do it using np.in1d using the flattened arrays of the main array, say a and the sub-array, say b.

Suppose the example:

a = np.random.random((100,50))
i=4
j=8
m=12
n=16
b = a[i:j,m:n]

And adding some repeated incomplete patterns:

a[0,:3] = b[0,:3]
a[4,40:44] = b[0,:]
a[4,44:48] = b[1,:]
a[8,:4] = b[3,:]

The indices where b appears in a can be obtained using:

c = np.where(np.lib.arraysetops.in1d(a.flat,b.flat)==True)[0]
#array([  0,   1,   2, 212, 213, 214, 215, 240, 241, 242, 243, 244, 245, 246, 247, 262, 263, 264, 265, 312, 313, 314, 315, 362, 363, 364, 365, 400, 401, 402, 403], dtype=int64)

See that the first three indices are not your answer, since the pattern is incomplete. You just have to define a rule to check if the pattern is complete, i.e. to check where you have b.shape[0] times a number of b.shape[1] indices belonging to the same line.

Then you have to interpret this in terms of the 2D array:

i = 212/a.shape[1]
j = i+b.shape[0]
m = 212 % a.shape[1]
n = m+b.shape[1]

The challenge is to find 212.