CODEWITHSUNDEEP
pythonnumpy
David
David

Reputation: 1267

Connected components in a 2D array

Imagine I have a big matrix with a background value of 0 and other points with values > 0, like

array([[1, 2, 2, 1, 0, 0, 0, 0, 0],
       [4, 1, 0, 0, 0, 1, 1, 0, 0],
       [0, 0, 0, 0, 5, 6, 7, 3, 0],
       [0, 0, 0, 4, 7, 3, 2, 1, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0]])

Now, I define a patch as a connected set of points with values > 0. In this example we have 2 patches: one in the upper left corner and one to the medium-right position.

I would like to write in Python an algorithm that finds the number of patches (2 in this case) and the minimum(s) and its (their) coordinates in each patch. It seems difficult. I have thought in K Means or Voronoi diagrams but I am not sure they fit into my problem. I'm still thinking but I appreciate any idea. Thx.

Upvotes: 1

Views: 2551

Answers (2)

yatu
yatu

Reputation: 88226

Seems like you're looking for the connected components of the array. We can use skimage.measure.label to label the different components in the array, and skimage.measure.regionprops for the slices that will give us the found components:

from skimage.measure import label, regionprops

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

l = label(a.clip(0,1))
for s in regionprops(l):
    print(s.slice)
#(slice(0, 2, None), slice(0, 4, None))
#(slice(1, 4, None), slice(3, 8, None))

Note that you can use each (x,y) slice objects to index the corresponding bounding boxes in a, for instance if we take the last slice:

a[s.slice]
array([[0, 0, 1, 1, 0],
       [0, 5, 6, 7, 3],
       [4, 7, 3, 2, 1]])

Which you can easily use to find the corresponding minimums or statistics of interest.

Upvotes: 1

Pani
Pani

Reputation: 1377

This is a well-known problem: Finding connected components in an undirected graph. In this case consider each number to be a node and adjacent numbers (up, down, right, left) to have an edge in between them in the graph. You can use BFS to solve this. There are various resources for this and ever ready code.

For pseudocode take a look at: https://math.stackexchange.com/questions/2699333/finding-connected-components-in-a-graph-using-bfs

Upvotes: 1

Related Questions