Checking if Adjacent Values are in a Numpy Matrix

Question

So, I am currently trying to figure out a more optimal solution to determine connected components in an image. Currently, I have an array with coordinates that have certain values. I want to create groups of these coordinates based on if they are touching. I am using a numpy array, and currently I have to check if each value (top left, top middle, top right, middle-left, middle right, bottom left, bottom middle, bottom right) is in that array. I do so via this code:

for x in range (0, groupCoords.shape[0]):
            global tgroup
            xCoord = groupCoords.item((x,0))
            yCoord = groupCoords.item((x,1))
            new = np.array([[xCoord, yCoord]])
            if np.equal(Arr,[xCoord, yCoord+1]).all(1).any():
                tgroup = np.append(tgroup, [[xCoord,yCoord+1]], axis=0)
                new = np.append(new, [[xCoord,yCoord+1]], axis=0)
                index = np.argwhere((Arr == [xCoord,yCoord+1]).all(1))
                Arr = np.delete(Arr, (index), axis=0)

            if np.equal(Arr,[xCoord, yCoord-1]).all(1).any():
                tgroup = np.append(tgroup, [[xCoord, yCoord-1]],axis=0)
                new = np.append(new, [[xCoord,yCoord-1]], axis=0)
                index = np.argwhere((Arr == [xCoord,yCoord-1]).all(1))
                Arr = np.delete(Arr, (index), axis=0)

            if np.equal(Arr,[xCoord+1, yCoord]).all(1).any():
                tgroup = np.append(tgroup, [[xCoord+1,yCoord]],axis=0)
                new = np.append(new, [[xCoord+1,yCoord]], axis=0)
                index = np.argwhere((Arr == [xCoord+1,yCoord]).all(1))
                Arr = np.delete(Arr, (index), axis=0)

            if np.equal(Arr,[xCoord+1, yCoord+1]).all(1).any():
                tgroup = np.append(tgroup, [[xCoord+1,yCoord+1]],axis=0)
                new = np.append(new, [[xCoord+1,yCoord+1]], axis=0)
                index = np.argwhere((Arr == [xCoord+1,yCoord+1]).all(1))
                Arr = np.delete(Arr, (index), axis=0)

            if np.equal(Arr,[xCoord+1, yCoord-1]).all(1).any():
                tgroup = np.append(tgroup, [[xCoord+1,yCoord-1]],axis=0)
                new = np.append(new, [[xCoord+1,yCoord-1]], axis=0)
                index = np.argwhere((Arr == [xCoord+1,yCoord-1]).all(1))
                Arr = np.delete(Arr, (index), axis=0)

            if np.equal(Arr,[xCoord-1, yCoord]).all(1).any():
                tgroup = np.append(tgroup, [[xCoord-1,yCoord]],axis=0)
                new = np.append(new, [[xCoord-1,yCoord]], axis=0)
                index = np.argwhere((Arr == [xCoord-1,yCoord]).all(1))
                Arr = np.delete(Arr, (index), axis=0)

            if np.equal(Arr,[xCoord-1, yCoord+1]).all(1).any():
                tgroup = np.append(tgroup, [[xCoord-1,yCoord+1]],axis=0)
                new = np.append(new, [[xCoord-1,yCoord+1]], axis=0)
                index = np.argwhere((Arr == [xCoord-1,yCoord+1]).all(1))
                Arr = np.delete(Arr, (index), axis=0)

            if np.equal(Arr,[xCoord-1, yCoord-1]).all(1).any():
                tgroup = np.append(tgroup, [[xCoord-1,yCoord-1]],axis=0)
                new = np.append(new, [[xCoord-1,yCoord-1]], axis=0)
                index = np.argwhere((Arr == [xCoord-1,yCoord-1]).all(1))
                Arr = np.delete(Arr, (index), axis=0)

However, this clearly takes a significant amount of time if the image is large. I had the idea to just create an boolean matrix with dimensions of the width and height of the image, and then assign the value "true" to values in the matrix which correspond to pixels in the image (the image is black-white).

I was wondering, is it possible to, instead of having to check each value like that, determine if their are elements labled "true" directly surrounding another "true" value?

This is what the input array would look like:

[
 [0 0]
 [0 1]
 [0 2]
 [10 2]

]

The output would look like

[
 [0 0]
 [0 1]
 [0 2]
]

The function I am hoping to refine would check if the "true" values are touching, and create a 'network' of all values touching (it would keep running with the new values found).

Does the order of coordinates matter? I guess we are filtering out coordinates there. Like do you need them in the order they are connected from one end to another (if applicable) or some other criteria? — Divakar
– Divakar, Commented Jan 1, 2017 at 20:34
Could you give a small example of the input (say a 4x4 array) and the expected output? — Warren Weckesser
– Warren Weckesser, Commented Jan 1, 2017 at 20:35
@Divakar The order does not matter, I just need to group them into an array. I am using this as an OCR method, so what it is doing is creating a list of the connected components, which ends up being each character in the image. — Trevor Judice
– Trevor Judice, Commented Jan 1, 2017 at 20:40
@WarrenWeckesser I included a sample input. What the function would do is take in coordinates in the array, lets say (1, 4) for example. It would then check the values directly next to this, and output an array which would be [(0,4), (1,3), (1,5), (2,4), (2,5)] — Trevor Judice
– Trevor Judice, Commented Jan 1, 2017 at 20:47
Thanks. That sounds like it might be a detail of the implementation. You say you want to "create a 'network' of all values touching", so at a higher level, would it be correct to say that the input is the boolean array, and the output is a collection (e.g. a list) of collections of coordinates, one (outer) collection for each connected component? E.g. If the input is [[T, T, F, F], [F, F, F, T], [F, F, F, T]], the output would be something like [[(0, 0), (0, 1)], [(1, 3), (2, 3)]]? — Warren Weckesser
– Warren Weckesser, Commented Jan 1, 2017 at 21:42

