Context

Im trying to take an array which consists of 1s and 0s in random locations and then seperate clusters of 1s within this array and label them seperately. I think it is best explained with an example.

On the left I have an example input and on the right is the example output.

My solution

To do this I wrote a recursive function which essentially fills in clusters and I essentially loop through the input array and then if I find one I will call this function to fill in that cluster. I have included python code below.

def search(i,j,dmask,lbls,lbl):

lbls[i,j] = lbl
if (i-1 < dmask.shape[0]) & (j-1 < dmask.shape[1]) & (i-1 >= 0) & (j-1 >= 0):
    if  (dmask[i-1,j-1] == 1) & (lbls[i-1,j-1] == 0):
        search(i-1,j-1,dmask,lbls,lbl)

if (i-1 < dmask.shape[0]) & (j < dmask.shape[1]) & (i-1 >= 0) & (j >= 0):
    if (dmask[i-1,j] == 1) & (lbls[i-1,j] == 0) :
        search(i-1,j,dmask,lbls,lbl)

if (i-1 < dmask.shape[0]) & (j+1 < dmask.shape[1]) & (i-1 >= 0 ) & ( j+1 >= 0 ):
    if ( dmask[i-1,j+1] == 1 ) & ( lbls[i-1,j+1] == 0):
        search(i-1,j+1,dmask,lbls,lbl)

if (i < dmask.shape[0]) & (j-1 < dmask.shape[1]) & (i >= 0 ) & ( j - 1 >= 0 ):
    if (dmask[i,j-1] == 1 ) & ( lbls[i,j-1] == 0 ):
        search(i,j-1,dmask,lbls,lbl)    
        
if (i < dmask.shape[0]) & (j+1 < dmask.shape[1]) & (i >= 0 ) & ( j+1 >= 0 ):
    if (dmask[i,j+1] == 1 ) & ( lbls[i,j+1] == 0):
        search(i,j+1,dmask,lbls,lbl)
        
if (i+1 < dmask.shape[0]) & (j-1 < dmask.shape[1]) & (i+1 >= 0 ) & ( j-1 >= 0 ):
    if ( dmask[i+1,j-1] == 1 ) & ( lbls[i+1,j-1] == 0): 
        search(i+1,j-1,dmask,lbls,lbl)
        
if (i+1 < dmask.shape[0]) & (j < dmask.shape[1]) & (i+1 >= 0 ) & ( j >= 0 ):
    if ( dmask[i+1,j] == 1 ) & ( lbls[i+1,j] == 0):
        search(i+1,j,dmask,lbls,lbl)
        
if (i+1 < dmask.shape[0]) & (j+1 < dmask.shape[1]) & (i+1 >= 0 ) & ( j+1 >= 0 ):
    if (dmask[i+1,j+1] == 1 ) & ( lbls[i+1,j+1] == 0):
        search(i+1,j+1,dmask,lbls,lbl)
return dmask,lbls

Initiliazing the label

lbl = 1;

Input array

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

Intializing the output array

b = np.zeros(np.shape(a),int)

Iterating through the array and calling the recursive function if a 1 is located

for i in np.arange(a.shape[0]):
    for j in np.arange(a.shape[1]):
        if (a[i,j] == 1) & (b[i,j] == 0):
            [c,d] = search(i,j,a,b,lbl)
            lbl += 1;

The problem

This solutions works for small input arrays, for example the picture I have included. However I need it to work on a much larger array which has much larger clusters. This results in my kernel restarting automatically when i run the code. I believe this is because it is hitting the recursion limit although I have tried increasing the recursion limit using the sys.setrecursionlimit() function.

Does anyone have any advice on how I can bypass this issue. I DON’T need to provide my own solution to this problem. If there is a library that does this very easily then that would be great.

Thanks for any help.

Answer

This is an old classical subject in computer vision. In image the “cluster of 1s” is called blob or connected component and the act of identify them is called blob extraction or labeling.

Use opencv library (pip install opencv-python) to find for you all blobs, and filter them out as you wish. In opencv look at connectedComponentsWithStats or findContours or SimpleBlobDetector. You can also search in google for “opencv blob detection” or “opencv connected components”.

How to seperate a 2d mask array into the individual segments within it?

Context

My solution

The problem

Advertisement

Answer