Counting the number of components/objects in an array

user_2947077 0
Viewed 68

I am wondering what is a good way to count the number of components in a matrix. Let's say that ones constitute a component and zeros constitute the background. So in the array below there are 4 components:

a = np.array([
    [1,1,0,0,0,0,0,0],
    [1,1,1,0,0,0,1,0],
    [0,1,0,0,0,1,1,1],
    [0,0,0,0,0,1,1,1],
    [0,1,0,0,0,0,1,0],
    [0,0,0,1,1,0,0,0],
    [0,0,1,1,0,0,0,0]])

I know that I can do this with Scipy like this:

from scipy.ndimage import label

labeled_array, num_features = label(a)

where num_features will give me the correct answer of 4.

How would I implement this myself? I am asking what the correct technique would be. Preferably I want to implement this with matrix operations (e.g. a Numpy solution). So no for-loops where I am checking every value individually.

I am asking this because in the end I want to implement the solution in Tensorflow such that the whole thing is differentiable. This way I can add the number of components as a term in my loss function for an image segmentation problem, which is my end goal.

I thought of using morphological erosion, to shrink the components in the matrix until only 1s remain. Then I could just take the sum of the array to count the number of components. Unfortunately if I erode an isolated one [[0,0,0],[0,1,0],[0,0,0]] it will remove it ([[0,0,0],[0,0,0],[0,0,0]]). If I repeat erosion it will continue until there are no components left. I also think I could use skeletonization, which garantuees that there would always remain a center-point? But I am not sure if that is the right technique, and how I would implement that.

I was wondering if anyone has any ideas on this problem or knows how to solve it. Any input would be greatly appreciated!

components object numpy arrays python
1 Answers

This can be done in linear time using the flood-fill algorithm. Here is an example:

count = 0
for i in range(a.shape[0]):
    for j in range(a.shape[1]):
        if a[i, j] == 1:
            floodFill(a, i, j)
            count += 1

While this solution use loops, you can use Numba or Cython to mitigate the cost of the function calls and the loops. The resulting code should be very fast.

There is no flood fill algorithm in Numpy but there is one in several image packages like OpenCV or scikit-image for example. You can write your own implementation as long as you use Cython or Numba to speed it up.

Actually, this operation is called segmentation and AFAIK it can be done directly in OpenCV in one pass. Once applied, you could easily count the labelled area using Numpy operation (with something like count = len(np.unique(segmentedResult.flatten())).

I highly doubt once can write an efficient code using only matrix-based Numpy functions here. The morphological erosion method would take a quadratic time assuming it could work correctly. A good scalar algorithm can sometimes outperform any vectorized inefficient algorithm.

user_129395570
Related