Divakar · Accepted Answer · 2017-01-01 21:26:58Z

Approach #1

We could get the euclidean distances and see if any of the distances is within sqrt(2), which would cover up-down with distance = 1 and diagonal with distance = sqrt(2). This would give us a mask, which when indexed into the group coordinates array would give us the connected ones from it.

Thus, an implementation using Scipy's cdist for getting those euclidean distances, would be -

from scipy.spatial.distance import cdist

out = groupCoords[(cdist(groupCoords,Arr)<1.5).any(1)]

Sample run -

In [401]: Arr
Out[401]: 
array([[ 5,  4],
       [11, 12],
       [ 5,  3],
       [ 1,  3],
       [15,  8],
       [55, 21]])

In [402]: groupCoords
Out[402]: 
array([[2, 3],  # In neighbourhood of (1,3)
       [5, 6],
       [6, 2],  # In neighbourhood of (5,3)
       [5, 3],  # In neighbourhood of (5,4)
       [5, 8]])

In [403]: groupCoords[(cdist(groupCoords,Arr)<1.5).any(1)]
Out[403]: 
array([[2, 3],
       [6, 2],
       [5, 3]])

Approach #2

Another way would be checking with absolute element-wise differences between the first columns of the two arrays and similarly for the second columns. Finally, get a joint mask from these two masks and checking any match and indexing again into group array for the filtered coordinates.

Thus, implementation for such a method would be -

col0_mask = (np.abs(groupCoords[:,0,None] - Arr[:,0])<=1)
col1_mask = (np.abs(groupCoords[:,1,None] - Arr[:,1])<=1)
out = groupCoords[(col0_mask & col1_mask).any(1)]

Approach #3

Another approach and probably would be better if you have Arr as a boolean array instead of as a 2-column coordinates array. The idea is to dilate this boolean array of Arr and then see which coordinates from groupCoords would also lie in this dilated image. For the dilation, we would use a 3 x 3 kernel of all ones to cover all of those neighborhood places. For detecting those common points, we need to draw an image with those groupCoords.

Thus, the code would be -

from scipy.ndimage.morphology import binary_dilation

img = np.zeros(Arr.shape,dtype=bool)
img[groupCoords[:,0],groupCoords[:,1]] = 1
out = np.argwhere(binary_dilation(Arr,np.ones((3,3))) & img)

Sample run -

In [444]: # Inputs : groupCoords and let's create a sample array for Arr
     ...: groupCoords = np.array([[2,3],[5,6],[6,2],[5,3],[5,8]])
     ...: 
     ...: Arr_Coords = np.array([[5,4],[11,12],[5,3],[1,3],[15,8],[55,21]])
     ...: Arr = np.zeros(Arr_Coords.max(0)+1,dtype=bool)
     ...: Arr[Arr_Coords[:,0], Arr_Coords[:,1]] = 1
     ...: 

In [445]: img = np.zeros(Arr.shape,dtype=bool)
     ...: img[groupCoords[:,0],groupCoords[:,1]] = 1
     ...: out = np.argwhere(binary_dilation(Arr,np.ones((3,3))) & img)
     ...: 

In [446]: out
Out[446]: 
array([[2, 3],
       [5, 3],
       [6, 2]])

Warren Weckesser · Accepted Answer · 2017-01-01 22:00:43Z

Depending on the ultimate goal of your code, you might find scipy.ndimage.label and its relatives useful.

For example,

In [44]: from scipy.ndimage import label

In [45]: x
Out[45]: 
array([[ True,  True, False, False,  True],
       [False, False, False,  True,  True],
       [False,  True, False,  True, False],
       [ True,  True, False, False, False]], dtype=bool)

In [46]: x.astype(int)  # More concise, easier to read
Out[46]: 
array([[1, 1, 0, 0, 1],
       [0, 0, 0, 1, 1],
       [0, 1, 0, 1, 0],
       [1, 1, 0, 0, 0]])

label returns two values. The first is an array with the same size as the input array. Each distinct connected component in the input is assigned an integer value, starting at 1. The background is 0. The second return value is the number of components found.

In [47]: labeled_arr, nlabels = label(x)

In [48]: nlabels
Out[48]: 3

In [49]: labeled_arr
Out[49]: 
array([[1, 1, 0, 0, 2],
       [0, 0, 0, 2, 2],
       [0, 3, 0, 2, 0],
       [3, 3, 0, 0, 0]], dtype=int32)

In the follwing, where(labeled_array = i) returns a tuple containing two arrays. These arrays are the row and column indices, resp., of the connected components:

In [50]: for i in range(1, nlabels+1):
    ...:     print(where(labeled_arr == i))
    ...:     
(array([0, 0]), array([0, 1]))
(array([0, 1, 1, 2]), array([4, 3, 4, 3]))
(array([2, 3, 3]), array([1, 0, 1]))

You can zip those together to convert them to lists of (row, col) pairs:

In [52]: for i in range(1, nlabels+1):
    ...:     print(list(zip(*where(labeled_arr == i))))
    ...:     
[(0, 0), (0, 1)]
[(0, 4), (1, 3), (1, 4), (2, 3)]
[(2, 1), (3, 0), (3, 1)]

Collectives™ on Stack Overflow

Checking if Adjacent Values are in a Numpy Matrix

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related