Finding connected components in a pixel-array

Question

I have a pixel-array like the array below and from that I want to distinguish the two "groups" of 1s. The plan is to do this in a large set of similar pixel-arrays so I need to find a way to do this efficient.

Maybe I can add all the 1-positions to a separate array and do some search to find the ones connected, but it should be some better way. Is there any algorithms for finding connected components like this?

[
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]

It goes by the various names of "Image Segmentation", "Connected Component Analysis", "labelling" and "Blob Analysis" - depending on your goal and background. — Mark Setchell
– Mark Setchell, Commented Oct 13, 2017 at 20:20
You can encode each matrix as a graph and search for connected components. This will work as long as the "groups" do not "touch". Alternatively, you can run some flavour of K-means clustering, which will work as long as you know the number of components beforehand. There are many other options, but as you might've noticed, we need more details on your data, i.e. what assumptions can be made: do you know the number of groups, are they linearly separable, can they "touch" each other... — Eli Korvigo
– Eli Korvigo, Commented Oct 13, 2017 at 21:06
What you want to do sounds a lot like flood filling to me, so looking at algorithms that do that might prove fruitful (although a Pure Python implementation of one might be too slow). — martineau
– martineau, Commented Oct 13, 2017 at 21:16
Pure Python is very slow for this task, consider using scipy or OpenCV or the like to do labeling/connected component. They are very fast. I've implemented connected components in pure Python and it was very very slow. — alkasm
– alkasm, Commented Oct 13, 2017 at 21:18
Thanks for the replies, I will look into them and see if I find something that suits me. @EliKorvigo They can't touch and they are always two in each image, but unfortunately not linear separable. — gugge
– gugge, Commented Oct 13, 2017 at 21:48

shantanuo · Accepted Answer · 2020-01-12 13:12:06Z

Considering that the groups should never touch each other, you can use scipy.ndimage.measurements.label to label the groups:

In [1]: import numpy as np

In [2]: from scipy.ndimage.measurements import label

In [3]: array = np.array(...)  # your example

In [4]: structure = np.ones((3, 3), dtype=np.int)  # this defines the connection filter

In [5]: structure  # in this case we allow any kind of connection
Out[5]: 
array([[1, 1, 1],
       [1, 1, 1],
       [1, 1, 1]])

In [6]: labeled, ncomponents = label(array, structure)

In [7]: labeled
Out[7]: 
array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], dtype=int32)

In [7]: ncomponents
Out[7]: 2

Although I haven't read the particular implementation, SciPy tends to use highly efficient algorithms implemented in C, hence the performance should be relatively high. You can then extract the indices for each group using NumPy:

In [8]: indices = np.indices(array.shape).T[:,:,[1, 0]]

In [9]: indices[labeled == 1]
Out[9]: 
array([[ 1,  6],
       [ 1,  7],
       [ 2,  6],
       [ 2,  7],
       [ 2,  8],
       [ 2,  9],
       [ 2, 10],
       [ 2, 11],
       [ 2, 12],
       [ 2, 13],
       [ 3, 11],
       [ 3, 12],
       [ 3, 13]])

In [10]: indices[labeled == 2]
Out[10]: 
array([[ 5,  1],
       [ 6,  1],
       [ 7,  1],
       [ 7,  2],
       [ 8,  1],
       [ 8,  2],
       [ 9,  2],
       [10,  2],
       [10,  3],
       [11,  2],
       [11,  3],
       [12,  3],
       [13,  3]])

I have a question, if want to group with value of range? like instead of group all those with value of 1 I group the values of 1 - 3? i mean, giving an epsilion of range of values
DeprecationWarning: Please use label` from the scipy.ndimage namespace, the scipy.ndimage.measurements namespace is deprecated.`

Collectives™ on Stack Overflow

Finding connected components in a pixel-array

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related